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: Mon Dec 04, 2017 9:08 am Reply to topic Reply with quote

The bare-bones idea underlying all this is of course to have a table indexed by move (e.g. like the history table), for each ply level, to be used for marking moves that have already been done before in that node. Like

Code:
char alreadyDone[MAXPLY][64*64];


When you enter search the table can be assumed to be empty (i.e. all zeros). When then searching hash or killers before move generation, you would then flag that through code like

Code:
alreadyDone[ply][hashMove] = 1;


The move loop would then contain the code

Code:
if(alreadyDone[ply][move]) { alreadyDone[ply][move] = 0; continue; }


before the MakeMove(). You would just have to make sure to always clean up before leaving the node, by clearing the flags you set for hash and killers. This because you might never get to the duplicat (which would also clear it) because of a beta cutoff through a move ecountered earlier.

This allows testing for duplication of a number of moves with just one simple test of the alreadyDone flags, which needs to be done at the latest possible time (maximizing the chaces it wouldn't have to be done at all). That is a lot more efficient than running through the move list in advance, to hunt for the duplicat and remove it.

The rest of the story is just dressing it up, to reduce the memory requirement by packing the move to be used for table index, and to also use it as a poor-man's substitute for a hash table.
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