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 :

[IA] Algorithme jeu PUISSANCE 4


Sujet :

Intelligence artificielle

  1. #1
    Membre habitué
    Profil pro
    Inscrit en
    Février 2008
    Messages
    190
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2008
    Messages : 190
    Points : 169
    Points
    169
    Par défaut [IA] Algorithme jeu PUISSANCE 4
    Bonjour,
    Je veux réaliser un jeu PUISSANCE 4 en C++. Pour cela je cherche un algorithme pour avoir des idées pour écrire mon propore algorithme.

    Merci de m'avance

    Lui

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Bonjour,

    A quoi doit servir l'algorithme que tu recherches ? Tu veux simuler un joueur ?
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  3. #3
    Inactif
    Inscrit en
    Février 2008
    Messages
    45
    Détails du profil
    Informations forums :
    Inscription : Février 2008
    Messages : 45
    Points : 38
    Points
    38
    Par défaut
    Bonjour,

    Les idées sont sur cette page !
    __________________
    - Premièrement, il faudra réfléchir;
    - Deuxièment, chercher;
    - Finalement, poser son problème en le décrivant correctement.

  4. #4
    Membre habitué
    Profil pro
    Inscrit en
    Février 2008
    Messages
    190
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2008
    Messages : 190
    Points : 169
    Points
    169
    Par défaut
    Citation Envoyé par paronyme Voir le message
    Bonjour,

    Les idées sont sur cette page !
    Oui, sur cette page, je trouve quelques idées. mais la je cherche la façon de réaliser l'algorithme quand on remplace les joueurs par la machine.

    Merci

  5. #5
    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,

    ce que tu souhaites c'est donc de créer une IA (Intelligence Artificielle).

    Tu peux regarder cette discussion qui te donne certaines pistes.
    Dans le cas du puissance 4 une recherche exhaustive apporte de très bon résultats.
    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.

  6. #6
    Membre habitué
    Profil pro
    Inscrit en
    Février 2008
    Messages
    190
    Détails du profil
    Informations personnelles :
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Février 2008
    Messages : 190
    Points : 169
    Points
    169
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Bonjour,

    ce que tu souhaites c'est donc de créer une IA (Intelligence Artificielle).

    Tu peux regarder cette discussion qui te donne certaines pistes et aussi le forum intelligence artificielle
    Dans le cas du puissance 4 une recherche exhaustive apporte de très bon résultats.
    Merci
    Deja je viens d'aprendre quelques chose : IA https://intelligence-artificielle.developpez.com
    Je vais faire un tour sur ce lien, j'espère que j'aurai ce que je cherche

    Lui

  7. #7
    Alp
    Alp est déconnecté
    Expert éminent sénior

    Avatar de Alp
    Homme Profil pro
    Inscrit en
    Juin 2005
    Messages
    8 575
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : Juin 2005
    Messages : 8 575
    Points : 11 860
    Points
    11 860
    Par défaut
    La technique la plus commune dans une situation telle que celle du Puissance 4 est la suivante :
    imaginons-nous au milieu de la partie, tu as les pions du joueur à telles et telles cases, ceux de l'ordi à telles et telles cases. La technique consiste à lister, à partir de cette situation, toutes les situations qu'entraineraient de jouer tel ou tel coup, et ainsi de suite. Tu obtiendras donc un arbre de "situations" de ton jeu.

    Cette technique est très exposée sur internet. Tu trouveras facilement des docouments.

  8. #8
    Rédacteur

    Avatar de Matthieu Brucher
    Profil pro
    Développeur HPC
    Inscrit en
    Juillet 2005
    Messages
    9 810
    Détails du profil
    Informations personnelles :
    Âge : 42
    Localisation : France, Pyrénées Atlantiques (Aquitaine)

    Informations professionnelles :
    Activité : Développeur HPC
    Secteur : Industrie

    Informations forums :
    Inscription : Juillet 2005
    Messages : 9 810
    Points : 20 970
    Points
    20 970
    Par défaut
    Tu peux regarder ce que fearyourself a fait pour son morpion, c'est le même principe : http://fearyourself.developpez.com/t...l/sdl/morpion/

  9. #9
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2007
    Messages
    52
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Décembre 2007
    Messages : 52
    Points : 66
    Points
    66
    Par défaut
    Citation Envoyé par Alp Voir le message
    toutes les situations qu'entraineraient de jouer tel ou tel coup, et ainsi de suite.
    Et pour un puissance 4 n*m (hauteur*largeur très grand)?

  10. #10
    Alp
    Alp est déconnecté
    Expert éminent sénior

    Avatar de Alp
    Homme Profil pro
    Inscrit en
    Juin 2005
    Messages
    8 575
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : Juin 2005
    Messages : 8 575
    Points : 11 860
    Points
    11 860
    Par défaut
    Dans ce cas, soit tu disposes d'une machine très puissante auquel cas tu peux te permettre d'explorer la plupart des coups possibles, voir tous, soit tu as une machine "normale", et tu dois "trier".

    Ca consiste à s'arrêter à une certaine profondeur -> tu construis l'arbre mais ne va pas au bout de chaque "branche". Par exemple, on peut s'arrêter dès que l'on voit que la situation n'est pas bénéfique du tout. On peut aussi construire toutes les branches jusqu'à une certaine profondeur P. Il s'agit donc de "simuler" tous les P coups suivants possibles. Ensuite, on choisit "le" meilleur (qui n'est pas toujours unique).

    Dans la plupart des jeux de ce genre, quand tu augmentes le niveau de difficulté de l'ordinateur (adversaire), cela augmente souvent son temps de réflexion. S'il applique un algo comme celui décrit plus haut, cela revient "simplement" à augmenter la profondeur. Il est normal que s'il "voit plus loin dans le jeu", il saura mieux prévoir et ainsi jouer un coup bien meilleur pour lui, car il sera meilleur sur le long terme (grâce à la profondeur) et non pas sur le court terme (dans le puissance 4, cela lui ferait par exemple aligner 3 pions, mais l'entrainerait 2 ou 3 coups plus loin à la défaite car il n'avait pas exploré assez en profondeur les situations qu'entraineraient son coup).

  11. #11
    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,

    Citation Envoyé par totaliou Voir le message
    Et pour un puissance 4 n*m (hauteur*largeur très grand)?
    Il faut bien regarder la façon dont tu joues au puissance 4 :
    - tu mets les pions par le haut dans une colonne !!!
    - donc il n'y a que "largeur" possibilité à chaque étape

    Alp te décrit ce que j'appelle la recherche exhaustive qui se représente sous forme d'arbres.
    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.

  12. #12
    Alp
    Alp est déconnecté
    Expert éminent sénior

    Avatar de Alp
    Homme Profil pro
    Inscrit en
    Juin 2005
    Messages
    8 575
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 35
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : Juin 2005
    Messages : 8 575
    Points : 11 860
    Points
    11 860
    Par défaut
    Et on appelle comment la méthode qui s'arrête à une profondeur donnée ? Elle n'est plus exhaustive

  13. #13
    Expert éminent
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    Avril 2003
    Messages
    6 245
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : Avril 2003
    Messages : 6 245
    Points : 8 586
    Points
    8 586
    Par défaut
    Les algos classiques pour l'exploration partielle d'un arbre sont le Min-Max et ses raffinements comme l'Alpha-Beta. Leur efficacité dépend beaucoup de la qualité de la fonction d'évaluation utilisée (la fonction qui affecte un score à une position donnée).

    --
    Jedaï

  14. #14
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2007
    Messages
    52
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Décembre 2007
    Messages : 52
    Points : 66
    Points
    66
    Par défaut
    Citation Envoyé par Alp Voir le message
    Ensuite, on choisit "le" meilleur (qui n'est pas toujours unique).
    Le problème n'est plus le même, dans un cas déterminer le meilleur coup est simple, car on joue celui qui fait gagner la partie en explorant toutes les possibilités. Fonction d'évaluation : Je gagne/je perds

    Dans le deuxième comment détermine t on qu'un coup est meilleur que l'autre? Il faut à chaque instant pouvoir dire qui est le plus avantagé.
    Avez vous une bonne fonction d'évaluation pour le P4?


    Il faut bien regarder la façon dont tu joues au puissance 4 :
    - tu mets les pions par le haut dans une colonne !!!
    - donc il n'y a que "largeur" possibilité à chaque étape
    HA... Tu penses qu'il y a autant de coup possible sur un plateau de 4*1 que 4*4 (L*H) par exemple, et donc que la complexité du problème n'est que fonction de la largeur?

  15. #15
    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,

    alors :

    - 1 - Pour la fonction de recherche du meilleur coup, tu ne regardes pas qu'un seul coup à l'avance, sinon elle ne va pas t'apporter beaucoup d'information. Quand tu joues, tu essaies de calculer plusieurs coups à l'avances, afin de créer une tactique pour gagner. Il faut donc parcourir l'arbre de recherche sur une profondeur N, donc N coups à l'avance.

    - 2 - Pour le nombre de coups possible par tour : tu ne peux mettre un pion qu'en le glissant par le haut du plateau dans une colonne. Donc tu as "Largeur" colonnes possible pour glisser un pion. Tu n'as pas plus de choix possibles à chaque tour.
    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.

  16. #16
    Membre du Club
    Profil pro
    Inscrit en
    Décembre 2007
    Messages
    52
    Détails du profil
    Informations personnelles :
    Âge : 37
    Localisation : France, Paris (Île de France)

    Informations forums :
    Inscription : Décembre 2007
    Messages : 52
    Points : 66
    Points
    66
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    Bonjour,
    - 1 - Pour la fonction de recherche du meilleur coup, tu ne regardes pas qu'un seul coup à l'avance, sinon elle ne va pas t'apporter beaucoup d'information. Quand tu joues, tu essaies de calculer plusieurs coups à l'avances, afin de créer une tactique pour gagner. Il faut donc parcourir l'arbre de recherche sur une profondeur N, donc N coups à l'avance.
    Oui, mais peu importe la profondeur, il faut être capable de Déterminer à un momment qui à l'avantage dans telle ou telle position, sinon comment savoir quelle coup jouer???
    Tu peux essayer de voir 500 coups à l'avance si tu es incapable de choisir les bons, ça ne sert à rien.
    Donc comment fait on pour choisir les bons coup au P4? La tactique on la construit à partir de quoi?

    - 2 - Pour le nombre de coups possible par tour : tu ne peux mettre un pion qu'en le glissant par le haut du plateau dans une colonne. Donc tu as "Largeur" colonnes possible pour glisser un pion. Tu n'as pas plus de choix possibles à chaque tour.
    Oui, et? je n'ai jamais nié cela, mais si tu veux dire par là qu'il ne faut prendre en compte que la largeur pour calculer la taille de l'arbre: non.

  17. #17
    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
    Bonsoir,

    Citation Envoyé par totaliou Voir le message
    Oui, et? je n'ai jamais nié cela, mais si tu veux dire par là qu'il ne faut prendre en compte que la largeur pour calculer la taille de l'arbre: non.
    La hauteur de ton arbre est le nombre de coups que tu vas calculer à l'avance.
    Le nombre de fils pour chaque noeuds de l'arbre est le nombre de possibilité à chaque étape du jeu, soit la largeur.
    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.

  18. #18
    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,

    Citation Envoyé par totaliou Voir le message
    Oui, mais peu importe la profondeur, il faut être capable de Déterminer à un momment qui à l'avantage dans telle ou telle position, sinon comment savoir quelle coup jouer???
    Tu peux essayer de voir 500 coups à l'avance si tu es incapable de choisir les bons, ça ne sert à rien.
    Donc comment fait on pour choisir les bons coup au P4? La tactique on la construit à partir de quoi?
    Là ce que tu souhaites typiquement c'est une fonction d'évaluation du jeu, comme les probabilités de gagner au poker.
    Donc j'aurai tendance compter le nombre de pions alignés.
    Je m'explique :
    - si ton adversaire a quatre pions alignés, tu mets la solution à 0 (ou -infini) car tu as perdu
    - si c'est toi qui en a quatre aligné, solution à l'infini, afin d'être sûr de garder cette solution.
    - Si ni toi ni l'adversaire n'avez gagné, tu comptes le nombre de séries de trois pions alignés pouvant encore être complétés (celle bloquées sont bien sûr à ignorer). Ce nombre de pions alginés doit être multiplié par un fort coefficient (100 par exemple) et additionné à la solution.
    - ensuite tu fais de même avec les séries de deux pions et un coeffficient plus faible (10 par exemple) et de même pour un pion (coef 1).

    C'est une méthode basique qui te donnera une solution correcte si elle est employé dans le cas d'un calcul exhaustif des solutions.

    Mais il doit exister pour chaque type de jeu, une formulation mathématique de la technique (comme pour le rubicube, les dames, ...).
    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.

  19. #19
    doccpu
    Invité(e)
    Par défaut
    Citation Envoyé par ToTo13 Voir le message
    ...Mais il doit exister pour chaque type de jeu, une formulation mathématique de la technique (comme pour le rubicube, les dames, ...).
    Oui ! enfin quelqun qui à compris qu'il de servait a rien de calculer mais il faut refléchir a point !

    imaginons que l'adversaire a 3 pions alligné, il ne sert a rien de calculer les 500 prochains coups il faut le bloquer dessuite !

    d'autres part au echecs il ne sert a rien de calculer les 20 000 suivants (surtout en début de partie) car rien ne garantis que la personne en face ne trouvera pas le moyen de faire une variante du mat de legal coups difficile a contrer au niveau algorithmique car on sacrifie la dame (pièce maitresse apres le roi) au benefice d'un mat en un coup avec une pièce subalterne ensuite !

    Le but etant, plutot, de ne pas prendre de trop mauvaises solutions que l'on peux calculer avec seulement 10 à 20 coups (loi de parreto : 20 % de choix déterminent 80% des actions) le reste des calculs n'etant pas nésséssaires car trop difficile à prédire avec certitude.
    meme les grands joueurs sont difficilement capables de voir avec certitude plus de 80 ou 100 coups. Tout en sachant que tous ne construisent pas d'arbre dans leur tetes. Il connaissent et définissent en cour de partie des "cases stratègiques à prendre" et a tenir et connaissent parfaitement la meilleure utilisation des mouvements de leurs pièces. Par exemple la tour gagne en puissance dans la ligne des pions enemis. Ou encore, les fous servent a maitriser les cavaliers adverses.

    Bref il faut calculer tous les coups oui mais il faut le faire en vérifiant que l'on ne vas pas tomber dans un piège (mat de legal). Le truc etant de vérifier avec des formules spécialisés tout comportement suspect et domageables.

    Ceci etant dit la "brute force" et un des meilleurs atout de l'informatique et ne pas s'en servire serait abérhent
    Dernière modification par doccpu ; 12/03/2008 à 00h10.

  20. #20
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    Citation Envoyé par doccpu Voir le message
    imaginons que l'adversaire a 3 pions alligné, il ne sert a rien de calculer les 500 prochains coups il faut le bloquer dessuite !
    1. Sauf dans le cas ou l'IA peut gagner immédiatement la partie.

    2. S'il y a plusieurs moyens de bloquer l'adversaire, l'IA choisit lequel ?

    etc.
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Algorithme Min-Max appliqué au jeu Puissance 4 en C .
    Par hebmaster dans le forum Intelligence artificielle
    Réponses: 17
    Dernier message: 29/10/2012, 08h33
  2. [DC] Jeu Puissance 4
    Par lkryss dans le forum Diagrammes de Classes
    Réponses: 6
    Dernier message: 15/01/2008, 19h22
  3. Jeu Puissance 4 en 3D
    Par macbang dans le forum Fortran
    Réponses: 0
    Dernier message: 05/12/2007, 01h21
  4. Réponses: 1
    Dernier message: 13/05/2007, 14h54

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