Le jeu
Tic-tac-toe est un jeu très populaire pour deux joueurs, X et O, qui marquent à tour de rôle les espaces dans une grille 3×3. Le joueur qui réussit à placer trois de ses marques dans une rangée verticale, horizontale ou diagonale gagne la partie.,
Propriétés Mathématiques
D’un point de vue mathématique, le jeu a deux propriétés importantes:
1:
Le jeu admet le joueur qui utilise cette stratégie optimale sera de victoire ou de match nul, mais il ne sera pas perdre.
propriété 2:
le nombre de correspondances possibles est relativement faible.
Au début, le premier joueur peut marquer l’un des 9 espaces. Dans le tour suivant, le deuxième joueur peut marquer l’un des 8 espaces restants et ainsi de suite., Le jeu continue jusqu’à ce que tous les espaces soient marqués ou que l’un des joueurs gagne.
Il est alors facile de comprendre que le nombre total de matches différents, est inférieur à:
987….1 = 9! = 362880
c’est un nombre raisonnablement petit pour un ordinateur.
L’algorithme
à partir des propriétés 1 et 2, Il s’ensuit qu’un algorithme pratique et général pour gagner / dessiner le jeu consiste à utiliser la recherche Alpha Beta.,
à chaque tour, l’algorithme évalue toutes les conséquences possibles de chaque coup (possible en raison de la propriété 2) et choisit celle qui assurera une victoire ou un match nul (possible en raison de la propriété 1).
Une IA joueur qui choisit chaque mouvement avec l’alpha bêta de l’algorithme de recherche ne perdra jamais. Pour rendre le jeu plus réaliste, il est agréable d’introduire un facteur stochastique de sorte que chaque fois avec une probabilité prédéfinie, le joueur IA se déplace de manière aléatoire plutôt que de suivre l’algorithme alpha beta., Cela rendra le jeu plus réaliste car il rendra le joueur AI plus humain et parfois il perdra.