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