📄 325-328.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=325-328//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="323-325.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="328-330.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
</P>
<P><FONT SIZE="+1"><B><I>Initialization</I></B></FONT></P>
<P>First, all configurations possible within the game of tic-tac-toe must be determined. As this is obviously a time-consuming task, a computer program was written to find all valid configurations. For the “X” player, which is the player that goes first, the number of Xs and Os on the board at that time must be equal. Conversely, for the “O” player, there must be exactly one more X than the number of Os on the board. There are also a lot of configurations that are equivalent to each other. For example, there are configurations that have mirror images or transposes. These equivalent configurations must be determined to keep the length of the GA strings as short as possible.
</P>
<P>A computer program was written to find all possible configurations for the “X” player. These configurations were saved to a file. The file looks like the following table:</P>
<TABLE WIDTH="100%" BORDER><TR>
<TD WIDTH="30%">Config.
<TD WIDTH="10%">0
<TD WIDTH="10%">5
<TD WIDTH="10%">7
<TD WIDTH="10%">11
<TD WIDTH="10%">15
<TD WIDTH="10%">19
<TD WIDTH="10%">…
<TR>
<TD>Index
<TD>1
<TD>2
<TD>3
<TD>4
<TD>2
<TD>4
<TD>…
<TR>
<TD>Variation
<TD>0
<TD>0
<TD>0
<TD>0
<TD>1
<TD>2
<TD>…
</TABLE>
<P>The index is the position in the string in which that particular configuration is stored. Notice that configurations 1-4 were not in the table because they are invalid for the “X” player. Configurations 5 and 15 contain the same index which means that 5 and 15 are variants of the same configuration:
</P>
<P><A NAME="Fig2"></A><A HREF="javascript:displayWindow('images/17-02.jpg',500,248)"><IMG SRC="images/17-02t.jpg"></A></P>
<P>As can be seen from the above figure, configuration 15 is the same as configuration 5, it is just flipped horizontally. There is not need for an extra space in the string to represent 15. In the GA implementation, the table will be referred to in order to discern that configuration 15 is the same as configuration 2. This same situation exists for configuration 19; it is the same as configuration 11. Thus, both of them share the same index. The above table also has a “variation field” to depict how the configuration is related to the original. For example, let “0” denote that the configuration is the original, “1” denotes that the configuration is the original flipped horizontally, “2” denotes that it is the original flipped vertically, etc.
</P>
<P>After the aforementioned program was executed, it returned 612 indices, which means that there are 612 unique configurations for the “X” player.</P>
<P>Such a file was also created for the “O” player, which contains all the valid configurations and their indices.</P>
<P><FONT SIZE="+1"><B><I>String Representations</I></B></FONT></P>
<P>Since there are 612 different configurations and each configuration can have nine responses, a string of length 612 is needed if the alphabet 0 to 8 is to be used. Each bit will represent a move corresponding to that configuration index. Alternatively, a ternary alphabet of 0, 1 and 2 could be used, but this would double the length of the string to 1224.
</P>
<P>Using the first method:</P>
<TABLE WIDTH="100%" BORDER><TR>
<TD WIDTH="30%">Index
<TD WIDTH="10%">1
<TD WIDTH="10%">2
<TD WIDTH="10%">3
<TD WIDTH="10%">4
<TD WIDTH="10%">5
<TD WIDTH="10%">6
<TD WIDTH="10%">…
<TR>
<TD>Content
<TD>5
<TD>0
<TD>4
<TD>6
<TD>3
<TD>8
<TD>…
</TABLE>
<P>Using the second method:
</P>
<TABLE WIDTH="100%" BORDER><TR>
<TD WIDTH="30%">Index
<TD WIDTH="10%">1
<TD WIDTH="10%">3
<TD WIDTH="10%">5
<TD WIDTH="10%">7
<TD WIDTH="10%">9
<TD WIDTH="10%">11
<TD WIDTH="10%">…
<TR>
<TD>Content
<TD>12
<TD>00
<TD>10
<TD>20
<TD>10
<TD>21
<TD>…
</TABLE>
<P>Both strings represent the same strategy. In general, the GA works better with a smaller alphabet. Therefore, method number two is used here.
</P>
<P><FONT SIZE="+1"><B><I>String Decoding</I></B></FONT></P>
<P>To discuss the coding of the GA strings, consider the configuration table listed above. If, as the “X” player, the following board configuration is encountered:
</P>
<P><A NAME="Fig3"></A><A HREF="javascript:displayWindow('images/17-03.jpg',150,150)"><IMG SRC="images/17-03t.jpg"></A></P>
<P>This board is encoded as 000000012<SUB><SMALL>(base3)</SMALL></SUB> = 5<SUB><SMALL>(base 10)</SMALL></SUB>. By consulting the configuration table, the index of configuration 5 is determined to be 2. Next, the string at index 2 is used if the first method is being used, or the string at index 3 if the second method is being used. Since the second method is being used here, the result is 0. Thus, the mover for the first board is to place an “X” at board position 0. After “X” makes this move, the board will appear as follows:</P>
<P><A NAME="Fig4"></A><A HREF="javascript:displayWindow('images/17-04.jpg',150,150)"><IMG SRC="images/17-04t.jpg"></A></P>
<P>If the string suggests making a move at a position that is already occupied, say position 8 for the above example, then a randomly selected valid move is made, and the string is altered so that this move is captured in the genetic material. Of course, if it is a good move, then that string will thrive in future generations, whereas, if it is an ineffective move, then said string will die out of the population.
</P>
<P>When selecting a move, the variation field must also be consulted so as to make any translations necessary to reflect that variation.</P>
<P><FONT SIZE="+1"><B><I>String Length Reduction</I></B></FONT></P>
<P>Certainly, there is motivation for reducing the length of the strings on which a GA must operate; if nothing else, this reduces the size of the search space. In the current case, the strings could be as long as 1000 bits; this might not be such a good idea since the corresponding search space would contain 2<SUP><SMALL>1000</SMALL></SUP> points or possible solutions to the problem at hand. Basically, it would be extremely difficult and time consuming for any search method to traverse this space and ensure a quality solution had been found. Thus, it is worthwhile to consider mechanisms of reducing the string length. One way to reduce the length is to reduce the number of decisions that the strings must represent. Instead of having the GA make every decision, the problem could be structured so that the simple decisions are not represented by the strings; domain knowledge is included. For instance, there are at least two predicaments for which any effective player will make the correct decision almost 100% of the time. First, if a player can win the game by placing its mark on one of the squares during the next move, then return that move. Second, if the opponent can win the game by placing its mark on one the squares during the next move, then return that move.</P>
<P>By using those rules, the string length can be reduced because it become unnecessary to store situations that fit the above description in the strings. By doing so, the number of configurations can be reduced down to 104. This means that the string length is 208 when a ternary alphabet is employed.</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="323-325.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="328-330.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 + -