[computer-go] KO in Hashtable-UCT?

[Peter Drake]

It took me a long time to get around my mental block and accept the  
advice of everyone here, but your intuition is correct: superko is so  
rare, and so expensive to detect, that you should NOT check for it on  
every move.

Orego's current approach is:

During search, just maintain a single ko point and ignore superko.  
(There is a maximum number of moves per game to prevent infinitely  
long games.)

After search, when actually making a move:
1) Make a copy of the board
2) Compute the Zobrist hash of the current position from scratch
3) Check for superko violations (against a stack of previous Zobrist  
hashes for positions in the real game,)
4) If there is a violation, go back to the copy and try the next best  
move

Thanks,

Peter Drake
http://www.lclark.edu/~drake/



On May 17, 2007, at 11:00 PM, Chrilly wrote:

>>> >
>>> I have serious problems with KO. UCT-Suzie plays generally  
>>> strong, but makes
>>> terrible blunders in KO-positions. So far I do not even  
>>> understand the
>>> problem. Could you describe it more detailed?
>>> I had also some serious SuperKO problems. UCT-Suzie was very  
>>> "clever" to
>>> find SuperKOs. We do not check for SuperKO in Alpha-Beta. The  
>>> search is not
>>> deep enough. Ignoring SuperKO in UCT is for a Hashtable version  
>>> deadly.
>>> GameStack-Overflow.
>>>
>>> Chrilly
>>
>>
>> So does your hash function consider all previous board states (for
>> superKo)?  If so, how?  I can think of one way, but I don't use it
>> since I have a tree that handles the allowable moves independent of
>> the hashtable.
>>
> When going down a variation the Hash and other Board-State  
> Information like e.g. the KO-Point are stored on a stack. Starting  
> from the current Top of Stack the detection goes down and search  
> for the same hash-key and Ko-Point. Its the "Repeated Position"  
> Detection method of chess. The Gamestack-Pointer is decremented by  
> 2, one can stop, when a non-capturing move is done (in chess its  
> the other way round). One can start 4 Plies from the top of stack.  
> Due to the stoping criterion one has to check only a few entries  
> (most of the time none).
> If a SuperKO occurs, the position is evaluated by the Material- 
> Balance. BlackCaptures - WhiteCaptures + Komi. Probably a better  
> way is to ignore the result. But I assumed that SuperKO is a rare  
> event and the result has no significant impact on the search-tree.
> Maybe there is something wrong with this approach and the Ko- 
> Problems I have a related to this simple SuperKO handling. I  
> noticed several times that a direct transformation of chess methods  
> has some subtle flaws.
>
> Chrilly
>
> _______________________________________________
>> computer-go mailing list
>> computer-go at computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070518/a6bd8cb1/attachment.htm