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 

Skipping duplicat moves
Post new topic    TalkChess.com Forum Index -> Computer Chess Club: Programming and Technical Discussions Flat
View previous topic :: View next topic  
Author Message
H.G.Muller



Joined: 10 Mar 2006
Posts: 21481
Location: Amsterdam

PostPost subject: Re: Skipping duplicat moves    Posted: Tue Dec 05, 2017 10:35 am Reply to topic Reply with quote

OK, that is a good point. All-nodes will in generally have no hash move, and the problem would not arise. So only the cut-nodes have to be considered. The calculation hinges on postponing the hash-move removal until after the hash move has been searched, though.

This suggests the best approach would be to explicitly test whether the next move in line happens to be a duplicat of the hash move, and skip it if it is. Then the test overhead is maximally delayed, and every cutoff occurring before it would relieve you of making the test for the remaining moves. The only downside is that you would then also make this test on all moves in all-nodes (where it always fails, because the hash move was invalid), unless you use different search routines for all-nodes and cut-nodes (or actually for nodes with hash move and without). You would not have that problem if you would locate it as a separate loop through the move list in the part of the code that searches the hash move, after you established that it did not cut. (And have a call to move generation from there.)

This still would not solve the problem with the IID, however. If during one of the IID iterations a particular move was deepened beyond the iteration depth, because it seemed to be a cut move, but in the end did not live up to the promise, it would still rely on the hash hit to prevent duplicat searches of that move in later iterations. Which is usually fine if you have a hash table, but rather costly if you have none (or a too-heavily-loaded one). If you would have a method for solving that, it would solve the duplicat hash and killer problem as a free side effect.

So I still like the idea of 'caching' all daughter hash entries in the local variables of the node, where they can never be overwritten. Keeping this info can be very affordable even in situations where memory is too cramped for a general TT. It only takes something like 256-512 bytes per ply. It seems important to keep at least the cut-move of the daughters for all daughters, because it is even important when it was obtained at a lower depth than the now requested one, for use as hash move. So even if in one IID iteration in an all-node did not search any of the moves deeper then necessary to establish their fail low, the cut-moves would still be used in the next iteration.

In fact you could get even more mileage out of this: very often the situation will occur during search of late moves in an all-node at ply N, the moves have similar refutations (e.g. through the same killer at ply N+1). This means that the all-node granddaughters at ply N+2 will be searched immediately after each other, at that level, and that the second one would thus inherit the cached info on the daughters of its cousin. So counting from the node at ply N, there would be a counter-move table for the move sequences

pointless - killer - X - anti-X

and we are now in a position

pointless' - killer - X

It seems there is an appreciable chance here that the move anti-X would do a good job at refuting X here as well. I am not sure it deserves to be tried as hash move, but it should definitely be eligible as killer. This seems to be dependent on the move at ply N+1 being the same. So it seems a good idea to store with the counter-move table which move was used to reach the position that created it. If a cousin then inherits that table, and finds it was reached by the same move, as for which the table was made, it could try to use the moves in that table, passing the relevant counter move for what it tries to its daughter. This is a sort of 'hyper-killer' scheme that inherits killers not from sibblings but from grand-cousins (is that the proper term?), in a way that keeps the two preceding ply equal (and only the ply before that different). This could be useful even in engines that do have a hash table, as normal hash probing would not provide such information. (Of course 'analogy probing', where you keep probing the tree of a sibbling late move in addition to your own, could provide it, even for deeper plies.)
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Subject Author Date/Time
Skipping duplicat moves H.G.Muller Sun Dec 03, 2017 10:30 pm
      Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 9:08 am
      Re: Skipping duplicat moves Steve Maughan Mon Dec 04, 2017 2:00 pm
            Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 2:52 pm
                  Re: Skipping duplicat moves Steve Maughan Mon Dec 04, 2017 3:07 pm
                        Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 6:16 pm
      Re: Skipping duplicat moves Álvaro Begué Mon Dec 04, 2017 6:17 pm
            Re: Skipping duplicat moves H.G.Muller Mon Dec 04, 2017 6:50 pm
                  Re: Skipping duplicat moves Sven Schüle Mon Dec 04, 2017 10:19 pm
                        Re: Skipping duplicat moves H.G.Muller Tue Dec 05, 2017 10:35 am
                              Re: Skipping duplicat moves Michael Sherwin Mon Dec 11, 2017 10:48 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