Connect6

Connect6 (Chinese: 六子棋; Pinyin: liùzǐqí; Chinese: 連六棋;Japanese: 六目並べ; Korean: 육목) introduced in 2003 by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University in Taiwan, is a two-player strategy game similar to Gomoku.

Two players, Black and White, alternately place two stones of their own colour, black and white respectively, on empty intersections of a Go-like board, except that Black (the first player) places one stone only for the first move. The one who gets six or more stones in a row (horizontally, vertically or diagonally) first wins the game.

The rules of Connect6 are very simple and similar to the traditional game of Gomoku:

According to Professor Wu, the handicap of black's only being able to play one stone on the first turn means that the game is comparatively fair; unlike similar games such as Gomoku and Connect Four, which have been proven to give the first player a large advantage, possibly no additional compensation is necessary to make the game fair.

In principle, even some complex games are not fair: either the first or second player has an advantage. (Games such as Gomoku have been mathematically proven to give an advantage to one player or another; complex games such as chess are generally too complicated to analyze fully.) Herik, Uiterwijk, and Rijswijck give an informal 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 roughly equal opportunities for making mistakes. From this, it is argued that Connect6 is fair in the following senses:

However, this evidence is not conclusive.

If Connect6 uses an infinite board, both state-space and game-tree complexities are infinite as well. Instead, assume that a Go board is used. The game-tree complexities for it are still much higher than those in Gomoku and Renju, since many more moves are possible placing two stones than one—specifically n(n−1)/2 moves are possible, where n is the number of unoccupied spaces before a move. However, the state-space complexity is largely unchanged, since any legal position in one game will also be legal in the other. Based on the standard in Herik, Huntjens, and Rijswijck, the state space complexity of Connect(19,19,6,2,1) is 10¹⁷², about the same as that in Go or Gomoku. If a larger board is used, the complexity is much higher, since the number of moves increases exponentially with board size; it should still be the same as the other two games on the same size board.

Now, let us investigate the game tree complexity. Assume that the averaged game length is still 30, the same as the estimation for Gomoku (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 ${\displaystyle \left({\frac {300\times 300}{2}}\right)}$ or 45,000. Thus, the game-tree complexity is about ${\displaystyle \left({\frac {300\times 300}{2}}\right)^{30}}$ ≈ 10¹⁴⁰, much higher than that for Gomoku. Alternatively, if one assumes that the total number of stones placed (instead of the number of moves) is the same as that for Gomoku, that leaves us with an average game length of roughly 15. Then the game-tree complexity is roughly ${\displaystyle \left({\frac {300\times 300}{2}}\right)^{15}}$ ≈ 10⁷⁰, the same order of magnitude as that for Gomoku given in Allis 1994. Again, if a larger board is used, this complexity becomes much higher.