Re: computer-go: transpositions

[Vincent Diepeveen <diep@xxxxxxxxx>]

At 02:26 PM 3/30/00 +0100, you wrote:
>My name is Mikael Thulin and I was a member of the computer-go
>mailing list before it moved to it's current location. I have now
>for fun started a small project, writing a tsumego solver for
>use on web-pages, therefore my new interest in this list
>
>Is there a way to retrieve (all) previous postings from this list?
>I better catch up on previous subjects before I enter the discussion.
>
>Well, I take my chance and start with a implementation question:
>
>Implementing the transposition table for my tsumego solver shows
>to be a bit trickier than it have been in programs for other games.
>The presence of the ko rule gives that I have to include information
>about illegal points into the hash code for all positions. It also
>gives that I have to play/try all moves and see if they are legal
>before I can search for a position in the transposition table. One
>way to exclude the check for legal moves is to never store/use
>transpositions after a capture move. This works well unless you
>want to use the super-ko rule. With the super-ko rule illegal points
>can occur even without a previous capture. However in a tsumego
>solver the super-ko rule is preferable as it also prevent the search
>from running into useless eternal loops.
>
>Is there any other simple way prevent these loops?

Yes, just hash the properties. That leads to a different hash so
false transpositions aren't possible then. Debugging such an incremental
hash in any game is very needed though. of course with a function
which at each leaf compares the incremental hash with a new generated 
hash from the position.

In general you should not skip checking hash. Just hash properties that
can change the position. Skipping to store/retrieve hash values
takes care you get a false scored backtracked more near the root where 
the next iteration it might hurt. 

>How does other programs approach the usage of transposition tables?
>Have I missed something important?

>Please excuse my bad English.

We all have to deal with that problem...

>Regards,
>Mikael Thulin

>
>
>