Algorithme Min-Max appliqué au jeu Puissance 4 en C .

**hebmaster** · 15/03/2006, 18h05

Je suis entrain de develloper le jeu puissance 4 en C mais il me reste la partie Intelligence Artificielle.
J'ai entendu parlé de l'algo Mini-Max .il permet de resoudre cette partie IA du jeu .
Est ce que quelqu'un pourait il me donner cette algo ou mieux le code C de cette partie IA du jeu

**fearyourself** · 15/03/2006, 18h07

Envoyé par hebmaster

Je suis entrain de develloper le jeu puissance 4 en C mais il me reste la partie Intelligence Artificielle.
J'ai entendu parlé sur l'algo Mini-Max .il permet de resoudre cette partie IA du jeu .
Est ce que quelqu'un pourait il me donner cette algo ou mieux le code C de cette partie IA du jeu

C'est une question algorithmique et non de C... Effectivement, tu vas le faire en C mais tu ne sais pas encore de quoi il est question alors fait d'abord un tour dans le forum Algorithmes...

Jc

**FrancisSourd** · 15/03/2006, 19h27

http://www.developpez.net/forums/viewtopic.php?t=463878

**hebmaster** · 15/03/2006, 19h33

Envoyé par FrancisSourd

http://www.developpez.net/forums/viewtopic.php?t=463878

je lé deja consulté il ya rien dessus ....
aidez moi svp c urgent je doit rendre le projet prochainement ...il me reste le rapport et tout

**khayyam90** · 15/03/2006, 21h30

bien le bonsoir,

Envoyé par la wikipedia

L'algorithme MinMax est très simple : on visite l'arbre de jeu pour faire remonter à la racine une valeur (appelée « valeur du jeu ») qui est calculée récursivement de la façon suivante :

* MinMax(p) = f(p) si P est une feuille de l’arbre où f est une fonction d’évaluation de la position du jeu

* MinMax(p) = max(MinMax(O1), ..., MinMax(On)) si p est un noeud Joueur avec fils O1, ..., On

* MinMax(p) = min(MinMax(O1), ..., MinMax(On)) si p est un nœud Opposant avec fils O1, ..., On

il faut donc que tu t'inventes une fonction f permettant de calculer la valeur du jeu à un instant donné (selon le nombre de 2-3-4 pions consécutifs par exemple).
L'arbre de jeu correspond aux coups possibles. Les étages de l'arbre sont alternativement pour le joueur 1 ou pour le joueur 2 (appelé Opposant chez la wikipedia).
Donc à chaque mouvement, tu crées un arbre de jeu (ou tu reprends le précédent ... c'est un détail d'implémentation), tu explorer l'arbre récusrivement et tu fais remonter les valeurs avec les 3 formules de la wikipedia.

**ToTo13** · 16/03/2006, 10h15

Bonjour,

pour des jeus aussi simple comme Otelo, puisssance 4, les dames,... la meilleur IA est de calculer toutes les possibilitée par récursivité. En effet la taille tres faible de ces jeux compense la compléxité d'un calcul exaustif des solutions.

**BugFactory** · 16/03/2006, 11h36

Je dits peut-être une bêtise, mais il me semble que au moins dans le cas d'Othello une recherche exhaustive est aussi peu praticable que pour les échecs.

**ToTo13** · 16/03/2006, 11h47

Bonjour,

non au contraire.
Les plus grands joueurs de dames et otelo ont été battu depuis longtemps par une simple recherche exhaustive.
C'est la petite taille du jeu et la simplicité des règles qui rend cela possible. D'autant plus pour otelo, où il faut toujours placer les pions contre un pion déjà existant, ce qui réduit encore le nombre de possibilité.

**ToTo13** · 16/03/2006, 11h51

Petit complément,

aux échecs, l'oridinateur DeepBlue a battu Kasparov il y a deux ou trois ans (3.5 à 2.5), mais il s'agit là d'heuristique et d'un ordi spécialement conçu pour les échecs.
Le seul et UNIQUE jeu où les grands maitres sont toujours invaincu est le GO.
Pourtant, il n'y a pas plus simple au niveau règle, mais.... Stratégie quand tu nous tiens....

**fearyourself** · 16/03/2006, 13h16

Envoyé par ToTo13

Petit complément,

aux échecs, l'oridinateur DeepBlue a battu Kasparov il y a deux ou trois ans (3.5 à 2.5), mais il s'agit là d'heuristique et d'un ordi spécialement conçu pour les échecs.
Le seul et UNIQUE jeu où les grands maitres sont toujours invaincu est le GO.
Pourtant, il n'y a pas plus simple au niveau règle, mais.... Stratégie quand tu nous tiens....

A savoir que ce n'est pas DeepBlue qui a battu Kasparov mais la deuxième version DeeperBlue (mais c'était un nom non officiel, je l'accorde). Kasparov a gagné 4-2 lors du premier match en 1996 et perdu 3.5-2.5 en 1997 contre DeeperBlue.

Par contre, il a été dit que l'ordinateur avait été programmé pour battre Kasparov et non n'importe quel grand maître. Difficile à prouver par contre...

Jc

**Mucho** · 16/03/2006, 14h40

hebmaster :
Il y a des implementations en prolog disponible sur internet :
Par exemple : http://www.montefiore.ulg.ac.be/~van...cification.txt
Tu peux t'en inspirer pour ton programme en C/C++.

Le hors sujet :
Effectivement une recherche exaustive est la surement la meilleure : puisque d'ailleurs la méthode Mini-Max est une recherche exaustive. Même une fois améliorée avec l'alpha bêta, cette amélioration fait uniquement l'économie des possibilité dont on est sûr qu'elles seront obligatoirement moins bonnes que des solutions precedement trouvés. Donc est du même ordre d'idée qu'une recherche exaustive.

**Sivrît** · 16/03/2006, 15h01

Envoyé par ToTo13

Le seul et UNIQUE jeu où les grands maitres sont toujours invaincu est le GO.

Pas unique. Aux dernières nouvelles le Shogi résiste aussi aux ordinateurs et leur bon vieux minmax. Bien que ce soient des échecs ils ont une combinatoire bien plus méchante que notre version, principalement parce que les pièces prises peuvent être remises en jeu n'importe où.

Et au Go il n'est même pas nécessaire d'être grand maître pour ridiculiser la machine.

Edit: si le but est de faire un jeu de puissance4 (pas l'IA la plus imbatable possible), mieux vaut ne pas faire une recherche exhaustive et limiter la profondeur lors du parcourt. Sinon, on a mathématiquement perdu d'avance et c'est même plus la peine de jouer

**Baptiste Wicht** · 16/03/2006, 15h44

Ce site va certainement t'aider, j'ai déja essayé cette IA et c'est tres puissant comme truc

**BugFactory** · 16/03/2006, 17h27

ToTo13 a écrit:

Par contre, il a été dit que l'ordinateur avait été programmé pour battre Kasparov et non n'importe quel grand maître. Difficile à prouver par contre...

J'ai entendu parler de ça. Il semble que Deeper Blue ait eu accès à l'ensemble des parties jouées par Kasparov. En revanche, Kasparov n'a pas eu accès aux parties de Deeper Blue.

**Herar01** · 12/10/2012, 22h31

Envoyé par Mucho

hebmaster :
Il y a des implementations en prolog disponible sur internet :
Par exemple : http://www.montefiore.ulg.ac.be/~van...cification.txt
Tu peux t'en inspirer pour ton programme en C/C++.

Le hors sujet :
Effectivement une recherche exaustive est la surement la meilleure : puisque d'ailleurs la méthode Mini-Max est une recherche exaustive. Même une fois améliorée avec l'alpha bêta, cette amélioration fait uniquement l'économie des possibilité dont on est sûr qu'elles seront obligatoirement moins bonnes que des solutions precedement trouvés. Donc est du même ordre d'idée qu'une recherche exaustive.

Je sais que le sujet date de 2006 mais quelqu'un pourrait m'indiquer où je peux voir le fichier du lien.

Merci