📄 rotated.htm
字号:
<TD>
<CENTER>x</CENTER></TD>
<TD>
<CENTER>x</CENTER></TD>
<TD>
<CENTER>x</CENTER></TD>
<TD>
<CENTER>x</CENTER></TD>
<TD>
<CENTER>x</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>6</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER>x</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>7</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER>x</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>8</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER>x</CENTER></TD></TR></TBODY></TABLE></CENTER>
<P>The key to this whole operation is precomputation. For each of the 64
squares, precompute the 256 possible rank attack boards and file attack boards.
During the search, the state of the rank (or file) is used as the index into
these precomputed arrays. </P>
<P>So, <B>step 1.</B> - Precomputing rank_attacks[64][256] and
file_attacks[64][256]. </P><TT>/* precompute horizontal rook/queen moves
*/<BR><BR>for every square (0-63) <BR>{<BR><IMG height=3
src="Rotated.files/spacer.gif" width=15> for every rank state (0-255)<BR><IMG
height=3 src="Rotated.files/spacer.gif" width=15> {<BR><IMG height=3
src="Rotated.files/spacer.gif" width=30> compute occupied squares for rank
state<BR><IMG height=3 src="Rotated.files/spacer.gif" width=30> compute moves
from square for this rank state to the left<BR><IMG height=3
src="Rotated.files/spacer.gif" width=30> compute moves from square for this rank
state to the right<BR><IMG height=3 src="Rotated.files/spacer.gif" width=30>
rank_attacks[square][rank state] = attack_board;<BR><IMG height=3
src="Rotated.files/spacer.gif" width=15> }<BR>}<BR><BR>/* precompute vertical
rook/queen moves */<BR><BR>for every square (0-63) <BR>{<BR><IMG height=3
src="Rotated.files/spacer.gif" width=15> for every file state (0-255) <BR><IMG
height=3 src="Rotated.files/spacer.gif" width=15> {<BR><IMG height=3
src="Rotated.files/spacer.gif" width=30> compute occupied squares for file
state<BR><IMG height=3 src="Rotated.files/spacer.gif" width=30> compute all
moves from square for this file state going up<BR><IMG height=3
src="Rotated.files/spacer.gif" width=30> compute all moves from square for this
file state going down<BR><IMG height=3 src="Rotated.files/spacer.gif" width=30>
file_attacks[square][file state] = attack_board;<BR><IMG height=3
src="Rotated.files/spacer.gif" width=15> }<BR>}<BR></TT>
<P><B>Step 2.</B> - indexing "rank_attacks[64][256]." </P>
<P>The first index is simply the square the rook sits on. The second is the
"state of the rank" the rook sits on. </P>
<P>Here's an example:</P>
<CENTER>
<TABLE border=1 cellPadding=0 cellSpacing=0 cols=9 width="25%">
<CAPTION><B>Rook Attack Board From E6</B></CAPTION>
<TBODY>
<TR>
<TD></TD>
<TD>
<CENTER><B>H</B></CENTER></TD>
<TD>
<CENTER><B>G</B></CENTER></TD>
<TD>
<CENTER><B>F</B></CENTER></TD>
<TD>
<CENTER><B>E</B></CENTER></TD>
<TD>
<CENTER><B>D</B></CENTER></TD>
<TD>
<CENTER><B>C</B></CENTER></TD>
<TD>
<CENTER><B>B</B></CENTER></TD>
<TD>
<CENTER><B>A</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>1</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER><B>K</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>2</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>3</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>4</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>5</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>6</B></CENTER></TD>
<TD></TD>
<TD>
<CENTER><B>P</B></CENTER></TD>
<TD></TD>
<TD>
<CENTER><B>r</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER><B>b</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>7</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>8</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER><B>k</B></CENTER></TD></TR></TBODY></TABLE></CENTER><BR>
<P>The first index is the square "E6." In my program, Square::E6 = 20. The
second index is the state of the sixth rank. </P>
<H3><B>01010010</B></H3><BR>
<P>To extract this number, we need to perform a shift and a logical AND
operation. In my program, the A8 square = 0. Anything in the eighth rank doesn't
need to be shifted. The seventh rank needs to be shifted eight bits to the
right. The sixth rank needs to be shifted 16 bits to the rights, and so on. </P>
<CENTER>
<TABLE border=1 cellPadding=0 cellSpacing=0 cols=9 width="25%">
<CAPTION><B>Number of Bits to Shift</B></CAPTION>
<TBODY>
<TR>
<TD></TD>
<TD>
<CENTER><B>H</B></CENTER></TD>
<TD>
<CENTER><B>G</B></CENTER></TD>
<TD>
<CENTER><B>F</B></CENTER></TD>
<TD>
<CENTER><B>E</B></CENTER></TD>
<TD>
<CENTER><B>D</B></CENTER></TD>
<TD>
<CENTER><B>C</B></CENTER></TD>
<TD>
<CENTER><B>B</B></CENTER></TD>
<TD>
<CENTER><B>A</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>1</B></CENTER></TD>
<TD>
<CENTER>56</CENTER></TD>
<TD>
<CENTER>56</CENTER></TD>
<TD>
<CENTER>56</CENTER></TD>
<TD>
<CENTER>56</CENTER></TD>
<TD>
<CENTER>56</CENTER></TD>
<TD>
<CENTER>56</CENTER></TD>
<TD>
<CENTER>56</CENTER></TD>
<TD>
<CENTER>56</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>2</B></CENTER></TD>
<TD>
<CENTER>48</CENTER></TD>
<TD>
<CENTER>48</CENTER></TD>
<TD>
<CENTER>48</CENTER></TD>
<TD>
<CENTER>48</CENTER></TD>
<TD>
<CENTER>48</CENTER></TD>
<TD>
<CENTER>48</CENTER></TD>
<TD>
<CENTER>48</CENTER></TD>
<TD>
<CENTER>48</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>3</B></CENTER></TD>
<TD>
<CENTER>40</CENTER></TD>
<TD>
<CENTER>40</CENTER></TD>
<TD>
<CENTER>40</CENTER></TD>
<TD>
<CENTER>40</CENTER></TD>
<TD>
<CENTER>40</CENTER></TD>
<TD>
<CENTER>40</CENTER></TD>
<TD>
<CENTER>40</CENTER></TD>
<TD>
<CENTER>40</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>4</B></CENTER></TD>
<TD>
<CENTER>32</CENTER></TD>
<TD>
<CENTER>32</CENTER></TD>
<TD>
<CENTER>32</CENTER></TD>
<TD>
<CENTER>32</CENTER></TD>
<TD>
<CENTER>32</CENTER></TD>
<TD>
<CENTER>32</CENTER></TD>
<TD>
<CENTER>32</CENTER></TD>
<TD>
<CENTER>32</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>5</B></CENTER></TD>
<TD>
<CENTER>24</CENTER></TD>
<TD>
<CENTER>24</CENTER></TD>
<TD>
<CENTER>24</CENTER></TD>
<TD>
<CENTER>24</CENTER></TD>
<TD>
<CENTER>24</CENTER></TD>
<TD>
<CENTER>24</CENTER></TD>
<TD>
<CENTER>24</CENTER></TD>
<TD>
<CENTER>24</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>6</B></CENTER></TD>
<TD>
<CENTER>16</CENTER></TD>
<TD>
<CENTER>16</CENTER></TD>
<TD>
<CENTER>16</CENTER></TD>
<TD>
<CENTER>16</CENTER></TD>
<TD>
<CENTER>16</CENTER></TD>
<TD>
<CENTER>16</CENTER></TD>
<TD>
<CENTER>16</CENTER></TD>
<TD>
<CENTER>16</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>7</B></CENTER></TD>
<TD>
<CENTER>8</CENTER></TD>
<TD>
<CENTER>8</CENTER></TD>
<TD>
<CENTER>8</CENTER></TD>
<TD>
<CENTER>8</CENTER></TD>
<TD>
<CENTER>8</CENTER></TD>
<TD>
<CENTER>8</CENTER></TD>
<TD>
<CENTER>8</CENTER></TD>
<TD>
<CENTER>8</CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>8</B></CENTER></TD>
<TD>
<CENTER>0</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD>
<TD>
<CENTER>0</CENTER></TD></TR></TBODY></TABLE></CENTER><BR>
<P>Now that the eight bits we are interested in are the least significant bits,
we can just peform a logical AND with 255 (0xff) to isolate them. The resulting
number is the second index into the rank_attacks array. </P>
<P><B>Step 3.</B> - indexing "file_attacks[64][256]." </P>
<P>Now comes the problem of obtaining the file_attacks bitboard. Once again, the
first index is simply the square the rook is sitting on. The second index is the
"state of the file" the rook sits on. </P>
<H3>
<CENTER><B>1<BR>0<BR>0<BR>0<BR>0<BR>1<BR>0<BR>1<BR></B></CENTER></H3>
<P>Extracting this index is a bit more complicated than with the rank_attacks
index. We can't simply perform a shift and an AND. First, we must rotate the
chessboard 90 degrees (right), so that it looks like this: </P>
<CENTER>
<TABLE border=1 cellPadding=0 cellSpacing=0 cols=9 width="25%">
<CAPTION><B>Rook Attack BitBoard Rotated 90 Degrees Right</B></CAPTION>
<TBODY>
<TR>
<TD></TD>
<TD>
<CENTER><B>8</B></CENTER></TD>
<TD>
<CENTER><B>7</B></CENTER></TD>
<TD>
<CENTER><B>6</B></CENTER></TD>
<TD>
<CENTER><B>5</B></CENTER></TD>
<TD>
<CENTER><B>4</B></CENTER></TD>
<TD>
<CENTER><B>3</B></CENTER></TD>
<TD>
<CENTER><B>2</B></CENTER></TD>
<TD>
<CENTER><B>1</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>H</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>G</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER><B>P</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>F</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>E</B></CENTER></TD>
<TD>
<CENTER><B>k</B></CENTER></TD>
<TD></TD>
<TD>
<CENTER><B>r</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER><B>K</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>D</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>C</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>B</B></CENTER></TD>
<TD></TD>
<TD></TD>
<TD>
<CENTER><B>b</B></CENTER></TD></TR>
<TR>
<TD>
<CENTER><B>A</B></CENTER></TD></TR></TBODY></TABLE></CENTER><BR>
<P>Where does this rotated bitboard come from? You can either create it on the
fly, or simply update it incrementally during <TT>make</TT> and <TT>unmake</TT>.
The following method demonstrates how to build it on the fly. (Not so elegant,
but easy to understand...) </P><TT>int r90R_map[64] = {<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> H8,H7,H6,H5,H4,H3,H2,H1,<BR><IMG
height=3 src="Rotated.files/spacer.gif" width=100>
G8,G7,G6,G5,G4,G3,G2,G1,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> F8,F7,F6,F5,F4,F3,F2,F1,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> E8,E7,E6,E5,E4,E3,E2,E1,<BR><IMG
height=3 src="Rotated.files/spacer.gif" width=100>
D8,D7,D6,D5,D4,D3,D2,D1,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> C8,C7,C6,C5,C4,C3,C2,C1,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> B8,B7,B6,B5,B4,B3,B2,B1,<BR><IMG
height=3 src="Rotated.files/spacer.gif" width=100> A8,A7,A6,A5,A4,A3,A2,A1
};<BR><BR>BitBoard Rotated90R = 0;<BR>for every square (0-63) <BR>{<BR><IMG
height=3 src="Rotated.files/spacer.gif" width=15> if square is not empty<BR><IMG
height=3 src="Rotated.files/spacer.gif" width=30> Rotated90R |=
mask[r90R_map[square]];<BR>}<BR></TT>
<P>So whatever is in square A8 in the normal board gets "mapped" to H8, whatever
is in square H8 in the normal board gets "mapped" to H1...</P>
<P>Now, we can perform the shift and AND on this rotated bitboard. </P>
<P><B>Step 4.</B> - Obtaining the rook_attacks bitboard. </P>
<P>Once you have the correct rank_attacks and file_attacks bitboards, simply
perform a logical OR of them to get the bitboard of all squares the rook
attacks. </P><TT>rook_attack = rank_attack |
file_attack;<BR></TT><BR><BR><B><U>Using rotated bitboards to compute bishop
attacks</U></B><BR>
<P>The method for computing a bishop's attack board is similiar to that of a
rook's. Instead of ORing the rank and file together, we OR the two diagonals the
bishop attacks together. We'll call the first diagonal <TT>diag_A8H1</TT>
(upleft-downright, from white's point of view) and the other diagonal
<TT>diag_H8A1</TT>. Additional steps are required since diagonals vary in
length. </P>
<P>Precomputing <TT>diag_A8H1_attacks[64][256]</TT> and
<TT>diag_H8A1_attacks[64][256]</TT>. Square A8 = 0, square H8 = 7, square A1 =
56, square H1 = 63. </P><TT>int length_A8H1_diag[64] = { <BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 8,7,6,5,4,3,2,1,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 7,8,7,6,5,4,3,2,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 6,7,8,7,6,5,4,3,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 5,6,7,8,7,6,5,4,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 4,5,6,7,8,7,6,5,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 3,4,5,6,7,8,7,6,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 2,3,4,5,6,7,8,7,<BR><IMG height=3
src="Rotated.files/spacer.gif" width=100> 1,2,3,4,5,6,7,8 };<BR><BR>int
length_H8A1_diag[64] = { <BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 1,2,3,4,5,6,7,8,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 2,3,4,5,6,7,8,7,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 3,4,5,6,7,8,7,6,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 4,5,6,7,8,7,6,5,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 5,6,7,8,7,6,5,4,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 6,7,8,7,6,5,4,3,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 7,8,7,6,5,4,3,2,<BR><IMG height=3 src="Rotated.files/spacer.gif"
width=100> 8,7,6,5,4,3,2,1 };<BR><BR>/* <BR>precompute A8/H1 diagonal
bishop/queen moves<BR>*/<BR><BR>for every square (0-63) <BR>{<BR><IMG height=3
src="Rotated.files/spacer.gif" width=15> /*<BR><IMG height=3
src="Rotated.files/spacer.gif" width=15> number of diagonal "states" will vary
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -