By your argument, it would seem to make sense to remove this check even if you
don't use my decaying weight.
boolean ok = true; // ok to use this move?
// see if either side has used this move before
for (int j=savctm; j<i; j++) {
if ( (mvs[j] & MASK) == mv ) {
ok = false;
break;
}
}
Don Dailey wrote:
On Mon, 2008-10-27 at 14:48 -0400, Michael Williams wrote:
It's actually more bare-bones (in the sense that there is less code) if you
consider the update loop that I showed.
The spirit of the recipe is to avoid any magic, any special cleverness,
anything that requires extra explanation, etc. For instance one thing
I hate is the magic constant of 3X for the stopping rule - but some
things are absolutely necessary.
I could have specified early cutoffs for AMAF because I have found it's
better not to go all the way to the end for this, but again that is an
enhancement that goes beyond the most basic thing and would require
additional explanation. This idea of course supplants that, but it's
easy to imagine that someone else might come along and show a different
decay function that is more effective than yours and so on.
In fact, the number of "simple" enhancements could go on indefinitely.
AMAF would even seem to violate this basic principle of simplicity,
however AMAF has become so ubiquitous that it seems right to make it
part of this.
So no, the idea isn't to make the strongest reference bot possible but
to provide a definition so simple and easy to explain that people will
be willing to implement it. I don't want to add several paragraphs to
explain each little tweak.
However, having said all of that, I like the idea of tracking these
kinds of enhancements. We might even have progressively stronger
version that we could "standardize" and test against so that new bot
authors could progressively add features (such as this nice enhancement)
as they learn.
- Don
Don Dailey wrote:
Great information. I'll include a version of this to my scalability
study. Is this the C version?
wins[] and hits[] are integer arrays and weight is a fraction less than
1.0, so I'm not sure how this works. Did you change hits and wins to be
doubles?
There are many enhancements possible, and I'm not going to change the
definition, it was my intention to provide a very basic "bare-bones"
reference implementation for others to build on.
- Don
On Mon, 2008-10-27 at 13:01 -0400, Michael Williams wrote:
The following modification to AMAF seems to perform better and scale better. The idea is to weight the moves at the beginning of the playout heavier than the
moves at the end of the playout. It's probably not a new idea.
This code from the reference implementation:
wins[mv] += sc;
hits[mv]++;
Becomes this:
double weight = 1.0 - (double)(i - savctm) / (ctm - savctm);
wins[mv] += weight * sc;
hits[mv] += weight;
If you are not familiar with the reference code, here are the meanings of the
variables in the code above:
i is the loop variable, counting from savctm to ctm
mv iterates over each move in the playout
sc is 1 or -1, depending on the outcome of the playout
ctm is the move count at the end of the playout
savctm is the move count at the beginning of the playout
hits is the number of times a given move was played
wins is the number of times a given move resulted in a playout win
At 15 playouts per move, the modified version wins 54.0% of the time (±3.5%)
after 200 games.
At 30 playouts per move, the modified version wins 54.0% of the time (±3.5%)
after 200 games.
At 60 playouts per move, the modified version wins 54.5% of the time (±3.5%)
after 200 games.
At 125 playouts per move, the modified version wins 53.0% of the time (±3.5%)
after 200 games.
At 250 playouts per move, the modified version wins 54.0% of the time (±3.5%)
after 200 games.
At 500 playouts per move, the modified version wins 55.5% of the time (±3.5%)
after 200 games.
At 1000 playouts per move, the modified version wins 57.5% of the time (±3.5%)
after 200 games.
At 2000 playouts per move, the modified version wins 63.0% of the time (±3.4%)
after 200 games.
At 4000 playouts per move, the modified version wins 63.5% of the time (±3.4%)
after 200 games.
At 8000 playouts per move, the modified version wins 63.5% of the time (±3.4%)
after 200 games.
At 16000 playouts per move, the modified version wins 71.0% of the time (±3.2%)
after 200 games.
Because of the weighting, it is probably safe to remove the code that checks to see if the move was previously played before awarding credit. Doing so and
incrementally calculating the weight would yield this simple and fast update loop after each playout:
// Track win statistics using weighted AMAF - (All Moves As First)
// ---------------------------------------------------------------
double weight = 1.0;
double weightDelta = 2.0 / (ctm - savctm + 1);
for (int i = savctm; i < ctm; i += 2)
{
int mv = mvs[i] & MASK;
wins[mv] += weight * sc;
hits[mv] += weight;
weight -= weightDelta;
}
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
------------------------------------------------------------------------
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
