Lazarus does full superko in the UCT search - but the play-out only look at simple KO.
In the play-outs, I'm pretty sure infinite play-outs due to not using superko are possible - even with the randomness. But I have a limit on the length of the play-out games because when you use heavy play-outs the games can occasionally last for hundreds of moves. The more randomness you take out of the play-outs the more likely you will get ridiculously long loops. Superko would solve this, but it would also slow down the play-outs significantly. I see no reason to have the refinement of superko in a random play-out. - Don On Fri, 2007-05-18 at 09:01 -0700, Peter Drake wrote: > 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 > > > [email protected] > > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > > > > _______________________________________________ > > computer-go mailing list > > [email protected] > > http://www.computer-go.org/mailman/listinfo/computer-go/ > > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
