On 5/17/07, Chrilly <[EMAIL PROTECTED]> 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.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
