View source for Gomoku

{{Short description|Abstract strategy board game}}
{{Italic title|reason=[[:Category:Japanese words and phrases]]}}
{{redirect|Omok|the language|Omok language}}
{{Infobox game
| italic title = no
| title         = ''Gomoku''
|image=| image_link    = [[File:Renju.jpg|200px]]
| image_caption = 
| years         = 
| genre         = [[Board game]] <br />[[Abstract strategy game]]
| players       = 2
| setup_time    = Minimal
| playing_time  = 
| random_chance = None
| skills        = [[Strategy game|Strategy]], tactics
| footnotes     = 
}}
'''''Gomoku''''', also called ''five in a row'', is an [[Abstract strategy game|abstract strategy]] [[board game]]. It is traditionally played with [[Go (game)|Go]] pieces (black and white stones) on a 15×15 Go board<ref>{{cite web|url=http://www.japan-101.com/culture/gomoku_japanese_board_game.htm |title=Gomoku - Japanese Board Game |publisher=Japan 101 |access-date=2013-06-25 |url-status=dead |archive-url=https://web.archive.org/web/20140326000833/http://www.japan-101.com/culture/gomoku_japanese_board_game.htm |archive-date=2014-03-26 }}</ref><ref>{{Cite web|title=Game Theory {{!}} GomokuWorld.com|url=http://gomokuworld.com/gomoku/1|access-date=2021-07-28|website=gomokuworld.com|archive-date=2021-07-22|archive-url=https://web.archive.org/web/20210722163855/http://gomokuworld.com/gomoku/1|url-status=dead}}</ref> while in the past a 19×19 board was standard.<ref>{{cite book|title=Go and go-moku: the oriental board games|url=https://archive.org/details/gogomokuoriental00lask|url-access=registration|last=Lasker|first=Edward|publisher=Dover|year=1960|isbn=9780486206134|edition=2nd rev.|place=New York}}</ref><ref>"The rules and the history of Renju and other five-in-a-row games." ''Luffarschack'', [https://renju.se/rif/r1rulhis.htm renju.se/rif/r1rulhis.htm]. Accessed 28 July 2021.</ref> 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. 

==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 line of five stones of their color horizontally, vertically, or diagonally. In some rules, this line must be exactly five stones long; six or more stones in a row does not count as a win and is called an overline.<ref>{{Cite web|title=Game Theory {{!}} GomokuWorld.com|url=http://gomokuworld.com/gomoku/1|url-status=live|archive-url=https://web.archive.org/web/20210722163855/http://gomokuworld.com/gomoku/1|archive-date=2021-07-22|access-date=2021-07-22|website=gomokuworld.com}}</ref><ref name=":6">{{Cite web|title=The Renju International Federation portal - RenjuNet|url=https://www.renju.net/rules/|url-status=live|archive-url=https://web.archive.org/web/20230210083330/https://www.renju.net/rules/|archive-date=2023-02-10|access-date=2023-02-10|website=www.renju.net}}</ref> If the board is completely filled and no one has made a line of 5 stones, then the game ends in a draw.

==Origin==
Historical records indicate that the origins of gomoku can be traced back to the mid-1700s during the Edo period. It is said that the 10th generation of Kuwanaya Buemon, a merchant who frequented the Nijō family, was highly skilled in this game, which subsequently spread among the people. By the late Edo period, around 1850, books had been published on gomoku.<ref>{{Cite web |date=2022-09-19 |title=About the origin and rules of renju |url=https://renjusha.net/about-renju/%e6%ad%b4%e5%8f%b2/ |archive-url=https://web.archive.org/web/20230403070608/https://renjusha.net/about-renju/%E6%AD%B4%E5%8F%B2/ |archive-date=2023-04-03 |access-date=2023-04-26 |website=Nihon Renju-sha |language=ja}}</ref> The earliest published book on gomoku that can be verified is the {{nihongo|''Gomoku Jōseki Collection''|五石定磧集}} in 1856.<ref>{{Cite web |date=1999-10-01 |title=Origins of renju |url=http://www.success-simulation.com/renju/roots.html |archive-url=https://web.archive.org/web/20220331100438/http://www.success-simulation.com/renju/roots.html |archive-date=2022-03-31 |access-date=2023-04-26 |website=www.success-simulation.com}}</ref>

The name "gomoku" is from the [[Japanese language]], in which it is referred to as {{nihongo|''gomokunarabe''|五目並べ}}. ''Go'' means [[5|five]], ''moku'' is a [[Japanese counter word|counter word]] for [[Go stone|piece]]s and ''narabe'' means ''line-up''. The game is popular in [[China]], where it is called ''Wuziqi'' (五子棋).<ref>{{Cite web|title=The Renju International Federation portal - RenjuNet|url=https://www.renju.net/tournament/2316/|access-date=2023-04-30|website=www.renju.net}}</ref> ''Wu'' (五 wǔ) means ''five'', ''zi'' (子 zǐ) means ''piece'', and ''qi'' ([[:zh:棋|棋]] qí) refers to a board game category in Chinese. 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 ''[[Go board|goban]]'', which was itself adapted from the Chinese ''k'i pan (qí pán)'' "go-board."<ref>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.
.</ref>

== First-player advantage ==
Gomoku has a strong advantage for the first player when unrestricted.<ref name=":1">{{Cite web|title=BoardGameGeek|url=https://boardgamegeek.com/thread/969642/article/36840025#36840025|url-status=live|archive-url=https://web.archive.org/web/20210722164845if_/https://boardgamegeek.com/thread/969642/article/36840025|archive-date=2021-07-22|access-date=2021-01-26|website=boardgamegeek.com}}</ref><ref name=":2">{{Cite web|title=Game database {{!}} GomokuWorld.com|url=http://gomokuworld.com/gamedatabase|access-date=2021-01-26|website=gomokuworld.com}}</ref>

Championships in gomoku previously used the "[[#Pro|'''Pro''']]" opening rule, which mandated that the first player place the first stone in the center of the board. The second player's stone placement was unrestricted. The first player's second stone had to be placed at least three intersections away from the first player's first stone. This rule was used in the 1989 and 1991 world championships.<ref name=":5" /> When the win–loss ratio of these two championships was calculated, the first player (black) won 67 percent of games.

This was deemed too unbalanced for tournament play, so tournament gomoku adopted the [[#Swap2|Swap2]] opening protocol in 2009. In Swap2, the first player places three stones, two black and one 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.<ref name=":9">{{Cite web|title=Gomoku - swap2 rule|url=https://www.renju.net/rule/11/|access-date=2016-11-09|website=renju.net}}</ref><ref name=":4" />

The win ratio of the first player has been calculated to be around 52 percent using the Swap2 opening protocol, greatly balancing the game and largely evening out the first-player advantage.<ref name=":1" /><ref name=":2" /><ref name=":3">{{Cite web|title=History {{!}} GomokuWorld.com|url=http://gomokuworld.com/worldchampionship/6|url-status=live|archive-url=https://archive.today/20210707172514/http://gomokuworld.com/worldchampionship/6|archive-date=2021-07-07|access-date=2021-01-26|website=gomokuworld.com}}</ref>

==Variants==

=== Freestyle gomoku ===
Freestyle gomoku has no restrictions on either player and allows a player to win by creating a line of five or more stones, with each player alternating turns placing one stone at a time.

==== Swap after 1st move ====
The rule of "swap after 1st move" is a variant of the freestyle gomoku rule, and is mostly played in China.  The game can be played on a 19×19 or 15×15 board. As per the rule, once the first player places a black stone on the board, the second player has the right to swap colors. The rest of the game proceeds as freestyle gomoku. This rule is set to balance the advantage of black in a simple way.<ref>{{Cite web |title=Swap after 1st move rule |url=http://www.wuzi8.com/Article/HTML/3764.html |archive-url=https://web.archive.org/web/20211208090454/http://www.wuzi8.com/Article/HTML/3764.html |archive-date=2021-12-08 |access-date=2023-04-28 |website=www.wuzi8.com |language=zh}}</ref>

=== [[Renju]] ===
Black (the player who makes the first move) has long been known to have an advantage, even before [[L. Victor Allis]] proved that black can force a win (see below). Renju attempts to mitigate this imbalance with extra rules that aim to reduce black's first player advantage.

It is played on a 15×15 board, with the rules of three and three, four and four, and overlines applied to Black only.<ref name=":6" />
* 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).
*Overlines prevent a player from winning if they form a line of 6 or more stones.<ref name=":6" /><ref>{{Cite web |title=The Renju International Federation portal - RenjuNet |url=https://www.renju.net/advanced/ |access-date=2021-07-22 |website= |archive-url=https://web.archive.org/web/20210711201520/https://www.renju.net/study/advanced.php |archive-date=11 July 2021 |url-status=dead}}</ref>
Renju also makes use of various tournament opening rules, such as [[Soosõrv opening rule|Soosõrv-8]], the current international standard.<ref>{{Cite web|title=The Renju International Federation portal - RenjuNet|url=http://renju.net/ga2015/|url-status=live|archive-url=https://archive.today/20210722180937/http://renju.net/organizations/ga2015.php|archive-date=2021-07-22|access-date=2021-07-22|website=renju.net}}</ref>

=== Caro ===
In Caro, (also called gomoku+, popular among Vietnamese), the winner must have an overline or an unbroken row of five stones that is not blocked at either end (overlines are immune to this rule). This makes the game more balanced and provides more power for White to defend.<ref>{{Cite web|title=Caro (aka Gomoku)|url=https://learnplaywin.net/caro/|url-status=live|archive-url=https://web.archive.org/web/20210722180806/https://learnplaywin.net/caro/|archive-date=2021-07-22|access-date=2021-07-22|website=LearnPlayWin|language=en-US}}</ref>

=== Omok ===
Omok is similar to Freestyle gomoku; however, it is played on a 19×19 board and includes the rule of ''three and three.''<ref name=":8">{{Cite web|date=2016-10-06|title=Omok: A Korean Game of Five Stones.|url=https://kpopjacketlady.com/2016/10/06/omok-a-korean-game-of-five-stones/|url-status=live|archive-url=https://web.archive.org/web/20210722180238/https://kpopjacketlady.com/2016/10/06/omok-a-korean-game-of-five-stones/|archive-date=2021-07-22|access-date=2021-07-22|website=KPOP Jacket Lady|language=en}}</ref><ref name=":7">Sungjin, Nam. "Omok." ''Encyclopedia of Korean Folk Culture'', National Folk Museum of Korea, https://web.archive.org/web/20210722180119/https://folkency.nfm.go.kr/en/topic/detail/1587 . Accessed 22 July 2021.</ref>

=== Ninuki-renju ===
Also called Wu, Ninuki Renju is a variant which adds capturing to the game; A pair of stones of the same color may be captured by the opponent by means of custodial capture (sandwiching a line of two stones lengthwise). The winner is the player either to make a perfect five in a row, or to capture five pairs of the opponent's stones. It uses a 15x15 board and the rules of three and three and overlines. It also allows the game to continue after a player has formed a row of five stones if their opponent can capture a pair across the line.<ref>{{Cite web|title=Rules of Pente, Keryo-Pente and Ninuki|url=https://renju.nu/pente-rules/|url-status=live|archive-url=https://web.archive.org/web/20210722180425/https://renju.nu/pente-rules/|archive-date=2021-07-22|access-date=2021-07-22|website=Renju|language=en-US}}</ref>

=== [[Pente]] ===
Pente is related to Ninuki-Renju, and has the same custodial capture method, but is most often played on a 19x19 board and does not use the rules of three and three, four and four, or overlines.<ref>{{Cite web|title=Pente|url=https://www.mindsports.nl/index.php/the-pit/546-pente|url-status=live|archive-url=https://web.archive.org/web/20210701212828/https://www.mindsports.nl/index.php/the-pit/546-pente|archive-date=2021-07-01|access-date=2021-07-22|website=www.mindsports.nl}}</ref>[[File:Pro Gomoku.jpg|thumb|'''Pro''' Opening Rule: Black places first stone in the center of board. White can place anywhere, but places to the South-East. Black places their second stone three spaces away.]]

=== Tournament Opening Rules ===
Tournament rules are used in professional play to balance the game and mitigate the first player advantage. The tournament rule used for the gomoku world championships since 2009 is the Swap2 opening rule. For all of the following professional rules, an overline (six or more stones in a row) does not count as a win.<ref name=":3" />
[[File:Swap Rule Gomoku.jpg|left|thumb|'''Swap''' Opening Rule: Tentative Black places two black stones and one white stone anywhere on the board. Tentative white chooses which color to play as.]]

==== Pro ====
The first player's first stone must be placed in the center of the board. The second player's first stone may be placed anywhere on the board. The first player's second stone must be placed at least three intersections away from the first stone (two empty intersections in between the two stones).<ref name=":4">{{Cite web|title=Opening rules {{!}} GomokuWorld.com|url=http://gomokuworld.com/gomoku/2|url-status=live|archive-url=https://web.archive.org/web/20210722164403/http://gomokuworld.com/gomoku/2|archive-date=2021-07-22|access-date=2021-07-07|website=gomokuworld.com}}</ref>

==== Long Pro ====
The first player's first stone must be placed in the center of the board. The second player's first stone may be placed anywhere on the board. The first player's second stone must be placed at least four intersections away from the first stone (three empty intersections in between the two stones).<ref name=":4" /><ref>{{cite web | access-date=2021-07-28 | url=https://www.renju.net/rule/7/ | title=Gomoku – pro rule | website=www.renju.net}}</ref>
[[File:Swap2 Gomoku.jpg|thumb|'''Swap2''' Opening Rule: Tentative Black places two black stones and one white stone anywhere on the board. Tentative White responds by picking option number three and placing two more stones, one of each color, on the board and passes the choice of which color to play as to tentative Black.]]

==== Swap ====
The tentative first player places three stones (two black, and one white) anywhere on the board. The tentative second player then chooses which color to play as. Play proceeds from there as normal with white playing their second stone.<ref name=":4" />

==== Swap2 ====
The tentative first player places three stones on the board, two black and one white. The tentative second player then has three options:

# They can choose to play as white and place a second white stone
# They can swap their color and choose to play as black
# Or they can place two more stones, one black and one white, and pass the choice of which color to play back to the tentative first player.

Because the tentative first player doesn't know where the tentative second player will place the additional stones if they take option 3, the swap2 opening protocol limits excessive studying of a line by only one of the players.<ref name=":9" /><ref name=":4" />

== Theoretical generalizations ==
[[m,n,k-game|''m'',''n'',''k''-games]] are a [[generalized game|generalization]] of gomoku to a board with ''m''×''n'' intersections, and ''k'' in a row needed to win. [[Connect Four]] is (7,6,4) with piece placement restricted to the lowest unoccupied place in a column.

Connect(''m'',''n'',''k'',''p'',''q'') games are another [[generalized game|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. In particular, Connect(''m'',''n'',6,2,1) is called [[Connect6]].

==Example game==
[[File:Gomoku-game-1.svg|thumb|300px|right|First game]]
This game on the 15×15 board is adapted from the paper "Go-Moku and Threat-Space Search".<ref>Allis, L. V., Herik, H. J., & Huntjens, M. P. H. (1993). ''Go-moku and threat-space search''. University of Limburg, Department of Computer Science.</ref>

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.

[[File:Gomoku-game-3.svg|thumb|300px|right|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.

[[File:Gomoku-game-2.svg|thumb|300px|right|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 Gomoku Championships]] have occurred 2 times in 1989, 1991.<ref name=":5">{{cite web|title=The Renju International Federation portal - RenjuNet|url=https://www.renju.net/gwc/|url-status=live|archive-url=https://web.archive.org/web/20210722164635/http://www.renju.net/media/gwc.php|archive-date=2021-07-22|access-date=2012-10-03|publisher=Renju.net}}</ref>
Since 2009 tournament play has resumed, with the opening rule changed to swap2.<ref name=":3" />

List of the tournaments occurred and title holders follows.
{| class="wikitable"
|+ World Championship
|-
!Title year
!Hosting city, country
!Gold
!Silver
!Bronze
!Opening rule
|-
|1989
|{{flagdeco|Japan}} [[Kyoto]], [[Japan]]
|{{flagicon|Soviet Union}} [[:ru:Чернов, Сергей Станиславович|Sergey Chernov]]
|{{flagicon|Soviet Union}} [[:ru:Таранников, Юрий Валерьевич|Yuriy Tarannikov]]
|{{flagicon|Japan}} [[Hirouji Sakamoto]]
|Pro
|-
|1991
|{{flagdeco|Soviet Union}} [[Moscow]], [[Soviet Union]]
|{{flagicon|Soviet Union}} [[:ru:Таранников, Юрий Валерьевич|Yuriy Tarannikov]]
|{{flagicon|Soviet Union}} [[Ando Meritee]]
|{{flagicon|Soviet Union}} [[:ru:Чернов, Сергей Станиславович|Sergey Chernov]]
|Pro
|-
|2009
|{{flagdeco|Czech Republic}} [[Pardubice]], [[Czech Republic]]
|{{flagicon|Poland}} [[Artur Tamioła]]
|{{flagicon|Hungary}} [[Attila Demján]]
|{{flagicon|Czech Republic}} [[Pavel Laube]]
|Swap2
|-
|2011
|{{flagdeco|Sweden}} [[Huskvarna]], [[Sweden]]
|{{flagicon|Hungary}} [[Attila Demján]]
|{{flagicon|Poland}} [[Artur Tamioła]]
|{{flagicon|Poland}} [[Michał Żukowski]]
|Swap2
|-
|2013
|{{flagdeco|Estonia}} [[Tallinn]], [[Estonia]]
|{{flagicon|Hungary}} [[Attila Demján]]
|{{flagicon|Czech Republic}} [[Pavel Laube]]
|{{flagicon|Russia}} [[Mikhail Kozhin]]
|Swap2
|-
|2015
|{{flagdeco|Russia}} [[Suzdal]], [[Russia]]
|{{flagicon|Hungary}} [[Rudolf Dupszki]]
|{{flagicon|Hungary}} [[Gergő Tóth]]
|{{flagicon|Russia}} [[Mikhail Kozhin]]
|Swap2
|-
|2017
|{{flagdeco|Czech Republic}} [[Prague]], [[Czech Republic]]
|{{flagicon|Hungary}} [[Zoltán László]]
|{{flagicon|Hungary}} [[Rudolf Dupszki]]
|{{flagicon|Russia}} [[Denis Osipov (gomoku player)|Denis Osipov]]
|Swap2
|-
|2019
|{{flagdeco|Estonia}} [[Tallinn]], [[Estonia]]
|{{flagicon|Czech Republic}} [[Martin Muzika]]
|{{flagicon|Ukraine}} [[Oleg Bulatowsky]]
|{{flagicon|Poland}} [[Michał Żukowski]]
|Swap2
|-
|2023
|{{flagdeco|Hungary}} [[Budapest]], [[Hungary]]
|{{flagicon|Czech Republic}} [[Pavel Laube]]
|{{flagicon|Poland}} [[Adrian Fitzermann]]
|{{flagicon|Czech Republic}} [[Martin Muzika]]
|Swap2
|}
{| class="wikitable" <
|+ Team World Championship
|-
!Title year
!Hosting city, country
!Gold
!Silver
!Bronze
!Opening rule
|- style="vertical-align: top;"
|2016
|{{flagdeco|Estonia}} [[Tallinn]], [[Estonia]]
|{{flag|Poland}} <br /> Michał Żukowski <br /> Michał Zajk <br /> Łukasz Majksner <br /> Piotr Małowiejski
|{{flag|Czech Republic}} <br /> Pavel Laube <br /> Igor Eged <br /> Štěpán Tesařík <br /> Marek Hanzl
|{{flag|Chinese Taipei}} <br /> Lu Wei-Yuan <br /> Chen Ko-Han <br /> Chang Yi-Feng <br /> Sung Pei-Jung
|Swap2
|-
|2018
|{{flagdeco|Poland}} [[Płock]], [[Poland]]
|{{flag|Russia}}-1 <br /> Edvard Rizvanov <br /> Denis Osipov <br /> Ilya Muratov <br /> Maksim Karasev <br /> Mikhail Kozhin
|{{flag|Hungary}} <br /> Zoltán László <br />  Gergő Tóth <br />  Márk Horváth <br /> Gábor Gyenes <br />  Attila Hegedűs
|{{flag|Poland}} <br /> Łukasz Majksner <br /> Michał Żukowski <br /> Michał Zajk <br /> Marek Gorzecki <br /> Paweł Tarasiński
|Swap2
|-
|2020
| colspan="5" |
{|align="center"
|Cancelled due to the [[COVID-19 pandemic]]
|
|
|
|
|}
|}

== Computers and gomoku ==
Researchers have been applying [[artificial intelligence]] techniques to playing gomoku for several decades. [[Joseph Weizenbaum]] published a short paper in [[Datamation]] in 1962 entitled "How to Make a Computer Appear Intelligent"<ref>'' [https://ebiquity.umbc.edu/paper/html/id/1130/ How to Make a Computer Appear Intelligent]'', Datamation, February, 1962</ref> that described the strategy used in a gomoku program that could beat novice players. 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.<ref name=":0">{{cite book | author = L. Victor Allis | title = Searching for Solutions in Games and Artificial Intelligence | publisher = Ph.D. thesis, University of Limburg, The Netherlands | year = 1994 | isbn = 90-900748-8-0 | pages=121–154 | author-link = L. Victor Allis | citeseerx = 10.1.1.99.5364 }}</ref> 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|''m'',''n'',''k''-game]], hence it is known that the first player can force a win or a draw. In 2001, Allis's winning strategy was also approved for renju, a variation of gomoku, when there was no limitation on the opening stage.<ref>{{cite journal | author=J. Wágner and I. Virág | s2cid=207577292 | title=Solving Renju | journal=ICGA Journal | volume=24 | number=1 | pages=30–35 | date=Mar 2001 | doi=10.3233/ICG-2001-24104 }}</ref>

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. Most [[state-of-the-art]] gomoku algorithms are based on the [[alpha-beta pruning]] framework.{{Cn|date=December 2022}}

Reisch proved that [[Generalized game|Generalized]] gomoku is [[PSPACE-complete]].<ref>{{cite journal | author = Stefan Reisch | title = Gobang ist PSPACE-vollständig (Gomoku is PSPACE-complete) | journal = Acta Informatica | volume = 13 | pages = 59–66 | year = 1980 | doi=10.1007/bf00288536| s2cid = 21455572 }}</ref> 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.<ref>{{cite arXiv|last1=Demaine|first1=Erik|last2=Hearn|first2=Robert|author2-link=Bob Hearn|title=Playing Games with Algorithms: Algorithmic Combinatorial Game Theory|eprint=cs/0106019v2|year=2001}}</ref>

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.<ref>{{Cite web|url=http://www.game-ai-forum.org/icga-tournaments/game.php?id=30|title=Go-Moku (ICGA Tournaments)|website=game-ai-forum.org|access-date=2016-06-02}}</ref> The Renju World Computer Championship was started in 1991, and held for 4 times until 2004.<ref>{{Cite web|url=http://www.5stone.net/wc/worldcup_en.html|title=Renju Computer World Championship|website=5stone.net|access-date=2016-06-02}}</ref><ref>{{Cite web|url=http://nosovsky.narod.ru/forth.html|title=4-th World Championship among Computer programs|website=Nosovsky Japanese Games Home Page|access-date=2016-06-03}}</ref> The [[Gomocup]] tournament has been held annually since 2000, with more than thirty participants from about ten countries taking part.<ref>{{Cite web|url=http://gomocup.org/home/|title=Gomocup - The Gomoku AI Tournament|website=Gomocup|access-date=2016-06-02|url-status=dead|archive-url=https://web.archive.org/web/20160604205643/http://gomocup.org/home/|archive-date=2016-06-04}}</ref> The Hungarian Computer Go-Moku Tournament was played twice in 2005.<ref>{{Cite web|url=http://gomokuworld.com/articles/hungarian_computer_gomoku_tournament_2005|title=Hungarian Computer Gomoku Tournament 2005 {{!}} GomokuWorld.com|website=gomokuworld.com|access-date=2016-06-02}}</ref><ref>{{Cite web|url=http://www.sze.hu/~gtakacs/tournament/index.html|title=2nd Hungarian Computer Go-Moku Open Tournament|website=sze.hu|access-date=2016-06-03}}</ref> There were also two Computer vs. Human tournaments played in the Czech Republic, in 2006 and 2011.<ref>{{Cite web|url=http://gomocup.org/results/ai-human-2006|title=The 1st tournament AI vs. Human (November the 11th, 2006) {{!}} Gomocup|website=gomocup.org|access-date=2016-06-02}}</ref><ref>{{Cite web|url=http://www.piskvorky.cz/clanky/zajimavosti-ze-sveta-piskvorek-a-renju/ai-vs-clovek-2011-2/|title=AI vs. Člověk 2011 {{!}} Česká federace piškvorek a renju|website=piskvorky.cz|access-date=2016-06-02}}</ref> Not until 2017 did the computer programs prove capable of outperforming the world human champion in public competitions. In the Gomoku World Championship 2017, there was a match between the world champion program [[Yixin (software)|Yixin]] and the world champion human player Rudolf Dupszki. Yixin won the match with a score of 2–0.<ref>{{Cite web|url=http://www.aiexp.info/ai-vs-human-gomoku-2.html|title=Rudolf Dupszki versus Yixin|website=AIEXP}}</ref><ref>{{Cite web|url=https://www.facebook.com/notes/gomokuworld/rudolf-dupszki-vs-yixin-2017/857225044431377/|title=Rudolf Dupszki vs. Yixin 2017|website=Facebook}}</ref>

== In popular culture ==
Gomoku was featured in a 2018 Korean drama by Baek Seung-Hwa starring Park Se-wan. The film follows Baduk Lee (Park Se-wan), a former go prodigy who retired after a humiliating loss on time. Years later, Baduk Lee works part time at a go club, where she meets Ahn Kyung Kim, who introduces her to an Omok (Korean gomoku) tournament. Lee is initially uninterested and considers Omok a children's game, but after her roommate loses money on an impulse purchase, she enters the tournament for the prize money and loses badly, being humiliated once again. Afterwards, she begins training to redeem herself and becomes a serious omok player.<ref>Seung-hwa, Baek, writer. ''Omok Girl''. Performance by Park Se-wan, SK Telecom, 2018.</ref>

In the video game <i>[[Vintage Story]]</i>, omok boards and pieces (made of gold and lead) can occasionally be found in ruins or as part of luxury traders' inventory. The board and pieces are functional, allowing players to have actual omok matches. In-universe, omok is so far the only game surviving from the times before the Rot.

==See also==
* [[Renju]]
* [[Pente]]
* [[Pegity]]
* [[Connect6]]
* [[Connection game]]
* [[Reversi]]

==References==
<references/>

==Further reading==
* Five-in-a-Row (Renju) For Beginners to Advanced Players {{ISBN|4-87187-301-3}}

==External links==
* [http://gomokuworld.com/ Gomoku World]
* [https://www.renju.net/ Renju International Federation website]
* [https://gomocup.org/ Gomocup tournament]

{{Tic-Tac-Toe}}

[[Category:Abstract strategy games]]
[[Category:Traditional board games]]
[[Category:Japanese games]]
[[Category:Japanese inventions]]
[[Category:Paper-and-pencil games]]
[[Category:PSPACE-complete problems]]
[[Category:In-a-row games]]
[[Category:Solved games]]
[[Category:Games played on Go boards]]