[computer-go] KO in Hashtable-UCT?

[Chris Fant]

On 5/17/07, Chrilly <c.donninger at wavenet.at> wrote:
> I have now also finished a first version of UCT-Suzie (in parallel the Peter
> Woitke works on the Alpha-Beta Version). UCT-Suzie uses a hashtable, mainly
> because I found the programming of the tree too complicated. The Monte-Carlo
> part uses some simple patterns according the MoGo article. Progress is
> rather slow, because I am working (more than) full-time on FPGA-projects in
> Computer-Tomography.
> >
> > Here are the problems with hash tables as a tree:
> >
> > 1. Time - it is more expensive - you must gather the children together
> > when making decisions about which node to expand (which generally
> > involves re-generating the keys by making all the legal moves.)   There
> > are ways around this that trade space for time but in either case it is
> > more expensive.
> >
> I do not understand this. In UCT-Suzie the moves are generated, when a new
> leaf-node is reached. The Hashtable has a link to the move-list. When the
> node is reached the next time, the moves must not be generated again. Just
> the calculation of the UCT-Urgency value (WinRate + sqrt(....) ) has to be
> done. I assume that this calculation has to be done also in a tree
> representation. I see no difference in this respect with Gunnars Gnu-GO UCT
> code.
> Memory is at least for 9x9 no problem. The number of Monte-Carlo runs/sec.
> is about 17K (9x9). This can be improved, because the UCT-Player uses the
> Alpha-Beta DoMove/UndoMove functions which are overkill for UCT.
>
> > 2. GHI - you must take special care to deal with Graph History
> > Interaction - primarly recognizing that ko situations are different.
> > You can get by with relatively simple solutions that don't fully address
> > this issue but it's still imperfect.
> >
> 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.