HIP 

Copyright (c) 1960 Martin Gardner

The game is played on a NxN square. The board starts empty

  • MOVE - Each player drops a stone into an empty cell, which does not form a square with 3 other placed stones of the same color.
    • Squares are not just formed by orthogonal lines, they can make any slope with the board edge.
  • GOAL - Wins the player that moved the last stone.
 
An example

White cannot play at [1] 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 posterity:

[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.

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:

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 (standard hip):

Columns are board size, winner (or 0 for draw), number of minMax() calls

Double hip:

Player 2 seems to have the advantage on larger games. A strange game. The only way to win is not to play… first.