| Gomoku, go-moku, or gobang (Japanese:
五目並べ, Gomoku Narabe, "five points") is a board game
traditionally played with go pieces (black and white stones) on a
go board (19x19 intersections). Black plays first, and players alternate in placing a stone of their color on an empty
intersection. The winner is the first player to get an unbroken row of five stones horizontally, vertically, or diagonally.
Gomoku is known in Korean by its cognate omok
(오목).
Example game
This game on the 15×15 board is adapted from the paper "Go-Moku and Threat-Space Search".
The opening moves show clearly black's advantage. An open row of three (one that is not blocked by an opponent's stone at
either end) has to be blocked immediately, or countered with a threat elsewhere on the board. If not blocked or countered, the
open row of three will be extended to an open row of four, which threatens to win in two ways. White has to block open rows of
three at moves 10, 14, 16 and 20, but black only has to do so at move 9.
Move 20 is a blunder for white (it should have been played next to black 19). Black can now force a win against any defence by
white, starting with move 21.
There are two forcing sequences for black, depending on whether white 22 is played next to black 15 or black 21. The diagram
on the right shows the first sequence. All the moves for white are forced (except for 38, but by then it is too late). Such long
forcing sequences are typical in gomoku, and expert players can read out forcing sequences of 20 to 40 moves rapidly and
accurately.
The diagram on the right shows the second forcing sequence. This diagram shows why white 20 was a blunder; if it had been next
to black 19 (at the position of move 32 in this diagram) then black 31 would not be a threat and so the forcing sequence would
fail.
Variations
Black was long known to have a big advantage, even before L. Victor
Allis proved that black could force a win (see below). So a number of variations are played with extra rules that aimed to
reduce black's advantage.
- Free-style gomoku is the basic game as described above.
- Standard gomoku requires a row of exactly five stones for a win: rows of six or more, called overlines, do not
count.
- The rule of three and three bans a move that simultaneously forms two open rows of three stones (rows not blocked by
an opponent's stone at either end).
- The rule of four and four bans a move that simultaneously forms two rows of four stones (open or not).
These restrictions are often applied only to black.
- Renju is played on a 15×15 board, with the rules of three and three, four and
four, and overlines applied to black only. There are special rules for the opening.
- Ninuki-renju is a variant which adds capturing to the game; it was published in the USA in a slightly simplified form
under the name Pente.
- m,n,k-games are a generalization of gomoku to a board with m×n intersections, and k in a row
needed to win.
Analysis
Computer search by L. Victor Allis has shown that on a 15x15
board, black wins with perfect play. This applies whether or not overlines
are considered as wins, but it assumes that the rule of three and three is not used. It seems very likely that black wins on
larger boards too.
Generalized gomoku is PSPACE-complete.
External links
References
- L. Victor Allis, Searching for Solutions in Games and Artificial
Intelligence, Ph.D. thesis, University of Limburg, The Netherlands, 1994 (ISBN 90-9007488-0) [1] (http://www.cs.unimaas.nl/~uiterwijk/AllisPhD.htm).
- L. Victor Allis, H. J. van den Herik, M. P. H. Huntjens, Go-Moku
and Threat-Space Search [2] (http://www.renju.nu/proof/Go-Moku.pdf).
- Stefan Reisch, Gobang ist PSPACE-vollstandig (Gomoku is PSPACE-complete). Acta Informatica, 13:5966, 1980.
|
