[computer-go] KGS Computer Go Tournaments

[Peter Drake]

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 <c.donninger at wavenet.at>:
>> 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 at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/