25,161
edits
Changes
0x88
,Created page with "'''Home * Board Representation * Mailbox * Vector Attacks * 0x88''' '''0x88''', a square centric board representation. It uses one [[Nibble|nibble]..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Mailbox]] * [[Vector Attacks]] * 0x88'''
'''0x88''',
a square centric board representation. It uses one [[Nibble|nibble]] for both [[Ranks|rank]] and [[Files|file]] each, to index the [[Pieces#PieceCoding|piece- or empty square codes]]. While the doubled [[Array|array]] size is negligible, the redundancy of the bit-gaps pays off for several applications. 0x88 is [[C]]-syntax and the [https://en.wikipedia.org/wiki/Hexadecimal hexadecimal] value of a mask of bits need to be zero for valid square coordinates (136 decimal, 210 [https://en.wikipedia.org/wiki/Octal octal], 10001000B).
=Layout=
In the 0x88 board-representation an 128 [[Byte|byte]] [[Array|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:
{| class="wikitable"
! !! 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:
<pre>
sq0x88 = 16 * rank07 + file07;
file07 = sq0x88 & 7;
rank07 = sq0x88 >> 4; // sq0x88 / 16
</pre>
0x88 index by a 0..63 8x8 square index needs to add the three upper rank bits:
<pre>
sq0x88 = sq8x8 + (sq8x8 & ~7);
</pre>
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: <ref>[https://www.stmintz.com/ccc/index.php?id=178502 Re: Fastest Conversion from 0x88 board to 8x8 board representation] by Ricardo Gibert, [[CCC]], July 06, 2001</ref>
<pre>
sq8x8 = (sq0x88 + (sq0x88 & 7)) >> 1;
</pre>
Of course, both calculations might be replaced by small lookup tables.
=Applications=
==Off the Board==
'Off the board' detection in [[Move Generation|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 [[Origin Square|from square]], to determine a [[Target Square|destination square]] - a cheap 'and' by 0x88 is appropriate for an 'off the board' test:
<pre>
if ( destination & 0x88) goto invalid square
</pre>
That is the trick with 0x88 - but it gains by an additional property.
==<span id="SquareRelations"></span>Square Relations==
The difference of valid 0x88 coordinates A and B is uniquely with respect to [[Distance|distance]] and [[Direction|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|distance]], [[Manhattan-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).
<pre>
0x88Diff = 0x77 + A - B
</pre>
==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|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|bitboards]] in the 1982-83 time-frame <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/qzs01XFt_6I/Usj8w4SnPjMJ Re: X88 board representations] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 17, 1996</ref> . 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]]) <ref>[https://www.stmintz.com/ccc/index.php?id=39085 Re: 0x88] by [[Robert Hyatt]], [[CCC]], January 11, 1999</ref>.
==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|assembly]] code snippets <ref>[[Jan Kuipers]] ('''1981'''). ''Tiny Chess 86 - Een schaakprogramma voor de 8088/8086''. [http://home.kpn.nl/a.dikker1/museum/databus.html Databus] 06-81, [http://www.schaakcomputers.nl/hein_veldhuis/database/files/06-1981,%20Databus,%20Jan%20Kuipers,%20Tiny%20Chess%2086.pdf pdf] hosted by [[Hein Veldhuis]]</ref> :
<pre>
0634 03FA 109 ADD DI,DX ;CALC. SQ. MOVING TO
0636 F7C78800 110 TEST DI,88H ;OFF BOARD?
063A 750C 111 JNZ G4 ;YES
</pre>
==Wiereyn==
In his 1985 paper ''Inventive Problem Solving'' <ref>[[Paul Wiereyn]] ('''1985'''). ''Inventive Problem Solving''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]</ref> , [[Paul Wiereyn]] described coordinates with nibbles for ranks and files inside a [[Byte|byte]], and used such square differences (mod 256) as table-index to determine [[Pin|pinned pieces]] and [[Discovered Check|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.
<pre>
Rd5 - Kf5 <=> 45 - 65 = E0, hexadecimals and reduction modulo 256
being implied throughout.
</pre>
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 <ref>[http://web.archive.org/web/20070716111804/www.brucemo.com/compchess/programming/0x88.htm 0x88 Move Generation] by [[Bruce Moreland]]</ref> :
When I was at the Hong Kong [[WCCC 1995|WCCC in 1995]], I had some conversations with [[David Kittinger]]. He told me about a [[Move Generation|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 [https://en.wikipedia.org/wiki/Hexadecimal 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 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462693&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 26, 2012</ref>
I was told this technique at I believe the [[WMCCC 1981|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 [[Mikhail Botvinnik|Michael Botvinnik]] (Former USSR World Champion) as something used in a version of [[Kaissa]] <ref>presumably in [[Pioneer]], see also [[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]]</ref>. 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]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462700&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 26, 2012</ref>
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 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462734&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 27, 2012</ref>
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 [[MVV-LVA|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 [[Sliding Pieces|slider]] and had [[Square Attacked By#By0x88Difference|path clear]]. Of course, w and b pawns had different [[Pieces#PieceTypeCoding|type]] bits. Made for a decently fast and ordered [[Quiescence Search|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 <ref>[https://www.stmintz.com/ccc/index.php?id=114377 Re: Question:1.hashtable 2.board 3.C] by [[Christophe Théron]], [[Computer Chess Forums|CCC]], June 13, 2000</ref> <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2407&p=11195#p11109 Re: Fruit's Board Representation?] by [[Fabien Letouzey]], [[Computer Chess Forums|Winboard Forum]], April 28, 2005</ref> <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, 2.2.1 ''Computer Chessboard Representation''</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=62279&start=6 Re: Recommended board representation for a rookie] by [[Harm Geert Muller]], [[CCC]], November 26, 2016</ref> .
=See also=
* [[Rajah#0x88|0x88 in Rajah]]
* [[Square Attacked By#By0x88Difference|0x88 meets Bitboards]]
* [[CPW-Engine]], the didactical 0x88 chess engine
: [[CPW-Engine_0x88_math]]
: [[CPW-Engine_board(0x88)]]
: [[CPW-Engine_constants]]
: [[CPW-Engine_move(0x88)]]
: [[CPW-Engine_movegen(0x88)]]
* [[Intersection Squares]] as application of 0x88 coordinates
=Publications=
* [[Jan Kuipers]] ('''1981'''). ''Tiny Chess 86 - Een schaakprogramma voor de 8088/8086''. [http://home.kpn.nl/a.dikker1/museum/databus.html Databus] 06-81, [http://www.schaakcomputers.nl/hein_veldhuis/database/files/06-1981,%20Databus,%20Jan%20Kuipers,%20Tiny%20Chess%2086.pdf pdf] hosted by [[Hein Veldhuis]]
* [[Paul Wiereyn]] ('''1985'''). ''Inventive Problem Solving''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]
* [[Valavan Manohararajah]] ('''1997''') ''Rajah: The Design of a Chess Program.'' [[ICGA Journal#20_2|ICCA Journal, Vol. 20, No. 2]] » [[Rajah]]
=Forum Posts=
==1995 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/MrZsomJL5wU/wvw97iD-PncJ What is X88 in computing chess ?] by Guido Stepken, [[Computer Chess Forums|rgcc]], April 07, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/qzs01XFt_6I/yyX6rwauT8UJ X88 board representations] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgcc]], April 17, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/NgHWjDZ43H8/iSJ-WR8BtLYJ Sane numbers] by [[Martin Borriss]], [[Computer Chess Forums|rgcc]], June 29, 1996
: [https://groups.google.com/d/msg/rec.games.chess.computer/NgHWjDZ43H8/FUl1b9ZjCMIJ Re: Sane numbers] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], June 29, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/1WniS0H_7UY/ObJXK3HKgjEJ Help with x88] by John Stoneham, [[Computer Chess Forums|rgcc]], June 30, 1996
* [https://www.stmintz.com/ccc/index.php?id=39080 0x88] by [[Daniel Clausen]], [[CCC]], January 11, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=114377 Re: Question:1.hashtable 2.board 3.C] by [[Christophe Théron]], [[CCC]], June 13, 2000
: [https://www.stmintz.com/ccc/index.php?id=114385 Re: Question:1.hashtable 2.board 3.C] by [[Eugene Nalimov]], [[CCC]], June 13, 2000
: [https://www.stmintz.com/ccc/index.php?id=114438 0x88 is not so smart] by [[Christophe Théron]], [[Computer Chess Forums|CCC]], June 13, 2000
* [https://www.stmintz.com/ccc/index.php?id=178465 Fastest Conversion from 0x88 board to 8x8 board representation] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], July 06, 2001
* [https://www.stmintz.com/ccc/index.php?id=262916 0x88 revisited] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], November 01, 2002
* [https://groups.google.com/d/msg/rec.games.chess.computer/fVq45InKdyc/SZMHX1Efa20J 0x88 and mailbox] by [[Jean-François Gazet]], [[Computer Chess Forums|rgcc]], December 03, 2003
* [https://groups.google.com/d/msg/rec.games.chess.computer/1FaB4tZT0l4/z9ZHuyq0Gg4J Board representation 0x88 or bitboard] by Rohit, [[Computer Chess Forums|rgcc]], October 03, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2407&p=11195#p11109 Re: Fruit's Board Representation?] by [[Fabien Letouzey]], [[Computer Chess Forums|Winboard Forum]], April 28, 2005
* [https://www.stmintz.com/ccc/index.php?id=481916 Simple 0x88 move generation source code] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], January 24, 2006
* [https://www.stmintz.com/ccc/index.php?id=488440 0x88 findings] by Sean Mintz, [[CCC]], February 21, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4442 Board representation : 0x88 or 10x12 ?] by Philippe, [[Computer Chess Forums|Winboard Forum]], March 02, 2006 » [[10x12 Board]]
* [http://www.talkchess.com/forum/viewtopic.php?t=17361 is there a 10x8 equivalent of 0x88] by [[Pawel Koziol]], [[CCC]], October 26, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=22316 O88 chess] by [[William H. Rogers]], [[CCC]], July 12, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=24466 0x88 board representation : basic question from beginner] by Von_Dingle, [[CCC]], October 18, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33276 0x88 move generation] by Jorma Nieminen, [[CCC]], March 15, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=34708 Problem with Move Gen in 0x88] by Suji, [[CCC]], June 04, 2010
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462693&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 26, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48173 0x88 with pointers] by [[Robert Pope]], [[CCC]], June 01, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=62279 Recommended board representation for a rookie] by [[Fred Hamilton]], [[CCC]], November 26, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=62279&start=6 Re: Recommended board representation for a rookie] by [[Harm Geert Muller]], [[CCC]], November 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62657 What're advantages of board 16x12?] by [[Pham Hong Nguyen|Nguyen Pham]], [[CCC]], December 30, 2016
=External Links=
* [https://en.wikipedia.org/wiki/Board_representation_%28chess%29#0x88_method 0x88 method, Board representation (chess) from Wikipedia]
* [http://web.archive.org/web/20070716111804/www.brucemo.com/compchess/programming/0x88.htm 0x88 Move Generation] by [[Bruce Moreland]]
* [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] by [[John Stanback]]
* [https://wannabe.guru.org/scott/hobbies/chess/ Monsoon/Typhoon Homepage] by [[Scott Gasch]]
* [http://mediocrechess.blogspot.com/2006/12/0x88-representation.html The 0x88 representation] from [http://mediocrechess.varten.org/index.html Mediocre Chess] by [[Jonatan Pettersson]]
=References=
<references />
'''[[Vector Attacks|Up one Level]]'''
'''0x88''',
a square centric board representation. It uses one [[Nibble|nibble]] for both [[Ranks|rank]] and [[Files|file]] each, to index the [[Pieces#PieceCoding|piece- or empty square codes]]. While the doubled [[Array|array]] size is negligible, the redundancy of the bit-gaps pays off for several applications. 0x88 is [[C]]-syntax and the [https://en.wikipedia.org/wiki/Hexadecimal hexadecimal] value of a mask of bits need to be zero for valid square coordinates (136 decimal, 210 [https://en.wikipedia.org/wiki/Octal octal], 10001000B).
=Layout=
In the 0x88 board-representation an 128 [[Byte|byte]] [[Array|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:
{| class="wikitable"
! !! 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:
<pre>
sq0x88 = 16 * rank07 + file07;
file07 = sq0x88 & 7;
rank07 = sq0x88 >> 4; // sq0x88 / 16
</pre>
0x88 index by a 0..63 8x8 square index needs to add the three upper rank bits:
<pre>
sq0x88 = sq8x8 + (sq8x8 & ~7);
</pre>
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: <ref>[https://www.stmintz.com/ccc/index.php?id=178502 Re: Fastest Conversion from 0x88 board to 8x8 board representation] by Ricardo Gibert, [[CCC]], July 06, 2001</ref>
<pre>
sq8x8 = (sq0x88 + (sq0x88 & 7)) >> 1;
</pre>
Of course, both calculations might be replaced by small lookup tables.
=Applications=
==Off the Board==
'Off the board' detection in [[Move Generation|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 [[Origin Square|from square]], to determine a [[Target Square|destination square]] - a cheap 'and' by 0x88 is appropriate for an 'off the board' test:
<pre>
if ( destination & 0x88) goto invalid square
</pre>
That is the trick with 0x88 - but it gains by an additional property.
==<span id="SquareRelations"></span>Square Relations==
The difference of valid 0x88 coordinates A and B is uniquely with respect to [[Distance|distance]] and [[Direction|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|distance]], [[Manhattan-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).
<pre>
0x88Diff = 0x77 + A - B
</pre>
==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|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|bitboards]] in the 1982-83 time-frame <ref>[https://groups.google.com/d/msg/rec.games.chess.computer/qzs01XFt_6I/Usj8w4SnPjMJ Re: X88 board representations] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], April 17, 1996</ref> . 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]]) <ref>[https://www.stmintz.com/ccc/index.php?id=39085 Re: 0x88] by [[Robert Hyatt]], [[CCC]], January 11, 1999</ref>.
==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|assembly]] code snippets <ref>[[Jan Kuipers]] ('''1981'''). ''Tiny Chess 86 - Een schaakprogramma voor de 8088/8086''. [http://home.kpn.nl/a.dikker1/museum/databus.html Databus] 06-81, [http://www.schaakcomputers.nl/hein_veldhuis/database/files/06-1981,%20Databus,%20Jan%20Kuipers,%20Tiny%20Chess%2086.pdf pdf] hosted by [[Hein Veldhuis]]</ref> :
<pre>
0634 03FA 109 ADD DI,DX ;CALC. SQ. MOVING TO
0636 F7C78800 110 TEST DI,88H ;OFF BOARD?
063A 750C 111 JNZ G4 ;YES
</pre>
==Wiereyn==
In his 1985 paper ''Inventive Problem Solving'' <ref>[[Paul Wiereyn]] ('''1985'''). ''Inventive Problem Solving''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]</ref> , [[Paul Wiereyn]] described coordinates with nibbles for ranks and files inside a [[Byte|byte]], and used such square differences (mod 256) as table-index to determine [[Pin|pinned pieces]] and [[Discovered Check|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.
<pre>
Rd5 - Kf5 <=> 45 - 65 = E0, hexadecimals and reduction modulo 256
being implied throughout.
</pre>
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 <ref>[http://web.archive.org/web/20070716111804/www.brucemo.com/compchess/programming/0x88.htm 0x88 Move Generation] by [[Bruce Moreland]]</ref> :
When I was at the Hong Kong [[WCCC 1995|WCCC in 1995]], I had some conversations with [[David Kittinger]]. He told me about a [[Move Generation|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 [https://en.wikipedia.org/wiki/Hexadecimal 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 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462693&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 26, 2012</ref>
I was told this technique at I believe the [[WMCCC 1981|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 [[Mikhail Botvinnik|Michael Botvinnik]] (Former USSR World Champion) as something used in a version of [[Kaissa]] <ref>presumably in [[Pioneer]], see also [[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]]</ref>. 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]] <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462700&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 26, 2012</ref>
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 <ref>[http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462734&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 27, 2012</ref>
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 [[MVV-LVA|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 [[Sliding Pieces|slider]] and had [[Square Attacked By#By0x88Difference|path clear]]. Of course, w and b pawns had different [[Pieces#PieceTypeCoding|type]] bits. Made for a decently fast and ordered [[Quiescence Search|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 <ref>[https://www.stmintz.com/ccc/index.php?id=114377 Re: Question:1.hashtable 2.board 3.C] by [[Christophe Théron]], [[Computer Chess Forums|CCC]], June 13, 2000</ref> <ref>[http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2407&p=11195#p11109 Re: Fruit's Board Representation?] by [[Fabien Letouzey]], [[Computer Chess Forums|Winboard Forum]], April 28, 2005</ref> <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, 2.2.1 ''Computer Chessboard Representation''</ref> <ref>[http://www.talkchess.com/forum/viewtopic.php?t=62279&start=6 Re: Recommended board representation for a rookie] by [[Harm Geert Muller]], [[CCC]], November 26, 2016</ref> .
=See also=
* [[Rajah#0x88|0x88 in Rajah]]
* [[Square Attacked By#By0x88Difference|0x88 meets Bitboards]]
* [[CPW-Engine]], the didactical 0x88 chess engine
: [[CPW-Engine_0x88_math]]
: [[CPW-Engine_board(0x88)]]
: [[CPW-Engine_constants]]
: [[CPW-Engine_move(0x88)]]
: [[CPW-Engine_movegen(0x88)]]
* [[Intersection Squares]] as application of 0x88 coordinates
=Publications=
* [[Jan Kuipers]] ('''1981'''). ''Tiny Chess 86 - Een schaakprogramma voor de 8088/8086''. [http://home.kpn.nl/a.dikker1/museum/databus.html Databus] 06-81, [http://www.schaakcomputers.nl/hein_veldhuis/database/files/06-1981,%20Databus,%20Jan%20Kuipers,%20Tiny%20Chess%2086.pdf pdf] hosted by [[Hein Veldhuis]]
* [[Paul Wiereyn]] ('''1985'''). ''Inventive Problem Solving''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]
* [[Valavan Manohararajah]] ('''1997''') ''Rajah: The Design of a Chess Program.'' [[ICGA Journal#20_2|ICCA Journal, Vol. 20, No. 2]] » [[Rajah]]
=Forum Posts=
==1995 ...==
* [https://groups.google.com/d/msg/rec.games.chess.computer/MrZsomJL5wU/wvw97iD-PncJ What is X88 in computing chess ?] by Guido Stepken, [[Computer Chess Forums|rgcc]], April 07, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/qzs01XFt_6I/yyX6rwauT8UJ X88 board representations] by [[Valavan Manohararajah]], [[Computer Chess Forums|rgcc]], April 17, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/NgHWjDZ43H8/iSJ-WR8BtLYJ Sane numbers] by [[Martin Borriss]], [[Computer Chess Forums|rgcc]], June 29, 1996
: [https://groups.google.com/d/msg/rec.games.chess.computer/NgHWjDZ43H8/FUl1b9ZjCMIJ Re: Sane numbers] by [[Robert Hyatt]], [[Computer Chess Forums|rgcc]], June 29, 1996
* [https://groups.google.com/d/msg/rec.games.chess.computer/1WniS0H_7UY/ObJXK3HKgjEJ Help with x88] by John Stoneham, [[Computer Chess Forums|rgcc]], June 30, 1996
* [https://www.stmintz.com/ccc/index.php?id=39080 0x88] by [[Daniel Clausen]], [[CCC]], January 11, 1999
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=114377 Re: Question:1.hashtable 2.board 3.C] by [[Christophe Théron]], [[CCC]], June 13, 2000
: [https://www.stmintz.com/ccc/index.php?id=114385 Re: Question:1.hashtable 2.board 3.C] by [[Eugene Nalimov]], [[CCC]], June 13, 2000
: [https://www.stmintz.com/ccc/index.php?id=114438 0x88 is not so smart] by [[Christophe Théron]], [[Computer Chess Forums|CCC]], June 13, 2000
* [https://www.stmintz.com/ccc/index.php?id=178465 Fastest Conversion from 0x88 board to 8x8 board representation] by [[Artem Petakov|Artem Pyatakov]], [[CCC]], July 06, 2001
* [https://www.stmintz.com/ccc/index.php?id=262916 0x88 revisited] by [[Tony van Roon-Werten|Tony Werten]], [[CCC]], November 01, 2002
* [https://groups.google.com/d/msg/rec.games.chess.computer/fVq45InKdyc/SZMHX1Efa20J 0x88 and mailbox] by [[Jean-François Gazet]], [[Computer Chess Forums|rgcc]], December 03, 2003
* [https://groups.google.com/d/msg/rec.games.chess.computer/1FaB4tZT0l4/z9ZHuyq0Gg4J Board representation 0x88 or bitboard] by Rohit, [[Computer Chess Forums|rgcc]], October 03, 2004
==2005 ...==
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=2407&p=11195#p11109 Re: Fruit's Board Representation?] by [[Fabien Letouzey]], [[Computer Chess Forums|Winboard Forum]], April 28, 2005
* [https://www.stmintz.com/ccc/index.php?id=481916 Simple 0x88 move generation source code] by [[Federico Andrés Corigliano|Federico Corigliano]], [[CCC]], January 24, 2006
* [https://www.stmintz.com/ccc/index.php?id=488440 0x88 findings] by Sean Mintz, [[CCC]], February 21, 2006
* [http://www.open-aurec.com/wbforum/viewtopic.php?f=4&t=4442 Board representation : 0x88 or 10x12 ?] by Philippe, [[Computer Chess Forums|Winboard Forum]], March 02, 2006 » [[10x12 Board]]
* [http://www.talkchess.com/forum/viewtopic.php?t=17361 is there a 10x8 equivalent of 0x88] by [[Pawel Koziol]], [[CCC]], October 26, 2007
* [http://www.talkchess.com/forum/viewtopic.php?t=22316 O88 chess] by [[William H. Rogers]], [[CCC]], July 12, 2008
* [http://www.talkchess.com/forum/viewtopic.php?t=24466 0x88 board representation : basic question from beginner] by Von_Dingle, [[CCC]], October 18, 2008
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=33276 0x88 move generation] by Jorma Nieminen, [[CCC]], March 15, 2010
* [http://www.talkchess.com/forum/viewtopic.php?t=34708 Problem with Move Gen in 0x88] by Suji, [[CCC]], June 04, 2010
* [http://www.talkchess.com/forum/viewtopic.php?topic_view=threads&p=462693&t=43447 Re: Hello all] by [[David Kittinger|Dave Kittinger]], [[CCC]], April 26, 2012
* [http://www.talkchess.com/forum/viewtopic.php?t=48173 0x88 with pointers] by [[Robert Pope]], [[CCC]], June 01, 2013
==2015 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=62279 Recommended board representation for a rookie] by [[Fred Hamilton]], [[CCC]], November 26, 2016
: [http://www.talkchess.com/forum/viewtopic.php?t=62279&start=6 Re: Recommended board representation for a rookie] by [[Harm Geert Muller]], [[CCC]], November 26, 2016
* [http://www.talkchess.com/forum/viewtopic.php?t=62657 What're advantages of board 16x12?] by [[Pham Hong Nguyen|Nguyen Pham]], [[CCC]], December 30, 2016
=External Links=
* [https://en.wikipedia.org/wiki/Board_representation_%28chess%29#0x88_method 0x88 method, Board representation (chess) from Wikipedia]
* [http://web.archive.org/web/20070716111804/www.brucemo.com/compchess/programming/0x88.htm 0x88 Move Generation] by [[Bruce Moreland]]
* [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] by [[John Stanback]]
* [https://wannabe.guru.org/scott/hobbies/chess/ Monsoon/Typhoon Homepage] by [[Scott Gasch]]
* [http://mediocrechess.blogspot.com/2006/12/0x88-representation.html The 0x88 representation] from [http://mediocrechess.varten.org/index.html Mediocre Chess] by [[Jonatan Pettersson]]
=References=
<references />
'''[[Vector Attacks|Up one Level]]'''
