25,161
edits
Changes
Created page with "'''Home * Board Representation * Mailbox * Vector Attacks''' File:Position vector.svg|right|thumb|Position Vector <ref>A vector in the [https://en.wik..."
'''[[Main Page|Home]] * [[Board Representation]] * [[Mailbox]] * Vector Attacks'''
[[File:Position vector.svg|right|thumb|Position Vector <ref>A vector in the [https://en.wikipedia.org/wiki/Cartesian_coordinate_system Cartesian plane], showing the position of a point A with coordinates (2,3), [https://en.wikipedia.org/wiki/Euclidean_vector Euclidean vector from Wikipedia]</ref>]]
'''Vector Attacks''' <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>,
the application of [https://en.wikipedia.org/wiki/Euclidean_vector vectors] in the [https://en.wikipedia.org/wiki/Chebyshev_distance Chebyshev] [https://en.wikipedia.org/wiki/Vector_space vector space] of a [[Chessboard|chessboard]] to the problem of chess [[Attacks|attacks]], including [[Static Exchange Evaluation|static exchange evaluation (SEE)]], and testing whether [[Moves|moves]] are [[Pseudo-Legal Move|pseudo-legal]].
=Displacement and Position Vectors=
A [https://en.wikipedia.org/wiki/Displacement_%28vector%29 displacement vector] is a [https://en.wikipedia.org/wiki/Tuple tuple] of [[Ranks|rank]]- and [[Files|file]]-difference of two [[Squares|squares]], for instance [[Origin Square|from]] and [[Target Square|to square]] of a [[Moves|move]].
[[File:Vector Attacks_1.jpg|none|border|text-bottom]]
The [https://en.wikipedia.org/wiki/Position_%28vector%29 position vector] of square A is the displacement to an arbitrary reference origin O.
[[File:Vector Attacks_2.jpg|none|border|text-bottom]]
=Vector Boards=
Vector board arrays with a one-dimensional, scalar index, require the difference of any two mailbox square indices preserve their rank- and file-difference and therefore their [[Direction|direction]] and [[Distance|distance]] relationship, which implies using the number of file differences as array dimension - which is '''15''' rather than 8 for the number of files. Therefore, the 8x8 mailbox needs at least 7 padded columns (files) of a 15xNROWS (or 16xNROWS) vector array:
[[File:Vector Attacks_3.jpg|none|border|text-bottom]]
or
[[File:Vector Attacks_4.jpg|none|border|text-bottom]]
=Vector as Index=
Represented as such a square difference, displacement vectors can be used to index 225 (15x15) or 240 (16x15) sized lookup tables for stuff dependent on square relations, that is [[Distance#15x15|Chebyshev distance]], [[Manhattan-Distance|Manhattan-distance]], boolean [[Rays|ray properties]] and most importantly, [[#IncrementVectors|increment vectors]] along a ray, or in the world of [[Bitboards|bitboards]], [[Square Attacked By#By0x88Difference|rotated in-between]] sets. Thus, the up to fourfold board size of the vector boards, largely pays off, since pure 8x8 coordinates would require two-dimensional [[Butterfly Boards|butterfly tables]] of size 4096 indexed by two square indices for the same purpose. To keep indices positive, an offset of 112 respective 119 (120) is added.
=<span id="Superimposition"></span>Superimposed Lookup=
8x8 tables inside 15x15 tables were already proposed by [[Mikhail Botvinnik]] as used in [[Pioneer]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref>. The table below demonstrates the vector enumeration from a square (here c2) on a 8x8 board, superimposed on the 15x15 array in such a way that the from square (c2) coincides with the central square of the 15x15 array, which is the origin, tail, or base of all displacement vectors.
<pre>
╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
210 ║ 98| 99 | 100| 101| 102| 103| 104| 105| 106| 107| 108| 109| 110| 111| 112║
╟────┼────┼────┼────┼────╔════╤════╤════╤════╤════╤════╤════╤════╗────┼────╢
195 ║ 83| 84| 85| 86| 87║ 88| 89| 90| 91| 92| 93| 94| 95║ 96| 97║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
180 ║ 68| 69| 70| 71| 72║ 73| 74| 75| 76| 77| 78| 79| 80║ 81| 82║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
165 ║ 53| 54| 55| 56| 57║ 58| 59| 60| 61| 62| 63| 64| 65║ 66| 67║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
150 ║ 38| 39| 40| 41| 42║ 42| 44| 45| 46| 47| 48| 49| 50║ 51| 52║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
135 ║ 23| 24| 25| 26| 27║ 28| 29| 30| 31| 32| 33| 34| 35║ 36| 37║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
120 ║ 8| 9| 10| 11| 12║ 13| 14| 15| 16| 17| 18| 19| 20║ 21| 22║
╟────┼────┼────┼────┼────╟────┼────╔════╗────┼────┼────┼────┼────╢────┼────╢
105 ║ -7| -6| -5| -4| -3║ -2| -1║ 0║ 1| 2| 3| 4| 5║ 6| 7║
╟────┼────┼────┼────┼────╟────┼────╚════╝────┼────┼────┼────┼────╢────┼────╢
90 ║ -22| -21| -20| -19| -18║ -17| -16| -15| -14| -13| -12| -11| -10║ -9| -8║
╟────┼────┼────┼────┼────╚════╧════╧════╧════╧════╧════╧════╧════╝────┼────╢
75 ║ -37| -36| -35| -34| -33| -32| -31| -30| -29| -28| -27| -26| -25| -24| -23║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
60 ║ -52| -51| -50| -49| -48| -47| -46| -45| -44| -43| -42| -41| -40| -39| -38║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
45 ║ -67| -66| -65| -64| -63| -62| -61| -60| -59| -58| -57| -56| -55| -54| -53║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
30 ║ -82| -81| -80| -79| -78| -77| -76| -75| -74| -73| -72| -71| -70| -66| -68║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
15 ║ -97| -96| -95| -94| -93| -92| -91| -90| -89| -88| -87| -86| -85| -84| -83║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
0 ║-112|-111|-110|-109|-108|-107|-106|-105|-104|-103|-102|-101|-100| -99| -98║
╚════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
</pre>
=<span id="RayVectors"></span>Ray Vectors=
[[Rays|Ray]] vectors are [https://en.wikipedia.org/wiki/Unit_vector unit vectors] to [https://en.wikipedia.org/wiki/Moore_neighborhood eight neighboring] squares, [https://en.wikipedia.org/wiki/Scalar_multiplication scaled] by [[Distance#15x15|Chebyshev distance]]. In the domain of [[Sliding Pieces|sliding piece]] attacks, unit vectors act as [[#IncrementVectors|increment vectors]] if none zero, to determine squares in-between are empty, and a [[Target Square|target square]] is attacked by a sliding piece on its [[Origin Square|origin]]. Following table demonstrates the [[Queen|queen]] unit or increment vectors, superimposed on the 15x15 array in such a way that the queen square (here c2) coincides with the central square of the 15x15 array.
<pre>
char rayUnitVectorQueen[15*15];
╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
210 ║ 14| | | | | | | 15| | | | | | | 16║
╟────┼────┼────┼────┼────╔════╤════╤════╤════╤════╤════╤════╤════╗────┼────╢
195 ║ | 14| | | ║ | | 15| | | | | ║ 16| ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
180 ║ | | 14| | ║ | | 15| | | | | 16║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
165 ║ | | | 14| ║ | | 15| | | | 16| ║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
150 ║ | | | | 14║ | | 15| | | 16| | ║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
135 ║ | | | | ║ 14| | 15| | 16| | | ║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
120 ║ | | | | ║ | 14| 15| 16| | | | ║ | ║
╟────┼────┼────┼────┼────╟────┼────╔════╗────┼────┼────┼────┼────╢────┼────╢
105 ║ -1| -1| -1| -1| -1║ -1| -1║ Q ║ 1| 1| 1| 1| 1║ 1| 1║
╟────┼────┼────┼────┼────╟────┼────╚════╝────┼────┼────┼────┼────╢────┼────╢
90 ║ | | | | ║ | -16| -15| -14| | | | ║ | ║
╟────┼────┼────┼────┼────╚════╧════╧════╧════╧════╧════╧════╧════╝────┼────╢
75 ║ | | | | | -16| | -15| | -14| | | | | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
60 ║ | | | | -16| | | -15| | | -14| | | | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
45 ║ | | | -16| | | | -15| | | | -14| | | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
30 ║ | | -16| | | | | -15| | | | | -14| | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
15 ║ | -16| | | | | | -15| | | | | | -14| ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
0 ║ -16| | | | | | | -15| | | | | | | -14║
╚════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
</pre>
=<span id="IncrementVectors"></span>Increment Vectors=
During offset [[Move Generation|move generation]], each piece applies a specific displacement or '''increment vector''' (offset) for each move direction, added to the position vector of the [[Origin Square|origin square]] to determine the next potential [[Target Square|move target]] in that direction, [[Sliding Pieces|sliding pieces]] continuing in the same direction as long the targets are empty. Due to the additional padded files and possibly ranks, off the board test are as simple as the [[10x12 Board|10x12 board]] with surrounding files and ranks containing off the board codes as [https://en.wikipedia.org/wiki/Sentinel_value sentinel values]. The [[0x88]] approach, a special 16x8 implementation of Vector Attacks, already indicates outside squares by its upper [[Nibble|nibble]] bits masked by 0x88.
One may argue, the 0x88 test is cheaper for off the board tests, because it does not need to lookup if the 0x88 test is true. On the other hand, for most cases, if false, it needs a lookup anyway, to perform a second test whether the square is empty, or occupied by an own or opponent piece <ref>[http://www.stmintz.com/ccc/index.php?id=114377 Re: Question:1.hashtable 2.board 3.C] by [[Christophe Théron]], [[CCC]], June 13, 2000</ref> <ref>[http://www.stmintz.com/ccc/index.php?id=114438 0x88 is not so smart] by [[Christophe Théron]], [[CCC]], June 13, 2000</ref>.
=<span id="NewArchitecture"></span>New Architecture=
Vector Attacks based on a 15x12 board were topic of [[Fritz Reul|Fritz Reul's]] Ph.D. thesis ''New Architectures in Computer Chess'', code samples given from Reul's [[Loop (Program)#32bit|Loop Leiden]] engine <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''</ref>.
==Source-Destination==
In conjunction with [[Pieces#DisjointPieceFlags|disjoint piece flags]] and [[Piece-Lists|piece-lists]], Vector Attacks allow efficient [[Move Generation|move generation]] of [[Sliding Pieces|sliding pieces]], even for [[Quiescence Search|quiescence search]] with a leading blocker loop:
<pre>
increment = rayVector[direction];
for (tosq = fromsq + increment; board[tosq] == EMPTY; tosq += increment);
if ( isOpponentPiece (board[tosq]) )
{
/* generate capture */
}
</pre>
==Destination-Source==
A destination-source blocker loop, to test whether a sliding piece on a from square attacks a target square, uses the reversed ray direction in order to dispense with additional conditions:
<pre>
increment = rayUnitVectorQueen[15*15/2 + fromsq - tosq];
if ( increment ) {
for (sq = tosq + increment; board[sq] == EMPTY; sq += increment);
if ( sq == fromsq ) {
/* a queen on fromsq attacks tosq */
}
}
</pre>
=Implementations=
==0x88==
''see main article [[0x88]]''
The [[0x88]] or 16x8 board uses [[Nibble|nibbles]] for both rank and file coordinates inside a [[Byte|byte]], and utilizes the redundant upper bit to indicate invalid squares outside the board, usually then not used as index.
===Layout===
<pre>
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
</pre>
===Coordinate Transformation===
16x8 square coordinate 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 square index needs to add the three upper rank bits:
<pre>
sq0x88 = sq + (sq & ~7);
</pre>
==15x12==
The odd number of files makes the [[Color of a Square|square color]] only dependent from the least significant index bit. Usually the seven surrounding border files are divided 4:3 (Offset 34) or 3:4 (Offset 33). One may also use 15x15 for a symmetric treatment of files and ranks as proposed by [[Fritz Reul]] <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''</ref> .
===Layout===
<pre>
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
</pre>
===Coordinate Transformation===
Coordinate transformation is usually not needed while generating moves, since [[Piece-Lists|piece-lists]], increments and move coordinates are only based on 15x12 coordinates. Anyway, for the sake of completeness valid 15x12 square transformation to file and rank indices and vice versa might be done quite efficiently without any [[x86]] div and mul instructions, but load effective address (lea) - otherwise simple lookup tables may used to convert coordinates:
<pre>
sq15x12 = 15 * rank07 + file07 + 34;
rank07 = ((sq15x12 - 34) * 9) >> 7; // div by reciprocal mul
file07 = sq15x12 - 34 - 15 * rank07; // % 15
</pre>
==16x12==
Usually the eight surrounding border files are divided 4:4, so the offset of the upper left square is 36. For a symmetric treatment of files and ranks, 16x16 is also quite common <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> .
===Layout===
<pre>
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
</pre>
===Coordinate Transformation===
16x12 square coordinate by file and rank and vice versa:
<pre>
sq16x12 = 16 * rank07 + file07 + 36;
rank07 = (sq16x12 - 36) >> 4; // div 16
file07 = (sq16x12 - 36) & 7; // % 8
</pre>
16x12 square index by a 0..63 square index needs to add the three upper rank bits plus offset:
<pre>
sq16x12 = sq8x8 + (sq8x8 & ~7) + 36;
</pre>
Convert 16x12 square index to 0..63 square index:
<pre>
file8x8 = (sq16x12 & 0xf) - 4
rank8x8 = ((sq16x12 >> 4) - 2
sq8x8 = (((sq16x12 >> 4) - 2) << 3) + (sq16x12 & 0xf) - 4;
</pre>
==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>[http://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=
* [[0x88]]
* [[Square Attacked By#By0x88Difference|0x88 meets Bitboards]]
* [[10x12 Board]]
* [[8x8 Board]]
* [[Distance]]
* [[Direction]]
* [[Intersection Squares]] as application of 0x88 coordinates
* [[Sliding Piece Attacks]] with [[Bitboards]]
=Publications=
* [[Mikhail Botvinnik]] ('''1968'''). ''Algoritm igry v shakhmaty''. (The algorithm of chess)
* [[Mikhail Botvinnik]] ('''1970'''). ''Computers, Chess and Long-Range Planning''. Springer
* [[Paul Wiereyn]] ('''1985'''). ''Inventive Problem Solving''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]
* [[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''
=Forum Posts=
* [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]], [[CCC]], June 13, 2000 » [[0x88]]
* [https://www.stmintz.com/ccc/index.php?id=178465 Fastest Conversion from 0x88 board to 8x8 board representation] by [[Artem Pyatakov]], July 06, 2001
* [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 » [[Fruit]]
* [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
=External Links=
* [https://en.wikipedia.org/wiki/Vector_%28mathematics_and_physics%29 Vector (mathematics and physics) from Wikipedia]
* [https://en.wikipedia.org/wiki/Euclidean_vector Euclidean vector from Wikipedia]
* [https://en.wikipedia.org/wiki/Position_%28vector%29 Position (vector) from Wikipedia]
* [https://en.wikipedia.org/wiki/Displacement_%28vector%29 Displacement (vector) from Wikipedia]
* [https://en.wikipedia.org/wiki/Linear_algebra Linear algebra from Wikipedia]
* [https://en.wikipedia.org/wiki/Vector_space Vector space from Wikipedia]
=References=
<references />
'''[[Mailbox|Up one Level]]'''
[[File:Position vector.svg|right|thumb|Position Vector <ref>A vector in the [https://en.wikipedia.org/wiki/Cartesian_coordinate_system Cartesian plane], showing the position of a point A with coordinates (2,3), [https://en.wikipedia.org/wiki/Euclidean_vector Euclidean vector from Wikipedia]</ref>]]
'''Vector Attacks''' <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>,
the application of [https://en.wikipedia.org/wiki/Euclidean_vector vectors] in the [https://en.wikipedia.org/wiki/Chebyshev_distance Chebyshev] [https://en.wikipedia.org/wiki/Vector_space vector space] of a [[Chessboard|chessboard]] to the problem of chess [[Attacks|attacks]], including [[Static Exchange Evaluation|static exchange evaluation (SEE)]], and testing whether [[Moves|moves]] are [[Pseudo-Legal Move|pseudo-legal]].
=Displacement and Position Vectors=
A [https://en.wikipedia.org/wiki/Displacement_%28vector%29 displacement vector] is a [https://en.wikipedia.org/wiki/Tuple tuple] of [[Ranks|rank]]- and [[Files|file]]-difference of two [[Squares|squares]], for instance [[Origin Square|from]] and [[Target Square|to square]] of a [[Moves|move]].
[[File:Vector Attacks_1.jpg|none|border|text-bottom]]
The [https://en.wikipedia.org/wiki/Position_%28vector%29 position vector] of square A is the displacement to an arbitrary reference origin O.
[[File:Vector Attacks_2.jpg|none|border|text-bottom]]
=Vector Boards=
Vector board arrays with a one-dimensional, scalar index, require the difference of any two mailbox square indices preserve their rank- and file-difference and therefore their [[Direction|direction]] and [[Distance|distance]] relationship, which implies using the number of file differences as array dimension - which is '''15''' rather than 8 for the number of files. Therefore, the 8x8 mailbox needs at least 7 padded columns (files) of a 15xNROWS (or 16xNROWS) vector array:
[[File:Vector Attacks_3.jpg|none|border|text-bottom]]
or
[[File:Vector Attacks_4.jpg|none|border|text-bottom]]
=Vector as Index=
Represented as such a square difference, displacement vectors can be used to index 225 (15x15) or 240 (16x15) sized lookup tables for stuff dependent on square relations, that is [[Distance#15x15|Chebyshev distance]], [[Manhattan-Distance|Manhattan-distance]], boolean [[Rays|ray properties]] and most importantly, [[#IncrementVectors|increment vectors]] along a ray, or in the world of [[Bitboards|bitboards]], [[Square Attacked By#By0x88Difference|rotated in-between]] sets. Thus, the up to fourfold board size of the vector boards, largely pays off, since pure 8x8 coordinates would require two-dimensional [[Butterfly Boards|butterfly tables]] of size 4096 indexed by two square indices for the same purpose. To keep indices positive, an offset of 112 respective 119 (120) is added.
=<span id="Superimposition"></span>Superimposed Lookup=
8x8 tables inside 15x15 tables were already proposed by [[Mikhail Botvinnik]] as used in [[Pioneer]] <ref>[[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]</ref>. The table below demonstrates the vector enumeration from a square (here c2) on a 8x8 board, superimposed on the 15x15 array in such a way that the from square (c2) coincides with the central square of the 15x15 array, which is the origin, tail, or base of all displacement vectors.
<pre>
╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
210 ║ 98| 99 | 100| 101| 102| 103| 104| 105| 106| 107| 108| 109| 110| 111| 112║
╟────┼────┼────┼────┼────╔════╤════╤════╤════╤════╤════╤════╤════╗────┼────╢
195 ║ 83| 84| 85| 86| 87║ 88| 89| 90| 91| 92| 93| 94| 95║ 96| 97║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
180 ║ 68| 69| 70| 71| 72║ 73| 74| 75| 76| 77| 78| 79| 80║ 81| 82║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
165 ║ 53| 54| 55| 56| 57║ 58| 59| 60| 61| 62| 63| 64| 65║ 66| 67║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
150 ║ 38| 39| 40| 41| 42║ 42| 44| 45| 46| 47| 48| 49| 50║ 51| 52║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
135 ║ 23| 24| 25| 26| 27║ 28| 29| 30| 31| 32| 33| 34| 35║ 36| 37║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
120 ║ 8| 9| 10| 11| 12║ 13| 14| 15| 16| 17| 18| 19| 20║ 21| 22║
╟────┼────┼────┼────┼────╟────┼────╔════╗────┼────┼────┼────┼────╢────┼────╢
105 ║ -7| -6| -5| -4| -3║ -2| -1║ 0║ 1| 2| 3| 4| 5║ 6| 7║
╟────┼────┼────┼────┼────╟────┼────╚════╝────┼────┼────┼────┼────╢────┼────╢
90 ║ -22| -21| -20| -19| -18║ -17| -16| -15| -14| -13| -12| -11| -10║ -9| -8║
╟────┼────┼────┼────┼────╚════╧════╧════╧════╧════╧════╧════╧════╝────┼────╢
75 ║ -37| -36| -35| -34| -33| -32| -31| -30| -29| -28| -27| -26| -25| -24| -23║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
60 ║ -52| -51| -50| -49| -48| -47| -46| -45| -44| -43| -42| -41| -40| -39| -38║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
45 ║ -67| -66| -65| -64| -63| -62| -61| -60| -59| -58| -57| -56| -55| -54| -53║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
30 ║ -82| -81| -80| -79| -78| -77| -76| -75| -74| -73| -72| -71| -70| -66| -68║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
15 ║ -97| -96| -95| -94| -93| -92| -91| -90| -89| -88| -87| -86| -85| -84| -83║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
0 ║-112|-111|-110|-109|-108|-107|-106|-105|-104|-103|-102|-101|-100| -99| -98║
╚════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
</pre>
=<span id="RayVectors"></span>Ray Vectors=
[[Rays|Ray]] vectors are [https://en.wikipedia.org/wiki/Unit_vector unit vectors] to [https://en.wikipedia.org/wiki/Moore_neighborhood eight neighboring] squares, [https://en.wikipedia.org/wiki/Scalar_multiplication scaled] by [[Distance#15x15|Chebyshev distance]]. In the domain of [[Sliding Pieces|sliding piece]] attacks, unit vectors act as [[#IncrementVectors|increment vectors]] if none zero, to determine squares in-between are empty, and a [[Target Square|target square]] is attacked by a sliding piece on its [[Origin Square|origin]]. Following table demonstrates the [[Queen|queen]] unit or increment vectors, superimposed on the 15x15 array in such a way that the queen square (here c2) coincides with the central square of the 15x15 array.
<pre>
char rayUnitVectorQueen[15*15];
╔════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╤════╗
210 ║ 14| | | | | | | 15| | | | | | | 16║
╟────┼────┼────┼────┼────╔════╤════╤════╤════╤════╤════╤════╤════╗────┼────╢
195 ║ | 14| | | ║ | | 15| | | | | ║ 16| ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
180 ║ | | 14| | ║ | | 15| | | | | 16║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
165 ║ | | | 14| ║ | | 15| | | | 16| ║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
150 ║ | | | | 14║ | | 15| | | 16| | ║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
135 ║ | | | | ║ 14| | 15| | 16| | | ║ | ║
╟────┼────┼────┼────┼────╟────┼────┼────┼────┼────┼────┼────┼────╢────┼────╢
120 ║ | | | | ║ | 14| 15| 16| | | | ║ | ║
╟────┼────┼────┼────┼────╟────┼────╔════╗────┼────┼────┼────┼────╢────┼────╢
105 ║ -1| -1| -1| -1| -1║ -1| -1║ Q ║ 1| 1| 1| 1| 1║ 1| 1║
╟────┼────┼────┼────┼────╟────┼────╚════╝────┼────┼────┼────┼────╢────┼────╢
90 ║ | | | | ║ | -16| -15| -14| | | | ║ | ║
╟────┼────┼────┼────┼────╚════╧════╧════╧════╧════╧════╧════╧════╝────┼────╢
75 ║ | | | | | -16| | -15| | -14| | | | | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
60 ║ | | | | -16| | | -15| | | -14| | | | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
45 ║ | | | -16| | | | -15| | | | -14| | | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
30 ║ | | -16| | | | | -15| | | | | -14| | ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
15 ║ | -16| | | | | | -15| | | | | | -14| ║
╟────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────┼────╢
0 ║ -16| | | | | | | -15| | | | | | | -14║
╚════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╧════╝
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
</pre>
=<span id="IncrementVectors"></span>Increment Vectors=
During offset [[Move Generation|move generation]], each piece applies a specific displacement or '''increment vector''' (offset) for each move direction, added to the position vector of the [[Origin Square|origin square]] to determine the next potential [[Target Square|move target]] in that direction, [[Sliding Pieces|sliding pieces]] continuing in the same direction as long the targets are empty. Due to the additional padded files and possibly ranks, off the board test are as simple as the [[10x12 Board|10x12 board]] with surrounding files and ranks containing off the board codes as [https://en.wikipedia.org/wiki/Sentinel_value sentinel values]. The [[0x88]] approach, a special 16x8 implementation of Vector Attacks, already indicates outside squares by its upper [[Nibble|nibble]] bits masked by 0x88.
One may argue, the 0x88 test is cheaper for off the board tests, because it does not need to lookup if the 0x88 test is true. On the other hand, for most cases, if false, it needs a lookup anyway, to perform a second test whether the square is empty, or occupied by an own or opponent piece <ref>[http://www.stmintz.com/ccc/index.php?id=114377 Re: Question:1.hashtable 2.board 3.C] by [[Christophe Théron]], [[CCC]], June 13, 2000</ref> <ref>[http://www.stmintz.com/ccc/index.php?id=114438 0x88 is not so smart] by [[Christophe Théron]], [[CCC]], June 13, 2000</ref>.
=<span id="NewArchitecture"></span>New Architecture=
Vector Attacks based on a 15x12 board were topic of [[Fritz Reul|Fritz Reul's]] Ph.D. thesis ''New Architectures in Computer Chess'', code samples given from Reul's [[Loop (Program)#32bit|Loop Leiden]] engine <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''</ref>.
==Source-Destination==
In conjunction with [[Pieces#DisjointPieceFlags|disjoint piece flags]] and [[Piece-Lists|piece-lists]], Vector Attacks allow efficient [[Move Generation|move generation]] of [[Sliding Pieces|sliding pieces]], even for [[Quiescence Search|quiescence search]] with a leading blocker loop:
<pre>
increment = rayVector[direction];
for (tosq = fromsq + increment; board[tosq] == EMPTY; tosq += increment);
if ( isOpponentPiece (board[tosq]) )
{
/* generate capture */
}
</pre>
==Destination-Source==
A destination-source blocker loop, to test whether a sliding piece on a from square attacks a target square, uses the reversed ray direction in order to dispense with additional conditions:
<pre>
increment = rayUnitVectorQueen[15*15/2 + fromsq - tosq];
if ( increment ) {
for (sq = tosq + increment; board[sq] == EMPTY; sq += increment);
if ( sq == fromsq ) {
/* a queen on fromsq attacks tosq */
}
}
</pre>
=Implementations=
==0x88==
''see main article [[0x88]]''
The [[0x88]] or 16x8 board uses [[Nibble|nibbles]] for both rank and file coordinates inside a [[Byte|byte]], and utilizes the redundant upper bit to indicate invalid squares outside the board, usually then not used as index.
===Layout===
<pre>
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
--------XXXXXXXX
</pre>
===Coordinate Transformation===
16x8 square coordinate 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 square index needs to add the three upper rank bits:
<pre>
sq0x88 = sq + (sq & ~7);
</pre>
==15x12==
The odd number of files makes the [[Color of a Square|square color]] only dependent from the least significant index bit. Usually the seven surrounding border files are divided 4:3 (Offset 34) or 3:4 (Offset 33). One may also use 15x15 for a symmetric treatment of files and ranks as proposed by [[Fritz Reul]] <ref>[[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''</ref> .
===Layout===
<pre>
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXX--------XXX
XXXXXXXXXXXXXXX
XXXXXXXXXXXXXXX
</pre>
===Coordinate Transformation===
Coordinate transformation is usually not needed while generating moves, since [[Piece-Lists|piece-lists]], increments and move coordinates are only based on 15x12 coordinates. Anyway, for the sake of completeness valid 15x12 square transformation to file and rank indices and vice versa might be done quite efficiently without any [[x86]] div and mul instructions, but load effective address (lea) - otherwise simple lookup tables may used to convert coordinates:
<pre>
sq15x12 = 15 * rank07 + file07 + 34;
rank07 = ((sq15x12 - 34) * 9) >> 7; // div by reciprocal mul
file07 = sq15x12 - 34 - 15 * rank07; // % 15
</pre>
==16x12==
Usually the eight surrounding border files are divided 4:4, so the offset of the upper left square is 36. For a symmetric treatment of files and ranks, 16x16 is also quite common <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> .
===Layout===
<pre>
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXX--------XXXX
XXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXX
</pre>
===Coordinate Transformation===
16x12 square coordinate by file and rank and vice versa:
<pre>
sq16x12 = 16 * rank07 + file07 + 36;
rank07 = (sq16x12 - 36) >> 4; // div 16
file07 = (sq16x12 - 36) & 7; // % 8
</pre>
16x12 square index by a 0..63 square index needs to add the three upper rank bits plus offset:
<pre>
sq16x12 = sq8x8 + (sq8x8 & ~7) + 36;
</pre>
Convert 16x12 square index to 0..63 square index:
<pre>
file8x8 = (sq16x12 & 0xf) - 4
rank8x8 = ((sq16x12 >> 4) - 2
sq8x8 = (((sq16x12 >> 4) - 2) << 3) + (sq16x12 & 0xf) - 4;
</pre>
==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>[http://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=
* [[0x88]]
* [[Square Attacked By#By0x88Difference|0x88 meets Bitboards]]
* [[10x12 Board]]
* [[8x8 Board]]
* [[Distance]]
* [[Direction]]
* [[Intersection Squares]] as application of 0x88 coordinates
* [[Sliding Piece Attacks]] with [[Bitboards]]
=Publications=
* [[Mikhail Botvinnik]] ('''1968'''). ''Algoritm igry v shakhmaty''. (The algorithm of chess)
* [[Mikhail Botvinnik]] ('''1970'''). ''Computers, Chess and Long-Range Planning''. Springer
* [[Paul Wiereyn]] ('''1985'''). ''Inventive Problem Solving''. [[ICGA Journal#8_4|ICCA Journal, Vol. 8, No. 4]]
* [[Boris Stilman]] ('''1994'''). ''A Linguistic Geometry of the Chess Model''. [[Advances in Computer Chess 7]], [http://www.stilman-strategies.com/bstilman/boris_papers/Jour94_CHESS7.pdf pdf draft]
* [[Fritz Reul]] ('''2009'''). ''New Architectures in Computer Chess''. Ph.D. Thesis, ''Chapter 2 Non-Bitboard Architectures''
=Forum Posts=
* [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]], [[CCC]], June 13, 2000 » [[0x88]]
* [https://www.stmintz.com/ccc/index.php?id=178465 Fastest Conversion from 0x88 board to 8x8 board representation] by [[Artem Pyatakov]], July 06, 2001
* [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 » [[Fruit]]
* [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
=External Links=
* [https://en.wikipedia.org/wiki/Vector_%28mathematics_and_physics%29 Vector (mathematics and physics) from Wikipedia]
* [https://en.wikipedia.org/wiki/Euclidean_vector Euclidean vector from Wikipedia]
* [https://en.wikipedia.org/wiki/Position_%28vector%29 Position (vector) from Wikipedia]
* [https://en.wikipedia.org/wiki/Displacement_%28vector%29 Displacement (vector) from Wikipedia]
* [https://en.wikipedia.org/wiki/Linear_algebra Linear algebra from Wikipedia]
* [https://en.wikipedia.org/wiki/Vector_space Vector space from Wikipedia]
=References=
<references />
'''[[Mailbox|Up one Level]]'''
