La théorie de l'algorithme Min-Max.
- On crée un arbre dont chaques branches représentent un coup joué.
- Ensuite si à la suite de ce coup, il ne se passe rien, je donne une note de 0 au noeud. Si celui-ci me fait gagner la partie je donne une note de 10000. Enfin si celui-ci me fait perdre je donne une note de -10000.
- Je parcours alors l'arbre (en fait je le remonte puisque l'algo est récursif) en gardant la branche la mieux notée.
- Théoriquement, l'IA jouerait de facon optimal, et serait IMBATTABLE.
Malheureusement, le nombre de combinaison possible augmente exponentiellement. Construire un arbre de jeu entier est pour l'instant impossible. C'est pourquoi on est obligé de stopper l'algo à une certaine profondeur.
De plus, on peux simplifier l'algo à l'aide de la méthode Alpha-Beta. Celle-ci consiste à ne pas parcourir toutes les branches de l'arbre. En effet, si un score est trop élevé ou trop faible, certaines branches ne valent pas le coup d'être explorées.
J'ai ajouté quelques optimisations propre à mon application.
Par exemple, je donne aussi un score lorsque je trouve des formations incompletes:
- 4 pions : 10000 points
- 3 pions : 100 points
- 2 pions : 1 points
Ainsi, j'ai plus de précision lors du choix de la branche de l'arbre.
Enfin, je ne parcours une branche que si c'est nécessaire. Je m'explique, si je n'ai pas le droit de poser dans une colonne (en vérifiant le "tableau d'interdit" que j'expliquerai après), alors le noeud et tout ses fils ne seront pas parcourus.
L'implementation de mon IA.
L'IA fonctionne comme ceci:
- Tout d'abord on verifi si on peux jouer un coup qui nous fait immédiatement gagner.
- Ensuite on verifi si on peux jouer un coup qui nous empêcherait de perdre sur le champ.
- Si on est dans aucun des cas ci-dessus, alors on inspecte le tableau des colonnes interdites.
Ce tableau est crée en même temps que les deux verifications précédentes. C'est simple, si lors de ma vérification je détecte que la position d'un pion entrainerait obligatoirement la défaite au coup suivant (deux coup apres en fait), je l'indique dans ce tableau. L'IA n'a alors plus le droit de poser un pion dans cette colonne, jusqu'à ce qu'un changement soit fait. De même, j'interdit de placer un pion dans une colonne, si le placement détruit une formation (par exemple trois de mes pions alignés). Ce tableau contient alors un état par colonne.
Les 3 états sont:
* AUCUN : on peut poser dans cette colonne.
* PLACER : poser dans cette colonne détruit une de nos formation.
* EMPECHER : poser dans cette colonne ferait gagner l'adversaire.
Pour en revenir à la méthode, j'inspecte le tableau d'interdit de la facon suivante:
- Si il reste des colonnes ou je peux placer, je lance l'aglorithme Min-Max (arbre des jeux expliqué ci-dessus).
- Si il ne reste plus de place, alors je sacrifie une de mes formations (c'est ca ou donner la victoire à l'adversaire), et je place un de mes pions dans une colonne (marqué PLACER)
- Si il ne reste plus de colonne à placer, et aucune de ses formations à sacrifier, alors la partie est perdu. On place (à contre coeur) le pions qui fera gagner l'adversaire.
Si vous voyez des améliorations à apporter, n'hésitez pas à me contacter.