diff options
| author | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
|---|---|---|
| committer | elioat <elioat@tilde.institute> | 2023-08-23 07:52:19 -0400 |
| commit | 562a9a52d599d9a05f871404050968a5fd282640 (patch) | |
| tree | 7d3305c1252c043bfe246ccc7deff0056aa6b5ab /js/games/nluqo.github.io/~bh/v1ch6 | |
| parent | 5d012c6c011a9dedf7d0a098e456206244eb5a0f (diff) | |
| download | tour-562a9a52d599d9a05f871404050968a5fd282640.tar.gz | |
*
Diffstat (limited to 'js/games/nluqo.github.io/~bh/v1ch6')
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch6/ttt.html | 1409 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch6/ttt.lg | 198 | ||||
| -rw-r--r-- | js/games/nluqo.github.io/~bh/v1ch6/v1ch6.html | 1409 |
3 files changed, 3016 insertions, 0 deletions
diff --git a/js/games/nluqo.github.io/~bh/v1ch6/ttt.html b/js/games/nluqo.github.io/~bh/v1ch6/ttt.html new file mode 100644 index 0000000..0a86e07 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch6/ttt.html @@ -0,0 +1,1409 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 6: Example: Tic-Tac-Toe</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Example: Tic-Tac-Toe</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../csls1.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/v1ch06.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT +Press web page for Computer Science Logo Style</A> +</TABLE></TABLE> + +<HR> +<P>Program file for this chapter: <A HREF="ttt.lg"><CODE>ttt</CODE></A> + +<P>This chapter is the first application of the ideas we've explored to a +sizable project. The primary purpose of the chapter is to introduce +the techniques of <EM>planning</EM> a project, especially the choice of +how to organize the information needed by the program. This organization is +called the <EM>data structure</EM> of the program. Along the way, +we'll also see a new data type, the array, and a few other details of Logo +programming. + +<P><H2>The Project</H2> + +<P>Tic-tac-toe is not a very challenging game for human beings. If you're +an enthusiast, you've probably moved from the basic game to some variant +like three-dimensional tic-tac-toe on a larger grid. + +<P>If you sit down right now to play ordinary three-by-three tic-tac-toe +with a friend, what will probably happen is that every game will come +out a tie. Both you and your friend can probably play perfectly, +never making a mistake that would allow your opponent to win. + +<P>But can you <EM>describe</EM> how you know where to move each turn? +Most of the time, you probably aren't even aware of alternative possibilities; +you just look at the board and instantly know where you want to move. +That kind of instant knowledge is great for human beings, because +it makes you a fast player. But it isn't much help in writing a computer +program. For that, you have to know very explicitly what your strategy +is. + +<P>By the way, although the example of tic-tac-toe strategy is a relatively +trivial one, this issue of instant knowledge versus explicit rules is a hot +one in modern psychology. Some cognitive scientists, who think that human +intelligence works through mechanisms similar to computer programs, maintain +that when you know how to do something without knowing <EM>how</EM> you know, +you have an explicit set of rules deep down inside. It's just that the +rules have become a habit, so you don't think about them deliberately. +They're "compiled," in the jargon of cognitive psychology. On +the other hand, some people think that your implicit how-to knowledge is very +different from the sort of lists of rules that can be captured in a computer +program. They think that human thought is profoundly different from the way +computers work, and that a computer cannot be programmed to simulate the +full power of human problem-solving. These people would say, for example, +that when you look at a tic-tac-toe board you immediately grasp the +strategic situation as a whole, and your eye is drawn to the best move +without any need to examine alternatives according to a set of rules. (You +might like to try to be aware of your own mental processes as you play a +game of tic-tac-toe, to try to decide which of these points of view more +closely resembles your own experience--but on the other hand, the +psychological validity of such introspective evidence is <EM>another</EM> +hotly contested issue in psychology!) + +<P>»Before you read further, try to write down a set of strategy rules +that, if followed consistently, will never lose a game. Play a few +games using your rules. Make sure they work even if the other player +does something bizarre. + +<P>I'm going to number the squares in the tic-tac-toe +board this way: + +<P> +<TABLE rules="all" frame="void" border="2" noshade><TR><TD align="center" height=30 width=30>1<TD align="center" height=30 width=30>2<TD align="center" height=30 width=30>3<TR><TD align="center" height=30 width=30>4<TD align="center" height=30 width=30>5<TD align="center" height=30 width=30>6<TR><TD align="center" height=30 width=30>7<TD align="center" height=30 width=30>8<TD align="center" height=30 width=30>9</TABLE> + +<P>Squares 1, 3, 7, and 9 are <EM>corner squares</EM>. I'll call +2, 4, 6, and 8 <EM>edge squares</EM>. And of course number 5 is the +<EM>center square</EM>. I'll use the word <EM>position</EM> to mean +a specific partly-filled-in board with X and O in certain squares, and +other squares empty. + +<P>One way you might meet my challenge of describing your strategy explicitly +is to list all the possible sequences of moves up to a certain point +in the game, then say what move you'd make next in each situation. +How big would the list have to be? There are nine possibilities for +the first move. For each first move, there are eight possibilities +for the second move. If you continue this line of reasoning, you'll +see that there are nine factorial, or 362880, possible sequences of +moves. Your computer may not have enough memory to list +them all, and you certainly don't have enough patience! + +<P>Fortunately, not all these sequences are interesting. Suppose you +are describing the rules a computer should use against a human player, +and suppose the human being moves first. Then there are, indeed, +nine possible first moves. But for each of these, there is only <EM> +one</EM> possible computer move! After all, we're programming the computer. +We get to decide which move it will choose. Then there are seven +possible responses by the opponent, and so on. The number of sequences +when the human being plays first is 9 times 7 times 5 times 3, or +945. If the computer plays first, it will presumably always make +the single best choice. Then there are eight possible responses, +and so on. In this case the number of possible game sequences is +8 times 6 times 4 times 2, or 384. Altogether we have 1329 cases +to worry about, which is much better than 300,000 but still not an +enjoyable way to write a computer program. + +<P>In fact, though, this number is still too big. Not all games go for +a full nine moves before someone wins. Also, many moves force the +opponent to a single possible response, even though there are other +vacant squares on the board. Another reduction can be achieved by +taking advantage of <EM>symmetry</EM>. For example, if X starts in square +5, any game sequence in which O responds in square 1 is equivalent +to a sequence in which O responds in square 3, with the board rotated +90 degrees. In fact there are only two truly different responses +to a center-square opening: any corner square, or any edge square. + +<P>With all of these factors reducing the number of distinct positions, +it would probably be possible to list all of them and write +a strategy program that way. I'm not sure, though, because I didn't +want to use that technique. I was looking for rules expressed in +more general terms, like "all else being equal, pick a corner rather +than an edge." + +<P>Why should I prefer a corner? Each corner square is part of three +winning combinations. For example, square 1 is part of <CODE>123</CODE>, +<CODE>147</CODE>, and <CODE>159</CODE>. (By expressing these winning combinations as +three-digit numbers, I've jumped ahead a bit in the story with a preview of how +the program I wrote represents this information.) An edge square, +on the other hand, is only part of two winning combinations. For +example, square 2 is part of <CODE>123</CODE> and <CODE>258</CODE>. Taking a corner +square makes three winning combinations available to me and unavailable +to my opponent. + +<P>Since I've brought up the subject of winning combinations, how many +of <EM>them</EM> are there? Not very many: three horizontal, three vertical, +and two diagonal. Eight altogether. That <EM>is</EM> a reasonable amount +of information to include in a program, and in fact there is a list +of the eight winning combinations in this project. + +<P>You might, at this point, enjoy playing a few games with the program, +to see if you can figure out the rules it uses in its strategy. If +you accepted my earlier challenge to write down your own set of strategy +rules, you can compare mine to yours. Are they the same? If not, +are they equally good? + +<P>The top-level procedure in this project is called <CODE>ttt</CODE>. It takes no +inputs. When you invoke this procedure, it will ask you if you'd +like to play first (X) or second (O). Then you enter moves by typing +a digit 1-9 for the square you select. The program draws the game +board on the Logo graphics screen. + +<P>I'm about to start explaining my strategy rules, so stop reading if +you want to work out your own and haven't done it yet. + +<P><H2>Strategy</H2> + +<P>The highest-priority and the lowest-priority rules seemed obvious +to me right away. The highest-priority are these: + +<P> + +<P><TABLE><TR><TH>1. <TD>If I can win on this move, do it. +<TR><TH>2. <TD>If the other player can win on the next move, block that winning +square. +</TABLE> + +<P>Here are the lowest-priority rules, used only if there is +nothing suggested more strongly by the board position: + +<P><TABLE><TR><TH><EM>n</EM>-2. <TD>Take the center square if it's free. +<TR><TH><EM>n</EM>-1. <TD>Take a corner square if one is free. +<TR><TH><EM>n</EM>. <TD>Take whatever is available. +</TABLE> + +<P>The highest priority rules are the ones dealing with the +most urgent situations: either I or my opponent can win on the next +move. The lowest priority ones deal with the least urgent situations, +in which there is nothing special about the moves already made to +guide me. + +<P>What was harder was to find the rules in between. I knew that the +goal of my own tic-tac-toe strategy was to set up a <EM>fork</EM>, a +board position in which I have two winning moves, so my opponent can +only block one of them. Here is an example: + +<P> <TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> + +<P>X can win by playing in square 3 or square 4. It's O's +turn, but poor O can only block one of those squares at a time. Whichever +O picks, X will then win by picking the other one. + +<P>Given this concept of forking, I decided to use it as the next highest +priority rule: + +<P><TABLE><TR><TH>3. <TD>If I can make a move that will set up a fork for myself, do it. +</TABLE> + +<P>That was the end of the easy part. My first attempt at +writing the program used only these six rules. Unfortunately, it +lost in many different situations. I needed to add something, but +I had trouble finding a good rule to add. + +<P>My first idea was that rule 4 should be the defensive equivalent of +rule 3, just as rule 2 is the defensive equivalent of rule 1: + +<P><TABLE><TR><TH>4a. <TD>If, on the next move, my opponent can set up a fork, block that +possibility by moving into the square that is common to his two winning +combinations. +</TABLE> + +<P>In other words, apply the same search technique to the opponent's +position that I applied to my own. + +<P>This strategy works well in many cases, but not all. For example, +here is a sequence of moves under this strategy, with the human player +moving first: + +<P><PRE><TABLE><TR> +<TD width=150 align="center" valign="bottom"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30><TD align="center" height=30 width=30> <TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30>x<TD align="center" height=30 width=30> <TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>In the fourth grid, the computer (playing O) has discovered +that X can set up a fork by moving in square 6, between the winning +combinations <CODE>456</CODE> and <CODE>369</CODE>. The computer moves to block this +fork. Unfortunately, X can also set up a fork by moving in squares +3, 7, or 8. The computer's move in square 6 has blocked one combination +of the square-3 fork, but X can still set up the other two. In the +fifth grid, X has moved in square 8. This sets up the winning combinations +<CODE>258</CODE> and <CODE>789</CODE>. The computer can only block one of these, and +X will win on the next move. + +<P>Since X has so many forks available, does this mean that the game +was already hopeless before O moved in square 6? No. Here is something +O could have done: + +<P><PRE><TABLE><TR> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>In this sequence, the computer's second move is in square +7. This move also blocks a fork, but it wasn't chosen for that reason. +Instead, it was chosen <EM>to force X's next move</EM>. In the fifth +grid, X has had to move in square 4, to prevent an immediate win by +O. The advantage of this situation for O is that square 4 was <EM> +not</EM> one of the ones with which X could set up a fork. O's next move, +in the sixth grid, is also forced. But by then the board is too crowded +for either player to force a win; the game ends in a tie, as usual. + +<P>This analysis suggests a different choice for an intermediate-level +strategy rule, taking the offensive: + +<P><TABLE><TR><TH>4b. <TD>If I can make a move that will set up a winning combination +for myself, do it. +</TABLE> + +<P>Compared to my earlier try, this rule has the benefit of +simplicity. It's much easier for the program to look for a single +winning combination than for a fork, which is two such combinations +with a common square. + +<P>Unfortunately, this simple rule isn't quite good enough. In the example +just above, the computer found the winning combination <CODE>147</CODE> in +which it already had square 1, and the other two were free. But why +should it choose to move in square 7 rather than square 4? If the +program did choose square 4, then X's move would still be forced, +into square 7. We would then have forced X into creating a fork, +which would defeat the program on the next move. + +<P>It seems that there is no choice but to combine the ideas from rules +4a and 4b: + +<P><TABLE><TR><TH>4b. <TD>If I can make a move that will set up a winning combination +for myself, do it. But ensure that this move does not force the opponent +into establishing a fork. +</TABLE> + +<P>What this means is that we are looking for a winning combination +in which the computer already owns one square and the other two are empty. +Having found such a combination, we can move in either of its empty squares. +Whichever we choose, the opponent will be forced to choose the other one +on the next move. If one of the two empty squares would create a fork for +the opponent, then the computer must choose that square and leave the other +for the opponent. + +<P>What if <EM>both</EM> of the empty squares in the combination we find +would make forks for the opponent? In that case, we've chosen a bad +winning combination. It turns out that there is only one situation +in which this can happen: + +<P><PRE><TABLE><TR> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>Again, the computer is playing O. After the third grid, +it is looking for a possible winning combination for itself. There +are three possibilities: <CODE>258</CODE>, <CODE>357</CODE>, and <CODE>456</CODE>. +So far we +have not given the computer any reason to prefer one over another. +But here is what happens if the program happens to choose <CODE>357</CODE>: + +<P><PRE><TABLE><TR> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>By this choice, the computer has forced its opponent into +a fork that will win the game for the opponent. +If the computer chooses either of the other two possible winning combinations, +the game ends in a tie. (All moves after this choice turn out to +be forced.) + +<P>This particular game sequence was very troublesome for me because +it goes against most of the rules I had chosen earlier. For one thing, +the correct choice for the program is any edge square, while the corner +squares must be avoided. This is the opposite of the usual priority. + +<P>Another point is that this situation contradicts rule 4a (prevent +forks for the other player) even more sharply than the example we +considered earlier. In that example, rule 4a wasn't enough +guidance to ensure a correct choice, but the correct choice was at +least <EM>consistent</EM> with the rule. That is, just blocking a fork +isn't enough, but threatening a win and <EM>also</EM> blocking a fork +is better than just threatening a win alone. This is the meaning +of rule 4. But in this new situation, the corner square (the move +we have to avoid) <EM>does</EM> block a fork, while the edge square (the +correct move) <EM>doesn't</EM> block a fork! + +<P>When I discovered this anomalous case, I was ready to give up on the +idea of beautiful, general rules. I almost decided to build into +the program a special check for this precise board configuration. +That would have been pretty ugly, I think. But a shift in viewpoint +makes this case easier to understand: What the program must do is +force the other player's move, and force it in a way that helps the +computer win. If one possible winning combination doesn't allow us to +meet these conditions, the program should try another combination. +My mistake was to think either about forcing alone (rule 4b) or about +the opponent's forks alone (rule 4a). + +<P>As it turns out, the board situation we've been considering is the only +one in which a possible winning combination could include two possible +forks for the opponent. What's more, in this board situation, it's a +diagonal combination that gets us in trouble, while a horizontal or +vertical combination is always okay. Therefore, I was able to implement +rule 4 in a way that only considers one possible winning combination by +setting up the program's data structures so that diagonal combinations +are the last to be chosen. This trick makes the program's design less +than obvious from reading the actual program, but it does save the program +some effort. + +<P><H2>Program Structure and Modularity</H2> + + +<P>Most game programs--in fact, most interactive programs of any +kind--consist of an initialization section followed by a sequence +of steps carried out repeatedly. In the case of the tic-tac-toe game, +the overall program structure will be something like this: + +<P><PRE>to ttt +initialize +forever [ + if <EM>game.is.over</EM> [stop] + <EM>record.human.move get.human.move</EM> + if <EM>game.is.over</EM> [stop] + <EM>record.program.move compute.program.move</EM> +] +end +</PRE> + +<P>The parts of this structure shown in <CODE><EM>italics</EM></CODE> are +just vague ideas. At this point in the planning, I don't know what inputs +these procedures might need, for example. In fact, there may not be +procedures exactly like this in the final program. One example is that +the test that I've called <CODE><EM>game.is.over</EM></CODE> here will actually +turn out to be two separate tests <CODE>already.wonp</CODE> and <CODE>tiedp</CODE> (using +a final letter <CODE>p</CODE> to indicate a predicate, following the convention +established by the Logo primitive predicates). + +<P>This half-written procedure introduces a Logo primitive we haven't used +before: <CODE>forever</CODE>. It takes a list of Logo instructions as its +input, and carries out those instructions repeatedly, much as <CODE>repeat</CODE>, +<CODE>for</CODE>, and <CODE>foreach</CODE> do. But the number of repetitions is unlimited; +the repetition stops only if, as in this example, the primitive <CODE>stop</CODE> or +<CODE>output</CODE> is invoked within the repeated instructions. <CODE>Forever</CODE> is +useful when the ending condition can't be predicted in advance, as in a game +situation in which a player might win at any time. + +<P>It may not be obvious why I've planned for one procedure to figure out the +next move and a separate procedure to record it. (There are two such pairs +of procedures, one for the program's moves and the other for the human +opponent's moves.) For one thing, I expect that the recording of moves +will be much the same whether it's the program or the person moving, while +the decision about where to move will be quite different in the two cases. +For the program's move we must apply strategy rules; for the human player's +moves we simply ask the player. Also, I anticipate that the selection of +the program's moves, which will be the hardest part of the program, can be +written in functional style. The strategy procedure is a function that takes +the current board position as its input, always returning the same chosen +square for any given input position. + +<P>This project contains 28 procedures. These procedures can be divided into +related groups like this: + +<P><TABLE> +<TR><TD>7<TD>overall orchestration +<TR><TD>6<TD>initialization +<TR><TD>2<TD>get opponent's moves +<TR><TD>9<TD>compute program's moves +<TR><TD>4<TD>draw moves on screen +</TABLE> + +<P>As you might expect, figuring out the computer's strategy +is the most complex part of the program's job. But this strategic +task is still only about a third of the complete program. + +<P>The five groups are quite cleanly distinguishable in this project. There are +relatively few procedure invocations between groups, compared to the number +within a group. It's easy to read the procedures within a group and +understand how they work without having to think about other parts of the +program at the same time. + +<P> +The following diagram shows the subprocedure/superprocedure relationships +within the program, and indicates which procedures are in each of the five +groups listed above. Some people find diagrams like this one very helpful in +understanding the structure of a program. Other people don't like these +diagrams at all. If you find it helpful, you may want to draw such diagrams +for your own projects. + +<P> + +<CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch6/tttflow.gif" ALT="figure: tttflow"></CENTER> + + + +<P>In the diagram, I've circled the names of seven procedures. If you +understand the purpose of each of these, then you will understand +the general structure of the entire program. (Don't turn to the end and +read the actual procedures just now. Instead, see if +you can understand the following paragraphs just from the diagram.) + +<P><CODE>Ttt</CODE> is the top-level procedure for which I gave a rough outline +earlier. It calls initialization procedures (<CODE>draw.board</CODE> and <CODE> +init</CODE>) to set up the game, then repeatedly alternates between the human +opponent's moves and the program's moves. It calls <CODE>getmove</CODE> to find +out the next move by the opponent, <CODE>youplay</CODE> to record that move, +then <CODE>pickmove</CODE> to compute the program's next move and <CODE>meplay</CODE> +to record it. + +<P><CODE>Make.triples</CODE> translates from one representation of the board +position to another. The representation used within <CODE>ttt</CODE> is best +suited for display and for user interaction, while the representation +output by <CODE>make.triples</CODE> is best for computing the program's strategy. +We'll look into data representation more closely later. + +<P><CODE>Getmove</CODE> invites the opponent to type in a move. It ensures that +the selected move is legal before accepting it. The output from <CODE> +getmove</CODE> is a number from 1 to 9 representing the chosen square. + +<P><CODE>Pickmove</CODE> figures out the program's next move. It is the "smartest" +procedure in the program, embodying the strategy rules I listed earlier. +It, too, outputs a number from 1 to 9. + +<P><CODE>Youplay</CODE> and <CODE>meplay</CODE> are simple procedures that actually carry out +the moves chosen by the human player and by the program, respectively. +Each contains only two instructions. The first invokes <CODE>draw</CODE> to draw +the move on the screen. The second modifies the <CODE>position</CODE> array +to remember that the move has been made. + +<P><CODE>Draw</CODE> moves the turtle to the chosen square on the tic-tac-toe board. +Then it draws either an X or an O. (We haven't really talked about Logo's +turtle graphics yet. If you're not familiar with turtle graphics from +earlier Logo experience, you can just take this part of the program on faith; +there's nothing very interesting about it.) + +<P>Notice, in the diagram, that the lines representing procedure calls +come into a box only at the top. This is one sign of a well-organized +program: The dashed boxes in the diagram truly do represent distinct +parts of the program that don't interact very much. + +<P><H2>Data Representation</H2> + +<P>I've written several tic-tac-toe programs, in different programming +languages. This experience has really taught me about the importance of +picking a good data representation. For my first tic-tac-toe +program, several years ago, I decided without much prior thought that a +board position should be represented as three lists of numbers, one with X's +squares, one with O's squares, and one with the free squares. So this board +position + +<P><PRE> +<TABLE rules="all" frame="void" border="2"> +<TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> +</PRE> + +<P>could be represented like this: + +<P><PRE>make "xsquares [1 4 5] +make "osquares [2 9] +make "free [3 6 7 8] +</PRE> + +<P>These three variables would change in value as squares moved +from <CODE>:free</CODE> to one of the others. This representation was easy +to understand, but not very helpful for writing the program! + +<P>What questions does a tic-tac-toe program have to answer about the board +position? If, for example, the program wants to print a display of the +position, it must answer questions of the form "Who's in square 4?" +With the representation shown here, that's not as easy a question as we +might wish: + +<P><PRE>to occupant :square ;; old program +if memberp :square :xsquares [output "x] +if memberp :square :osquares [output "o] +output "free +end +</PRE> + +<P> +<P>On the other hand, this representation isn't so bad when we're +accepting a move from the human player and want to make sure it's a legal +move: + +<P><PRE>to freep :square ;; old program +output memberp :square :free +end +</PRE> + +<P>Along with this representation of the board, my first program used +a constant list of winning combinations: + +<P><PRE>make "wins [[1 2 3] [4 5 6] [7 8 9] [1 4 7] [2 5 8] + [3 6 9] [1 5 9] [3 5 7]] +</PRE> + +<P>It also had a list of all possible forks. I won't bother +trying to reproduce this very long list for you, since it's not used +in the current program, but the fork set up by X in the +board position just above was represented this way: + +<P><PRE>[4 [1 7] [5 6]] +</PRE> + +<P>This indicates that square 4 is the pivot of a fork between +the winning combinations <CODE>[1 4 7]</CODE> and <CODE>[4 5 6]</CODE>. Each member of the +complete list of forks was a list like this sample. The list of forks +was fairly long. Each edge square is the pivot of a fork. Each corner +square is the pivot of three forks. The center square is the pivot +of six forks. This adds up to 22 forks altogether. + +<P>Each time the program wanted to choose a move, it would first check +all eight possible winning combinations to see if two of the squares +were occupied by the program and the third one free. Since any of +the three squares might be the free one, this is a fairly tricky program +in itself: + +<P><PRE>to checkwin :candidate :mysquares :free ;; old program +if memberp first :candidate :free ~ + [output check1 butfirst :candidate :mysquares] +if memberp last :candidate :free ~ + [output check1 butlast :candidate :mysquares] +if memberp first butfirst :candidate :free ~ + [output check1 list first :candidate last :candidate :mysquares] +output "false +end + +to check1 :sublist :mysquares ;; old program +output and (memberp first :sublist :mysquares) ~ + (memberp last :sublist :mysquares) +end +</PRE> + +<P>This procedure was fairly slow, especially when invoked +eight times, once for each possible win. But the procedure to check +each of the possible forks was even worse! + +<P>In the program that I wrote for the first edition of <EM>Computer Science +Logo Style,</EM> a very different approach is used. This approach is based on +the realization that, at any moment, a particular winning combination may be +free for anyone (all three squares free), available only to one player, or +not available to anyone. It's silly for the program to go on checking a +combination that can't possibly be available. Instead of a single list of +wins, the new program has three lists: + +<P> +<TABLE> +<TR><TD><CODE>mywins</CODE><TD width=30><TD>wins available to the computer +<TR><TD><CODE>yourwins</CODE><TD width=30><TD>wins available to the opponent +<TR><TD><CODE>freewins</CODE><TD width=30><TD>wins available to anyone +</TABLE> + +<P>Once I decided to organize the winning combinations in this form, +another advantage became apparent: for each possible winning combination, +the program need only remember the squares that are free, not the +ones that are occupied. For example, the board position shown above +would contain these winning combinations, supposing the computer is +playing X: + +<P><PRE>make "mywins [[7] [6] [3 7]] +make "yourwins [[3 6] [7 8]] +make "freewins [] +</PRE> + +<P>The sublist <CODE>[7]</CODE> of <CODE>:mywins</CODE> indicates that the computer can +win simply by filling square 7. This list represents the winning +combination that was originally represented as <CODE>[1 4 7]</CODE>, but since +the computer already occupies squares 1 and 4 there is no need to +remember those numbers. + +<P>The process of checking for an immediate win is streamlined with this +representation for two reasons, compared with the <CODE>checkwin</CODE> procedure +above. First, only those combinations in <CODE>:mywins</CODE> must +be checked, instead of all eight every time. Second, an immediate +win can be recognized very simply, because it is just a list with +one member, like <CODE>[7]</CODE> and <CODE>[6]</CODE> in the example above. The procedure +<CODE>single</CODE> looks for such a list: + +<P><PRE>to single :list ;; old program +output find [equalp (count ?) 1] :list +end +</PRE> + +<P>The input to <CODE>single</CODE> is either <CODE>:mywins</CODE>, to find a winning +move for the computer (rule 1), or <CODE>:yourwins</CODE>, to find and block a +winning move for the opponent (rule 2). + +<P>Although this representation streamlines the strategy computation (the +<CODE>pickmove</CODE> part of the program), it makes the recording of a move +quite difficult, because combinations must be moved from one list to +another. That part of the program was quite intricate and hard to +understand. + +<P><H2>Arrays</H2> + +<P>This new program uses <EM>two</EM> representations, one for the interactive +part of the program and one for the strategy computation. The first of these +is simply a collection of nine words, one per square, each of which is the +letter X, the letter O, or the number of the square. With this +representation, recording a move means changing one of the nine words. +It would be possible to keep the nine words in a list, and compute a new +list (only slightly different) after each move. But Logo provides another +data type, the <EM>array,</EM> which allows for changing one member +while keeping the rest unchanged. + +<P>If arrays allow for easy modification and lists don't, why not always use +arrays? Why did I begin the book with lists? The answer is that each +data type has advantages and disadvantages. The main disadvantage of an +array is that you must decide in advance how big it will be; there aren't +any constructors like <CODE>sentence</CODE> to lengthen an array. + +<P>In this case, the fixed length of an array is no problem, because a +tic-tac-toe board has nine squares. The <CODE>init</CODE> procedure creates +the position array with the instruction + +<P><PRE>make "position {1 2 3 4 5 6 7 8 9} +</PRE> + +<P>The braces <CODE>{} +</CODE> indicate an array in the same +way that brackets indicate a list. + +<P>If player X moves in square 7, we can record that information +by saying + +<P><PRE><CODE>setitem</CODE> 7 :position "x +</PRE> + +<P>(Of course, the actual instruction in procedures <CODE>meplay</CODE> and +<CODE>youplay</CODE> uses variables instead of the specific values 7 and X.) +<CODE>Setitem</CODE> is a command with three inputs: a number indicating which +member of the array to change, the array itself, and the new value for +the specified member. + +<P>To find out who owns a particular square, we could write this procedure: + +<P><PRE>to occupant :square +output <CODE>item</CODE> :square :position +end +</PRE> + +<P>(The <CODE>item</CODE> operation can select a member of an array just as +it can select a member of a list or of a word.) In fact, though, it turns +out that I don't have an <CODE>occupant</CODE> procedure in this program. But the +parts of the program that examine the board position do use <CODE>item</CODE> in a +similar way, as in this example: + +<P><PRE>to freep :square +output numberp item :square :position +end +</PRE> + +<P>To create an array without explicitly listing all of its members, use the +operation <CODE>array</CODE>. It takes a number as argument, indicating how many +members the array should have. It returns an array of the chosen size, in +which each member is the empty list. Your program can then use <CODE>setitem</CODE> +to assign different values to the members. + +<P>The only primitive operation to select a member of an array is <CODE>item</CODE>. +Word-and-list operations such as <CODE>butfirst</CODE> can't be used with arrays. +There are operations <CODE>arraytolist</CODE> and <CODE>listtoarray</CODE> to convert +a collection of information from one data type to the other. + +<P><H2>Triples</H2> + +<P>The position array works well as a long-term representation for the board +position, because it's easy to update; it also works well for interaction +with the human player, because it's easy to find out the status of a +particular square. But for computing the program's moves, we need a +representation that makes it easy to ask questions such as "Is there a +winning combination for my opponent on the next move?" That's why, in +the first edition of these books, I used the representation with three +lists of possible winning combinations. + +<P>When MatthewWright and I wrote the book <EM>Simply Scheme,</EM> we +decided that the general idea of combinations was a good one, but the three +lists made the program more complicated than necessary. Since there are +only eight possible winning combinations in the first place, it's not so +slow to keep one list of all of them, and use that list as the basis for +all the questions we ask in working out the program's strategy. If the +current board position is + +<P><PRE> +<TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> +</PRE> + +<P>we represent the three horizontal winning combinations with +the words <CODE>xo3</CODE>, <CODE>xx6</CODE>, and <CODE>78o</CODE>. Each combination is +represented as a three-"letter" word containing an <CODE>x</CODE> or an <CODE>o</CODE> +for an occupied square, or the square's number for a free square. By +using words instead of lists for the combinations, we make the entire +set of combinations more compact and easier to read. Each of these words +is called a <EM>triple.</EM> The job of procedure <CODE>make.triples</CODE> is +to combine the information in the position array with a list of the eight +winning combinations: + +<P><PRE>? <U>show make.triples</U> +[xo3 xx6 78o xx7 ox8 36o xxo 3x7] +</PRE> + +<P><CODE>Make.triples</CODE> takes no inputs because the list of possible +winning combinations is built into it, and the position array is in <CODE> +ttt</CODE>'s local variable <CODE>position</CODE>: + +<P><PRE>to make.triples +output map "substitute.triple [123 456 789 147 258 369 159 357] +end + +to substitute.triple :combination +output map [item ? :position] :combination +end +</PRE> + +<P>This short subprogram will repay careful attention. It uses +<CODE>map</CODE> twice, once in <CODE>make.triples</CODE> to compute a function of +each possible winning combination, and once in <CODE>substitute.triple</CODE> to +compute a function of each square in a given combination. (That latter +function is the one that looks up the square in the array <CODE>:position</CODE>.) + +<P>Once the program can make the list of triples, we can use that to answer +many questions about the status of the game. For example, in the top-level +<CODE>ttt</CODE> procedure we must check on each move whether or not a certain +player has already won the game. Here's how: + +<P><PRE>to already.wonp :player +output memberp (word :player :player :player) (make.triples) +end +</PRE> + +<P>If we had only the <CODE>position</CODE> array to work with, it would be +complicated to check all the possible winning combinations. But once we've +made the list of triples, we can just ask whether the word <CODE>xxx</CODE> or the +word <CODE>ooo</CODE> appears in that list. + +<P>Here is the actual top-level procedure definition: + +<P><PRE>to ttt +local [me you position] +draw.board +init +if equalp :me "x [meplay 5] +forever [ + if already.wonp :me [print [I win!] stop] + if tiedp [print [Tie game!] stop] + youplay getmove ;; ask person for move + if already.wonp :you [print [You win!] stop] + if tiedp [print [Tie game!] stop] + meplay pickmove make.triples ;; compute program's move +] +end +</PRE> + +<P>Notice that <CODE>position</CODE> is declared as a local variable. +Because of Logo's dynamic scope, all of the subprocedures in this project +can use <CODE>position</CODE> as if it were a global variable, but Logo will +"clean up" after the game is over. + +<P>Two more such quasi-global variables are used to remember whether the +computer or the human opponent plays first. The value of <CODE>me</CODE> will be +either the word <CODE>x</CODE> or the word <CODE>o</CODE>, whichever letter the program +itself is playing. Similarly, the value of <CODE>you</CODE> will be <CODE>x</CODE> or +<CODE>o</CODE> to indicate the letter used by the opponent. All of these variables +are given their values by the initialization procedure <CODE>init</CODE>. + +<P>This information could have been kept in the form of a single +<EM>flag variable,</EM> called something like <CODE>mefirst</CODE>, that would +contain the word <CODE>true</CODE> if the computer is X, or <CODE>false</CODE> if the +computer is O. (A flag variable is one whose value is always <CODE> +true</CODE> or <CODE>false</CODE>, just as a predicate is a procedure whose output is +<CODE>true</CODE> or <CODE>false</CODE>.) It would be used something like this: + +<P><PRE>if :mefirst [draw "x :square] [draw "o :square] +</PRE> + +<P>But it turned out to be simpler to use two variables and +just say + +<P><PRE>draw :me :square +</PRE> + +<P> +<P>One detail in the final program that wasn't in my first rough draft is the +instruction + +<P><PRE>if equalp :me "x [meplay 5] +</PRE> + +<P>just before the <CODE>forever</CODE> loop. It was easier to write the +loop so that it always gets the human opponent's move first, and then +computes a move for the program, rather than having two different loops +depending on which player goes first. If the program moves first, its +strategy rules would tell it to choose the center square, because there is +nothing better to do when the board is empty. By checking for that case +before the loop, we are ready to begin the loop with the opponent as the +next to move. + +<P><H2>Variables in the Workspace</H2> + + +<P>There are nine global variables that are part +of the workspace, entered directly with top-level <CODE>make</CODE> instructions +rather than set up by <CODE>init</CODE>, because their +values are never changed. Their names are <CODE>box1</CODE> through <CODE> +box9</CODE>, and their values are the coordinates on the graphics screen of +the center of each square. For example, <CODE>:box1</CODE> is <CODE> +[-40 50]</CODE>. These variables are used by <CODE>move</CODE>, a subprocedure of +<CODE>draw</CODE>, to know where to position the turtle before drawing an X +or an O. + +<P>The use of variables loaded with a workspace file, rather than given values +by an initialization procedure, is a practice that Logo encourages in some +ways and discourages in others. Loading variables in a workspace file makes +the program start up faster, because it decreases the amount of +initialization required. On the other hand, variables are sort of +second-class citizens in workspace files. In many versions of Logo the <CODE> +load</CODE> command lists the names of the procedures in the workspace file, but +not the names of the variables. Similarly, <CODE>save</CODE> often reports the +number of procedures saved, but not the number of variables. It's easy to +create global variables and forget that they're there. + +<P>Certainly preloading variables makes sense only if the variables are really +constants; in other words, a variable whose value may change during the +running of a program should be initialized explicitly when the program +starts. Otherwise, the program will probably give incorrect results if you +run it a second time. (One of the good ideas in the programming language +Pascal is that there is a sort of thing in the language called a <EM> +constant</EM>; it has a name and a value, like a variable, but you can't give +it a new value in mid-program. In Logo, you use a global variable to hold a +constant, and simply refrain from changing its value. But being able to +<EM>say</EM> that something is a constant makes the program easier to +understand.) + +<P>One reason the use of preloaded variables is sometimes questioned as a point +of style is that when people are sloppy in their use of global variables, +it's hard to know which are really meant to be preloaded and which are just +left over from running the program. That is, if you write a program, test +it by running it, and then save it on a diskette, any global variables that +were created during the program execution will still be in the workspace +when you load that diskette file later. If there are five +intentionally-loaded variables along with 20 leftovers, it's particularly +hard for someone to understand which are which. This is one more reason not +to use global variables when what you really want are variables local to the +top-level procedure. + +<P><H2>The User Interface</H2> + +<P>The only part of the program that really interacts with the human user is +<CODE>getmove</CODE>, the procedure that asks the user where to move. + +<P><PRE>to getmove +local "square +forever [ + type [Your move:] + make "square readchar + print :square + if numberp :square + [if and (:square > 0) (:square < 10) + [if freep :square [output :square]]] + print [not a valid move.] +] +end +</PRE> + +<P>There are two noteworthy things about this part of the program. One is that +I've chosen to use <CODE>readchar</CODE> to read what the player types. This +primitive operation, with no inputs, waits for the user to type any single +character on the keyboard, and outputs whatever character the user types. +This "character at a time" interaction is in contrast with the more usual +"line at a time" typing, in which you can type characters, erase some if +you make a mistake, and finally use the RETURN or ENTER key to indicate that +the entire line you've typed should be made available to your program. +(In Chapter 1 you met Logo's <CODE>readlist</CODE> primitive for line at a +time typing.) Notice that if tic-tac-toe had ten or more squares in its +board I wouldn't have been able to make this choice, because the program +would have to allow the entry of two-digit numbers. + +<P><CODE>Readchar</CODE> was meant for fast-action programs such as video games. +It therefore does not display (or <EM>echo</EM>) the character that you type +on the computer screen. That's why <CODE>getmove</CODE> includes a <CODE>print</CODE> +instruction to let the user see what she or he has typed! + +<P>The second point to note in <CODE>getmove</CODE> is how careful it is to allow for +the possibility of a user error. Ordinarily, when one procedure uses a +value that was computed by another procedure, the programmer can assume that +the value is a legitimate one for the intended purpose. For example, when +you invoke a procedure that computes a number, you assume that you can add +the output to another number; you don't first use the <CODE>number?</CODE> +predicate to double-check that the result was indeed a number. But in +<CODE>getmove</CODE> we are dealing with a value that was typed by a human being, +and human beings are notoriously error-prone! The user is <EM>supposed</EM> +to type a number between 1 and 9. But perhaps someone's finger might slip +and type a zero instead of a nine, or even some character that isn't a +number at all. Therefore, <CODE>getmove</CODE> first checks that what the user +typed is a number. If so, it then checks that the number is in the allowed +range. (We'd get a Logo error message if <CODE>getmove</CODE> used the <CODE> +<</CODE> operation with a non-numeric input.) Only if these conditions are met +do we use the user's number as the square-selecting input to <CODE>freep</CODE>. + +<P><H2>Implementing the Strategy Rules</H2> + +<P>To determine the program's next move, <CODE>ttt</CODE> invokes <CODE>pickmove</CODE>; +since many of the strategy rules will involve an examination of possible +winning combinations, <CODE>pickmove</CODE> is given the output from <CODE> +make.triples</CODE> as its input. + +<P>The strategy I worked out for the program consists of several rules, in +order of importance. So the structure of <CODE>pickmove</CODE> should be something +like this: + +<P><PRE>to pickmove :triples +if first.rule.works [output first.rule's.square] +if second.rule.works [output second.rule's.square] +... +end +</PRE> + +<P>This structure would work, but it would be very inefficient, +because the procedure to determine whether a rule is applicable does +essentially the same work as the procedure to choose a square by following +the rule. For example, here's a procedure to decide whether or not the +program can win on this move: + +<P><PRE>to can.i.win.now +output not emptyp find "win.nowp :triples +end + +to win.nowp :triple +output equalp (filter [not numberp ?] :triple) (word :me :me) +end +</PRE> + +<P>The subprocedure <CODE>win.nowp</CODE> decides whether or not a +particular triple is winnable on this move, by looking for a triple +containing one number and two letters equal to whichever of X or O +the program is playing. For example, <CODE>3xx</CODE> is a winnable triple +if the program is playing X. + +<P>The procedure to pick a move if there is a winnable triple also must +apply <CODE>win.nowp</CODE> to the triples: + +<P><PRE>to find.winning.square +output filter "numberp find "win.nowp :triples +end +</PRE> + +<P>If there is a winnable triple <CODE>3xx</CODE>, then the program +should move in square 3. We find that out by looking for the number +within the first winnable triple we can find. + +<P>It seems inelegant to find a winnable triple just to see if there are +any, then find the same triple again to extract a number from it. +Instead, we take advantage of the fact that the procedure I've called +<CODE>find.winning.square</CODE> will return a distinguishable value--namely, +an empty list--if there is no winnable triple. We say + +<P><PRE>to pickmove :triples +local "try +make "try find.winning.square +if not emptyp :try [output :try] +... +end +</PRE> + +<P>In fact, instead of the procedure <CODE>find.winning.square</CODE> the +actual program uses a similar <CODE>find.win</CODE> procedure that takes the +letter X or O as an input; this allows the same procedure to check both +rule 1 (can the computer win on this move) and rule 2 (can the opponent +win on the following move). + +<P><CODE>Pickmove</CODE> checks each of the strategy rules with a similar pair of +instructions: + +<P><PRE>make "try something +if not emptyp :try [output :try] +</PRE> + +<P>Here is the complete procedure: + +<P><PRE>to pickmove :triples +local "try +make "try find.win :me ; rule 1: can computer win? +if not emptyp :try [output :try] +make "try find.win :you ; rule 2: can opponent win? +if not emptyp :try [output :try] +make "try find.fork ; rule 3: can computer fork? +if not emptyp :try [output :try] +make "try find.advance ; rule 4: can computer force? +if not emptyp :try [output :try] +output find [memberp ? :position] [5 1 3 7 9 2 4 6 8] ; rules 5-7 +end +</PRE> + +<P>The procedures that check for each rule have a common flavor: They all +use <CODE>filter</CODE> and <CODE>find</CODE> to select interesting triples and then +to select an available square from the chosen triple. I won't go through +them in complete detail, but there's one that uses a Logo feature I haven't +described before. Here is <CODE>find.fork</CODE>: + +<P><PRE>to find.fork +local "singles +make "singles singles :me ; find triples like 14x, x23 +if emptyp :singles [output []] +output repeated.number reduce "word :singles ; find square in two triples +end +</PRE> + +<P>Suppose the computer is playing X and the board looks like this: + +<P><PRE> +<TABLE rules="all" frame="void" border="2"> +<TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> +</PRE> + +<P><CODE>Find.fork</CODE> calls <CODE>singles</CODE> (a straightforward procedure +that you can read in the complete listing at the end of this chapter) to +find all the triples containing one X and two vacant squares. It outputs + +<P><PRE>[4x6 x47 3x7] +</PRE> + +<P>indicating that the middle row, the left column, and one of the +diagonals meet these conditions. To find a fork, we must find a vacant +square that is included in two of these triples. The expression + +<P><PRE>reduce "word :singles +</PRE> + +<P>strings these triples together into the word <CODE> +4x6x473x7</CODE>. The job of <CODE>repeated.number</CODE> is to find a digit that +occurs more than once in this word. Here is the procedure: + +<P><PRE>to repeated.number :squares +output find [memberp ? ?rest] filter "numberp :squares +end +</PRE> + +<P>The expression + +<P><PRE>filter "numberp :squares +</PRE> + +<P>gives us the word <CODE>464737</CODE>, which is the input word with +the letters removed. We use <CODE>find</CODE> to find a repeated digit in +this number. The new feature is the use of <CODE>?rest</CODE> in the predicate template + +<P><PRE>[memberp ? ?rest] +</PRE> + +<P><CODE>?rest</CODE> represents the part of the input to <CODE>find</CODE> (or any +of the other higher-order functions that understand templates) to the right +of the value being used as <CODE>?</CODE>. So in this example, <CODE>find</CODE> first +computes the value of the expression + +<P><PRE>memberp 4 64737 +</PRE> + +<P>This happens to be <CODE>true</CODE>, so <CODE>find</CODE> returns the value 4 +without looking at the remaining digits. But if necessary, <CODE>find</CODE> would +have gone on to compute + +<P><PRE>memberp 6 4737 +memberp 4 737 +memberp 7 37 +memberp 3 7 +memberp 7 " +</PRE> + +<P>(using the empty word as <CODE>?rest</CODE> in the last line) until one +of these turned out to be true. + +<P><H2>Further Explorations</H2> + +<P>The obvious first place to look for improvements to this project is +in the strategy. + +<P>At the beginning of the discussion about strategy, I suggested that +one possibility would be to make a complete list of all possible move +sequences, with explicit next-move choices recorded for each. How +many such sequences are there? If you write the program in a way +that considers rotations of the board as equivalent, perhaps not +very many. For example, if the computer moves first (in the center, +of course) there are really only two responses the opponent can make: +a corner or an edge. Any corner is equivalent to any other. From +that point on, the entire sequence of the game can be forced by the +computer, to a tie if the opponent played a corner, or to a win if +the opponent played an edge. If the opponent moves first, there are +three cases, center, corner, or edge. And so on. + +<P>An intermediate possibility between the complete list of cases and +the more general rules I used would be to keep a complete list of +cases for, say, the first two moves. After that, general rules could +be used for the "endgame." This is rather like the way people, +and some computer programs, play chess: they have the openings memorized, +and don't really have to start thinking until several moves have passed. +This book-opening approach is particularly appealing to me because +it would solve the problem of the anomalous sequence that made such +trouble for me in rule 4. + +<P>A completely different approach would be to have no rules at all, +but instead to write a <EM>learning</EM> program. The program might +recognize an immediate win (rule 1) and the threat of an immediate +loss (rule 2), but otherwise it would move randomly and record the +results. If the computer loses a game, it would remember the last +unforced choice it made in that game, and keep a record to try something +else in the same situation next time. The result, after many games, +would be a complete list of all possible sequences, as I suggested +first, but the difference is that you wouldn't have to do the figuring +out of each sequence. Such learning programs are frequently used +in the field of artificial intelligence. + +<P>It is possible to combine different approaches. A famous checkers-playing +program written by Arthur Samuel had several general rules programmed +in, like the ones in this tic-tac-toe program. But instead of having +the rules arranged in a particular priority sequence, the program +was able to learn how much weight to give each rule, by seeing which +rules tended to win the game and which tended to lose. + +<P>If you're tired of tic-tac-toe, another possibility would be to write +a program that plays some other game according to a strategy. Don't +start with checkers or chess! Many people have written programs in +which the computer acts as dealer for a game of Blackjack; you could +reverse the roles so that you deal the cards, and the computer tries +to bet with a winning strategy. Another source of ideas is Martin +Gardner, author of many books of mathematical games. + +<P> +<TABLE width="100%"><TR><TD><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<TD align="right"><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A> +</TABLE> + +<P><H2>Program Listing</H2> + +<PRE> +;; Overall orchestration + +to ttt +local [me you position] +draw.board +init +if equalp :me "x [meplay 5] +forever [ + if already.wonp :me [print [I win!] stop] + if tiedp [print [Tie game!] stop] + youplay getmove ;; ask person for move + if already.wonp :you [print [You win!] stop] + if tiedp [print [Tie game!] stop] + meplay pickmove make.triples ;; compute program's move +] +end + +to make.triples +output map "substitute.triple [123 456 789 147 258 369 159 357] +end + +to substitute.triple :combination +output map [item ? :position] :combination +end + +to already.wonp :player +output memberp (word :player :player :player) (make.triples) +end + +to tiedp +output not reduce "or map.se "numberp arraytolist :position +end + +to youplay :square +draw :you :square +setitem :square :position :you +end + +to meplay :square +draw :me :square +setitem :square :position :me +end + +;; Initialization + +to draw.board +splitscreen clearscreen hideturtle +drawline [-20 -50] 0 120 +drawline [20 -50] 0 120 +drawline [-60 -10] 90 120 +drawline [-60 30] 90 120 +end + +to drawline :pos :head :len +penup +setpos :pos +setheading :head +pendown +forward :len +end + +to init +make "position {1 2 3 4 5 6 7 8 9} +print [Do you want to play first (X)] +type [or second (O)? Type X or O:] +choose +print [For each move, type a digit 1-9.] +end + +to choose +local "side +forever [ + make "side readchar + pr :side + if equalp :side "x [choosex stop] + if equalp :side "o [chooseo stop] + type [Huh? Type X or O:] +] +end + +to chooseo +make "me "x +make "you "o +end + +to choosex +make "me "o +make "you "x +end + +;; Get opponent's moves + +to getmove +local "square +forever [ + type [Your move:] + make "square readchar + print :square + if numberp :square ~ + [if and (:square > 0) (:square < 10) + [if freep :square [output :square]]] + print [not a valid move.] +] +end + +to freep :square +output numberp item :square :position +end + +;; Compute program's moves + +to pickmove :triples +local "try +make "try find.win :me +if not emptyp :try [output :try] +make "try find.win :you +if not emptyp :try [output :try] +make "try find.fork +if not emptyp :try [output :try] +make "try find.advance +if not emptyp :try [output :try] +output find [memberp ? :position] [5 1 3 7 9 2 4 6 8] +end + +to find.win :who +output filter "numberp find "win.nowp :triples +end + +to win.nowp :triple +output equalp (filter [not numberp ?] :triple) (word :who :who) +end + +to find.fork +local "singles +make "singles singles :me +if emptyp :singles [output []] +output repeated.number reduce "word :singles +end + +to singles :who +output filter [singlep ? :who] :triples +end + +to singlep :triple :who +output equalp (filter [not numberp ?] :triple) :who +end + +to repeated.number :squares +output find [memberp ? ?rest] filter "numberp :squares +end + +to find.advance +output best.move filter "numberp find [singlep ? :me] :triples +end + +to best.move :my.single +local "your.singles +if emptyp :my.single [output []] +make "your.singles singles :you +if emptyp :your.singles [output first :my.single] +ifelse (count filter [? = first :my.single] + reduce "word :your.singles) > 1 ~ + [output first :my.single] ~ + [output last :my.single] +end + +;; Drawing moves on screen + +to draw :who :square +move :square +ifelse :who = "x [drawx] [drawo] +end + +to move :square +penup +setpos thing word "box :square +end + +to drawo +pendown +arc 360 18 +end + +to drawx +setheading 45 +pendown +repeat 4 [forward 25.5 back 25.5 right 90] +end + +make "box1 [-40 50] +make "box2 [0 50] +make "box3 [40 50] +make "box4 [-40 10] +make "box5 [0 10] +make "box6 [40 10] +make "box7 [-40 -30] +make "box8 [0 -30] +make "box9 [40 -30] +</PRE> + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> diff --git a/js/games/nluqo.github.io/~bh/v1ch6/ttt.lg b/js/games/nluqo.github.io/~bh/v1ch6/ttt.lg new file mode 100644 index 0000000..aa1c7a0 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch6/ttt.lg @@ -0,0 +1,198 @@ +;; Overall orchestration + +to ttt +local [me you position] +draw.board +init +if equalp :me "x [meplay 5] +forever [ + if already.wonp :me [print [I win!] stop] + if tiedp [print [Tie game!] stop] + youplay getmove ;; ask person for move + if already.wonp :you [print [You win!] stop] + if tiedp [print [Tie game!] stop] + meplay pickmove make.triples ;; compute program's move +] +end + +to make.triples +output map "substitute.triple [123 456 789 147 258 369 159 357] +end + +to substitute.triple :combination +output map [item ? :position] :combination +end + +to already.wonp :player +output memberp (word :player :player :player) (make.triples) +end + +to tiedp +output not reduce "or map.se "numberp arraytolist :position +end + +to youplay :square +draw :you :square +setitem :square :position :you +end + +to meplay :square +draw :me :square +setitem :square :position :me +end + +;; Initialization + +to draw.board +splitscreen clearscreen hideturtle +drawline [-20 -50] 0 120 +drawline [20 -50] 0 120 +drawline [-60 -10] 90 120 +drawline [-60 30] 90 120 +end + +to drawline :pos :head :len +penup +setpos :pos +setheading :head +pendown +forward :len +end + +to init +make "position {1 2 3 4 5 6 7 8 9} +print [Do you want to play first (X)] +type [or second (O)? Type X or O:] +choose +print [For each move, type a digit 1-9.] +end + +to choose +local "side +forever [ + make "side readchar + pr :side + if equalp :side "x [choosex stop] + if equalp :side "o [chooseo stop] + type [Huh? Type X or O:] +] +end + +to chooseo +make "me "x +make "you "o +end + +to choosex +make "me "o +make "you "x +end + +;; Get opponent's moves + +to getmove +local "square +forever [ + type [Your move:] + make "square readchar + print :square + if numberp :square ~ + [if and (:square > 0) (:square < 10) + [if freep :square [output :square]]] + print [not a valid move.] +] +end + +to freep :square +output numberp item :square :position +end + +;; Compute program's moves + +to pickmove :triples +local "try +make "try find.win :me +if not emptyp :try [output :try] +make "try find.win :you +if not emptyp :try [output :try] +make "try find.fork +if not emptyp :try [output :try] +make "try find.advance +if not emptyp :try [output :try] +output find [memberp ? :position] [5 1 3 7 9 2 4 6 8] +end + +to find.win :who +output filter "numberp find "win.nowp :triples +end + +to win.nowp :triple +output equalp (filter [not numberp ?] :triple) (word :who :who) +end + +to find.fork +local "singles +make "singles singles :me +if emptyp :singles [output []] +output repeated.number reduce "word :singles +end + +to singles :who +output filter [singlep ? :who] :triples +end + +to singlep :triple :who +output equalp (filter [not numberp ?] :triple) :who +end + +to repeated.number :squares +output find [memberp ? ?rest] filter "numberp :squares +end + +to find.advance +output best.move filter "numberp find [singlep ? :me] :triples +end + +to best.move :my.single +local "your.singles +if emptyp :my.single [output []] +make "your.singles singles :you +if emptyp :your.singles [output first :my.single] +ifelse (count filter [? = first :my.single] + reduce "word :your.singles) > 1 ~ + [output first :my.single] ~ + [output last :my.single] +end + +;; Drawing moves on screen + +to draw :who :square +move :square +ifelse :who = "x [drawx] [drawo] +end + +to move :square +penup +setpos thing word "box :square +end + +to drawo +pendown +arc 360 18 +end + +to drawx +setheading 45 +pendown +repeat 4 [forward 25.5 back 25.5 right 90] +end + +make "box1 [-40 50] +make "box2 [0 50] +make "box3 [40 50] +make "box4 [-40 10] +make "box5 [0 10] +make "box6 [40 10] +make "box7 [-40 -30] +make "box8 [0 -30] +make "box9 [40 -30] diff --git a/js/games/nluqo.github.io/~bh/v1ch6/v1ch6.html b/js/games/nluqo.github.io/~bh/v1ch6/v1ch6.html new file mode 100644 index 0000000..0a86e07 --- /dev/null +++ b/js/games/nluqo.github.io/~bh/v1ch6/v1ch6.html @@ -0,0 +1,1409 @@ +<HTML> +<HEAD> +<TITLE>Computer Science Logo Style vol 1 ch 6: Example: Tic-Tac-Toe</TITLE> +</HEAD> +<BODY> +<CITE>Computer Science Logo Style</CITE> volume 1: +<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT +<H1>Example: Tic-Tac-Toe</H1> + +<TABLE width="100%"><TR><TD> +<IMG SRC="../csls1.jpg" ALT="cover photo"> +<TD><TABLE> +<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian +Harvey</A><BR>University of California, Berkeley</CITE> +<TR><TD align="right"><BR> +<TR><TD align="right"><A HREF="../pdf/v1ch06.pdf">Download PDF version</A> +<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A> +<TR><TD align="right"><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A> +<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT +Press web page for Computer Science Logo Style</A> +</TABLE></TABLE> + +<HR> +<P>Program file for this chapter: <A HREF="ttt.lg"><CODE>ttt</CODE></A> + +<P>This chapter is the first application of the ideas we've explored to a +sizable project. The primary purpose of the chapter is to introduce +the techniques of <EM>planning</EM> a project, especially the choice of +how to organize the information needed by the program. This organization is +called the <EM>data structure</EM> of the program. Along the way, +we'll also see a new data type, the array, and a few other details of Logo +programming. + +<P><H2>The Project</H2> + +<P>Tic-tac-toe is not a very challenging game for human beings. If you're +an enthusiast, you've probably moved from the basic game to some variant +like three-dimensional tic-tac-toe on a larger grid. + +<P>If you sit down right now to play ordinary three-by-three tic-tac-toe +with a friend, what will probably happen is that every game will come +out a tie. Both you and your friend can probably play perfectly, +never making a mistake that would allow your opponent to win. + +<P>But can you <EM>describe</EM> how you know where to move each turn? +Most of the time, you probably aren't even aware of alternative possibilities; +you just look at the board and instantly know where you want to move. +That kind of instant knowledge is great for human beings, because +it makes you a fast player. But it isn't much help in writing a computer +program. For that, you have to know very explicitly what your strategy +is. + +<P>By the way, although the example of tic-tac-toe strategy is a relatively +trivial one, this issue of instant knowledge versus explicit rules is a hot +one in modern psychology. Some cognitive scientists, who think that human +intelligence works through mechanisms similar to computer programs, maintain +that when you know how to do something without knowing <EM>how</EM> you know, +you have an explicit set of rules deep down inside. It's just that the +rules have become a habit, so you don't think about them deliberately. +They're "compiled," in the jargon of cognitive psychology. On +the other hand, some people think that your implicit how-to knowledge is very +different from the sort of lists of rules that can be captured in a computer +program. They think that human thought is profoundly different from the way +computers work, and that a computer cannot be programmed to simulate the +full power of human problem-solving. These people would say, for example, +that when you look at a tic-tac-toe board you immediately grasp the +strategic situation as a whole, and your eye is drawn to the best move +without any need to examine alternatives according to a set of rules. (You +might like to try to be aware of your own mental processes as you play a +game of tic-tac-toe, to try to decide which of these points of view more +closely resembles your own experience--but on the other hand, the +psychological validity of such introspective evidence is <EM>another</EM> +hotly contested issue in psychology!) + +<P>»Before you read further, try to write down a set of strategy rules +that, if followed consistently, will never lose a game. Play a few +games using your rules. Make sure they work even if the other player +does something bizarre. + +<P>I'm going to number the squares in the tic-tac-toe +board this way: + +<P> +<TABLE rules="all" frame="void" border="2" noshade><TR><TD align="center" height=30 width=30>1<TD align="center" height=30 width=30>2<TD align="center" height=30 width=30>3<TR><TD align="center" height=30 width=30>4<TD align="center" height=30 width=30>5<TD align="center" height=30 width=30>6<TR><TD align="center" height=30 width=30>7<TD align="center" height=30 width=30>8<TD align="center" height=30 width=30>9</TABLE> + +<P>Squares 1, 3, 7, and 9 are <EM>corner squares</EM>. I'll call +2, 4, 6, and 8 <EM>edge squares</EM>. And of course number 5 is the +<EM>center square</EM>. I'll use the word <EM>position</EM> to mean +a specific partly-filled-in board with X and O in certain squares, and +other squares empty. + +<P>One way you might meet my challenge of describing your strategy explicitly +is to list all the possible sequences of moves up to a certain point +in the game, then say what move you'd make next in each situation. +How big would the list have to be? There are nine possibilities for +the first move. For each first move, there are eight possibilities +for the second move. If you continue this line of reasoning, you'll +see that there are nine factorial, or 362880, possible sequences of +moves. Your computer may not have enough memory to list +them all, and you certainly don't have enough patience! + +<P>Fortunately, not all these sequences are interesting. Suppose you +are describing the rules a computer should use against a human player, +and suppose the human being moves first. Then there are, indeed, +nine possible first moves. But for each of these, there is only <EM> +one</EM> possible computer move! After all, we're programming the computer. +We get to decide which move it will choose. Then there are seven +possible responses by the opponent, and so on. The number of sequences +when the human being plays first is 9 times 7 times 5 times 3, or +945. If the computer plays first, it will presumably always make +the single best choice. Then there are eight possible responses, +and so on. In this case the number of possible game sequences is +8 times 6 times 4 times 2, or 384. Altogether we have 1329 cases +to worry about, which is much better than 300,000 but still not an +enjoyable way to write a computer program. + +<P>In fact, though, this number is still too big. Not all games go for +a full nine moves before someone wins. Also, many moves force the +opponent to a single possible response, even though there are other +vacant squares on the board. Another reduction can be achieved by +taking advantage of <EM>symmetry</EM>. For example, if X starts in square +5, any game sequence in which O responds in square 1 is equivalent +to a sequence in which O responds in square 3, with the board rotated +90 degrees. In fact there are only two truly different responses +to a center-square opening: any corner square, or any edge square. + +<P>With all of these factors reducing the number of distinct positions, +it would probably be possible to list all of them and write +a strategy program that way. I'm not sure, though, because I didn't +want to use that technique. I was looking for rules expressed in +more general terms, like "all else being equal, pick a corner rather +than an edge." + +<P>Why should I prefer a corner? Each corner square is part of three +winning combinations. For example, square 1 is part of <CODE>123</CODE>, +<CODE>147</CODE>, and <CODE>159</CODE>. (By expressing these winning combinations as +three-digit numbers, I've jumped ahead a bit in the story with a preview of how +the program I wrote represents this information.) An edge square, +on the other hand, is only part of two winning combinations. For +example, square 2 is part of <CODE>123</CODE> and <CODE>258</CODE>. Taking a corner +square makes three winning combinations available to me and unavailable +to my opponent. + +<P>Since I've brought up the subject of winning combinations, how many +of <EM>them</EM> are there? Not very many: three horizontal, three vertical, +and two diagonal. Eight altogether. That <EM>is</EM> a reasonable amount +of information to include in a program, and in fact there is a list +of the eight winning combinations in this project. + +<P>You might, at this point, enjoy playing a few games with the program, +to see if you can figure out the rules it uses in its strategy. If +you accepted my earlier challenge to write down your own set of strategy +rules, you can compare mine to yours. Are they the same? If not, +are they equally good? + +<P>The top-level procedure in this project is called <CODE>ttt</CODE>. It takes no +inputs. When you invoke this procedure, it will ask you if you'd +like to play first (X) or second (O). Then you enter moves by typing +a digit 1-9 for the square you select. The program draws the game +board on the Logo graphics screen. + +<P>I'm about to start explaining my strategy rules, so stop reading if +you want to work out your own and haven't done it yet. + +<P><H2>Strategy</H2> + +<P>The highest-priority and the lowest-priority rules seemed obvious +to me right away. The highest-priority are these: + +<P> + +<P><TABLE><TR><TH>1. <TD>If I can win on this move, do it. +<TR><TH>2. <TD>If the other player can win on the next move, block that winning +square. +</TABLE> + +<P>Here are the lowest-priority rules, used only if there is +nothing suggested more strongly by the board position: + +<P><TABLE><TR><TH><EM>n</EM>-2. <TD>Take the center square if it's free. +<TR><TH><EM>n</EM>-1. <TD>Take a corner square if one is free. +<TR><TH><EM>n</EM>. <TD>Take whatever is available. +</TABLE> + +<P>The highest priority rules are the ones dealing with the +most urgent situations: either I or my opponent can win on the next +move. The lowest priority ones deal with the least urgent situations, +in which there is nothing special about the moves already made to +guide me. + +<P>What was harder was to find the rules in between. I knew that the +goal of my own tic-tac-toe strategy was to set up a <EM>fork</EM>, a +board position in which I have two winning moves, so my opponent can +only block one of them. Here is an example: + +<P> <TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> + +<P>X can win by playing in square 3 or square 4. It's O's +turn, but poor O can only block one of those squares at a time. Whichever +O picks, X will then win by picking the other one. + +<P>Given this concept of forking, I decided to use it as the next highest +priority rule: + +<P><TABLE><TR><TH>3. <TD>If I can make a move that will set up a fork for myself, do it. +</TABLE> + +<P>That was the end of the easy part. My first attempt at +writing the program used only these six rules. Unfortunately, it +lost in many different situations. I needed to add something, but +I had trouble finding a good rule to add. + +<P>My first idea was that rule 4 should be the defensive equivalent of +rule 3, just as rule 2 is the defensive equivalent of rule 1: + +<P><TABLE><TR><TH>4a. <TD>If, on the next move, my opponent can set up a fork, block that +possibility by moving into the square that is common to his two winning +combinations. +</TABLE> + +<P>In other words, apply the same search technique to the opponent's +position that I applied to my own. + +<P>This strategy works well in many cases, but not all. For example, +here is a sequence of moves under this strategy, with the human player +moving first: + +<P><PRE><TABLE><TR> +<TD width=150 align="center" valign="bottom"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30><TD align="center" height=30 width=30> <TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30>x<TD align="center" height=30 width=30> <TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>In the fourth grid, the computer (playing O) has discovered +that X can set up a fork by moving in square 6, between the winning +combinations <CODE>456</CODE> and <CODE>369</CODE>. The computer moves to block this +fork. Unfortunately, X can also set up a fork by moving in squares +3, 7, or 8. The computer's move in square 6 has blocked one combination +of the square-3 fork, but X can still set up the other two. In the +fifth grid, X has moved in square 8. This sets up the winning combinations +<CODE>258</CODE> and <CODE>789</CODE>. The computer can only block one of these, and +X will win on the next move. + +<P>Since X has so many forks available, does this mean that the game +was already hopeless before O moved in square 6? No. Here is something +O could have done: + +<P><PRE><TABLE><TR> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>In this sequence, the computer's second move is in square +7. This move also blocks a fork, but it wasn't chosen for that reason. +Instead, it was chosen <EM>to force X's next move</EM>. In the fifth +grid, X has had to move in square 4, to prevent an immediate win by +O. The advantage of this situation for O is that square 4 was <EM> +not</EM> one of the ones with which X could set up a fork. O's next move, +in the sixth grid, is also forced. But by then the board is too crowded +for either player to force a win; the game ends in a tie, as usual. + +<P>This analysis suggests a different choice for an intermediate-level +strategy rule, taking the offensive: + +<P><TABLE><TR><TH>4b. <TD>If I can make a move that will set up a winning combination +for myself, do it. +</TABLE> + +<P>Compared to my earlier try, this rule has the benefit of +simplicity. It's much easier for the program to look for a single +winning combination than for a fork, which is two such combinations +with a common square. + +<P>Unfortunately, this simple rule isn't quite good enough. In the example +just above, the computer found the winning combination <CODE>147</CODE> in +which it already had square 1, and the other two were free. But why +should it choose to move in square 7 rather than square 4? If the +program did choose square 4, then X's move would still be forced, +into square 7. We would then have forced X into creating a fork, +which would defeat the program on the next move. + +<P>It seems that there is no choice but to combine the ideas from rules +4a and 4b: + +<P><TABLE><TR><TH>4b. <TD>If I can make a move that will set up a winning combination +for myself, do it. But ensure that this move does not force the opponent +into establishing a fork. +</TABLE> + +<P>What this means is that we are looking for a winning combination +in which the computer already owns one square and the other two are empty. +Having found such a combination, we can move in either of its empty squares. +Whichever we choose, the opponent will be forced to choose the other one +on the next move. If one of the two empty squares would create a fork for +the opponent, then the computer must choose that square and leave the other +for the opponent. + +<P>What if <EM>both</EM> of the empty squares in the combination we find +would make forks for the opponent? In that case, we've chosen a bad +winning combination. It turns out that there is only one situation +in which this can happen: + +<P><PRE><TABLE><TR> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>Again, the computer is playing O. After the third grid, +it is looking for a possible winning combination for itself. There +are three possibilities: <CODE>258</CODE>, <CODE>357</CODE>, and <CODE>456</CODE>. +So far we +have not given the computer any reason to prefer one over another. +But here is what happens if the program happens to choose <CODE>357</CODE>: + +<P><PRE><TABLE><TR> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE> +</TABLE></PRE> + +<P>By this choice, the computer has forced its opponent into +a fork that will win the game for the opponent. +If the computer chooses either of the other two possible winning combinations, +the game ends in a tie. (All moves after this choice turn out to +be forced.) + +<P>This particular game sequence was very troublesome for me because +it goes against most of the rules I had chosen earlier. For one thing, +the correct choice for the program is any edge square, while the corner +squares must be avoided. This is the opposite of the usual priority. + +<P>Another point is that this situation contradicts rule 4a (prevent +forks for the other player) even more sharply than the example we +considered earlier. In that example, rule 4a wasn't enough +guidance to ensure a correct choice, but the correct choice was at +least <EM>consistent</EM> with the rule. That is, just blocking a fork +isn't enough, but threatening a win and <EM>also</EM> blocking a fork +is better than just threatening a win alone. This is the meaning +of rule 4. But in this new situation, the corner square (the move +we have to avoid) <EM>does</EM> block a fork, while the edge square (the +correct move) <EM>doesn't</EM> block a fork! + +<P>When I discovered this anomalous case, I was ready to give up on the +idea of beautiful, general rules. I almost decided to build into +the program a special check for this precise board configuration. +That would have been pretty ugly, I think. But a shift in viewpoint +makes this case easier to understand: What the program must do is +force the other player's move, and force it in a way that helps the +computer win. If one possible winning combination doesn't allow us to +meet these conditions, the program should try another combination. +My mistake was to think either about forcing alone (rule 4b) or about +the opponent's forks alone (rule 4a). + +<P>As it turns out, the board situation we've been considering is the only +one in which a possible winning combination could include two possible +forks for the opponent. What's more, in this board situation, it's a +diagonal combination that gets us in trouble, while a horizontal or +vertical combination is always okay. Therefore, I was able to implement +rule 4 in a way that only considers one possible winning combination by +setting up the program's data structures so that diagonal combinations +are the last to be chosen. This trick makes the program's design less +than obvious from reading the actual program, but it does save the program +some effort. + +<P><H2>Program Structure and Modularity</H2> + + +<P>Most game programs--in fact, most interactive programs of any +kind--consist of an initialization section followed by a sequence +of steps carried out repeatedly. In the case of the tic-tac-toe game, +the overall program structure will be something like this: + +<P><PRE>to ttt +initialize +forever [ + if <EM>game.is.over</EM> [stop] + <EM>record.human.move get.human.move</EM> + if <EM>game.is.over</EM> [stop] + <EM>record.program.move compute.program.move</EM> +] +end +</PRE> + +<P>The parts of this structure shown in <CODE><EM>italics</EM></CODE> are +just vague ideas. At this point in the planning, I don't know what inputs +these procedures might need, for example. In fact, there may not be +procedures exactly like this in the final program. One example is that +the test that I've called <CODE><EM>game.is.over</EM></CODE> here will actually +turn out to be two separate tests <CODE>already.wonp</CODE> and <CODE>tiedp</CODE> (using +a final letter <CODE>p</CODE> to indicate a predicate, following the convention +established by the Logo primitive predicates). + +<P>This half-written procedure introduces a Logo primitive we haven't used +before: <CODE>forever</CODE>. It takes a list of Logo instructions as its +input, and carries out those instructions repeatedly, much as <CODE>repeat</CODE>, +<CODE>for</CODE>, and <CODE>foreach</CODE> do. But the number of repetitions is unlimited; +the repetition stops only if, as in this example, the primitive <CODE>stop</CODE> or +<CODE>output</CODE> is invoked within the repeated instructions. <CODE>Forever</CODE> is +useful when the ending condition can't be predicted in advance, as in a game +situation in which a player might win at any time. + +<P>It may not be obvious why I've planned for one procedure to figure out the +next move and a separate procedure to record it. (There are two such pairs +of procedures, one for the program's moves and the other for the human +opponent's moves.) For one thing, I expect that the recording of moves +will be much the same whether it's the program or the person moving, while +the decision about where to move will be quite different in the two cases. +For the program's move we must apply strategy rules; for the human player's +moves we simply ask the player. Also, I anticipate that the selection of +the program's moves, which will be the hardest part of the program, can be +written in functional style. The strategy procedure is a function that takes +the current board position as its input, always returning the same chosen +square for any given input position. + +<P>This project contains 28 procedures. These procedures can be divided into +related groups like this: + +<P><TABLE> +<TR><TD>7<TD>overall orchestration +<TR><TD>6<TD>initialization +<TR><TD>2<TD>get opponent's moves +<TR><TD>9<TD>compute program's moves +<TR><TD>4<TD>draw moves on screen +</TABLE> + +<P>As you might expect, figuring out the computer's strategy +is the most complex part of the program's job. But this strategic +task is still only about a third of the complete program. + +<P>The five groups are quite cleanly distinguishable in this project. There are +relatively few procedure invocations between groups, compared to the number +within a group. It's easy to read the procedures within a group and +understand how they work without having to think about other parts of the +program at the same time. + +<P> +The following diagram shows the subprocedure/superprocedure relationships +within the program, and indicates which procedures are in each of the five +groups listed above. Some people find diagrams like this one very helpful in +understanding the structure of a program. Other people don't like these +diagrams at all. If you find it helpful, you may want to draw such diagrams +for your own projects. + +<P> + +<CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch6/tttflow.gif" ALT="figure: tttflow"></CENTER> + + + +<P>In the diagram, I've circled the names of seven procedures. If you +understand the purpose of each of these, then you will understand +the general structure of the entire program. (Don't turn to the end and +read the actual procedures just now. Instead, see if +you can understand the following paragraphs just from the diagram.) + +<P><CODE>Ttt</CODE> is the top-level procedure for which I gave a rough outline +earlier. It calls initialization procedures (<CODE>draw.board</CODE> and <CODE> +init</CODE>) to set up the game, then repeatedly alternates between the human +opponent's moves and the program's moves. It calls <CODE>getmove</CODE> to find +out the next move by the opponent, <CODE>youplay</CODE> to record that move, +then <CODE>pickmove</CODE> to compute the program's next move and <CODE>meplay</CODE> +to record it. + +<P><CODE>Make.triples</CODE> translates from one representation of the board +position to another. The representation used within <CODE>ttt</CODE> is best +suited for display and for user interaction, while the representation +output by <CODE>make.triples</CODE> is best for computing the program's strategy. +We'll look into data representation more closely later. + +<P><CODE>Getmove</CODE> invites the opponent to type in a move. It ensures that +the selected move is legal before accepting it. The output from <CODE> +getmove</CODE> is a number from 1 to 9 representing the chosen square. + +<P><CODE>Pickmove</CODE> figures out the program's next move. It is the "smartest" +procedure in the program, embodying the strategy rules I listed earlier. +It, too, outputs a number from 1 to 9. + +<P><CODE>Youplay</CODE> and <CODE>meplay</CODE> are simple procedures that actually carry out +the moves chosen by the human player and by the program, respectively. +Each contains only two instructions. The first invokes <CODE>draw</CODE> to draw +the move on the screen. The second modifies the <CODE>position</CODE> array +to remember that the move has been made. + +<P><CODE>Draw</CODE> moves the turtle to the chosen square on the tic-tac-toe board. +Then it draws either an X or an O. (We haven't really talked about Logo's +turtle graphics yet. If you're not familiar with turtle graphics from +earlier Logo experience, you can just take this part of the program on faith; +there's nothing very interesting about it.) + +<P>Notice, in the diagram, that the lines representing procedure calls +come into a box only at the top. This is one sign of a well-organized +program: The dashed boxes in the diagram truly do represent distinct +parts of the program that don't interact very much. + +<P><H2>Data Representation</H2> + +<P>I've written several tic-tac-toe programs, in different programming +languages. This experience has really taught me about the importance of +picking a good data representation. For my first tic-tac-toe +program, several years ago, I decided without much prior thought that a +board position should be represented as three lists of numbers, one with X's +squares, one with O's squares, and one with the free squares. So this board +position + +<P><PRE> +<TABLE rules="all" frame="void" border="2"> +<TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> +</PRE> + +<P>could be represented like this: + +<P><PRE>make "xsquares [1 4 5] +make "osquares [2 9] +make "free [3 6 7 8] +</PRE> + +<P>These three variables would change in value as squares moved +from <CODE>:free</CODE> to one of the others. This representation was easy +to understand, but not very helpful for writing the program! + +<P>What questions does a tic-tac-toe program have to answer about the board +position? If, for example, the program wants to print a display of the +position, it must answer questions of the form "Who's in square 4?" +With the representation shown here, that's not as easy a question as we +might wish: + +<P><PRE>to occupant :square ;; old program +if memberp :square :xsquares [output "x] +if memberp :square :osquares [output "o] +output "free +end +</PRE> + +<P> +<P>On the other hand, this representation isn't so bad when we're +accepting a move from the human player and want to make sure it's a legal +move: + +<P><PRE>to freep :square ;; old program +output memberp :square :free +end +</PRE> + +<P>Along with this representation of the board, my first program used +a constant list of winning combinations: + +<P><PRE>make "wins [[1 2 3] [4 5 6] [7 8 9] [1 4 7] [2 5 8] + [3 6 9] [1 5 9] [3 5 7]] +</PRE> + +<P>It also had a list of all possible forks. I won't bother +trying to reproduce this very long list for you, since it's not used +in the current program, but the fork set up by X in the +board position just above was represented this way: + +<P><PRE>[4 [1 7] [5 6]] +</PRE> + +<P>This indicates that square 4 is the pivot of a fork between +the winning combinations <CODE>[1 4 7]</CODE> and <CODE>[4 5 6]</CODE>. Each member of the +complete list of forks was a list like this sample. The list of forks +was fairly long. Each edge square is the pivot of a fork. Each corner +square is the pivot of three forks. The center square is the pivot +of six forks. This adds up to 22 forks altogether. + +<P>Each time the program wanted to choose a move, it would first check +all eight possible winning combinations to see if two of the squares +were occupied by the program and the third one free. Since any of +the three squares might be the free one, this is a fairly tricky program +in itself: + +<P><PRE>to checkwin :candidate :mysquares :free ;; old program +if memberp first :candidate :free ~ + [output check1 butfirst :candidate :mysquares] +if memberp last :candidate :free ~ + [output check1 butlast :candidate :mysquares] +if memberp first butfirst :candidate :free ~ + [output check1 list first :candidate last :candidate :mysquares] +output "false +end + +to check1 :sublist :mysquares ;; old program +output and (memberp first :sublist :mysquares) ~ + (memberp last :sublist :mysquares) +end +</PRE> + +<P>This procedure was fairly slow, especially when invoked +eight times, once for each possible win. But the procedure to check +each of the possible forks was even worse! + +<P>In the program that I wrote for the first edition of <EM>Computer Science +Logo Style,</EM> a very different approach is used. This approach is based on +the realization that, at any moment, a particular winning combination may be +free for anyone (all three squares free), available only to one player, or +not available to anyone. It's silly for the program to go on checking a +combination that can't possibly be available. Instead of a single list of +wins, the new program has three lists: + +<P> +<TABLE> +<TR><TD><CODE>mywins</CODE><TD width=30><TD>wins available to the computer +<TR><TD><CODE>yourwins</CODE><TD width=30><TD>wins available to the opponent +<TR><TD><CODE>freewins</CODE><TD width=30><TD>wins available to anyone +</TABLE> + +<P>Once I decided to organize the winning combinations in this form, +another advantage became apparent: for each possible winning combination, +the program need only remember the squares that are free, not the +ones that are occupied. For example, the board position shown above +would contain these winning combinations, supposing the computer is +playing X: + +<P><PRE>make "mywins [[7] [6] [3 7]] +make "yourwins [[3 6] [7 8]] +make "freewins [] +</PRE> + +<P>The sublist <CODE>[7]</CODE> of <CODE>:mywins</CODE> indicates that the computer can +win simply by filling square 7. This list represents the winning +combination that was originally represented as <CODE>[1 4 7]</CODE>, but since +the computer already occupies squares 1 and 4 there is no need to +remember those numbers. + +<P>The process of checking for an immediate win is streamlined with this +representation for two reasons, compared with the <CODE>checkwin</CODE> procedure +above. First, only those combinations in <CODE>:mywins</CODE> must +be checked, instead of all eight every time. Second, an immediate +win can be recognized very simply, because it is just a list with +one member, like <CODE>[7]</CODE> and <CODE>[6]</CODE> in the example above. The procedure +<CODE>single</CODE> looks for such a list: + +<P><PRE>to single :list ;; old program +output find [equalp (count ?) 1] :list +end +</PRE> + +<P>The input to <CODE>single</CODE> is either <CODE>:mywins</CODE>, to find a winning +move for the computer (rule 1), or <CODE>:yourwins</CODE>, to find and block a +winning move for the opponent (rule 2). + +<P>Although this representation streamlines the strategy computation (the +<CODE>pickmove</CODE> part of the program), it makes the recording of a move +quite difficult, because combinations must be moved from one list to +another. That part of the program was quite intricate and hard to +understand. + +<P><H2>Arrays</H2> + +<P>This new program uses <EM>two</EM> representations, one for the interactive +part of the program and one for the strategy computation. The first of these +is simply a collection of nine words, one per square, each of which is the +letter X, the letter O, or the number of the square. With this +representation, recording a move means changing one of the nine words. +It would be possible to keep the nine words in a list, and compute a new +list (only slightly different) after each move. But Logo provides another +data type, the <EM>array,</EM> which allows for changing one member +while keeping the rest unchanged. + +<P>If arrays allow for easy modification and lists don't, why not always use +arrays? Why did I begin the book with lists? The answer is that each +data type has advantages and disadvantages. The main disadvantage of an +array is that you must decide in advance how big it will be; there aren't +any constructors like <CODE>sentence</CODE> to lengthen an array. + +<P>In this case, the fixed length of an array is no problem, because a +tic-tac-toe board has nine squares. The <CODE>init</CODE> procedure creates +the position array with the instruction + +<P><PRE>make "position {1 2 3 4 5 6 7 8 9} +</PRE> + +<P>The braces <CODE>{} +</CODE> indicate an array in the same +way that brackets indicate a list. + +<P>If player X moves in square 7, we can record that information +by saying + +<P><PRE><CODE>setitem</CODE> 7 :position "x +</PRE> + +<P>(Of course, the actual instruction in procedures <CODE>meplay</CODE> and +<CODE>youplay</CODE> uses variables instead of the specific values 7 and X.) +<CODE>Setitem</CODE> is a command with three inputs: a number indicating which +member of the array to change, the array itself, and the new value for +the specified member. + +<P>To find out who owns a particular square, we could write this procedure: + +<P><PRE>to occupant :square +output <CODE>item</CODE> :square :position +end +</PRE> + +<P>(The <CODE>item</CODE> operation can select a member of an array just as +it can select a member of a list or of a word.) In fact, though, it turns +out that I don't have an <CODE>occupant</CODE> procedure in this program. But the +parts of the program that examine the board position do use <CODE>item</CODE> in a +similar way, as in this example: + +<P><PRE>to freep :square +output numberp item :square :position +end +</PRE> + +<P>To create an array without explicitly listing all of its members, use the +operation <CODE>array</CODE>. It takes a number as argument, indicating how many +members the array should have. It returns an array of the chosen size, in +which each member is the empty list. Your program can then use <CODE>setitem</CODE> +to assign different values to the members. + +<P>The only primitive operation to select a member of an array is <CODE>item</CODE>. +Word-and-list operations such as <CODE>butfirst</CODE> can't be used with arrays. +There are operations <CODE>arraytolist</CODE> and <CODE>listtoarray</CODE> to convert +a collection of information from one data type to the other. + +<P><H2>Triples</H2> + +<P>The position array works well as a long-term representation for the board +position, because it's easy to update; it also works well for interaction +with the human player, because it's easy to find out the status of a +particular square. But for computing the program's moves, we need a +representation that makes it easy to ask questions such as "Is there a +winning combination for my opponent on the next move?" That's why, in +the first edition of these books, I used the representation with three +lists of possible winning combinations. + +<P>When MatthewWright and I wrote the book <EM>Simply Scheme,</EM> we +decided that the general idea of combinations was a good one, but the three +lists made the program more complicated than necessary. Since there are +only eight possible winning combinations in the first place, it's not so +slow to keep one list of all of them, and use that list as the basis for +all the questions we ask in working out the program's strategy. If the +current board position is + +<P><PRE> +<TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> +</PRE> + +<P>we represent the three horizontal winning combinations with +the words <CODE>xo3</CODE>, <CODE>xx6</CODE>, and <CODE>78o</CODE>. Each combination is +represented as a three-"letter" word containing an <CODE>x</CODE> or an <CODE>o</CODE> +for an occupied square, or the square's number for a free square. By +using words instead of lists for the combinations, we make the entire +set of combinations more compact and easier to read. Each of these words +is called a <EM>triple.</EM> The job of procedure <CODE>make.triples</CODE> is +to combine the information in the position array with a list of the eight +winning combinations: + +<P><PRE>? <U>show make.triples</U> +[xo3 xx6 78o xx7 ox8 36o xxo 3x7] +</PRE> + +<P><CODE>Make.triples</CODE> takes no inputs because the list of possible +winning combinations is built into it, and the position array is in <CODE> +ttt</CODE>'s local variable <CODE>position</CODE>: + +<P><PRE>to make.triples +output map "substitute.triple [123 456 789 147 258 369 159 357] +end + +to substitute.triple :combination +output map [item ? :position] :combination +end +</PRE> + +<P>This short subprogram will repay careful attention. It uses +<CODE>map</CODE> twice, once in <CODE>make.triples</CODE> to compute a function of +each possible winning combination, and once in <CODE>substitute.triple</CODE> to +compute a function of each square in a given combination. (That latter +function is the one that looks up the square in the array <CODE>:position</CODE>.) + +<P>Once the program can make the list of triples, we can use that to answer +many questions about the status of the game. For example, in the top-level +<CODE>ttt</CODE> procedure we must check on each move whether or not a certain +player has already won the game. Here's how: + +<P><PRE>to already.wonp :player +output memberp (word :player :player :player) (make.triples) +end +</PRE> + +<P>If we had only the <CODE>position</CODE> array to work with, it would be +complicated to check all the possible winning combinations. But once we've +made the list of triples, we can just ask whether the word <CODE>xxx</CODE> or the +word <CODE>ooo</CODE> appears in that list. + +<P>Here is the actual top-level procedure definition: + +<P><PRE>to ttt +local [me you position] +draw.board +init +if equalp :me "x [meplay 5] +forever [ + if already.wonp :me [print [I win!] stop] + if tiedp [print [Tie game!] stop] + youplay getmove ;; ask person for move + if already.wonp :you [print [You win!] stop] + if tiedp [print [Tie game!] stop] + meplay pickmove make.triples ;; compute program's move +] +end +</PRE> + +<P>Notice that <CODE>position</CODE> is declared as a local variable. +Because of Logo's dynamic scope, all of the subprocedures in this project +can use <CODE>position</CODE> as if it were a global variable, but Logo will +"clean up" after the game is over. + +<P>Two more such quasi-global variables are used to remember whether the +computer or the human opponent plays first. The value of <CODE>me</CODE> will be +either the word <CODE>x</CODE> or the word <CODE>o</CODE>, whichever letter the program +itself is playing. Similarly, the value of <CODE>you</CODE> will be <CODE>x</CODE> or +<CODE>o</CODE> to indicate the letter used by the opponent. All of these variables +are given their values by the initialization procedure <CODE>init</CODE>. + +<P>This information could have been kept in the form of a single +<EM>flag variable,</EM> called something like <CODE>mefirst</CODE>, that would +contain the word <CODE>true</CODE> if the computer is X, or <CODE>false</CODE> if the +computer is O. (A flag variable is one whose value is always <CODE> +true</CODE> or <CODE>false</CODE>, just as a predicate is a procedure whose output is +<CODE>true</CODE> or <CODE>false</CODE>.) It would be used something like this: + +<P><PRE>if :mefirst [draw "x :square] [draw "o :square] +</PRE> + +<P>But it turned out to be simpler to use two variables and +just say + +<P><PRE>draw :me :square +</PRE> + +<P> +<P>One detail in the final program that wasn't in my first rough draft is the +instruction + +<P><PRE>if equalp :me "x [meplay 5] +</PRE> + +<P>just before the <CODE>forever</CODE> loop. It was easier to write the +loop so that it always gets the human opponent's move first, and then +computes a move for the program, rather than having two different loops +depending on which player goes first. If the program moves first, its +strategy rules would tell it to choose the center square, because there is +nothing better to do when the board is empty. By checking for that case +before the loop, we are ready to begin the loop with the opponent as the +next to move. + +<P><H2>Variables in the Workspace</H2> + + +<P>There are nine global variables that are part +of the workspace, entered directly with top-level <CODE>make</CODE> instructions +rather than set up by <CODE>init</CODE>, because their +values are never changed. Their names are <CODE>box1</CODE> through <CODE> +box9</CODE>, and their values are the coordinates on the graphics screen of +the center of each square. For example, <CODE>:box1</CODE> is <CODE> +[-40 50]</CODE>. These variables are used by <CODE>move</CODE>, a subprocedure of +<CODE>draw</CODE>, to know where to position the turtle before drawing an X +or an O. + +<P>The use of variables loaded with a workspace file, rather than given values +by an initialization procedure, is a practice that Logo encourages in some +ways and discourages in others. Loading variables in a workspace file makes +the program start up faster, because it decreases the amount of +initialization required. On the other hand, variables are sort of +second-class citizens in workspace files. In many versions of Logo the <CODE> +load</CODE> command lists the names of the procedures in the workspace file, but +not the names of the variables. Similarly, <CODE>save</CODE> often reports the +number of procedures saved, but not the number of variables. It's easy to +create global variables and forget that they're there. + +<P>Certainly preloading variables makes sense only if the variables are really +constants; in other words, a variable whose value may change during the +running of a program should be initialized explicitly when the program +starts. Otherwise, the program will probably give incorrect results if you +run it a second time. (One of the good ideas in the programming language +Pascal is that there is a sort of thing in the language called a <EM> +constant</EM>; it has a name and a value, like a variable, but you can't give +it a new value in mid-program. In Logo, you use a global variable to hold a +constant, and simply refrain from changing its value. But being able to +<EM>say</EM> that something is a constant makes the program easier to +understand.) + +<P>One reason the use of preloaded variables is sometimes questioned as a point +of style is that when people are sloppy in their use of global variables, +it's hard to know which are really meant to be preloaded and which are just +left over from running the program. That is, if you write a program, test +it by running it, and then save it on a diskette, any global variables that +were created during the program execution will still be in the workspace +when you load that diskette file later. If there are five +intentionally-loaded variables along with 20 leftovers, it's particularly +hard for someone to understand which are which. This is one more reason not +to use global variables when what you really want are variables local to the +top-level procedure. + +<P><H2>The User Interface</H2> + +<P>The only part of the program that really interacts with the human user is +<CODE>getmove</CODE>, the procedure that asks the user where to move. + +<P><PRE>to getmove +local "square +forever [ + type [Your move:] + make "square readchar + print :square + if numberp :square + [if and (:square > 0) (:square < 10) + [if freep :square [output :square]]] + print [not a valid move.] +] +end +</PRE> + +<P>There are two noteworthy things about this part of the program. One is that +I've chosen to use <CODE>readchar</CODE> to read what the player types. This +primitive operation, with no inputs, waits for the user to type any single +character on the keyboard, and outputs whatever character the user types. +This "character at a time" interaction is in contrast with the more usual +"line at a time" typing, in which you can type characters, erase some if +you make a mistake, and finally use the RETURN or ENTER key to indicate that +the entire line you've typed should be made available to your program. +(In Chapter 1 you met Logo's <CODE>readlist</CODE> primitive for line at a +time typing.) Notice that if tic-tac-toe had ten or more squares in its +board I wouldn't have been able to make this choice, because the program +would have to allow the entry of two-digit numbers. + +<P><CODE>Readchar</CODE> was meant for fast-action programs such as video games. +It therefore does not display (or <EM>echo</EM>) the character that you type +on the computer screen. That's why <CODE>getmove</CODE> includes a <CODE>print</CODE> +instruction to let the user see what she or he has typed! + +<P>The second point to note in <CODE>getmove</CODE> is how careful it is to allow for +the possibility of a user error. Ordinarily, when one procedure uses a +value that was computed by another procedure, the programmer can assume that +the value is a legitimate one for the intended purpose. For example, when +you invoke a procedure that computes a number, you assume that you can add +the output to another number; you don't first use the <CODE>number?</CODE> +predicate to double-check that the result was indeed a number. But in +<CODE>getmove</CODE> we are dealing with a value that was typed by a human being, +and human beings are notoriously error-prone! The user is <EM>supposed</EM> +to type a number between 1 and 9. But perhaps someone's finger might slip +and type a zero instead of a nine, or even some character that isn't a +number at all. Therefore, <CODE>getmove</CODE> first checks that what the user +typed is a number. If so, it then checks that the number is in the allowed +range. (We'd get a Logo error message if <CODE>getmove</CODE> used the <CODE> +<</CODE> operation with a non-numeric input.) Only if these conditions are met +do we use the user's number as the square-selecting input to <CODE>freep</CODE>. + +<P><H2>Implementing the Strategy Rules</H2> + +<P>To determine the program's next move, <CODE>ttt</CODE> invokes <CODE>pickmove</CODE>; +since many of the strategy rules will involve an examination of possible +winning combinations, <CODE>pickmove</CODE> is given the output from <CODE> +make.triples</CODE> as its input. + +<P>The strategy I worked out for the program consists of several rules, in +order of importance. So the structure of <CODE>pickmove</CODE> should be something +like this: + +<P><PRE>to pickmove :triples +if first.rule.works [output first.rule's.square] +if second.rule.works [output second.rule's.square] +... +end +</PRE> + +<P>This structure would work, but it would be very inefficient, +because the procedure to determine whether a rule is applicable does +essentially the same work as the procedure to choose a square by following +the rule. For example, here's a procedure to decide whether or not the +program can win on this move: + +<P><PRE>to can.i.win.now +output not emptyp find "win.nowp :triples +end + +to win.nowp :triple +output equalp (filter [not numberp ?] :triple) (word :me :me) +end +</PRE> + +<P>The subprocedure <CODE>win.nowp</CODE> decides whether or not a +particular triple is winnable on this move, by looking for a triple +containing one number and two letters equal to whichever of X or O +the program is playing. For example, <CODE>3xx</CODE> is a winnable triple +if the program is playing X. + +<P>The procedure to pick a move if there is a winnable triple also must +apply <CODE>win.nowp</CODE> to the triples: + +<P><PRE>to find.winning.square +output filter "numberp find "win.nowp :triples +end +</PRE> + +<P>If there is a winnable triple <CODE>3xx</CODE>, then the program +should move in square 3. We find that out by looking for the number +within the first winnable triple we can find. + +<P>It seems inelegant to find a winnable triple just to see if there are +any, then find the same triple again to extract a number from it. +Instead, we take advantage of the fact that the procedure I've called +<CODE>find.winning.square</CODE> will return a distinguishable value--namely, +an empty list--if there is no winnable triple. We say + +<P><PRE>to pickmove :triples +local "try +make "try find.winning.square +if not emptyp :try [output :try] +... +end +</PRE> + +<P>In fact, instead of the procedure <CODE>find.winning.square</CODE> the +actual program uses a similar <CODE>find.win</CODE> procedure that takes the +letter X or O as an input; this allows the same procedure to check both +rule 1 (can the computer win on this move) and rule 2 (can the opponent +win on the following move). + +<P><CODE>Pickmove</CODE> checks each of the strategy rules with a similar pair of +instructions: + +<P><PRE>make "try something +if not emptyp :try [output :try] +</PRE> + +<P>Here is the complete procedure: + +<P><PRE>to pickmove :triples +local "try +make "try find.win :me ; rule 1: can computer win? +if not emptyp :try [output :try] +make "try find.win :you ; rule 2: can opponent win? +if not emptyp :try [output :try] +make "try find.fork ; rule 3: can computer fork? +if not emptyp :try [output :try] +make "try find.advance ; rule 4: can computer force? +if not emptyp :try [output :try] +output find [memberp ? :position] [5 1 3 7 9 2 4 6 8] ; rules 5-7 +end +</PRE> + +<P>The procedures that check for each rule have a common flavor: They all +use <CODE>filter</CODE> and <CODE>find</CODE> to select interesting triples and then +to select an available square from the chosen triple. I won't go through +them in complete detail, but there's one that uses a Logo feature I haven't +described before. Here is <CODE>find.fork</CODE>: + +<P><PRE>to find.fork +local "singles +make "singles singles :me ; find triples like 14x, x23 +if emptyp :singles [output []] +output repeated.number reduce "word :singles ; find square in two triples +end +</PRE> + +<P>Suppose the computer is playing X and the board looks like this: + +<P><PRE> +<TABLE rules="all" frame="void" border="2"> +<TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE> +</PRE> + +<P><CODE>Find.fork</CODE> calls <CODE>singles</CODE> (a straightforward procedure +that you can read in the complete listing at the end of this chapter) to +find all the triples containing one X and two vacant squares. It outputs + +<P><PRE>[4x6 x47 3x7] +</PRE> + +<P>indicating that the middle row, the left column, and one of the +diagonals meet these conditions. To find a fork, we must find a vacant +square that is included in two of these triples. The expression + +<P><PRE>reduce "word :singles +</PRE> + +<P>strings these triples together into the word <CODE> +4x6x473x7</CODE>. The job of <CODE>repeated.number</CODE> is to find a digit that +occurs more than once in this word. Here is the procedure: + +<P><PRE>to repeated.number :squares +output find [memberp ? ?rest] filter "numberp :squares +end +</PRE> + +<P>The expression + +<P><PRE>filter "numberp :squares +</PRE> + +<P>gives us the word <CODE>464737</CODE>, which is the input word with +the letters removed. We use <CODE>find</CODE> to find a repeated digit in +this number. The new feature is the use of <CODE>?rest</CODE> in the predicate template + +<P><PRE>[memberp ? ?rest] +</PRE> + +<P><CODE>?rest</CODE> represents the part of the input to <CODE>find</CODE> (or any +of the other higher-order functions that understand templates) to the right +of the value being used as <CODE>?</CODE>. So in this example, <CODE>find</CODE> first +computes the value of the expression + +<P><PRE>memberp 4 64737 +</PRE> + +<P>This happens to be <CODE>true</CODE>, so <CODE>find</CODE> returns the value 4 +without looking at the remaining digits. But if necessary, <CODE>find</CODE> would +have gone on to compute + +<P><PRE>memberp 6 4737 +memberp 4 737 +memberp 7 37 +memberp 3 7 +memberp 7 " +</PRE> + +<P>(using the empty word as <CODE>?rest</CODE> in the last line) until one +of these turned out to be true. + +<P><H2>Further Explorations</H2> + +<P>The obvious first place to look for improvements to this project is +in the strategy. + +<P>At the beginning of the discussion about strategy, I suggested that +one possibility would be to make a complete list of all possible move +sequences, with explicit next-move choices recorded for each. How +many such sequences are there? If you write the program in a way +that considers rotations of the board as equivalent, perhaps not +very many. For example, if the computer moves first (in the center, +of course) there are really only two responses the opponent can make: +a corner or an edge. Any corner is equivalent to any other. From +that point on, the entire sequence of the game can be forced by the +computer, to a tie if the opponent played a corner, or to a win if +the opponent played an edge. If the opponent moves first, there are +three cases, center, corner, or edge. And so on. + +<P>An intermediate possibility between the complete list of cases and +the more general rules I used would be to keep a complete list of +cases for, say, the first two moves. After that, general rules could +be used for the "endgame." This is rather like the way people, +and some computer programs, play chess: they have the openings memorized, +and don't really have to start thinking until several moves have passed. +This book-opening approach is particularly appealing to me because +it would solve the problem of the anomalous sequence that made such +trouble for me in rule 4. + +<P>A completely different approach would be to have no rules at all, +but instead to write a <EM>learning</EM> program. The program might +recognize an immediate win (rule 1) and the threat of an immediate +loss (rule 2), but otherwise it would move randomly and record the +results. If the computer loses a game, it would remember the last +unforced choice it made in that game, and keep a record to try something +else in the same situation next time. The result, after many games, +would be a complete list of all possible sequences, as I suggested +first, but the difference is that you wouldn't have to do the figuring +out of each sequence. Such learning programs are frequently used +in the field of artificial intelligence. + +<P>It is possible to combine different approaches. A famous checkers-playing +program written by Arthur Samuel had several general rules programmed +in, like the ones in this tic-tac-toe program. But instead of having +the rules arranged in a particular priority sequence, the program +was able to learn how much weight to give each rule, by seeing which +rules tended to win the game and which tended to lose. + +<P>If you're tired of tic-tac-toe, another possibility would be to write +a program that plays some other game according to a strategy. Don't +start with checkers or chess! Many people have written programs in +which the computer acts as dealer for a game of Blackjack; you could +reverse the roles so that you deal the cards, and the computer tries +to bet with a winning strategy. Another source of ideas is Martin +Gardner, author of many books of mathematical games. + +<P> +<TABLE width="100%"><TR><TD><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<TD align="right"><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A> +</TABLE> + +<P><H2>Program Listing</H2> + +<PRE> +;; Overall orchestration + +to ttt +local [me you position] +draw.board +init +if equalp :me "x [meplay 5] +forever [ + if already.wonp :me [print [I win!] stop] + if tiedp [print [Tie game!] stop] + youplay getmove ;; ask person for move + if already.wonp :you [print [You win!] stop] + if tiedp [print [Tie game!] stop] + meplay pickmove make.triples ;; compute program's move +] +end + +to make.triples +output map "substitute.triple [123 456 789 147 258 369 159 357] +end + +to substitute.triple :combination +output map [item ? :position] :combination +end + +to already.wonp :player +output memberp (word :player :player :player) (make.triples) +end + +to tiedp +output not reduce "or map.se "numberp arraytolist :position +end + +to youplay :square +draw :you :square +setitem :square :position :you +end + +to meplay :square +draw :me :square +setitem :square :position :me +end + +;; Initialization + +to draw.board +splitscreen clearscreen hideturtle +drawline [-20 -50] 0 120 +drawline [20 -50] 0 120 +drawline [-60 -10] 90 120 +drawline [-60 30] 90 120 +end + +to drawline :pos :head :len +penup +setpos :pos +setheading :head +pendown +forward :len +end + +to init +make "position {1 2 3 4 5 6 7 8 9} +print [Do you want to play first (X)] +type [or second (O)? Type X or O:] +choose +print [For each move, type a digit 1-9.] +end + +to choose +local "side +forever [ + make "side readchar + pr :side + if equalp :side "x [choosex stop] + if equalp :side "o [chooseo stop] + type [Huh? Type X or O:] +] +end + +to chooseo +make "me "x +make "you "o +end + +to choosex +make "me "o +make "you "x +end + +;; Get opponent's moves + +to getmove +local "square +forever [ + type [Your move:] + make "square readchar + print :square + if numberp :square ~ + [if and (:square > 0) (:square < 10) + [if freep :square [output :square]]] + print [not a valid move.] +] +end + +to freep :square +output numberp item :square :position +end + +;; Compute program's moves + +to pickmove :triples +local "try +make "try find.win :me +if not emptyp :try [output :try] +make "try find.win :you +if not emptyp :try [output :try] +make "try find.fork +if not emptyp :try [output :try] +make "try find.advance +if not emptyp :try [output :try] +output find [memberp ? :position] [5 1 3 7 9 2 4 6 8] +end + +to find.win :who +output filter "numberp find "win.nowp :triples +end + +to win.nowp :triple +output equalp (filter [not numberp ?] :triple) (word :who :who) +end + +to find.fork +local "singles +make "singles singles :me +if emptyp :singles [output []] +output repeated.number reduce "word :singles +end + +to singles :who +output filter [singlep ? :who] :triples +end + +to singlep :triple :who +output equalp (filter [not numberp ?] :triple) :who +end + +to repeated.number :squares +output find [memberp ? ?rest] filter "numberp :squares +end + +to find.advance +output best.move filter "numberp find [singlep ? :me] :triples +end + +to best.move :my.single +local "your.singles +if emptyp :my.single [output []] +make "your.singles singles :you +if emptyp :your.singles [output first :my.single] +ifelse (count filter [? = first :my.single] + reduce "word :your.singles) > 1 ~ + [output first :my.single] ~ + [output last :my.single] +end + +;; Drawing moves on screen + +to draw :who :square +move :square +ifelse :who = "x [drawx] [drawo] +end + +to move :square +penup +setpos thing word "box :square +end + +to drawo +pendown +arc 360 18 +end + +to drawx +setheading 45 +pendown +repeat 4 [forward 25.5 back 25.5 right 90] +end + +make "box1 [-40 50] +make "box2 [0 50] +make "box3 [40 50] +make "box4 [-40 10] +make "box5 [0 10] +make "box6 [40 10] +make "box7 [-40 -30] +make "box8 [0 -30] +make "box9 [40 -30] +</PRE> + +<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A> +<P><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A> +chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A> + +<P> +<ADDRESS> +<A HREF="../index.html">Brian Harvey</A>, +<CODE>bh@cs.berkeley.edu</CODE> +</ADDRESS> +</BODY> +</HTML> |