Soutenez-nous
Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 18 sur 18
  1. #1
    Invité régulier
    Inscrit en
    novembre 2005
    Messages
    27
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 27
    Points : 8
    Points
    8

    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
    Rédacteur/Modérateur

    Avatar de fearyourself
    Homme Profil pro
    Ingénieur Informaticien Senior
    Inscrit en
    décembre 2005
    Messages
    5 001
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

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

    Informations forums :
    Inscription : décembre 2005
    Messages : 5 001
    Points : 9 907
    Points
    9 907

    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 éprouvé

    Profil pro
    Inscrit en
    avril 2005
    Messages
    417
    Détails du profil
    Informations personnelles :
    Âge : 41
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : avril 2005
    Messages : 417
    Points : 474
    Points
    474

    Par défaut

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

  4. #4
    Invité régulier
    Inscrit en
    novembre 2005
    Messages
    27
    Détails du profil
    Informations forums :
    Inscription : novembre 2005
    Messages : 27
    Points : 8
    Points
    8

    Par défaut

    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

  5. #5
    Responsable Portail

    Avatar de khayyam90
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    janvier 2004
    Messages
    9 842
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 29
    Localisation : France, Saône et Loire (Bourgogne)

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : janvier 2004
    Messages : 9 842
    Points : 39 767
    Points
    39 767

    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.
    Responsable du Portail Developpez.
    Mes tutoriels Algo, Web, C++, PHP - Mon CV

  6. #6
    Modérateur
    Avatar de ToTo13
    Homme Profil pro Guillaume
    Ingénieur de Recherche
    Inscrit en
    janvier 2006
    Messages
    5 086
    Détails du profil
    Informations personnelles :
    Nom : Homme Guillaume
    Âge : 35
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Santé

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 086
    Points : 7 871
    Points
    7 871

    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é
    Inscrit en
    octobre 2005
    Messages
    691
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : octobre 2005
    Messages : 691
    Points : 754
    Points
    754

    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 Guillaume
    Ingénieur de Recherche
    Inscrit en
    janvier 2006
    Messages
    5 086
    Détails du profil
    Informations personnelles :
    Nom : Homme Guillaume
    Âge : 35
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Santé

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 086
    Points : 7 871
    Points
    7 871

    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 Guillaume
    Ingénieur de Recherche
    Inscrit en
    janvier 2006
    Messages
    5 086
    Détails du profil
    Informations personnelles :
    Nom : Homme Guillaume
    Âge : 35
    Localisation : Etats-Unis

    Informations professionnelles :
    Activité : Ingénieur de Recherche
    Secteur : Santé

    Informations forums :
    Inscription : janvier 2006
    Messages : 5 086
    Points : 7 871
    Points
    7 871

    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
    Rédacteur/Modérateur

    Avatar de fearyourself
    Homme Profil pro
    Ingénieur Informaticien Senior
    Inscrit en
    décembre 2005
    Messages
    5 001
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 33
    Localisation : France, Paris (Île de France)

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

    Informations forums :
    Inscription : décembre 2005
    Messages : 5 001
    Points : 9 907
    Points
    9 907

    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 : 73
    Points
    73

    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 Expert
    Avatar de Sivrît
    Profil pro
    Inscrit en
    février 2006
    Messages
    953
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : février 2006
    Messages : 953
    Points : 1 137
    Points
    1 137

    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 Confirmé Sénior
    Avatar de Baptiste Wicht
    Homme Profil pro Baptiste Wicht
    Étudiant
    Inscrit en
    octobre 2005
    Messages
    7 433
    Détails du profil
    Informations personnelles :
    Nom : Homme Baptiste Wicht
    Âge : 26
    Localisation : Suisse

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

    Informations forums :
    Inscription : octobre 2005
    Messages : 7 433
    Points : 19 363
    Points
    19 363

    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é
    Inscrit en
    octobre 2005
    Messages
    691
    Détails du profil
    Informations personnelles :
    Âge : 34

    Informations forums :
    Inscription : octobre 2005
    Messages : 691
    Points : 754
    Points
    754

    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
    Invité de passage
    Homme Profil pro
    Développeur .NET
    Inscrit en
    août 2011
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme

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

    Informations forums :
    Inscription : août 2011
    Messages : 8
    Points : 3
    Points
    3

    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 Expert Avatar de davcha
    Profil pro
    Inscrit en
    avril 2004
    Messages
    1 253
    Détails du profil
    Informations personnelles :
    Âge : 32
    Localisation : France

    Informations forums :
    Inscription : avril 2004
    Messages : 1 253
    Points : 1 285
    Points
    1 285

    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 chevronné
    Avatar de Kirilenko
    Homme Profil pro Lucas Pesenti
    Étudiant
    Inscrit en
    décembre 2011
    Messages
    234
    Détails du profil
    Informations personnelles :
    Nom : Homme Lucas Pesenti
    Âge : 17
    Localisation : France, Vaucluse (Provence Alpes Côte d'Azur)

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

    Informations forums :
    Inscription : décembre 2011
    Messages : 234
    Points : 766
    Points
    766

    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
    Invité de passage
    Homme Profil pro
    Développeur .NET
    Inscrit en
    août 2011
    Messages
    8
    Détails du profil
    Informations personnelles :
    Sexe : Homme

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

    Informations forums :
    Inscription : août 2011
    Messages : 8
    Points : 3
    Points
    3

    Par défaut

    Citation Envoyé par Kirilenko Voir le message
    J'ai trouvé un lien qui semble correspondre : ici.
    Merci

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •