Editors Scientific American Sirs: I am writing to report that I have solved John Scarne's game "Teeko" ---Standard Teeko is a draw, Advanced Teeko is a first-player win--- and to inquire about publication in Scientific American. One possibility is that you might simply pass this note along to Ian Stewart to see whether he might want to devote one of his columns to it. I'd be happy to work with him to provide whatever information he needs. (Solving a game like this is, to me, a "classic Martin Gardner" topic; perhaps the younger generation might regard it as "classic Ian Stewart".) Alternatively, you might want to consider having me write a full-length article that would broaden the topic to cover various computational techniques for brute-force analysis of games, most notably the exploitation of symmetries to reduce the computational requirements. I would compare heuristics to complete analysis and discuss past efforts to solve subsets of chess (endgames) and estimate the level of effort required to solve checkers completely. This can be compared to the growth curve for computer power; as a result, I believe that checkers can be solved in my lifetime---and I am 44 now. This illustrates an interesting approach to solving difficult problems by computer, problems that might take a year or more: just wait until the (so far exponential) growth of computer power catches up with the problem, then solve the problem in a weekend. (I first set out almost a decade ago to solve Teeko on a Connection Machine supercomputer, but ended up using an ordinary desktop microprocessor---with a few hundred megabytes of main memory!) Attached is a summary of the game of Teeko and of my results in analyzing the game. Also attached are my credentials in brief. --Yours, Guy L. Steele Jr. ---------------------------------------------------------------- Distinguished Engineer, Sun Microsystems Laboratory, 1994-present Senior Scientist, Thinking Machines Corporation, 1985-1994 Assistant Professor, Computer Science, Carnegie-Mellon University, 1980-1984 PhD, MIT, 1980, computer science and artificial intelligence AB, Harvard, 1975, applied mathematics Fellow of the American Association for Artificial Intelligence, 1990 Fellow of the Association for Computing Machinery, 1994 Author of books on programming languages C, Common Lisp, Fortran, Java ---------------------------------------------------------------- Teeko is a simple board game invented by John Scarne, who was well-known earlier in this century as a magician and as an authority on games and gambling. The game enjoyed some popularity in the mid-1950's. Scarne wrote a book about it, "Scarne on Teeko", in 1955 (Crown Publishers), in which he boasted that Teeko was the equal of chess, checkers, and go and predicted that Teeko would "outclass Checkers and Chess in popularity within a very few years". The book contains 50 problems with proposed solutions and a few dozen annotated games. According to the book, Teeko clubs were formed in many cities around the world and the game was enjoyed by such celebrities as Art Buchwald, Humphrey Bogart, Lauren Bacall, Steve Allen, Marilyn Monroe, Joe DiMaggio, and Dave Garroway. (I'd love to research the history further.) The rules are simple. The game is played on a 5-by-5 square grid. Two players, Black and Red, each have four pieces (tokens) of their respective colors and alternate turns, Black going first. For the first eight turns, they alternate dropping a piece onto any unoccupied position of the grid. Thereafter, a turn consists of moving any one piece to an adjacent unoccupied position; a move may be horizontal, vertical, or diagonal. The goal for each player is to be the first to arrange his pieces into a winning configuration, either a straight line of 4 or a square. To be precise, for the "standard" form of the game, there are 44 winning configurations: in a contiguous straight line horizontally (10), in a contiguous straight line vertically (10), in a contiguous straight line diagonally (8), or in a small square of four mutually adjacent positions (16). For the "advanced" form of the game, also called "58 Positions", there are 14 additional winning configurations: at the corners of any 3-by-3 subgrid of the grid (9), at the corners of any 4-by-4 subgrid of the grid (9), or at the corners of the entire 5-by-5 grid (1). The 1972 MIT Memo "HAKMEM" (by Beeler, Gosper, and Schroeppel)---a potpourri of mathematical and computational trivia, tricks, techniques, and challenges---proposed the challenge of solving Teeko as its item 90. To "solve" a game such as Teeko (or chess, or checkers, or go-moku) is to determine precisely, with a proof, what the outcome of the game will be if both sides play optimally---that is, always making of the best available moves at each turn. There are three possible determinations: (a) the first player can always win; (b) the second player can always win; or (c) neither player can force a win, in which case the game is said to be a draw. We have solved Teeko by using a computer to enumerate all the possible positions of the game and calculating for each position a score that indicates whether that position is a forced win for Black, a forced win for Red, or neither. (If a position is a forced win, the score also indicates the maximum number of additional turns that will be needed by the winning side to achieve a winning configuration.) The algorithmic technique is iterative backward propagation of scores from the winning positions (whose scores are known ab initio). There are 75,710,250 ways to arrange the eight pieces on the 25 locations of the grid. (Scarne's book gives the figure 1,081,575, which is a factor of 70 = 8!/(4! 4!) too small, because he forgot to account for the fact that the pieces are of two different colors.) A small number of these positions cannot actually occur in a game because both sides have winning configurations simultaneously. The computer program uses one byte to encode the score for each position and stores the scores densely in a manner that allows the board position for a score to be decoded from its position in the table (the mathematics of this encoding is itself of interest, and can be described as a walk on Pascal's triangle). In this way, the game graph can be represented in just under 76 megabytes of memory. For technical reasons, it is convenient to have two copies of the table, which makes 152 megabytes. Tables to keep track of the positions during the "drop phase" (first eight turns) require another 53 megabytes, for a total of about 205 megabytes of main memory. (This is about 200 times the size of the main memory of the PDP-10 computer in use at the MIT AI Laboratory when HAKMEM was written.) I first worked on solving Teeko seven or eight years ago, while I was working at Thinking Machines Corporation, using a Connection Machine (CM-2) supercomputer; the largest size of CM-2 (65,536 processors) had 256 megabytes of memory, but unfortunately I never was able to get enough computer time on a full-size machine to test my program and then do the full computation. This year, I realized that this supercomputer-sized task had become a desktop-sized task: workstations and servers with a gigabyte of memory were not hard to come by, so I hauled out my old code and spent a couple of weeks cleaning it up and carefully desk-checking it. Here at Sun Microsystems Laboratories, on a Sun compute server, using one 300 MHz UltraSPARC processor, solving Standard Teeko took just under 32 hours and 15 minutes (October 24--25, 1998); solving the Advanced Teeko took just under 45 hours (October 30--November 1, 1998). It might have been done more quickly, but I placed an emphasis on keeping the code fairly simple so that its correctness would be easier to demonstrate or verify. The results: STANDARD TEEKO (44 POSITIONS) IS A DRAW. ADVANCED TEEKO (58 POSITIONS) IS A FIRST-PLAYER WIN. In addition, we have analyzed the game in more detail. For example, we know that the only winning first move for Black in Advanced Teeko is to drop a piece on the center position of the grid. If the rules for Advanced Teeko were to be amended to prohibit Black from dropping his first piece on the center position, then the amended game would be a draw. Scarne defined seven variations in which the opponent is allowed to choose the position on which to drop certain pieces. For example, in what he called the "Alternate Style", Red always decides where Black's pieces should be dropped and Black always decides where Red's pieces should be dropped. In the "Two-Move Alternate Style", the sequence is: (1) Red decides where Black's first piece should be dropped; (2) Black decides where Red's first piece should be dropped; (3) Red decides where Black's second piece should be dropped; (4) Black decides where Red's second piece should be dropped; (5) Black decides where Black's third piece should be dropped; (6) Red decides where Red's third piece should be dropped; (7) Black decides where Black's fourth piece should be dropped; (8) Red decides where Red's fourth piece should be dropped. In all these variations, play continues normally once all eight pieces have been dropped, each player making decisions for his own pieces. In all, then, Scarne defined sixteen forms of the game, and we have solved them all: Standard DRAW Alternate DRAW One-Move Alternate DRAW Two-Move Alternate DRAW Three-Move Alternate DRAW One-Move Standard DRAW Two-Move Standard DRAW Three-Move Standard DRAW Standard, 58 Positions FIRST-PLAYER WIN (in 13 turns) Alternate, 58 Positions DRAW One-Move Alternate, 58 Positions DRAW Two-Move Alternate, 58 Positions DRAW Three-Move Alternate, 58 Positions DRAW One-Move Standard, 58 Positions FIRST-PLAYER WIN (in 25 turns) Two-Move Standard, 58 Positions DRAW Three-Move Standard, 58 Positions DRAW The first-player win for "One-Move Standard, 58 Positions" can also be changed to a draw by forbidding Black to drop his first piece in the center. Moreover, this prohibition would not change the outcome for any of the other 14 variations, so one might recommend this prohibition generally for all forms of Teeko. Teeko also has an extra rule designed to avoid the dull repetitions in which one player shuttles a single piece back and forth. (Chess and Go have similar "extra rules".) In Teeko, if one player moves a piece from position A to position B and then moves it back to position A, then the other player can invoke a four-move limit: one of the next four moves by the first player must be other than moving that one piece to A or B. Our analysis shows that under certain circumstances this extra rule can actually be used to convert a tied position to a forced win, but only in situations where the player invoking the rule himself shuttles a piece back and forth! This hardly seems fair. We would recommend that the rule be amended to say that a player may invoke the rule against his opponent only on a turn in which he himself does not move a piece back to the position it occupied before his previous turn. in this connection, there is one interesting anomaly in the advanced game that does not occur in the standard game: there is a cycle of four positions with the property that each player has exactly one move that maintains the draw (any other move loses), and the net result is that perfect play requires each player to shuttle a single piece back and forth: - O O O - @ O O O - @ O O - - - O O - - O @ - @ - O - - @ - O - O @ - O @ O @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ - - @ - @ - - @ - @ - - @ - @ - - @ - Red threatens Black blocks; Now Black must And Red needs to make four now, if Red block formation another immediate in a row does not occupy of a small square. counter-threat upper right corner, to prevent Black Black will take it from forming the and win on the next corners of a move by taking lower 3-by-3 square. right corner; but if (It cannot be to Red occupies upper move Red's leftmost right corner, Black piece upward, takes vacated position for Black would then and two moves later immediately win with completes corners of the corners of a a 4-by-4 square. 4-by-4 square.) The only way out for So Red must shuttle Red is an immediate his piece back to counter-threat. where it was. (It cannot be to move Red's leftmost piece to the right, for Black would then immediately win with the corners of a 4-by-4 square.) With the original four-move limit rule, whoever decided to invoke the rule first would win. With the amended rule, neither player would find it in his best interest to invoke the rule, because it would require him to make a losing move! As a result, the game, with best play, would remain drawn. In all other cases, one player can invoke the rule safely and the other player can then comply while maintaining the draw. Teeko has a second "extra rule" designed to prevent a player from boxing one of his opponent's pieces into a corner: if a player finds that one of his pieces cannot be moved because it is in a corner of the grid and is surrounded by three of his opponent's pieces, he may invoke a ten-move limit: one of the next ten moves by his opponent must be with one of the three pieces boxing him in. Our analysis shows that invoking this rule does not affect the outcome of the game when the game is played perfectly; that is, if the position is drawn when a piece gets boxed in, then the player against whom the rule is invoked can always maintain the draw while satisfying the rule. We have also written software that reads in the moves of a game and annotates the game, showing at each step the expected outcome of the game if the remainder of the game were to be played perfectly. We have run 30 games and 50 problems from Scarne's book through this annotation software, which allows us to check the quality of Scarne's commentary. For the most part it is accurate, but there are a few exceptions (which only goes to show that Scarne was human). For example, three of the problem positions, given as "Black to win" or "Red to win" are actually draws. For the purpose of notating move sequences, Scarne numbered the squares of the board thus: 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 Here is an example of a problem and its automatic annotation: #Problem No. 6, page 151 problem: Black on 14 18 19 24; Red on 13 15 17 23; Red to move and win Initially: Red in 9 - - - - - - - - - - - - O @ O - O @ @ - - - O @ - 15-9 ! Red in 8 18-22 ! Red in 7 23-18 ! Red in 6 14-8 ! Red in 5 18-14 ! Red in 4 8-4 Red in 3 9-15 Red in 2 22-16 Red in 1 17-12 ! Red wins Here is an example of a game and its automatic annotation: #Standard Game No. 8, page 125 game 19 Draw 13 Draw 18 Draw 17 Draw 24 Draw 23 !! Draw 14 ?? Red in 9 (best: 7, 8, 9, 12, 15, 16, 20, 21, 22, 25 Draw) 12 ?= Draw (best: 9 Red in 8) 14-9 !! Draw 13-14 !! Draw 9-13 Draw 12-8 Draw 18-12 Draw 8-7 Draw 24-18 Draw 23-22 ?? Black in 7 (best: 7-2, 7-6, 7-8, 7-1, 7-3, 7-11, 14-15, 17-16, 23-24 Draw) 12-8 ?= Draw (best: 19-23 Black in 6) 22-23 Draw 19-15 Draw 14-9 ?? Black in 3 (best: 7-2, 7-3, 17-12, 23-22, 23-24, 23-19 Draw) 8-14 ! Black in 2 17-12 Black in 1 15-19 ! Black wins The notation "!" means that the move is the unique best move in that position; "!!" means that the move is not only the best move, but in fact the only move that avoids losing; "?=" means that a win was thrown away, leaving a draw; "??" means that a draw was thrown away, leaving a lost position. We have also analyzed the game graph to find the longest available forced wins. For the standard game, with all 8 pieces on the board, the longest forced win is 39 turns (that is, with, say, Black to move, then Black can force a winning configuration no later than his 19th move). For the advanced game (58 Positions), the longest forced win is 59 turns. There are other interesting variants of Teeko to be explored. For example, what if other winning configurations are allowed, such as "tilted squares"? What if the board were regarded as toroidal (the edges "wrap around")? What if the board were infinite in size? (Red would have an interest in staying near Black's pieces.) ----------------------------------------------------------------