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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
|
<HTML>
<HEAD>
<TITLE>Computer Science Logo Style vol 1 ch 6: Example: Tic-Tac-Toe</TITLE>
</HEAD>
<BODY>
<CITE>Computer Science Logo Style</CITE> volume 1:
<CITE>Symbolic Computing</CITE> 2/e Copyright (C) 1997 MIT
<H1>Example: Tic-Tac-Toe</H1>
<TABLE width="100%"><TR><TD>
<IMG SRC="../csls1.jpg" ALT="cover photo">
<TD><TABLE>
<TR><TD align="right"><CITE><A HREF="http://www.cs.berkeley.edu/~bh/">Brian
Harvey</A><BR>University of California, Berkeley</CITE>
<TR><TD align="right"><BR>
<TR><TD align="right"><A HREF="../pdf/v1ch06.pdf">Download PDF version</A>
<TR><TD align="right"><A HREF="../v1-toc2.html">Back to Table of Contents</A>
<TR><TD align="right"><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A>
<TR><TD align="right"><A HREF="https://mitpress.mit.edu/books/computer-science-logo-style-second-edition-volume-1">MIT
Press web page for Computer Science Logo Style</A>
</TABLE></TABLE>
<HR>
<P>Program file for this chapter: <A HREF="ttt.lg"><CODE>ttt</CODE></A>
<P>This chapter is the first application of the ideas we've explored to a
sizable project. The primary purpose of the chapter is to introduce
the techniques of <EM>planning</EM> a project, especially the choice of
how to organize the information needed by the program. This organization is
called the <EM>data structure</EM> of the program. Along the way,
we'll also see a new data type, the array, and a few other details of Logo
programming.
<P><H2>The Project</H2>
<P>Tic-tac-toe is not a very challenging game for human beings. If you're
an enthusiast, you've probably moved from the basic game to some variant
like three-dimensional tic-tac-toe on a larger grid.
<P>If you sit down right now to play ordinary three-by-three tic-tac-toe
with a friend, what will probably happen is that every game will come
out a tie. Both you and your friend can probably play perfectly,
never making a mistake that would allow your opponent to win.
<P>But can you <EM>describe</EM> how you know where to move each turn?
Most of the time, you probably aren't even aware of alternative possibilities;
you just look at the board and instantly know where you want to move.
That kind of instant knowledge is great for human beings, because
it makes you a fast player. But it isn't much help in writing a computer
program. For that, you have to know very explicitly what your strategy
is.
<P>By the way, although the example of tic-tac-toe strategy is a relatively
trivial one, this issue of instant knowledge versus explicit rules is a hot
one in modern psychology. Some cognitive scientists, who think that human
intelligence works through mechanisms similar to computer programs, maintain
that when you know how to do something without knowing <EM>how</EM> you know,
you have an explicit set of rules deep down inside. It's just that the
rules have become a habit, so you don't think about them deliberately.
They're "compiled," in the jargon of cognitive psychology. On
the other hand, some people think that your implicit how-to knowledge is very
different from the sort of lists of rules that can be captured in a computer
program. They think that human thought is profoundly different from the way
computers work, and that a computer cannot be programmed to simulate the
full power of human problem-solving. These people would say, for example,
that when you look at a tic-tac-toe board you immediately grasp the
strategic situation as a whole, and your eye is drawn to the best move
without any need to examine alternatives according to a set of rules. (You
might like to try to be aware of your own mental processes as you play a
game of tic-tac-toe, to try to decide which of these points of view more
closely resembles your own experience--but on the other hand, the
psychological validity of such introspective evidence is <EM>another</EM>
hotly contested issue in psychology!)
<P>»Before you read further, try to write down a set of strategy rules
that, if followed consistently, will never lose a game. Play a few
games using your rules. Make sure they work even if the other player
does something bizarre.
<P>I'm going to number the squares in the tic-tac-toe
board this way:
<P>
<TABLE rules="all" frame="void" border="2" noshade><TR><TD align="center" height=30 width=30>1<TD align="center" height=30 width=30>2<TD align="center" height=30 width=30>3<TR><TD align="center" height=30 width=30>4<TD align="center" height=30 width=30>5<TD align="center" height=30 width=30>6<TR><TD align="center" height=30 width=30>7<TD align="center" height=30 width=30>8<TD align="center" height=30 width=30>9</TABLE>
<P>Squares 1, 3, 7, and 9 are <EM>corner squares</EM>. I'll call
2, 4, 6, and 8 <EM>edge squares</EM>. And of course number 5 is the
<EM>center square</EM>. I'll use the word <EM>position</EM> to mean
a specific partly-filled-in board with X and O in certain squares, and
other squares empty.
<P>One way you might meet my challenge of describing your strategy explicitly
is to list all the possible sequences of moves up to a certain point
in the game, then say what move you'd make next in each situation.
How big would the list have to be? There are nine possibilities for
the first move. For each first move, there are eight possibilities
for the second move. If you continue this line of reasoning, you'll
see that there are nine factorial, or 362880, possible sequences of
moves. Your computer may not have enough memory to list
them all, and you certainly don't have enough patience!
<P>Fortunately, not all these sequences are interesting. Suppose you
are describing the rules a computer should use against a human player,
and suppose the human being moves first. Then there are, indeed,
nine possible first moves. But for each of these, there is only <EM>
one</EM> possible computer move! After all, we're programming the computer.
We get to decide which move it will choose. Then there are seven
possible responses by the opponent, and so on. The number of sequences
when the human being plays first is 9 times 7 times 5 times 3, or
945. If the computer plays first, it will presumably always make
the single best choice. Then there are eight possible responses,
and so on. In this case the number of possible game sequences is
8 times 6 times 4 times 2, or 384. Altogether we have 1329 cases
to worry about, which is much better than 300,000 but still not an
enjoyable way to write a computer program.
<P>In fact, though, this number is still too big. Not all games go for
a full nine moves before someone wins. Also, many moves force the
opponent to a single possible response, even though there are other
vacant squares on the board. Another reduction can be achieved by
taking advantage of <EM>symmetry</EM>. For example, if X starts in square
5, any game sequence in which O responds in square 1 is equivalent
to a sequence in which O responds in square 3, with the board rotated
90 degrees. In fact there are only two truly different responses
to a center-square opening: any corner square, or any edge square.
<P>With all of these factors reducing the number of distinct positions,
it would probably be possible to list all of them and write
a strategy program that way. I'm not sure, though, because I didn't
want to use that technique. I was looking for rules expressed in
more general terms, like "all else being equal, pick a corner rather
than an edge."
<P>Why should I prefer a corner? Each corner square is part of three
winning combinations. For example, square 1 is part of <CODE>123</CODE>,
<CODE>147</CODE>, and <CODE>159</CODE>. (By expressing these winning combinations as
three-digit numbers, I've jumped ahead a bit in the story with a preview of how
the program I wrote represents this information.) An edge square,
on the other hand, is only part of two winning combinations. For
example, square 2 is part of <CODE>123</CODE> and <CODE>258</CODE>. Taking a corner
square makes three winning combinations available to me and unavailable
to my opponent.
<P>Since I've brought up the subject of winning combinations, how many
of <EM>them</EM> are there? Not very many: three horizontal, three vertical,
and two diagonal. Eight altogether. That <EM>is</EM> a reasonable amount
of information to include in a program, and in fact there is a list
of the eight winning combinations in this project.
<P>You might, at this point, enjoy playing a few games with the program,
to see if you can figure out the rules it uses in its strategy. If
you accepted my earlier challenge to write down your own set of strategy
rules, you can compare mine to yours. Are they the same? If not,
are they equally good?
<P>The top-level procedure in this project is called <CODE>ttt</CODE>. It takes no
inputs. When you invoke this procedure, it will ask you if you'd
like to play first (X) or second (O). Then you enter moves by typing
a digit 1-9 for the square you select. The program draws the game
board on the Logo graphics screen.
<P>I'm about to start explaining my strategy rules, so stop reading if
you want to work out your own and haven't done it yet.
<P><H2>Strategy</H2>
<P>The highest-priority and the lowest-priority rules seemed obvious
to me right away. The highest-priority are these:
<P>
<P><TABLE><TR><TH>1. <TD>If I can win on this move, do it.
<TR><TH>2. <TD>If the other player can win on the next move, block that winning
square.
</TABLE>
<P>Here are the lowest-priority rules, used only if there is
nothing suggested more strongly by the board position:
<P><TABLE><TR><TH><EM>n</EM>-2. <TD>Take the center square if it's free.
<TR><TH><EM>n</EM>-1. <TD>Take a corner square if one is free.
<TR><TH><EM>n</EM>. <TD>Take whatever is available.
</TABLE>
<P>The highest priority rules are the ones dealing with the
most urgent situations: either I or my opponent can win on the next
move. The lowest priority ones deal with the least urgent situations,
in which there is nothing special about the moves already made to
guide me.
<P>What was harder was to find the rules in between. I knew that the
goal of my own tic-tac-toe strategy was to set up a <EM>fork</EM>, a
board position in which I have two winning moves, so my opponent can
only block one of them. Here is an example:
<P> <TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE>
<P>X can win by playing in square 3 or square 4. It's O's
turn, but poor O can only block one of those squares at a time. Whichever
O picks, X will then win by picking the other one.
<P>Given this concept of forking, I decided to use it as the next highest
priority rule:
<P><TABLE><TR><TH>3. <TD>If I can make a move that will set up a fork for myself, do it.
</TABLE>
<P>That was the end of the easy part. My first attempt at
writing the program used only these six rules. Unfortunately, it
lost in many different situations. I needed to add something, but
I had trouble finding a good rule to add.
<P>My first idea was that rule 4 should be the defensive equivalent of
rule 3, just as rule 2 is the defensive equivalent of rule 1:
<P><TABLE><TR><TH>4a. <TD>If, on the next move, my opponent can set up a fork, block that
possibility by moving into the square that is common to his two winning
combinations.
</TABLE>
<P>In other words, apply the same search technique to the opponent's
position that I applied to my own.
<P>This strategy works well in many cases, but not all. For example,
here is a sequence of moves under this strategy, with the human player
moving first:
<P><PRE><TABLE><TR>
<TD width=150 align="center" valign="bottom"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30><TD align="center" height=30 width=30> <TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30>x<TD align="center" height=30 width=30> <TR><TD align="center" height=30 width=30> <TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30><TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30 align="center" height=30 width=30>o<TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30> <TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30 align="center" height=30 width=30> <TD align="center" height=30 width=30 align="center" height=30 width=30>x<TD align="center" height=30 width=30 align="center" height=30 width=30>x</TABLE>
</TABLE></PRE>
<P>In the fourth grid, the computer (playing O) has discovered
that X can set up a fork by moving in square 6, between the winning
combinations <CODE>456</CODE> and <CODE>369</CODE>. The computer moves to block this
fork. Unfortunately, X can also set up a fork by moving in squares
3, 7, or 8. The computer's move in square 6 has blocked one combination
of the square-3 fork, but X can still set up the other two. In the
fifth grid, X has moved in square 8. This sets up the winning combinations
<CODE>258</CODE> and <CODE>789</CODE>. The computer can only block one of these, and
X will win on the next move.
<P>Since X has so many forks available, does this mean that the game
was already hopeless before O moved in square 6? No. Here is something
O could have done:
<P><PRE><TABLE><TR>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
</TABLE></PRE>
<P>In this sequence, the computer's second move is in square
7. This move also blocks a fork, but it wasn't chosen for that reason.
Instead, it was chosen <EM>to force X's next move</EM>. In the fifth
grid, X has had to move in square 4, to prevent an immediate win by
O. The advantage of this situation for O is that square 4 was <EM>
not</EM> one of the ones with which X could set up a fork. O's next move,
in the sixth grid, is also forced. But by then the board is too crowded
for either player to force a win; the game ends in a tie, as usual.
<P>This analysis suggests a different choice for an intermediate-level
strategy rule, taking the offensive:
<P><TABLE><TR><TH>4b. <TD>If I can make a move that will set up a winning combination
for myself, do it.
</TABLE>
<P>Compared to my earlier try, this rule has the benefit of
simplicity. It's much easier for the program to look for a single
winning combination than for a fork, which is two such combinations
with a common square.
<P>Unfortunately, this simple rule isn't quite good enough. In the example
just above, the computer found the winning combination <CODE>147</CODE> in
which it already had square 1, and the other two were free. But why
should it choose to move in square 7 rather than square 4? If the
program did choose square 4, then X's move would still be forced,
into square 7. We would then have forced X into creating a fork,
which would defeat the program on the next move.
<P>It seems that there is no choice but to combine the ideas from rules
4a and 4b:
<P><TABLE><TR><TH>4b. <TD>If I can make a move that will set up a winning combination
for myself, do it. But ensure that this move does not force the opponent
into establishing a fork.
</TABLE>
<P>What this means is that we are looking for a winning combination
in which the computer already owns one square and the other two are empty.
Having found such a combination, we can move in either of its empty squares.
Whichever we choose, the opponent will be forced to choose the other one
on the next move. If one of the two empty squares would create a fork for
the opponent, then the computer must choose that square and leave the other
for the opponent.
<P>What if <EM>both</EM> of the empty squares in the combination we find
would make forks for the opponent? In that case, we've chosen a bad
winning combination. It turns out that there is only one situation
in which this can happen:
<P><PRE><TABLE><TR>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
</TABLE></PRE>
<P>Again, the computer is playing O. After the third grid,
it is looking for a possible winning combination for itself. There
are three possibilities: <CODE>258</CODE>, <CODE>357</CODE>, and <CODE>456</CODE>.
So far we
have not given the computer any reason to prefer one over another.
But here is what happens if the program happens to choose <CODE>357</CODE>:
<P><PRE><TABLE><TR>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30></TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
<TD width=150 align="center"><TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TD align="center" height=30 width=30>x</TABLE>
</TABLE></PRE>
<P>By this choice, the computer has forced its opponent into
a fork that will win the game for the opponent.
If the computer chooses either of the other two possible winning combinations,
the game ends in a tie. (All moves after this choice turn out to
be forced.)
<P>This particular game sequence was very troublesome for me because
it goes against most of the rules I had chosen earlier. For one thing,
the correct choice for the program is any edge square, while the corner
squares must be avoided. This is the opposite of the usual priority.
<P>Another point is that this situation contradicts rule 4a (prevent
forks for the other player) even more sharply than the example we
considered earlier. In that example, rule 4a wasn't enough
guidance to ensure a correct choice, but the correct choice was at
least <EM>consistent</EM> with the rule. That is, just blocking a fork
isn't enough, but threatening a win and <EM>also</EM> blocking a fork
is better than just threatening a win alone. This is the meaning
of rule 4. But in this new situation, the corner square (the move
we have to avoid) <EM>does</EM> block a fork, while the edge square (the
correct move) <EM>doesn't</EM> block a fork!
<P>When I discovered this anomalous case, I was ready to give up on the
idea of beautiful, general rules. I almost decided to build into
the program a special check for this precise board configuration.
That would have been pretty ugly, I think. But a shift in viewpoint
makes this case easier to understand: What the program must do is
force the other player's move, and force it in a way that helps the
computer win. If one possible winning combination doesn't allow us to
meet these conditions, the program should try another combination.
My mistake was to think either about forcing alone (rule 4b) or about
the opponent's forks alone (rule 4a).
<P>As it turns out, the board situation we've been considering is the only
one in which a possible winning combination could include two possible
forks for the opponent. What's more, in this board situation, it's a
diagonal combination that gets us in trouble, while a horizontal or
vertical combination is always okay. Therefore, I was able to implement
rule 4 in a way that only considers one possible winning combination by
setting up the program's data structures so that diagonal combinations
are the last to be chosen. This trick makes the program's design less
than obvious from reading the actual program, but it does save the program
some effort.
<P><H2>Program Structure and Modularity</H2>
<P>Most game programs--in fact, most interactive programs of any
kind--consist of an initialization section followed by a sequence
of steps carried out repeatedly. In the case of the tic-tac-toe game,
the overall program structure will be something like this:
<P><PRE>to ttt
initialize
forever [
if <EM>game.is.over</EM> [stop]
<EM>record.human.move get.human.move</EM>
if <EM>game.is.over</EM> [stop]
<EM>record.program.move compute.program.move</EM>
]
end
</PRE>
<P>The parts of this structure shown in <CODE><EM>italics</EM></CODE> are
just vague ideas. At this point in the planning, I don't know what inputs
these procedures might need, for example. In fact, there may not be
procedures exactly like this in the final program. One example is that
the test that I've called <CODE><EM>game.is.over</EM></CODE> here will actually
turn out to be two separate tests <CODE>already.wonp</CODE> and <CODE>tiedp</CODE> (using
a final letter <CODE>p</CODE> to indicate a predicate, following the convention
established by the Logo primitive predicates).
<P>This half-written procedure introduces a Logo primitive we haven't used
before: <CODE>forever</CODE>. It takes a list of Logo instructions as its
input, and carries out those instructions repeatedly, much as <CODE>repeat</CODE>,
<CODE>for</CODE>, and <CODE>foreach</CODE> do. But the number of repetitions is unlimited;
the repetition stops only if, as in this example, the primitive <CODE>stop</CODE> or
<CODE>output</CODE> is invoked within the repeated instructions. <CODE>Forever</CODE> is
useful when the ending condition can't be predicted in advance, as in a game
situation in which a player might win at any time.
<P>It may not be obvious why I've planned for one procedure to figure out the
next move and a separate procedure to record it. (There are two such pairs
of procedures, one for the program's moves and the other for the human
opponent's moves.) For one thing, I expect that the recording of moves
will be much the same whether it's the program or the person moving, while
the decision about where to move will be quite different in the two cases.
For the program's move we must apply strategy rules; for the human player's
moves we simply ask the player. Also, I anticipate that the selection of
the program's moves, which will be the hardest part of the program, can be
written in functional style. The strategy procedure is a function that takes
the current board position as its input, always returning the same chosen
square for any given input position.
<P>This project contains 28 procedures. These procedures can be divided into
related groups like this:
<P><TABLE>
<TR><TD>7<TD>overall orchestration
<TR><TD>6<TD>initialization
<TR><TD>2<TD>get opponent's moves
<TR><TD>9<TD>compute program's moves
<TR><TD>4<TD>draw moves on screen
</TABLE>
<P>As you might expect, figuring out the computer's strategy
is the most complex part of the program's job. But this strategic
task is still only about a third of the complete program.
<P>The five groups are quite cleanly distinguishable in this project. There are
relatively few procedure invocations between groups, compared to the number
within a group. It's easy to read the procedures within a group and
understand how they work without having to think about other parts of the
program at the same time.
<P>
The following diagram shows the subprocedure/superprocedure relationships
within the program, and indicates which procedures are in each of the five
groups listed above. Some people find diagrams like this one very helpful in
understanding the structure of a program. Other people don't like these
diagrams at all. If you find it helpful, you may want to draw such diagrams
for your own projects.
<P>
<CENTER><IMG SRC="https://people.eecs.berkeley.edu/~bh/v1ch6/tttflow.gif" ALT="figure: tttflow"></CENTER>
<P>In the diagram, I've circled the names of seven procedures. If you
understand the purpose of each of these, then you will understand
the general structure of the entire program. (Don't turn to the end and
read the actual procedures just now. Instead, see if
you can understand the following paragraphs just from the diagram.)
<P><CODE>Ttt</CODE> is the top-level procedure for which I gave a rough outline
earlier. It calls initialization procedures (<CODE>draw.board</CODE> and <CODE>
init</CODE>) to set up the game, then repeatedly alternates between the human
opponent's moves and the program's moves. It calls <CODE>getmove</CODE> to find
out the next move by the opponent, <CODE>youplay</CODE> to record that move,
then <CODE>pickmove</CODE> to compute the program's next move and <CODE>meplay</CODE>
to record it.
<P><CODE>Make.triples</CODE> translates from one representation of the board
position to another. The representation used within <CODE>ttt</CODE> is best
suited for display and for user interaction, while the representation
output by <CODE>make.triples</CODE> is best for computing the program's strategy.
We'll look into data representation more closely later.
<P><CODE>Getmove</CODE> invites the opponent to type in a move. It ensures that
the selected move is legal before accepting it. The output from <CODE>
getmove</CODE> is a number from 1 to 9 representing the chosen square.
<P><CODE>Pickmove</CODE> figures out the program's next move. It is the "smartest"
procedure in the program, embodying the strategy rules I listed earlier.
It, too, outputs a number from 1 to 9.
<P><CODE>Youplay</CODE> and <CODE>meplay</CODE> are simple procedures that actually carry out
the moves chosen by the human player and by the program, respectively.
Each contains only two instructions. The first invokes <CODE>draw</CODE> to draw
the move on the screen. The second modifies the <CODE>position</CODE> array
to remember that the move has been made.
<P><CODE>Draw</CODE> moves the turtle to the chosen square on the tic-tac-toe board.
Then it draws either an X or an O. (We haven't really talked about Logo's
turtle graphics yet. If you're not familiar with turtle graphics from
earlier Logo experience, you can just take this part of the program on faith;
there's nothing very interesting about it.)
<P>Notice, in the diagram, that the lines representing procedure calls
come into a box only at the top. This is one sign of a well-organized
program: The dashed boxes in the diagram truly do represent distinct
parts of the program that don't interact very much.
<P><H2>Data Representation</H2>
<P>I've written several tic-tac-toe programs, in different programming
languages. This experience has really taught me about the importance of
picking a good data representation. For my first tic-tac-toe
program, several years ago, I decided without much prior thought that a
board position should be represented as three lists of numbers, one with X's
squares, one with O's squares, and one with the free squares. So this board
position
<P><PRE>
<TABLE rules="all" frame="void" border="2">
<TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE>
</PRE>
<P>could be represented like this:
<P><PRE>make "xsquares [1 4 5]
make "osquares [2 9]
make "free [3 6 7 8]
</PRE>
<P>These three variables would change in value as squares moved
from <CODE>:free</CODE> to one of the others. This representation was easy
to understand, but not very helpful for writing the program!
<P>What questions does a tic-tac-toe program have to answer about the board
position? If, for example, the program wants to print a display of the
position, it must answer questions of the form "Who's in square 4?"
With the representation shown here, that's not as easy a question as we
might wish:
<P><PRE>to occupant :square ;; old program
if memberp :square :xsquares [output "x]
if memberp :square :osquares [output "o]
output "free
end
</PRE>
<P>
<P>On the other hand, this representation isn't so bad when we're
accepting a move from the human player and want to make sure it's a legal
move:
<P><PRE>to freep :square ;; old program
output memberp :square :free
end
</PRE>
<P>Along with this representation of the board, my first program used
a constant list of winning combinations:
<P><PRE>make "wins [[1 2 3] [4 5 6] [7 8 9] [1 4 7] [2 5 8]
[3 6 9] [1 5 9] [3 5 7]]
</PRE>
<P>It also had a list of all possible forks. I won't bother
trying to reproduce this very long list for you, since it's not used
in the current program, but the fork set up by X in the
board position just above was represented this way:
<P><PRE>[4 [1 7] [5 6]]
</PRE>
<P>This indicates that square 4 is the pivot of a fork between
the winning combinations <CODE>[1 4 7]</CODE> and <CODE>[4 5 6]</CODE>. Each member of the
complete list of forks was a list like this sample. The list of forks
was fairly long. Each edge square is the pivot of a fork. Each corner
square is the pivot of three forks. The center square is the pivot
of six forks. This adds up to 22 forks altogether.
<P>Each time the program wanted to choose a move, it would first check
all eight possible winning combinations to see if two of the squares
were occupied by the program and the third one free. Since any of
the three squares might be the free one, this is a fairly tricky program
in itself:
<P><PRE>to checkwin :candidate :mysquares :free ;; old program
if memberp first :candidate :free ~
[output check1 butfirst :candidate :mysquares]
if memberp last :candidate :free ~
[output check1 butlast :candidate :mysquares]
if memberp first butfirst :candidate :free ~
[output check1 list first :candidate last :candidate :mysquares]
output "false
end
to check1 :sublist :mysquares ;; old program
output and (memberp first :sublist :mysquares) ~
(memberp last :sublist :mysquares)
end
</PRE>
<P>This procedure was fairly slow, especially when invoked
eight times, once for each possible win. But the procedure to check
each of the possible forks was even worse!
<P>In the program that I wrote for the first edition of <EM>Computer Science
Logo Style,</EM> a very different approach is used. This approach is based on
the realization that, at any moment, a particular winning combination may be
free for anyone (all three squares free), available only to one player, or
not available to anyone. It's silly for the program to go on checking a
combination that can't possibly be available. Instead of a single list of
wins, the new program has three lists:
<P>
<TABLE>
<TR><TD><CODE>mywins</CODE><TD width=30><TD>wins available to the computer
<TR><TD><CODE>yourwins</CODE><TD width=30><TD>wins available to the opponent
<TR><TD><CODE>freewins</CODE><TD width=30><TD>wins available to anyone
</TABLE>
<P>Once I decided to organize the winning combinations in this form,
another advantage became apparent: for each possible winning combination,
the program need only remember the squares that are free, not the
ones that are occupied. For example, the board position shown above
would contain these winning combinations, supposing the computer is
playing X:
<P><PRE>make "mywins [[7] [6] [3 7]]
make "yourwins [[3 6] [7 8]]
make "freewins []
</PRE>
<P>The sublist <CODE>[7]</CODE> of <CODE>:mywins</CODE> indicates that the computer can
win simply by filling square 7. This list represents the winning
combination that was originally represented as <CODE>[1 4 7]</CODE>, but since
the computer already occupies squares 1 and 4 there is no need to
remember those numbers.
<P>The process of checking for an immediate win is streamlined with this
representation for two reasons, compared with the <CODE>checkwin</CODE> procedure
above. First, only those combinations in <CODE>:mywins</CODE> must
be checked, instead of all eight every time. Second, an immediate
win can be recognized very simply, because it is just a list with
one member, like <CODE>[7]</CODE> and <CODE>[6]</CODE> in the example above. The procedure
<CODE>single</CODE> looks for such a list:
<P><PRE>to single :list ;; old program
output find [equalp (count ?) 1] :list
end
</PRE>
<P>The input to <CODE>single</CODE> is either <CODE>:mywins</CODE>, to find a winning
move for the computer (rule 1), or <CODE>:yourwins</CODE>, to find and block a
winning move for the opponent (rule 2).
<P>Although this representation streamlines the strategy computation (the
<CODE>pickmove</CODE> part of the program), it makes the recording of a move
quite difficult, because combinations must be moved from one list to
another. That part of the program was quite intricate and hard to
understand.
<P><H2>Arrays</H2>
<P>This new program uses <EM>two</EM> representations, one for the interactive
part of the program and one for the strategy computation. The first of these
is simply a collection of nine words, one per square, each of which is the
letter X, the letter O, or the number of the square. With this
representation, recording a move means changing one of the nine words.
It would be possible to keep the nine words in a list, and compute a new
list (only slightly different) after each move. But Logo provides another
data type, the <EM>array,</EM> which allows for changing one member
while keeping the rest unchanged.
<P>If arrays allow for easy modification and lists don't, why not always use
arrays? Why did I begin the book with lists? The answer is that each
data type has advantages and disadvantages. The main disadvantage of an
array is that you must decide in advance how big it will be; there aren't
any constructors like <CODE>sentence</CODE> to lengthen an array.
<P>In this case, the fixed length of an array is no problem, because a
tic-tac-toe board has nine squares. The <CODE>init</CODE> procedure creates
the position array with the instruction
<P><PRE>make "position {1 2 3 4 5 6 7 8 9}
</PRE>
<P>The braces <CODE>{}
</CODE> indicate an array in the same
way that brackets indicate a list.
<P>If player X moves in square 7, we can record that information
by saying
<P><PRE><CODE>setitem</CODE> 7 :position "x
</PRE>
<P>(Of course, the actual instruction in procedures <CODE>meplay</CODE> and
<CODE>youplay</CODE> uses variables instead of the specific values 7 and X.)
<CODE>Setitem</CODE> is a command with three inputs: a number indicating which
member of the array to change, the array itself, and the new value for
the specified member.
<P>To find out who owns a particular square, we could write this procedure:
<P><PRE>to occupant :square
output <CODE>item</CODE> :square :position
end
</PRE>
<P>(The <CODE>item</CODE> operation can select a member of an array just as
it can select a member of a list or of a word.) In fact, though, it turns
out that I don't have an <CODE>occupant</CODE> procedure in this program. But the
parts of the program that examine the board position do use <CODE>item</CODE> in a
similar way, as in this example:
<P><PRE>to freep :square
output numberp item :square :position
end
</PRE>
<P>To create an array without explicitly listing all of its members, use the
operation <CODE>array</CODE>. It takes a number as argument, indicating how many
members the array should have. It returns an array of the chosen size, in
which each member is the empty list. Your program can then use <CODE>setitem</CODE>
to assign different values to the members.
<P>The only primitive operation to select a member of an array is <CODE>item</CODE>.
Word-and-list operations such as <CODE>butfirst</CODE> can't be used with arrays.
There are operations <CODE>arraytolist</CODE> and <CODE>listtoarray</CODE> to convert
a collection of information from one data type to the other.
<P><H2>Triples</H2>
<P>The position array works well as a long-term representation for the board
position, because it's easy to update; it also works well for interaction
with the human player, because it's easy to find out the status of a
particular square. But for computing the program's moves, we need a
representation that makes it easy to ask questions such as "Is there a
winning combination for my opponent on the next move?" That's why, in
the first edition of these books, I used the representation with three
lists of possible winning combinations.
<P>When MatthewWright and I wrote the book <EM>Simply Scheme,</EM> we
decided that the general idea of combinations was a good one, but the three
lists made the program more complicated than necessary. Since there are
only eight possible winning combinations in the first place, it's not so
slow to keep one list of all of them, and use that list as the basis for
all the questions we ask in working out the program's strategy. If the
current board position is
<P><PRE>
<TABLE rules="all" frame="void" border="2"><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE>
</PRE>
<P>we represent the three horizontal winning combinations with
the words <CODE>xo3</CODE>, <CODE>xx6</CODE>, and <CODE>78o</CODE>. Each combination is
represented as a three-"letter" word containing an <CODE>x</CODE> or an <CODE>o</CODE>
for an occupied square, or the square's number for a free square. By
using words instead of lists for the combinations, we make the entire
set of combinations more compact and easier to read. Each of these words
is called a <EM>triple.</EM> The job of procedure <CODE>make.triples</CODE> is
to combine the information in the position array with a list of the eight
winning combinations:
<P><PRE>? <U>show make.triples</U>
[xo3 xx6 78o xx7 ox8 36o xxo 3x7]
</PRE>
<P><CODE>Make.triples</CODE> takes no inputs because the list of possible
winning combinations is built into it, and the position array is in <CODE>
ttt</CODE>'s local variable <CODE>position</CODE>:
<P><PRE>to make.triples
output map "substitute.triple [123 456 789 147 258 369 159 357]
end
to substitute.triple :combination
output map [item ? :position] :combination
end
</PRE>
<P>This short subprogram will repay careful attention. It uses
<CODE>map</CODE> twice, once in <CODE>make.triples</CODE> to compute a function of
each possible winning combination, and once in <CODE>substitute.triple</CODE> to
compute a function of each square in a given combination. (That latter
function is the one that looks up the square in the array <CODE>:position</CODE>.)
<P>Once the program can make the list of triples, we can use that to answer
many questions about the status of the game. For example, in the top-level
<CODE>ttt</CODE> procedure we must check on each move whether or not a certain
player has already won the game. Here's how:
<P><PRE>to already.wonp :player
output memberp (word :player :player :player) (make.triples)
end
</PRE>
<P>If we had only the <CODE>position</CODE> array to work with, it would be
complicated to check all the possible winning combinations. But once we've
made the list of triples, we can just ask whether the word <CODE>xxx</CODE> or the
word <CODE>ooo</CODE> appears in that list.
<P>Here is the actual top-level procedure definition:
<P><PRE>to ttt
local [me you position]
draw.board
init
if equalp :me "x [meplay 5]
forever [
if already.wonp :me [print [I win!] stop]
if tiedp [print [Tie game!] stop]
youplay getmove ;; ask person for move
if already.wonp :you [print [You win!] stop]
if tiedp [print [Tie game!] stop]
meplay pickmove make.triples ;; compute program's move
]
end
</PRE>
<P>Notice that <CODE>position</CODE> is declared as a local variable.
Because of Logo's dynamic scope, all of the subprocedures in this project
can use <CODE>position</CODE> as if it were a global variable, but Logo will
"clean up" after the game is over.
<P>Two more such quasi-global variables are used to remember whether the
computer or the human opponent plays first. The value of <CODE>me</CODE> will be
either the word <CODE>x</CODE> or the word <CODE>o</CODE>, whichever letter the program
itself is playing. Similarly, the value of <CODE>you</CODE> will be <CODE>x</CODE> or
<CODE>o</CODE> to indicate the letter used by the opponent. All of these variables
are given their values by the initialization procedure <CODE>init</CODE>.
<P>This information could have been kept in the form of a single
<EM>flag variable,</EM> called something like <CODE>mefirst</CODE>, that would
contain the word <CODE>true</CODE> if the computer is X, or <CODE>false</CODE> if the
computer is O. (A flag variable is one whose value is always <CODE>
true</CODE> or <CODE>false</CODE>, just as a predicate is a procedure whose output is
<CODE>true</CODE> or <CODE>false</CODE>.) It would be used something like this:
<P><PRE>if :mefirst [draw "x :square] [draw "o :square]
</PRE>
<P>But it turned out to be simpler to use two variables and
just say
<P><PRE>draw :me :square
</PRE>
<P>
<P>One detail in the final program that wasn't in my first rough draft is the
instruction
<P><PRE>if equalp :me "x [meplay 5]
</PRE>
<P>just before the <CODE>forever</CODE> loop. It was easier to write the
loop so that it always gets the human opponent's move first, and then
computes a move for the program, rather than having two different loops
depending on which player goes first. If the program moves first, its
strategy rules would tell it to choose the center square, because there is
nothing better to do when the board is empty. By checking for that case
before the loop, we are ready to begin the loop with the opponent as the
next to move.
<P><H2>Variables in the Workspace</H2>
<P>There are nine global variables that are part
of the workspace, entered directly with top-level <CODE>make</CODE> instructions
rather than set up by <CODE>init</CODE>, because their
values are never changed. Their names are <CODE>box1</CODE> through <CODE>
box9</CODE>, and their values are the coordinates on the graphics screen of
the center of each square. For example, <CODE>:box1</CODE> is <CODE>
[-40 50]</CODE>. These variables are used by <CODE>move</CODE>, a subprocedure of
<CODE>draw</CODE>, to know where to position the turtle before drawing an X
or an O.
<P>The use of variables loaded with a workspace file, rather than given values
by an initialization procedure, is a practice that Logo encourages in some
ways and discourages in others. Loading variables in a workspace file makes
the program start up faster, because it decreases the amount of
initialization required. On the other hand, variables are sort of
second-class citizens in workspace files. In many versions of Logo the <CODE>
load</CODE> command lists the names of the procedures in the workspace file, but
not the names of the variables. Similarly, <CODE>save</CODE> often reports the
number of procedures saved, but not the number of variables. It's easy to
create global variables and forget that they're there.
<P>Certainly preloading variables makes sense only if the variables are really
constants; in other words, a variable whose value may change during the
running of a program should be initialized explicitly when the program
starts. Otherwise, the program will probably give incorrect results if you
run it a second time. (One of the good ideas in the programming language
Pascal is that there is a sort of thing in the language called a <EM>
constant</EM>; it has a name and a value, like a variable, but you can't give
it a new value in mid-program. In Logo, you use a global variable to hold a
constant, and simply refrain from changing its value. But being able to
<EM>say</EM> that something is a constant makes the program easier to
understand.)
<P>One reason the use of preloaded variables is sometimes questioned as a point
of style is that when people are sloppy in their use of global variables,
it's hard to know which are really meant to be preloaded and which are just
left over from running the program. That is, if you write a program, test
it by running it, and then save it on a diskette, any global variables that
were created during the program execution will still be in the workspace
when you load that diskette file later. If there are five
intentionally-loaded variables along with 20 leftovers, it's particularly
hard for someone to understand which are which. This is one more reason not
to use global variables when what you really want are variables local to the
top-level procedure.
<P><H2>The User Interface</H2>
<P>The only part of the program that really interacts with the human user is
<CODE>getmove</CODE>, the procedure that asks the user where to move.
<P><PRE>to getmove
local "square
forever [
type [Your move:]
make "square readchar
print :square
if numberp :square
[if and (:square > 0) (:square < 10)
[if freep :square [output :square]]]
print [not a valid move.]
]
end
</PRE>
<P>There are two noteworthy things about this part of the program. One is that
I've chosen to use <CODE>readchar</CODE> to read what the player types. This
primitive operation, with no inputs, waits for the user to type any single
character on the keyboard, and outputs whatever character the user types.
This "character at a time" interaction is in contrast with the more usual
"line at a time" typing, in which you can type characters, erase some if
you make a mistake, and finally use the RETURN or ENTER key to indicate that
the entire line you've typed should be made available to your program.
(In Chapter 1 you met Logo's <CODE>readlist</CODE> primitive for line at a
time typing.) Notice that if tic-tac-toe had ten or more squares in its
board I wouldn't have been able to make this choice, because the program
would have to allow the entry of two-digit numbers.
<P><CODE>Readchar</CODE> was meant for fast-action programs such as video games.
It therefore does not display (or <EM>echo</EM>) the character that you type
on the computer screen. That's why <CODE>getmove</CODE> includes a <CODE>print</CODE>
instruction to let the user see what she or he has typed!
<P>The second point to note in <CODE>getmove</CODE> is how careful it is to allow for
the possibility of a user error. Ordinarily, when one procedure uses a
value that was computed by another procedure, the programmer can assume that
the value is a legitimate one for the intended purpose. For example, when
you invoke a procedure that computes a number, you assume that you can add
the output to another number; you don't first use the <CODE>number?</CODE>
predicate to double-check that the result was indeed a number. But in
<CODE>getmove</CODE> we are dealing with a value that was typed by a human being,
and human beings are notoriously error-prone! The user is <EM>supposed</EM>
to type a number between 1 and 9. But perhaps someone's finger might slip
and type a zero instead of a nine, or even some character that isn't a
number at all. Therefore, <CODE>getmove</CODE> first checks that what the user
typed is a number. If so, it then checks that the number is in the allowed
range. (We'd get a Logo error message if <CODE>getmove</CODE> used the <CODE>
<</CODE> operation with a non-numeric input.) Only if these conditions are met
do we use the user's number as the square-selecting input to <CODE>freep</CODE>.
<P><H2>Implementing the Strategy Rules</H2>
<P>To determine the program's next move, <CODE>ttt</CODE> invokes <CODE>pickmove</CODE>;
since many of the strategy rules will involve an examination of possible
winning combinations, <CODE>pickmove</CODE> is given the output from <CODE>
make.triples</CODE> as its input.
<P>The strategy I worked out for the program consists of several rules, in
order of importance. So the structure of <CODE>pickmove</CODE> should be something
like this:
<P><PRE>to pickmove :triples
if first.rule.works [output first.rule's.square]
if second.rule.works [output second.rule's.square]
...
end
</PRE>
<P>This structure would work, but it would be very inefficient,
because the procedure to determine whether a rule is applicable does
essentially the same work as the procedure to choose a square by following
the rule. For example, here's a procedure to decide whether or not the
program can win on this move:
<P><PRE>to can.i.win.now
output not emptyp find "win.nowp :triples
end
to win.nowp :triple
output equalp (filter [not numberp ?] :triple) (word :me :me)
end
</PRE>
<P>The subprocedure <CODE>win.nowp</CODE> decides whether or not a
particular triple is winnable on this move, by looking for a triple
containing one number and two letters equal to whichever of X or O
the program is playing. For example, <CODE>3xx</CODE> is a winnable triple
if the program is playing X.
<P>The procedure to pick a move if there is a winnable triple also must
apply <CODE>win.nowp</CODE> to the triples:
<P><PRE>to find.winning.square
output filter "numberp find "win.nowp :triples
end
</PRE>
<P>If there is a winnable triple <CODE>3xx</CODE>, then the program
should move in square 3. We find that out by looking for the number
within the first winnable triple we can find.
<P>It seems inelegant to find a winnable triple just to see if there are
any, then find the same triple again to extract a number from it.
Instead, we take advantage of the fact that the procedure I've called
<CODE>find.winning.square</CODE> will return a distinguishable value--namely,
an empty list--if there is no winnable triple. We say
<P><PRE>to pickmove :triples
local "try
make "try find.winning.square
if not emptyp :try [output :try]
...
end
</PRE>
<P>In fact, instead of the procedure <CODE>find.winning.square</CODE> the
actual program uses a similar <CODE>find.win</CODE> procedure that takes the
letter X or O as an input; this allows the same procedure to check both
rule 1 (can the computer win on this move) and rule 2 (can the opponent
win on the following move).
<P><CODE>Pickmove</CODE> checks each of the strategy rules with a similar pair of
instructions:
<P><PRE>make "try something
if not emptyp :try [output :try]
</PRE>
<P>Here is the complete procedure:
<P><PRE>to pickmove :triples
local "try
make "try find.win :me ; rule 1: can computer win?
if not emptyp :try [output :try]
make "try find.win :you ; rule 2: can opponent win?
if not emptyp :try [output :try]
make "try find.fork ; rule 3: can computer fork?
if not emptyp :try [output :try]
make "try find.advance ; rule 4: can computer force?
if not emptyp :try [output :try]
output find [memberp ? :position] [5 1 3 7 9 2 4 6 8] ; rules 5-7
end
</PRE>
<P>The procedures that check for each rule have a common flavor: They all
use <CODE>filter</CODE> and <CODE>find</CODE> to select interesting triples and then
to select an available square from the chosen triple. I won't go through
them in complete detail, but there's one that uses a Logo feature I haven't
described before. Here is <CODE>find.fork</CODE>:
<P><PRE>to find.fork
local "singles
make "singles singles :me ; find triples like 14x, x23
if emptyp :singles [output []]
output repeated.number reduce "word :singles ; find square in two triples
end
</PRE>
<P>Suppose the computer is playing X and the board looks like this:
<P><PRE>
<TABLE rules="all" frame="void" border="2">
<TR><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30>o<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30>x<TD align="center" height=30 width=30><TR><TD align="center" height=30 width=30><TD align="center" height=30 width=30><TD align="center" height=30 width=30>o</TABLE>
</PRE>
<P><CODE>Find.fork</CODE> calls <CODE>singles</CODE> (a straightforward procedure
that you can read in the complete listing at the end of this chapter) to
find all the triples containing one X and two vacant squares. It outputs
<P><PRE>[4x6 x47 3x7]
</PRE>
<P>indicating that the middle row, the left column, and one of the
diagonals meet these conditions. To find a fork, we must find a vacant
square that is included in two of these triples. The expression
<P><PRE>reduce "word :singles
</PRE>
<P>strings these triples together into the word <CODE>
4x6x473x7</CODE>. The job of <CODE>repeated.number</CODE> is to find a digit that
occurs more than once in this word. Here is the procedure:
<P><PRE>to repeated.number :squares
output find [memberp ? ?rest] filter "numberp :squares
end
</PRE>
<P>The expression
<P><PRE>filter "numberp :squares
</PRE>
<P>gives us the word <CODE>464737</CODE>, which is the input word with
the letters removed. We use <CODE>find</CODE> to find a repeated digit in
this number. The new feature is the use of <CODE>?rest</CODE> in the predicate template
<P><PRE>[memberp ? ?rest]
</PRE>
<P><CODE>?rest</CODE> represents the part of the input to <CODE>find</CODE> (or any
of the other higher-order functions that understand templates) to the right
of the value being used as <CODE>?</CODE>. So in this example, <CODE>find</CODE> first
computes the value of the expression
<P><PRE>memberp 4 64737
</PRE>
<P>This happens to be <CODE>true</CODE>, so <CODE>find</CODE> returns the value 4
without looking at the remaining digits. But if necessary, <CODE>find</CODE> would
have gone on to compute
<P><PRE>memberp 6 4737
memberp 4 737
memberp 7 37
memberp 3 7
memberp 7 "
</PRE>
<P>(using the empty word as <CODE>?rest</CODE> in the last line) until one
of these turned out to be true.
<P><H2>Further Explorations</H2>
<P>The obvious first place to look for improvements to this project is
in the strategy.
<P>At the beginning of the discussion about strategy, I suggested that
one possibility would be to make a complete list of all possible move
sequences, with explicit next-move choices recorded for each. How
many such sequences are there? If you write the program in a way
that considers rotations of the board as equivalent, perhaps not
very many. For example, if the computer moves first (in the center,
of course) there are really only two responses the opponent can make:
a corner or an edge. Any corner is equivalent to any other. From
that point on, the entire sequence of the game can be forced by the
computer, to a tie if the opponent played a corner, or to a win if
the opponent played an edge. If the opponent moves first, there are
three cases, center, corner, or edge. And so on.
<P>An intermediate possibility between the complete list of cases and
the more general rules I used would be to keep a complete list of
cases for, say, the first two moves. After that, general rules could
be used for the "endgame." This is rather like the way people,
and some computer programs, play chess: they have the openings memorized,
and don't really have to start thinking until several moves have passed.
This book-opening approach is particularly appealing to me because
it would solve the problem of the anomalous sequence that made such
trouble for me in rule 4.
<P>A completely different approach would be to have no rules at all,
but instead to write a <EM>learning</EM> program. The program might
recognize an immediate win (rule 1) and the threat of an immediate
loss (rule 2), but otherwise it would move randomly and record the
results. If the computer loses a game, it would remember the last
unforced choice it made in that game, and keep a record to try something
else in the same situation next time. The result, after many games,
would be a complete list of all possible sequences, as I suggested
first, but the difference is that you wouldn't have to do the figuring
out of each sequence. Such learning programs are frequently used
in the field of artificial intelligence.
<P>It is possible to combine different approaches. A famous checkers-playing
program written by Arthur Samuel had several general rules programmed
in, like the ones in this tic-tac-toe program. But instead of having
the rules arranged in a particular priority sequence, the program
was able to learn how much weight to give each rule, by seeing which
rules tended to win the game and which tended to lose.
<P>If you're tired of tic-tac-toe, another possibility would be to write
a program that plays some other game according to a strategy. Don't
start with checkers or chess! Many people have written programs in
which the computer acts as dealer for a game of Blackjack; you could
reverse the roles so that you deal the cards, and the computer tries
to bet with a winning strategy. Another source of ideas is Martin
Gardner, author of many books of mathematical games.
<P>
<TABLE width="100%"><TR><TD><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<TD align="right"><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A>
</TABLE>
<P><H2>Program Listing</H2>
<PRE>
;; Overall orchestration
to ttt
local [me you position]
draw.board
init
if equalp :me "x [meplay 5]
forever [
if already.wonp :me [print [I win!] stop]
if tiedp [print [Tie game!] stop]
youplay getmove ;; ask person for move
if already.wonp :you [print [You win!] stop]
if tiedp [print [Tie game!] stop]
meplay pickmove make.triples ;; compute program's move
]
end
to make.triples
output map "substitute.triple [123 456 789 147 258 369 159 357]
end
to substitute.triple :combination
output map [item ? :position] :combination
end
to already.wonp :player
output memberp (word :player :player :player) (make.triples)
end
to tiedp
output not reduce "or map.se "numberp arraytolist :position
end
to youplay :square
draw :you :square
setitem :square :position :you
end
to meplay :square
draw :me :square
setitem :square :position :me
end
;; Initialization
to draw.board
splitscreen clearscreen hideturtle
drawline [-20 -50] 0 120
drawline [20 -50] 0 120
drawline [-60 -10] 90 120
drawline [-60 30] 90 120
end
to drawline :pos :head :len
penup
setpos :pos
setheading :head
pendown
forward :len
end
to init
make "position {1 2 3 4 5 6 7 8 9}
print [Do you want to play first (X)]
type [or second (O)? Type X or O:]
choose
print [For each move, type a digit 1-9.]
end
to choose
local "side
forever [
make "side readchar
pr :side
if equalp :side "x [choosex stop]
if equalp :side "o [chooseo stop]
type [Huh? Type X or O:]
]
end
to chooseo
make "me "x
make "you "o
end
to choosex
make "me "o
make "you "x
end
;; Get opponent's moves
to getmove
local "square
forever [
type [Your move:]
make "square readchar
print :square
if numberp :square ~
[if and (:square > 0) (:square < 10)
[if freep :square [output :square]]]
print [not a valid move.]
]
end
to freep :square
output numberp item :square :position
end
;; Compute program's moves
to pickmove :triples
local "try
make "try find.win :me
if not emptyp :try [output :try]
make "try find.win :you
if not emptyp :try [output :try]
make "try find.fork
if not emptyp :try [output :try]
make "try find.advance
if not emptyp :try [output :try]
output find [memberp ? :position] [5 1 3 7 9 2 4 6 8]
end
to find.win :who
output filter "numberp find "win.nowp :triples
end
to win.nowp :triple
output equalp (filter [not numberp ?] :triple) (word :who :who)
end
to find.fork
local "singles
make "singles singles :me
if emptyp :singles [output []]
output repeated.number reduce "word :singles
end
to singles :who
output filter [singlep ? :who] :triples
end
to singlep :triple :who
output equalp (filter [not numberp ?] :triple) :who
end
to repeated.number :squares
output find [memberp ? ?rest] filter "numberp :squares
end
to find.advance
output best.move filter "numberp find [singlep ? :me] :triples
end
to best.move :my.single
local "your.singles
if emptyp :my.single [output []]
make "your.singles singles :you
if emptyp :your.singles [output first :my.single]
ifelse (count filter [? = first :my.single]
reduce "word :your.singles) > 1 ~
[output first :my.single] ~
[output last :my.single]
end
;; Drawing moves on screen
to draw :who :square
move :square
ifelse :who = "x [drawx] [drawo]
end
to move :square
penup
setpos thing word "box :square
end
to drawo
pendown
arc 360 18
end
to drawx
setheading 45
pendown
repeat 4 [forward 25.5 back 25.5 right 90]
end
make "box1 [-40 50]
make "box2 [0 50]
make "box3 [40 50]
make "box4 [-40 10]
make "box5 [0 10]
make "box6 [40 10]
make "box7 [-40 -30]
make "box8 [0 -30]
make "box9 [40 -30]
</PRE>
<P><A HREF="../v1-toc2.html">(back to Table of Contents)</A>
<P><A HREF="../v1ch5/v1ch5.html"><STRONG>BACK</STRONG></A>
chapter thread <A HREF="../v1ch7/v1ch7.html"><STRONG>NEXT</STRONG></A>
<P>
<ADDRESS>
<A HREF="../index.html">Brian Harvey</A>,
<CODE>bh@cs.berkeley.edu</CODE>
</ADDRESS>
</BODY>
</HTML>
|