0x88

From Chessprogramming wiki
Jump to: navigation, search

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

0x88,

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
A B C D E F G H

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 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 8086 assembly code snippets [4] :

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

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.

David Kittinger further in 2012 [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.
... and on the utilization of Memory [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.
... 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.

Conclusion

A combination of 0x88 and 10x12 Board with surrounded ranks, that is 16x12 or even 16x16 for a symmetric treatment of files and ranks (or 15x12, 15x15) seems slightly more efficient than pure 0x88 aka 16x8, making the "off the board" index condition almost redundant, since it can be combined with the coding of the guard or sentinal squares [11] [12] [13] [14] .

See also

CPW-Engine_0x88_math
CPW-Engine_board(0x88)
CPW-Engine_move(0x88)
CPW-Engine_movegen(0x88)

Publications

Forum Posts

1995 ...

Re: Sane numbers by Robert Hyatt, rgcc, June 29, 1996

2000 ...

Re: Question:1.hashtable 2.board 3.C by Eugene Nalimov, CCC, June 13, 2000
0x88 is not so smart by Christophe Théron, CCC, June 13, 2000

2005 ...

2010 ...

2015 ...

Re: Recommended board representation for a rookie by Harm Geert Muller, CCC, November 26, 2016

External Links

References

  1. Re: Fastest Conversion from 0x88 board to 8x8 board representation by Ricardo Gibert, CCC, July 06, 2001
  2. Re: X88 board representations by Robert Hyatt, rgcc, April 17, 1996
  3. Re: 0x88 by Robert Hyatt, CCC, January 11, 1999
  4. Jan Kuipers (1981). Tiny Chess 86 - Een schaakprogramma voor de 8088/8086. Databus 06-81, pdf hosted by Hein Veldhuis
  5. Paul Wiereyn (1985). Inventive Problem Solving. ICCA Journal, Vol. 8, No. 4
  6. 0x88 Move Generation by Bruce Moreland
  7. Re: Hello all by Dave Kittinger, CCC, April 26, 2012
  8. presumably in Pioneer, see also Boris Stilman (1994). A Linguistic Geometry of the Chess Model. Advances in Computer Chess 7
  9. Re: Hello all by Dave Kittinger, CCC, April 26, 2012
  10. Re: Hello all by Dave Kittinger, CCC, April 27, 2012
  11. Re: Question:1.hashtable 2.board 3.C by Christophe Théron, CCC, June 13, 2000
  12. Re: Fruit's Board Representation? by Fabien Letouzey, Winboard Forum, April 28, 2005
  13. Fritz Reul (2009). New Architectures in Computer Chess. Ph.D. Thesis, 2.2.1 Computer Chessboard Representation
  14. Re: Recommended board representation for a rookie by Harm Geert Muller, CCC, November 26, 2016

Up one Level