INTRODUCTION TO CONNECT6

Introduction to Connect6

The Connect6 game, introduced by Dr. I-Chen Wu, is a fair and highly complex game. Due to its simple rule, fairness and complexity, we believe that this game is a good alternative for those players who love to play Go-Moku or Renju. The outline is listed as follows.

Games rules
Fairness
Complexity
History
Naming
Game playing strategy
Game records

All comments are welcome to send to connect6@java.csie.nctu.edu.tw.

Thank you.

Connect6 Working Group
Internet Application Technology Laboratory
Department of Computer Science and Information Engineering
National Chiao Tung University
Hsinchu, Taiwan

GAME RULES

The rules of Connect6 are very simple and similar to the traditional Go-Moku game, as listed as follows.

Players and stones: There are two players. The first player, called Black here, holds a set of black stones, like Go or Go-Moku games. The second player, called White here, holds a set of white stones.
Game boards: In theory, the size of game board can be infinite. However, practically, it is hard to support such a game board. Therefore, our proposal is as follows.
- For casual players, simply use 19x19 Go boards.
- For professional players, use 59x59 boards.
  The reason we suggest this size for professional players in the following two senses. Players can tile up 9 Go boards to play, if games are played without the help of computers. In addition, judging from some current games, such as Go and Chess, we roughly estimate at most hundreds of moves per game in the extreme cases. Hundreds of moves inside a 59x59 board for Connect6 seem reasonable.
Game moves: Black plays first and puts only one black stone on one unoccupied intersection (or called grid). Subsequently, Black and White alternately put two of their own stones on two unoccupied grids.
Game winning: The one who first gets six or more consecutive stones (horizontally, vertically or diagonally) of her/his own wins. When all squares on the board are placed without connecting six, the game draws.

Unlike Renju, we do not need to impose some extra rules on Connect6, since the rules of Connect6 appear to be fair enough as shown in the section, fairness.

Note that most current Connect6 professionals play on 19x19 Go boards. However, many of them believe that Connect6 is a draw game. After one or two years, we may need to extend the rule. The current proposals include the following:

Simply use 59x59 boards as described above.
When all squares on the board are placed without connecting six, the one who has more fives than the other wins. If the number of fives are still the same, the one who has more fours wins, etc.

You are welcome to discuss this issue in the forum.

FAIRNESS

First, we want to review the fairness problem of Go-Moku and then discuss the fairness of Connect6.

Fairness of Go-Moku

Fairness has been a major issue for Go-Moku, even though it has been a popular game.

In the free style of rules (without any restriction to Black), it has been well known that the game favors Black. Theoretically, it was proved (Allis, 1994; Allis, Herik, and Huntjens, 1996) that Black wins in the free style.
To reduce the unfairness problem, the Japanese professional Renju association added some rules (Japanese professional Renju association, 1903) to restrict the play of Black for professional players. For example, Black is prohibited to play double three and double four. The game with the restrictions is called Renju. In fact, Renju still favors Black, from the experiences of professionals. It was also proved (Wágner, Virág, 2001) that Black wins under these restrictions.
The Renju International Federation (RIF) changed the rules (RIF, 1998) to make it fairer by imposing some opening rules for the first five moves.
In 2003, RIF requested a proposal (RIF, 2003) for better opening rules again and listed the requirements for new rules. We believe that the next generation rules from RIF would be good in this sense. However, this hints that the current rules are still not perfect. In fact, adding more rules makes it harder to learn the game.

The fairness problem for Go-Moku or Renju also has a side effect.

Reduce the board size. It was argued (Sakata and Ikawa, 1981) that a larger board increases black's advantage which resulted in the standard Renju board size of 15x15. However, a smaller board reduces the complexity of the game. Consequently, it becomes easier to solve the game.

Definitions of Fairness

Herik, Uiterwijk, and Rijswijck gave a good definition of fairness (Herik, Uiterwijk, and Rijswijck, 2002) as follows: A game is considered a fair game if it is a draw and both players have a roughly equal probability on making a mistake. However, practically, it is hard to have a perfect model for calculating the probability of making a mistake, since some undiscovered strategies such as making breakaway moves, as described in Subsection 2.3, may result in different probabilities. On the contrary, it is relatively easy and possible to
show when a game is unfair. Therefore, Professor Wu provides the following three distinct definitions for unfair games.

A game is definitely unfair, if it has been proved that some player wins the game. For example, since B wins in Go-Moku (in the free style) as described above, Go-Moku is definitely unfair.
A game is monotonically unfair, if it has been proved that one player does not win the game, but it has not been proved for the other player.
A game is empirically unfair, if most players, in particular professionals, have claimed that the game favours some player. For example, before Go-Moku was solved, Go-Moku was empirically unfair, since most professionals claimed that B would win.

Then, Professor Wu defined that a game is considered potentially fair, if it has not yet been shown or claimed to be definitely unfair, monotonically unfair, or empirically unfair. This definition indicates that a potentially fair game for the time being may not remain potentially fair in the future. If a game remains potentially fair any longer, it could have a higher chance to be fair.

Fairness of Connect6

Connect6 games are intuitively fair, in the sense that one player always has one more stone than the other after making each move. Besides, Connect6 is, at least, potentially fair for the time being.

Surely, we expect to see more evidences, either fair or unfair, or more experiences in the future.

COMPLEXITY

If Connect6 uses an infinite board, both state-space and game-tree complexities are infinite too. So, we assume to use a Go board, instead. Both state-space and game-tree complexities for it are still much higher than those in Go-Moku and Renju, in the sense that each move places two stones that make the branch factor increase by a factor of the board size. Based on the standard in (Herik, Huntjens, and Rijswijck, 2002), the state-space complexity of Connect(19,19,6,2,1) is 10172, the same as that in Go. If a larger board is used, the complexity is much higher.

Now, let us investigate the game-tree complexity. Assume that the averaged game length is still 30, the same as the estimation for Go-Moku (Allis 1994). Then, the number of grids chosen to put one stone is about 300, and the number of choices of one move is about (300*300/2). Thus, the game-tree complexity is about (300*300/2)30 ~ 10140, much higher than that for Go-Moku. Also, if a larger board is used, this complexity is much higher.

HISTORY

(written by I-Chen Wu)

One day in Summer 2003, I played Go-Moku on a Go board with my daughter for fun. My daughter suggested playing it differently by letting both Black and White put two stones in each turn. This motivated me to think the potential of the game, Connect6, to be a popular game, and researching on it. However, as a popular game, this game must be fair enough and highly complicated. My first plan is to have an AI program to play the game to see how fair and complex the game is.

In Spring 2004, my Master student, Dei-Yen Huang, joined this work as the study of his Master Thesis. In Q1 of 2005, we completed the first Connect6 AI program, which already can beat most of us. Then, we let our AI program fight with our AI program. And, so far, we still cannot determine who (Black or White) has the advantage.

In 2005, we wrote a paper, to be presented in the 11th Advances in Computer Games Conference (ACG11), held in Taipei, Taiwan, 2005.

In September 2005, ThinkNewIdea Limited built the first Connnect6 game server at http://www.cycgame.com.tw/connect6/.

In 2005, some interested persons are organizing a Connect6 association at http://www.connect6.org, and supporting a forum for discussion.

NAMING

Officially, we name it Connect6 (pronounced "Connect-Six"), "連六棋" ( or more commonly called "六子棋") in Chinese and Roku-Moku ("六目") in Japanese. Originally, it was named Ren6 in order to distinguish it from Connect(6,2,2). However, Ren6 might be connected to Renju, which imposes some more restriction rules, so we call it Connect6 now.

GAME PLAYING STRATEGY

In Connect6 games, a line consists of a set of grids in the same horizontal, vertical, or diagonal line. The stones of a line form a pattern of the line. A line pattern is called a line threat where one player must put one or more stones in the line to prevent the other from winning by putting p stones into the line. For example, in Connect6, B has a threat pattern in the line in the left of Figure 1 (a), since B can connect up to consecutive six stones by playing on the two empty grids above “△”. If W cannot connect six in the next ply, W must defend at either empty grid above “△”.

Definition 1. In a line pattern of Connect6, assume that one player, say W, cannot connect six. B is said to have t threats, if and only if W needs to put t stones to prevent B from winning in the next ply. ▌

(a) One threat.

(b) Two threats.

Figure 1: Threat patterns for Connect6.

In Figure 1(a), B has one threat, since W needs to use one stone to defend. In Figure 1(b), B has two threats, since W needs to use two stones to defend. In the case of three threats as shown in Figure 1(c), B wins since W needs three stones to defend. That is, the winning strategy of a player is to have at least three threats

It needs to be careful to count the number of threats. For example, the line pattern in the right of Figure 1(a) has only one threat (not two), because W only needs to put one stone on the empty grid above “△”.

For the line pattern in the right of Figure 1(a), when the window first covers the four black stones without the white, mark the two empty grids including the one above “△”. Thus, when the window is slid for one grid, the window covers the marked empty grid. Thus, the second window is not counted. Thus, the line pattern has only one threat.

Figure 2: Blocking strategies in Connect6.

In Connect6, putting one stone in a line increases threats by at most two. It is interesting to distinguish a grid which will cause one threat or two threats in subsequent playing. For example, in Go-Moku or Renju, a three is called live-three if it has two open ends and can create two threats by adding one stone, and dead-three, if it has only one open end and can create one threat only by adding one stone. Like Go-Moku or Renju, Connect6 also has dead-l and live-l threats, as defined as follows.

Definition 2. In Connect6, a line pattern includes a dead-l threat for one player, say B, if B only needs to add extra (4–l) stones to create one threat. Similarly, a line pattern includes a Live-l threat for B, if B only needs to add extra (4–l) stones to create two threats. ▌

(a) Live-3 threats.

(b) Live-2 threats.

(d) Dead-2 threats.

Figure 3: Live-l and Dead-l threats for Connect6.

For example, the line patterns in Figure 3(a) are live-3 threats, since B only needs to put one more stone to create two threats, as shown in Figure 1(b). Similarly, the line patterns in Figure 3(b) are live-2 threats, since B only needs to put two more stones to create two threats. Similarly, examples of dead-3 and dead-2 are given in Figure 3(c) and Figure 3(d), respectively.

In Connect6, live-3, live-2, dead-3, and dead-2 threats are important, since a move includes two stones and may make them become threats. Especially, players usually attack with a sequence of moves most including live-2 and dead-3. These are also very useful for game playing.

Now, let us go back to review Gomoku, Connect(5,1,1). In Gomoku, since players can put one stone (p=1) only in each move, players cannot defend live-4 threats, unless connecting five. Furthermore, in the case of not making dead-4 threats, players must defend a live-3 threat, also called a three (Allis, 1994; Allis, Herik, and Huntjens, 1996). Otherwise, opponents can put one stone to make it a live-4 to win the game. Since players must defend live-3 threats in this case, live-3 threats can be viewed as delayed threats.

GAME RECORDS

The following are played by two computers. White wins in the following case.

Black wins in the following case.

The following are played by Computer and Dei-Yen Huang. Computer (Black) wins in the following case.

Computer (White) wins in the following case.

We will post more game records later.

REFERENCES

Allis, L. V. (1994). Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht.

Allis, L. V., Herik, H. J. van den, and Huntjens, M. P. H. (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence, Vol. 12, pp. 7–23.

Allis, L.V., Meulen, M. van der, Herik, H.J. van den(1994). Proof-number search, Artificial Intelligence 66 (1) 91–124

Beal, D.F. (1989). Experiments with the Null Move. Advances in Computer Chess 5 (ed. D.F. Beal), pp.65-79. Elsevier Science Publishers B.V., Amsterdam, The Netherlands.

Beck, J. (1981) On positional games. J. of Combinatorial Theory Series A 30 (1981), 117-133.

Csirmaz, L., (1980). On a combinatorial game with an application to Go-Moku, Discrete Math. 29, 19-23.

Cazenave, T. (2001a). Iterative Widening. Proceedings of IJCAI-01, Vol. 1, pp. 523–528, Seattle.

Cazenave, T. (2001b). Abstract Proof Search. Computers and Games (eds. T. A. Marsland and I. Frank), Vol. 2063 of Lecture Notes in Computer Science, pp. 39–54, Springer. ISBN 3–540–43080–6.

Cazenave, T. (2003). A Generalized Threats Search Algorithm. Computers and Games, Vol. 2883 of Lecture Notes in Computer Science, pp. 75–87.

Hales, A.W., Jewett, R.I. (1963). Regularity and positional games. Transactions of the American Mathematical Society 106 222-229.

Herik, H. J. van den, Uiterwijk, J.W.H.M., Rijswijck, J.V. (2002). Games solved: Now and in the future. Artificial Intelligence, Vol. 134, pp. 277-311.

Japanese Professional Renju Association, (1903). History of Renju Rules, http://www.renjusha.net/database/oldrule.htm.

Pluhar, A. (1994). Generalizations of the game k-in-a-row, Rutcor Res. Rep. 15-94.

Pluhar, A. (2002). The accelerated k-in-a-row game, Theoretical Computer Science. 271 (1-2) 865-875.

Renju International Federation (1998). The International Rules of Renju, http://www.renju.nu/rifrules.htm.

Renju International Federation (2003).

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

Thomsen, T. (2000). Lambda-search in game trees - with application to Go. ICGA Journal, Vol. 23(4), pp. 203–217.

Uiterwijk, J.W.H.M., Herik, H.J. van den. (2000). The advantage of the initiative, Information Sciences 122 (1) 43–58..

Wágner, J., Virág, I. (2001) Solving Renju, ICGA Journal, Vol. 24 (1) 30–34.

Wu, I-C., Huang, D.-Y. (2005) A New Family of k-in-a-row Games. ACG11, September 2005.

Wu, I-C., Huang, D.-Y. (2005) Null-move search for Connect Games. (in preparation).

Zetters, T.G.L. (1980). Problem S.10 proposed by R.K. Guy and J.L. Selfridge, Amer. Math. Monthly 86 (1979), solution 87(1980) 575-576.