⭐ 欢迎来到虫虫下载站！ | 📦 资源下载 📁 资源专辑 ℹ️ 关于我们
⭐ 虫虫下载站
📤 上传资源

📄 rotated bitboards.htm

📁 介绍各种经典算法的代码。说明详细
💻 HTM
字号:
🔍 
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0053)http://wwwipd.ira.uka.de/Tichy/DarkThought/node8.html -->
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds* revised and updated by:  Marcus Hennecke, Ross Moore, Herb Swan* with significant contributions from:  Jens Lippmann, Marek Rouchal, Martin Wilck and others --><HTML><HEAD><TITLE>Rotated Bitboards</TITLE>
<META content="Rotated Bitboards" name=description>
<META content=dt name=keywords>
<META content=document name=resource-type>
<META content=global name=distribution>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type><LINK 
href="Rotated Bitboards.files/dt.css" rel=STYLESHEET>
<META content="MSHTML 5.00.2014.210" name=GENERATOR></HEAD>
<BODY>
<H3><A name=SECTION00124200000000000000>&nbsp;</A> <A name=bboard-rot>&nbsp;</A> 
<BR>Rotated Bitboards </H3>
<P>Vectors of attack masks for all pieces on each square of an otherwise empty 
chess board enable an easy attack detection for sliding pieces without having to 
loop over the squares of the respective diagonals, files, and ranks&nbsp;[<A 
href="http://wwwipd.ira.uka.de/Tichy/DarkThought/node95.html#bbrd:attack-det">207</A>]. 
This loop-less attack-detection scheme operates on consecutive strings of bits 
representing the rays of squares potentially covered by the sliding piece. In 
order to really excel, it therefore requires efficient access to consecutive 
strings of ray bits. As listed below, the normal row-major mapping of squares to 
bits in a bitboard consecutively aligns the bits of each file. Hence, it only 
provides efficient access to consecutive strings of file bits. 
<P><B>Normal Bitboard. </B>
<TABLE border=1 cellPadding=3>
  <TBODY>
  <TR>
    <TD align=right><B>#7</B></TD>
    <TD align=right><B>#6</B></TD>
    <TD align=right><B>#5</B></TD>
    <TD align=right><B>#4</B></TD>
    <TD align=right><B>#3</B></TD>
    <TD align=right><B>#2</B></TD>
    <TD align=right><B>#1</B></TD>
    <TD align=right><B>#0</B></TD>
    <TD align=right><B>Bit/Byte</B></TD></TR>
  <TR>
    <TD align=right>a8</TD>
    <TD align=right>b8</TD>
    <TD align=right>c8</TD>
    <TD align=right>d8</TD>
    <TD align=right>e8</TD>
    <TD align=right>f8</TD>
    <TD align=right>g8</TD>
    <TD align=right>h8</TD>
    <TD align=right><B>#7</B></TD></TR>
  <TR>
    <TD align=right>a7</TD>
    <TD align=right>b7</TD>
    <TD align=right>c7</TD>
    <TD align=right>d7</TD>
    <TD align=right>e7</TD>
    <TD align=right>f7</TD>
    <TD align=right>g7</TD>
    <TD align=right>h7</TD>
    <TD align=right><B>#6</B></TD></TR>
  <TR>
    <TD align=right>a6</TD>
    <TD align=right>b6</TD>
    <TD align=right>c6</TD>
    <TD align=right>d6</TD>
    <TD align=right>e6</TD>
    <TD align=right>f6</TD>
    <TD align=right>g6</TD>
    <TD align=right>h6</TD>
    <TD align=right><B>#5</B></TD></TR>
  <TR>
    <TD align=right>a5</TD>
    <TD align=right>b5</TD>
    <TD align=right>c5</TD>
    <TD align=right>d5</TD>
    <TD align=right>e5</TD>
    <TD align=right>f5</TD>
    <TD align=right>g5</TD>
    <TD align=right>h5</TD>
    <TD align=right><B>#4</B></TD></TR>
  <TR>
    <TD align=right>a4</TD>
    <TD align=right>b4</TD>
    <TD align=right>c4</TD>
    <TD align=right>d4</TD>
    <TD align=right>e4</TD>
    <TD align=right>f4</TD>
    <TD align=right>g4</TD>
    <TD align=right>h4</TD>
    <TD align=right><B>#3</B></TD></TR>
  <TR>
    <TD align=right>a3</TD>
    <TD align=right>b3</TD>
    <TD align=right>c3</TD>
    <TD align=right>d3</TD>
    <TD align=right>e3</TD>
    <TD align=right>f3</TD>
    <TD align=right>g3</TD>
    <TD align=right>h3</TD>
    <TD align=right><B>#2</B></TD></TR>
  <TR>
    <TD align=right>a2</TD>
    <TD align=right>b2</TD>
    <TD align=right>c2</TD>
    <TD align=right>d2</TD>
    <TD align=right>e2</TD>
    <TD align=right>f2</TD>
    <TD align=right>g2</TD>
    <TD align=right>h2</TD>
    <TD align=right><B>#1</B></TD></TR>
  <TR>
    <TD align=right>a1</TD>
    <TD align=right>b1</TD>
    <TD align=right>c1</TD>
    <TD align=right>d1</TD>
    <TD align=right>e1</TD>
    <TD align=right>f1</TD>
    <TD align=right>g1</TD>
    <TD align=right>h1</TD>
    <TD align=right><B>#0</B></TD></TR></TBODY></TABLE>
<P>A column-major mapping of squares to bits in a bitboard, however, 
consecutively aligns the bits of each rank. Consequently, such flipped bitboards 
allow for efficient access to consecutive strings of rank bits. 
<P><B>Flipped Bitboard. </B>
<TABLE border=1 cellPadding=3>
  <TBODY>
  <TR>
    <TD align=right><B>#7</B></TD>
    <TD align=right><B>#6</B></TD>
    <TD align=right><B>#5</B></TD>
    <TD align=right><B>#4</B></TD>
    <TD align=right><B>#3</B></TD>
    <TD align=right><B>#2</B></TD>
    <TD align=right><B>#1</B></TD>
    <TD align=right><B>#0</B></TD>
    <TD align=right><B>Bit/Byte</B></TD></TR>
  <TR>
    <TD align=right>a8</TD>
    <TD align=right>a7</TD>
    <TD align=right>a6</TD>
    <TD align=right>a5</TD>
    <TD align=right>a4</TD>
    <TD align=right>a3</TD>
    <TD align=right>a2</TD>
    <TD align=right>a1</TD>
    <TD align=right><B>#7</B></TD></TR>
  <TR>
    <TD align=right>b8</TD>
    <TD align=right>b7</TD>
    <TD align=right>b6</TD>
    <TD align=right>b5</TD>
    <TD align=right>b4</TD>
    <TD align=right>b3</TD>
    <TD align=right>b2</TD>
    <TD align=right>b1</TD>
    <TD align=right><B>#6</B></TD></TR>
  <TR>
    <TD align=right>c8</TD>
    <TD align=right>c7</TD>
    <TD align=right>c6</TD>
    <TD align=right>c5</TD>
    <TD align=right>c4</TD>
    <TD align=right>c3</TD>
    <TD align=right>c2</TD>
    <TD align=right>c1</TD>
    <TD align=right><B>#5</B></TD></TR>
  <TR>
    <TD align=right>d8</TD>
    <TD align=right>d7</TD>
    <TD align=right>d6</TD>
    <TD align=right>d5</TD>
    <TD align=right>d4</TD>
    <TD align=right>d3</TD>
    <TD align=right>d2</TD>
    <TD align=right>d1</TD>
    <TD align=right><B>#4</B></TD></TR>
  <TR>
    <TD align=right>e8</TD>
    <TD align=right>e7</TD>
    <TD align=right>e6</TD>
    <TD align=right>e5</TD>
    <TD align=right>e4</TD>
    <TD align=right>e3</TD>
    <TD align=right>e2</TD>
    <TD align=right>e1</TD>
    <TD align=right><B>#3</B></TD></TR>
  <TR>
    <TD align=right>f8</TD>
    <TD align=right>f7</TD>
    <TD align=right>f6</TD>
    <TD align=right>f5</TD>
    <TD align=right>f4</TD>
    <TD align=right>f3</TD>
    <TD align=right>f2</TD>
    <TD align=right>f1</TD>
    <TD align=right><B>#2</B></TD></TR>
  <TR>
    <TD align=right>g8</TD>
    <TD align=right>g7</TD>
    <TD align=right>g6</TD>
    <TD align=right>g5</TD>
    <TD align=right>g4</TD>
    <TD align=right>g3</TD>
    <TD align=right>g2</TD>
    <TD align=right>g1</TD>
    <TD align=right><B>#1</B></TD></TR>
  <TR>
    <TD align=right>h8</TD>
    <TD align=right>h7</TD>
    <TD align=right>h6</TD>
    <TD align=right>h5</TD>
    <TD align=right>h4</TD>
    <TD align=right>h3</TD>
    <TD align=right>h2</TD>
    <TD align=right>h1</TD>
    <TD align=right><B>#0</B></TD></TR></TBODY></TABLE>
<P>In the case of diagonals, the necessary mappings prove to be more complex. 
The number of diagonals amounts to 15 in each of the two directions a1-h8 and 
a8-h1. Furthermore, diagonals are of variable lengths ranging from 1 to 8. 
Because not all diagonals can be stuffed into separate bytes of a bitboard the 
mapping must pack some together in a clever way. 
<P>Figuratively, viable mappings can be deduced as follows: slice a normal 
bitboard along one of the main diagonals (a1-h8 or a8-h1), then rotate the half 
with the squares of the main diagonal to lie at the bottom, and finally paste 
the other half such that it results in a parallelogram. As shown below, the 
diagonalized mappings of squares to bits in a bitboard consecutively align the 
bits of each a1-h8 and a8-h1 diagonal. Thus, diagonalized bitboards enable 
efficient access to consecutive strings of diagonal bits if the ends of the 
diagonals (as marked by vertical bars) are known. 
<P><B>A1-H8 Bitboard. </B>
<TABLE border=1 cellPadding=3>
  <TBODY>
  <TR>
    <TD align=right><B>#7</B></TD>
    <TD align=right><B>#6</B></TD>
    <TD align=right><B>#5</B></TD>
    <TD align=right><B>#4</B></TD>
    <TD align=right><B>#3</B></TD>
    <TD align=right><B>#2</B></TD>
    <TD align=right><B>#1</B></TD>
    <TD align=right><B>#0</B></TD>
    <TD align=right><B>Bit/Byte</B></TD></TR>
  <TR>
    <TD align=right>a8</TD>
    <TD align=right>| b1</TD>
    <TD align=right>c2</TD>
    <TD align=right>d3</TD>
    <TD align=right>e4</TD>
    <TD align=right>f5</TD>
    <TD align=right>g6</TD>
    <TD align=right>h7</TD>
    <TD align=right><B>#7</B></TD></TR>
  <TR>
    <TD align=right>a7</TD>
    <TD align=right>b8</TD>
    <TD align=right>| c1</TD>
    <TD align=right>d2</TD>
    <TD align=right>e3</TD>
    <TD align=right>f4</TD>
    <TD align=right>g5</TD>
    <TD align=right>h6</TD>
    <TD align=right><B>#6</B></TD></TR>
  <TR>
    <TD align=right>a6</TD>
    <TD align=right>b7</TD>
    <TD align=right>c8</TD>
    <TD align=right>| d1</TD>
    <TD align=right>e2</TD>
    <TD align=right>f3</TD>
    <TD align=right>g4</TD>
    <TD align=right>h5</TD>
    <TD align=right><B>#5</B></TD></TR>
  <TR>
    <TD align=right>a5</TD>
    <TD align=right>b6</TD>
    <TD align=right>c7</TD>
    <TD align=right>d8</TD>
    <TD align=right>| e1</TD>
    <TD align=right>f2</TD>
    <TD align=right>g3</TD>
    <TD align=right>h4</TD>
    <TD align=right><B>#4</B></TD></TR>
  <TR>
    <TD align=right>a4</TD>
    <TD align=right>b5</TD>
    <TD align=right>c6</TD>
    <TD align=right>d7</TD>
    <TD align=right>e8</TD>
    <TD align=right>| f1</TD>
    <TD align=right>g2</TD>
    <TD align=right>h3</TD>
    <TD align=right><B>#3</B></TD></TR>
  <TR>
    <TD align=right>a3</TD>
    <TD align=right>b4</TD>
    <TD align=right>c5</TD>
    <TD align=right>d6</TD>
    <TD align=right>e7</TD>
    <TD align=right>f8</TD>
    <TD align=right>| g1</TD>
    <TD align=right>h2</TD>
    <TD align=right><B>#2</B></TD></TR>
  <TR>
    <TD align=right>a2</TD>
    <TD align=right>b3</TD>
    <TD align=right>c4</TD>
    <TD align=right>d5</TD>
    <TD align=right>e6</TD>
    <TD align=right>f7</TD>
    <TD align=right>g8</TD>
    <TD align=right>| h1</TD>
    <TD align=right><B>#1</B></TD></TR>
  <TR>
    <TD align=right>a1</TD>
    <TD align=right>b2</TD>
    <TD align=right>c3</TD>
    <TD align=right>d4</TD>
    <TD align=right>e5</TD>
    <TD align=right>f6</TD>
    <TD align=right>g7</TD>
    <TD align=right>h8</TD>
    <TD align=right><B>#0</B></TD></TR></TBODY></TABLE>
<P>
<P>
<P><BR><B>A8-H1 Bitboard. </B>
<TABLE border=1 cellPadding=3>
  <TBODY>
  <TR>
    <TD align=right><B>#7</B></TD>
    <TD align=right><B>#6</B></TD>
    <TD align=right><B>#5</B></TD>
    <TD align=right><B>#4</B></TD>
    <TD align=right><B>#3</B></TD>
    <TD align=right><B>#2</B></TD>
    <TD align=right><B>#1</B></TD>
    <TD align=right><B>#0</B></TD>
    <TD align=right><B>Bit/Byte</B></TD></TR>
  <TR>
    <TD align=right>a8</TD>
    <TD align=right>b7</TD>
    <TD align=right>c6</TD>
    <TD align=right>d5</TD>
    <TD align=right>e4</TD>
    <TD align=right>f3</TD>
    <TD align=right>g2</TD>
    <TD align=right>h1</TD>
    <TD align=right><B>#7</B></TD></TR>
  <TR>
    <TD align=right>a7</TD>
    <TD align=right>b6</TD>
    <TD align=right>c5</TD>
    <TD align=right>d4</TD>
    <TD align=right>e3</TD>
    <TD align=right>f2</TD>
    <TD align=right>g1</TD>
    <TD align=right>| h8</TD>
    <TD align=right><B>#6</B></TD></TR>
  <TR>
    <TD align=right>a6</TD>
    <TD align=right>b5</TD>
    <TD align=right>c4</TD>
    <TD align=right>d3</TD>
    <TD align=right>e2</TD>
    <TD align=right>f1</TD>
    <TD align=right>| g8</TD>
    <TD align=right>h7</TD>
    <TD align=right><B>#5</B></TD></TR>
  <TR>
    <TD align=right>a5</TD>
    <TD align=right>b4</TD>
    <TD align=right>c3</TD>
    <TD align=right>d2</TD>
    <TD align=right>e1</TD>
    <TD align=right>| f8</TD>
    <TD align=right>g7</TD>
    <TD align=right>h6</TD>
    <TD align=right><B>#4</B></TD></TR>
  <TR>
    <TD align=right>a4</TD>
    <TD align=right>b3</TD>
    <TD align=right>c2</TD>
    <TD align=right>d1</TD>
    <TD align=right>| e8</TD>
    <TD align=right>f7</TD>
    <TD align=right>g6</TD>
    <TD align=right>h5</TD>
    <TD align=right><B>#3</B></TD></TR>
  <TR>
    <TD align=right>a3</TD>
    <TD align=right>b2</TD>
    <TD align=right>c1</TD>
    <TD align=right>| d8</TD>
    <TD align=right>e7</TD>
    <TD align=right>f6</TD>
    <TD align=right>g5</TD>
    <TD align=right>h4</TD>
    <TD align=right><B>#2</B></TD></TR>
  <TR>
    <TD align=right>a2</TD>
    <TD align=right>b1</TD>
    <TD align=right>| c8</TD>
    <TD align=right>d7</TD>
    <TD align=right>e6</TD>
    <TD align=right>f5</TD>
    <TD align=right>g4</TD>
    <TD align=right>h3</TD>
    <TD align=right><B>#1</B></TD></TR>
  <TR>
    <TD align=right>a1</TD>
    <TD align=right>| b8</TD>
    <TD align=right>c7</TD>
    <TD align=right>d6</TD>
    <TD align=right>e5</TD>
    <TD align=right>f4</TD>
    <TD align=right>g3</TD>
    <TD align=right>h2</TD>
    <TD align=right><B>#0</B></TD></TR></TBODY></TABLE>
<P>For historical reasons, diagonalized and flipped bitboards are both called 
rotated. In order to fully exploit the benefits of rotation, 
D<SMALL>ARK</SMALL>T<SMALL>HOUGHT</SMALL> incrementally updates rotated 
bitboards with 1-bits for all occupied squares of the current position. 
Additionally, it manages compressed vectors of rotated attack masks that strike 
a good balance between instruction and memory efficiency. 
<P><BR>
<HR>

<ADDRESS>Created by <A href="mailto:heinze@ira.uka.de">Ernst A. Heinz</A>, Thu 
Feb 4 14:12:12 MET 1999 </ADDRESS></BODY></HTML>

⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -