Go-moku family of games

Topic editor: Alexander Nosovsky stigma.ltd@g23.relcom.ru

Contributions are welcome and the ICGA will, with permission, list contributor’s names and email addresses on its Contributor’s page.

Introduction, Game Names and Rules

Here we survey a collection of associated games variously known as the Connect-Five, Go-Moku or Renju family.

Connect Five. The object of this two-player game is to create a line of 5 stones of the player’s colour on a square grid. Black starts first and stones are laid down alternately, and permanently, on the grid. The game is a draw if the board is filled and no horizontal, vertical or diagonal line of 5 stones has been created.

Connect Five is known as Ameba (Hungary, Poland), Caro (Vietnam), Cross-Circles on a Non-Margin Board (Russia), Freestyle Go-Moku (van den Herik, Uiterwijk and van Rijswijck, 2002), Gobang (Germany), Go-moku (Japan), Lufarchak (Sweden), Morpion (France), Omok (Korea), Piskvorky (Chehia, Slovakia), WuZiQi (China), and Go-Moku or Five In A Row elsewhere.

The game is a 'big brother' version of Tic-Tac-Toe or Noughts and Crosses which requires only a 3x3 grid and aims to create a line of 3 stones. Pencil and squared paper may conveniently be used instead of stones on a board, making the game very accessible worldwide.

Both Tic-Tac-Toe and Connect Five are examples of m-n-k games where the objective is to create a line of k stones on an m x n board. Tic-Tac-Toe is 3-3-3, whereas Connect Five is 19-19-5 on a Go board (as played in countries that know Go), 15-15-5 or 13-13-5 on smaller boards, and ¥-¥-5 on an unrestricted board.

Since 1936, the Japanese have believed that Connect Five was a first-player win, and had produced an extended, though partial, proof to their satisfaction. The information in that proof was used as opening book theory in the earliest computer-codes for this game.

Victor Allis proved by a complete computer-search that it was a first-player win and thereby weakly-solved the game.

Because of the first-player bias, a variety of games have been derived from the basic Connect Five to make the game fairer for the 2nd player. These use various rules which constrain either Black, White, or both players.

This introduction to the Renju family mentions some of these games.

Go-moku. This is Connect Five on a 19x19, 15x15 or 13x13 board with this rule:

  • Rbw1: an Overline is not a win for either side.

It is popular all over the world and the Computer Olympiads of 1989-1992 had 15x15 tournaments for computers. It is also called Standard Go-moku (van den Herik, Uiterwijk and van Rijswijck, 2002).

The game was regarded as a 1st-player win by Japanese players, and was also weakly solved for a 15x15 (or larger) board as a 1st-player by Victor Allis.  Go Moku on a 13x13 board is also a 1st-player win but requires a solution other than for the 15x15 board.

Japanese Go-moku (Go-moku-narabe). This is played on a 19x19 board with these rules:

  • Rbw1: an Overline is not a win for either side

  • Rb1: the 1st player (Black) puts the first stone on the center of the board (j10, assuming an a-s, 1-19 board)

  • Rw1: the 2nd-player (White) must play move 2 in the central 3x3 square (i9-k11)

  • Rb2: Black is not allowed to create a 3x3 fork

Korean O-muk. This is played on a 19x19 board with these rules:

  • Rbw1: an Overline is not a win for either side

  • Rb1: the 1st player (Black) puts the first stone on the center of the board (j10, assuming an a-s, 1-19 board)

  • Rw2: the 2nd-player (White) must play move 2 in the central 5x5 square (h8-l12)

  • Rb3: Black is not allowed to create a 3x3 or 4x4 fork

Pro-Go-Moku (Five in a Row with the prohibited central square). This is played on a 15x15 board with these rules:

  • Rbw1: an Overline is not a win for either side

  • Rb4: move 3 (i.e. Black’s 2nd) must be outside the central 5x5 square (i.e. outside f6-j10)

The game is sometimes known as Free Renju in Russia and the Ukraine. The first player has a big advantage with 90-95% wins at a high level of play.

Renju. This is played on a 15x15 board with these rules:

  • Rb5: Black is not allowed to create an overline, a 3x3 fork or a 4x4 fork: such moves win for White.

Rules about opening play vary according to the standard of the players:

  1. Beginners: any opening is allowed

  2. Intermediate Players: White Option Opening Rule. White places:
    • 1st Black stone on central square h8, 1st White stone in the central 3x3 square g7-i9,

    • 2nd Black stone in one of 12 places in the central 5x5 square f6-j10.

  3. Masters:
    • Black places the 1st Black stone on h8, and the 1st White stone in the central 3x3 square g7-i9.

    • Black places the 2nd Black stone in the central 5x4 square f6-j10.

    • White may then choose to swap colours and play Black if it wishes.

    • The side now White plays a 4th move.

    • The side now Black gives two options for the 5th move, and White picks one of these.

These are the Renju International Federation Rules as used for the human World Renju Championships.

Computer Renju World Championships were held in 1991, 1998 and 2000: there are over-the-board tournaments and problem-solving competitions. The strongest Tournament program strength is above 3-4 Dan (Candidate of Master).

Important links

Pente. This game is played on a 19x19 board with these rules:

  • Rb4: the 3rd move (Black’s 2nd) is made outside the central 5x5 square

  • Rbw2: if a player can close 2 opponent’s stones on both ends, this 'pair' is removed as a 'capture'

  • Rbw3: five 'captures' is one way of winning

This is popular in the USA, and is a simplified variant of Japanese Ninuki-renju. The first player’s advantage is probably too high at 70-80%. There have been Pente tournaments in USA, Sweden and Russia, and a match between two Pente programs was won by Mark Mammel’s Program. The programs cannot beat the strongest players yet.

Important links

Keryo-Pentei. This game is played on a 19x19 board with these rules:

  • Rb4: the 3rd move (Black's 2nd) is made outside the central 5x5 square

  • Rbw4: if a player can close 3 opponent's stones on both ends, this 'three' is removed as a 'capture'

  • Rbw3: five 'captures' is one way of winning

This game is popular in the USA and Japan, but not as popular as Pente.

Ninuki-Renju. This game is played on a 19x19 board with these rules:

  • Rbw1: an Overline is not a win for either side

  • Rb2: Black is not allowed to create a 3x3 fork

  • Rbw2: if a player can close 2 opponent’s stones on both ends, this ‘pair’ is removed as a ‘capture’

  • Rbw3: five ‘captures’ is one way of winning

  • Rbw5: only perfect five win the game. (Perfect five such five which can not be captured by next move)

It was played before the 2nd World War but is not popular in Japan now.

Boku. This game can be played on a hexagonal board invented by Rob Nelson. It has these rules:

  • Rbw6: if a player can close two opponent-stones on both ends, they can choose which to remove

  • Rbw7: the next move cannot be done at the place where a stone is removed (the Go rule of Ko)

Of course, it is possible to play this game on a 19x19 or other-sized board.

Link: www.londongame.com/boku.html

Example Games

1) Free-style Go-moku:  a forced 1st-player win (Allis, 1994; 5.5.3, p152) but not minimax play:

1. H8 2. H7 3. G7 4. F6 5. I9 6. G8 7. I8 8. I6 9. F9 10. G9 11. H9 12. H6 13. G6 14. J5 15. K4 16. G10 17. I11 18. I10 19. J10 20. K11 21. K9 22 L8 23. J9 {but 23. G11 with threats 25. H12 or J8 wins in 31} 24. L9 25. J8 26. G11 27. G12 28. J11 29. K7 30. L6 31. J7 32. J6 33. K6 34. L5 35. L7 36. M7 37. K5 38. K3 39. K8

A quicker win starts 23. G11 as there are two wins 25. A 27. B and 25. C 27. D, expanded here:

  1. 24. A 25. C {threat G11-J8} 26. <blocks G11-J8> 27. D {forcing} 28. L9 29. J11 {a winning 4} 1-0.
  2. 24. C 25. A (forcing} 26. G13 27. B {forcing} 28. H10 29. F11 {a winning 4} 1-0.
  3. 24. J11 25. A {forcing} 26. G13 27. H10 {forcing} 28. H11 29. J8 {a winning 4} 1-0.


2) Standard Go-Moku: a forced 1st-player win (Allis, 1994; 5.5.3, p152) but not minimax play:

1. H8 2. H7 3. G7 4. F6 5. I9 6. G8 7. I8 8. I6 9. F9 10. G9 11. H9 12. H6 13. G6 {and now the line diverges from the free-style Go. moku game above} 14. K4 15. J5 16. G10 17. I11 18. I10 19. J10 20. K11 21. K9 22. L8 23. J8 {but 23. G11 24. H10 25. F10 26. A/B 27. B/A wins more quickly} 24. G11 25. G12 26. L9 27. L10 28. M11 29. K6 30. K7 31. J11 32. J9 33. H12 34. G13 35. I12 36. J12 37. H13 38. G14 39. F12 40. E12 41. F11 42. I14 43. F10 44. F13 45. F8

Quicker wins starting 23. G11 24. H10 25. F10 are illustrated here:

3) Renju with no opening rules: a forced 1st-player win (Wágner and Virág, 2001):

1. H8 2. H7 3. I7 4. G9 5. J6 6. I8 7. I6 8. G6 9. J9 10. K5 11. K6 12. L6 13. J7 14. J8 15. K8 16. L9 17. L7 18. M6 19. J4 {but a quicker win, illustrated below, is 19. I4 20. J5 21. I5 22. I3 23. K7 24. M7 25. J4 26. H4 27. G7 28. H6 29. J10 30. I9 31. K10 32. K9 33. I10 34. H11 35. H10} 20. I4 21. K7 22. M7 23. I5 24. H4 25. G7 26. H6 27. H5 28. G4 29. F5 30. G5 31. J10 32. F4 33. E4 34. E3 35. D2 36. G3 37. G2 38. N8 39. O9 40. I9 41. I10 42. H11 43. K10 44. K9 45. H10 46. G10 47. L10

and the shorter win is shown here:

4) Renju, Masters Opening Rules. Linas Laibinis (Litvenia-Finland) - Alexander Nosovsky (Russia):

a game from E-mail World Championship Final 2002


Diagram 1

Laibinis chose the opening 11 Direct. White, after some thinking, decided not to swap but to play as White.

To make the chances equal, the Master Opening Rules were used in this competition. Black is able to play any opening, i.e. first 3 moves, that he likes, but White is able to swap sides. If Black plays an opening with strong chances to win, White will surely reverse and the first player will have to play the weaker side as White. This rule means that opponents chose the openings they are happy to play as either side. Also, in Master Regulations, Black has to suggest two variants of the 5th move to provide a choice for White.

Move 5-10 was suggested as the alternative but not chosen by White. After move 5, play is governed only by the rules of Renju.

These first eleven moves are the standard opening moves in the 11 Direct Opening. 11 Direct has become a rather popular opening in the last 5 years. 12-H7 is standard but then Black can play 13-K10, a very famous position in which Black has an advantage. Now, more and more players try new moves to improve White's strategy.

This 12th move is very rare; the 13th is the strongest. Move 14 was a novelty for that time and Linas played the 15-15 move because move 14 was a surprise for him.

Later it was found that 15-H7 was stronger, and that Black could win.

Diagram 2

The idea of move 16 is to cut Black’s attack into two parts, left and right. Move 17 is trying to use a strategy of "going far away". The aim of this strategy is to create an excess of black stones on the left flank so that White cannot defend against them, and to create them a lot of opportunities and possible points for continued attack.

Move 18 is trying to protect against this strategy - to defend against a possible “going far away”. Move 19 is defending against White’s probable pair 12-14 and simultaneously trying to attack on the right side of the position. It threatens a 4-3 fork at the point J8.

Move 20 protects against the fork on J8, stopping a probable three, and at the same time makes a three for White. Black stops a white three with its own three and White has to stop it by playing move 22. That was the key point of this game, Black has to decide what plan he wants to use. Will he continue an attack, or is there a better way to defend in this position? Really it was difficult to decide.

Probably 23-23 was the wrong choice. It seems that Linas did not find good attacking possibilities and decided to start defend against the white activity on the right side of position.

Diagram 3

So, the initiative is now on White’s side, and he starts an attack in the left side! To stop this three from the other side is not possible because of a strong attack.

If 27-D9 then 28-27, 30-31 ... 32-F9, 33-F10, 34-F5, 36-G10, 38-C6, 40-33 foul 3x3 on the point D8. (If Black stops the three 33-F6, 34-G10, 36-C6, 38-33). So, Black stops the three with four 27-27 and protects from the upper three playing moves 29-29 and 31-31.

White has a VCT, Victory by Continuous Threats, win on the left side of the position, so Black has to use one move to try to stop it. So, he plays 33-33 which makes White’s win possible.

Diagram 4

Move 36 is really strong and very nice. This is fukumi and threatens to win by forcing various 3x3 fouls. This is the final attack. If 35-39 36-G10, 37-D7, 38-G3, 40-35 and a 4x4 foul on the point F5. After move 40, Black resigns because of threats E12, G10 and G11, C11.

This is a rather short game which shows us that in Renju the initiative is very important . First Black has the advantage and if White can neutralise that, it has more opportunities because of the non-symmetrical rules.

Future Challenges

  1. Weakly solve the remaining variants of Connect Five – different board-sizes, different rules – including:

    • free-style and standard Go-moku on smaller boards

    • Go-moku with new Opening Rules, including swapping

    • Renju with opening rules

  2. 4th Computer Renju Tournament (2004) and Solving Problems Competitions.

  3. Discover minimax-win solutions from opening positions.

  4. Strongly-solve weakly-solved games.

References

Books and Papers

  • Allis, L.V. (1994). Searching for Solutions in Games and Artificial Intelligence. Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 9-0900-7488-0.

  • Allis, L.V., Herik, H.J van den, and Huntjens, M.P.H. (1993). Go-Moku and Threat-Space Search. Report CS 93-02, Department of Computer Science, Faculty of General Sciences, University of Limburg, Maastricht, The Netherlands. ISSN 0922-8721.

  • Allis, L.V., Herik, H.J. van den, and Huntjens, M.P.H. (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence: An International Journal. Vol. 12, No. 1, pp. 7-24. Special Issue on Games. Blackwell Publishers. ISSN 0824-7935.

  • Allis, L.V., Meulen, M. van der, and Herik, H.J. van den (1994). Proof-Number Search. Artificial Intelligence, Vol. 66, No. 1, pp. 91-124. ISSN 0004-3702.

  • Herik, H.J. van den, Uiterwijk, J.W.H.M. and Van Rijswijck, J. (2002). Games solved:  now and in the future. Artificial Intelligence, Vol. 134, pp. 277-311. Reprinted in Chips Challenging Champions (ed. J. Schaeffer and J. van den Herik), Elsevier (2002). ISBN 0-4445-0949-6.

  • Lasker E. (1934). Go and Go-moku. Dover Publications Inc., New York, USA. ISBN 0-4862-0613-0 (1982 Ed.)

  • Nosovsky, A. (2002). Go-moku Still Alive. ICGA Journal, Vol. 25, No. 1, pp. 47-48.

  • Sakata, G. and Ikawa, W. (1981). Five-in-a-Row, Renju. The Ishi Press, Inc. Tokyo, Japan.

  • Wágner and Virág (2001). Solving Renju.  ICGA Journal, Vol. 24, No. 1, pp. 30-34.

Web sources