Atelier Puissance 4

Atelier : Jeu Puissance 4.

Prérequis : développement d'interfaces en Visual Basic, récursivité.

1	Développement de l'interface.

Le premier travail est de développer une interface semblable à celle représentée ci-contre :

Tout est réalisable avec des contrôles Shapes.
Les cases sont numérotées de gauche à droite (comme d'habitude) et de bas en haut (pas comme d'habitude !). C'est pour simplifier la gestion ultérieure des jetons à poser.

2	Quelques structures de données essentielles.

Entre autres, on aura besoin des données suivantes :

Damier(0 to 6, 0 to 5) : représente l'état de chaque case du damier (0 si vide, 1 ou 2 selon quel joueur a posé un jeton).
HauteurColonne(0 to 6) : un tableau d'entier qui nous indique la hauteur atteinte dans une colonne. Au début, chaque valeur est à 0. Lorsqu'on pose un pion dans la i^ème case, on incrémente HauteurColonne(i).
NbPionsPosés : le nombre total de pions posés dans le jeu, cela nous aide à savoir si la partie est fini, sans avoir à parcourir tout le damier.

Toutes ces données, qui représentent la situation du jeu à un moment donnée, doivent être regroupées dans un type défini par l'utilisateur : TJeu. Cela nous servira énormément lors de la réflexion de l'ordinateur.

3	Algorithme princial : faire jouer deux joueurs humains.

Dans la procédure Sub Main d'un module (qui représentera le point d'entrée de votre programme, réalisez l'algorithme suivant (remarque : ce qui doit être à nouveau décomposé en fonction ou procédure est écrit en bleu. Ce qui peut être écrit directement en une ou deux instructions est écrit en noir) :

Afficher Form1
Initialiser le jeu
Répéter
Faire Jouer le joueur courant
Inverser le joueur courant
Jusqu'à ce que la partie soit finie
Afficher le résultat de la partie

Pour compléter ceci, vous devez écrire les procédures et fonctions suivantes :

Initialiser le jeu : initialise le joueur courant (0 ou 1), est-ce que les joueurs sont humains ou ordinateur, vide et efface le damier (dans le cas ou on a joué une partie avant), etc.
Faire jouer (Joueur) :

Si le joueur est humain alors
  Répéter
    Saisir le coup
  Jusqu'à ce que le coup soit valable
Sinon
  le coup = Meilleur coup de l'ordinateur
Fin Si
Effectuer le coup
La partie est finie : renvoie TRUE si le damier est plein ou si un joueur a aligné 4 jetons, FALSE sinon. C'est une des fonctions les plus longues à écrire.

Une variante pour simplifier l'ensemble : la fonction Effectuer décrite ci-dessous renvoie TRUE si le coup joué est un coup gagnant, FALSE sinon.
Afficher le résultat
Effectuer (Joueur, Coup) : pose le jeton dans le damier.

A ce stade, votre programme devrait marcher avec deux joueurs humains.

Rappels sur... Programmer proprement !

Pour que votre programme soit lisible par vous, par le prof et par ceux qui sont susceptible de maintenir vos applications, n'oubliez pas les points suivants, tous fondamentaux :

utilisez des noms de variables explicites, quitte à les rallonger. Par exemple :
- n'utilisez pas : i, j, k ; n , max ;
- utilisez : iColonne, JoueurCourant, NiveauMaximum, CoupSaisi, etc. ;
Indentez le code
Commenter votre code. En général, un commentaire par fonction suffit.
En Visual Basic, l'option de compilation Option Explicit permet d'éliminer 50% des erreurs.

4	Préparer la réflexion de l'ordinateur : adaptation des fonctions déjà écrites.

Pour gérer l'Intelligence Artificielle, l'ordinateur va en fait simuler tous les coups possibles (dans certaines limites...) pour trouver le meilleur coup.

Il va donc utiliser certaines de nos fonctions (effectuer, partie finie), mais en agissant dans des damiers virtuels et non pas dans le damier affiché à l'écran.

On doit donc modifier ces 2 fonctions de façon à ce qu'elles reçoivent en paramètre le damier (type TJeu) dans lequel elles agissent. Par exemple, le paramétrage complet de la fonction Effectuer sera :

Function Effectuer(Damier As TJeu, Joueur As Integer, Coup As Integer, Affiche as Boolean) As Boolean

Damier est le damier, réel ou virtuel, dans lequel on effectue le coup ;
Joueur est le numéro du joueur qui effectue le coup ;
Coup est le coup joué, c'est à dire le numéro de la colonne dans lequel le joueur pose un jeton.
Affiche indique si le coup doit être affiché à l'écran ou pas, c'est à dire si c'est un coup dans le damier réel ou dans un damier virtuel.
Le booléen renvoyé indique (comme expliqué dans l'étape 3) si le coup est gagnant ou pas.

Votre travail est de :

modifier ainsi les deux fonctions ;
adapter les appels de fonction correspondant ;
vérifier que votre programme marche à l'identique.

4	Réflexion de l'ordinateur : écriture de la procédure récursive.

Principes.


C'est au jaune, l'ordinateur, de jouer	Il va simuler ses 7 coups possibles (en jaune foncé ici)	Pour son 1er coup possible (puis pour tous les autres), il va simuler toutes les réponses possibles de l'adversaire (en rouge foncé ici). Pas génialce premier coup, c'est perdu !

Le principe de réflexion de l'ordinateur est le suivant :

Pour chacun de mes 7 coups possibles
  Pour chacune des 7 réponses possible de l'adversaire
    Pour chacune de mes 7 réponses possibles
      ... (autant de fois que le niveau maximum de réflexion)
        Evaluer le damier résultant de ces simulation, lui donner un score

Remarques :

On ne va pas écrire des boucles imbriquées comme écrites ci-dessus, c'est la récursivité qui va réaliser ces imbrications de boucles.
Si l'ordinateur était capable de simuler tous les coups jusqu'à la fin de la partie (donc 42 niveaux dans le cas du puissance 4), il serai imbattable. Sa faiblesse vient du fait qu'on va pouvoir simuler que 7 niveaux environ, pour des raisons de performance (la complexité est exponentielle en fonction du niveau atteint).
Lorsque l'ordinateur simule son coup, ce qui l'intéresse est évidemment le meilleur score (il retient le coup qui lui donne le meilleur avantage). Mais (et c'est difficile à comprendre), lorsqu'il simule le coup de l'adversaire, ce qui l'intéresse est le plus mauvais score : il suppose que l'adversaire joue parfaitement bien. Ce qui l'intéresse est donc ce que l'adversaire peut faire pour le mettre dans la pire situation.

Algorithme à retranscrire.

La fonction MeilleurCoup doit au final revoyer un coup (celui que l'ordinateur va jouer), mais dans les appels récursifs c'est uniquement le score qui nous intéresse. Pour réaliser ces deux choses en même temps, la fonction va en fait renvoyer la structure suivante :

Type TCoup
Score as Integer
Coup as Integer
End Type

L'algorithme est le suivant :

Function MeilleurCoup(ByVal⁽¹⁾ Damier, Joueur, NiveauCourant) As TCoup
  Si le NiveauCourant = le NiveauMaximum alors
    MeilleurCoup.Score = Evaluation⁽²⁾(Damier, Joueur)
  Sinon
    Pour chacun des 7 coups (si le coup est possible)
      Effectuer⁽³⁾ le coup dans le damier virtuel reçu en paramètre
      Si le coup est gagnant⁽⁴⁾ alors
        Score = Maximum si le niveau est pair, Minimum si le niveau est impair.
      Sinon
        Score = MeilleurCoup⁽⁵⁾(Damier, Joueur, NiveauCourant + 1)
      Fin Si
    Fin Pour
    MeilleurCoup.Score = maximum des scores ci-dessus si le niveau est pair (minimum sinon)
    MeilleurCoup.Coup = le coup correspondant
  Fin Si
Fin Function

(1) : Le passage par valeur est extrêmement important : les coups ne sont pas simulés dans le damier principal mais dans des damiers virtuels. Le passage par valeur recopie le damier. Ainsi, la fonction travaillera effectivement sur un deuxième damier, sans interférer sur le damier principal.
(2) : Ici, l'ordinateur a simulé autant de niveau que demandé. Il n'est donc plus question de simuler d'autres coups, mais d'évaluer le score du damier ainsi obtenu et de renvoyer ce score comme résultat de la fonction.
(3) : Attention au joueur qui simule le coup, c'est tantôt l'un tantôt l'autre. Basez-vous sur le niveau : s'il est pair (0, 2, 4...), l'ordinateur simule son propre coup. Sinon, il simule un coup de l'adversaire.
(4) : pendant les simulations, l'ordinateur tombe sur un coup gagnant qui termine la partie. Il est à la fois inutile et impossible de continuer les simulations suiteà ce coup. On renvoie directement un score : le plus mauvais si c'était un coup de l'adversaire, le maximum si c'est un coup de l'ordinateur.
(5) : l'appel récursif est ici. C'est ici qu'on pousse la simulation un niveau plus loin.

Fonction d'évaluation du damier.

Le but de cette fonction est de dire si un damier est à l'avantage du joueur qui a lancé ces simulations, ou non. Il faut même chiffrer cet avantage pour affiner la qualité de la réflexion.

Pour le Puissance 4, je n'ai personellement pas trouvé de fonction d'évaluation du damier satisfaisante. Mon programme renvoie systématiquement 0 !!! Ce qui veut dire qu'au bout des simulations, si aucun joueur n'a virtuellement gagné, l'ordinateur n'en tire aucune information pertinente.

A vous d'essayer de chiffrer la valeur d'un damier et de renvoyer le score correpondant. L'IA y gagnera énormément en efficacité.

Expliquez à l'ordinateur que ce damier
est à l'avantage du rouge !

5	Pour aller plus loin et accélérer l'IA : Application du principe de l'Alpha-Bêta.

L'ordinateur n'est pas très rapide à réfléchir, vous n'arrivez peut-être même pas à 7 niveaux de profondeur dans l'exploration récusive.

Il existe un algorithme efficace pour l'accélérer, sans du tout y perdre en réflexion, c'est l'algorithme de l'alpha-bêta. Cet algorithme sert uniquement à éviter d'explorer certaines branches de la récursivité.

Cliquez sur le shéma pour avoir un tentative d'explication de l'Alpha-Bêta (appliquée au jeu de l'Awalé). Comprendre c'est une chose, le programmer c'en est une autre...

Sébastien PASTORE.