----- Original Message -----
From: "Magnus Persson" <[EMAIL PROTECTED]>
To: <computer-go@computer-go.org>
Sent: Monday, December 04, 2006 7:45 PM
Subject: Re: [computer-go] Proposed UCT / transposition tableimplementation
Quoting Peter Drake <[EMAIL PROTECTED]>:
I've noticed that Orego has done very poorly in the last couple of
competitions. This is partly due to the improvements in others'
programs, but I think the fact that Orego currently doesn't have a
transposition table is crippling. Since I'm rewriting this stuff in
Java, I'm thinking about how to handle this, and would like to offer up
the following plan for all of you to poke holes in. I'm not sure if I'm
reinventing the CrazyStone structure here, but I think this one is
slightly different.
The interesting point is how to handle overwrites in the transpositions
table,
there I cannot help you since I have not tried it myself. As I understand
it
there is a tradeoff between shrinking the effective tree with
transpositions
and not being able to expand the tree where collisions occur.
In conventional hashtables a simple heuristic is to search the next
K-entries and to mark the entry with the smallest subtree depth. If the
depth of the current entry >= oldepth, the old entry is overwritten,
otherwise it is kept. In UCT one does not have such a thing as remaining
depth, but I assume one can use the number of MC-episodes as a simple
replacement criterion.
I assume collision is not a severe problem. E.g. one has 70.000 MC-episodes.
This gives at most 70.000 entries. Even a relative small hashtable with e.g.
1 Mega-Entries should not have much collisions if one searches a couple of
entries ahead to find an unused slot. Maybe it pays to use some better
collision resolution techniques to avoid long primary runs. But with a
filling ration of 7 percent this should be no issue.
I think the more difficult question is how to handle the move-statistics in
each node. In most nodes there are only a few moves explored, in a few ones
near the root all or almost all moves are searched and the statistic must be
kept. The most simple way would be a linked list. But linked lists are
nasty. One jumps around in memory, its difficult to change the order and
there is the link overhead.
One idea is to have 3 types of arrays. An array with only 2 entries, with 16
entries and with 362 entries. If a node is visited first, the move
statistics is stored in the 2 entry arrays. Maybe this arrays could be a
direct part of the Hashtable record. When the 3rd move is stored, the 2
moves are copied to the 16 entry array, when this also overflows, the final
array is used.
I think it is not necessary to reuse smaller chunks. The "memory-handler" is
just an index into one big array. Depending on the allocated chunk-size the
next-free entry index is just incremented by 2,16 or 362.
One can think about to organize this arrays as a heap. But thats probably an
overkill for the smaller chunks and pays only for bigger ones. But I assume
even for the biggest chunk it does probably not pay off. If one keeps the
list sorted according UCT-priority, the currently searched move is in the
first position. The only thing what can happen is, that this first move is
after a bad search result not anymore the best and sorted back in the list.
In my understanding the second best should be the new number one.
There should also not more than 70.000 moves. It can of course happen, that
e.g. in a 362 entry chunk just 17 entries are used. But in generall I assume
that either a lot of moves are searched or only a few one. If one entry is 8
(or 12) Bytes long, one can with todays RAM-sizes allocate quite a lot of
these array entries (e.g. 10 Mega-Entries) and even a worst case filling
factor of 17/380 should be no problem.
(its 380 because the 16 and the 2 chunk is also not used anymore).
Note: I have not yet written an UCT programm. The numbers above are
examples. One has to find out the best chunk-sizes by trial and error.
Chrilly
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
