*

1 files changed, 1127 insertions, 0 deletions

diff --git a/js/games/nluqo.github.io/~bh/ssch10/ttt b/js/games/nluqo.github.io/~bh/ssch10/ttt
new file mode 100644
index 0000000..85f731e
--- /dev/null
+++ b/js/games/nluqo.github.io/~bh/ssch10/ttt
@@ -0,0 +1,1127 @@
+\input bkmacs
+\pagetag{\tttttm}\photo{This computer, built of Tinker-Toy parts, plays
+tic-tac-toe.}{\pspicture{4in}{tinker}{tinker}{\TrimLeft{60pt}}}
+\chapter{Example: Tic-Tac-Toe}
+\chaptag{\ttt}
+\catcode`\_=12
+
+Now that you've learned about higher-order functions, we're going to look at
+a large example that uses them extensively.  Using the
+techniques you've learned so far, we're going to write a program that plays
+perfect tic-tac-toe.
+
+You can load our program into Scheme by typing
+
+{\prgex%
+(load "ttt.scm")
+}
+
+\noindent (See Appendix A if this doesn't work for you.)
+
+\subhd{A Warning}
+
+Programs don't always come out right the first time.  One of our goals in
+this chapter is to show you how a program is developed, so we're presenting
+early versions of procedures.  These include some mistakes that we made, and
+also some after-the-fact simplifications to make our explanations
+easier.  If you type in these early versions, they won't work.  We will show
+you how we corrected these ``bugs'' and also will present a complete, correct
+version at the end of the chapter.
+
+To indicate the unfinished versions of procedures, we'll use comments like
+``first version'' or ``not really part of game.''
+
+\subhd{Technical Terms in Tic-Tac-Toe}
+
+We'll number the squares of the board this way:
+
+{\ttboard123456789}
+
+We'll call a partially filled-in board a ``\idx{position}.''
+
+\ttboard__o_xox_x
+
+To the computer, the same position will be represented by the word {\ttx
+__o_xox_x}.  The nine letters of the word correspond to squares one through
+nine of the board.  (We're thinking ahead to the possibility of using {\tt
+item} to extract the $n$th square of a given position.)
+
+\subhd{Thinking about the Program Structure}
+
+Our top-level procedure, {\tt ttt}, will return the computer's next move 
+given the current position.  It takes two arguments:\ the current position
+and whether the computer is playing X or O.  If the computer is O and the
+board looks like the one above, then we'd invoke {\tt ttt} like this:
+
+{\prgex%
+(\ufun{ttt} '__o_xox_x 'o)
+}
+
+Here is a sample game:
+
+{\prgex%
+> (ttt '____x____ 'o)                   ; Human goes first in square 5
+1                                       ; Computer moves in square 1
+> (ttt 'o__xx____ 'o)                   ; Human moves in square 4
+6                                       ; Computer blocks in square 6
+> (ttt 'o_xxxo___ 'o)                   ; Human moves in square 3
+7                                       ; Computer blocks again
+> (ttt 'o_xxxoox_ 'o)
+2
+}
+
+This is not a complete game program!  Later, when we talk about input and
+output, you'll see how to write an interactive program that displays the
+board pictorially, asks the player where to move, and so on.  For now, we'll
+just write the {\it \idx{strategy}\/} procedure that chooses the next
+move.  As a paying customer, you wouldn't be satisfied with this
+partial program, but from the programmer's point of view, this is the more
+interesting part.
+
+Let's plan the computer's strategy in English before we start writing a
+computer program.  How do {\it you\/} play tic-tac-toe?  You have several
+strategy rules in your head, some of which are more urgent than others.  For
+example, if you can win on this move, then you just do it without thinking
+about anything else.  But if there isn't anything that immediate, you
+consider less urgent questions, such as how this move might affect what
+happens two moves later.
+
+So we'll represent this set of rules by a giant {\tt cond} expression:
+
+{\prgex%
+(define (ttt position me)                    ;; first version
+  (cond ((i-can-win?)
+         (choose-winning-move))
+        ((opponent-can-win?)
+         (block-opponent-win))
+        ((i-can-win-next-time?)
+         (prepare-win))
+        (else (whatever))))
+}
+
+We're imagining many helper procedures.  {\tt I-can-win?}\ will look at the
+board and tell if the computer has an immediate winning move. If so, {\tt
+choose-winning-move} will find that particular move.  {\tt
+Opponent-can-win?}\ returns true if the human player has an immediate
+winning move.  {\tt Block-opponent-win} will return a move that prevents the
+computer's opponent from winning, and so on.
+
+We didn't actually start by writing this definition of {\tt ttt}.  The
+particular names of helper procedures are just guesses, because we haven't
+yet planned the tic-tac-toe strategy in detail.  But we did know that this
+would be the overall structure of our program.  This big picture doesn't
+automatically tell us what to do next; different programmers might fill in
+the details differently.  But it's a framework to keep in mind during the
+rest of the job.
+
+Our first practical step was to think about the {\it
+\bkidx{data}{structure}s\/} in our program.  A data structure is a way of
+organizing several pieces of information into a big chunk.  For example, a
+sentence is a data structure that combines several words in a sequence (that
+is, in left-to-right order).
+
+In the first, handwavy version of {\tt ttt}, the strategy procedures like
+{\tt i-can-win?}\ are called with no arguments, but of course we knew they
+would need some information about the board position.  We began by thinking
+about how to represent that information within the program.
+
+\subhd{The First Step: Triples}
+
+A person looking at a tic-tac-toe board looks at the rows, columns, and
+diagonals.  The question ``do I have a winning move?'' is equivalent to the
+question ``are there three squares in a line such that two of them are mine
+and the last one is blank?''  In fact, nothing else matters about the game
+besides these potential winning combinations.
+
+There are eight potential winning combinations:\ three rows, three
+columns, and two diagonals.  Consider the combination containing the three
+squares 1, 5, and 9.  If it contains both an {\tt x} and an {\tt o} then
+nobody can win with this combination and there's nothing to think about.
+But if it contains two {\tt x}s and a free square, we're very interested in
+the combination.  What we want to know in particular is which square is
+free, since we want to move in that square to win or block.
+
+More generally, the only squares whose {\it numbers\/} we care about are the
+ones we might want to move into, namely, the free ones.  So the only
+interesting information about a square is whether it has an {\tt x} or an
+{\tt o}, and if not, what its number is.
+
+The information that 1, 5, 9 is a potential winning combination and the
+information that square 1 contains an {\tt x}, square 5 is empty, and square
+{\tt 9} contains another {\tt x} can be combined into the single word {\tt
+x5x}.  Looking at this word we can see immediately that there are two {\tt
+x}s in this ``\idx{triple}'' and that the free square is square 5.  So when we
+want to know about a three-square combination, we will turn it into a
+triple of that form.
+
+Here's a sample board position:
+
+\ttboard_xo_x_o__
+
+\noindent and here is a sentence of all of its triples:
+
+{\prgex%
+(1xo 4x6 o89 14o xx8 o69 1x9 oxo)
+}
+
+Take a minute to convince yourself that this sentence really does tell you
+everything you need to know about the corresponding board position.  Once
+our strategy procedure finds the triples for a board position, it's never
+going to look at the original position again.
+
+This technique of converting data from one form to another so that it can be
+manipulated more easily is an important idea in computer science.  There are
+really three \idx{representation}s of the same thing.  There's this picture:
+
+\ttboard_xo_x_o__
+
+\noindent as well as the word {\tt _xo_x_o__} and the sentence {\tt (1xo 4x6
+o89 14o xx8 o69 1x9 oxo)}.  All three of these formats have the same
+information but are convenient in different ways.  The pictorial form is
+convenient because it makes sense to the person who's playing tic-tac-toe.
+Unfortunately, you can't type that picture into a computer, so we need a
+different format, the word {\tt _xo_x_o__}, which contains the {\it
+contents\/} of the nine squares in the picture, but without the lines
+separating the squares and without the two-dimensional shape.
+
+The third format, the sentence, is quite {\it inconvenient\/} for human
+beings.  You'd never want to think about a tic-tac-toe board that way
+yourself, because the sentence doesn't have the visual simplicity that lets
+you take in a tic-tac-toe position at a glance.  But the sentence of triples
+is the most convenient representation for our program.  {\tt Ttt} will have
+to answer questions like ``can {\tt x} win on the next move?'' To do that, it
+will have to consider an equivalent but more detailed question:  ``For each
+of the eight possible winning combinations, can {\tt x} complete that
+combination on the next move?'' It doesn't really matter whether a
+combination is a row or a column; what does matter is that each of the eight
+combinations be readily available for inspection by the program.  The
+sentence-of-triples representation obscures part of the available
+information (which combination is where) to emphasize another part (making
+the eight combinations explicit, instead of implicit in the nine boxes of
+the diagram).
+
+The representation of fractions as ``mixed numerals,'' such as $2 {1 \over 3}$,
+and as ``improper fractions,'' such as $7 \over 3$, is a non-programming
+example of this idea about multiple representations.  A mixed numeral makes
+it easier for a person to tell how big the number is, but an improper
+fraction makes arithmetic easier.
+
+\subhd{Finding the Triples}
+
+We said that we would combine the current board position with the
+numbers of the squares in the eight potential winning combinations in order
+to compute the things we're calling triples.  That was our first task in
+writing the program.
+
+Our program will start with this sentence of all the winning combinations:
+
+{\prgex%
+(123 456 789 147 258 369 159 357)
+}
+
+\noindent and a position word such as {\tt _xo_x_o__}; it will return a
+sentence of triples such as
+
+{\prgex%
+(1xo 4x6 o89 14o xx8 o69 1x9 oxo)
+}
+
+All that's necessary is to replace some of the numbers with {\tt x}s and
+{\tt o}s.  This kind of word-by-word translation in a sentence is a good job
+for {\tt every}.
+
+{\prgex%
+(define (find-triples position)              ;; first version
+  (every substitute-triple '(123 456 789 147 258 369 159 357)))
+}
+
+We've made up a name {\tt substitute-triple} for a procedure we haven't
+written yet.  This is perfectly OK, as long as we write it before we try to
+invoke {\tt find-triples}.  The {\tt substitute-triple} function will take
+three digits, such as {\tt 258}, and return a triple, such as {\tt 2x8}:
+
+{\prgex%
+(define (substitute-triple combination)      ;; first version
+  (every substitute-letter combination))
+}
+
+\noindent This procedure uses {\tt every} to call {\tt substitute-letter} on
+all three letters.
+
+There's a small problem, though.  {\tt Every} always returns a sentence, and
+we want our triple to be a word.  For example, we want to turn the potential
+winning combination {\tt 258} into the word {\tt 2x8}, but {\tt every} would
+return the sentence {\tt (2~x~8)}.  So here's our next version of {\tt
+substitute-triple}:
+
+{\prgex%
+(define (substitute-triple combination)      ;; second version
+  (accumulate word (every substitute-letter combination)))
+}
+
+{\tt Substitute-letter} knows that letter number 3 of the word that
+represents the board corresponds to the contents of square 3 of the board.
+This means that it can just call {\tt item} with the given square number and
+the board to find out what's in that square.  If it's empty, we return the
+square number itself; otherwise we return the contents of the square.
+
+{\prgex%
+(define (substitute-letter square)           ;; first version
+  (if (equal? '_ (item square position))
+      square
+      (item square position)))
+}
+
+Whoops!  Do you see the problem?
+
+{\prgex%
+> (substitute-letter 5)
+ERROR: Variable POSITION is unbound.
+}
+
+\subhd{Using \ttpmb{Every} with Two-Argument Procedures}
+
+Our procedure only takes one argument, {\tt square}, but it needs to know
+the position so it can find out what's in the given square.  So here's the
+real {\tt substitute-letter}:
+
+{\prgex%
+(define (\ufun{substitute-letter} square position)
+  (if (equal? '_ (item square position))
+      square
+      (item square position)))
+
+> (substitute-letter 5 '_xo_x_o__)
+X
+
+> (substitute-letter 8 '_xo_x_o__)
+8
+}
+
+\noindent Now {\tt substitute-letter} can do its job, since it has access to
+the position.  But we'll have to modify {\tt substitute-triple} to invoke
+{\tt substitute-letter} with two arguments.
+
+This is a little tricky.  Let's look again at the way we're using {\tt
+substitute-letter} inside {\tt substitute-triple}:
+
+{\prgex%
+(define (substitute-triple combination)      ;; second version again
+  (accumulate word (every substitute-letter combination)))
+}
+
+\noindent By giving {\tt substitute-letter} another argument, we have made
+this formerly correct procedure incorrect.  The first argument to {\tt every}
+must be a function of one argument, not two.  This is exactly the kind of
+situation in which {\tt lambda} can help us:  We have a function of two
+arguments, and we need a function of one argument that does the same thing,
+but with one of the arguments fixed.
+
+The procedure returned by
+
+{\prgex%
+(lambda (square) (substitute-letter square position))
+}
+
+\noindent does exactly the right thing; it takes a square as its argument
+and returns the contents of the position at that square.
+
+Here's the final version of {\tt substitute-triple}:
+
+{\prgex%
+(define (\ufun{substitute-triple} combination position)
+  (accumulate word
+	      (every (lambda (square)
+		       (substitute-letter square position))
+		     combination)))
+
+> (substitute-triple 456 '_xo_x_o__)
+"4X6"
+
+> (substitute-triple 147 '_xo_x_o__)
+"14O"
+
+> (substitute-triple 357 '_xo_x_o__)
+OXO
+}
+
+\noindent As you can see, Scheme prints some of these words with
+double-quote marks.  The rule is that a word that isn't a number but begins
+with a digit must be double-quoted.  But in the finished program we're not
+going to print such words at all; we're just showing you the working of a
+helper procedure.  Similarly, in this chapter we'll show direct invocations
+of helper procedures in which some of the arguments are \idx{string}s, but a
+user of the overall program won't have to use this notation.
+
+We've fixed the {\tt substitute-letter} problem by giving {\tt
+substitute-triple} an extra argument, so we're going to have to go through
+the same process with {\tt find-triples}.  Here's the right version:
+
+{\prgex%
+(define (\ufun{find-triples} position)
+  (every (lambda (comb) (substitute-triple comb position))
+         '(123 456 789 147 258 369 159 357)))
+}
+
+\noindent It's the same trick.  {\tt Substitute-triple} is a procedure
+of two arguments.  We use {\tt lambda} to transform it into a procedure
+of one argument for use with {\tt every}.
+
+We've now finished {\tt find-triples}, one of the most important procedures in
+the game.
+
+{\prgex%
+> (find-triples '_xo_x_o__)
+("1XO" "4X6" O89 "14O" XX8 O69 "1X9" OXO)
+
+> (find-triples 'x_____oxo)
+(X23 456 OXO X4O "25X" "36O" X5O "35O")
+}
+
+Here again are the jobs of all three procedures we've written so far:
+
+\htstart
+<TABLE>
+<TR><TD><CODE>Substitute-letter&nbsp;&nbsp;</CODE>
+<TD>finds the letter in a single square.
+<TR><TD><CODE>Substitute-triple</CODE>
+<TD>finds all three leters corresponding to three squares.
+<TR><TD><CODE>Find-triples</CODE>
+<TD>finds all the letters in all eight winning combinations.
+</TABLE>
+\htend
+
+% \medskip
+% \def\tabRule{\noalign{\hrule}}
+% \def\two#1{\omit\span #1\hfil}
+% \noindent \vbox{\offinterlineskip
+% \baselineskip=12pt
+% \halign{\strut #\hfil & %function
+% \quad#\quad\hfil \cr%result
+% {\tt Substitute-letter}&finds the letter in a single square.\cr
+% {\tt Substitute-triple}&finds all three letters corresponding to
+% three squares.\cr
+% {\tt Find-triples}&finds all the letters in all eight winning
+% combinations.\cr
+% }}\hfil\medskip
+
+We've done all this because we think that the rest of the program can use
+the triples we've computed as data.  So we'll just compute the triples once
+for all the other procedures to use:
+
+{\prgex%
+(define (\ufun{ttt} position me)
+  (ttt-choose (find-triples position) me))
+
+(define (ttt-choose triples me)              ;; first version
+  (cond ((i-can-win? triples me)
+         (choose-winning-move triples me))
+        ((opponent-can-win? triples me)
+         (block-opponent-win triples me))
+        \ellipsis))
+}
+
+\subhd{Can the Computer Win on This Move?}
+
+The obvious next step is to write {\tt i-can-win?}, a procedure that should
+return {\tt \#t} if the computer can win on the current move---that is, if
+the computer already has two squares of a triple whose third square is empty.
+The triples {\tt x6x} and {\tt oo7} are examples.
+
+So we need a function that takes a word and a letter as arguments
+and counts how many times that letter appears in the word.  The
+{\tt appearances} primitive that we used in Chapter \functions\ (and
+that you re-implemented in Exercise \appear) will do the job:
+
+{\prgex%
+> (appearances 'o 'oo7)
+2
+
+> (appearances 'x 'oo7)
+0
+}
+
+The computer ``owns'' a triple if the computer's letter appears twice and
+the opponent's letter doesn't appear at all.  (The second condition is
+necessary to exclude cases like {\tt xxo}.)
+
+{\prgex%
+(define (\ufun{my-pair?} triple me)
+  (and (= (appearances me triple) 2)
+       (= (appearances (opponent me) triple) 0)))
+}
+
+Notice that we need a function {\tt opponent} that returns the opposite
+letter from ours.
+
+{\prgex%
+(define (\ufun{opponent} letter)
+  (if (equal? letter 'x) 'o 'x))
+
+> (opponent 'x)
+O
+
+> (opponent 'o)
+X
+
+> (my-pair? 'oo7 'o)
+#T
+
+> (my-pair? 'xo7 'o)
+#F
+
+> (my-pair? 'oox 'o)
+#F
+}
+
+Finally, the computer can win if it owns any of the triples:
+
+{\prgex%
+(define (i-can-win? triples me)                ;; first version
+  (not (empty?
+	(keep (lambda (triple) (my-pair? triple me))
+	      triples))))
+
+> (i-can-win? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'x)
+#T
+
+> (i-can-win? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'o)
+#F
+}
+
+\noindent By now you're accustomed to this trick with {\tt lambda}.  {\tt
+My-pair?}\ takes a triple and the computer's letter as arguments, but we
+want a function of one argument for use with {\tt keep}.
+
+\subhd{If So, in Which Square?}
+
+Suppose {\tt i-can-win?}\ returns {\tt \#t}.  We then have to find the
+particular square that will win the game for us.  This will involve a
+repetition of some of the same work we've already done:
+
+{\prgex%
+(define (choose-winning-move triples me)     ;; not really part of game
+  (keep number? (first (keep (lambda (triple) (my-pair? triple me))
+                             triples))))
+}
+
+\noindent We again use {\tt keep} to find the triples with two of the
+computer's letter, but this time we extract the number from the first such
+winning triple.
+
+We'd like to avoid this inefficiency.  As it turns out, generations of Lisp
+programmers have been in just this bind in the past, and so they've invented
+a \idx{kludge}\footnt{A kludge is a programming trick that doesn't follow
+the rules but works anyway somehow.  It doesn't rhyme with ``sludge''; it's
+more like ``clue'' followed by ``j'' as in ``Jim.''} to get around it.
+
+Remember we told you that everything other than {\tt \#f} counts as true?
+We'll take advantage of that by having a single procedure that returns the
+number of a winning square if one is available, or {\tt \#f} otherwise.  In
+Chapter \true\ we called such a procedure a ``semipredicate.'' The kludgy
+part is that \ttidx{cond} accepts a clause containing a single expression
+instead of the usual two expressions; if the expression has any true value,
+then {\tt cond} returns that value.  So we can say
+
+{\prgex%
+(define (ttt-choose triples me)              ;; second version
+  (cond ((i-can-win? triples me))
+        ((opponent-can-win? triples me))
+        \ellipsis))
+}
+
+\noindent where each {\tt cond} clause invokes a semipredicate.  We then
+modify {\tt i-can-win?}\ to have the desired behavior:
+
+{\prgex%
+(define (\ufun{i-can-win?} triples me)
+  (choose-win
+   (keep (lambda (triple) (my-pair? triple me))
+	 triples)))
+
+(define (\ufun{choose-win} winning-triples)
+  (if (empty? winning-triples)
+      #f
+      (keep number? (first winning-triples))))
+
+> (i-can-win? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'x)
+8
+
+> (i-can-win? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'o)
+#F
+}
+
+\vskip -5pt
+
+By this point, we're starting to see the structure of the overall program.
+There will be several procedures, similar to {\tt i-can-win?}, that will try
+to choose the next move.  {\tt I-can-win?} checks to see if the computer can
+win on this turn, another procedure will check to see if the computer should
+block the opponent's win next turn, and other procedures will check for
+other possibilities.  Each of these procedures will be what we've been
+calling ``semipredicates.'' That is to say, each will return the number of
+the square where the computer should move next, or {\tt \#f} if it can't
+decide.  All that's left is to figure out the rest of the computer's
+strategy and write more procedures like {\tt i-can-win?}.
+
+\backskipsubhd{Second Verse, Same as the First}{5}
+
+Now it's time to deal with the second possible strategy case:  The computer
+can't win on this move, but the opponent can win unless we block a triple
+right now.
+
+(What if the computer and the opponent both have immediate winning triples?
+In that case, we've already noticed the computer's win, and by winning the
+game we avoid having to think about blocking the opponent.)
+
+Once again, we have to go through the complicated business of finding
+triples that have two of the opponent's letter and none of the computer's
+letter---but it's already done!
+
+\vskip -2pt
+
+{\prgex%
+(define (\ufun{opponent-can-win?} triples me)
+  (i-can-win? triples (opponent me)))
+
+> (opponent-can-win? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'x)
+#F
+
+> (opponent-can-win? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'o)
+8
+}
+
+\vskip -2pt
+
+\penalty 10000
+
+\noindent Is that amazing or what?
+
+\goodbreak
+
+\subhd{Now the Strategy Gets Complicated}
+
+Since our goal here is to teach programming, rather than tic-tac-toe
+strategy, we're just going to explain the strategy we use and not give the
+history of how we developed it.
+
+The third step, after we check to see if either player can win on the next
+move, is to look for a situation in which a move that we make now will give
+rise to {\it two\/} winning triples next time.  Here's an example:
+
+\ttboard xo__x___o
+
+Neither {\tt x} nor {\tt o} can win on this move.  But if the computer is
+playing {\tt x}, moving in square 4 or square 7 will produce a situation
+with two winning triples.  For example, here's what happens if we move in
+square 7:
+
+\ttboard xo__x_x_o
+
+\noindent From this position, {\tt x} can win by moving either in square
+3 or in square 4.  It's {\tt o}'s turn, but {\tt o} can block only one of
+these two possibilities.  By contrast, if (in the earlier position) {\tt x}
+moves in square 3 or square 6, that would create a single winning triple for
+next time, but {\tt o} could block it.
+
+In other words, we want to find {\it two\/} triples in which one square is
+taken by the computer and the other two are free, with one free square
+shared between the two triples.  (In this example, we might find the two
+triples {\tt x47} and {\tt 3x7}; that would lead us to move in square 7, the
+one that these triples have in common.)  We'll call a situation like this a
+``\idx{fork},'' and we'll call the common square the ``\idx{pivot}.'' This
+isn't standard terminology; we just made up these terms to make it easier to
+talk about the strategy.
+
+In order to write the strategy procedure {\tt i-can-fork?}\ we assume that
+we'll need a procedure {\tt pivots} that returns a sentence of all pivots of
+forks currently available to the computer.  In this board, 4 and 7 are the
+pivots, so the {\tt pivots} procedure would return the sentence {\tt
+(4~7)}.  If we assume {\tt pivots}, then writing {\tt i-can-fork?}\ is
+straightforward:
+
+{\prgex%
+(define (\ufun{i-can-fork?} triples me)
+  (first-if-any (pivots triples me)))
+
+(define (\ufun{first-if-any} sent)
+  (if (empty? sent)
+      #f
+      (first sent)))
+}
+
+\subhd{Finding the Pivots}
+
+{\tt Pivots} should return a sentence containing the pivot numbers.  Here's
+the plan.  We'll start with the triples:
+
+{\prgex%
+(xo3 4x6 78o x47 ox8 36o xxo 3x7)
+}
+
+\noindent We {\tt keep} the ones that have an {\tt x} and two numbers:
+
+{\prgex%
+(4x6 x47 3x7)
+}
+
+\noindent We mash these into one huge word:
+
+{\prgex%
+4x6x473x7
+}
+
+\noindent We sort the digits from this word into nine ``buckets,'' one for
+each digit:
+
+{\prgex%
+("" "" 3 44 "" 6 77 "" "")
+}
+
+\noindent We see that there are no ones or twos, one three, two fours, and
+so on.  Now we can easily see that four and seven are the pivot squares.
+
+Let's write the procedures to carry out that plan.  {\tt Pivots} has to find
+all the triples with one computer-owned square and two free squares, and
+then it has to extract the square numbers that appear in more than one
+triple.
+
+{\prgex%
+(define (\ufun{pivots} triples me)
+  (repeated-numbers (keep (lambda (triple) (my-single? triple me))
+			  triples)))
+
+(define (\ufun{my-single?} triple me)
+  (and (= (appearances me triple) 1)
+       (= (appearances (opponent me) triple) 0)))
+
+> (my-single? "4x6" 'x)
+#T
+
+> (my-single? 'xo3 'x)
+#F
+
+> (keep (lambda (triple) (my-single? triple 'x))
+	(find-triples 'xo__x___o))
+("4X6" X47 "3X7")
+}
+
+\noindent {\tt My-single?}\ is just like {\tt my-pair?}\ except that it looks
+for one appearance of the letter instead of two.
+
+{\tt Repeated-numbers} takes a sentence of triples as its argument and has
+to return a sentence of all the numbers that appear in more than one
+triple.
+
+{\prgex%
+(define (\ufun{repeated-numbers} sent)
+  (every first
+         (keep (lambda (wd) (>= (count wd) 2))
+	       (sort-digits (accumulate word sent)))))
+}
+
+\noindent We're going to read this procedure inside-out, starting with the
+{\tt accumulate} and working outward.
+
+Why is it okay to {\tt accumulate word} the sentence?  Suppose that a number
+appears in two triples.  All we need to know is that number, not the
+particular triples through which we found it.  Therefore, instead of writing
+a program to look through several triples separately, we can just as well
+combine the triples into one long word, keep only the digits of that word,
+and simply look for the ones that appear more than once.
+
+{\prgex%
+> (accumulate word '("4x6" x47 "3x7"))
+"4X6X473X7"
+}
+
+We now have one long word, and we're looking for repeated digits.  Since
+this is a hard problem, let's start with the subproblem of finding all the
+copies of a particular digit.
+
+{\prgex%
+(define (\ufun{extract-digit} desired-digit wd)
+  (keep (lambda (wd-digit) (equal? wd-digit desired-digit)) wd))
+
+> (extract-digit 7 "4x6x473x7")
+77
+
+> (extract-digit 2 "4x6x473x7")
+""
+}
+
+Now we want a sentence where the first word is all the {\tt 1}s, the second
+word is all the {\tt 2}s, etc.  We could do it like this:
+
+{\prgex%
+(se (extract-digit 1 "4x6x473x7")
+    (extract-digit 2 "4x6x473x7")
+    (extract-digit 3 "4x6x473x7")
+    \ellipsis)
+}
+
+\noindent but that wouldn't be taking advantage of the power of computers to
+do that sort of repetitious work for us.  Instead, we'll use {\tt every}:
+
+{\prgex%
+(define (\ufun{sort-digits} number-word)
+  (every (lambda (digit) (extract-digit digit number-word))
+	 '(1 2 3 4 5 6 7 8 9)))
+}
+
+{\tt Sort-digits} takes a word full of numbers and returns a sentence whose
+first word is all the ones, second word is all the twos, etc.\footnt{Brian
+thinks this is a \idx{kludge}, but Matt thinks it's brilliant and elegant.}
+
+{\prgex%
+> (sort-digits 123456789147258369159357)
+(111 22 333 44 5555 66 777 88 999)
+
+> (sort-digits "4x6x473x7")
+("" "" 3 44 "" 6 77 "" "")
+}
+
+Let's look at {\tt repeated-numbers} again:
+
+{\prgex%
+(define (repeated-numbers sent)
+  (every first
+	 (keep (lambda (wd) (>= (count wd) 2))
+	       (sort-digits (accumulate word sent)))))
+
+> (repeated-numbers '("4x6" x47 "3x7"))
+(4 7)
+
+> (keep (lambda (wd) (>= (count wd) 2))
+	'("" "" 3 44 "" 6 77 "" ""))
+(44 77)
+
+> (every first '(44 77))
+(4 7)
+}
+
+This concludes the explanation of {\tt pivots}.  Remember that {\tt
+i-can-fork?}\ chooses the first pivot, if any, as the computer's move.
+
+\subhd{Taking the Offensive}
+
+Here's the final version of {\tt ttt-choose} with all the clauses shown:
+
+{\prgex%
+(define (\ufun{ttt-choose} triples me)
+  (cond ((i-can-win? triples me))
+        ((opponent-can-win? triples me))
+        ((i-can-fork? triples me))
+        ((i-can-advance? triples me))
+        (else (best-free-square triples))))
+}
+
+\noindent You already know about the first three possibilities.
+
+Just as the second possibility was the ``mirror image'' of the first
+(blocking an opponent's move of the same sort the computer just attempted), 
+it would make sense for the fourth possibility to be blocking the creation
+of a fork by the opponent.  That would be easy to do:
+
+{\prgex%
+(define (opponent-can-fork? triples me)      ;; not really part of game
+  (i-can-fork? triples (opponent me)))
+}
+
+Unfortunately, although the programming works, the strategy doesn't.  Maybe
+the opponent has {\it two\/} potential forks; we can block only one of
+them.  (Why isn't that a concern when blocking the opponent's wins?  It {\it
+is\/} a concern, but if we've allowed the situation to reach the point where
+there are two ways the opponent can win on the next move, it's too late to
+do anything about it.)
+
+Instead, our strategy is to go on the offensive.  If we can get two in a row
+on this move, then our opponent will be forced to block on the next move,
+instead of making a fork.  However, we want to make sure that we don't
+accidentally force the opponent {\it into\/} making a fork.
+
+Let's look at this board position again, but from {\tt o}'s point of view:
+
+\ttboard xo__x___o
+
+\noindent {\tt X}'s pivots are 4 and 7, as we discussed earlier; {\tt o}
+couldn't take both those squares.  Instead, look at the triples {\tt 369}
+and {\tt 789}, both of which are singles that belong to {\tt o}.  So {\tt o}
+should move in one of the squares 3, 6, 7, or 8, forcing {\tt x} to block
+instead of setting up the fork.  But {\tt o} {\it shouldn't\/} move in square
+8, like this:
+
+\ttboard xo__x__oo
+
+\noindent because that would force {\tt x} to block in square 7, setting up
+a fork!
+
+\ttboard xo__x_xoo
+
+The structure of the algorithm is much like that of the other strategy
+possibilities.  We use {\tt keep} to find the appropriate triples, take the
+first such triple if any, and then decide which of the two empty squares in
+that triple to move into.
+
+{\prgex%
+(define (\ufun{i-can-advance?} triples me)
+  (best-move (keep (lambda (triple) (my-single? triple me)) triples)
+             triples
+             me))
+
+(define (\ufun{best-move} my-triples all-triples me)
+  (if (empty? my-triples)
+      #f
+      (best-square (first my-triples) all-triples me)))
+}
+
+\noindent {\tt Best-move} does the same job as {\tt first-if-any}, which we
+saw earlier, except that it also invokes {\tt best-square} on the first
+triple if there is one.  
+
+Since we've already chosen the relevant triples before we get to {\tt
+best-move}, you may be wondering why it needs {\it all\/} the triples as an
+additional argument.  The answer is that {\tt best-square} is going to look
+at the board position from the opponent's point of view to look for forks.
+
+{\prgex%
+(define (\ufun{best-square} my-triple triples me)
+  (best-square-helper (pivots triples (opponent me))
+		      (keep number? my-triple)))
+
+(define (\ufun{best-square-helper} opponent-pivots pair)
+  (if (member? (first pair) opponent-pivots)
+      (first pair)
+      (last pair)))
+}
+
+We {\tt keep} the two numbers of the triple that we've already selected.  We
+also select the opponent's possible pivots from among all the triples.  If
+one of our two possible moves is a potential pivot for the opponent, that's
+the one we should move into, to block the fork.  Otherwise, we arbitrarily
+pick the second ({\tt last}) free square.
+
+{\prgex%
+> (best-square "78o" (find-triples 'xo__x___o) 'o)
+7
+
+> (best-square "36o" (find-triples 'xo__x___o) 'o)
+6
+
+> (best-move '("78o" "36o") (find-triples 'xo__x___o) 'o)
+7
+
+> (i-can-advance? (find-triples 'xo__x___o) 'o)
+7
+}
+
+What if {\it both\/} of the candidate squares are pivots for the opponent?
+In that case, we've picked a bad triple; moving in either square will make
+us lose.  As it turns out, this can occur only in a situation like the
+following:
+
+\ttboard x___o___x
+
+\noindent If we chose the triple {\tt 3o7}, then either move will force the
+opponent to set up a fork, so that we lose two moves later.  Luckily,
+though, we can instead choose a triple like {\tt 2o8}.  We can move in
+either of those squares and the game will end up a tie.
+
+In principle, we should analyze a candidate triple to see if both free
+squares create forks for the opponent.  But since we happen to know that
+this situation arises only on the diagonals, we can be lazier.  We just list
+the diagonals {\it last\/} in the procedure {\tt find-triples}.  Since we
+take the first available triple, this ensures that we won't take a diagonal
+if there are any other choices.\footnt{Matt thinks this is a
+\idx{kludge}, but Brian thinks it's brilliant and elegant.}
+
+\subhd{Leftovers}
+
+If all else fails, we just pick a square.  However, some squares are better
+than others.  The center square is part of four triples, the corner squares
+are each part of three, and the edge squares each a mere two.
+
+So we pick the center if it's free, then a corner, then an edge.
+
+{\prgex\prgexskipamount=10pt%
+(define (\ufun{best-free-square} triples)
+  (first-choice (accumulate word triples)
+		'(5 1 3 7 9 2 4 6 8)))
+
+(define (\ufun{first-choice} possibilities preferences)
+  (first (keep (lambda (square) (member? square possibilities))
+	       preferences)))
+
+> (first-choice 123456789147258369159357 '(5 1 3 7 9 2 4 6 8))
+5
+
+> (first-choice "1xo4x6o8914oxx8o691x9oxo" '(5 1 3 7 9 2 4 6 8))
+1
+
+> (best-free-square (find-triples '_________))
+5
+
+> (best-free-square (find-triples '____x____))
+1
+}
+
+\backskipsubhd{Complete Program Listing}{5}
+
+\medskip
+{\listingskipamount=10pt
+\listing{ttt.scm}}
+
+\esubhd{Exercises}
+
+{\exercise The {\tt ttt} procedure assumes that nobody has won the game
+yet.  What happens if you invoke {\tt ttt} with a board position in which
+some player has already won?  Try to figure it out by looking through the
+program before you run it.
+
+A complete tic-tac-toe program would need to stop when one of the two
+players wins.  Write a predicate {\tt \ufun{already-won?}}\ that takes a
+board position and a letter ({\tt x} or {\tt o}) as its arguments and returns
+{\tt \#t} if that player has already won.
+\extag{\tttwon}
+}
+
+\solution
+
+The {\tt ttt} procedure doesn't notice that someone has already
+won.  When someone wins, they make a triple {\tt xxx} or {\tt
+ooo}.  Since this triple doesn't have any free squares, the {\tt
+ttt} procedure isn't interested in it at all; the triple {\tt xxx}
+is treated the same as the triple {\tt oxx}.  If there are still
+free squares on the board, then the program picks a square as if
+the win hadn't happened.  But if the winning move filled the
+board, then the program crashes because of the same bug that
+affects tie games as described in Exercise 9.2.
+
+{\prgex%
+(define (already-won? position player)
+  (member? (word player player player)
+           (find-triples position)))
+}
+@
+
+{\exercise
+The program also doesn't notice when the game has ended in a tie, that is,
+when all nine squares are already filled.  What happens now if you ask it to
+move in this situation?
+
+Write a procedure {\tt \ufun{tie-game?}}\ that returns {\tt \#t} in this case.
+\extag{\ttttied}
+}
+
+\solution
+{\prgex%
+(define (tie-game? position)
+  (not (member? '_ position)))
+}
+
+As it stands in the book, the {\tt ttt} program generates an error if the
+board is full.  The functions {\tt i-can-win?}, {\tt i-can-fork?}, and {\tt
+i-can-advance?} all return {\tt #f} if the board is full.  {\tt
+Best-free-square} combines all the triples, none of which contain any
+numbers, into one long word, and passes this as the first argument to {\tt
+first-choice}.  None of the letters in {\tt possibilities} are numbers, so
+
+{\prgex%
+(keep (lambda (square) (member? square possibilities))
+      preferences)
+}
+
+\noindent is empty.  We generate an error in trying to take the {\tt first}
+of this empty sentence.
+@
+
+{\exercise
+A real human playing tic-tac-toe would look at a board like this:
+
+{\parindent=20pt
+
+\ttboard oxooxxxo_
+
+}
+
+\noindent and notice that it's a tie, rather than moving in square {\tt 9}.
+Modify {\tt tie-game?}\ from Exercise \ttttied\ to notice this situation and
+return {\tt \#t}.
+
+(Can you improve the program's ability to recognize ties even further?
+What about boards with two free squares?)
+}
+
+\solution
+{\prgex%
+(define (tie-game? position)
+  (empty? (keep winnable? (find-triples position))))
+
+(define (winnable? triple)
+  (or (not (member? 'x triple))
+      (not (member? 'o triple))))
+}
+
+\noindent (If you didn't think of looking at the triples, but instead
+tried to examine the position directly, the problem is a lot harder
+because it requires looking at several special cases, such as a board
+with no free squares, a board with one free square, and so on.)
+@
+
+{\exercise
+Here are some possible changes to the rules of tic-tac-toe:
+
+\smallskip
+{\parindent=1em\everypar={}
+\bb What if you could
+win a game by having three squares forming an L shape in a corner, such
+as squares 1, 2, and 4?
+
+\bb What if the diagonals didn't win?
+
+\bb What if you could win by having {\it four\/}
+squares in a corner, such as 1, 2, 4, and 5?
+
+}\smallskip
+
+Answer the following questions for each of these modifications separately:
+What would happen if we tried to implement the change merely by changing the
+quoted sentence of potential winning combinations in {\tt find-triples}?
+Would the program successfully follow the rules as modified?
+}
+
+\solution
+If the winning combinations were all still three squares, then none of the
+functions in the program would blow up.  There is a possible subtle strategy
+problem, though, because of the kludgy way in which {\tt best-move}
+relies on the ordering of triples in {\tt find-triples}.  It's important to make
+sure the best triples still come first.  This is the kind of bug that's very
+difficult to track down, because the problem has to do with the handling of
+pivots and  you'd never think that {\tt find-triples} was
+responsible for the pivot choosing algorithm.
+
+If the diagonals didn't win, then again nothing would break.  In
+fact, that would eliminate the program's reliance on keeping the
+triples in a particular order, because the case in which creating
+a fork can lose the game wouldn't exist.
+
+If a ``triple'' could have more than three squares in it, then lots of
+things would break.  For example, {\tt i-can-win?} depends on {\tt my-pair?},
+which has the number 2 built into it.
+@
+
+{\exercise
+Modify {\tt ttt} to play chess.
+}
+
+\solution
+{\prgex%
+(define (chess position me)
+  (if (= (random 1) 0)
+      '(i give up)
+      'checkmate!))
+}
+@
+
+\catcode`\_=8
+\bye