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

Version imprimable

15/03/2006, 17h05
hebmaster

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

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
15/03/2006, 17h07
fearyourself

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

Citation:

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
15/03/2006, 18h27
FrancisSourd

http://www.developpez.net/forums/viewtopic.php?t=463878
15/03/2006, 18h33
hebmaster

Citation:

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
15/03/2006, 20h30
khayyam90

bien le bonsoir,

Citation:

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.
16/03/2006, 09h15
ToTo13

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.
16/03/2006, 10h36
BugFactory

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.
16/03/2006, 10h47
ToTo13

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é.
16/03/2006, 10h51
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.... :wink:
16/03/2006, 12h16
fearyourself

Citation:

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.... :wink:

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
16/03/2006, 13h40
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.
16/03/2006, 14h01
Sivrît

Citation:

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. :wink:

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 :cry:
16/03/2006, 14h44
Baptiste Wicht

Ce site va certainement t'aider, j'ai déja essayé cette IA et c'est tres puissant comme truc
16/03/2006, 16h27
BugFactory

ToTo13 a écrit:

Citation:

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.
12/10/2012, 21h31
Herar01

Citation:

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
17/10/2012, 18h54
davcha

Un minmax sur un truc simple comme p4, c'est possible ? On se retrouve pas face à un problème bien connu de la théorie des jeux ?..
28/10/2012, 18h11
Kirilenko

Citation:

Envoyé par Herar01

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

J'ai trouvé un lien qui semble correspondre : ici.
29/10/2012, 07h33
Herar01

Citation:

Envoyé par Kirilenko

J'ai trouvé un lien qui semble correspondre : ici.

Merci :ccool: