📄 chess board representations.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0057)http://www.xs4all.nl/~verhelst/chess/representations.html -->
<HTML><HEAD><TITLE>Chess Board Representations</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type><!-- SpHyDir created this page. --><LINK
href="programming.html" rel=UP><LINK href="search.html" rel=NEXT><LINK
href="publications.html" rel=PREVIOUS>
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY><!-- SpHyDir Ignore --><A
href="http://www.aescon.com/innoval/everos2/"><IMG align=left
alt="[Ever Onward OS/2]" height=30
src="Chess Board Representations.files/everos2t.gif" width=143> </A><A
href="http://www.eff.org/blueribbon.html"><IMG align=right
alt="[Free Speech Online]" height=30
src="Chess Board Representations.files/freesp.gif" width=143> </A>
<CENTER>Last modified: 10 Mar 1997 <BR>Accessed: <IMG
src="Chess Board Representations.files/usercounter.htm"> </CENTER>
<HR>
<!-- SpHyDir -->
<H1>Chess Board Representations</H1>
<H2>Arrays</H2>
<P>The most straighforward representation of a chess board is as a 64 elements
long array. Each element represents a square of the chess board that either is
empty or is occupied by a chess piece. There are 12 different chess pieces and
one value is needed to represent an empty square; this fits into 4 bits per
square. For efficiency reasons in most cases one byte per square will be used.
<P>In addition to the position of all pieces, the following information is
needed:
<UL>
<LI>the side to move
<LI>the position of an en passant square if present
<LI>flags indication possibility of short/long castling for both sides
</LI></UL>
<P>Variations on the array theme are to use 10x12 and 16x16 chess boards. The
idea here is to have cheap checks to see if a move crosses a border. In the
10x12 case, the 8x8 board is centered on the 10x12 board and enclosed with
occupied squares. In the 16x16 case, we can encode square numbers as
<CODE>0rrr0ccc</CODE> (binary), where <CODE>rrr</CODE> is the row number and
<CODE>ccc</CODE> the column number (file); crossing a border will turn one of
the <CODE>0</CODE> bits into a <CODE>1</CODE>, which can be detected with an AND
operation.
<H2>Minimal coding</H2>
<P>When using 4 bits per square, an array representation will have a total size
of 256 bits. It is possible to squeeze a chess position in less bits by using
Huffman coding techniques. For example (C is colour of the piece):
<UL>
<LI>Empty square: 0
<LI>Pawn: 10C
<LI>Bishop: 1100C
<LI>Knight: 1101C
<LI>Rook: 1110C
<LI>Queen: 11110C
<LI>King: 11111C </LI></UL>
<P>This gives a total size of 32 + 48 + 20 + 20 + 20 + 12 + 12 = 164 bits. Some
additional bits will be necessary to indicate castle status and side to move.
<P>An alternative for this is to store the sequence of moves from the opening
position. Again by using Huffman coding this can be very compact, although it is
difficult to give an upper bound or average size.
<P>Such representations are not very useful for use in a chess program, but may
be useful e.g. for storing positions in a database.
<H2><A name=bitboards>Bit boards</A></H2>
<P>Bit board representations are based on the observation that a chess board has
64 squares and that there is a trend towards 64 bit computers. One computer word
can then represent a boolean condition for each square of the chess board.
Examples of such conditions are:
<UL>
<LI>Square is occupied by certain piece.
<LI>Square is occupied by white (or black).
<LI>Square is attacked by white (or black). </LI></UL>
<P>The advantage of bit boards is that boolean operations can be performed on
all squares in parallel. The disadvantage is that updating all bit board
information after each move can be costly. This is especially true for attack
information (which sqaures are attacking a square).
<H2><A name=Rotated-bitboard>Rotated bitboards</A></H2>
<P>Normally a bitboard will have one byte per rank of the chess board. This
allows efficient determination of rook attacks across a rank by using a lookup
table indexed by square and rank-occupied-byte (we need the occupied bitboard
because rook attacks stop at the first occupied square in the line of sight).
<P>A simple variation of the normal bitboard is to use a 90 degree rotated
occupied bitboard, where each file of the chess board will be represented by one
byte. In the same way as above, the rook attacks across a file can be
determined.
<P>We can also introduce 45 degrees left and right rotated occupied bitboards,
where a left or right diagonal will be stored in one byte (actually in less than
one byte). Using these bitboards and a table lookup we can determine bishop
attacks. Queen attacks are obtained by or-ing the rook and bishop attacks. <!-- SpHyDir Ignore -->
<HR>
<A href="http://www.xs4all.nl/~verhelst/lynx-enhanced.html"><IMG align=left
alt="[Enhanced for Lynx]" height=45
src="Chess Board Representations.files/lynx-enhanced.gif" width=115> </A><IMG
align=right alt="[HTML 2.0 OK]" height=32
src="Chess Board Representations.files/html-2.0-ok.gif" width=48>
<CENTER>[<A href="http://www.xs4all.nl/">XS4ALL</A>] [<A
href="http://www.xs4all.nl/~verhelst/">Home</A>] [<A
href="http://www.xs4all.nl/~verhelst/stats/today.html">Statistics</A>] [<A
href="http://www.xs4all.nl/~verhelst/chess/programming.html">Up</A>] [<A
href="http://www.xs4all.nl/~verhelst/chess/publications.html">Previous</A>] [<A
href="http://www.xs4all.nl/~verhelst/chess/search.html">Next</A>] <BR>Comments
to: Paul Verhelst (<A href="mailto:verhelst@xs4all.nl">verhelst@xs4all.nl</A>) /
<A
href="http://www.cs.indiana.edu:800/finger/gateway/?verhelst@xs4all.nl">finger
me</A> </CENTER>
<HR>
<P>This document generated by <A
href="http://pclt.cis.yale.edu/pclt/sphydir/sphydir.htm">SpHyDir,</A> another
fine product of <A href="http://pclt.cis.yale.edu/pclt/default.htm">PC Lube and
Tune</A>.</P><!-- SpHyDir --></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -