Beeler, M., Gosper, R.W., and Schroeppel, R. HAKMEM. MIT AI Memo 239, Feb. 29, 1972. Retyped and converted to html ('Web browser format) by Henry Baker, April, 1995.

GAMES

Previous Up Next

ITEM 67 (Schroeppel):

Regarding "poker coins" game, whose rules are:
  1. a player throws N coins; he then puts one or more aside and rethrows the rest
  2. this throwing is repeated until he no longer has any to throw
  3. highest score (dice) or maximum number of heads (coins) wins
For poker coins, the optimal strategy, with N coins thrown, is:

Z = number of zeros (tails)

The optimal strategy for poker dice is hairier.

ITEM 68 (Schroeppel):

PROBLEM: Solve Blackout, a game as follows:

Two players alternate placing X's on a rectangular grid. No two X's may appear adjacent along a side or across the diagonal at a corner. The last X wins.

Some theory: The "indicator" for a position is: make all possible moves from the given position.

Evaluate the indicator of each of these successor positions.

The indicator of the first position is the smallest number which is not the indicator of a successor position. The indicator of the null position is 0. The second player wins iff the indicator is 0. Example of calculating an indicator for the 3 x 3 board: There are 3 distinct moves possible -- corner, side, center. Playing in the center leaves the null position, indicator 0. Playing on the side leaves a 1 x 3 line, indicator 2. Playing in the corner leaves a 3 x 3 L, indicator 3. The smallest number not appearing in our list is 1, so the indicator of a 3 x 3 square is 1. For two boards (not touching) played simultaneously, the indicator is the XOR of the indicators for the separate boards. For any position, the indicator is <= the maximum game length.

PROBLEM: Find some non-exponential way to compute the indicator of a given position. For lines, a period of 34 is entered after the line is about 80 long. For Ls: if one leg is held fixed, the indicator (as a function of the other leg) seems to become periodic with period 34. The time to enter the period becomes greater as the fixed leg increases.

This indicator analysis is similar for many other take-away games, such as Nim.

ITEM 69:

Berlekamp of Bell Labs has done the 9 squares (16 dots) Dots game; the 2nd player wins.

ITEM 70:

A neat chess problem, swiped from "Chess for Fun and Chess for Blood", by Edward Lasker:

white: pawns at QN3 and KN7, knight at QN4, bishop at KB7, king at QB2;

black: pawn at QN3, king at QR6. White mates in three moves.

ITEM 71 (Beeler):

There is only one distinct solution to the commercial "Instant Insanity" colored-faces cubes puzzle, which is how it comes packed. (Independently discovered by Dave Plumer.) Mike Paterson has discovered a clever way to solve the puzzle.

ITEM 72 (Beeler):

A window-dice game is as follows:
  1. The player starts with each of nine windows open, showing the digits 1 - 9.
  2. Roll two dice.
  3. Cover up any digits whose sum is the sum on the dice.
  4. Iterate throwing and closing windows until the equality of sums is impossible.
  5. Your score is the total of closed windows (highest wins).
An optimum strategy has been tabulated. Usually it is best to take the largest digits possible, but not always; it also depends critically on the remaining numbers.

ITEM 73 (Beeler):

Sim is a game where two players alternately draw lines connecting six dots. The first person can always win, and whether his first move connects with the first player's first move doesn't matter; from there on, however, the strategy branches to a relatively gruesome degree.

PROBLEM: 6 dots is minimum to ensure no stalemate with 2 players; how many dots are required with 3 players?

ITEM 74 (Beeler):

The 4 x 4 game of Nim, also known as Tactix, is a win for the second player, who on his first move can reply center-symmetrically unless the first player's first move was B1 and B2 (analyzed on RLE PDP-1).

ITEM 75 (Gosper, Brown, Rayfield):

A 1963 PDP-1 computer program gave us some interesting data on the traditional game of peg solitaire (33 holes in a plus shape). 
    A B C
    D E F
G H I J K L M
N P Q . S T U
V W X Y Z 1 2
    3 4 5
    6 7 8
From the starting position, complement the board. This is the ending position. Now from the starting position, make one move, then complement the board. This is a position one move from a win. By induction, you can win from the complement of any position you can reach. Thus every successful game has a dual game whose positions are the complements of the original ones. This debunks the heuristic of emptying the arms of the plus first and then cleaning up the middle, because there are just as many dual games which empty out the middle first and then the arms! The program found one counterintuitive win which at one point left the center nine empty but had ten in the arms. 
    . B .
    D E .
. . . . . . .
. P . . . T U
V W . . . . .
    . 4 .
    . 7 .
By dualizing and permuting a solution from the folklore, we found a similar winning position with 20. (T Q 4 R 1 L J H W Y M J) leaves: 
    A B C
    D E F
G H . . . L .
N . . . . . U
V W . . . 1 2
    3 . 5
    6 7 8
then (8 V A C/B 2 6 G M F/K S 8 1 Y V 3 Q A H E).

Another useful observation is that the pegs and their original hole positions fall into four equivalence classes in which they stay throughout the game. Thus the four pegs which can reach the center on the first move are the only ones that ever can. Similarly, the peg jumped over on the last move must be in one of the two classes of eight members which get reduced on the first move. The program's main heuristic was to reduce the larger classes first. 

    a b a
    c d c
a b a b a b a
c d c . c d c
a b a b a b a
    c d c
    a b a
With its heuristics disabled, the program simply scanned lexicographically (left to right in the inner loop, then top to bottom) for a peg which could move. At one point, there is a peg which can move two ways; it chose west. Twelve moves from the end it stopped and went into an exhaustive tree search, in which it found two basically different wins. (Try it yourself.) 
    . . .
    . . .
. . . . K . .
. . Q . . . .
. . X Y Z 1 2
    3 4 5
    6 7 8

ITEM 76 (Beeler):

Triangular Hi-Q (or peg solitaire) is 15 pegs in a triangle. Once peg is removed, and thereafter pegs jump others, which are removed. With pegs numbered 1 at the top, 2 and 3 in the next row, etc., 
REMOVE  CAN END WITH ONLY THE PEG
1       1, 7 = 10, 13
2       2, 6, 11, 14
4       3 = 12, 4, 9, 15
5       13
Removing only one, no way exists to get to either 1 + 11 + 15 (tips) or 4 + 6 + 13 (centers of sides). Starting with peg 1 removed, 3,016 positions are attainable (not turning board); the sum of ways to get to each of these is 10,306. An example is: remove peg 1, then jump as follows: 6, 13, 10, 1, 2, 11, 14/13, 6, 12/13, 15, 7/4, 13, 4; leaving peg 1.

Previous Up Next