Gomoku

Gomoku, also called Five in a Row, is an abstract strategy board game. It is traditionally played with Go pieces (black and white stones) on a Go board. It can be played using the 15×15 board[1] or the 19×19 board.[2] Because pieces are typically not moved or removed from the board, gomoku may also be played as a paper-and-pencil game. The game is known in several countries under different names.

Gomoku
Genre(s)Board game
Abstract strategy game
Players2
Setup timeMinimal
Random chanceNone
Age range4+
Skill(s) requiredStrategy, tactics

Origin

Gomoku has existed in Japan since the Meiji Restoration.[3] The name "gomoku" is from the Japanese language, in which it is referred to as gomokunarabe (五目並べ). Go means five, moku is a counter word for pieces and narabe means line-up. The game is also popular in Korea, where it is called omok (오목 [五目]) which has the same structure and origin as the Japanese name.

In the nineteenth century, the game was introduced to Britain where it was known as Go Bang, said to be a corruption of the Japanese word goban, which was itself adapted from the Chinese k'i pan (qí pán) "go-board."[4]

Official rules

Players alternate turns placing a stone of their color on an empty intersection. Black plays first. The winner is the first player to form an unbroken chain of five stones horizontally, vertically, or diagonally. Placing so that a line of more than five stones of the same color is created does not result in a win. These are called overlines.

Because gomoku has a strong advantage for the first player when unrestricted,[5][6] the Swap2 rule is currently adapted in tournaments among professional players, including gomoku World Championships.[7]

In Swap2 rule, the first player starts by placing three stones, 2 black and 1 white, on the board. The second player then selects one of three options: play as black, play as white and place another white stone, or place two more stones, one white and one black, and let the first player choose the color.[8][9] This is essentially a more elaborate pie rule.

Swap2 solves the first-move advantage problem.[5][6]

Variations

Most variations are based on either Free-style gomoku or Standard gomoku.

  • Free-style gomoku requires a row of five or more stones for a win.
  • Standard gomoku requires a row of exactly five stones for a win: rows of six or more, called overlines, do not count.

Optional ("house") rules

Black (the player who makes the first move) 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.

  • 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).
  • Alternatively, a handicap may be given such that after the first "three and three" play has been made, the opposing player may place two stones as their next turn. These stones must block an opponent's row of three.
  • Efforts to improve fairness by reducing first-move advantage include the rule of swap, generalizable as "swap-(x,y,z)" and characterizable as a partially compounded and partially iterated version of the pie rule ("one person slices; the other chooses"): One player "A" places on the board x stones of the first-moving color and a lesser number y stones of the second-moving color ("slicing" in the pie metaphor); the other player "B" is entitled to choose between a) playing from the starting position, in which case player "B" is also entitled to choose which color to play, and b) placing z (usually [(x - y) + 1]) more stones on the board at locations of that player's choice ("reslicing" in the pie metaphor, with limitations created by the board's existing setup akin to limitations arising from the existing slices in the pie), in which case player "A" is entitled to choose which color side to play on.

Specific variations
  • Renju is played on a 15×15 board, with the rules of three and three, four and four, and overlines applied to Black only and with opening rules, some of which are following the swap pattern.
  • In Caro (also called gomoku+, popular among Vietnamese), the winner must have an overline or an unbroken row of five stones that must not be blocked at both ends (overlines are immune to this rule). This makes gomoku more balanced and provides more power for White to defend.
  • Omok is played the same as Standard gomoku; however, it is played on a 19×19 board and include the rule of three and three. The overlines rules, do not count.
  • Ninuki-renju or Wu is a variant which adds capturing to the game; it was published in the US in a modified version under the name Pente.

Theoretical generalizations
  • m,n,k-games are a generalization of gomoku to a board with m×n intersections, and k in a row needed to win.
  • Connect(m,n,k,p,q) games are another generalization of gomoku to a board with m×n intersections, k in a row needed to win, p stones for each player to place, and q stones for the first player to place for the first move only. Each player may play only at the lowest unoccupied place in a column. In particular, Connect(m,n,6,2,1) is called Connect6.

Example game
First game

This game on the 15×15 board is adapted from the paper "Go-Moku and Threat-Space Search".[10]

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 defense by white, starting with move 21.

Second game (continuation from first game)

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. Such long forcing sequences are typical in gomoku, and expert players can read out forcing sequences of 20 to 40 moves rapidly and accurately.

Other second game

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.

World championships

World Championships in gomoku have occurred 2 times in 1989, 1991.[11] Since 2009 tournament play has resumed, with the opening rule changed to swap2.[7]

List of the tournaments occurred and title holders follows.

World Championship
Title year Hosting city, country Gold Silver Bronze Opening rule
1989 Kyoto, Japan Sergey Chernov Yuriy Tarannikov Hirouji Sakamoto Pro
1991 Moscow, Soviet Union Yuriy Tarannikov Ando Meritee Sergey Chernov Pro
2009 Pardubice, Czech Republic Artur Tamioła Attila Demján Pavel Laube Swap2
2011 Huskvarna, Sweden Attila Demján Artur Tamioła Michał Żukowski Swap2
2013 Tallinn, Estonia Attila Demján Pavel Laube Mikhail Kozhin Swap2
2015 Suzdal, Russia Rudolf Dupszki Gergő Tóth Mikhail Kozhin Swap2
2017 Prague, Czech Republic Zoltán László Rudolf Dupszki Denis Osipov Swap2
2019 Tallinn, Estonia Martin Muzika Oleg Bulatowsky Michał Żukowski Swap2
Team World Championship
Title year Hosting city, country Gold Silver Bronze Opening rule
2016 Tallinn, Estonia  Poland
Michał Żukowski
Michał Zajk
Łukasz Majksner
Piotr Małowiejski		  Czech Republic
Pavel Laube
Igor Eged
Štěpán Tesařík
Marek Hanzl		  Chinese Taipei
Lu Wei-Yuan
Chen Ko-Han
Chang Yi-Feng
Sung Pei-Jung		 Swap2
2018 Płock, Poland  Russia-1
Edvard Rizvanov
Denis Osipov
Ilya Muratov
Maksim Karasev
Mikhail Kozhin		  Hungary
Zoltán László
Gergő Tóth
Márk Horváth
Gábor Gyenes
Attila Hegedűs		  Poland
Łukasz Majksner
Michał Żukowski
Michał Zajk
Marek Gorzecki
Paweł Tarasiński		 Swap2
2020
Cancelled due to the COVID-19 pandemic

Computers and Gomoku

Researchers have been applying artificial intelligence techniques on playing gomoku for several decades. In 1994, L. Victor Allis raised the algorithm of proof-number search (pn-search) and dependency-based search (db-search), and proved that when starting from an empty 15×15 board, the first player has a winning strategy using these searching algorithms.[12] This applies to both free-style gomoku and standard gomoku without any opening rules. It seems very likely that black wins on larger boards too. In any size of a board, freestyle gomoku is an m,n,k-game, hence it is known that the first player can force a win or a draw. In 2001, Allis' winning strategy was also approved for renju, a variation of gomoku, when there was no limitation on the opening stage.[13]

However, neither the theoretical values of all legal positions, nor the opening rules such as Swap2 used by the professional gomoku players have been solved yet, so the topic of gomoku artificial intelligence is still a challenge for computer scientists, such as the problem on how to improve the gomoku algorithms to make them more strategic and competitive. Nowadays, most of the state-of-the-art gomoku algorithms are based on the alpha-beta pruning framework.

Reisch proved that Generalized gomoku is PSPACE-complete.[14] He also observed that the reduction can be adapted to the rules of k-in-a-Row for fixed k. Although he did not specify exactly which values of k are allowed, the reduction would appear to generalize to any k ≥ 5.[15]

There exist several well-known tournaments for gomoku programs since 1989. The Computer Olympiad started with the gomoku game in 1989, but gomoku has not been in the list since 1993.[16] The Renju World Computer Championship was started in 1991, and held for 4 times until 2004.[17][18] The Gomocup tournament is played since 2000 and taking place every year, still active now, with more than 30 participants from about 10 countries.[19] The Hungarian Computer Go-Moku Tournament was also played twice in 2005.[20][21] There were also two Computer vs. Human tournaments played in the Czech Republic, in 2006 and 2011.[22][23] Not until 2017 were the computer programs proved to be able to outperform the world human champion in public competitions. In the gomoku World Championship 2017, there was a match between the world champion program Yixin and the world champion human player Rudolf Dupszki. Yixin won the match with a score of 2–0.[24][25]

See also

References
  1. "Gomoku - Japanese Board Game". Japan 101. Archived from the original on 2014-03-26. Retrieved 2013-06-25.
  2. Lasker, Edward (1960). Go and go-moku: the oriental board games (2nd rev. ed.). New York: Dover.
  3. Huang Zunxian, Chen Zheng (2005). 《黄遵宪全集》第2卷 (in Chinese). China: Zhonghua Book Company. ISBN 9787101044904.
  4. OED citations: 1886 GUILLEMARD Cruise ‘Marchesa’ I. 267 Some of the games are purely Japanese..as go-ban. Note, This game is the one lately introduced into England under the misspelt name of Go Bang. 1888 Pall Mall Gazette 1. Nov. 3/1 These young persons...played go-bang and cat's cradle. The board below shows the three types of winning arrangements as they might appear on an 8x8 Petteia board. Obviously the cramped conditions would result in a draw most of the time, depending on the rules. Play would be easier on a larger Latrunculi board of 12x8 or even 10x11. .
  5. "BoardGameGeek". boardgamegeek.com. Retrieved 2021-01-26.
  6. "Game database | GomokuWorld.com". gomokuworld.com. Retrieved 2021-01-26.
  7. "History | GomokuWorld.com". gomokuworld.com. Retrieved 2021-01-26.
  8. "Gomoku - swap2 rule". renju.net. Retrieved 2016-11-09.
  9. "Opening rules | GomokuWorld.com". gomokuworld.com. Retrieved 2021-01-26.
  10. Allis, L. V., Herik, H. J., & Huntjens, M. P. H. (1993). Go-moku and threat-space search. University of Limburg, Department of Computer Science.
  11. "The Renju International Federation portal - RenjuNet". Renju.net. Retrieved 2012-10-03.
  12. L. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. thesis, University of Limburg, The Netherlands. pp. 121–154. CiteSeerX 10.1.1.99.5364. ISBN 90-900748-8-0.
  13. J. Wágner and I. Virág (Mar 2001). "Solving Renju". ICGA Journal. 24 (1): 30–35. doi:10.3233/ICG-2001-24104. S2CID 207577292.
  14. Stefan Reisch (1980). "Gobang ist PSPACE-vollständig (Gomoku is PSPACE-complete)". Acta Informatica. 13: 59–66. doi:10.1007/bf00288536. S2CID 21455572.
  15. Demaine, Erik; Hearn, Robert (2001). "Playing Games with Algorithms: Algorithmic Combinatorial Game Theory". arXiv:cs/0106019v2.
  16. "Go-Moku (ICGA Tournaments)". game-ai-forum.org. Retrieved 2016-06-02.
  17. "Renju Computer World Championship". 5stone.net. Retrieved 2016-06-02.
  18. "4-th World Championship among Computer programs". Nosovsky Japanese Games Home Page. Retrieved 2016-06-03.
  19. "Gomocup - The Gomoku AI Tournament". Gomocup. Archived from the original on 2016-06-04. Retrieved 2016-06-02.
  20. "Hungarian Computer Gomoku Tournament 2005 | GomokuWorld.com". gomokuworld.com. Retrieved 2016-06-02.
  21. "2nd Hungarian Computer Go-Moku Open Tournament". sze.hu. Retrieved 2016-06-03.
  22. "The 1st tournament AI vs. Human (November the 11th, 2006) | Gomocup". gomocup.org. Retrieved 2016-06-02.
  23. "AI vs. Člověk 2011 | Česká federace piškvorek a renju". piskvorky.cz. Retrieved 2016-06-02.
  24. "Rudolf Dupszki versus Yixin". AIEXP.
  25. "Rudolf Dupszki vs. Yixin 2017". Facebook.

Further reading
  • Five-in-a-Row (Renju) For Beginners to Advanced Players ISBN 4-87187-301-3
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.