0x88

The 0x88 chess board representation is a square-centric method of representing the chess board used by some chess programs. The number 0x88 is a hexadecimal integer (13610, 2108, 100010002). The rank and file positions are each represented by a nibble (hexadecimal digit), and the bit gaps simplify a number of computations to bitwise operations.

Layout

In the 0x88 board representation, the layout is spread out to cover an 8-by-16 board, equal to the size of two adjacent chessboards. Each square of the 8-by-16 matrix is assigned a number as can be seen in the board layout table. In this scheme each nibble represents a rank or a file, so that the 8-bit integer 0x42 represents the square at (4,2) in zero-based numbering, i.e. c5 in standard algebraic notation.[1]

Adding 16 to a number for a square results in the number for the square one row above, and subtracting 16 results in the number for the square one row below. To move from one column to another the number is increased or decreased by one.[2] In hexadecimal notation, legal chess positions (A1-H8) are always below 0x88. This layout simplifies many computations that chess programs need to perform by allowing bitwise operations instead of comparisons.[3]

0x88 board layout[1]
0x00 (a)0x01 (b)0x02 (c)0x03 (d)0x04 (e)0x05 (f)0x06 (g)0x07 (h)0x080x090x0A0x0B0x0C0x0D0x0E0x0F
0x70 (8) 707172737475767778797A7B7C7D7E7F
0x60 (7) 606162636465666768696A6B6C6D6E6F
0x50 (6) 505152535455565758595A5B5C5D5E5F
0x40 (5) 404142434445464748494A4B4C4D4E4F
0x30 (4) 303132333435363738393A3B3C3D3E3F
0x20 (3) 202122232425262728292A2B2C2D2E2F
0x10 (2) 101112131415161718191A1B1C1D1E1F
0x00 (1) 000102030405060708090A0B0C0D0E0F

Algebraic notation and conversion

Squares on a chess board with algebraic notation

Each square of the chessboard is identified by a unique coordinate pair — a letter between (a and h) for the file, and a number between 1 and 8 for the rank. This method of referring to squares is a part of algebraic notation. To convert a coordinate pair to a 0x88 value, files are treated as integers, with a corresponding to 0 and h corresponding to 7.

Thus, a1 corresponds to , with all 8 of the bits set to , b2 corresponds to , and h8 corresponds to .[1]

To convert an 0x88 value to a rank-file coordinate pair:

Applications

Off-the-board detection

Off-the-board detection is a feature of chess programs which determines whether a piece is on or off the legal chess board. In 0x88, the highest bit of each nibble represents whether a piece is on the board or not. Specifically, out of the 8 bits to represent a square, the fourth and the eighth must both be 0 for a piece to be located within the board.[4] This allows off-the-board detection by bitwise and operations. If $square AND 0x88 (or, in binary, 0b10001000) is non-zero, then the square is not on the board.[5] This bitwise operation requires fewer computer resources than integer comparisons. This makes calculations such as illegal move detection faster.[5]

Square relations

The difference of valid 0x88 coordinates A and B is unique with respect to distance and direction, which is not true for classical packed three-bit rank and file coordinates. That makes lookups for Manhattan distance, possible piece attacks, and legal piece moves more resource-friendly. While classical square coordinates in the 0–63 range require 4K-sized tables (64×64), the 0x88 difference takes 1/16 that or 256-sized tables—or even 16 less.[6]

An offset of 119 (0x77 as the maximum valid square index) is added, to make ±119 a 0–238 range (a size of 240 for alignment reasons).[6]

0×88Diff = 0×77 + A − B

Adoption

Though the 0x88 representation was initially popular, it has been mostly replaced by the system of bitboards.[7]

References

Works cited

  • Hyatt, Robert (2013). "Chess program board representations". Archived from the original on 12 February 2013. Retrieved 6 March 2020.
  • Reul, Fritz Max Heinrich (2009). New architectures in computer chess (Thesis). Gildeprint, TICC Dissertation Series 6. ISBN 9789490122249.
  • Østensen, Emil Fredrik (Autumn 2016). University of Oslo (PDF) (Master in programming and networks thesis). University of Oslo.
  • Moreland, Bruce (2007-07-16). "0x88 Move Generation". Archived from the original on 2007-07-16. Retrieved 2020-03-12.
  • Schalk, Andrea (August 7, 2008). "COMP30191 The Theory of Games and Game Models" (PDF). University of Manchester Department of Computer Science. Retrieved 2020-03-18.
  • Keen, Ben (November 2009). "A History of Computer Chess" (PDF). Laboratoire Bordelais de Recherche en Informatique. Archived from the original (PDF) on 2020-03-23. Retrieved 2020-03-23.
  • Dailly, Paul; Gotojuch, Dominik; Henning, Neil; Lawson, Keir; Macdonald, Alec; Tajaddinov, Tamerlan (March 18, 2008). "Chess Mantis A Chess Engine". Retrieved 2020-03-23.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.