Introduction to Connect Games

In this page, we introduce a family of k-in-a-row games. The outline is listed as follows. 

• Games rules
• Fairness
• Game Playing Strategy

Related Pages:

• Connect6 homepage.
• Connect6 Chinese homepage. (六子棋中文版首頁)
• Introduction to Connect6.
• Introduction to generalized k-in-a-row games.
• Frequently Asked Question (FAQ) page.
• The paper about Connect6, published in ICGA.
• The paper about generalized k-in-a-row games, published in ACG11.
• The Connect6 organization (being organized)

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. 

Here, we introduce a new family of k-in-a-row games, Connect(m,n,k,p,q), with the following rules. 

• Players and stones: There are two players.  The first player, called Black here, holds an infinite set of black stones, like Go or Go-Moku games.  The second player, called White here, holds an infinite set of white stones.
• Game boards: There is a game board, like Go or Go-Moku game boards, with mxn grids.  
• Game moves:  Black plays first and puts only q black stone on q unoccupied intersections (also called grids).  Subsequently, Black and White alternately put p of their own stones on p unoccupied grids.
• Game winning: The one who first gets k or more consecutive stones (horizontally, vertically or diagonally) of her/his own wins. 

For simplicity, Connect(k,p,q) denotes the game Connect(¥,¥,k,p,q), played on infinite boards.

FAIRNESS

In the past, many researchers were engaged in understanding the fairness of k-in-a-row. We first try to list the solved games as follows.

1. (Allis, 1994; Allis, Herik, and Huntjens, 1996) Black wins for Go-Moku in the free style, i.e., Connect(5,1,1). 
2. (Wágner, Virág, 2001) Black wins for Renju, the same as Connect(5,1,1) without double three and double four. 
3. (Zetters, 1980) White ties for Connect(8,1,1).  
4. (Uiterwijk, Herik, 2000; Herik, Uiterwijk, Rijswijck, 2002) Many Connect(m,n,k,1,1) games are solved and listed.
5. (Pluhar 2002; Wu, Huang, 2005a) White ties in some condition, roughly like d=W(log p) (cf. Theorem 1 of Pluhar 2002).
6. (Wu, Huang, 2005a) For Connect(k,p,q) game, Black wins when p < ëq/d²û(4d+4), where d=k–p.
7. (Wu, Huang, 2005a)  Several games are solved empirically.

Empirically Unfair Connect Games

Now, we empirically investigate the fairness of some Connect games in two ways.  First, we try to prove informally that either B or W wins.  Second, if we cannot prove, we try to see whether one player keeps obtaining initiatives leading to a win in the cases that we investigate.  In this case, we call that the game favors that player. Namely, FB means to favor B and FW means to favor W.

Table 1: The empirical results for Connect games with k£9 and d = 3.

Now, we list one game record (note that the above links to files in the SGF format ) for each of some cases as follows. 

In the following case, White wins for Connect(6,3,2).

In the following case, White wins for Connect(7,4,2).

In the following case, Black wins for Connect(8,5,3).

In the following case, White wins for Connect(9,6,4).

Our empirical experiences for k£9 show that most games with d£3 are unfair, as shown in Table 1.  In this table, B (or W) indicates that the game can be informally proved with Black (or White) winning; and FB (or FW) indicates that the game favors Black (White).  For example, in Figure 5, we show a game history of Connect(9,6,4), where White keeps obtaining initiatives on attacking Black.    

GAME PLAYING STRATEGY

Like Ren6's threat definitions, we generalizes threat definitions. 

Definition 1.  In a line pattern of Connect(k,p,q), assume that one player, say W, cannot connect up to k.  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 move. ▌

a) One threat in Connect(9,6,3).

(b) Two threats.

Figure 5: Threats for Connect(9,6,3).

For example, in Figure 5(a), B has one threat in Connect(9,6,3), since W can defend by using one stone on any of grids above “△”.  In  Figure 5(b), B has two threats in Connect(9,6,3), since W needs to use two stones to defend. 

In general, the winning strategy of a player is to have at least (p+1) threats (after defending the opponent’s threats), since the opponent only has p stones to put.  For example, in Connect(9,6,3), one player needs to have 7 threats to win the game.

Definition 4.  In Connect(k,p,q), a line pattern includes a dead-l threat for one player, say B, if B only needs to add extra (d–l) stones to make the line pattern one threat.  Similarly, a line pattern includes a live-l threat for B, if B only needs to add extra (d–l) stones to make the line pattern have two threats.  ▌

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., and Chang, H.-C. (2005) "Connect6", ICGA Journal, Vol. 28, No. 4, pp. 234-241, December 2005.

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.