📄 ch16.htm
字号:
is simply a 7<FONT FACE="Symbol">¥</FONT>6 two-dimensional
array of integers that represents the state of the game. Each
integer entry can be set to either <TT><FONT FACE="Courier">0</FONT></TT>
or <TT><FONT FACE="Courier">1</FONT></TT> (for a player occupying
that position on the board) or <TT><FONT FACE="Courier">Empty</FONT></TT>.
<P>
The <TT><FONT FACE="Courier">score</FONT></TT> member variable
contains a two-dimensional array of integers representing the
"score" for the players. The main array in <TT><FONT FACE="Courier">score</FONT></TT>
contains a subarray for each player that is <TT><FONT FACE="Courier">winPlaces</FONT></TT>
in length. These subarrays contain information describing how
close the player is to completing a winning series. It works like
this: Each subarray entry corresponds to a potential winning series
and contains a count of how many of the player's pieces occupy
the series. If a series is no longer a winning possibility for
the player, its entry in the array is set to 0. Otherwise, the
entry is set to <TT><FONT FACE="Courier">2</FONT></TT><FONT SIZE=1 FACE="MCPdigital">p</FONT>,
where <TT><FONT FACE="Courier">p</FONT></TT> is the number of
the player's pieces occupying the series. So if one of these entries
is set to <TT><FONT FACE="Courier">16</FONT></TT> (<TT><FONT FACE="Courier">2</FONT></TT><FONT SIZE=1 FACE="MCPdigital">4</FONT>),
that player has won.
<P>
Rounding out the member variables for <TT><FONT FACE="Courier">Connect4State</FONT></TT>
is <TT><FONT FACE="Courier">numPieces</FONT></TT>, which is just
a count of how many pieces have been played in the game. <TT><FONT FACE="Courier">numPieces</FONT></TT>
is really used only in determining whether the game is a tie;
in the event of a tie, <TT><FONT FACE="Courier">numPieces</FONT></TT>
is equal to <TT><FONT FACE="Courier">maxPieces</FONT></TT>.
<P>
That covers the member variables for the <TT><FONT FACE="Courier">Connect4State</FONT></TT>
class. You might have realized by now that by understanding the
member variables and what they model, you already understand a
great deal about how the AI works in the game. Let's move on to
the methods in <TT><FONT FACE="Courier">Connect4State</FONT></TT>,
because that's where the fun really begins.
<P>
The default constructor for <TT><FONT FACE="Courier">Connect4State</FONT></TT>
takes on the role of initializing the <TT><FONT FACE="Courier">map</FONT></TT>,
<TT><FONT FACE="Courier">board</FONT></TT>, and <TT><FONT FACE="Courier">score</FONT></TT>
arrays. This constructor is shown in Listing 16.2.
<HR>
<BLOCKQUOTE>
<B>Listing 16.2. The </B><TT><B><FONT FACE="Courier">Connect4State</FONT></B></TT><B>
class's default constructor.<BR>
</B>
</BLOCKQUOTE>
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public Connect4State() {<BR>
// Initialize the map<BR>
int i, j, k, count = 0;<BR>
if (map == null) {<BR>
map = new boolean[7][6][winPlaces];<BR>
for (i = 0; i < 7; i++)<BR>
for (j = 0; j < 6; j++)
<BR>
for (k = 0; k
< winPlaces; k++)<BR>
map[i][j][k]
= false;<BR>
<BR>
// Set the horizontal win positions<BR>
for (i = 0; i < 6; i++)<BR>
for (j = 0; j < 4; j++)
{<BR>
for (k = 0; k
< 4; k++)<BR>
map[j
+ k][i][count] = true;<BR>
count++;<BR>
}<BR>
<BR>
// Set the vertical win positions<BR>
for (i = 0; i < 7; i++)<BR>
for (j = 0; j < 3; j++)
{<BR>
for (k = 0; k
< 4; k++)<BR>
map[i][j
+ k][count] = true;<BR>
count++;<BR>
}<BR>
<BR>
// Set the forward diagonal win positions
<BR>
for (i = 0; i < 3; i++)<BR>
for (j = 0; j < 4; j++)
{<BR>
for (k = 0; k
< 4; k++)<BR>
map[j
+ k][i + k][count] = true;<BR>
count++;<BR>
}<BR>
<BR>
// Set the backward diagonal win positions
<BR>
for (i = 0; i < 3; i++)<BR>
for (j = 6; j >= 3; j--)
{<BR>
for (k = 0; k
< 4; k++)<BR>
map[j
- k][i + k][count] = true;<BR>
count++;<BR>
}<BR>
}<BR>
<BR>
// Initialize the board<BR>
for (i = 0; i < 7; i++)<BR>
for (j = 0; j < 6; j++)<BR>
board[i][j] = Empty;<BR>
<BR>
// Initialize the scores<BR>
for (i = 0; i < 2; i++)<BR>
for (j = 0; j < winPlaces; j++)<BR>
score[i][j] = 1;<BR>
<BR>
numPieces = 0;<BR>
}</FONT></TT>
</BLOCKQUOTE>
<HR>
<P>
The default constructor also sets the number of pieces to zero.
There is also a copy constructor for <TT><FONT FACE="Courier">Connect4State</FONT></TT>,
whose source code follows:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public Connect4State(Connect4State state)
{<BR>
// Copy the board<BR>
for (int i = 0; i < 7; i++)<BR>
for (int j = 0; j < 6; j++)<BR>
board[i][j] = state.board[i][j];
<BR>
<BR>
// Copy the scores<BR>
for (int i = 0; i < 2; i++)<BR>
for (int j = 0; j < winPlaces; j++)
<BR>
score[i][j] = state.score[i][j];
<BR>
<BR>
numPieces = state.numPieces;<BR>
}</FONT></TT>
</BLOCKQUOTE>
<P>
If you aren't familiar with copy constructors, they enable you
to create new objects that are copies of existing objects. It
is necessary to have a copy constructor for <TT><FONT FACE="Courier">Connect4State</FONT></TT>
because the AI algorithms use temporary state objects a great
deal, as you'll see in a moment. The copy constructor for <TT><FONT FACE="Courier">Connect4State</FONT></TT>
just copies the contents of each member variable.
<P>
The <TT><FONT FACE="Courier">isWinner</FONT></TT> method in <TT><FONT FACE="Courier">Connect4State</FONT></TT>
checks to see whether either player has won the game:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public boolean isWinner(int player) {
<BR>
for (int i = 0; i < winPlaces; i++)<BR>
if (score[player][i] == 16)<BR>
return true;<BR>
return false;<BR>
}</FONT></TT>
</BLOCKQUOTE>
<P>
The <TT><FONT FACE="Courier">isWinner</FONT></TT> method looks
for a winner by checking to see whether any member in the <TT><FONT FACE="Courier">score</FONT></TT>
array is equal to <TT><FONT FACE="Courier">16</FONT></TT> (<TT><FONT FACE="Courier">2</FONT></TT><FONT SIZE=1 FACE="MCPdigital">4</FONT>).
This indicates victory because it means that four pieces occupy
the series.
<P>
The <TT><FONT FACE="Courier">isTie</FONT></TT> method checks for
a tie by simply seeing whether <TT><FONT FACE="Courier">numPieces</FONT></TT>
equals <TT><FONT FACE="Courier">maxPieces</FONT></TT>, which indicates
that the board is full. The source code for <TT><FONT FACE="Courier">isTie</FONT></TT>
follows:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public boolean isTie() {<BR>
return (numPieces == maxPieces);<BR>
}<BR>
The dropPiece method handles dropping a new piece onto the board:
<BR>
public int dropPiece(int player, int xPos) {<BR>
int yPos = 0;<BR>
while ((board[xPos][yPos] != Empty) && (++yPos
< 6))<BR>
;<BR>
<BR>
// The column is full<BR>
if (yPos == 6)<BR>
return -1;<BR>
<BR>
// The move is OK<BR>
board[xPos][yPos] = player;<BR>
numPieces++;<BR>
updateScore(player, xPos, yPos);<BR>
<BR>
return yPos;<BR>
}</FONT></TT>
</BLOCKQUOTE>
<P>
The <TT><FONT FACE="Courier">dropPiece</FONT></TT> method takes
a player and an X position (column) as its only parameters. It
first checks to make sure there is room in the specified column
to drop a new piece. Incidentally, you might have noticed from
this code that the board is stored upside down in the <TT><FONT FACE="Courier">board</FONT></TT>
member variable. Having the board inverted simplifies the process
of adding a new piece a little. If the move is valid, the entry
in the <TT><FONT FACE="Courier">board</FONT></TT> array is set
to <TT><FONT FACE="Courier">player</FONT></TT>, and <TT><FONT FACE="Courier">numPieces</FONT></TT>
is incremented. Then the score is updated to reflect the move
with a call to <TT><FONT FACE="Courier">updateScore</FONT></TT>.
You'll learn about <TT><FONT FACE="Courier">updateScore</FONT></TT>
in a moment.
<P>
The <TT><FONT FACE="Courier">evaluate</FONT></TT> method is where
the low-level AI in the game takes place. The source code for
the <TT><FONT FACE="Courier">evaluate</FONT></TT> method is shown
in Listing 16.3.
<HR>
<BLOCKQUOTE>
<B>Listing 16.3. The </B><TT><B><FONT FACE="Courier">Connect4State</FONT></B></TT><B>
class's </B><TT><B><FONT FACE="Courier">evaluate</FONT></B></TT><B>
method.<BR>
</B>
</BLOCKQUOTE>
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public int evaluate(int player, int level,
int depth, int alpha,<BR>
int beta) {<BR>
int goodness, best, maxab = alpha;<BR>
<BR>
if (level != depth) {<BR>
best = -30000;<BR>
for(int i = 0; i < 7; i++) {<BR>
Connect4State tempState =
new Connect4State(this);<BR>
if (tempState.dropPiece(getOtherPlayer(player),
i) < 0)<BR>
continue;<BR>
<BR>
if (tempState.isWinner(getOtherPlayer(player)))
<BR>
goodness = 25000
- depth;<BR>
else<BR>
goodness = tempState.evaluate(getOtherPlayer(player),
<BR>
level,
depth + 1, -beta, -maxab);<BR>
if (goodness > best) {
<BR>
best = goodness;
<BR>
if (best >
maxab)<BR>
maxab
= best;<BR>
}<BR>
if (best > beta)<BR>
break;<BR>
}<BR>
<BR>
// What's good for the other player is
bad for this one<BR>
return -best;<BR>
}<BR>
<BR>
return (calcScore(player) - calcScore(getOtherPlayer(player)));
<BR>
}</FONT></TT>
</BLOCKQUOTE>
<HR>
<P>
It is the <TT><FONT FACE="Courier">evaluate</FONT></TT> method's
job to come up with the best move for the computer player given
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -