Copyright (c) 1960 Martin Gardner
The game is played on a NxN square. The board starts empty
- Each player drops a stone into an empty cell, which does not
form a square with 3 other placed stones of the same color.
are not just formed by orthogonal lines, they can make any slope with the board edge.
- Wins the player that moved the last stone.
White cannot play at  since it would form
a square with c5,e4 and d2 stones.
Black cannot also play there since it
would form a black square with b5, d5 and d3.
Gardner, on his legendary Scientific American articles, states that if the board size is even (like
the 8x8 Chess board), the game is a win for the 2nd player. Why? He just needs to
mirror what the 1st player is doing, until his opponent is out of legal moves.
There are two ways to remedy this:
1) Play on odd sized boards, with a center cell where the 2nd
player cannot continue to use the mirror strategy.
2) Each player moves twice (except for the first move of the
first player). This version, called DM Hip was designed by Mark Thompson
and is presented at his website.
In July 2014 I received an email from
Kurt Alan Franke which wrote a min-max solver and found that the 5x5
version is a win for player 2 (the solver evaluated 8331853 positions).
He also wrote a blog
entry about this which I'll copy-paste here in the interest of
[The 6x6 board] an interesting problem to solve numerically. There are
2^36 possible filled board positions, but “only” 36 choose 18 have an
even number of counters. We know that the 6x6 board has possible draw
games, but how many? And what about larger or smaller boards?
The 6x6 board has 2^36 possible filled board positions. Iterating
through all of them and checking for a draw game takes ~1 hour. 7x7
boards have 2^49 possible filled board positions — that will take a long
time to iterate through.
But there is a trick! A 6x6 subset of a draw game on a 7x7 board must be
a draw game on a 6x6 board. We only need to iterate through all possible
6x6 draw games, and for each one expand with all possible combinations
for the 2*6+1 additional board places. Using this strategy, the results
are calculated extremely fast. I used straight c for this because of the
abundance of bit-twiddling involved.
Here are the number of draw games as the board size increases. Playable
draws are restricted to states that can be reached during game play
whereas “draws” are any filled board with no completed squares, even if
the number of pieces played by each side is not equal.
Board Draws Playable Draws
(2x3) 50 20
(3x3) 248 92
(3 x 4) 1236 482
(4 x 4) 5006 2094
(4 x 5) 18282 7236
(5 x 5) 7120 2704
(5 x 6) 5684 2316
(6 x 6) 56 24
(6 x 7) 0 0
(7 x 7) 0 0
So there are no draw games on boards larger than 6x6. The number of
draws first increases rapidly as the possible number of filled boards
goes up exponentially, but then falls quickly since the possible number
of “squares” is increasing.
Can you find a draw board for the 6x6 game by hand?
Next question: What is the value of the game for the different board
sizes? If both players are perfect, will the game be a draw, or will
player 1 or player two win the game?
So, to answer this question, I wrote a min-max solver to find the value
of the game of Hip. The search space increases rapidly with board size,
as players may play on any open place. Consider: at a size of 6x7 or
larger, there must be a winner because there are no draw positions. The
smaller boards have many draw positions, so it seems likely that the
values of these games are zero. Boards with an odd number of spaces seem
to favor player 2 because player 1 has to make the first and last moves.
A simple exhaustive min-max search got bogged down on 4x4 boards, but
there were room for improvements:
Cache computed results with a hash of the board state.
Cache the state symmetrically to avoid repeating different
rotations/inversions of the same position.
Use a heuristic to order the search of possible plays at each level.
This is a simple position evaluator which tries to score each move
based on partially completed squares and plays no longer available
(because they would complete a square).
Optimize the weighting factors for the heuristic by calculating the
number of function calls needed for solving mid-sized games. The
most important factor seems to be avoidance of obstructing the
opponent’s partially completed squares.
Instead of having both players trying to win, allow one to be
satisfied with a draw. If the other player can’t beat the
draw-accepting opponent, then he also couldn’t beat the cut-throat
opponent. On the other hand, if he *can* beat the draw-accepting
opponent, then he could beat any opponent. Of course, this won’t
help in pruning the search tree on larger games where no draw is
Using these improvements, I was able to solve the 5x5 game in 30 seconds
of run time. I also looked at a variant called Double-Hip where player 1
first makes a single move followed by players taking turns making two
moves at a time.
The hippest winners:
3x3 — Hip: Draw Double-Hip: Player 2
3x4 — Hip: Draw Double-Hip: Draw
3x5 — Hip: Draw Double-Hip: Player 1
3x6 — Hip: Draw Double-Hip: Draw
3x7 — Hip: Draw Double-Hip: Player 2
3x8 — Hip: Draw Double-Hip: Draw
3x9 — Hip: Draw Double-Hip: Player 1
3x10 - Hip: Draw Double-Hip: Draw
3x11 - Hip: Draw Double-Hip: Draw
3x12 - Hip: Draw Double-Hip: Draw?
4x4 — Hip: Draw Double-Hip: Draw
4x5 — Hip: Draw Double-Hip: Player 1
4x6 — Hip: Draw Double-Hip: Player 1
4x7 — Hip: Player 2 Double-Hip: Player 1
4x8 — Hip: Player 2 Double-Hip: Draw
4x9 — Hip: Player 2? Double-Hip: Player 2?
5x5 — Hip: Player 2 Double-Hip: Player 1
5x6 — Hip: Player 2 Double-Hip: Player 2
5x7 — Hip: Player 2? Double-Hip: Player 2?
6x6 — Hip: Player 2? Double-Hip: Player 2?
Note that the results with a ‘?’ are from non-exhaustive searches, where
only the top 3 candidate moves are considered. For small boards, the
non-exhaustive search produces the correct answer, but for 3x11 a win
was predicted for player 2, and also for 4x8 double-hip a win was
predicted for player 2.
Player 2 seems to have the advantage on larger games. A strange game.
The only way to win is not to play… first.