Jason House wrote:
On 6/6/07, *Rémi Coulom* <[EMAIL PROTECTED]
<mailto:[EMAIL PROTECTED]>> wrote:
> I wonder if other people had thought about this before...
>
> Álvaro.
Yes, I did it in the beginning. But I found that it is faster to divide
by more than two. Currently, I keep the probability of the whole board,
each line, and each point. It is simple, and more efficient than a
binary tree.
Rémi
I'm not clear on how you efficiently index into which line to select. I
think the discussion here is still relevant to that. If we take a
simple example of a 5x5 board where the line weights are
{15,10,30,20,25}, and I roll the dice and compute 44 (out of 100), I
don't know to jump instantly to the 3rd entry; other information is
needed if a sequential check is to be avoided. Tokens of 5 could make
it easy to pick a number from 1 to 20 and then jump to the row owned by
that token, and a binary tree could result in ~3 comparisons... not much
better than a sequential check at such a small number of lines.
I do a sequential check.
It is important to understand that it is worthless to be able to pick a
move extremely rapidly, if updating the related data takes a lot of
time. With 3x3 patterns, 8 points have their urgencies updated after
each move. Updating the probability distribution is the time-critical
part of the algorithm, not picking one move at random. With my
algorithm, I have to update 3 values each time the urgency of a move
changes. With a binary tree, I would have to update 8 in 9x9, and 10 in
19x19.
Also, if you have a clever probability distribution, the range of values
for each move will be very large. For instance, here are two 3x3 shapes
used by Crazy Stone (# to move):
O O #
# . .
# O #
Gamma = 143473;
. # #
. . .
. . .
Gamma = 20;
Playing in the empty corner has gamma = 1. So that would be a lot of
tickets to distribute.
Simple straightforward algorithms often work well. I do not do anything
extraordinary in Crazy Stone, and, on 9x9 from the empty board, it still
runs 21,700 simulations per second on a 2.6 GHz opteron (20,400 with the
tree-search logic).
I am sure it could be made significantly faster, but adding knowledge
and high-level algorithmic improvements is tremendously more profitable
in terms of playing strength than finding tricks to accelerate playouts.
Rémi
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
