IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Intelligence artificielle Discussion :

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


Sujet :

Intelligence artificielle

  1. #1
    Membre à l'essai
    Inscrit en
    Novembre 2005
    Messages
    27
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 27
    Points : 23
    Points
    23
    Par défaut 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

  2. #2
    Expert éminent sénior

    Avatar de fearyourself
    Homme Profil pro
    Ingénieur Informaticien Senior
    Inscrit en
    Décembre 2005
    Messages
    5 121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur Informaticien Senior
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2005
    Messages : 5 121
    Points : 11 877
    Points
    11 877
    Par défaut 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

  3. #3
    Membre confirmé
    Profil pro
    Directeur Scientifique
    Inscrit en
    Avril 2005
    Messages
    419
    Détails du profil
    Informations personnelles :
    Âge : 51
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Directeur Scientifique

    Informations forums :
    Inscription : Avril 2005
    Messages : 419
    Points : 554
    Points
    554

  4. #4
    Membre à l'essai
    Inscrit en
    Novembre 2005
    Messages
    27
    Détails du profil
    Informations forums :
    Inscription : Novembre 2005
    Messages : 27
    Points : 23
    Points
    23
    Par défaut

    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

  5. #5
    Rédacteur

    Avatar de khayyam90
    Homme Profil pro
    Architecte de système d’information
    Inscrit en
    Janvier 2004
    Messages
    10 369
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 39
    Localisation : France, Bas Rhin (Alsace)

    Informations professionnelles :
    Activité : Architecte de système d’information

    Informations forums :
    Inscription : Janvier 2004
    Messages : 10 369
    Points : 40 164
    Points
    40 164
    Par défaut
    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.

  6. #6
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  7. #7
    Membre chevronné
    Profil pro
    Inscrit en
    Octobre 2005
    Messages
    940
    Détails du profil
    Informations personnelles :
    Âge : 44
    Localisation : France

    Informations forums :
    Inscription : Octobre 2005
    Messages : 940
    Points : 1 816
    Points
    1 816
    Par défaut
    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.

  8. #8
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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é.
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  9. #9
    Modérateur
    Avatar de ToTo13
    Homme Profil pro
    Chercheur en informatique
    Inscrit en
    Janvier 2006
    Messages
    5 793
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Chercheur en informatique
    Secteur : Santé

    Informations forums :
    Inscription : Janvier 2006
    Messages : 5 793
    Points : 9 860
    Points
    9 860
    Par défaut
    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....
    Consignes aux jeunes padawans : une image vaut 1000 mots !
    - Dans ton message respecter tu dois : les règles de rédaction et du forum, prévisualiser, relire et corriger TOUTES les FAUTES (frappes, sms, d'aurteaugrafe, mettre les ACCENTS et les BALISES) => ECRIRE clairement et en Français tu DOIS.
    - Le côté obscur je sens dans le MP => Tous tes MPs je détruirai et la réponse tu n'auras si en privé tu veux que je t'enseigne.(Lis donc ceci)
    - ton poste tu dois marquer quand la bonne réponse tu as obtenu.

  10. #10
    Expert éminent sénior

    Avatar de fearyourself
    Homme Profil pro
    Ingénieur Informaticien Senior
    Inscrit en
    Décembre 2005
    Messages
    5 121
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 43
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur Informaticien Senior
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2005
    Messages : 5 121
    Points : 11 877
    Points
    11 877
    Par défaut
    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....
    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

  11. #11
    Membre régulier Avatar de Mucho
    Inscrit en
    Décembre 2005
    Messages
    221
    Détails du profil
    Informations forums :
    Inscription : Décembre 2005
    Messages : 221
    Points : 109
    Points
    109
    Par défaut
    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.

  12. #12
    Membre éprouvé
    Avatar de Sivrît
    Profil pro
    Inscrit en
    Février 2006
    Messages
    953
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2006
    Messages : 953
    Points : 1 249
    Points
    1 249
    Par défaut
    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.


    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

  13. #13
    Expert éminent sénior
    Avatar de Baptiste Wicht
    Homme Profil pro
    Étudiant
    Inscrit en
    Octobre 2005
    Messages
    7 431
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : Suisse

    Informations professionnelles :
    Activité : Étudiant
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Octobre 2005
    Messages : 7 431
    Points : 21 324
    Points
    21 324
    Par défaut
    Ce site va certainement t'aider, j'ai déja essayé cette IA et c'est tres puissant comme truc

  14. #14
    Membre chevronné
    Profil pro
    Inscrit en
    Octobre 2005
    Messages
    940
    Détails du profil
    Informations personnelles :
    Âge : 44
    Localisation : France

    Informations forums :
    Inscription : Octobre 2005
    Messages : 940
    Points : 1 816
    Points
    1 816
    Par défaut
    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.

  15. #15
    Futur Membre du Club
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Août 2011
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Madagascar

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : Service public

    Informations forums :
    Inscription : Août 2011
    Messages : 9
    Points : 9
    Points
    9
    Par défaut
    Citation Envoyé par Mucho Voir le message
    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

  16. #16
    Membre expérimenté Avatar de davcha
    Profil pro
    Inscrit en
    Avril 2004
    Messages
    1 258
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France

    Informations forums :
    Inscription : Avril 2004
    Messages : 1 258
    Points : 1 539
    Points
    1 539
    Par défaut
    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 ?..

  17. #17
    Membre éclairé
    Avatar de Kirilenko
    Homme Profil pro
    Étudiant
    Inscrit en
    Décembre 2011
    Messages
    234
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : Décembre 2011
    Messages : 234
    Points : 807
    Points
    807
    Par défaut
    Citation Envoyé par Herar01 Voir le message
    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.
    Récursivité en C : épidémie ou hérésie ?

    "Pour être un saint dans l'Église de l'Emacs, il faut vivre une vie pure. Il faut se passer de tout logiciel propriétaire. Heureusement, être célibataire n'est pas obligé. C'est donc bien mieux que les autres églises" - Richard Stallman

  18. #18
    Futur Membre du Club
    Homme Profil pro
    Développeur .NET
    Inscrit en
    Août 2011
    Messages
    9
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Madagascar

    Informations professionnelles :
    Activité : Développeur .NET
    Secteur : Service public

    Informations forums :
    Inscription : Août 2011
    Messages : 9
    Points : 9
    Points
    9
    Par défaut
    Citation Envoyé par Kirilenko Voir le message
    J'ai trouvé un lien qui semble correspondre : ici.
    Merci

Discussions similaires

  1. [Aide] Performances de mon algorithme min-max
    Par moithibault dans le forum Intelligence artificielle
    Réponses: 1
    Dernier message: 16/02/2013, 02h22
  2. Algorithme Min-Max en C appliqué au jeu de Morpion (Tic-Tac-Toe)
    Par crooss dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 02/01/2012, 17h41
  3. Parallélisation de l'algorithme Min Max
    Par on2101 dans le forum Intelligence artificielle
    Réponses: 0
    Dernier message: 08/02/2011, 22h08
  4. [IA] Algorithme jeu PUISSANCE 4
    Par luilui dans le forum Intelligence artificielle
    Réponses: 27
    Dernier message: 03/05/2008, 17h21
  5. Fonction d'évaluation d'un jeu de dames utilisant l'algorithme du min/max
    Par elron8 dans le forum Algorithmes et structures de données
    Réponses: 4
    Dernier message: 31/01/2007, 12h04

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo