Games - Connect6

	Games - Connect6

Connect6 game, introduced by Professor I-Chen Wu at Department of Computer Science and Information Engineering, National Chiao Tung University, is a fair and highly complex game.

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 for that Black (the first player) places one stone only for the first move. The one who gets six consecutive (horizontally, vertically or diagonally) stones first wins the game.

Game Rules

The rules of Connect6 are very simple and similar to the traditional Go-Moku game:

Players and stones: There are two players. Black plays first, and White second. Each player plays with an appropriate color of stones, as in Go and Go-Moku.

Game board: Connect6 is played on a square board made up of orthogonal lines, with each intersection capable of holding one stone. In theory, the game board can be any finite size from 1×1 up (integers only), or it could be of infinite size. However, boards that are too small may lack strategy (boards smaller than 6×6 are automatic draws), and extremely large or infinite boards are of little practical use. 19×19 Go boards might be the most convenient. For a longer and more challenging game, another suggested size is 57×57, or nine Go boards tiled in a larger square.

Game moves: Black plays first, putting one black stone on one intersection. Subsequently, White and Black take turns, placing two stones on two different unoccupied spaces each turn.

Winner: The player who is the first to get six stones in a row (horizontally, vertically, or diagonally) wins.

According to Professor Wu, the handicap of black only being able to play one stone on the first turn means that the game is comparatively fair; unlike similar games such as Go-Moku 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.

Fairness

In principle, even some complex games are not fair: either the first or second player has an advantage. (Games such as Go-Moku 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 a roughly equal probability on making a mistake. From this, it is argued that Connect6 is fair in the following senses:

Each player always has one more stone than the other after making each move.

For about one thousand opening templates, Professor Wu let the AI program written by his team play against itself, and the result seemed to show that the game does not favor either one for these templates. Note that the AI program can beat most casual players, but this does not necessarily imply that its strategy is strictly optimal.

The initial breakaway (where White plays far away from the initial black stone) does not apparently favor White, according to Professor Wu. If the initial breakaway did not get penalty, the game would favor White for the following reason: Black must go back to defend the two white stones and then the situation is good for White since the game becomes to let White place two stones initially.

However, this evidence is not conclusive.

Complexity

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 Go-Moku and Renju, since many more moves are possible placing two stones than one—specifically n(n−1) 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¹⁷², the same as that in Go or Go-Moku. 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 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

(\frac{300\times300}{2})

or 45,000. Thus, the game-tree complexity is about

(\frac{300\times300}{2})^{30}

≈ 10¹⁴⁰, much higher than that for Go-Moku. Again, if a larger board is used, this complexity becomes much higher.

[ Visit the complete Wikipedia entry for Connect6 ]

Searches on eBay

connect6