On Thu, Nov 19, 2009 at 09:43:41AM +0100, Petr Baudis wrote:
> Hi!
>
> On Thu, Nov 19, 2009 at 12:35:09AM -0800, Seth Pellegrino wrote:
> > I'm working on an implementation of Rémi Coulom's Elo-based move
> > prediction algorithm[1], and I seem to be running into efficiency
> > issues. With my current implementation, I'm running at around 8 or 10
> > playouts per second. I can't imagine that the playouts would be so
> > accurate that I would be able to accurately evaluate my next move at
> > that speed. It seems that simply visiting each vacant point on the
> > board and checking whether that move would be a legal move for the
> > current player (without even computing which gammas are present at a
> > point) takes me down to about 60-75 playouts per second.
>
> What language are you using for your implementation? 60-75 playouts
> per second is still *extremely* slow, it seems you are in for much
> optimizing yet. Common speed of heavy playouts is at least _thousands_
> of playouts per second (per core of modern CPU), in case of light
> playouts it should be getting into tens of thousands.
>
> I'm not sure how much slowdown in general you get by implementing ELO
> patterns, the improvement has not been implemented commonly yet in
> public codebases (though it does seem very promising, no doubt); I plan
> to implement it in Pachi later, but I want to try out few different
> things first yet.
>
This is indeed extremly slow. As a reference, some number from my own
bot who is still in full rewrite. On my rather old Pentium4 at 1.6Ghz I
get the following on 9x9 board:
v1 : ~54000pps
v2 : ~49000pps
v3 : ~41000pps
v4 : ~26000pps
v1 do pure random playouts by selecting play randomly in the empty point
list and testing for validity.
v2 do pure random playouts but select play from the empty list according
to their weight who is set to 1.0 for all plays. (this is for testing
the impact of drawing from weights)
v3 do weighted playouts using elo rating to weights plays with only 3x3
patterns.
v4 same as v3 but use big patterns: up to size 9 manathan paterns.
This is probably not the speedest implementation you can have, but I
think its good performance for a programme fully written in ansi/C
without assembly.
You can also use libego to check speed on your machine for pure random
playouts.
Some tricks from my experiences :
- A lot of thing can be computed incrementally and will be a lot more
slower if you recompute them each times: the list of empty points, the
patterns, the cell weights...
- Don't check for validity of each play in the empty list before drawing
one, just pick one until you find a laid one. This not theoreticaly
exact but in practice, there is no problems and you can gain a lot of
speed here.
- Don't try to undo all move at the end of playout before the next one,
just make a copy before starting playout and do it on the copy.
As a plan to build a bot, I first think you must build a basic bot with
pure random playouts only and get it fast enough. You don't have to go
to 50kpps, but I think at least you must go to 10kpps.
When this works and it's fully tested, start to add weighted drawing and
small fixed size patterns. Those are easy to implement and to maintain
incrementally, and will allow you to debug more your base. At this point
you start to get strong playouts.
Only when you have this you can add bigger patterns.
The Elo ratting from Remy is very powerfull but it's also very tricky to
implement efficiently in your bot, so start with a good base before
trying it.
When I've written the first version of goober, I've tried to put all my
ideas and all ideas of others I find nice at the same time and after a
will this starting to be unmanageable and very difficult to debug. Now,
I'm rewritting it fully from scratch, and don't do the same mistake. The
numbers above show you the progress of it :
- I've started to build a bot without tree search, with only pure random
playouts ;
- Next I've made it work with weighted plays ;
- Next I've added small fixed size patterns with elo-ratings ;
- Adding big patterns was the more tricky and difficult part to get them
efficients.
Now I have a reliable playout engine, with weighted plays. Weights are
computed from small or big patterns and a lot of other features. And I'm
currently working on the tree search part of the bot.
I've already a basic UCT without RAVE but using a lockless transposition
table (the only part not in ansi/c) and I test it a lot before starting
to add anything fancy.
Another advantage of this approach is you can see the progress of your
bot and check for the efficienty of each addition.
Writting a bot is a lot of work but it's also a lot of pleasure, so good
luck for your one.
Tom
--
Thomas Lavergne "Entia non sunt multiplicanda praeter
necessitatem." (Guillaume d'Ockham)
[email protected] http://oniros.org
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
