Mark Boon wrote:
Sorry, without a bit more explanation, the assembler code is very
hard to understand. What exactly does it do?
The first source code was just an example to see what kind of code
is generated. The second is useful, if you understand asm you should
understand it. The board has 4 modes, as far as patterns are concerned.
So the following applies for each mode and for each possible mapping
scheme. When 40 neighbors are used, (i.e. Manhattan distance 4) there
are 81 possible situations (all the cells of a 9x9 board are different
as far as board limits are concerned). On bigger boards, each cell maps
one of the 81 possible 9x9 cells. The board system cannot play on less
than 9x9. And for each of these 4x(maximum)81 (some board modes have
smaller distance) the generator writes 2 functions: one for creating
the mask/hash from scratch and an other to update all masks/hashes
in the neighborhood of a new stone.
Does it relate to a pattern?
Yes the complete pattern is:
+---+
| 4 |
+---+---+---+
| 4 | 3 | 4 |
+---+---+---+---+---+
| 4 | 3 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+
| 4 | 3 | 2 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+
| 4 | 3 | 2 | 1 | · | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+---+---+
| 4 | 3 | 2 | 1 | 2 | 3 | 4 |
+---+---+---+---+---+---+---+
| 4 | 3 | 2 | 3 | 4 |
+---+---+---+---+---+
| 4 | 3 | 4 |
+---+---+---+
| 4 |
+---+
Justification of this shape:
1. It includes all standard nobi, iken tobi, niken tobi, kosumi,
keima & ogeima relations (+ double iken tobi + double kosumi)
2. It detects if a pattern is at the 4-th line or the 4x4 corner
(and below obviously). Less than that is too small.
The 4-th line is too different from the center.
3. It is a nested structure, {dist12, dist12 + dist3} are both usable.
4. It has reasonable size for the information it contains.
5. The bit arrangement is optimized for 90 deg rotation.
Additionally, I keep urgency information for: normal, the pattern
shows up for the first time and urgency in a ko.
Did you write a paper or post explaining this in more detail?
Not yet.
Do I understand correctly that you generate this code automatically?
Yes. It would be a nightmare to write about 70K lines by hand and
debugging would be hard as well. Although what the functions do is
simple enough to create a test that verifies 100% of the cases.
You are talking about updating 40 hashes. Does it mean your patterns
have fixed size?
Yes. 3 sizes: Manhattan distance 2, 3 and 4
In the 500 nanoseconds, how many patterns do you compare?
That was updating (max) 40 hashes in the neighborhood of a newly
placed stone. The precise number of hashes depends on the board
coordinate and the surrounding stones although that is achieved
without a single conditional jump. (It is a very conservative
estimation for approx 140 instructions in a jump free sequence.
The typical case is probably more like half of that.) But, as
mentioned, it does not include neither the board logic nor the
search that translates hash -> urgency.
How about rotations and color inversions?
In the slowest mode the pattern is rotated using macros like this
one (that rotates a 40 neighbor pattern)
asm
mov edx, eax // @jm
mov eax, [edx + 8] // jm.mask4
rol eax, 8
mov [edx + 8], eax // jm.mask4
mov eax, [edx + 4] // jm.mask3
shl eax, 6
mov ecx, eax
and eax, 0ffFFFFh
rol ecx, 8
or al, cl
mov [edx + 4], eax // jm.mask3
mov eax, [edx] // jm.msk12
mov ecx, eax
shl eax, 4
rol cl, 2
mov al, cl
mov ecx, eax
shr ecx, 16
and eax, 0ffF0FFh
and ecx, 0000F00h
or eax, ecx
mov [edx], eax // jm.msk12
end
and converted to canonical. Color inversion is automatic
because the pattern is own/opponent instead of black/white.
In the fastest mode, the hash table has x8 size and includes
the hashes of the rotated patterns.
Jacques.
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
