[computer-go] UCT

[Rémi Coulom]

Peter Drake wrote:
> On Nov 3, 2006, at 8:10 AM, Rémi Coulom wrote:
>
>> You can try multiplying uncertainty by a well-chosen constant value. 
>> This way, you can tune how selective your search is. I found that 
>> using a constant < 1 improves the search on 9x9 for Crazy Stone (I 
>> use 1/sqrt(10), if I recall correctly). I wonder what is the 
>> experience of other UCT programmers, by the way.
>
> Whee, parameter tweaking!  :-)
>
> Do you have some reason for choosing this value, or did it just work 
> well in practice?
I tried plenty, and measured how they performed against GNU.
>
>>> Also, are people pruning any move for which (average + uncertainty) 
>>> is less than the (average - uncertainty) of some other move?
>> I am not sure what you mean. In UCT, you only search the move that 
>> has the highest average + uncertainty, and you don't search any other 
>> at all.
>
> By "prune" I mean "remove from the stored tree", making the memory 
> used on that branch available for something else.
I have never had memory problems with Crazy Stone. Crazy Stone uses 32 
bytes of RAM per node of the tree. It is not really a tree, but a hash 
table, to handle transpositions. For nodes closer to the root, I 
"extend" each node with more data (pointers to children). This is only 
needed for a small proportion of the total number of nodes, so it does 
not eat up a huge amount of RAM. That is because I don't do UCT in a 
node before 81 random simulations have been run there.

Since I use transpositions, it is not really possible to remove a 
subtree, anyways.

Rémi