Mark Boon wrote:
> I suppose there's no reason why it has to be assembler,
> you could just as well generate C-code.
I don't think so. But I don't write that much asm as it may appear.
I see what the compiler writes when I debug and write critical
parts only. And automatically generated code.
> I don't see yet how you go from there to finding patterns.
Depending on the mode, it computes either the hash or the mask.
That mask has to be translated into urgency by a table search.
(Btw. urgency is not just:
times_played / (times_played + times_postponed)
but that value is used as an a priori value for Bradley Terry
models as Rémi introduced. My adjustment is not as advanced
as what Rémi describes. I just give a weight to a competition
based on the sum of the competing gamma values, and that gives
me another point:
SUM weights_of_played / SUM weights_of_played + weights_of_postponed
And I advance a step (like 1/4 of the distance) in that direction
and use the new point as the current value. Iterating this way
improves the wins of the best move but distorts the distribution
(I extract lots of statistics at each step) so I stop rather early.)
The macro for searching in an ordered list is an efficient
implementation of the "canonical method".
<Copy/paste from Numerical Recipes in C ISBN 0-521-43 108-5
(c) Cambridge University Press 1988-1992>
void locate(float xx[], unsigned long n, float x, unsigned long *j)
{
unsigned long ju,jm,jl;
int ascnd;
jl=0; //Initialize lower
ju=n+1; //and upper limits.
ascnd=(xx[n] >= xx[1]);
while (ju-jl > 1) { // If we are not yet done,
jm=(ju+jl) >> 1; //compute a midpoint,
if (x >= xx[jm] == ascnd)
jl=jm; // and replace either the lower limit
else
ju=jm; // or the upper limit, as appropriate.
} // Repeat until the test condition is satisfied.
if (x == xx[1]) *j=1; // Then set the output
else if(x == xx[n]) *j=n-1;
else *j=jl;
} // and return.
</Copy/paste>
Improvement 1: Instead of if/else, use conditional moves.
Improvement 2. Since when the value is not found, the while
loop has a fixed number of iterations for a fixed table size,
unroll the loop as a sequence of iterations. As mentioned,
an iteration has only 8 instructions.
Improvement 3: When the value is found, break.
(That wouldn't come for free in C it would
require a additional "if (x = xx[jm] )" )
mov eax, ebx
add eax, ecx
shr eax, 1
and al, 0fch ;; Align to a valid pointer
cmp edx, [eax]
jz &name&out
cmovc ecx, eax ;; This is true if [eax] > value
cmovnc ebx, eax ;; This is true if the previous is false
Here ecx is a pointer to xx[jl], ebx is a pointer to xx[ju],
edx is x and eax is a pointer to xx[jm].
> I assume you allow some of the points to be undefined
> (also called 'don't care points') but I don't see how. And
> if you allow undefined points, why would you need masks
> of smaller manhatten distances?
I don't use don't care. I mask code in 2 bits: void, own,
opponent, out_of_board. This produces bigger database size,
because the only way to introduce "don't care" is to repeat the
pattern. Since my patterns are learned automatically and database
size is not a problem at all, I didn't see the need of don't care.
The bigger patterns have the disadvantage that around move 150
2/3 of the legal moves have unknown patterns. The smaller distances
improve this. I don't know yet if that is required, because patterns are
mainly intended to break the ice, when complex shapes emerge, the
moves suggested by the search may be much better candidates.
Jacques.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
