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).

In the 0x88 board-representation an 128 bytearray 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:

0x88 index by a 0..63 8x8 square index needs to add the three upper rank bits:

sq0x88 = sq8x8 +(sq8x8 & ~7);

The other way around, 8x8 square index by 0x88 coordinates, takes three operations, and adds the three lower bits with possible overflow into empty bit 3, finally shifting right one: ^{[1]}

sq8x8 = (sq0x88 + (sq0x88 & 7)) >> 1;

Of course, both calculations might be replaced by small lookup tables.

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 ^{[2]} . 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) ^{[3]} .

Kuipers

Tiny Chess 86 by Jan Kuipers used 88H for off the board test, as published in a June 1981 Databus article with some 8086assembly code snippets ^{[4]} :

In his 1985 paper Inventive Problem Solving^{[5]} , 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.

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.

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^{[8]}. 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.

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 ^{[10]}

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.

Home * Board Representation * Mailbox * Vector Attacks * 0x880x88is 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).## Table of Contents

## 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:70717273747576776061626364656667505152535455565740414243444546473031323334353637202122232425262710111213141516170001020304050607## Coordinate Transformation

Square index by file and rank and vice versa:0x88 index by a 0..63 8x8 square index needs to add the three upper rank bits:

The other way around, 8x8 square index by 0x88 coordinates, takes three operations, and adds the three lower bits with possible overflow into empty bit 3, finally shifting right one:

^{[1]}Of course, both calculations might be replaced by small lookup tables.

## 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: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).

## 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^{[2]}. 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)^{[3]}.## Kuipers

Tiny Chess 86 by Jan Kuipers used 88H for off the board test, as published in a June 1981Databusarticle with some 8086 assembly code snippets^{[4]}:## Wiereyn

In his 1985 paperInventive Problem Solving^{[5]}, 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.,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^{[6]}: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.^{[7]}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^{[8]}. 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.^{[9]}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.^{[10]}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

CPW-Engine_0x88_math

CPW-Engine_board(0x88)

CPW-Engine_constants

CPW-Engine_move(0x88)

CPW-Engine_movegen(0x88)

## Publications

1981).Tiny Chess 86 - Een schaakprogramma voor de 8088/8086. Databus 06-81, pdf hosted by Hein Veldhuis1985).Inventive Problem Solving. ICCA Journal, Vol. 8, No. 41997)Rajah: The Design of a Chess Program.ICCA Journal, Vol. 20, No. 2 » Rajah## Forum Posts

## 1995 ...

## 2000 ...

## 2005 ...

## 2010 ...

## External Links

## References

1981).Tiny Chess 86 - Een schaakprogramma voor de 8088/8086. Databus 06-81, pdf hosted by Hein Veldhuis1985).Inventive Problem Solving. ICCA Journal, Vol. 8, No. 41994).A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7, pdf draft## What links here?

Up one Level