[Commit] RRbot README.stopT,NONE,1.1

Adam Ingram-Goble commit at keithp.com
Thu Jun 12 16:40:06 PDT 2003

Committed by: adamaig

Update of /local/src/CVS/RRbot
In directory home.keithp.com:/tmp/cvs-serv19652

Added Files:
Log Message:

--- NEW FILE: README.stopT ---

The stop table was implemented by extending the HashMap that generates
a set of zobrist keys for the game board presented to it.  The Map was used to
allow for key collisions, while only replacing key-value pairings where the
values were equal. The table was used for preventing researching of subtrees
by checking for containment of a value with a shorter known path, and only
pruning the paths that have a longer known path.  If the same state is 
already present in the table with a shorter path ( g-value ) then it is
assumed that the path has already been searched, and the move taken to generate
that state is reversed, and the search proceeds on with the next move 
generated. If the state is not contained in the stop table, then the children of
that state are searched.  Upon return from searching all children down to the
maximum depth, all mappings for the current node's key are removed from the
table, and the current state is inserted.  This allows the search to take
advantage of previouslyy searched nodes that had the same key, but not
the same state.  Only after this removal is the current mapping added to the
stop table, to allow futher searching to take advantage of this information.

It may be possible to have even better performance by using a HashSet instead
of a HashMap to eliminate the need to remove the mappings. This should be 
possible since set equality would be based on the state, not a hashkey.

More information about the Commit mailing list