Information AboutGo-moku |
| CATEGORIES ABOUT GOMOKU | |
| abstract strategy games | |
| japanese games | |
| paper and pencil games | |
| pspace-complete problems | |
|
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 (오목) and in Chinese as "五子棋" ( Pinyin : wǔzǐqí). With Go traditionally seen as a 'man's game', Gomoku is often a game associated with women, its simpler rulers better for their 'delicate' minds. Nonetheless, while Gomoku is infinitely easier than Go, it is a highly difficult game for both sexes. 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.
These restrictions are often applied only to black.
ANALYSIS Computer search by L. Victor Allis has shown that on a 15x15 board, black wins with Perfect Play . This applies regardless of whether 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 . The following recursive algorithm Pseudocode shows how one may develop a winning strategy for the problem gomoku (in PSPACE – proof not given) – for player X. Stop when step 1 hits a row of five X’s. 1: Assign X to a position, if X has won (there are five X's in a row) then we have a winning strategy and exit. If the board is full and no player has won, exit - there is no winning strategy. a: Assign O to a position – if the board is full or there are five Os in a row X was obviously a bad position, go back to 1 and choose another position, otherwise run the program on the new positions – via recursion, if that fails choose another position X in step 1. 2: If no assignment in step 1 allows for a ‘winning strategy’ then there isn’t one – ie X will eventually lose. SEE ALSO
EXTERNAL LINKS
REFERENCES
|
|
|