Only 28 bytes? What's in your nodes? That doesn't seem like enough
room for 82 pointers to children. If you don't have pointers to
children, how do you find the children's statistics for UCT? Play
each move and examine the resulting hash code?
Peter Drake
Assistant Professor of Computer Science
Lewis & Clark College
http://www.lclark.edu/~drake/
On Dec 6, 2006, at 2:04 AM, Magnus Persson wrote:
Quoting Chrilly <[EMAIL PROTECTED]>:
Maybe there is a logical flaw in my calculation. In this case it
would be nice if one of the UCT-programmers explains were all this
memory is used.
Valkyria currently preallocate 2 million records for the nodes of
28 bytes
each which is about 50 MB. I could allocate more memory than that
but at some
point I had a problem with severe memory thrashing (*) so I decided
to try
using as little as possible. I also only have access to computer
with are a
little outdated.
I think the huge factor here is that for every terminal node
reached I add all
children for that node, although only one of them is actually
played. The
reason is that then there is a lot of code (pattern matching) that
thus only
have to run once. I used to to only expand nodes that were selected
to be
played, but the overhead of the recomputing stuff and some
nightmare bugs,
made me sacrifice memory for simplicity and a 30% speedup. With old
code I had
no memory problems as you correctly predicted although my numbers
differs
somewhat from what you assumed.
When I run out of nodes I simply delete all subtrees that has been
visited less
times than a threshold.
---
I just ran a test having it think for one hour on the empty 9x9 board.
It played on average 2500 simulations per second, but added 30000
Nodes/second. This means that it fills memory in one minute. This
is not an
accident of course I designed it such that it should never need
garbage
collection the first minute it thinks. It played 222000 moves per
second
including all overhead.
The principle variation was 7 ply deep. And here I limit the depth
to nodes
which has been visited at least 2000 times, the UCT tree goes much
deeper than
that but with this restricition the moves in the principle
variation is always
reasonable.
The second best variation was searchd to 5 ply, and the remaining 4
was searched
to 3 ply. Thanks to symmetry pruning Valkyria only searches 6 moves
in the
opening position.
The first time garbage collection was done 1.9 Mnodes were freed
which is close
to 100%, so most of the initial tree is really unimportant nodes.
The last time
it freed only 0.7 MNodes which means that more than half of the
nodes is
actually is used for nodes that I do not dare to prune. I guess if
I allocate 5
times more memory then I could play up to 10 hours without a
serious problem but
after 20 hours perhaps the program would do garbage collection all
the time.
-Magnus
(*) In reality it turned out that my laptop easily overheats and
shuts down
all systems that generated heat, so I can probably allocate 5-10
times more
memory without problems on my machines.
_______________________________________________
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/
