Puissance
4 :
Description
du jeu :
Puissance 4 est un jeu où chaque joueur, symbolisé par une couleur, tente de réaliser un alignement de 4 cases. Les 4 directions horizontale, verticale et diagonales sont envisageables.
Le placement de ses pions n’obéit qu’à une seule règle : après avoir choisi une colonne, le pion « tombe » jusqu’à rencontrer la base ou un autre pion.
Différentes stratégies sont possibles, qui influerons directement sur la fonction d’évaluation :
Créer des alignements potentiels, et bloquer ceux des adversaires.
Représentation
des données :
Liste chaînée de listes pour l’arbre, chaque nœud étant représenté par un tableau 7x7 d’octets.
3 valeurs possibles : Vide, Humain, Ordinateur.
D’où : occupation de 392 octets par nœud.
Algorithme :
A chaque tour de l’ordinateur :
A] Construction de l’arbre :
1/ recherche de tous les coups possibles
ð application des règles du jeu
Ici : loi de la gravité :
les pièces « tombent » jusqu’à rencontrer la base ou une autre pièce.
ð
Génération de plusieurs tableaux 7x7 (autant que de coups
possibles)
2/ idem => recherche de toutes les répliques du joueur humain
3/ itérer jusqu’à un niveau ‘n’, ‘n’ pouvant représenter la force de l’ordinateur.
B] Evaluation de l’arbre :
2 méthodes :
- en profondeur
- en largeur
ð
évaluation des feuilles terminales, puis remontée des valeurs
jusqu’au sommet.
Techniques pour optimiser la taille de l’arbre : heuristiques
- évaluation min-max
- min-max + élagage alpha/béta
C] Vérifier si fin de partie => y a-t-il un alignement de 4 cases consécutives de même couleur
Fonction
d’évaluation :
avec min-max
Ordinateur => dans le but de jouer le meilleur coup possible, on cherche à maximiser la valeur retournée par la fonction d’évaluation.
Humain => on estime que le joueur humain joue à chaque tour son meilleur coup et on veut donc minimiser le résultat.
Création de la fonction d’évaluation :
- points de position :
Il s’agit de favoriser la création d’alignements.
On regarde dans chacune des 4 directions (/, \, |, _) qui passent par le coup joué, dans le but de trouver d’autres cases de même couleur déjà jouées. La valuation se fait alors en fonction de la distance du coup joué vers la plus proche case voisine, ainsi que du nombre des cases déjà placées par le joueur dans les 4 directions.
Ex : 2e case : +10 distance à la plus proche : 1 case : +20
3e case : +100
2 cases: +10
4e case : +1000
(victoire)
3 cases : +5
- points de blocage :
Il s’agit là de gêner l’adversaire dans sa tentative de création d’alignements.
Il faut repérer des alignements consécutifs de cases adverses (2 ou 3 cases, car 4 cases impossible : défaite) et jouer à coté.
Il s’agit avant tout d’éviter les cas de victoire de l’adversaire. ( 3 cases alignées)
Ex :
3 cases : +500
2 cases : +50
1 case : +5
Améliorations possibles :
- statistiques sur les coups joués le plus souvent dans certaines situations.
- Apprentissage du jeu de l’adversaire au fur et à mesure de la partie, pour optimiser le choix des coups en fonction des coups précédents.
- Création de bibliothèques de parties, afin de pouvoir s’y référer par analogie.