Home * Board Representation * Mailbox * Vector Attacks * 0x88
0x88

0x88 is a square centric board representation. It uses one nibble for both rank and file each, to index the piece- or empty square codes. While the doubled array size is negligible, the redundancy of the bit-gaps pays off for several applications. 0x88 is C-syntax and the hexadecimal value of a mask of bits need to be zero for valid square coordinates (136 decimal, 210 octal, 10001000B).

Layout

In the 0x88 board-representation an 128 byte array is used. Only the half of the board-array are valid squares representing the position. The second half is almost garbage as usually not addressed. The little-endian layout of an 0x88 array, valid indices bold:

A
B
C
D
E
F
G
H
8
70
71
72
73
74
75
76
77
78
79
7A
7B
7C
7D
7E
7F
7
60
61
62
63
64
65
66
67
68
69
6A
6B
6C
6D
6E
6F
6
50
51
52
53
54
55
56
57
58
59
5A
5B
5C
5D
5E
5F
5
40
41
42
43
44
45
46
47
48
49
4A
4B
4C
4D
4E
4F
4
30
31
32
33
34
35
36
37
38
39
3A
3B
3C
3D
3E
3F
3
20
21
22
23
24
25
26
27
28
29
2A
2B
2C
2D
2E
2F
2
10
11
12
13
14
15
16
17
18
19
1A
1B
1C
1D
1E
1F
1
00
01
02
03
04
05
06
07
08
09
0A
0B
0C
0D
0E
0F

Coordinate Transformation

Square index by file and rank and vice versa:
sq0x88 = 16 * rank07 + file07;
file07 = sq0x88 & 7;
rank07 = sq0x88 >> 4; // sq0x88 / 16
0x88 index by a 0..63 square index needs to add the three upper rank bits:
sq0x88 = sq + (sq & ~7);

Applications

Off the Board

'Off the board' detection in move generation becomes cheaper and faster. Both nibbles, rank and file, utilize the redundant upper bit to indicate invalid squares. While adding certain offsets to a from square, to determine a destination square - a cheap 'and' by 0x88 is appropriate for an 'off the board' test:
if ( destination & 0x88) goto invalid square
That is the trick with 0x88 - but it gains by an additional property.

Square Relations

The difference of valid 0x88 coordinates A and B is uniquely with respect to distance and direction, which is not true for classical packed three bit rank and file coordinates (for instance -+7 may occur on ranks, anti-diagonals). That makes lookups for distance, Manhattan-distance, possible piece attacks and that like, much more resource friendly. While classical square coordinates in the 0..63 range require 4K (64*64) sized tables, the 0x88 difference takes 1/16 or 256 sized tables - or even 16 less.

An offset of 119 (0x77 as max valid square index) is added, to make +-119 a 0..238 range (size of 240 for alignment reasons).
0x88Diff = 0x77 + A - B

Attack Lookup

Looking up pre-calculated tables of 240 elements by 0x88diff of from- and to-squares is useful in determining possible attacks of certain piece-types. For a most dense tables, each piece-type might be represented set-wise by a certain bit-position. Distant squares of sliding pieces need to check whether squares are obstructed, though.

History

Hyatt

In a reply to Valavan Manohararajah in 1996, Robert Hyatt mentioned he used 0x88 in Cray Blitz, and changed to bitboards in the 1982-83 time-frame [1]. He further said in a 1999 CCC post, the algorithm has been around basically forever and he first saw it in another chess program written around 1970 (Coko) [2].

Kuipers

Tiny Chess 86 by Jan Kuipers used 88H for off the board test, as published in a June 1981 Databus article with some 8086 assembly code snippets [3]:
0634 03FA         109            ADD    DI,DX           ;CALC. SQ. MOVING TO
0636 F7C78800     110            TEST   DI,88H          ;OFF BOARD?
063A 750C         111            JNZ    G4              ;YES

Wiereyn

In his 1985 paper Inventive Problem Solving [4], Paul Wiereyn described coordinates with nibbles for ranks and files inside a byte, and used such square differences (mod 256) as table-index to determine pinned pieces and discovered checks in his problem solving program:
It is obvious to chess-players that a piece when pinned should not be allowed to move out of the direction in which it is pinned. Hence, as a preliminary, we calculate, in one byte, the difference between the coordinates of the piece about to be moved and one's own King, e.g.,
Rd5 - Kf5 <=> 45 - 65 = E0, hexadecimals and reduction modulo 256
being implied throughout.
The difference, E0 say, serves to enter a table T. The tabular value T[E0] so found, when zero, indicates non-collinearity (the pieces are not on the same rank, file or (co-)diagonal). If not zero, the value codes the direction of collinearity, i.e., the pinning direction. In our example the value T[E0] = F0, stands for due West.

Kittinger

About its origin Bruce Moreland wrote [5] :
When I was at the Hong Kong WCCC in 1995, I had some conversations with David Kittinger. He told me about a move generation scheme, whose name I promptly forgot. When I came back home, I explained this scheme online many times. Since I didn't know the name, I couldn't give it the proper name, and it kind of acquired a name. The name that seems to have stuck is "0x88", which is means hexadecimal 88. The reason it's called 0x88 is that this constant is critical in the implementation of the scheme.
David Kittinger further in 2012 [6]
I was told this technique at I believe the Travemunde world championship. It just involved using 0rrr0ccc encoding. The advantage was that (sq + offset) & 0x88 would tell you if off board. Many of the devices I programmed on took longer to read ram than test a register result. Also, immediate test for < 0 (byte value) could test for off board, so faster off board test than accessing a 'collar' of off board values. The fellow who told me this attributed it to Michael Botvinnik (Former USSR World Champion) as something used in a version of Kaissa [7] . However, when I was riding an elevator w/Mr. Botvinnik and asked him about this to confirm the derivation, one of his handlers asked that I not ask Mr. Botvinnik any questions.
... and on the utilization of Memory [8]
Another advantage of the 0rrr0ccc was that I put the 'ioboard' at 0rrr1ccc so basically used 1/2 a page of ram efficiently for both boards. I would then have the piece table at 1000wwww and 1000bbbb for the white and black pieces respectively just to pack things in.
... and the difference of 0x88 coordinates [9]
The whole 0x88 is pretty obvious. In fact, another big benefit is that you could take the difference of two sqs and use that to look into a table to see the legal piece types that could be attackers. Having bit 3 cleared prevented wrap around on this look up. Hence, for most my programs the basic capture routine iterated from largest to smallest captured piece, using smallest to largest capturing piece, taking the difference of the sqs, looking up in att_table and seeing if nz, if nz, then if & with attacker type bit nz then just had to check if slider and had path clear. Of course, w and b pawns had different type bits. Made for a decently fast and ordered capture search.

See also


Publications


Forum Posts

1995 ...

2000 ...

2005 ...

2010 ...


External Links


References

  1. ^ Re: X88 board representations by Robert Hyatt, rgcc, April 17, 1996
  2. ^ Re: 0x88 by Robert Hyatt, CCC, January 11, 1999
  3. ^ Jan Kuipers (1981). Tiny Chess 86 - Een schaakprogramma voor de 8088/8086. Databus 06-81, pdf hosted by Hein Veldhuis
  4. ^ Paul Wiereyn (1985). Inventive Problem Solving. ICCA Journal, Vol. 8, No. 4
  5. ^ 0x88 Move Generation by Bruce Moreland
  6. ^ Re: Hello all by Dave Kittinger, CCC, April 26, 2012
  7. ^ presumably in Pioneer, see also Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft
  8. ^ Re: Hello all by Dave Kittinger, CCC, April 26, 2012
  9. ^ Re: Hello all by Dave Kittinger, CCC, April 27, 2012

What links here?


Up one Level