[computer-go] KGS Computer Go Tournaments

[Chrilly]

----- Original Message ----- 
From: "Magnus Persson" <magnus.persson at phmp.se>
To: <computer-go at computer-go.org>
Sent: Wednesday, December 06, 2006 9:19 AM
Subject: Re: [computer-go] KGS Computer Go Tournaments


> Quoting Don Dailey <drdailey at cox.net>:
>
>> I would love to see such a tournament,  but the UCT programs could not
>> take full advantage of the extra time.   As you see, we run out of
>> memory after a minute or two!
>
> Valkyria can prune the tree but not indefinetly. I think it would at least 
> be
> able to think for an hour per move. But there is a risk that the cure 
> (pruning)
> hurts it such that it playing strength starts scaling poorly with 
> increased
> thinking time.
>
> -Magnus

I do not understand why they run out of memory in such a short time. E.g. 
MoGo calculates 1100 Episodes/sec on 19x19. If one assumes 1 episode is 400 
moves, its max. 440 KPositions/sec.
In 2 minutes its about 60 MPositions. This is a very conservative upper 
bound. As far as I have understood it the MC-part not stored, only the 
UCT-part. Additionally nodes are visited several times and there are 
transpositions. But even with this upper-bound, if one uses 16 
Bytes/Position its still "only" 1 GByte of RAM.
If one assumes a ratio of 1:10 between UCT and MC nodes, its only 6 
MPositions or 100 MBytes which must be stored. In my paper-design 200 MBytes 
should be enough to run practically "forever".

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.

Note: If one uses for each small chunk of memory malloc() there is a 
considerable overhead. With STL it gets worse. But STL is anyway no option 
for a speed and memory critical programm. It should be relative trivial to 
write an efficient memory handler.

Chrilly