MiniMax, Tic-Tac-Toe, nim, P4 et Othello…
Je me suis intéressé à cet algorithme plutôt bien décrit ici (rubrique MinMax et élagage Alpha-Béta) ici aussi
En résumé, quand vient son tour de jouer, un joueur cherche à MAXimiser son coup, pour cela il analyse les coups possibles qui donneront des coups adverses ; coups qu’il faudra MINimiser (puisque c’est adverse), il faudra analyser les coups engendrés des coups engendrés, ces coups étant des coups joueurs il faudra les MAXimiseret ainsi de suite jusqu’aux feuilles de l’arbre. A chaque niveau, on regarde qui gagne, on note + un gain et – une perte….on fait alors remonter ces notes, s'il n'y a pas de gagant on s'enfonce d'un niveau supplémentaire. Dans le cas ou les feuilles ne peuvent être atteintes, arbre trop gros, on évaluera les états à une profondeur donnée en utilisant une fonction d'évaluation pas toujours évidente à définir.
Dans cet arbre (tiré du document cité plus haut), la remontée donne
Pour les jeux dont l'arbre peut être complétement exploré, par exemple Tic-tac-toe, Nim ,etc..., cette
méthode est imparable
(essayez de battre mon morpion !...ou le Nim)
Pour les autres jeux, dont l'arbre ne peut être complétement déployé (P4, Othello, échecs....),
la simple application de la méthode permet d'obtenir un automate qui joue mais qui a du mal à gagner...
Il faut évaluer la situation finale (la pseudo feuille) avec une fonction dont la perfomance fera la différence.
Pour mon Othello cette fonction est:
n:=1*Notes[l,c]+1*(NbBlancs-NbNoirs)+3*NbCoupsPossibles;
(l'ordinateur jouant avec les blancs), c'est pas terrible!...
même en essayant d'ajuster avec les coefficients (1,1,3)
Ici des versions de P4 et Othello en Delphi avec des sources à améliorer
Pour le jeu Puissance4, qui est résolu, le joueur qui commence doit gagner, voila un excellent site avec un programme qui gagne...
