Connect6
Encyclopedia
Connect6 introduced in 2003 by Professor I-Chen Wu
at Department of Computer Science and Information Engineering, National Chiao Tung University
, is a two-player 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.
:
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.
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.
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 10172, 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
or 45,000. Thus, the game-tree complexity is about 
≈ 10140, 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 
≈ 1070, 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.
One day in the summer of 2003, Professor I-Chen Wu came up with this game when playing with his daughter. He started considering the potential of the game to be popular, and began to investigate it. To be popular, he reasoned, his game must be fair and complex, so his first plan was to have a computer program play the game to see how fair and complex it is.
In spring 2004, a master
student of Professor Wu, Dei-Yen Huang, joined Wu's project as his master thesis. In the first quarter of 2005, they completed the first Connect6 AI program, which already can beat most players. Then Wu's team allowed his AI program to play itself.
In 2005, Wu's team wrote a paper, presented in the 11th Advances in Computer Games Conference (ACG11), held in Taipei
, Taiwan
, 2005.
In September 2005, ThinkNewIdea Limited built the first Connect6 game server.
On September 20–September 21, 2005, the game was covered by many news media in Taiwan
.
In 2005, interested people started discussing the organization of a Connect6 website at http://www.connect6.org and supporting a forum for discussion.
The program NCTU6, rewritten by Professor Wu, won gold in the Connect6 tournament at the 11th Computer Olympiad
.
The First Annual NCTU Cup Connect6 Open Tournament was sponsored by National Chiao Tung University (NCTU) and held in Hsinchu, Taiwan, on July 16th, 2006.
I-Chen Wu
I-Chen Wu is a Professor at Department of Computer Science, National Chiao Tung University. He received his B.S. in Electronic Engineering from National Taiwan University , M.S. in Computer Science from NTU, and Ph.D...
at Department of Computer Science and Information Engineering, National Chiao Tung University
National Chiao Tung University
National Chiao Tung University is a public university located in Hsinchu, Taiwan. It is recognized as one of the most prestigious and selective universities in Taiwan and is renowned for its research and teaching excellence in electrical engineering, computer science, engineering, management, and...
, is a two-player game similar to Gomoku
Gomoku
Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil 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 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.
Rules
The rules of Connect6 are very simple and similar to the traditional game of GomokuGomoku
Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil 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 Gomoku.
- 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 59×59, or nine Go boards tiled in a larger square (using the join lines between the boards as additional grid lines).
- 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 or more stones in a row (horizontally, vertically, or diagonally) wins. (This is a departure from GomokuGomokuGomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game...
, where it must be exactly five in a row.)
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
Gomoku
Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game...
and Connect Four
Connect Four
Connect Four is a two-player game in which the players first choose a color and then take turns dropping their colored discs from the top into a seven-column, six-row vertically-suspended grid...
, 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 Gomoku have been mathematically proven to give an advantage to one player or another; complex games such as chessChess
Chess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
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:
- Each player always has one more stone than the other after making each move.
- For about one thousand opening templates, Professor Wu let the AIArtificial intelligenceArtificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...
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 GomokuGomoku
Gomoku is an abstract strategy board game. Also called Gobang or Five in a Row, it is traditionally played with go pieces on a go board ; however, because once placed, pieces are not moved or removed from the board, gomoku may also be played as a paper and pencil game...
and Renju
Renju
Renju is the professional variant of Gomoku, a board game originated from Japan in Heian Period. It was named Renju by Japanese journalist Ruikou Kuroiwa on December 6, 1899 in a Japanese newspaper Yorozu chouhou . It is played with black and white stones on a 15x15 intersection Go board...
, 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
State space
In the theory of discrete dynamical systems, a state space is a directed graph where each possible state of a dynamical system is represented by a vertex, and there is a directed edge from a to b if and only if ƒ = b where the function f defines the dynamical system.State spaces are...
complexity of Connect(19,19,6,2,1) is 10172, 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
Game tree
In game theory, a game tree is a directed graph whose nodes are positions in a game and whose edges are moves. The complete game tree for a game is the game tree starting at the initial position and containing all possible moves from each position; the complete tree is the same tree as that...
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
or 45,000. Thus, the game-tree complexity is about ≈ 10140, 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 ≈ 1070, 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.History
It is unclear who first came up with the idea of the game Connect6. However, it is widely believed that the idea of the game (Chinese name "六子棋") emerged on the internet around 1999 first on the Chinese popular BBS site bbs.tsinghua.edu.cn and subsequently on the popular overseas Chinese BBS site bbs.mit.edu (now www.mitbbs.com).One day in the summer of 2003, Professor I-Chen Wu came up with this game when playing with his daughter. He started considering the potential of the game to be popular, and began to investigate it. To be popular, he reasoned, his game must be fair and complex, so his first plan was to have a computer program play the game to see how fair and complex it is.
In spring 2004, a master
Master's degree
A master's is an academic degree granted to individuals who have undergone study demonstrating a mastery or high-order overview of a specific field of study or area of professional practice...
student of Professor Wu, Dei-Yen Huang, joined Wu's project as his master thesis. In the first quarter of 2005, they completed the first Connect6 AI program, which already can beat most players. Then Wu's team allowed his AI program to play itself.
In 2005, Wu's team wrote a paper, presented in the 11th Advances in Computer Games Conference (ACG11), held in Taipei
Taipei
Taipei City is the capital of the Republic of China and the central city of the largest metropolitan area of Taiwan. Situated at the northern tip of the island, Taipei is located on the Tamsui River, and is about 25 km southwest of Keelung, its port on the Pacific Ocean...
, Taiwan
Republic of China
The Republic of China , commonly known as Taiwan , is a unitary sovereign state located in East Asia. Originally based in mainland China, the Republic of China currently governs the island of Taiwan , which forms over 99% of its current territory, as well as Penghu, Kinmen, Matsu and other minor...
, 2005.
In September 2005, ThinkNewIdea Limited built the first Connect6 game server.
On September 20–September 21, 2005, the game was covered by many news media in Taiwan
Taiwan
Taiwan , also known, especially in the past, as Formosa , is the largest island of the same-named island group of East Asia in the western Pacific Ocean and located off the southeastern coast of mainland China. The island forms over 99% of the current territory of the Republic of China following...
.
In 2005, interested people started discussing the organization of a Connect6 website at http://www.connect6.org and supporting a forum for discussion.
The program NCTU6, rewritten by Professor Wu, won gold in the Connect6 tournament at the 11th Computer Olympiad
11th Computer Olympiad
The 11th Computer Olympiad was held in Turin, Italy between May 25 and June 4, 2006 in conjunction with the 14th World Computer Chess Championship and the 5th Computer and Games conference...
.
The First Annual NCTU Cup Connect6 Open Tournament was sponsored by National Chiao Tung University (NCTU) and held in Hsinchu, Taiwan, on July 16th, 2006.
See also
- Game complexityGame complexityCombinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.-Measures of game complexity:...
- RenjuRenjuRenju is the professional variant of Gomoku, a board game originated from Japan in Heian Period. It was named Renju by Japanese journalist Ruikou Kuroiwa on December 6, 1899 in a Japanese newspaper Yorozu chouhou . It is played with black and white stones on a 15x15 intersection Go board...
- IrenseiIrenseiIrensei is an abstract strategy board game. It is traditionally played with Go pieces on a Go board , but any equipment with which Go can be played is also suitable for Irensei....
- ChessChessChess is a two-player board game played on a chessboard, a square-checkered board with 64 squares arranged in an eight-by-eight grid. It is one of the world's most popular games, played by millions of people worldwide at home, in clubs, online, by correspondence, and in tournaments.Each player...
- Games played with Go equipmentGames played with Go equipmentMany games can be played with Go equipment: a supply of white and black stones and a board with 19×19 intersections, other than Go and many more can be played with minor modification....
External links
- The organization for Connect6
- Play Connect6 on Little Golem (turn-based)
- Play Connect6 on igGameCenter (real-time)
- Play Connect6 on wtanaka.com (turn-based)
- Play Connect6 on kevinverhoef.nl