📄 ch16.htm
字号:
processing time. But enough theory, let's go ahead and look into
how all this stuff is implemented in the <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>
and <TT><FONT FACE="Courier">Connect4State</FONT></TT> classes!
<P>
The <TT><FONT FACE="Courier">Connect4Engine</FONT></TT> class
models the game engine, including the computer player AI, for
the Connect4 game; it is based on implementations originally developed
by Keith Pomakis and Sven Wiebus. The following are the member
variables defined in <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">private static Random rand = new Random(System.currentTimeMillis());
<BR>
private Connect4State state;</FONT></TT>
</BLOCKQUOTE>
<P>
The <TT><FONT FACE="Courier">Connect4Engine</FONT></TT> class
contains a member variable, <TT><FONT FACE="Courier">state</FONT></TT>,
which is of type <TT><FONT FACE="Courier">Connect4State</FONT></TT>.
It turns out that <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>
delegates much of the dirty work of the AI and game state upkeep
to the <TT><FONT FACE="Courier">Connect4State</FONT></TT> class.
Even without knowing the details of the <TT><FONT FACE="Courier">Connect4State</FONT></TT>
class, you'll find that it's not too hard to figure out what the
<TT><FONT FACE="Courier">Connect4State</FONT></TT> class is doing
by examining how <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>
uses it. Nevertheless, you'll learn all the messy details of the
<TT><FONT FACE="Courier">Connect4State</FONT></TT> class in a
little while.
<P>
<TT><FONT FACE="Courier">Connect4Engine</FONT></TT> implements
two methods for handling each player making a move: <TT><FONT FACE="Courier">makeMove</FONT></TT>
and <TT><FONT FACE="Courier">computerMove</FONT></TT>. The following
is the source code for <TT><FONT FACE="Courier">makeMove</FONT></TT>:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public Point makeMove(int player, int
xPos) {<BR>
int yPos = state.dropPiece(player, xPos);<BR>
return (new Point(xPos, yPos));<BR>
}</FONT></TT>
</BLOCKQUOTE>
<P>
The <TT><FONT FACE="Courier">makeMove</FONT></TT> method is called
when the human player makes a move. <TT><FONT FACE="Courier">makeMove</FONT></TT>
takes a player number (<TT><FONT FACE="Courier">player</FONT></TT>),
which can be <TT><FONT FACE="Courier">0</FONT></TT> or <TT><FONT FACE="Courier">1</FONT></TT>,
and a column to drop the piece in (<TT><FONT FACE="Courier">xPos</FONT></TT>)
as parameters. The game state is updated to reflect the move,
and the XY position of the move on the board is returned as a
<TT><FONT FACE="Courier">Point</FONT></TT> object. If the move
is invalid (for example, the column might already be full), the
<TT><FONT FACE="Courier">y</FONT></TT> member of the <TT><FONT FACE="Courier">Point</FONT></TT>
object is set to <TT><FONT FACE="Courier">-1</FONT></TT>. Otherwise,
it has a value in the range of <TT><FONT FACE="Courier">0</FONT></TT>
to <TT><FONT FACE="Courier">6</FONT></TT>.
<P>
The <TT><FONT FACE="Courier">computerMove</FONT></TT> method is
called for the computer player to make a move. Listing 16.1 shows
the source code for the <TT><FONT FACE="Courier">computerMove</FONT></TT>
method.
<HR>
<BLOCKQUOTE>
<B>Listing 16.1. The </B><TT><B><FONT FACE="Courier">Connect4Engine</FONT></B></TT><B>
class's </B><TT><B><FONT FACE="Courier">computerMove</FONT></B></TT><B>
method.<BR>
</B>
</BLOCKQUOTE>
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public Point computerMove(int player,
int level) {<BR>
int bestXPos = -1, goodness = 0, bestWorst = -30000;
<BR>
int numOfEqual = 0;<BR>
<BR>
// Simulate a drop in each of the columns<BR>
for (int i = 0; i < 7; i++) {<BR>
Connect4State tempState = new Connect4State(state);
<BR>
<BR>
// If column is full, move on<BR>
if (tempState.dropPiece(player, i) <
0)<BR>
continue;<BR>
<BR>
// If this drop wins the game, then cool
<BR>
if (tempState.isWinner(player)) {<BR>
bestWorst = 25000;<BR>
bestXPos = i;<BR>
}<BR>
// Otherwise, look ahead to see how good
it is<BR>
else<BR>
goodness = tempState.evaluate(player,
level, 1, -30000,<BR>
-bestWorst);<BR>
<BR>
// If this move looks better than previous
moves, remember it<BR>
if (goodness > bestWorst) {<BR>
bestWorst = goodness;<BR>
bestXPos = i;<BR>
numOfEqual = 1;<BR>
}<BR>
<BR>
// If two moves are equally good, make
a random choice<BR>
if (goodness == bestWorst) {<BR>
numOfEqual++;<BR>
if (Math.abs(rand.nextInt())
% 10000 <<BR>
(10000 / numOfEqual))
<BR>
bestXPos = i;
<BR>
}<BR>
}<BR>
<BR>
// Drop the piece in the best column<BR>
if (bestXPos >= 0) {<BR>
int yPos = state.dropPiece(player, bestXPos);
<BR>
if (yPos >= 0)<BR>
return (new Point(bestXPos,
yPos));<BR>
}<BR>
return null;<BR>
}</FONT></TT>
</BLOCKQUOTE>
<HR>
<P>
The <TT><FONT FACE="Courier">computerMove</FONT></TT> method handles
all the details of determining the best move for the computer
player given the current state of the game. It takes a player
number (<TT><FONT FACE="Courier">player</FONT></TT>) and a level
(<TT><FONT FACE="Courier">level</FONT></TT>) as parameters. The
<TT><FONT FACE="Courier">level</FONT></TT> parameter specifies
the depth of the look-ahead search and directly affects both the
intelligence of the computer player and the amount of time it
takes the computer player to figure out its move. All this is
carried out by determining how each possible move affects the
computer player's score. Most of the low-level AI work is handled
by the <TT><FONT FACE="Courier">evaluate</FONT></TT> method in
<TT><FONT FACE="Courier">Connect4State</FONT></TT>, which is called
by <TT><FONT FACE="Courier">computerMove</FONT></TT>. Notice that
if <TT><FONT FACE="Courier">computerMove</FONT></TT> isolates
the best move down to two equal choices, it randomly chooses one
or the other. This gives a little more human feel to the computer
player.
<P>
The other three methods in <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>
are <TT><FONT FACE="Courier">getBoard</FONT></TT>, <TT><FONT FACE="Courier">getWinner</FONT></TT>,
and <TT><FONT FACE="Courier">isTie</FONT></TT>, whose source code
follows:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public int[][] getBoard() {<BR>
return state.board;<BR>
}<BR>
<BR>
public boolean isWinner(int player) {<BR>
return state.isWinner(player);<BR>
}<BR>
<BR>
public boolean isTie() {<BR>
return state.isTie();<BR>
}</FONT></TT>
</BLOCKQUOTE>
<P>
The <TT><FONT FACE="Courier">getBoard</FONT></TT> method simply
returns a 7<FONT FACE="Symbol">¥</FONT>6 array of integers
representing the current state of the game board. <TT><FONT FACE="Courier">getWinner</FONT></TT>
and <TT><FONT FACE="Courier">isTie</FONT></TT> check with the
game state member object, <TT><FONT FACE="Courier">state</FONT></TT>,
to see whether the game has been won or tied.
<P>
That pretty much sums up the <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>
class. With the exception of the <TT><FONT FACE="Courier">computerMove</FONT></TT>
method, which was a little tricky, it was pretty painless, don't
you think? Well, brace yourself, because <TT><FONT FACE="Courier">Connect4State</FONT></TT>
is a little messier. Here are the member variables defined in
the <TT><FONT FACE="Courier">Connect4State</FONT></TT> class:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">public static final int winPlaces = 69,
maxPieces = 42, Empty = 2;<BR>
public static boolean[][][] map;<BR>
public int[][] board = new int[7][6];<BR>
public int[][] score = new int[2][winPlaces];<BR>
public int numPieces;</FONT></TT>
</BLOCKQUOTE>
<P>
The first step in figuring out <TT><FONT FACE="Courier">Connect4State</FONT></TT>
is to understand what the member variables represent. The first
three members (<TT><FONT FACE="Courier">winPlaces</FONT></TT>,
<TT><FONT FACE="Courier">maxPieces</FONT></TT>, and <TT><FONT FACE="Courier">Empty</FONT></TT>)
are static final integers, which simply means that they are all
constant. <TT><FONT FACE="Courier">winPlaces</FONT></TT>, which
specifies the number of possible winning combinations on the board,
is calculated using the following equation:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">winPlaces = 4*w*h - 3*w*n - 3*h*n + 3*w
+ 3*h - 4*n + 2*n*n;</FONT></TT>
</BLOCKQUOTE>
<P>
This is a general equation that can be applied to any ConnectX-type
game. In the equation, <TT><FONT FACE="Courier">w</FONT></TT>
and <TT><FONT FACE="Courier">h</FONT></TT> represent the width
and height of the game board, and <TT><FONT FACE="Courier">n</FONT></TT>
represents the number of pieces that must be in a series to constitute
a victory. Because Connect4 uses a 7<FONT FACE="Symbol">¥</FONT>6
game board with a four-piece series constituting a win, you can
simply calculate <TT><FONT FACE="Courier">winPlaces</FONT></TT>
beforehand, which is exactly what is done in <TT><FONT FACE="Courier">Connect4State</FONT></TT>.
<P>
The <TT><FONT FACE="Courier">maxPieces</FONT></TT> member specifies
the maximum number of pieces that can be placed on the board.
It is calculated using the following equation:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">maxPieces = w*h;</FONT></TT>
</BLOCKQUOTE>
<P>
This calculation is pretty straightforward. The result is used
to detect whether there is a tie; a tie occurs when nobody has
won and the number of pieces in the game equals <TT><FONT FACE="Courier">maxPieces</FONT></TT>.
<P>
The other constant member, <TT><FONT FACE="Courier">Empty</FONT></TT>,
represents an empty space on the board. Each space on the board
can contain a player number (<TT><FONT FACE="Courier">0</FONT></TT>
or <TT><FONT FACE="Courier">1</FONT></TT>) or the <TT><FONT FACE="Courier">Empty</FONT></TT>
constant, which is set to <TT><FONT FACE="Courier">2</FONT></TT>.
<P>
Moving right along, the <TT><FONT FACE="Courier">map</FONT></TT>
member variable is a three-dimensional array of booleans that
holds the lookup table of winning combinations. To better understand
how the map is laid out, first think of it as a two-dimensional
array with the same dimensions as the board for the game; in other
words, think of it as a 7<FONT FACE="Symbol">¥</FONT>6 two-dimensional
array. Now, add the third dimension by attaching an array of winning
positions onto each two-dimensional array entry. Each different
winning combination in the game is given a unique position within
this array (the winning position array is <TT><FONT FACE="Courier">winPlaces</FONT></TT>
in length). Each location in this array is set to <TT><FONT FACE="Courier">true</FONT></TT>
or <TT><FONT FACE="Courier">false</FONT></TT> based on whether
the winning series intersects the associated board position.
<P>
Let's go over a quick example to make sure you understand how
the map works. Take a look at the upper-left space on the game
board back in Figure 16.1; let's call this position 0,0 on the
board. Now, think about which different winning series of pieces
would include this position. Give up? Check out Figure 16.5.
<P>
<A HREF="f16-5.gif" ><B>Figure 16.5 : </B><I>Winning series possibilities for position 0,0.</I></A>
<P>
As you can see, position 0,0 on the board is a part of three different
winning scenarios. Therefore, the winning position array for position
0,0 would have these three entries set to <TT><FONT FACE="Courier">true</FONT></TT>,
and all the others would be set to <TT><FONT FACE="Courier">false</FONT></TT>.
If the winning moves shown in Figure 16.5 were at positions 11-13
in the winning series array, you would initialize position 0,0
in the map like this:
<BLOCKQUOTE>
<TT><FONT FACE="Courier">...<BR>
map[0][0][9] = false;<BR>
map[0][0][10] = false;<BR>
map[0][0][11] = true;<BR>
map[0][0][12] = true;<BR>
map[0][0][13] = true;<BR>
map[0][0][14] = false;<BR>
map[0][0][15] = false;<BR>
...</FONT></TT>
</BLOCKQUOTE>
<P>
After the entire map is constructed, the AI algorithms can use
it to look up winning combinations and determine how close each
player is to winning.
<P>
The <TT><FONT FACE="Courier">board</FONT></TT> member variable
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -