📄 ics 180, april 8, 1997.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0049)http://www.ics.uci.edu/~eppstein/180a/970408.html -->
<HTML><HEAD><TITLE>ICS 180, April 8, 1997</TITLE>
<META content="text/html; charset=gb2312" http-equiv=Content-Type>
<META name=Owner value="eppstein">
<META name=Reply-To value="eppstein@ics.uci.edu">
<META content="MSHTML 5.00.2614.3500" name=GENERATOR></HEAD>
<BODY><IMG alt="" height=72 src="ICS 180, April 8, 1997.files/icslogo2.gif"
width=472>
<P><A href="http://www.ics.uci.edu/~eppstein/180a/index.html">
<H1>ICS 180A, Spring 1997:<BR>Strategy and board game programming</H1></A>
<H2>Lecture notes for April 8, 1997<BR>Board representations</H2>In order to
operate, any game program needs to be able to store and manipulate two kinds of
objects: game positions, and game moves. These representations need to allow the
program to perform the following operations:
<UL>
<LI>Make a given move (not just when user requests, but as part of search)
<LI>Undo a move (not just for user interface, needed in search)
<LI>Display board to user
<LI>Generate a list of all possible moves
<LI>Evaluate a board position </LI></UL>Everything except displaying the board
must be fast since it happens in the inner loops of the search routine. (Board
display can be slower since it doesn't happen often.)
<P>The internal representation of moves should be very concise (since we don't
want to spend too much time generating long lists of moves) and quickly
decodable. But (very important) it should also able to represent all possible
moves! E.g. for chess, a typical computer move representation is to store the
starting square and ending square of the piece being moved; for instance the
common beginning move of the king's pawn forward two squares would be
represented "e2e4" where e2 is the name for the initial position of the pawn and
e4 is the name for its final position. The piece being captured (if any) does
not need to be stored as part of the move since it is determined by the final
position. In the computer, these positions can be represented as 6-bit values,
so the whole move could be stored internally as two bytes. But (even though some
programs are based on it) this representation is not quite capable of
representing all moves! In castling, two pieces move, a king and a rook, but we
can handle this as a special case in which we list only the king movement. More
importantly, if a pawn moves from the seventh rank to the eighth, it can be
replaced by any of four pieces: queen, rook, knight, and bishop. The
representation above doesn't allow us to specify which replacement is happening.
So when designing a move representation, one should be careful to make sure that
it covers all the special cases that might happen in your game.
<P>The onternal representation of board can be less concise but should still not
be too huge. It must represent all relevant information, not just all visible
information, but not including irrelevant information. E.g. in chess, we need to
know the positions of pieces on the board (the obvious visible information), but
we also need to know some invisible information: who's on move, whether either
player can castle, whether an en passant capture is possible, and how many moves
it's been since the last capture or pawn move. We also need to know something
about what positions have occurred in the past (because of triple repetition)
but don't need to know the entire list of past moves.
<H3>Example of Multiple Representation Possibilities: Chess</H3>There are many
possible ways of representing even something with as clearly defined a structure
as a chessboard in a computer. Here are some of the methods that have been used
by chess programs.
<P><B>Representation 1: 8x8 array of squares</B>. Within each square, keep a
value indicating which piece is present in the square (e.g. enum { empty, wK,
wN, wB, wR, wQ, wP, bK, bN, bR, bQ, bP }). Advantages: (1) simple. (2) easy to
compute material scores: <PRE> for (i=0;i<8;i++)
for(j=0;j<8;j++)
score += value[square[i,j]];
</PRE>It's a little messy but not really hard to compute possible moves; you can
loop through the squares finding pieces of appropriate color and branch
according to piece type: <PRE> for (i=0;i<8;i++)
for(j=0;j<8;j++)
switch (board[i,j]) {
case wP:
if (board[i+1,j] empty) generate move to (i+1,j)
if (i==2 && board[i+1,j] empty && board[i+2,j] empty)
generate move to (i+2,j)
if (j > 0 && board[i+1,j-1] contains black piece)
generate capture of (i+1,j-1)
if (j < 7 && board[i+1,j+1] contains black piece)
generate capture of (i+1,j+1)
break;
...
}
</PRE>however there are various annoying boundary conditions to check (e.g. a
pawn on rook-file shouldn't try to capture to one side) making this code
complicated and slower than necessary.
<P><B>Representation 2: extended array</B>. 10x10, containing extra boundary
squares containing a special "boundary" value added to the enum. This simpifies
some of the cases (reduces number of conditions in the if-statements above) at
the expense of a little space.
<P><B>Representation 3: 0x88</B>. The name of this representation comes from a
trick for testing whether a square is a valid move involving the binary
representation of the number 136 (which in hexadecimal is 0x88). We give each
square of the board a number (a single byte), of which the high 4 bits are the
row and the low 4 bits are the column: <PRE> 112 113 114 115 116 117 118 119
96 97 98 99 100 101 102 103
80 81 82 83 84 85 86 87
64 65 66 67 68 69 70 71
48 49 50 51 52 53 54 55
32 33 34 35 36 37 38 39
16 17 18 19 20 21 22 23
0 1 2 3 4 5 6 7
</PRE>Then the square left of i is i-1, right is i+1, up is i+16, down is i-16
etc. Then represent the board as an array of 128 squares (of which 64 correspond
to actual squares on the board). The advantages of this representation are (1)
it speeds up the program a little by using only one index instead of two in the
array references, and (2) you can test really quickly and easily whether a move
stays on the board: i is a legal board position if and only if (i&0x88)==0.
[Work it out, moving off the board either overflows the column giving i&0x08
nonzero, or overflows the row giving i&0x80 nonzero.] This is a pretty
commonly used technique.
<P><B>Representation 4: bitboards</B>. I'll go into this in a lot more length
than the other representations because it's probably more unfamiliar, but I
think it's also likely to work better. Instead of having an array of squares,
each containing a piece types, have an array of piece types, each of which
stores a packed array of bits listing the squares containing that piece. Since
there are 64 possible squares, each of these packed arrays can be stored in a
64-bit number (two 32-bit words). The big advantage is that you can perform
certain evaluation and move generation operations very quickly using bitwise
Boolean operations. Think of it as a way of getting your computer to do
massively parallel computations by packing things into long words. For example,
in the following position:
<P>
<CENTER><IMG src="ICS 180, April 8, 1997.files/970408.gif"></CENTER>
<P>The bitboard for the white pawns (call this 64-bit value "wP") would consist
of the bits <PRE> 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 1
0 0 0 0 0 0 0 0
</PRE>Then the bitboard squares occupied by black can be computed by a formula <PRE> bOcc = bP | bN | bB | bR | bQ | bK
</PRE>(where bP etc are bitboards for the different kinds of black pieces).
Similarly we can compute the white occupied squares, and or these two bitboards
together to get all occupied squares. The bitboard of possible white pawn
one-square move destinations can then be computed by a formula: <PRE> single_pawn_moves = (wP << 8) & ~occupied
</PRE>Let's look at this in slow motion. Shifting wP by 8 produces a bitboard of
positions one place in front of each pawn: <PRE> 0 0 0 0 0 0 0 0
0 0 0 0 0 1 0 0
0 0 0 0 0 1 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
1 1 1 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
</PRE>The negation of occupied gives a bitboard of empty squares: <PRE> 0 0 1 1 0 0 1 0
1 0 1 0 1 0 0 0
1 1 1 0 0 0 1 1
1 0 1 1 1 0 1 1
1 0 1 1 0 1 1 1
1 0 1 1 1 0 1 1
0 0 0 1 1 1 1 0
0 1 0 1 0 0 1 0
</PRE>The bitwise and of these two bitboards then gives the positions in front
of a pawn, that are not already occupied: <PRE> 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
</PRE>Similarly you can find two-square pawn moves by taking the bitboard of
one-square moves, shifting it another 8 bits, anding it with the non-occupied
squares again, and anding it with a constant bitboard (shown below) of the
squares on the fourth row (the only row onto which pawns are allowed to move two
squares): <PRE> 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
1 1 1 1 1 1 1 1
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
</PRE>Note that this constant bitboard can be generated at compile time rather
than each time we want to generate moves. Pawn captures are similar (shift by
seven or nine, and with a constant to eliminate captures off the left and right
side of the board, and with bOcc).
<P>The point of this technique is not that your code is simpler when you program
with bitboards (it's a little more complicated) but that you generate the pawn
moves all at once rather than one at a time. Also, a lot of the intermediate
expressions you need (such as bOcc) get used over and over, and only need to be
computed once. So bitboards end up being very efficient, and I think would be
even better for games other than chess in which there are fewer types of pieces.
<P>One complication arises: it's often important to count the number of nonzero
bits in a bitboard, or to find a nonzero bit (e.g. to turn the bitboard of
possible pawn moves into an explicit list of moves). Counting can be done one
byte at a time, looking up in a 256-entry table the number of nonzero bits in
each byte. There's a cute trick for finding a single nonzero bit: x^(x-1) (where
the uparrow is C notation for exclusive or) gives a binary number ...000111...
where the first one of x^(x-1) is the last nonzero bit of x. If you need to turn
this into an actual bit, take the result modulo some carefully chosen number M
(for which the numbers ...000111... are all different mod M), and look the
result up in a table. As a simple example, the following code finds the index of
the last nonzero bit of a byte: <PRE> int T = { -1, 0, 7, 1, 3, -1, 6, 2, 5, 4, -1, -1 };
int last_bit(unsigned char b) { return T[(b^(b-1)) % 11]; }
</PRE>
<H3>How to Undo?</H3>Remember we said our board representation needed to handle
undo operations. There are two possible methods: (1) Keep a stack in which each
stack item holds a whole board representation; to make a move push it on the
stack and to undo a move pop the stack. Probably this is too slow... (2) Keep a
stack storing only the move itself together with enough extra information to
undo the move and restore all the information in the board position. E.g. in
chess you would need to store the identity of a captured piece (if any) and
enough information to restore castling and en passant capturing privileges.
<H3>Repetition Detection</H3>Some games e.g. Go, Chess have special rules about
what happens when the same position is repeated (in chess, third repetition of a
position gives the player making the repetition the right to declare a draw).
How to tell? Short answer: make a hash function translating the position to a
reasonably large number (we'll talk more about this later because this is also
very important for speeding up the search). Then keep a list of the hash codes
for previous game positions and test if your position shows up in it. Typical
hash function: make 64*13 table of large random numbers; when piece x is on
position y, look up table[x,y] and add it to hash ignoring overflow [Zobrist].
Note that, when making a move of a piece y from positions x to z, you can update
the hash very quickly: just subtract table[x,y] and add table[z,y].
<HR>
<A href="http://www.ics.uci.edu/~eppstein/">David Eppstein, <A
href="http://www.ics.uci.edu/">Dept. Information & Computer Science</A>, <A
href="http://www.uci.edu/">UC Irvine</A>, Monday, 14-Apr-1997 11:31:24 PDT.
</BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -