Mijnlieff solution: a win for the second player

Andy Hopwood’s board game Mijnlieff can be thought of as an advanced variant of noughts-and-crosses (also known as tic-tac-toe). The game is played by placing tiles on a four-by-four board of sixteen squares, with the aim of creating more lines of three tiles than the other player (with a line of four counting as two lines of three).

Each player begins with a hand of eight tiles: two Pullers, two Pushers, two Straights, and two Diagonals. The first player can play any of these tiles on one of the twelve squares around the edge of the board. Each type of tile places restrictions on where the other player can place their next tile:

• After playing a Puller, the other player must place a tile on one of the eight neighbouring squares
• After playing a Pusher, the other player must place a tile on a square other than one of the eight neighbouring squares
• After playing a Straight, the other player must place a tile on a square in the same row or column
• After playing a Diagonal, the other player must place a tile on a square in the same diagonal

Tiles can only be placed on empty squares, and if a player is unable to place a tile then they must pass, with the other player then allowed to place a tile in any empty square. The game ends when a player has no tiles left at the start of their turn, at which point the player with the most lines of three tiles wins.

Solution

Mijnlieff is a win for the second player with perfect play.

Mijnlieff has few enough possible games that it can be solved in around a minute on modern computer hardware using an optimised minimax algorithm analysing just over a billion games. My mijnlieff-solver GitHub repository contains a program that does this.

Intuitions about the best strategy can be confirmed by modifying the program to test particular positions. For example, seven of the eight possible first moves allow the second player to place a tile in one of the central squares. For these first moves, a winning response is to place a Pusher in a central square, forcing the first player to place a tile on the edge of the board again. For the remaining first move (placing a Straight in a corner), a winning response is to place a Straight in another corner. Players can continue placing Straights in corners until all corners are occupied, after which the first player’s next move allows the second player to place a tile in one of the central squares.