📄 ch16.htm
字号:
<HTML>
<HEAD>
<TITLE>Chapter 16 -- Connect4: Human versus Machine</TITLE>
<META>
</HEAD>
<BODY TEXT="#000000" BGCOLOR="#FFFFFF" LINK="#0000EE" VLINK="#551A8B" ALINK="#CE2910">
<H1><FONT COLOR=#FF0000>Chapter 16</FONT></H1>
<H1><B><FONT SIZE=5 COLOR=#FF0000>Connect4: Human versus Machine</FONT></B>
</H1>
<P>
<HR WIDTH="100%"></P>
<P>
<H3 ALIGN=CENTER><FONT COLOR="#000000"><FONT SIZE=+2>CONTENTS<A NAME="CONTENTS"></A>
</FONT></FONT></H3>
<UL>
<LI><A HREF="#DesigningConnect4" >Designing Connect4</A>
<UL>
<LI><A HREF="#HowtoPlaytheGame" >How to Play the Game</A>
<LI><A HREF="#TheElementsoftheGame" >The Elements of the Game</A>
<LI><A HREF="#TheAIStrategy" >The AI Strategy</A>
</UL>
<LI><A HREF="#SampleAppletConnect4" >Sample Applet: Connect4</A>
<UL>
<LI><A HREF="#TheGameEngineClasses" >The Game Engine Classes</A>
<LI><A HREF="#TheConnect4Class" >The Connect4 Class</A>
</UL>
<LI><A HREF="#Summary" >Summary</A>
<LI><A HREF="#QA" >Q&A</A>
<LI><A HREF="#Workshop" >Workshop</A>
<UL>
<LI><A HREF="#Quiz" >Quiz</A>
<LI><A HREF="#Exercises" >Exercises</A>
</UL>
</UL>
<HR>
<P>
Yesterday you broke away from Java code for a little while and
spent some time learning about artificial intelligence (AI) and
how it is used in games. I promised you yesterday that you would
spend today's lesson implementing a game complete with a computer
opponent using strategic AI. I've been known to keep most of my
promises, and today's lesson is no exception.
<P>
Today you develop a complete Connect4 game from scratch. Along
the way, you learn about the type of AI strategy used by a game
like Connect4, and then you get to work implementing it. By the
end of today, you will have created your own worst nightmare:
a computer opponent that can consistently beat you in a game of
Connect4. You might be thinking that no stupid computer player
could ever match wits with you. At this point, I'm not going to
making any guarantees, but let me just say that if any money were
involved, mine would be on the player with the silicon brain!
Still skeptical? Well, read on and find out for yourself.
<P>
The following topics are covered in today's lesson:
<UL>
<LI>Designing Connect4
<LI>Sample applet: Connect4
</UL>
<H2><A NAME="DesigningConnect4"><B><FONT SIZE=5 COLOR=#FF0000>Designing
Connect4</FONT></B></A></H2>
<P>
Today's entire focus is on creating a Connect4 game with a computer
player that can at least give a human player a good game. After
you finish the game, I think you'll agree that the computer player
can do a lot more than give you a good game. In fact, I've already
mentioned that the computer player will be able to beat most human
players pretty consistently. But enough of that for now; you'll
have plenty of time to go head-to-head against the computer later.
<H3><A NAME="HowtoPlaytheGame"><B>How to Play the Game</B></A>
</H3>
<P>
In case you've never played Connect4, let's briefly go over the
basic rules. It is a simple game that is similar to tic-tac-toe
in that the goal is to complete a continuous row, column, or diagonal
series. The game is played on a rectangular "board"
that contains a 7<FONT FACE="Symbol">¥</FONT>6 array of positions.
You use round pieces, similar to checker pieces, to represent
each move. Figure 16.1 shows what a Connect4 board looks like.
<P>
<A HREF="f16-1.gif" ><B>Figure 16. : </B><I>A Connect4 board, complete with pieces.</I></A>
<P>
The main catch to Connect4 is that the board stands upright, with
each column being slotted. So a move consists of selecting a column
to drop your piece in, and then gravity takes care of the rest.
This means that instead of explicitly choosing the vertical position
of each move, you can only stack up the pieces vertically. This
fact impacts the strategy greatly.
<P>
The game is won when one of the players manages to connect a horizontal,
vertical, or diagonal series of four pieces. There is the chance
for a tie, as in tic-tac-toe, but it is less likely, simply because
of the number of ways in which the game can be won.
<H3><A NAME="TheElementsoftheGame"><B>The Elements of the Game</B></A>
</H3>
<P>
Before moving into the meat of today's lesson-studying the AI
necessary to create an engaging computer opponent-let's take a
look at what Connect4 requires in terms of the basic game. First
of all, you know that it is a board game, or at least the play
is similar to that of a board game. The style of play involves
the players dropping pieces into columns of the board on alternating
turns. Thus, you apparently don't have much need for the sprite
animation code you've relied on so heavily throughout the book.
Well, technically you could animate the pieces falling down the
columns, but because that would involve a decent amount of extra
work, let's leave it as an exercise for later!
<P>
Because you're not going to fool with any animation, the graphics
for the game are simplified a little. This is a good thing, because
implementing the AI alone will keep you busy enough. The graphics
for the game basically consist of drawing the board and pieces.
Not bad so far. Because the computer player is likely to take
time calculating its next move, it might also be nice to have
a status line. The status line simply indicates the current state
of the game, with a message something like "Thinking..."
or "Your Turn."
<P>
Because you're not going to implement animation, there is one
neat little extra you can add without too much extra work: a column
selector hand. The column selector hand is displayed over the
currently selected column so that the human player can tell exactly
which column a piece will be dropped in. Each time the player
moves the mouse, the hand is updated to reflect the selected column.
The selector hand is simple to implement, and it gives the game
a nice touch.
<P>
So far, the graphics requirements of the game consist of four
elements:
<UL>
<LI>Board
<LI>Pieces
<LI>Status line
<LI>Hand selector
</UL>
<P>
Now, let's take a look at what type of user input the game needs.
Because you've already decided to go with a mouse-controlled hand
selector to pick the column to drop a piece in, it only makes
sense to make the entire user interface for the game mouse-driven.
So moving the mouse selects a column, and clicking the mouse button
drops a piece in that column.
<H3><A NAME="TheAIStrategy"><B>The AI Strategy</B></A></H3>
<P>
The only other area to cover is the type of AI strategy used by
the game and how it connects to the general play of the game.
As you might recall from yesterday's lesson, the most popular
type of AI used in games like Connect4 is strategic AI that makes
use of a depth search algorithm linked to a fixed table of rule
information. This is exactly the AI strategy you use when developing
the Connect4 code, but you'll learn the details of that later
in this lesson.
<P>
For now, let's think of the AI in terms of the logical components
required to make it work. Basically, the AI algorithm should come
up with the best possible column for the computer player to drop
the next piece into. Keeping that in mind, a good approach would
be to break the game into two components: the AI engine that calculates
the computer player's next move, and the higher-level applet itself,
which uses this move to update the graphics in the game.
<P>
In this way, the human and computer players' moves are handled
very similarly, which makes things much easier to deal with; each
move just results in a piece being placed in a position on the
game board. Another important benefit of this arrangement is that
the AI engine handles all the details of figuring out whether
moves are valid, along with determining whether there is a winner
in the game. In this way, the engine is actually more of a general
Connect4 game engine, rather than just an AI engine. Figure 16.2
shows the two Connect4 components and what kind of information
they transfer to each other.
<P>
<A HREF="f16-2.gif" ><B>Figure 16.2 : </B><I>The logical Connect4 game components.</I></A>
<P>
This approach results in a complete separation of the low-level
algorithms necessary to drive the game from the high-level applet
issues. But you still haven't learned anything about the details
of the AI itself. How can the computer player possibly know what
moves to make and be able to actually compete with a human player?
To answer this question, you must first be able to assess the
state of the game from a particular player's perspective. More
specifically, you need to be able to calculate a score for a player
that determines how he is faring in the game.
<P>
A player's score reflects his status in the game and basically
how close he is to victory. So to calculate the score, you first
need to be able to know when a game has been won. This might at
first seem trivial; just look for a series of four pieces in a
row, column, or diagonal, right? That's right for you or me, but
teaching the computer how to look at the board and figure this
out isn't quite so simple. One approach is to keep up with every
possible combination of piece positions that constitutes a victory.
These combinations could be stored in a table and then used as
a basis to determine how close each player is to winning the game.
Although this approach sounds fairly cumbersome, it's actually
not too hard to implement.
<P>
With the scoring system in place, you can then use a look-ahead
depth search to try out different moves for the computer player
and determine the best one. The combination of the table of winning
moves and the look-ahead search is what gives the computer player
its "brains." Although a few more details are involved
in implementing the AI for the game, this covers the major points
of interest. I don't know about you, but I'm getting tired of
talking about the game in general terms; let's start writing it!
<P>
<CENTER><TABLE BORDERCOLOR=#000000 BORDER=1 WIDTH=80%>
<TR><TD><B>Note</B></TD></TR>
<TR><TD>
<BLOCKQUOTE>
Incidentally, a look-ahead depth search is a technique that involves looking into the future of a game and trying out every possible move to determine the best one. A look-ahead depth search is a computer AI version of the common human strategy of planning
moves in a game based on what the other player might do in each situation; the primary difference being that the computer is much more efficient and can evaluate a lot more possibilities.</BLOCKQUOTE>
</TD></TR>
</TABLE></CENTER>
<P>
<H2><A NAME="SampleAppletConnect4"><B><FONT SIZE=5 COLOR=#FF0000>Sample
Applet: Connect4</FONT></B></A></H2>
<P>
The Connect4 applet is a complete Java Connect4 game including
strategic AI for a computer player good enough to give most people
fits. Figure 16.3 shows a screen shot of a game of Connect4-and,
yes, I'm the one losing! The complete source code, executable,
images, and sounds for Connect4 are located on the accompanying
CD-ROM.
<P>
<A HREF="f16-3.gif" ><B>Figure 16.3 : </B><I>The Connect4 sample applet.</I></A>
<P>
Connect4 starts out by setting up an empty game board and giving
the human player the first turn. After the human player makes
a move, the status message "Thinking..." is displayed
while the AI engine determines the computer player's move. Figure
16.4 shows the game while the computer player is "thinking."
<P>
<A HREF="f16-4.gif" ><B>Figure 16.4 : </B><I>The Connect4 sample applet during the computer player's turn.</I></A>
<P>
<CENTER><TABLE BORDERCOLOR=#000000 BORDER=1 WIDTH=80%>
<TR><TD><B>Note</B></TD></TR>
<TR><TD>
<BLOCKQUOTE>
Study has revealed that it is technically possible to always win at Connect4 if you are the player to make the first move, regardless of the other player's strategy.</BLOCKQUOTE>
</TD></TR>
</TABLE></CENTER>
<P>
<P>
The computer makes its move and the play shifts back to the human
player. This exchange of turns continues until there is a win,
loss, or tie. When the game ends, you can start a new one by clicking
in the applet window. Sound effects are played during the course
of the game to indicate who made which move. Sound effects are
also played for making an invalid move, starting a new game, winning,
and losing.
<P>
If you're curious about how well the computer player plays the
game, load it up and give it a try. You might be a Connect4 whiz
and teach the computer a lesson, or you might end up learning
a few things!
<H3><A NAME="TheGameEngineClasses"><B>The Game Engine Classes</B></A>
</H3>
<P>
The heart of the AI in Connect4 is the Connect4 game engine. The
Connect4 game engine is composed of two classes: <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>
and <TT><FONT FACE="Courier">Connect4State</FONT></TT>. The <TT><FONT FACE="Courier">Connect4Engine</FONT></TT>
class provides the framework for the game engine itself, while
the <TT><FONT FACE="Courier">Connect4State</FONT></TT> class models
the current state of a Connect4 game. Together, these two classes
provide the overhead necessary to conduct a two-player game of
Connect4 with either player being a human or computer player.
<P>
These engine classes implement a computer player using look-ahead
depth searching AI. The intelligence of the computer player is
determined by the depth of the search. Higher depth searches result
in a more intelligent computer player, but at the cost of more
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -