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/
