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@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
