Hi John,
The impressive numbers reported by Lukasz Lew is based on designing
the fastest possible randomly distributed play-out you can manage.
But when using "heavy" play-outs, things become more complicated
because the play-outs become far more expensive. Lazarus does
some of the sames things Mogo does, which require extra tests.
I believe a great deal of optimizations can be done to improve
the play-out speed of Lazarus.
But to get apples to apples comparison, here are the numbers
for Lazarus using both lite and heavy play-out versions:
Lite - play-outs randomly distributed
Heavy - Mogo-like play-outs
----------------------------------------------
Lite - playouts per second 22,042
Lite - UCT search 17,955
Heavy - playouts per seconds 8,051
Heavy - UCT search 7,940
Lazarus could probably be far more efficient in all areas,
but you can see that heavy play-out time dominates total
search time, but not so much with lite play-outs.
It is far faster to look at all the moves and do the basic
calculations required that it is to play a random game, even a
lite random game. Playing a random game requires quite a
bit of logic, but the loop to find the correct UCT choice
is rather tight in comparison. And of course with heavy
play-outs it's not even close.
Of course these ratio's could be substantially different
depending on your implementation.
Allocating memory for nodes can really slow down the program
so they are pre-allocated in Lazarus. I never malloc or free,
I manage this myself with a fixed pool of nodes and simple
pointer operations.
- Don
On Sat, 2007-03-17 at 09:29 -0400, John Tromp wrote:
> Many people here have reported on their MC playout speed,
> with numbers approaching a most impressive 100K playouts/sec.
> I would like to know what impact adding UCT has on this speed.
> In the playout you need only spend a small constant amount of
> work per move, but choosing a single child node in UCT seems to
> require examining all (up to 81) children, which could be almost as costly
> as an entire MC playout. Thus, if you descend 9 moves in the UCT tree, then
> that could take 90% of your overall time, making MC playout speed
> somewhat insignificant.
>
> What drop in speed are UCT implementors experiencing?
>
> regards,
> -John
> _______________________________________________
> computer-go mailing list
> [email protected]
> http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
