[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Teeko, a new game (sounds interesting)
This message describes a game that's new to me and sounds interesting,
Teeko.
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.
Although most of the enclosed mail message describes a (very recent)
computer solution of Teeko, I suspect it's harder to solve or "cook"
than several other games which are known to be solved but still
played and enjoyed (e.g., connect4, connexxions, etc.).
Anyone up for programming it on pbmserv? sharkey?
Best,
- Scott
------- Forwarded Message
Date: Mon, 23 Nov 1998 11:46:26 PST
From: Guy Steele - Sun Microsystems Labs <gls@livia.East.Sun.COM>
To: guy.steele@East.Sun.COM, rkg@cpsc.ucalgary.ca, ken@mirror.org,
rcs@cheltenham.CS.Arizona.EDU
cc: math-fun@cheltenham.CS.Arizona.EDU
Reply-To: Guy Steele - Sun Microsystems Labs <gls@livia.East.Sun.COM>
Content-MD5: skSywzAhaI0vLOO8BmG1cw==
Subject: Re: Teeko, HAKMEM
Date: Fri, 20 Nov 1998 11:49:00 -0700 (MST)
From: Richard Schroeppel <rcs@cheltenham.cs.arizona.edu>
To: guy.steele@East, rkg@cpsc.ucalgary.ca, ken@mirror.org
Subject: Teeko, HAKMEM
I suggest Guy Steele should post the rules to math-fun, since my
summary from 25 years ago isn't really adequate.
Since there seems to be interest, here is a summary of the rules and what
I have done so far:
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.)
In later years, Scarne added some new twists to the game that change
the scoring but not the essential question of who wins, so this matters
only when a series of games is played. The number of points awarded
to the winner typically depends on either which winning configuration
is achieves, which piece was moved last (to achieve the winning configuration),
and/or which square the last piece was moved onto.
------- End of Forwarded Message