On Thu, Nov 19, 2009 at 08:25:53PM -0800, Seth Pellegrino wrote:
> Apologies all for replying to myself so many times, but Darren Cook
> has been kind enough to help me clear the matter up. Essentially, I
> had misread his paper. I was trying to compute the expensive features
> Rémi uses for progressive widening as a move selector for playouts
> rather than the stripped down, speedy features he actually uses.
>
> Thank you all for your help in increasing my understanding.
>
> >> Also, Tom, I was wondering if you could speak to adding patterns
> >> larger than 3x3. A nice feature of 3x3 patterns is that they can be
> >> jammed into two bytes (4 possibilities [black, white, vacant, off
> >> board] for 8 positions), which facilitates the creation of a lookup
> >> table. I've yet to figure out as fast a method for 4x4 patterns (or
> >> larger), so I was wondering both how you've done it and how much it
> >> helped.
A thing to always get in mind is compute incrementaly, so for each
features you have to check each time you play a stone, if this play
chane features somewhere on the board. For example, for the atari
feature, when you play a stone, just check if it's group or one of the
neighboorin groups go to one liberty, if it's the case, update the
weights and flags the group as "in atari". When you add this stone, you
also check if it's group is flagged as "in atari", if it's the case and
now it have more than one liberty, update the weight and flag.
In order to have this work, you must also add little update when
connecting and removing groups, but all this can be done incrementaly.
For the patterns, I keep two things:
- For all points on the board I keep a 16 bit value containing the 3x3
pattern of the surrounding cell like you said. This can be easily done
and update each on cell change. If you change the content of a cell,
just update the neighbooring patterns. This is very fast to do and
require no branching.
- For empty points only, a list of bigger patterns. First, those cost a
lot more so I update them only for empty cells. These are stored as
zobrist hash key, so for each cell I have an array of wiht hash value
for patterns from size 2 to 9.
When the content of one cell change, I have to lookup for empty cells in
it's 9-neighbooring, and for them I have to update the patterns. The
pattern update is done by first computing the old weights of modified
patterns, updating the patterns and updating the weight by the
difference between old and new weights.
When a stone is captured, his cell become empty and you have to
recompute each pattern for this cell because it was not updated
incrementally, but in practice, this cost you less than keeping all
non-empty cell upto date.
Surely this cost a lot more than simples 3x3 patterns but if implemented
carefully it's tracktable and I've got them even in playouts. In
playouts I don't go as far as size 9, just upto size 4. Without them I
do 41kpps and with them I've dropped to 26kpps as stated in my previous
mail. This is one of the more costly addition to my engine but it was a
very big improvement in the playout quality.
A pure playout bots, i.e. no tree search, can play nicely one 9x9. It's
not very strong and I can beat it easily but his playing style is a lot
better.
For sure, on 19x19 the speeds are a lot lower but the impact of patterns
is just different. On one hand, on 9x9 each time you change a cell, you
almost have to update all the cell on the board as opposed to 19x19
where you just update a subset of them generally between 10% and 20% of
the cells. But, on the other hand, of these cells to update, on 19x19
there is more empty ones than on 9x9. On small board, it's hard to build
big territory, so the board finish almost full of stone. On 19x19 you
build big territory and each time on stone is played near the border of
aterritory, you have to update patterns of all empty cells in it.
So even if there is, less percent of the board covered by a change, a
bigger portion of this set is concerned by updates. I focus for the
moment on 9x9 so I have no bench for the 19x19 boards, but I will try to
make them. Last time I've looked, if I remember well I have similar drop
in performance than in 9x9, but this have to be checked more carefully.
The main things you don't want to do in playouts is complexe analysis
which can take a long time like ladder reading or life and death
reading. For all thing that you can simply compute incrementaly, it's
good to have the possibility to enable them also during playouts and
test if the improvement of the playouts value the slowdown. You never
can guess it without testing.
It's, in my opinion, one of the most difficult things to do. Choosing
exactly what enabling and what not require a lot of testing of a lot of
combination and the improvement of each of them is small so you have to
do a lot of games for seeing if there is an improvement. It's my big
damn that I don't have actually a computer that can be up and connected
a lot of time to run my bot on cgos to do theses tests. But this will
probably solved at start of january.
On that topic, I have around 17 flag who enable or not features in my
pure playouts bots, and I want to search the best combinations of them.
I known this is almost a dream but does anyone know the best way to
approximate this.
I can play round robbin tournament between different combinations or
make them play on cgos, but how to cleverly choose combinations of
them ? Do you know some papers about this. I know there is research on
this type of problems, but for the moment I just want a simple solution
that is not so bad.
Tom
--
Thomas Lavergne "Entia non sunt multiplicanda praeter
necessitatem." (Guillaume d'Ockham)
thomas.laver...@reveurs.org http://oniros.org
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
