Black Path Game


The Black Path Game is a two-player board game described and analysed in Winning Ways for your Mathematical Plays. It was invented by Larry Black in 1960.
It has also been reported that a game known as "Black" or "Black's Game" was invented in 1960 by William L. Black. This "William L. Black" was at that time an undergraduate at the Massachusetts Institute of Technology, investigating Hex and Bridg-It, two games based on the challenge to create a connected "chain" of counters that link opposite sides of a game board. The creative outcome of Black's research was a new topological game that his friends called Black. The game was introduced to the public by Martin Gardner in his October 1963 "Mathematical Games column" in Scientific American.

Rules

The Black Path Game is played on a board ruled into squares. One edge on the boundary of the board is designated to be the start of the path. After the first move, the players extend the path away from the starting edge by alternately filling the adjacent square at the end of the current path with one of three configurations shown below.
Any square that is not empty is filled with one of the following configurations that contains two paths linking two sides:
These tiles are the three ways to join the sides of the square in pairs. The first two are
the tiles of the Truchet tiling.
The path may return to a previously filled square and follow the yet-unused segment on that square. The player who first causes the path to run back into the edge of the board loses the game.

Strategy

As outlined in the example games provided, the player who routes the path into a corner of the board will win the game, as the other player will have no choice but to run the path into the edge of the board.
For a rectangular board with an even number of squares, the first player has a winning strategy. This occurs when at least one side-length is even. Imagine the board covered with rectangular dominoes. If the first player always plays so the end of the path falls on the middle of one of the dominoes, that player will win. This strategy was discovered by Black's friend Elwyn R. Berlekamp, who subsequently described it in his book.




For a rectangular board with an odd total number of squares, i.e., when both sides of the board are odd, the second player can instead win by using a similar domino tiling strategy occupying every square except the one containing the first player's first move.

Logic

The domino tiling strategy works by making the losing player end the path on the edge of a new domino; by continuing the path on the new domino, the winning player will eventually force the losing player to the edge or a corner.
The second player can win on a board with an even number of square cells; first consider the board completely covered with 2×1 dominoes except for the upper left and lower right corners. If Player 2 forces Player 1 to move in, the second cell of the main diagonal, regardless of Player 1's move in, the unused path in will connect two squares which can be regarded as the two squares of a "split domino" that Player 2 can use, and the remaining tiles can be covered in dominoes.
Refer to the three examples below, illustrating the "split domino" that results from the third move:
  1. -T3
  2. -T2






Examples

Consider the example game shown at right on a 4×4 grid, where the moves have been:
  1. -T2
  2. -T2
  3. -T3
  4. -T2
  5. -T1
  6. -T2
  7. -T1
  8. -T2
According to the rules, the next move by Player 1 must be in space to continue the path. If Player 1 makes the move -T3 that will result in an instant loss, since this tile will link the path to the bottom edge. Playing -T1 will result in a win, as Player 2's following move is placed in the corner and Player 3 will lose regardless of the piece played. Playing -T2 results in an eventual loss for Player 1; comparison to the 4×4 domino-tiled blank board shows that Player 1 making the move -T1 puts the path into the middle of the domino, while -T2 puts the path onto the edge of the domino, and Player 2 can maneuver Player 1 into making the last move.
ABCD
11
22
33
44
ABCD

Gardner describes a second example game, where the moves have been:
  1. -T3
  2. -T2
  3. -T3
  4. -T1
  5. -T2
  6. -T1
  7. -T2
  8. -T1
  9. -T1
In this second example, Player 1 has maneuvered the path into the corner space, which results in a win regardless of the move made by Player 2. After the third move in -T3, the split domino exists in cells and . However, the fifth move by Player 2 -T2 brought the path to the edge of the split domino, which Player 1 took advantage of with the sixth move -T1, playing to the middle of the split domino.