ChessUSA.com TalkChess.com
Hosted by Your Move Chess & Games
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

SEE on non-capture moves in main search
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
Robert Hyatt



Joined: 27 Feb 2006
Posts: 15820
Location: Birmingham, AL
PostPost subject: Re: SEE on non-capture moves in main search    Posted: Mon Apr 02, 2007 2:05 am Reply to topic Reply with quote
hgm wrote:
bob wrote:
Then please cite a solution to the following problem. A hardware chess implementation is a finite state machine with a static cycle-time. So how are you going to implement a SEE that can do its thing in one cycle that is a constant-time thing? You can't. Either you stretch the cycle time out horrendously to allow for the max SEE run-time when there are lots of pieces bearing on the square, or you end up with a SEE that can't complete in the synchronous timing required by the hardware.

That is _the_ reason MVV/LVA was developed. Because it is a constant-time algorithm that lends it self well to hardware implementations...

Perhaps this hard-ware business is a bit off topic, but nevertheless very interesting. You seem to argue from the assumption that there exists nothing else but SEE and pure MVV/LVA. "SEE is too difficult, so the only viable solution is MVV/LVA."


Not quite. What I am saying is that MVV/LVA is the only (so far) viable algorithm for a FSM-type implementation, which is what we need for a hardware implementation, at least implementations that look like belle/deep thought/Hydra. No one has proposed any other type of implementation due to the clock cycle time having to be the same every cycle.


Quote:


Well, MVV/LVA has obvous shortcomings w.r.t. the HxL captures, and there are plenty of ways to improve on that even within the restictions of fixed-length algorithms. BLIND is one of them (reduce the victim value to zero or one for pieces that are defended, before applying MVV/LVA sorting). Especially in hardware, where basing a decision on extra information often does ot require any additional time at all, as the extra information can be computed in parallel. (Of course there is a trade-off here as well, as transistors or gates are also not an unlimited resource.)


That would stretch the clock cycle time for _everything" since the clock cycle time has to be long enough for the most complex circuit in the thing to settle. MVV/LVA requires two minor cycles in a hardware implementation. First cycle is find the most valuable attacked piece (victim), second cycle is to find the least valuable piece defending that piece. If you add another "thing" then you increase the basic clock cycle time by 50% which is murderous for speed.


Quote:


For the balancing of process time of different units, one generally uses pipe-lining. I have no experience at all in designing hard-ware Chess machines. (Looks like fun, though, so who knows? Micro-Max seems simple enough to implement in hardware. Perhaps I will return with a matchbox-size version of it some day after all! Laughing ) Seems to me, though, that a cleverly designed hardware move generator can just as easily generate moves for both sides at once as just for the side to move, so that the information which squares are defended is freely available.


That kind of information is not in a usable form. You still have to extract the parts that are pertinent to the current capture, and that takes time. MVV/LVA just answers the question in two easy steps. More steps = slower cycle time.

Quote:


You still did not answer my question about what exactly you are testing now. It would be a pity if your conclusion was based on a theoretically sub-optimal alternative ordering. And within the assumptions where SEE is a mainingful quantity (which is that none of the moves has any side effects w.r.t. captures on other squares) the sorting on



I have taken current Crafty, and for non-losing captures (as proven by SEE) I then re-order them using MVV/LVA. I do this everywhere I would normally sort captures by SEE. I did not try to make it as efficient as possible since I am not (currently) worried about the time cost. I am only looking at tree sizes for identical fixed-depth searches, one using my normal SEE ordering, one using the MVV/LVA ordering for non-losing captures...



Quote:


(Victim<Attacker ? (SEE&1 || SEE<=0 ? SEE : Victim) : Victim) - 0.01*Attacker

is provably better than the others in singling out the move with the best score.

Of course there are situations where your first priority is not to get the best move in front, but just a good-enough one. (If beta is not much above eval.) There you might want to go for the cut-score SEE with the shortest sequence. So if window-dependent ordering is an option, further improvement is still possible.
Back to top
View user's profile Send private message
Display posts from previous:   
Subject Author Date/Time
SEE on non-capture moves in main search Gary Wed Mar 28, 2007 11:25 pm
      Re: SEE on non-capture moves in main search Robert Hyatt Thu Mar 29, 2007 1:17 am
            Re: SEE on non-capture moves in main search Tord Romstad Thu Mar 29, 2007 10:03 am
                  Re: SEE on non-capture moves in main search ed Thu Mar 29, 2007 1:34 pm
                        Re: SEE on non-capture moves in main search Sam Hamilton Fri Mar 30, 2007 12:07 am
                        Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:46 am
                  Re: SEE on non-capture moves in main search Robert Hyatt Thu Mar 29, 2007 9:35 pm
                        Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 10:27 pm
                              Re: SEE on non-capture moves in main search Robert Hyatt Fri Mar 30, 2007 12:05 am
                                    Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 6:50 am
                                          Re: SEE on non-capture moves in main search Robert Hyatt Fri Mar 30, 2007 9:27 pm
                                                Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 10:29 pm
                                                      Re: SEE on non-capture moves in main search Robert Hyatt Sun Apr 01, 2007 1:51 am
                                                            Re: SEE on non-capture moves in main search Tord Romstad Sun Apr 01, 2007 7:54 am
                                                                  Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 1:57 am
                                                            Re: SEE on non-capture moves in main search H.G.Muller Sun Apr 01, 2007 10:22 am
                                                                  Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 2:05 am
                                                                        Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 12:31 pm
                                                                              Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 3:56 pm
                                                                                    Re: SEE on non-capture moves in main search Steven Edwards Mon Apr 02, 2007 4:44 pm
                                                                                          Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 4:59 pm
                                                                                          Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 6:44 pm
                                                                                          Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 6:40 pm
                                                                                    Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 4:53 pm
                                                Re: SEE on non-capture moves in main search H.G.Muller Sat Mar 31, 2007 8:38 am
                                                      Re: SEE on non-capture moves in main search Robert Hyatt Sun Apr 01, 2007 1:59 am
                                                            Re: SEE on non-capture moves in main search Tord Romstad Sun Apr 01, 2007 7:58 am
                                                                  Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 3:57 pm
                                                                  Re: SEE on non-capture moves in main search Peter Fendrich Mon Apr 02, 2007 5:19 pm
                                                                        Re: SEE on non-capture moves in main search Robert Hyatt Mon Apr 02, 2007 6:46 pm
                                                                        Re: SEE on non-capture moves in main search Tord Romstad Mon Apr 02, 2007 6:51 pm
                                                                              Re: SEE on non-capture moves in main search Peter Fendrich Mon Apr 02, 2007 7:53 pm
                                                                                    Re: SEE on non-capture moves in main search H.G.Muller Mon Apr 02, 2007 9:01 pm
                                                                                          Re: SEE on non-capture moves in main search Peter Fendrich Mon Apr 02, 2007 9:30 pm
                                                                                          Re: SEE on non-capture moves in main search H.G.Muller Tue Apr 03, 2007 8:46 am
                                                                                          Re: SEE on non-capture moves in main search Peter Fendrich Tue Apr 03, 2007 10:29 am
                                                                                          Re: SEE on non-capture moves in main search Robert Hyatt Tue Apr 03, 2007 9:23 pm
                                                                                          Re: SEE on non-capture moves in main search Tord Romstad Wed Apr 04, 2007 2:38 pm
                                                                                          Re: SEE on non-capture moves in main search Peter Fendrich Wed Apr 04, 2007 7:49 pm
                                                                                          Re: SEE on non-capture moves in main search Tony Tue Apr 03, 2007 10:54 am
                                                                                          Re: SEE on non-capture moves in main search Robert Hyatt Tue Apr 03, 2007 9:24 pm
                                                                                          Re: SEE on non-capture moves in main search H.G.Muller Tue Apr 03, 2007 9:29 pm
                                    Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:40 am
                              Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:54 am
                                    Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 1:28 pm
                                          Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 4:41 pm
                        Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 11:30 am
                              Re: SEE on non-capture moves in main search Uri Blass Fri Mar 30, 2007 11:50 am
                                    Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 10:32 pm
                              Re: SEE on non-capture moves in main search H.G.Muller Fri Mar 30, 2007 12:16 pm
                              Re: SEE on non-capture moves in main search Robert Hyatt Fri Mar 30, 2007 9:32 pm
                                    Re: SEE on non-capture moves in main search Tord Romstad Fri Mar 30, 2007 10:00 pm
      Re: SEE on non-capture moves in main search Mark Lefler Thu Mar 29, 2007 6:30 am
      Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 9:28 am
            Re: SEE on non-capture moves in main search Tord Romstad Thu Mar 29, 2007 10:13 am
                  Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 12:03 pm
                        Re: SEE on non-capture moves in main search Tord Romstad Thu Mar 29, 2007 12:39 pm
                              Re: SEE on non-capture moves in main search H.G.Muller Thu Mar 29, 2007 2:15 pm
                                    Re: SEE on non-capture moves in main search Zach Wegner Thu Mar 29, 2007 9:10 pm
                  Re: SEE on non-capture moves in main search Steven Edwards Thu Mar 29, 2007 2:18 pm
                  Re: SEE on non-capture moves in main search Rob Sun Apr 01, 2007 6:01 pm
      Re: SEE on non-capture moves in main search Gary Sun Apr 01, 2007 8:26 am
      Re: SEE on non-capture moves in main search Markoff Thu Apr 05, 2007 11:25 pm
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum




Powered by phpBB © 2001, 2005 phpBB Group
Enhanced with Moby Threads