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/
signature.asc
Description: This is a digitally signed message part
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
