📄 323-325.html
字号:
<HTML>
<HEAD>
<META name=vsisbn content="0849398010">
<META name=vstitle content="Industrial Applications of Genetic Algorithms">
<META name=vsauthor content="Charles Karr; L. Michael Freeman">
<META name=vsimprint content="CRC Press">
<META name=vspublisher content="CRC Press LLC">
<META name=vspubdate content="12/01/98">
<META name=vscategory content="Web and Software Development: Artificial Intelligence: Other">
<TITLE>Industrial Applications of Genetic Algorithms:Genetic Algorithms for Game Playing</TITLE>
<!-- HEADER -->
<STYLE type="text/css">
<!--
A:hover {
color : Red;
}
-->
</STYLE>
<META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW">
<!--ISBN=0849398010//-->
<!--TITLE=Industrial Applications of Genetic Algorithms//-->
<!--AUTHOR=Charles Karr//-->
<!--AUTHOR=L. Michael Freeman//-->
<!--PUBLISHER=CRC Press LLC//-->
<!--IMPRINT=CRC Press//-->
<!--CHAPTER=17//-->
<!--PAGES=323-325//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="321-323.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="325-328.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B>PROBLEM DESCRIPTION</B></FONT></P>
<P><FONT SIZE="+1"><B><I>The Game</I></B></FONT></P>
<P>The game of “Tic-Tac-Toe” is quite simple; generally thought of as a “kid’s game.” It is played on a 3 × 3 board. Initially, the board contains nothing but blank squares. The two players, X and O, each place X’s and O’s on the board, one at a time, alternately. The player who places three of his pieces in a row either horizontally, vertically, or diagonally wins the game. The game is a tie if nobody has won after the board is filled.
</P>
<P><FONT SIZE="+1"><B><I>Traditional AI Methods</I></B></FONT></P>
<P>Traditionally, there are two classes of methods for solving a problem such as playing Tic-Tac-Toe: (1) the brute force method or (2) some sort of heuristic search method.
</P>
<P>In solving such a search problem, the decision tree can be searched breadth first, expanding the game playing tree as far as possible, and examining each possible move and its merits. By looking ahead in this fashion, the ramification of each possible move can be examined using a minimax technique which involves computing a function value to evaluate possible solutions and assign a numerical value to each move according to player’s chance of winning the game. The higher the probability of winning the game as a result of making a particular move, the higher the evaluation function value assigned to that particular move. A computer program employing such a strategy would then select the move that results in the maximization of its own score while simultaneously minimizing its opponent’s score.</P>
<P>The problem with the aforementioned approach is that for many games, including tic-tac-toe, the search tree grows too big too quickly. The combinatorial explosion prohibits searching far enough down the decision tree for effective solutions.</P>
<P>As an alternative, any of a number of heuristic search rules can be used to eliminate branches of the search tree from consideration, to prune the tree. This is in effect a depth first search. Such an approach requires a lot of effort on the programmer’s part to carefully choose which branches to discard. For most problems, however, the breadth first search method is still used even though it is much less efficient.</P>
<P>A problem shared by both the breadth first and the depth first methods is the lack of robustness. Once a program is written to play a specific game, it requires a lot of work to change the evaluation function and the search methods to play a different game, even though it might be a slight variation of the original game. Thus, such a program is only as good as the evaluation function, and it does not learn from its mistakes to get any better.</P>
<P><FONT SIZE="+1"><B><I>GA and Game Playing</I></B></FONT></P>
<P>Genetic algorithms are search algorithms based on the principle of natural selection. For game playing, each string in a GA population can represent different strategies for playing the game. Initially, a fixed number of strings are generated randomly. Then, during the selection process, each strategy is required to play a certain number of games against other strategies. A win-loss record is kept for each strategy. The ones that perform badly are discarded while the strategies with the most wins are kept. After selection, crossover, and mutation are performed on those strings to create new strings which form the new population. After this process is repeated a number of times, the population pool will consist of strategies that are fit to survive (i.e., playing a good game of tic-tac-toe).
</P>
<P><FONT SIZE="+1"><B>GA IMPLEMENTATION</B></FONT></P>
<P><FONT SIZE="+1"><B><I>Configuration Encoding</I></B></FONT></P>
<P>To develop a strategy for the game of tic-tac-toe, there exists a desired move for each board configuration. The game of tic-tac-toe is played on a board of nine squares. Each square can either be marked by an “X,” an “O,” or a blank. The total number of possible configurations is 3<SUP>9</SUP> or 19683. Here, it is assumed that a ternary string of length nine is used to code each possible configuration. “0” is used to represent a blank, “1” is used to represent an “X,” and “2” is used to represent an “O.” For example, the following board could be represented as shown:</P>
<P><A NAME="Fig1"></A><A HREF="javascript:displayWindow('images/17-01.jpg',350,343)"><IMG SRC="images/17-01t.jpg"></A><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="321-323.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="325-328.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<hr width="90%" size="1" noshade>
<div align="center">
<font face="Verdana,sans-serif" size="1">Copyright © <a href="/reference/crc00001.html">CRC Press LLC</a></font>
</div>
<!-- all of the reference materials (books) have the footer and subfoot reveresed -->
<!-- reference_subfoot = footer -->
<!-- reference_footer = subfoot -->
</BODY>
</HTML>
<!-- END FOOTER -->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -