SUMMARY OF THE SOLVING OF THE GAME OF TEEKO (DRAFT) Guy L. Steele Jr. Sun Microsystems Laboratories 1 Network Drive Burlington, MA 01803 (781)442-2620 guy.steele@east.sun.com October 1999 ABSTRACT Standard Teeko (44 goal positions), as defined by John Scarne, is a draw. Advanced Teeko (58 goal positions) is a first-player win, but becomes a draw if one stipulates that the first drop may not occupy the center. All eight Scarne-defined variants of Standard Teeko are draws. Of the eight Scarne-defined variants of Advanced Teeko, six are draws and two are first-player wins that becomes draws if one stipulates that the first drop may not occupy the center. We also analyze other aspects of Teeko and consider other variants such as allowing pieces to move as chess knights rather than as chess kings. DESCRIPTION OF TEEKO Teeko is a game invented and marketed by John Scarne and described at length in his book "Scarne on Teeko" (Crown, New York, 1955). While it has not yet supplanted chess and checkers as Scarne optimistically predicted, it is a pleasant, well-designed game that at least deserves to be taught to children as they outgrow tic-tac-toe. In brief, Teeko is a game in which two players, Black and Red, alternately drop tokens of their respective colors onto a 5-by-5 grid. After each player has dropped four tokens, they continue to alternate turns; at each turn a player may move one of his tokens to an empty adjacent position on the grid, either orthogonally or diagonally. A player wins if he can achieve a goal configuration with his four tokens. Scarne defined two versions of the game. Standard Teeko has 44 goal configurations: four tokens in a contiguous line vertically (10 configurations): @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ @ - - - - - @ - - - - - @ - - - - - @ - - - - - @ four tokens in a contiguous line horizontally (10 configurations): @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ - - @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ @ @ four tokens in a contiguous line diagonally (8 configurations): @ - - - - - @ - - - - - - - - - - - - - - @ - - - - - @ - - @ - - - - - @ - - - - - @ - - - - - @ - - @ - - - - - @ - - - - - @ - - - - - @ - - @ - - - - - @ - - - - - - - - - - - - - - @ - - - - - @ - - - - @ - - - @ - - - - - - - - - - - - - - @ - - - @ - - - - - - @ - - - @ - - - @ - - - @ - - - - - - @ - - - @ - - - @ - - - @ - - - - - - @ - - - @ - - - - - - - - - - - - - - @ - - - @ - - - - or four tokens forming a 2-by-2 square (16): @ @ - - - - @ @ - - - - @ @ - - - - @ @ @ @ - - - - @ @ - - - - @ @ - - - - @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ - - - - @ @ - - - - @ @ - - - - @ @ @ @ - - - - @ @ - - - - @ @ - - - - @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ - - - - @ @ - - - - @ @ - - - - @ @ @ @ - - - - @ @ - - - - @ @ - - - - @ @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ @ - - - - @ @ - - - - @ @ - - - - @ @ @ @ - - - - @ @ - - - - @ @ - - - - @ @ Advanced Teeko has 58 goal positions: the 44 positions of Standard Teeko, in addition to four tokens at the corners of a 3-by-3 square (9): @ - @ - - - @ - @ - - - @ - @ - - - - - - - - - - - - - - - @ - @ - - - @ - @ - - - @ - @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ - @ - - - @ - @ - - - @ - @ - - - - - - - - - - - - - - - @ - @ - - - @ - @ - - - @ - @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ - @ - - - @ - @ - - - @ - @ - - - - - - - - - - - - - - - @ - @ - - - @ - @ - - - @ - @ of a 4-by-4 square (4): @ - - @ - - @ - - @ - - - - - - - - - - - - - - - - - - - - @ - - @ - - @ - - @ - - - - - - - - - - - - - - - - - - - - @ - - @ - - @ - - @ - - - - - - - - - - - - - - - - - - - - @ - - @ - - @ - - @ or of the entire 5-by-5 board (1): @ - - - @ - - - - - - - - - - - - - - - @ - - - @ Many other persons have independently suggested a third version with 78 goal positions, in which four tokens at the corners of squares tilted with respect to the game board also constitute a goal position: - @ - - - - - @ - - - - - @ - - @ - - - - - @ - - @ - @ - - - @ - @ - - - @ - @ - - - @ - @ - - - - - @ - - - - - @ - - - - - @ - @ - - - - - - - @ - - - - - - - - - - - - - - - - - - @ - - - @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ - - - - - @ - - @ - - - - - @ - - - - - @ - - - - - @ - @ - - - @ - @ - - - @ - @ - - - @ - @ - @ - - - - - - - @ - @ - - - - - @ - - - - - @ - - - - @ - - - @ - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - @ - - - - - @ - - - @ - - - - - @ - - - - - @ - - - - @ - @ - - - - @ - @ - - - @ - @ - - - @ - @ @ - - - - - - - @ - - @ - - - - - @ - - - - - @ - - - @ - - - @ - - - - @ - - - - - @ - - - - - @ - - - - - - - - - - - - - - - @ - - - - - @ - - - - - @ - - - - - @ - - - - - - - @ - - - @ - - - - - - - - @ - @ - - - - @ - - - - - - - - - - - - - @ @ - - - - - - - @ - - - - @ - - - @ - - - @ - - - - - @ - - - @ - - - Scarne himself never discussed this variant, as far as I know. We will call this version "Teeko 78". In Teeko there are no tie positions, that is, positions in which the player to move cannot move. Like chess, checkers, and tic-tac-toe, Teeko is a two-player game with where both players have perfect knowledge of the game situation at all times and there is no element of chance. It is not difficult to see that, with best play by both players, Teeko is necessarily either a first-player win, a second-player win, or a draw by reason of the game not terminating. COMPUTER ANALYSIS In late 1998, we proved by an exhaustive computer analysis that Standard Teeko is a draw but Advanced Teeko is a first-player win. However, Advanced Teeko can be converted to a sporting draw by the simple device of prohibiting the first player from dropping his first token in the center position of the board. We also found that Teeko 78 is a first-player win that can be converted to a draw by forbidding the first player from dropping his first token in any of the nine central squares of the board. We also investigated variants of the game in which, when a token is moved, it is moved to an empty position that is a knight's move away rather than adjacent. Teeko 58 with knight moves is a first-player win if the first player makes his first drop anywhere but a corner, but if he makes that first drop in a corner then the second player wins. The same result applies to Teeko 78 with knight moves. Teeko 44 with knight moves turns out to have a tie position, in which the player to move cannot move: @ - - - @ - - O - - - O - O - Black, to move (using a knight's move), cannot move - - O - - @ - - - @ We are investigating other variants as well. The results so far might lead us to believe that Scarne, in his fifteen years (his figure) of refining Teeko, seems to have found a local optimum in the design space. Scarne himself defined eight variants of Standard Teeko and eight variants of Advanced Teeko in which, during the first eight moves of the game, certain drops are made to squares chosen by the opponent rather than by the player making the drop. These may be described by stating which of a player's four drops are dictated by his opponent: none, all, first one, first two, first three, last one, last two, or last three. Scarne never defined, but we have also investigated, eight other possibilities as well: second only, third only, first and third, second and fourth, first and fourth, second and third, all but the second, and all but the third. We have analyzed all sixteen variants of each game with results as follows: Standard Teeko Advanced Teeko Teeko 78 none draw first player first player all draw draw first player first one draw draw first player first two draw draw first player first three draw draw first player last one draw draw first player last two draw draw first player last three draw first player first player second only draw draw first player third only draw draw first player first and third draw draw first player second and fourth draw draw first player first and fourth draw draw first player second and third draw draw first player all but the second draw first player first player all but the third draw first player first player All eight variants of Advanced Teeko that Scarne defined convert to, or remain, draws if it is forbidden to drop the first token of the game in the center position of the board. However, this rule does not rescue the variants "all but the second" and "all but the third". All sixteen variants of Standard Teeko remain draws if it is forbidden to drop the first token of the game in the center position of the board. This rule does not rescue any of the variants of Teeko 78. Therefore our recommendations to Teeko players would be: (a) to abandon Teeko 78, even though it seems constantly to be "reinvented" by Teeko enthusiasts, because analysis shows it to be fatally flawed; (b) to stick with the eight possibilities for having opponents choose drops that were proposed by Scarne, because the other eight introduce flaws into Advanced Teeko; and (c) to alter Scarne's rules for Advanced Teeko, and perhaps also for Standard Teeko, by adopting a uniform proviso that the first token of the first player may not be dropped in the center position of the board. ANALYZING SCARNE'S GAMES AND PROBLEMS Scarne's book "Scarne on Teeko" contains a large number of games, with annotations by Scarne, as well as composed problems. We analyzed these games, problems, and problem solutions by having a computer print the value ("Draw", "Black in 5", etc.) of each successive position assuming best play from that point on. Here is an example of the output of such a computer analysis: #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 (Note that we use a conventions of counting plies, so that the "Black in n" count steadily decreases; this is in contrast to the convention in chess of counting moves by just one side when stating how long it will take to win with best play.) The computer not only prints the value of the position after each move, but may also provide an annotation to indicate the quality of the move: ! the unique best move available !! the only move that preserves the win or preserves the draw ? not the best move (loses faster or wins slower) ?! the only move that is not one of the best ?= a move that converts a win to a draw ?=! the unique move that converts a win to a draw ?? a move that converts a draw to a loss ??! the unique move that converts a draw to a loss ??? a move that converts a win to a loss ???! the unique move that converts a win to a loss Finally, if the given move was not one of the best moves, then the computer lists the best moves available from that position and what the value of the game would have been if one of those moves had been chosen. ANALYZING SCARNE'S ANALYSIS We then performed a meta-analysis by hand, comparing Scarne's extensive comments on thirty games of Standard Teeko to the comments produced by the computer. Out of these 30 games: Number of games in which Scarne correctly identifies the last move that loses the draw: 25 Number of games in which Scarne identifies a move as losing but the game was actually lost at an earlier move: 1 Number of games in which there is at least one losing move that Scarne fails to identify as a losing move: 12 (and two of these games contain two such unidentified losing moves). However, it must be conceded that Scarne made no claim to have identified or to have intended to identify all such moves. In one game, Scarne called a move good but it was nonoptimal. In one game, Scarne called a move good but in fact it was a losing move. In six games, Scarne identified a total of eight moves as "forced" and in fact they were forced. In four games, Scarne identified a total of four moves as "forced" but there were other moves available that were just as good or better. In one game, Scarne said that a move was a losing move but in fact the move does not lose the game with best play. From this we can perhaps infer that Scarne's grasp of the game was, as he claimed, quite good, but it was certainly not perfect. ANALYSIS OF ADVANCED TEEKO GAMES Scarne gave five examples of games of Advanced Teeko "played by the more expert members of the Fairview Teeko Club". He did not annotate these games, but he did comment that they "are not to be considered as perfect, but they are the best available at the time of writing". Computer analysis shows that in each of the five games presented, the player who did not win the game had a won position at some point in the game and then threw it away, sometimes by converting from a won to a lost position directly and sometimes by converting a win to a draw and then later converting the draw to a loss. It is certainly understandable that a player might miss a "win in 37" and choose a drawing move instead; but in one case a very simple win in 5 (what in chess would be called a win in 3) was overlooked. #Game No. 1 (58 positions), page 228 game 2 ?= Draw (best: 13 Black in 12) 7 Draw 5 Draw 13 Draw 17 Draw 20 !! Draw 25 Draw 1 Draw 25-19 !! Draw 13-14 ?? Black in 17 (best: 7-12, 7-8, 13-8, 13-9 Draw) 5-4 ?= Draw (best: 5-9 Black in 16) 7-13 ?? Black in 25 (best: 7-12, 7-8, 14-9 Draw) 4-9 ?= Draw (best: 2-7 Black in 24) 1-7 !! Draw 9-5 ?? Red in 11 (best: 2-1, 2-3, 2-6, 2-8, 9-10, 9-15, 17-12, 17-16, 17-18 Draw) 7-12 ! Red in 10 19-15 ! Red in 9 12-18 ? Red in 12 (best: 14-19 Red in 8) 15-19 ! Red in 11 - @ - - @ - - - - - - - O O - - @ O @ O - - - - - *18-12! 19-15! 14-19! 2- 7! 12-18! 15-14! 18-23! Red in 4 18-23 ??? Black in 7 (best: 18-12 Red in 10) 5-9 Black in 6 13-7 ! Black in 5 - @ - - - - O - @ - - - - O - - @ - @ O - - O - - 19-13 ?= Draw (best: 2-1 Black in 4) 14-10 Draw 17-22 Draw 23-17 Draw 2-8 Draw 10-5 Draw 8-2 !! Draw 20-19 Draw 22-23 ?? Red in 5 (best: 13-18, 13-12, 13-14, 22-21, 22-18 Draw) 7-1 ! Red in 4 23-22 Red in 3 17-21 ! Red in 2 9-15 Red in 1 19-25 ! Red wins The computer was directed to print the position at two critical points in the game. The line beginning with "*" is the computer's recommendation as to the best line of play. It can be seen that early in the game Red made some subtle missteps, giving Black distant wins (in 17 and in 25), but Black did not recognize them; then Black gave Red a win in 11, which Red did not play optimally and soon blundered away (pictured); but Black then threw away an easy win (pictured) and subsequently blundered into a loss to Red in 5, which Red then executed perfectly. DISCOVERY OF LENGTHY WINS For each of Standard Teeko, Advanced Teeko, and Teeko 78, the computer was directed to print positions that are not draws but are of the maximal number of moves away from the forced win, assuming best play by both players. For Standard Teeko, these positions (and their rotations and reflections) are won for Black (with Black to move) in 39 plies: - O @ O - O - @ - - - - - @ O - - - @ O O - @ - - - - - - - - - - - O O - - - - O - - - - - - - @ O - - - - - O - - - - O - - - - O @ - - - - - - - - O - @ - - @ - - - - - @ - - - - - - - - O - - - - O @ @ - - O - @ @ - - O - @ @ - O - @ @ - O @ - @ For Advanced Teeko, these positions (and their rotations and reflections) are won for Black (with Black to move) in 59 plies: O - - - - - - O - - - - O - @ - O - @ - - @ O - - O @ - - O - @ - - - O - - - O O - - - O - - - - - @ - - - - O - - - O @ - - - - @ - - - - O - - - O - - - - - @ - - - - - - - @ - - - - @ - @ - - @ - - - O @ @ - - O @ @ O - - - @ O - - - @ - - O - @ O O @ - O - - O - - - - O @ - O - @ - - O - - @ - - - - - - - - - - - O - - - O O - - - O O - - @ O - - - - - O - @ - O @ - - - - @ - - - - - - - - - @ - - - - @ - - @ - - - - @ - - - - @ - @ - - - - - O - @ @ - - O - @ O - - - @ - - O - @ - - O @ - O O @ - O - - O - - - O - - @ O @ - - - - @ O - - - - - - - - - @ - - O - - - O O - - - O O - @ - - @ - - - - O - - - O @ - - - - @ - - - - - - - O - - - - - - @ - - @ - - - - @ - - - - @ - - - @ - - - O - @ @ - - O - @ O - - - @ - - O - @ - - - O @ - @ O - - - O @ - - O @ - - - - - - - - - - - O - O @ @ - O - - @ - - - O - - - - - - O @ - - - @ - For Teeko 78, these positions (and their rotations and reflections) are won for Red (with Black to move) in 78 plies: O - - @ - O - - @ - - - - - - - - - - O O - - - O O - - - - O - - - - O - - - - @ @ @ - - @ @ @ - - and these positions (and their rotations and reflections) are won for Black (with Black to move) in 77 plies: - @ - - - - - @ - - - - - @ - - - - - @ - - - - - - - - - O - - - - O - - - - O - - - - O O @ - - - - O - - - O - - - - O O - - - O - - - - - - - - O O - - - - O O - - - O - - - - O O - - - - - - O O O @ @ - @ - @ @ - @ - @ @ - @ - @ @ - @ @ - @ - @ - - @ - - - - - @ - - - - @ - O - - - @ - - - - O O - - - - - - - - O - O - - - O O - - - - - - O O O - - - - - - - - O O - - - - - - - - O O O - - - - - - - O - @ @ - @ @ - @ @ - - @ @ - @ @ @ @ - - The apparent close correlation between the number of goal positions and the length of the most distant win is perhaps only coincidental.