Connect6

Connect6 ( chinois :六子棋; pinyin : liùzǐqí; chinois :連六棋; japonais :六目並べ; coréen : 육목 ) introduit en 2003 par le professeur I-Chen Wu du Département d'informatique et d'ingénierie de l'information de l'Université nationale Chiao Tung à Taiwan , est un jeu de stratégie à deux joueurs similaire à Gomoku .

Deux joueurs, Noir et Blanc, placent alternativement deux pierres de leur couleur, respectivement noire et blanche, sur des intersections vides d'un plateau de jeu de Go , sauf que Noir (le premier joueur) ne place qu'une seule pierre pour le premier coup. Le premier à placer six pierres ou plus d'affilée (horizontalement, verticalement ou en diagonale) remporte la partie.

Les règles de Connect6 sont très simples et similaires au jeu traditionnel de Gomoku :

• Joueurs et pierres : Il y a deux joueurs. Les Noirs jouent en premier, puis les Blancs. Chaque joueur joue avec une couleur de pierres appropriée, comme au Go et au Gomoku .
• Plateau de jeu : Connect6 se joue sur un plateau carré composé de lignes orthogonales, chaque intersection pouvant contenir une pierre. En théorie, le plateau de jeu peut avoir n'importe quelle taille finie à partir de 1×1 (entiers uniquement), ou il peut être de taille infinie. Cependant, les plateaux trop petits peuvent manquer de stratégie (les plateaux plus petits que 6×6 sont automatiquement nuls), et les plateaux extrêmement grands ou infinis sont peu utiles en pratique. Les plateaux de Go de 19×19 peuvent être les plus pratiques. Pour une partie plus longue et plus difficile, une autre taille suggérée est 59×59, ou neuf plateaux de Go disposés dans un carré plus grand (en utilisant les lignes de jonction entre les plateaux comme lignes de grille supplémentaires).
• Déroulement du jeu : les Noirs jouent en premier et posent une pierre noire sur une intersection. Ensuite, les Blancs et les Noirs jouent à tour de rôle et posent deux pierres sur deux cases différentes inoccupées à chaque tour.
• Gagnant : Le joueur qui est le premier à obtenir six pierres ou plus d'affilée (horizontalement, verticalement ou en diagonale) gagne. (Il s'agit d'un écart par rapport au Gomoku , où il doit y en avoir exactement cinq d'affilée.)

Selon le professeur Wu, le handicap du fait que les Noirs ne peuvent jouer qu'une seule pierre au premier tour signifie que le jeu est relativement équitable ; contrairement à des jeux similaires tels que Gomoku et Connect Four , qui se sont avérés donner un grand avantage au premier joueur, il est possible qu'aucune compensation supplémentaire ne soit nécessaire pour rendre le jeu équitable.

En principe, même certains jeux complexes ne sont pas équitables : soit le premier joueur, soit le deuxième joueur a un avantage. (Il a été mathématiquement prouvé que des jeux comme le Gomoku donnent un avantage à l'un ou l'autre joueur ; les jeux complexes comme les échecs sont généralement trop compliqués pour être analysés complètement.) Herik, Uiterwijk et Rijswijck donnent une définition informelle de l'équité (Herik, Uiterwijk et Rijswijck, 2002) comme suit : une partie est considérée comme équitable s'il s'agit d'un match nul et que les deux joueurs ont à peu près les mêmes chances de faire des erreurs. À partir de là, on soutient que Connect6 est équitable dans les sens suivants :

• Chaque joueur a toujours une pierre de plus que l'autre après avoir effectué chaque coup.
• Pendant environ mille modèles d'ouverture, le professeur Wu a laissé le programme d'IA écrit par son équipe jouer contre lui-même, et le résultat semble montrer que le jeu ne favorise aucun des deux pour ces modèles. Notez que le programme d'IA peut battre la plupart des joueurs occasionnels, mais cela n'implique pas nécessairement que sa stratégie soit strictement optimale.
• Selon le professeur Wu, l'échappée initiale (où les Blancs jouent loin de la pierre noire initiale) est une perte garantie pour les Blancs. Le principe est que les Noirs peuvent essentiellement ignorer le coup des Blancs, ce qui donne aux Noirs une avance de trois pierres qui est insurmontable.

Toutefois, ces preuves ne sont pas concluantes.

Si Connect6 utilise un plateau infini, les complexités de l'espace d'état et de l'arbre de jeu sont également infinies. Supposons plutôt qu'un plateau de Go soit utilisé. Les complexités de l'arbre de jeu sont toujours bien plus élevées que celles de Gomoku et Renju , car beaucoup plus de coups sont possibles en plaçant deux pierres qu'une seule — en particulier, n ( n −1)/2 coups sont possibles, où n est le nombre d'espaces inoccupés avant un coup. Cependant, la complexité de l'espace d'état reste largement inchangée, car toute position légale dans un jeu sera également légale dans l'autre. Sur la base de la norme de Herik, Huntjens et Rijswijck, la complexité de l'espace d'état de Connect(19,19,6,2,1) est de 10 ¹⁷² , la même que celle de Go ou de Gomoku. Si un plateau plus grand est utilisé, la complexité est bien plus élevée, car le nombre de coups augmente de manière exponentielle avec la taille du plateau ; elle devrait toujours être la même que pour les deux autres jeux sur un plateau de même taille.

Français Maintenant, étudions la complexité de l'arbre de jeu . Supposons que la durée moyenne de la partie soit toujours de 30, la même que l'estimation pour Gomoku (Allis 1994). Ensuite, le nombre de grilles choisies pour poser une pierre est d'environ 300, et le nombre de choix d'un coup est d'environ 45 000. Ainsi, la complexité de l'arbre de jeu est d'environ ≈ 10 ¹⁴⁰ , bien plus élevée que celle de Gomoku. Alternativement, si l'on suppose que le nombre total de pierres posées (au lieu du nombre de coups) est le même que celui de Gomoku, cela nous laisse avec une durée moyenne de partie d'environ 15. Alors la complexité de l'arbre de jeu est d'environ ≈ 10 ⁷⁰ , le même ordre de grandeur que celui de Gomoku donné par Allis 1994. Là encore, si un plateau plus grand est utilisé, cette complexité devient beaucoup plus élevée.

Le courant principal du développement actuel de Connect6 a commencé avec la présentation du professeur I-Chen Wu. Comme les règles du jeu sont simples, on pense que plusieurs personnes y ont pensé plus tôt. Par exemple, l'une d'entre elles affirme que l'idée du jeu (nom chinois « 六子棋 ») est apparue sur Internet vers 1999, d'abord sur le site BBS chinois populaire bbs.tsinghua.edu.cn, puis sur le site BBS chinois populaire à l'étranger bbs.mit.edu (aujourd'hui www.mitbbs.com). Cependant, aucun enregistrement du jeu Connect6 n'existait ou n'était discuté avant que le professeur Wu ne présente le jeu Connect6. L'historique depuis le professeur Wu est le suivant.

Un jour de l'été 2003, le professeur Wu a eu l'idée de ce jeu alors qu'il jouait avec sa fille. Il a commencé à réfléchir au potentiel de popularité du jeu et a commencé à l'étudier. Pour être populaire, a-t-il estimé, son jeu devait être équitable et complexe. Son premier plan a donc été de faire jouer le jeu à un programme informatique pour voir à quel point il était équitable et complexe.

Au printemps 2004, un étudiant en master du professeur Wu, Dei-Yen Huang, a rejoint le projet de Wu dans le cadre de sa thèse de master . Au premier trimestre 2005, ils ont terminé le premier programme d'IA Connect6, qui peut déjà battre la plupart des joueurs. L'équipe de Wu a ensuite permis à son programme d'IA de jouer tout seul.

En 2005, l'équipe de Wu a rédigé un article, présenté lors de la 11e conférence Advances in Computer Games (ACG11), qui s'est tenue à Taipei , Taiwan , en 2005.

En septembre 2005, ThinkNewIdea Limited a construit le premier serveur de jeu Connect6.

Les 20 et 21 septembre 2005, le match a été couvert par de nombreux médias à Taïwan .

Le programme NCTU6, réécrit par le professeur Wu, a remporté l'or au tournoi Connect6 lors de la 11e Olympiade informatique .