Well, it shows that it always pays to measure the effect of an
'optimization' instead of trusting on blind-faith. Or logic. Because
it seems very counterintuitive. I would not have been so surprised
if, as Don said, it would have been negligeable. But for it to
actually become noticeably slower... that doesn't make any sense to
me. That should teach me to actually try things out before I make off-
the-cuff suggestions.
Mark
On 29-okt-08, at 15:49, Michael Williams wrote:
Thanks for the suggestion, Mark. Below I show the exact code used
(C#) and the amount of time each version took.
Original:
for (int mv = 0; mv < NNN; mv++)
{
credit[mv] = true; // initial assumption is that credit
is awarded for any move
}
double weight = 1.0;
double weightDelta = 2.0 / (ctm - savctm + 1);
for (int i = savctm; i < ctm; i += 2)
{
int mv = mvs[i] & MASK;
if (credit[mv])
{
wins[mv] += weight * sc;
hits[mv] += weight;
credit[mv] = false; // do not award credit for
this move again
}
int opponentMove = mvs[i + 1] & MASK;
if (credit[opponentMove])
{
double opponentWeight = 0.1 * weight;
wins[opponentMove] -= opponentWeight * sc;
hits[opponentMove] += opponentWeight;
credit[opponentMove] = false; // do not award
credit for this move again
}
weight -= weightDelta;
}
After Mark's suggestion:
currentPlayoutId++;
if (currentPlayoutId == 0)
{
// Need to reset
for (int mv = 0; mv < NNN; mv++)
playoutInWhichMoveLastUsed[mv] = 0;
currentPlayoutId = 1;
}
double weight = 1.0;
double weightDelta = 2.0 / (ctm - savctm + 1);
for (int i = savctm; i < ctm; i += 2)
{
int mv = mvs[i] & MASK;
if (playoutInWhichMoveLastUsed[mv] != currentPlayoutId)
{
wins[mv] += weight * sc;
hits[mv] += weight;
playoutInWhichMoveLastUsed[mv] =
currentPlayoutId; // do not award credit for this move again
}
int opponentMove = mvs[i + 1] & MASK;
if (playoutInWhichMoveLastUsed[opponentMove] !=
currentPlayoutId)
{
double opponentWeight = 0.1 * weight;
wins[opponentMove] -= opponentWeight * sc;
hits[opponentMove] += opponentWeight;
playoutInWhichMoveLastUsed[opponentMove] =
currentPlayoutId; // do not award credit for this move again
}
weight -= weightDelta;
}
1M playouts on 9x9 (2 test runs each):
Original -- 83.23 seconds, 83.66 seconds
Mark's Suggestion -- 84.45 seconds, 85.69 seconds
100K playouts on 19x19 (2 test runs each):
Original -- 51.02 seconds, 50.83 seconds
Mark's Suggestion -- 51.48 seconds, 50.90 seconds
50K playouts on 29x29 (2 test runs each):
Original -- 77.77 seconds, 76.76 seconds
Mark's Suggestion -- 79.11 seconds, 79.10 seconds
I am unable to explain the results.
Don Dailey wrote:
The marker idea I call aging. I call the variable age because it
seems
to be more descriptive to me. Each playout has a different age
associated with it. The idea is used in persistent hash tables in
computer chess and I'm sure in other games too.
However, I seriously doubt this particular enhancement is even worth
doing in this context. It may even be difficult to measure the
speedup
it will give you. I would be surprised if you get 1/2 percent.
I don't initialize the array in a loop either, I use memset in
C. If I
did this is java I would use whatever java method is the equivalent
assuming it is optimized. If you want to save on initialization
(which is pretty fast on modern
processors anyway) you can make this a bit array instead of an int
array. Then it would initialize about 32 times faster but you would
probably spend a little more time referencing it. If you were to
profile the code, I'll bet this would be one of the very
last sections of code you would bother optimizing. Still, if you
are a
speed freak you would probably at some point get around to doing
it just
because you can! - Don
On Tue, 2008-10-28 at 21:24 -0200, Mark Boon wrote:
Some interesting ideas Michael, keep them coming.
With regards to the code-snippet you posted, this kind of
'mark-to-prevent-double-work' type of construction is very common in
computer-Go. Looping over the complete array to set the initial
value
is very expensive and totally avoidable.
The same functionality could be achieved by the following:
marker++; // This is an int initialised to zero somewhere in
the beginning of your program.
double weight = 1.0;
double weightDelta = 2.0 / (ctm - savctm + 1);
for (int i = savctm; i < ctm; i += 2)
{
int mv = mvs[i] & MASK;
if (credit[mv]!=marker) // Note that credit[] is now an
array of int instead of boolean
{
wins[mv] += weight * sc;
hits[mv] += weight;
credit[mv] = marker; // do not award credit for
this move
again
}
This is slightly simplified, just so you get the idea. To make it
100%
safe you need to check if marker==0 after the increment and clear
the
credit array. This is so common I use a little helper class that
wraps
this fucntionality for me, called BoardMarker. The code would
look as
follows:
boardMarker.getNewMarker(); // BoardMarker is allocated
somewhere at the beginning of the program: BoardMarker boardMarker =
new BoardMarker();
double weight = 1.0;
double weightDelta = 2.0 / (ctm - savctm + 1);
for (int i = savctm; i < ctm; i += 2)
{
int mv = mvs[i] & MASK;
if (boardMarker.notSet(mv))
{
wins[mv] += weight * sc;
hits[mv] += weight;
boardMarker.set(mv); // do not award credit for
this move
again
}
Disclaimer, my code is not like this (yet) so I didn't try this for
real. But it should work.
On Tue, Oct 28, 2008 at 8:43 PM, Michael Williams
<[EMAIL PROTECTED]> wrote:
for (int mv = 0; mv < NNN; mv++)
{
credit[mv] = true; // initial assumption is that
credit is
awarded for any move
}
double weight = 1.0;
double weightDelta = 2.0 / (ctm - savctm + 1);
for (int i = savctm; i < ctm; i += 2)
{
int mv = mvs[i] & MASK;
if (credit[mv])
{
wins[mv] += weight * sc;
hits[mv] += weight;
credit[mv] = false; // do not award credit for
this move
again
}
_______________________________________________
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/
