Note: References to “the computer” or “the player” are interchangeable and refer to whatever side the ttt
procedure will act on behalf of. References to a “mark” are references to an x or o, which I think of as marks that a player makes on a tictactoe board.
For this chapter we’re loading ttt.scm
. It’s a TicTacToe program that takes the following arguments: the current game board state (in the form of a word like '__o_xox_x
, where each character corresponds to a position on the game board) and whether the computer is playing x
or o
.
For this chapter I quoted heavily and made comments on the quoted material as I went along.
Here’s how the board locations are numbered:
When referring to “triples” like 159 below, I’m using this numbering of the spaces.
Here’s the board state that '__o_xox_x
corresponds to:
Strategy
The focus of the chapter is on strategy. Tictactoe is a fairly simple game strategically – perfect play is easily doable. The book lays out the following first draft implementation of strategy:
1
2
3
4
5
6
7
8
9

(define (ttt position me) ;; first version
(cond ((icanwin?)
(choosewinningmove))
((opponentcanwin?)
(blockopponentwin))
((icanwinnexttime?)
(preparewin))
(else (whatever))))

This lacks a bunch of detail like arguments, and is more in the vein of a pseudocode roadmap for what we want to do.
Triples
You win tictactoe by getting three of the same value (x’s or o’s) in a row, so these triples (159, 357, 123, 456, 789, 147, 258, 369) are key.
So we want to a list of triples and the current board position and put that information together somehow so that we can determine what the next move should be.
Our program will start with this sentence of all the winning combinations:
1
2

(123 456 789 147 258 369 159 357)

and a position word such as
_xo_x_o__
; it will return a sentence of triples such as
1
2

(1xo 4x6 o89 14o xx8 o69 1x9 oxo)

All that’s necessary is to replace some of the numbers with
x
s ando
s. This kind of wordbyword translation in a sentence is a good job forevery
.
1
2
3

(define (findtriples position) ;; first version
(every substitutetriple '(123 456 789 147 258 369 159 357)))

substitutetriple
, which we haven’t written yet, will take 3 digits from our list of triples and make the appropriate substitutions with the information from position
. (Note that substitutetriple
isn’t currently being passed position
as an argument).
substitutetriple
will have a procedure called substituteletter
which does the actual substitution of the letters:
1
2
3

(define (substitutetriple combination) ;; first version
(every substituteletter combination))

We want triples to be words, not sentences like (2 x 8)
, so substitutetriple
should return words:
1
2
3

(define (substitutetriple combination) ;; second version
(accumulate word (every substituteletter combination)))

(This process of iterating on a program to get it closer to what we want to do is fun).
Substituteletter
knows that letter number 3 of the word that represents the board corresponds to the contents of square 3 of the board.
Hmm not currently sure how it knows that.
This means that it can just call
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.
1
2
3
4
5

(define (substituteletter square) ;; first version
(if (equal? '_ (item square position))
square
(item square position)))

Whoops! Do you see the problem?
1
2
3

> (substituteletter 5)
ERROR: Variable POSITION is unbound.

This is the same issue I was worrying about earlier.
Using Every
with TwoArgument Procedures
Our procedure only takes one argument,
square
, but it needs to know the position so it can find out what’s in the given square. So here’s the realsubstituteletter
:
1
2
3
4
5
6
7
8
9
10
11

(define (substituteletter square position)
(if (equal? '_ (item square position))
square
(item square position)))
> (substituteletter 5 '_xo_x_o__)
X
> (substituteletter 8 '_xo_x_o__)
8

Now
substituteletter
can do its job, since it has access to the position. But we’ll have to modifysubstitutetriple
to invokesubstituteletter
with two arguments.
Right. This is the thing I was wondering about earlier. Since substitutetriple
calls substituteletter
, we’ve got to give substitutetriple
access to position
. Are we gonna use a lambda
or let
or something perhaps?
This is a little tricky. Let’s look again at the way we’re using
substituteletter
insidesubstitutetriple
:
1
2
3

(define (substitutetriple combination) ;; second version again
(accumulate word (every substituteletter combination)))

By giving
substituteletter
another argument, we have made this formerly correct procedure incorrect. The first argument toevery
must be a function of one argument, not two. This is exactly the kind of situation in whichlambda
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.
🤔 I’m not 100% sure I follow this part. Is substituteletter
only a function of one argument in the lambda
below? It seems like it’s still taking two arguments.
The procedure returned by
1
2

(lambda (square) (substituteletter square position))

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 ofsubstitutetriple
:
1
2
3
4
5
6
7
8
9
10
11
12
13

(define (substitutetriple combination position)
(accumulate word
(every (lambda (square) (substituteletter square position)) combination)))
> (substitutetriple 456 '_xo_x_o__)
"4X6"
> (substitutetriple 147 '_xo_x_o__)
"14O"
> (substitutetriple 357 '_xo_x_o__)
OXO

Ok so summing up in my own words so far:
substituteletter
takes a square
and state of the game (called position
). It uses item
plus the number of the square
to determine whether a particular square is empty (which is represented by an underscore character _
.) If the square is empty, the number of the square is returned (so in the example with the arguments 456 '_xo_x_o__)
, as the 4 square is empty, 4X6 is returned.) If the square is not empty, the x or o value of the square is returned.
substitutetriple
applies substituteletter
to each square
in a triple and then accumulates the result in a word. The lambda
returns a procedure that runs the substituteletter
procedure on a particular square. The every
procedure applies these lambda
procedures to each digit of a particular combination
(such as “456”), and returns the result in sentence form, and then the sentence results are accumulated into words.
We’ve fixed the
substituteletter
problem by givingsubstitutetriple
an extra argument, so we’re going to have to go through the same process withfindtriples
. Here’s the right version:
1
2
3
4

(define (findtriples position)
(every (lambda (comb) (substitutetriple comb position))
'(123 456 789 147 258 369 159 357)))

It’s the same trick.
Substitutetriple
is a procedure of two arguments. We uselambda
to transform it into a procedure of one argument for use withevery
.
Thinking about this issue some more…position
is fixed but comb
varies. Like the every
will provide the lambda
here with 123
as the comb
and 456
and so on. And the lambda
only has one formal parameter defined. I’m not sure which of those is the critical decisive factor in terms of what lets us say that the lambda
is now a oneargument function but I can maybe see the idea a bit.
Wait…I was looking at how the unnamed procedure is defined (in terms of another procedure) and looking at the number of arguments the procedure inside the lambda took, rather than thinking about what arguments the lambda was taking (namely, the one parameter defined for each lambda)
We’ve now finished
findtriples
, one of the most important procedures in the game.
1
2
3
4

> (findtriples '_xo_x_o__)("1XO" "4X6" O89 "14O" XX8 O69 "1X9" OXO)
> (findtriples 'x_____oxo)(X23 456 OXO X4O "25X" "36O" X5O "35O")

Can the Computer Win on This Move?
Finally, the computer can win if it owns any of the triples:
1
2
3
4
5
6

(define (icanwin? triples me) ;; firstversion (not (empty? (keep (lambda (triple) (mypair? triple me)) triples))))
> (icanwin? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'x)
#T
> (icanwin? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'o)
#F

the not (empty?
part causes the procedure to return true if there are any triples the computer “owns”.
If So, in Which Square?
Suppose
icanwin?
returns#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:
123 (define (choosewinningmove triples me) ;; not really part of game(keep number? (first (keep (lambda (triple) (mypair? triple me)) triples))))
This would keep
the number from a triple that can be won on the next move. Since the number represents the fact that a square is not occupied by an x or o, then that number represents the square where a winning move can be made.
We again use
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.
Right.
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 kludge to get around it.
Remember we told you that everything other than#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#f
otherwise.
Ok that makes sense as a solution.
In Chapter 6 we called such a procedure a “semipredicate.” The kludgy part is that
cond
accepts a clause containing a single expression instead of the usual two expressions; if the expression has any true value, thencond
returns that value. So we can say
1234 (define (tttchoose triples me)(cond ((icanwin? triples me)((opponentcanwin? triples me)) …))where each
cond
clause invokes a semipredicate.
I was unclear on this point so I wound up trying to explain it at length.
So normally a cond
expression looks something like this
1
2
3
4
5
6
7
8
9
10

(define (romanvalue letter)
(cond (equal? letter 'i) 1)
(equal? letter 'v) 5)
(equal? letter 'x) 10)
(equal? letter 'l) 50)
(equal? letter 'c) 100)
(equal? letter 'd) 500)
(equal? letter 'm) 1000)
else 'huh?))

in this we see two distinct expressions – for example, (equal? letter 'i)
and 1
. The second expression is returned if the condition in the first expression is met.
However, earlier, in chapter 6, the book authors did give us the following warning:
Don’t get into bad habits of thinking about the appearance of
cond
clauses in terms of “two parentheses in a row.” That’s often the case, but not always. For example, here is a procedure that translates Scheme true or false values (#t
and#f
) into more humanreadable wordstrue
andfalse
.
1
2
3
4
5
6
7
8
9

(define (truefalse value)
(cond (value 'true)
(else 'false)))
> (truefalse (= 2 (+ 1 1)))
TRUE
> (truefalse (= 5 (+ 2 2)))
FALSE

The meaning of (value 'true)
is basically “If value
is #t
, return 'true
.” Because Scheme defaults to treating stuff as true unless it’s false, then if value
has any nonfalse value, truefalse
will return #t
. And this is accomplished inside a single set of parentheses. However, even with truefalse
, there is still a separation between the thing being evaluated and the thing being returned. In other words, value
is the thing that is getting evaluated for its truth value, and 'true
is the thing being returned if the evaluation of value
is #t
.
With the proposed changes to our tictactoe program, (icanwin? triples me)
will return a single value that will 1) provide the truth value that is evaluated as true or false for the purposes of the cond
expression and 2) provide additional information (besides merely being true or false) when returning a true value (namely, it will return the number of the square that provides the winning move).
We then modify
icanwin?
to have the desired behavior:
1
2
3
4
5
6
7
8
9
10
11
12
13

(define (icanwin? triples me)
(choosewin (keep (lambda (triple) (mypair? triple me)) triples)))
(define (choosewin winningtriples)
(if (empty? winningtriples)
#f
(keep number? (first winningtriples))))
> (icanwin? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'x)
8
> (icanwin? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'o)
#F

mypair?
takes a triple and the computer’s mark (x
or o
) as arguments and then determines whether a triple has 2 appearances of the computer’s marks and 0 appearances of the opponent’s marks.
icanwin?
takes the existing set of triples (based on the current game state) and the computer’s mark as arguments and then invokes choosewin
. The list of all triples is filtered by the operation of a lambda
function in conjunction with keep
. The lambda
determines whether a particular triple is “owned” by the computer using mypair?
. If a triple is “owned” by the computer, then that satisfied the mypair
predicate and it is kept and passed to choosewin
.
choosewin
takes a list of winning triples as arguments. If the list is empty, it returns #f
. Otherwise, it keeps and returns the number that is present in the first winning triple.
Second Verse, Same as the First
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 letterbut it’s already done!
1
2
3
4
5
6
7
8

(define (opponentcanwin? triples me) (icanwin? triples (opponent me)))
> (opponentcanwin? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo)
'x)
#F
> (opponentcanwin? '("1xo" "4x6" o89 "14o" xx8 o69 "1x9" oxo) 'o)
8

Is that amazing or what?
the opponent
procedure returns the other mark (x or o) from whatever the computer’s mark is, and a lot of our work can work fine with either side so that saves us a lot of work.
Finding the Pivots
Pivots
should return a sentence containing the pivot numbers. Here’s the plan. We’ll start with the triples:
1
2

(xo3 4x6 78o x47 ox8 36o xxo 3x7)

We
keep
the ones that have anx
and two numbers:
1
2

(4x6 x47 3x7)

Right, these are our candidates for potentially finding pivots. And we already dealt with the 2 x’s case earlier with icanwin?
.
We mash these into one huge word:
1
2

4x6x473x7

We sort the digits from this word into nine “buckets,” one for each digit:
1
2

("" "" 3 44 "" 6 77 "" "")

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.
Right. The repeated appearance of a number in triples where our mark appearances once indicates a pivot.
Let’s write the procedures to carry out that plan.
Pivots
has to find all the triples with one computerowned square and two free squares, and then it has to extract the square numbers that appear in more than one triple.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(define (pivots triples me)
(repeatednumbers
(keep (lambda (triple) (mysingle? triple me)) triples)))
(define (mysingle? triple me)
(and (= (appearances me triple) 1)
(= (appearances (opponent me) triple) 0)))
> (mysingle? "4x6" 'x)
#T
> (mysingle? 'xo3 'x)
#F
> (keep (lambda (triple) (mysingle? triple 'x))(findtriples 'xo__x___o))
("4X6" X47 "3X7")

Mysingle?
is just likemypair?
except that it looks for one appearance of the letter instead of two.
Makes sense. And then the lambda
in pivots
checks if a particular triple is returns true for mysingle?
, and a list of triples that meet that criteria is returned to repeatednumbers
for further processing.
Repeatednumbers
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.
1
2
3
4

(define (repeatednumbers sent)
(every first
(keep (lambda (wd) (>= (count wd) 2)) (sortdigits (accumulate word sent)))))

We’re going to read this procedure insideout, starting with the
accumulate
and working outward.
Why is it okay toaccumulate 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.
Right that makes sense.
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.
1
2
3

> (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.
Seems like maybe you could use appearances
somehow perhaps?
1
2
3
4
5
6
7
8

(define (extractdigit desireddigit wd)
(keep (lambda (wddigit) (equal? wddigit desireddigit)) wd))
> (extractdigit 7 "4x6x473x7")
77
> (extractdigit 2 "4x6x473x7")
""

Ok so what this appears to do is check the word with the digits for the presence of a desired digit. Specifically, the lambda
checks to see if a digit is in the digitword is equaled to the desired digit. If so, it returns all instances of that digit.
Now we want a sentence where the first word is all the
1
s, the second word is all the2
s, etc. We could do it like this:
1
2

(se (extractdigit 1 "4x6x473x7") (extractdigit 2 "4x6x473x7")(extractdigit 3 "4x6x473x7")…)

that looks inelegant!
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
every
:
1
2
3
4

(define (sortdigits numberword)
(every (lambda (digit) (extractdigit digit numberword))
'(1 2 3 4 5 6 7 8 9)))

So this program has a lambda
which takes a digit and numberword and returns the digit the same number of times it appears in numberword
. numberword
is an argument from sortdigits
and the digit
is provided by the '(1 2 3 4 5 6 7 8 9)
sentence. every
applies the lambda to every digit of the '(1 2 3 4 5 6 7 8 9)
sentence and returns a sentence with all the copies of the extracted digits.
Sortdigits
takes a word full of numbers and returns a sentence whose first word is all the ones, second word is all the twos, etc.[2]
1
2
3
4
5

> (sortdigits 123456789147258369159357)
(111 22 333 44 5555 66 777 88 999)
> (sortdigits "4x6x473x7")
("" "" 3 44 "" 6 77 "" "")

what’s with the 5 ""
‘s? I thought maybe it was related to the x
‘s but there are only 3 of those.
Let’s look at
repeatednumbers
again:
1
2
3
4
5
6
7
8
9
10
11

(define (repeatednumbers sent)
(every first
(keep (lambda (wd) (>= (count wd) 2)) (sortdigits (accumulate word sent)))))
> (repeatednumbers '("4x6" x47 "3x7"))
(4 7)
> (keep (lambda (wd) (>= (count wd) 2))'("" "" 3 44 "" 6 77 "" ""))
(44 77)
> (every first '(44 77))
(4 7)

So repeatednumbers
takes a sentence of triples. It has to return a sentence of all the numbers that appear in more than one triple.
sortdigits
accumulates a word from the triples and then sorts the numbers and groups instances of the same number that appear more than once together as words within a sentence.
The keep (lambda (wd)...
bit keeps all the words within the sentence created by sortdigits
that appear at least twice (which indicates a pivot)
Then everyfirst
returns only the first digit of each pivotword.
This concludes the explanation of
pivots
. Remember thaticanfork?
chooses the first pivot, if any, as the computer’s move.
Taking the Offensive
Here’s the final version of
tttchoose
with all the clauses shown:
1
2
3
4
5
6
7

(define (tttchoose triples me)
(cond ((icanwin? triples me))
((opponentcanwin? triples me))
((icanfork? triples me))
((icanadvance? triples me))
(else (bestfreesquare triples))))

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:
1
2
3

(define (opponentcanfork? triples me) ;; not really part of game
(icanfork? triples (opponent me)))

Unfortunately, although the programming works, the strategy doesn’t. Maybe the opponent has two potential forks;
🤔 What would two potential forks look like?
we can block only one of them. (Why isn’t that a concern when blocking the opponent’s wins? 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 into making a fork.
Ok, so there are two steps: get two in row, but make sure that doing so doesn’t force the opponent into making a fork. If you get two in a row, and then the opponent blocks you with a move that makes a fork, then that’s a kinda pyrrhic victory. The opponent will block you so you won’t win, and then you won’t be able to stop the opponent from winning. So you can’t just look at the game next moves from your point of view but need to look at them from the opponent’s point of view.
Let’s look at this board position again, but from
o
‘s point of view:
The board position here is ‘xo__x___o
X
‘s pivots are 4 and 7, as we discussed earlier;o
couldn’t take both those squares. Instead, look at the triples369
and789
, both of which are singles that belong too
. Soo
should move in one of the squares 3, 6, 7, or 8, forcingx
to block instead of setting up the fork. Buto
shouldn’t move in square 8, like this:
because that would force
x
to block in square 7, setting up a fork!
So o wants to make sure that a move doesn’t put x in an icanfork?
position.
The structure of the algorithm is much like that of the other strategy possibilities. We use
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.
1
2
3

(define (icanadvance? triples me)
(bestmove (keep (lambda (triple) (mysingle? triple me)) triples) triples me))

getting a little overwhelmed by all the procedures so I’m making trees to help me understand them.
For the board state 'xo__x___o
mentioned above, for the following input:
1
2

(icanadvance? (findtriples 'xo__x___o) 'o)

the value returned is 7
(note that I used findtriples
so I could test this part of the procedure separately.)
1
2
3
4

(define (bestmove mytriples alltriples me)
(if (empty? mytriples) #f
(bestsquare (first mytriples) alltriples me)))

Bestmove
does the same job asfirstifany
, which we saw earlier, except that it also invokesbestsquare
on the first triple if there is one.
Since we’ve already chosen the relevant triples before we get tobestmove
, you may be wondering why it needs all the triples as an additional argument. The answer is thatbestsquare
is going to look at the board position from the opponent’s point of view to look for forks.
Right okay. The triples that are relevant from our side’s perspective don’t address the issue of what potential moves the other player might make.
1
2
3
4
5
6
7
8
9

(define (bestsquare mytriple triples me)
(bestsquarehelper (pivots triples (opponent me)) (keep number? mytriple)))
(define (bestsquarehelper opponentpivots pair)
(if (member? (first pair) opponentpivots)
(first pair)
(last pair)))

We
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.
Right okay, and that’s what (if (member? (first pair) opponentpivots)
is doing – checking the two numbers of our triple against the opponent’s pivots.
Otherwise, we arbitrarily pick the second (
last
) free square.
1
2

> (bestsquare "78o" (findtriples 'xo__x___o) 'o)7> (bestsquare "36o" (findtriples 'xo__x___o) 'o)6> (bestmove '("78o" "36o") (findtriples 'xo__x___o) 'o)7> (icanadvance? (findtriples 'xo__x___o) 'o)7

What if 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:
If we chose the triple
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 like2o8
. 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 last in the procedurefindtriples
. Since we take the first available triple, this ensures that we won’t take a diagonal if there are any other choices.
Ah that’s clever.
Exercises
❌ Exercise 10.1
The
ttt
procedure assumes that nobody has won the game yet. What happens if you invokettt
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.
So I think looking through the main cond
in tttchoose is a reasonable way to organize my answer to this:
1
2
3
4
5
6
7

(define (tttchoose triples me)
(cond ((icanwin? triples me))
((opponentcanwin? triples me))
((icanfork? triples me))
((icanadvance? triples me))
(else (bestfreesquare triples)) ))

icanwin?
‘s helper procedure mypair?
looks for triples where the number of appearances of the computer’s marks is exactly 2. So I don’t think icanwin
would “catch” a winning board position.
icanfork?
‘s helper procedure mysingle?
triples with 1 appearance of the opponent’s marks, so likewise it won’t “catch” the 3 case.
icanadvance?
also relies on mysingle?
, so the same logic applies.
So I think maybe tttchoose
would default to using bestfreesquare
. I’m lowconfidence on this though.
UPDATE: I tried playing with it some and it seemed to just recommend that I make moves without acknowledging that victory had occurred. By the way, I realized that depending on the game board, the program might actually find triples that meet the criteria of the strategy other than the “winning” triple. So basically my updated guess is that the program would analyze the game state as normal without taking into account the fact that there was a winner.
SECOND UPDATE: I missed the fact mentioned by AnneB that the program will return an error if there are no empty square
A complete tictactoe program would need to stop when one of the two players wins. Write a predicate
alreadywon?
that takes a board position and a letter (x
oro
) as its arguments and returns#t
if that player has already won.
I used modifications of existing stuff in ttt
and built on top of the existing program some. So note, this is intended to be run as an addition to the ttt
program. It particular relies on findtriples
, substitutetriple
, and substituteletter
and can be run just with those parts.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

(define (alreadywon? position me)
(ihavewon (findtriples position) me))
(define (mywin? triple me)
(and (= (appearances me triple) 3)))
(define (ihavewon triples me)
(returntrueifwinner
(keep (lambda (triple) (mywin? triple me))
triples)))
(define (returntrueifwinner winningtriples)
(if (not (empty? winningtriples))
#t #f))

alreadywon?
invokes ihavewon
and generates the triples using findtriples
.
ihavewon
invokes choosewinner
and uses mywin?
to filter the triples for winning triples.
mywin?
looks for triples where there are 3 appearances of the computer’s mark. There’s no checking for the opponent’s mark, because if there are actually 3 of the computer’s mark then you know the opponent’s mark number is 0.
returntrueifwinner
returns #true
if there are any winning triples (meaning triples where we’ve already won).
This program appears to work:
Ok so solves the problem but is wildly overcomplicated. Here’s buntine’s effort for comparison:
1
2
3
4

(define (alreadywon? position letter)
(member? (word letter letter letter)
(findtriples position)))

So this checks whether a word consisting of the letter three times is a member of the list of triples generated by (findtriples position)
. Very easy!
Here’s AnneB’s:
1
2
3
4
5

(define (alreadywon? position me)
(not (empty?
(keep (lambda (triple)
(equal? (word me me me) triple)) (findtriples position)))) )

I’m going to go through Anne’s procedure and then compare my procedure and Anne’s procedure.
Anne’s procedure works as follows:
The lambda
checks whether a particular triple is equal to three instances of the computer’s mark me
. This would indicate a winning triple. keep
tests each triple generated by findtriples
for whether it is true for (equal? (word me me me)
, and if the list of triples generated by keep
is not
empty?
(indicating that there is at least one winning triple) then the whole procedure returns as true.
my mywin?
procedure somewhat parallels the functionality of Anne’s (equal? (word me me me)
in that the point is to check for three instances of the me
letter.
My returntrueifwinner
somewhat parallels the (not (empty?
part of Anne’s procedure, although Anne returns the truth values directly using not
rather than needing to use an if
statement.
My ihavewon
procedure parallels the part of Anne’s procedure starting at the keep
. This seems like the part of my procedure that would be easiest to turn into something more elegant.
✅❌ Exercise 10.2
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?
❌ (forgot to answer this part of the question at first): You get an error.
Write a procedure
tiegame?
that returns#t
in this case.
Here’s one solution (which makes use of the opponent
procedure from ttt
, although you could also just specify x and o)
1
2
3
4

(define (tiegame? position letter)
(equal? (+ (appearances letter position)(appearances (opponent letter) position))
9))

It checks if the number of appearances of the computer’s letter and the opponent’s letter total to 9.
Here’s another solution (from buntine), which doesn’t make use of letter
:
1
2
3

(define (tiegame2? position)
(not (member? '_ position)))

AnneB’s solution, which actually incorporates an alreadywon?
check, is better:
1
2
3
4
5

(define (tiegame? position)
(and (not (alreadywon? position ‘x))
(not (alreadywon? position ‘o))
(fullsquares? position) ))

Exercise 10.3
A real human playing tictactoe would look at a board like this:
and notice that it’s a tie, rather than moving in square
9
. Modifytiegame?
from Exercise 10.2 to notice this situation and return#t
.
Ok. A situation like the above always involves the following two things:
 There is exactly one space free
 The triples involving that space (in the above, 149, 369, and 789) have one x and one o respectively (so that neither side can actually win). If there was only one space free but one of the triples with that space had 2 appearances of the same letter, then that would mean we had a potentially winning move on our hands and not a tie.
So let’s think about this in terms of tiegame?
. We want tiegame?
to notice that there’s only one free space left. We also want it to notice that nobody can win by occupying that free space. So those are two separate requirements for tiegame?
. The one free space one seems easiest, so we’ll start with that one:
1
2
3

(define (tiegame? position letter)
(equal? (appearances '_ position) 1))

One way to approach this problem is to create and compare filtered lists of triples. We can use one function, freespaceispresent?
, to generate a list of all the triples in which the free space is present. We can use another function, tripleistie?
, to generate a list of all the triples which fit the criteria for being a tie. If the board situation is truly one where a tie is inevitable, then the number of triples fitting both criteria should be identical. If one or another of the lists weren’t identical, that might indicate e.g. that there was a triple which included the free space and which did not fit the criteria for a tie (in other words, a potentially winning move).
We can say that a particular triple indicates a tie when all of the following conditions are met:
 We know there is only one free space left in the board
 A triple generated by
findtriples
has a number value and not just x’s or o’s (this indicates that that particular triple has the free space), and  A triple generated by
findtriples
has no more than one appearance of the computer’s mark (if it had 2, that would indicate a potentially winning move that the computer could make. If there’s only one free space left, then the opponent’s number of marks in a triple with the free space doesn’t matter)
A triple meeting 2 and 3 while 1 is true means that the free space in the triple can no longer be used to win by either side.
Since I want to ensure that 1 is true, I restructure (equal? (appearances '_ position) 1))
within an if
. If (equal? (appearances '_ position) 1))
, then the other stuff will be analyzed (and possibly return true or false). Otherwise the procedure will return false.
I also want to still cover the case where all there are no free spaces.
So I nest my more complex analysis as the alternative within an if
statement that first checks whether 0 spaces are free:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

(define (tiegame? position letter)
(if (not (member? '_ position)) #t
(if (equal? (appearances '_ position) 1)
(equal?
(count
(keep
(lambda (triple)
(freespaceispresent? triple letter))
(findtriples position)))
(count
(keep
(lambda (triple)
(tripleistie? triple letter))
(findtriples position))))
#f)))

After doing the problems above, I refactored my program as follows and added testing for alreadywon?
:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

; newer version
(define (alreadywon? position letter)
(member? (word letter letter letter)
(findtriples position)))
(define (tiegame? position letter)
(and (not (alreadywon? position letter))
(not (alreadywon? position (opponent letter)))
(equal?
(count
(keep
(lambda (triple)
(freespaceispresent? triple letter))
(findtriples position)))
(count
(keep
(lambda (triple)
(tripleistie? triple letter))
(findtriples position))))))

Here are some tests I ran:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

(tiegame? 'xoxoxoxo_ 'x)
;f  x won
;xox
;oxo
;xo_
(tiegame? 'xoxoxoo__ 'x)
;#f  x can win
;xox
;oxo
;o__
(tiegame? 'xoxxooox_ 'o)
;t  o can't win
;xox
;xoo
;ox_
(tiegame? 'oxoxoxxo_ 'o)
;f  o can win
;oxo
;xox
;xo_
(tiegame? 'oxoxoxoxo 'o)
;#f  o won
;oxo
;xox
;oxo
(tiegame? 'xoxoxoxo_ 'o)
;#f  opponent x won
;xox
;oxo
;xo_

For the first four tests, both versions produce the same result. For the final two tests, only the newer version produces the correct output. For the fifth test, I think that the new version of the procedure finds that the 159 triple has won and so (not (alreadywon? position letter))
correctly fails. For the sixth test, I think that the newer verison of the procedure correctly finds that the (not (alreadywon? position (opponent letter)))
test fails due to x
having won with triple 357.
(Can you improve the program’s ability to recognize ties even further? What about boards with two free squares?)
Let’s look at a scenario where there’s a tie. Assume the following board state, and o is going to move next:
‘xoxoox_x_ ‘o
xox
oox
_x_
o has no winning moves and can block x from winning by placing a square at 9. So this game has already deadlocked and should return true.
Here’s another case:
‘_oxxxoox_ ‘o
_ox
xxo
ox_
x can’t win if o moves in any of the remaining free spaces. o can’t win either.
One thing we haven’t done is figure out a way to update position
based on a move, which I think would be essential for implementing this approach. So let’s try seeing if we can do that.
We want a procedure that can take a board position
and player’s mark, figure out what move to make, and then update position
.
So basically it would run ttt
, take the value from that, and update the position
based on the value. Whatever player’s mark was, it would replace that value in position
.
Here’s my solution to this problem:
1
2
3
4
5

(define (positionupdater position me)
(accumulate word (every (lambda (digit)
(if (equal? digit (ttt position me)) me (item digit position)))
'(1 2 3 4 5 6 7 8 9))))

I am borrowing heavily from the structure of the sortdigits
procedure here. My procedure has a lambda
which checks if a digit from a list of 1 through 9 is equal to the square returned by calling ttt
on the current board state and with the player’s mark (x or o). If so, the player’s mark is returned. If not, a character representing the current board state (x, o, or _ indicating empty) is returned. every
does this for 9 digits, representing 9 squares of the board, and returns a sentence. This sentence is then accumulated into a word in order to be in the original form of position
.
I realized when I was working on this problem that my previous iteration of tiegame
had an issue. For the two cases of facing a tie game two moves out that I mentioned above, 'xoxoox_x_ 'o
and '_oxxxoox_ 'o
respectively, my current tiegame?
procedure returns #t
. I want it to return #t
ultimately after I make certain adjustments to handle the twospacesout case, but it shouldn’t be returning #t
yet. So let’s see if we can fix that before we add further layers of complexity.
1
2
3
4
5
6
7
8
9
10
11
12

(define (tiegame? position letter)
(and (not (alreadywon? position letter))
(not (alreadywon? position (opponent letter)))
(and (equal? (appearances '_ position) 1)
(equal?
(count (keep (lambda (triple)
(freespaceispresent? triple letter))
(findtriples position)))
(count (keep (lambda (triple)
(tripleistie? triple letter))
(findtriples position)))))))

I’ve added (and (equal? (appearances '_ position) 1)
and that flips my two new test cases to false, as desired.
I’m also wondering if there is some way to simplify the program here along the lines I figured out already when trying to have the program handle two free spaces.
Oh. So if there is one free space, and the player can’t win, and the opponent has not already won, then that’s a tie. We’re already always checking for whether the opponent has already won, because we want to know whether either player has won regardless of whether there’s 4 free moves left or 0. So I think in the case where there is one free space left, we just need to check for whether the player will have already won after making the best move!
1
2
3
4
5
6

(define (tiegame? position letter)
(and (not (alreadywon? position letter))
(not (alreadywon? position (opponent letter)))
(and (equal? (appearances '_ position) 1)
(not (alreadywon? (positionupdater position letter) letter)))))

Ok, now we’ve got the 0 and 1 free space cases handled more elegantly!
Now to go to two spaces. Wait, first, I think since we’re handling more cases, we might want to go to a cond
expression. Let me translate what I have into that first.
Let’s think about this. So if someone’s already won, that’s always going to be a nottie situation, so that can go first, and we want to return false for tiegame?
in that case.
1
2
3
4

(define (tiegame? position me)
(cond (or ((alreadywon? position me)
(alreadywon? position (opponent me))) #f)...

Next, I think we want to test the two free spaces case. My intuition is that if the program can see that the game is a tie two spaces out, we don’t need to worry about testing the one free space case. The one free space case is like a subset of the two free spaces case. So we can just stop there and return false.
So one way to think of the two free spaces case is in terms of the following questions:
1. Can the player win?
2. Supposing that the player makes the best move regardless of whether they can win or not, can the opponent win?
So what you’d want to do to check for a tiegame two spaces out is to first see if the player can win, which is something we can already ask using our existing tools. Then look at the game from the opponent’s perspective but with the assumption that the player has made the best possible move in their next move, and then ask if the opponent can win. If the player can win, or the opponent can win, then the game is not tied, and this part of the procedure should return #f.
1
2
3
4
5
6
7

(define (tiegame? position me)
(cond ((or (alreadywon? position me)
(alreadywon? position (opponent me))) #f)
((and (equal? (appearances '_ position) 2)
(or (icanwin? (findtriples position) me)
(opponentcanwin? (findtriples (positionupdater position me)) me))) #f)...

A thought occurs to me. Since we have something that can “look ahead” and judge ties with two free spaces, do we need to address 1 free space case specifically?
Another way of asking this question: are ties with one free space left a perfect subset of ties with two free spaces left?
I think one free space ties are not a perfect subset of twospace ties, and so we do need to test the 1 free space case separately. Why? Because one of the assumptions we make for the player’s move when testing whether there is a tie two free spaces out is that they make the best possible move. However, it is possible that the player fails to make the best possible move, and that that creates a tiegame situation due to the error of the player. So I think we want to test for that possibility.
I also realized a better way to test for this case. Just ask: is it true that the number of free spaces is equal to 1 and that player can win? If so, that’s not a tiegame, so return false. Since we’ve already asked if opponent has already won, we just need to know whether player 1 can win.
1
2
3
4
5
6
7
8
9

(define (tiegame? position me)
(cond ((or (alreadywon? position me)
(alreadywon? position (opponent me))) #f)
((and (equal? (appearances '_ position) 2)
(or (icanwin? (findtriples position) me)
(opponentcanwin? (findtriples (positionupdater position me)) me))) #f)
((and (equal? (appearances '_ position) 1) (icanwin? (findtriples position) me)) #f)
(else #t)))

After glancing at buntine’s answer, I added a let statement to clean things up a bit:
1
2
3
4
5
6
7
8
9
10
11

(define (tiegame? position me)
(let ((underscores (appearances '_ position)))
(cond ((or (alreadywon? position me)
(alreadywon? position (opponent me))) #f)
((and (= underscores 2)
(or (icanwin? (findtriples position) me)
(opponentcanwin? (findtriples (positionupdater position me)) me))) #f)
((and (= underscores 1) (icanwin? (findtriples position) me)) #f)
(else #t))))

I also noticed that neither buntine nor AnneB specified which player was making the next move for their versions of tiegame
. I’m not quite sure if I made a mistake in doing so/if that was unnecessary to do on my part.
In the way I’ve currently structured the program, except for the check for whether either side has already won, the information about who the next player to move is going to be seemed necessary. But then I read Anne’s solution a bit and realized that if there’s two spaces left and only two possible moves in each space, that’s only two possibilities to check.
Here’s a modification dropping the use of me
for the alreadywon?
case:
1
2
3
4
5
6
7
8
9
10
11

(define (tiegame? position me)
(let ((underscores (appearances '_ position)))
(cond
((or (alreadywon? position 'x)
(alreadywon? position 'o)) #f)
((and (= underscores 2)
(or (icanwin? (findtriples position) me)
(opponentcanwin? (findtriples (positionupdater position me)) me))) #f)
((and (= underscores 1) (icanwin? (findtriples position) me)) #f)
(else #t))))

Exercise 10.4
Here are some possible changes to the rules of tictactoe:
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?
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 infindtriples
?
Would the program successfully follow the rules as modified?
I ran some tests and it appears to. I made the following modification findtriples
:
1
2
3
4

(define (findtriples position)
(every (lambda (comb) (substitutetriple comb position))
'(123 456 789 147 258 369 159 357 124 236 478 698)))

and ran the following tests:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

(ttt 'ox_xoxoxo 'x)
3
;ox_
;xox
;oxo
(ttt 'xoo___x_x 'o)
;6
;xoo
;___
;x_x
(ttt 'x_o__ox_x 'o)
2
;(and not 8 to block, since 2 is a winning move)
;x_o
;__o
;x_x

(the comments in semicolons represent a graphical depiction of the tictactoe board state, since it’s easier for me to understand the board state that way).
I guess based on the program design this makes sense. findtriples
is generated earlier on and then those triples are fed by ttt
into the strategy procedure tttchoose
. So the triples list “flows down” into every portion of the program. So because the triples list is the reference point for whether a pair is winning, changing it can allow the program to adapt to different rules, at least if the rule change still involves a triple. The idea of trying to get a particular set of three values in order to win is hardcoded into the math of procedures like mypair?
. So this particular change works, but if you wanted to move to a system where you need like, an L shape to win (like 1234, for example) then I don’t think the existing program would be able to handle that. You’d need to make more changes to handle that case.
Going into more detail: suppose you have something like the following board state:
1
2
3
4
5

(ttt 'xoo___x_x 'o)
;xoo
;___
;x_x

Under the normal rules of tictactoe, if you were o
and making the next move here, you’d want to occupy square 8 in order to block x from winning and also to build a potential 258 triple. And indeed, the normal tictactoe program returns 8 for this.
But with a “corners win” modification, you want to return 6 in order to win. And with the modification above, the procedure mypair?
will see that 236 is a potentially winning triple, and then return 6 according, which it does.
What if the diagonals didn’t win?
What would happen if we tried to implement the change merely by changing the quoted sentence of potential winning combinations in
findtriples
?
Would the program successfully follow the rules as modified?
I think this change would work based on the reasoning above.
The change would be reflected in the following code, which has removed the diagonal triples:
1
2
3
4

(define (findtriples position)
(every (lambda (comb) (substitutetriple comb position))
'(123 456 789 147 258 369)))

So for the following board state:
1
2
3
4
5

(ttt 'xo__xo___ 'x)
;xo_
;_xo
;___

I would expect the unaltered ttt
program to return a 9 (in order to win) and the modified program to return a 4 or an 7 (to try to build a 147 triple)
Both programs performed as expected.
What if you could win by having four squares in a corner, such as 1, 2, 4, and 5?
What would happen if we tried to implement the change merely by changing the quoted sentence of potential winning combinations in
findtriples
?
Would the program successfully follow the rules as modified?
I would expect this change to fail if implemented by editing findtriples, for the reason stated above. To recap, the idea of trying to get a particular set of three values in order to win is hardcoded into the math of procedures like mypair?
. So if you wanted to move to a system where you need like, an L shape to win (like 1234, for example) then I don’t think the existing program would be able to handle that just by modifying findtriples
. You’d need to make more substantial changes.
I changed the code as follows to test this:
1
2
3
4

(define (findtriples position)
(every (lambda (comb) (substitutetriple comb position))
'(123 456 789 147 258 369 159 357 1245 2356 4578 5689)))

Now consider the following board state:
1
2
3
4
5

(ttt 'xxox_oo__ 'x)
xxo
x_o
o__

I’d expect the standard ttt program to attempt to block the computer from winning at 9. I’d expect the modified procedure to do the same.
My prediction was correct.
Exercise 10.5
Modify ttt to play chess.
Sounds hard, especially since I don’t know anything about chess. I’m going to skip this one for now.
Trees
After reviewing her work on this chapter, I tried making some trees like AnneB did, to see the overall structure of the whole program.
Initially I thought the more detailed tree AnneB made looked overwhelming, but then I realized that I’d already some of the work in terms of describing what each part of the program did. Filling in the gaps and elaborating was a significant amount of additional work though.
Making the more detailed tree had a concrete benefit for me: I did not actually understand in detail the operation of opponentcanwin?
or the various subprocedures within pivots
or icanadvance?
previously. I had a sort of vague idea but making the tree gave me a more solid appreciation. I mention this as a reminder to myself of the value of making the tree, since I seem to still be somewhat skeptical and do such things in an inconsistent manner.
Things to Improve
Some of it is stuff I’ve mentioned before:
 Use trees more (like, I could have made a tree of the whole program).
 Do more thorough testing.
 Integrate past solutions into future steps (like Anne did with integrating alreadywon? into tiegame).
 (specific to this chapter) A failure to represent the tictactoe board pictorially caused me some confusion about the board game state when coming up with tests. I fixed this as I went along.
Not sure if I’m overreaching or just failing to consistently apply best practices or something, but I found this chapter pretty difficult to work through. Possibly my standards are still not high enough in some way. I think part of the difficulty may have been that I’d worked through a lot of the material for the previous chapters in the past, but I might have skipped over most of this chapter previously, so it was kind of like totally new material. Since the next chapter looks to be stuff I’ve worked through before, I think I should go through it with some sort of checklist in order to use those (hopefully relatively easier problems) as an opportunity to work on developing some skills. Here are some things I’m thinking of having on my checklist:
 Make trees of procedures.
 Describe what each part of a procedure does in detail. Domain, range, big picture role, detailed steps.
 Figure out tests, including tests that try to go at least a bit beyond the scope of what the text says and make sense in terms of input someone might give an actual program (like – can the program handle erroneous input?)
 Ensure that I represent important information to myself in a way that’s easy for me to check for errors and issues (this came up with my initial failure in Chapter 10 to represent my tictactoe test cases pictorially, which wasted some time)
 Integrate past solutions to problems into future steps in order to make procedures I write more robust/able to handle more cases (instead of treating each procedure as its own thing).
 Consider whether parameter names are reasonable.
 Consider whether there is redundant or unnecessary functionality. Consider especially whether
if
statements are needed.  Carefully check each line of a program for parentheses issues when I’m done writing.
 Don’t rush to artificial deadlines. Focus on mastery not speed.