📄 331-337.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=331-337//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="328-330.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="337-338.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B>RESULTS</B></FONT></P>
<P>First, consider the on-line and off-line performance of the GA population. The on-line performance measures the average fitness of all individuals through the generations. The off-line performance is the average of the best individuals over generations. Since the GA is a stochastic method, it was run ten times to help dampen out any probabilistic errors. Figure 17.1 shows that the on-line performance starts out around 80, which is fairly weak (about 20 wins over 50 games). But then it starts improving rather quickly, up to 140 just after 30 generations, and increases all the way to 165 after 70 generations. After 100 generations, it is past 170 which is very good, considering the optimum is 200.
</P>
<P><A NAME="Fig5"></A><A HREF="javascript:displayWindow('images/17-05.jpg',550,389)"><IMG SRC="images/17-05t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-05.jpg',550,389)"><FONT COLOR="#000077"><B>Figure 17.1</B></FONT></A> On-line performance of the genetic algorithm.</P>
<P>Figure 17.2 is a plot of the off-line performance. The off-line performance starts out around 130, and begins to converge rather quickly. After 40 generations, it is around 180, and after 100 generations the off-line performance is almost 195. The best-ever string has a fitness value of 200, which means that it won every one of its games.
</P>
<P><A NAME="Fig6"></A><A HREF="javascript:displayWindow('images/17-06.jpg',550,390)"><IMG SRC="images/17-06t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-06.jpg',550,390)"><FONT COLOR="#000077"><B>Figure 17.2</B></FONT></A> Off-line performance of the genetic algorithm.</P>
<P>An issue that needs to be considered is random moves made by the GA. Recall that in the strings, an invalid move is replaced by a randomly generated move. This random move is then put back in the string. Figure 17.3 shows the percentage of moves that were made randomly over the generations. The GA starts out by making almost 20% of the moves randomly, but as generations progress, the percentage starts to drop. After 100 generations, the number of moves made randomly is only around 3%. This indicates that as the GA begins to play the games “better” (as shown on the performance graphs), the strings also rely less and less on random moves. This is a good example of exploration versus exploitation.
</P>
<P><A NAME="Fig7"></A><A HREF="javascript:displayWindow('images/17-07.jpg',550,392)"><IMG SRC="images/17-07t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-07.jpg',550,392)"><FONT COLOR="#000077"><B>Figure 17.3</B></FONT></A> Percentage of random moves made by the genetic algorithm.</P>
<P>The on-line and off-line performance plots might not tell the whole story. A few games were played with the strings in the GA that have top fitness values to see if they have really mastered the game as their fitness measures indicate. The results are documented in the next section.
</P>
<P><FONT SIZE="+1"><B><I>Sample Games</I></B></FONT></P>
<P><U>Game 1</U></P>
<P><A NAME="Fig8"></A><A HREF="javascript:displayWindow('images/17-08.jpg',300,596)"><IMG SRC="images/17-08t.jpg"></A></P>
<P>X wins the game. As one can see, X plays a very aggressive game (as the opening player should). X does not just make moves aimlessly, but it actually tries to set up its plays, the O player failed to make the right first move and X player took advantage of that.
</P>
<P><U>Game 2</U></P>
<P><A NAME="Fig9"></A><A HREF="javascript:displayWindow('images/17-09.jpg',300,640)"><IMG SRC="images/17-09t.jpg"></A></P>
<P>X wins the game. Again, X tried to set the human up and the human failed to make the right response for X’s opening move. There was no way the X player could have been prevented from winning the game after the first “O” move was selected.
</P>
<P><U>Game 3</U></P>
<P><A NAME="Fig10"></A><A HREF="javascript:displayWindow('images/17-10.jpg',300,601)"><IMG SRC="images/17-10t.jpg"></A></P>
<P>X wins the game. This time a different opening was used, but as before, the GA strategy indicates an attempt to set up its human counterpart.
</P>
<P><FONT SIZE="+1"><B><I>Execution Performance</I></B></FONT></P>
<P>One popular concern with GAs seems to be execution time. When an algorithm is computing the effectiveness of 100 possible solutions in each generation, and then being run for numerous generations, the number of possible solutions evaluated can become significant. Thus, it is important to consider the amount of computational time associated with determining a solution. The GA code the current effort was run on is a SUN SPARCstation 20. On average, each generation took approximately 3.8 seconds, so over 100 generations, the program ran for just under 8 minutes.
</P>
<P><FONT SIZE="+1"><B>CONCLUSION</B></FONT></P>
<P><FONT SIZE="+1"><B><I>Learning Classifier System</I></B></FONT></P>
<P>It turns out that the current effort is basically a simplified version of the “Pittsburgh” approach to the learning classifier system. The positions of the bits in the strings are the conditions. The actions are the contents of the strings. Here, all the possible states have been encoded into the strings. The selection process is basically a reward mechanism. Strings with good fitness values are allowed on to the next generation while the poorly fit strings are eliminated.
</P>
<P><FONT SIZE="+1"><B><I>GA Versus Traditional AI Approach</I></B></FONT></P>
<P>In the early version of the GA program, the GA was allowed to make all of the decisions regarding a game, even the simple obvious moves. This resulted in longer strings, 618 bits each. With strings this long, it took the GA a very long time to develop an effective strategy. Even after 500 generations, the results were still not suitable. After the program was modified to make simple decisions by making winning moves and preventing the opponent from winning, the string length was reduced to 104 bits. This reduced the number of generations significantly. Just after 100 generations, the GA was able to play the game at “expert” level. Therefore, by incorporating traditional AI search methods (simple searches that do not take a lot of computation power) into the GA, the program was much more effective. This lends credence to the old axiom: “If you have domain knowledge, then use it.”
</P>
<P>One of the most difficult problems in AI is the credit assignment and evaluation definition. To decide how much credit to assign to different situations is not a trivial task. Most of the time, to one extent or another, it is a trial and error process. By using GAs, the amount of work required for these problems seems to be substantially reduced. As seen from this effort, the GA does not replace the traditional AI search methods, rather, they complement each other.</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="328-330.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="337-338.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 + -