Keep the common case fast (was Re: [computer-go] KO in Hashtable-UCT?)

[Peter Drake]

Yes, that sounds reasonable too.

In thinking about optimization, the rule as always is "keep the  
common case fast". The cases in UCT Go, in decreasing order of  
commonness, are:

1) Play a move in an MC playout
2) Play a UCT tree move
3) Start (or finish) a playout
4) Make (or accept) a move in the actual game
5) Initialize data structures and the beginning of the game

1 has to be blazingly fast. 2-3 have to be relatively fast. 4-5 don't  
matter much unless you're spending an outrageous amount of time on them.

Also note that almost all UCT moves are played from nodes with very  
few children (often 0 or 1).

Peter Drake
http://www.lclark.edu/~drake/



On May 18, 2007, at 9:15 AM, John Tromp wrote:

> On 5/18/07, Peter Drake <drake at lclark.edu> wrote:
>> It took me a long time to get around my mental block and accept  
>> the advice
>> of everyone here, but your intuition is correct: superko is so  
>> rare, and so
>> expensive to detect, that you should NOT check for it on every move.
>
> In dimwit, we check for superko while descending the UCT tree,
> and only check basic ko in the MC playouts. Our check involves
> a single lookup (of the current, incrementally computed Zobrist key)
> in a hash_map of previous Zobrist keys, which is not all that  
> expensive.
> I agree that doing superko checks in MC playouts would cause an
> unnecesary slowdown.
>
> regards,
> -John
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/

-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://computer-go.org/pipermail/computer-go/attachments/20070518/73e80332/attachment.htm