View source for 0x88

{{about|a chess programming concept|the number|0x88 (number)}}
{{Chess programming series}}
The '''0x88 chess board representation''' is a square-centric method of [[Board representation (computer chess)|representing the chess board]] in [[chess engine|computer chess programs]]. The [[136 (number)|number 0x88]] is a [[hexadecimal]] integer (136{{sub|[[decimal|10]]}}, 210{{sub|[[octal system|8]]}}, 10001000{{sub|[[Binary number|2]]}}). The rank and file positions are each represented by a [[nibble]] (hexadecimal digit), and the bit gaps simplify a number of computations to [[bitwise operation]]s.

==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 (chess)|algebraic notation]].{{sfn|Hyatt|2013}}

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.{{sfn|Schalk|2008}} In hexadecimal notation, legal chess positions (A1-H8) are always below 0x88. This layout simplifies many computations that [[chess program]]s need to perform by allowing bitwise operations instead of comparisons.{{sfn|Østensen|2016}}

{| class="wikitable"
|+ 0x88 board layout{{sfn|Hyatt|2013}}
! !! 0x00 (a) !! 0x01 (b) !! 0x02 (c) !! 0x03 (d) !! 0x04 (e) !! 0x05 (f) !! 0x06 (g) !! 0x07 (h) !! 0x08 !! 0x09 !! 0x0A !! 0x0B !! 0x0C !! 0x0D !! 0x0E !! 0x0F
|- 
! 0x70 (8)
| '''70''' || '''71''' || '''72''' || '''73''' || '''74''' || '''75''' || '''76''' || '''77''' || 78 || 79 || 7A || 7B || 7C || 7D || 7E || 7F
|- 
! 0x60 (7)
| '''60''' || '''61''' || '''62''' || '''63''' || '''64''' || '''65''' || '''66''' || '''67''' || 68 || 69 || 6A || 6B || 6C || 6D || 6E || 6F
|- 
! 0x50 (6)
| '''50''' || '''51''' || '''52''' || '''53''' || '''54''' || '''55''' || '''56''' || '''57''' || 58 || 59 || 5A || 5B || 5C || 5D || 5E || 5F
|- 
! 0x40 (5)
| '''40''' || '''41''' || '''42''' || '''43''' || '''44''' || '''45''' || '''46''' || '''47''' || 48 || 49 || 4A || 4B || 4C || 4D || 4E || 4F
|- 
! 0x30 (4)
| '''30''' || '''31''' || '''32''' || '''33''' || '''34''' || '''35''' || '''36''' || '''37''' || 38 || 39 || 3A || 3B || 3C || 3D || 3E || 3F
|- 
! 0x20 (3)
| '''20''' || '''21''' || '''22''' || '''23''' || '''24''' || '''25''' || '''26''' || '''27''' || 28 || 29 || 2A || 2B || 2C || 2D || 2E || 2F
|- 
! 0x10 (2)
| '''10''' || '''11''' || '''12''' || '''13''' || '''14''' || '''15''' || '''16''' || '''17''' || 18 || 19 || 1A || 1B || 1C || 1D || 1E || 1F
|- 
! 0x00 (1)
| '''00''' || '''01''' || '''02''' || '''03''' || '''04''' || '''05''' || '''06''' || '''07''' || 08 || 09 || 0A || 0B || 0C || 0D || 0E || 0F
|}

== Algebraic notation and conversion ==
[[File:SCD algebraic notation.svg|thumb|right|Squares on a chess board with algebraic notation]]
{{see also|Algebraic notation (chess)}}

The modern standard to identify the squares on a chessboard and moves in a game is [[Algebraic notation (chess)|algebraic notation]], whereby each square of the board is identified by a unique coordinate pair — a letter between ''a'' and ''h'' for the horizontal coordinate, known as the file, and a number between 1 and 8 for the vertical coordinate, known as the rank.

In computer chess, file-rank coordinates are internally represented as integers ranging from 0 to 7, with file ''a'' mapping to 0 through to file ''h'' mapping to 7, while the rank coordinate is shifted down by one to the range 0 to 7.

An advantage of the 0x88 coding scheme is that values can be easily converted between 0x88 representation and file-rank coordinates using only [[bitwise operation]]s, which are simple and efficient for computer processors to work with. To convert a [[Zero-based numbering|zero-based]] file-rank coordinate to 0x88 value:

: <math> \text{square}_{0\rm{x}88} = (\text{rank}_\text{0 to 7} << 4) + \text{file}_\text{0 to 7}</math>

Thus, ''a''1 corresponds to <math>00000000_2</math>, with all 8 of the bits set to <math>0</math>, ''b''2 corresponds to <math>00010001_2</math>, and ''h''8 corresponds to <math>01110111_2</math>.{{sfn|Hyatt|2013}}

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

: <math> \text{file}_\text{0 to 7} = \text{square}_{0\rm{x}88}\ \&\ 7</math>

: <math> \text{rank}_\text{0 to 7} = ( \text{square}_{0\rm{x}88}\ >> 4 )</math>

''Note: In the above formulas, '''<<''' and '''>>''' represent left and right [[Logical shift|logical bit shift]] operations respectively while '''&''' represents [[bitwise and]].''
{{clear}}

==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.{{sfn|Dailly|Gotojuch|Henning|Lawson|2008}} This allows off-the-board detection by [[bitwise]] {{smallcaps|and}} operations. If <code>$square AND 0x88</code> (or, in binary, <code>0b10001000</code>) is non-zero, then the square is not on the board.{{sfn|Reul|2009}} This bitwise operation requires fewer computer resources than integer comparisons. This makes calculations such as illegal move detection faster.{{sfn|Reul|2009}}

===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.{{sfn|Moreland|2007}}

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).{{sfn|Moreland|2007}}
<pre>
0x88Diff = 0x77 + A − B
</pre>

== Adoption ==
{{see also|Bitboard#Chess bitboards}}
Though the 0x88 representation was initially popular, it has been mostly replaced by the system of [[Bitboard#Chess bitboards|bitboards]].{{sfn|Keen|2009}}

==References==
{{reflist}}

=== Works cited ===
{{refbegin}}
*{{cite web|url=http://www.cis.uab.edu/hyatt/boardrep.html|title=Chess program board representations|last=Hyatt|first=Robert|year=2013|author-link=Robert Hyatt|archive-url=https://web.archive.org/web/20130212063528/http://www.cis.uab.edu/hyatt/boardrep.html|url-status=dead|archive-date=12 February 2013|access-date=6 March 2020}}
*{{Cite thesis|last=Reul|first=Fritz Max Heinrich|title=New architectures in computer chess|date=2009|publisher=Gildeprint, TICC Dissertation Series 6|url=https://research.tilburguniversity.edu/en/publications/new-architectures-in-computer-chess|isbn=9789490122249}}
*{{Cite thesis|last=Østensen|first=Emil Fredrik|title=University of Oslo|date=Autumn 2016|degree=Master in programming and networks|publisher=University of Oslo|url=https://www.duo.uio.no/bitstream/handle/10852/53769/master.pdf}}
*{{Cite web|url=http://www.brucemo.com/compchess/programming/0x88.htm|archive-url=https://web.archive.org/web/20070716111804/http://www.brucemo.com/compchess/programming/0x88.htm|url-status=dead|archive-date=2007-07-16|title=0x88 Move Generation|last=Moreland|first=Bruce|date=2007-07-16|access-date=2020-03-12}}
*{{Cite web|url=http://www.cs.man.ac.uk/~schalk/3192/notes.pdf|title=COMP30191 The Theory of Games and Game Models|last=Schalk|first=Andrea|date=August 7, 2008|website=University of Manchester Department of Computer Science|access-date=2020-03-18}}
*{{cite web|url=https://www.labri.fr/perso/fleury/courses/pdp/Board_Games/Chess/LitReview.pdf|title=A History of Computer Chess|last=Keen|first=Ben|date=November 2009|website=Laboratoire Bordelais de Recherche en Informatique|access-date=2020-03-23|archive-date=2020-03-23|archive-url=https://web.archive.org/web/20200323045059/https://www.labri.fr/perso/fleury/courses/pdp/Board_Games/Chess/LitReview.pdf|url-status=dead}}
*{{cite web|url=https://www.researchgate.net/publication/268426213|title=Chess Mantis A Chess Engine|last1=Dailly|first1=Paul|last2=Gotojuch|first2=Dominik|last3=Henning|first3=Neil|last4=Lawson|first4=Keir|last5=Macdonald|first5=Alec|last6=Tajaddinov|first6=Tamerlan|date=March 18, 2008|access-date=2020-03-23}}
{{refend}}

==External links==
* [http://www.craftychess.com/hyatt/boardrep.html Chess board representations] by [[Robert Hyatt]]
* [http://john.stanback.net/zarkov/zarkov_methods.html How Zarkov Plays Chess] {{Webarchive|url=https://web.archive.org/web/20200819041139/http://john.stanback.net/zarkov/zarkov_methods.html |date=2020-08-19 }} by [[John Stanback]]
* [http://mediocrechess.blogspot.com/2006/12/0x88-representation.html The 0x88 representation] from [http://mediocrechess.varten.org/index.html Mediocre Chess] {{Webarchive|url=https://web.archive.org/web/20180820110756/http://mediocrechess.varten.org/index.html |date=2018-08-20 }} by [[Jonatan Pettersson]]

[[Category:Computer chess]]