# Tic-tac-toe quantique

Le tic-tac-toe quantique est une « généralisation quantique » du jeu tic-tac-toe, au cours duquel les coups des joueurs sont des « superpositions » de coups du jeu classique. Le jeu a été inventé par Allan Goff et Novatia Labs. Selon l’auteur, le jeu permet d’introduire la notion de mécanique quantique sans la nécessité d’utiliser des outils mathématiques complexes.

## Principe

Les règles du tic-tac-toe quantique ne sont pas particulièrement complexes, mais introduisent des mécanismes peu familiers des joueurs ; leur apprentissage représente donc un défi plus grand que celui de la plupart des jeux conventionnels. Comprendre sur quelles bases le jeu a été inventé peut aider à les assimiler.
Le but premier, avec l’invention du tic-tac-toe quantique était d’explorer la possibilité d’avoir un coup placé potentiellement à deux endroits. En physique classique, un objet ne peut être qu’à un endroit à un moment donné, tandis qu’en physique quantique, les mathématiques utilisées pour décrire un système quantique introduisent la possibilité pour certaines particules quantiques d’être dans un état indéfini, avant que celui-ci ne soit déterminé par une mesure.
Les chercheurs ayant inventé le tic-tac-toe quantique travaillaient sur les systèmes quantiques abstraits, des systèmes formels dont les axiomes fondateurs n’incluent que quelques axiomes de la mécanique quantique. Le tic-tac-toe quantique est devenu le système quantique abstrait le plus minutieusement étudié, et offrait de surcroit de nouvelles pistes de recherche intéressantes. Il s’est également révélé être un jeu engageant à bonne valeur pédagogique pour les étudiants.
Les règles du tic-tac-toe quantique tentent de refléter plusieurs phénomènes des systèmes quantiques :
* La superposition, qui est la capacité d’une particule quantique à être dans un état indéfini ;
* L’intrication, qui est un phénomène de corrélations qui ne sont pas impliquées par la causalité entre les différentes parties d’un système quantique ;
* La réduction, qui implique qu’après une mesure, un système quantique voit son état réduit à celui qui a été mesuré.

## Règles

Les règles du tic-tac-toe quantique découlent des trois phénomènes expliqués ci-dessus en modifiant la règle du tic-tac-toe classique : le nombre d’états possibles pour un coup. Des règles supplémentaires permettent de spécifier quand et comment ces coups sont « réduits » pour aboutir aux emplacements définis classiques du tic-tac-toe.
À chaque coup, le joueur marque deux cases distinctes avec sa lettre (X ou O) au lieu d’une, et chaque marque porte en indice le numéro du coup (de 1, jusqu’à éventuellement 9). Les paires de marques ainsi formées portent le nom de « marques fantômes » (spooky marks). Si X joue en premier, les indices des marques de X sont impairs, et ceux de O sont pairs. Les deux cases reliées par une paire de « marques fantômes » sont dites « intriquées ». Durant la partie, il peut y avoir jusqu’à huit « marques fantômes » dans la même case, si celle-ci est « intriquée » avec les huit autres cases.
Le phénomène de « réduction » apparaît dès lors qu’un cycle d’intrication est créé, provoquant une « mesure ». Celle-ci est décidée par le joueur qui n’est pas responsable de la création du cycle (s’il y a une décision à prendre). Par exemple, si au début de la partie le premier joueur a décidé de relier deux cases, et que le second relie les mêmes cases, ce dernier crée un cycle et c’est au premier joueur de choisir laquelle des deux cases il souhaite. Toutes les « marques fantômes » appartenant au cycle ou qui y sont reliées sont ainsi réduites en des marques définitives. Les cases qui ont été marquées définitivement ne peuvent plus accueillir de nouvelles « marques fantômes ».
Le premier joueur qui parvient à obtenir un alignement (horizontal, vertical ou diagonal) de trois marques définitives gagne la partie. Puisqu’il est possible qu’une réduction aboutisse à plusieurs alignements, il y a plusieurs configurations finales possibles :
* Un des joueurs a un alignement et l’autre non, il marque donc un point ;
* Un des joueurs a deux alignements, il marque donc deux points ;
* Chaque joueur a un alignement, celui dont l’alignement possède l’indice maximal le moins élevé marque un point, l’autre marque un demi point.

## Stratégie
### Solution exacte

Lors de l’International Conference on Advanced Computing and Communication Technologies de 2011, les chercheurs japonais Takumi Ishizeki et Akihiro Matsuura ont présenté leurs travaux sur la résolution informatique du Tic-tac-toe quantique. Leurs conclusions sont que le premier joueur suivant une stratégie parfaite ne peut pas obtenir une victoire complète (1 vs 0) ou (2 vs 0), mais peut obtenir une demi-victoire (1 vs ½) au bout de neuf coups en commençant à jouer dans deux coins opposés d’une diagonale.
En modifiant la règle du joueur qui choisit la mesure lors de la réduction (ie. celui qui crée le cycle d’intrication choisit la mesure), ils concluent que le premier joueur a la possibilité d’une victoire complète en commençant par deux coins horizontalement ou verticalement alignés, et d’une demi-victoire dans la plupart des autres configurations de départ. Ils en déduisent que la règle donnant au joueur ne formant pas le cycle le choix de la mesure permet de contrebalancer efficacement l’avantage donné au joueur qui commence.