Black Path Game

Last updated

The Black Path Game (also known by various other names, such as Brick) is a two-player board game described and analysed in Winning Ways for your Mathematical Plays . It was invented by Larry Black in 1960. [1]

Contents

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" (possibly known as "Larry") 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 (perhaps unimaginatively) called Black. The game was introduced to the public by Martin Gardner in his October 1963 "Mathematical Games column" in Scientific American . [2]

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

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

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

 ABCD 
1 DOMINO TILE HORIZONTAL-00-00.svg DOMINO TILE HORIZONTAL-00-00.svg 1
2 DOMINO TILE VERTICAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg 2
33
4 DOMINO TILE HORIZONTAL-00-00.svg DOMINO TILE HORIZONTAL-00-00.svg 4
 ABCD 

The first player has a winning strategy on any rectangular board with at least one side-length even so there are an even number of squares in total. Imagine the board covered with rectangular (2×1 unit-size) 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, [2] who subsequently described it in his book. [1]

 ABCDE 
1 DOMINO TILE HORIZONTAL-00-00.svg DOMINO TILE HORIZONTAL-00-00.svg 1
2 DOMINO TILE VERTICAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg 2
33
4 DOMINO TILE HORIZONTAL-00-00.svg DOMINO TILE HORIZONTAL-00-00.svg DOMINO TILE VERTICAL-00-00.svg 4
5 DOMINO TILE HORIZONTAL-00-00.svg DOMINO TILE HORIZONTAL-00-00.svg 5
 ABCDE 

If both sides of the board are odd, the second player can instead win by using a similar domino tiling strategy, including every square but the one containing the first player's first move. [1]

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. [2] Player 2 can win on an even-celled board; 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 [B2], the second cell of the main diagonal, regardless of Player 1's move in [B2], the unused path in [B2] 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 (save the lower-right corner) can be covered in dominoes. [2]

Refer to the three examples below, illustrating the "split domino" that results from the third move.

3: [B2]-T1, path to [B1]
 ABCD 
1 Square (20) 13-24.svg  1
2 Square (02) 14-23.svg Square (02) 12-34.svg S2
3S3
44
 ABCD 
3: [B2]-T2, path to [B3]
 ABCD 
1 Square (20) 13-24.svg S 1
2 Square (02) 14-23.svg Square (02) 14-23.svg S2
33
44
 ABCD 
3: [B2]-T3, path to [C2]
 ABCD 
1 Square (20) 13-24.svg S  1
2 Square (02) 14-23.svg Square (20) 13-24.svg 2
3S3
44
 ABCD 

Examples

 ABCD 
1 Square (02) 14-23.svg Square (02) 14-23.svg  1
2 Square (02) 12-34.svg Square (20) 13-24.svg Square (02) 14-23.svg 2
3 Square (02) 14-23.svg Square (02) 14-23.svg Square (02) 12-34.svg 3
4 4
 ABCD 

Consider the example game shown at right on a 4×4 grid, where the moves have been:

  1. [A1]-T2
  2. [B1]-T2
  3. [B2]-T3
  4. [B3]-T2
  5. [C3]-T1
  6. [C2]-T2
  7. [A2]-T1
  8. [A3]-T2

According to the rules, the next move by Player 1 (odd-numbered turns) must be in space [B4] to continue the path. If Player 1 makes the move [B4]-T3 Square (20) 13-24.svg that will result in an instant loss, since this tile will link the path to the bottom edge. Playing [B4]-T1 Square (02) 12-34.svg will result in a win, as Player 2's following move is placed in the corner [A4] and Player 3 will lose regardless of the piece played. Playing [B4]-T2 Square (02) 14-23.svg results in an eventual loss for Player 1; [1] comparison to the 4×4 domino-tiled blank board shows that Player 1 making the move [B4]-T1 puts the path into the middle of the domino, while [B4]-T2 puts the path onto the edge of the domino, and Player 2 can maneuver Player 1 into making the last move.

 ABCD 
1 Square (20) 13-24.svg Square (02) 12-34.svg Square (02) 14-23.svg 1
2 Square (02) 14-23.svg Square (20) 13-24.svg Square (02) 12-34.svg Square (02) 12-34.svg 2
3 Square (02) 14-23.svg Square (02) 12-34.svg 3
44
 ABCD 

Gardner describes a second example game, where the moves have been:

  1. [A1]-T3
  2. [A2]-T2
  3. [B2]-T3
  4. [C2]-T1
  5. [C1]-T2
  6. [B1]-T1
  7. [B3]-T2
  8. [C3]-T1
  9. [D2]-T1

In this second example, Player 1 has maneuvered the path into the corner space [D1], which results in a win regardless of the move made by Player 2. [2] After the third move (by Player 2) in [B2]-T3, the split domino exists in cells [B1] and [B3]. However, the fifth move by Player 2 [C1]-T2 brought the path to the edge of the split domino, which Player 1 took advantage of with the sixth move [B1]-T1, playing to the middle of the split domino.

See also

Related Research Articles

<span class="mw-page-title-main">Dominoes</span> Chinese and European game played with rectangular tiles

Dominoes is a family of tile-based games played with gaming pieces, commonly known as dominoes. Each domino is a rectangular tile, usually with a line dividing its face into two square ends. Each end is marked with a number of spots or is blank. The backs of the tiles in a set are indistinguishable, either blank or having some common design. The gaming pieces make up a domino set, sometimes called a deck or pack. The traditional European domino set consists of 28 tiles, also known as pieces, bones, rocks, stones, men, cards or just dominoes, featuring all combinations of spot counts between zero and six. A domino set is a generic gaming device, similar to playing cards or dice, in that a variety of games can be played with a set. Another form of entertainment using domino pieces is the practice of domino toppling.

<span class="mw-page-title-main">Pentomino</span> Geometric shape formed from five squares

Derived from the Greek word for '5', and "domino", a pentomino is a polyomino of order 5, that is, a polygon in the plane made of 5 equal-sized squares connected edge-to-edge. When rotations and reflections are not considered to be distinct shapes, there are 12 different free pentominoes. When reflections are considered distinct, there are 18 one-sided pentominoes. When rotations are also considered distinct, there are 63 fixed pentominoes.

In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first. The game is played until a terminal position is reached. A terminal position is one from which no moves are possible. Then one of the players is declared the winner and the other the loser. Furthermore, impartial games are played with perfect information and no chance moves, meaning all information about the game and operations for both players are visible to both players.

Pips are small but easily countable items, such as the dots on dominoes and dice, or the symbols on a playing card that denote its suit and value.

<span class="mw-page-title-main">Combinatorial game theory</span> Branch of game theory about two-player sequential games with perfect information

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

<span class="mw-page-title-main">Shut the box</span> Game of dice

Shut the box is a game of dice for one or more players, commonly played in a group of two to four for stakes. Traditionally, a counting box is used with tiles numbered 1 to 9 where each can be covered with a hinged or sliding mechanism, though the game can be played with only a pair of dice, pen, and paper. Variations exist where the box has 10 or 12 tiles. In 2018 the game had a renaissance in Liverpool, England, when it became the house game at Hobo Kiosk pub on the Baltic Triangle. It was popularized by DJ duo Coffee and Turntables and became the most played board game in Merseyside for 4 years in a row.

<span class="mw-page-title-main">Trax (game)</span>

Trax is a two-player abstract strategy game of loops and lines invented by David Smith in 1980.

<span class="mw-page-title-main">Domineering</span>

Domineering is a mathematical game that can be played on any collection of squares on a sheet of graph paper. For example, it can be played on a 6×6 square, a rectangle, an entirely irregular polyomino, or a combination of any number of such components. Two players have a collection of dominoes which they place on the grid in turn, covering up squares. One player places tiles vertically, while the other places them horizontally. As in most games in combinatorial game theory, the first player who cannot move loses.

<span class="mw-page-title-main">Rivers, Roads & Rails</span>

Rivers, Roads & Rails is a matching game similar to dominoes, but with 140 square tiles and in some respects similar to Bendomino. The game consists of square card pieces featuring different coloured tracks. The game was created by Ken Garland and Associates and first published in 1969 under the name Connect. Since 1982 it has been produced by Ravensburger, first in an abstract form, and since 1984 under the current theme with artwork by Josef Loeflath.

<span class="mw-page-title-main">Tsuro</span>

Tsuro is a tile-based board game designed by Tom McMurchie, originally published by WizKids and now published by Calliope Games.

<span class="mw-page-title-main">Muggins</span> Domino game

Muggins, sometimes also called All Fives, is a domino game played with any of the commonly available sets. Although suitable for up to four players, Muggins is described by John McLeod as "a good, quick two player game".

<span class="mw-page-title-main">Mutilated chessboard problem</span> On domino tiling after removing two corners

The mutilated chessboard problem is a tiling puzzle posed by Max Black in 1946 that asks:

Suppose a standard 8×8 chessboard has two diagonally opposite corners removed, leaving 62 squares. Is it possible to place 31 dominoes of size 2×1 so as to cover all of these squares?

<span class="mw-page-title-main">Domino tiling</span> Geometric construct

In geometry, a domino tiling of a region in the Euclidean plane is a tessellation of the region by dominoes, shapes formed by the union of two unit squares meeting edge-to-edge. Equivalently, it is a perfect matching in the grid graph formed by placing a vertex at the center of each square of the region and connecting two vertices when they correspond to adjacent squares.

<span class="mw-page-title-main">Edge-matching puzzle</span>

An edge-matching puzzle is a type of tiling puzzle involving tiling an area with polygons whose edges are distinguished with colours or patterns, in such a way that the edges of adjacent tiles match.

A connection game is a type of abstract strategy game in which players attempt to complete a specific type of connection with their pieces. This could involve forming a path between two or more endpoints, completing a closed loop, or connecting all of one's pieces so they are adjacent to each other. Connection games typically have simple rules, but complex strategies. They have minimal components and may be played as board games, computer games, or even paper-and-pencil games.

<span class="mw-page-title-main">Cram (game)</span>

Cram is a mathematical game played on a sheet of graph paper. It is the impartial version of Domineering and the only difference in the rules is that each player may place their dominoes in either orientation, but it results in a very different game. It has been called by many names, including "plugg" by Geoffrey Mott-Smith, and "dots-and-pairs." Cram was popularized by Martin Gardner in Scientific American.

In information visualization and graphic design, Truchet tiles are square tiles decorated with patterns that are not rotationally symmetric. When placed in a square tiling of the plane, they can form varied patterns, and the orientation of each tile can be used to visualize information associated with the tile's position within the tiling.

Serpentiles is the name coined by Kurt N. Van Ness for the hexagonal tiles used in various edge-matching puzzle connection abstract strategy games, such as Psyche-Paths, Kaliko, and Tantrix. For each tile, one to three colors are used to draw paths linking the six sides together in various configurations. Each side is connected to another side by a specific path route and color. Gameplay generally proceeds so that players take turns laying down tiles. During each turn, a tile is laid adjacent to existing tiles so that colored paths are contiguous across tile edges.

<span class="mw-page-title-main">Glossary of domino terms</span> List of definitions of terms and jargon used in dominoes

The following is a glossary of terms used in dominoes. Besides the terms listed here, there are numerous regional or local slang terms. Terms in this glossary should not be game-specific, i.e. specific to one particular version of dominoes, but apply to a wide range of domino games. For glossaries that relate primarily to one game or family of similar games, see the relevant article.

References

  1. 1 2 3 4 5 Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1982), "The Black Path Game", Winning Ways for your Mathematical Plays, Vol. 2: Games in Particular, London: Academic Press Inc. [Harcourt Brace Jovanovich Publishers], pp. 682–683, MR   0654502 .
  2. 1 2 3 4 5 6 Gardner, Martin (1983). "5: Four Unusual Board Games". Sixth Book of Mathematical Diversions from 'Scientific American' . Chicago: University of Chicago Press. pp. 39–47. ISBN   0226282503.
  3. Browne, Cameron (2008), "Truchet curves and surfaces", Computers & Graphics, 32 (2): 268–281, doi:10.1016/j.cag.2007.10.001, Truchet-style tiles are used as the basis for several strategy games including Trax, Meander and the Black Path Game, all of which predate Smith's seminal 1987 article that associates such tiles with the work of Sébastien Truchet.