[computer-go] KO in Hashtable-UCT?

[Darren Cook]

Heikki Levanto wrote:
>>> I don't make any tests for the first 20 moves. Thereafter, I
>>> resign if
>>>   - I have no stones left on board
>>>   - I have less than half the number of stones my opponent has
>>> I also pass if my opponent has no stones left on board.

Eduardo Sabbatella wrote:
>> My cut logic was: dead stone difference > X. stop the
>> game, wins the player with less dead stones.

Dave Hillis wrote:
> ..., for a sufficiently high threshold 'X', you should get
> the correct value and still obtain a speedup worth having. Keep
> increasing the threshold until it stops making mistakes.

Alternatively, I wonder if there is some theoretical way to work it out?
What is the most extreme example of being behind (either by X stones, or
by some percentage, such as Heikki's 50% above) where the losing player
can make a comeback and win the game (assume perfect play by both
players from that point)?

It sounds like a puzzle the people who come up with the go bestiary [1]
or huge nakade [2] would enjoy.

(Of course, the nice thing about playouts is we don't need to be
perfect, just right most of the time; but, still, a theoretical basis is
always nice if one is available.)

Darren


[1]: http://www.goban.demon.co.uk/go/bestiary/rule_challenge.html

[2]: http://senseis.xmp.net/?BiggestKnownEyeSpaceForWhichThereIsANakade