Partage
  • Partager sur Facebook
  • Partager sur Twitter

Utiliser la méthode de MonteCarlo ?

    9 mai 2020 à 16:53:27

    Bonjour,  

    (Mon problème est purement mathématique et algorithmique, pas informatique ;))
    Je veux créer une IA de Puissance 4, pour cela, je voudrais utiliser la méthode de MonteCarlo pour mon IA. (Juste MonteCarlo, pas UCT)

    De ce que je sais (et comprend), la méthode de MonteCarlo, consiste à jouer plein de partie au hasard (ou quasiment au hasard) et à en tirer des conclusions sur le potentiel moyen de chaque coup.

    Donc ma 1er approche pour mon IA a été la suivante:
    Pour évaluer le "potentiel" d'un coup C, pour une partie P1 données: on simule la fait qu'on ait joué ce coup C, ce qui donne une partie P2. ET à partie de cette partie, on joue aléatoirement plein de partie, et on en tire des conclusion sur le potentiel du coup C.

    Mon problème est: Quelle formule dois-je utiliser pour calculer le potentiel de ce coup ?

    1) Nombre de victoire / Nombre de parties simulées ?

    2) Nombre de victoire / Nombre de défaite ?

    3) Score Moyen /  Nombre de parties simulées ?   (Score: -1 = perdu | 0 = match nul | 1 = Gagné )

    4) Nombre de tour moyen pour gagner / Nombre de tour moyen pour gagner ?

    5) Une formule qui combinerai efficacement la proportion de victoire, et le nombre de coup moyen qu'il faut pour l'obtenir ? (Par exemple, je pense qu'un victoire obtenue après 20, à moins de valeur qu'un victoire obtenue après 10, et est aussi plus incertaine, car le nombre de possibilité augmente....)

    Etc....

    En y réfléchissant bien, je me suis aussi demander, si au lieu de jouer N parties pour évaluer chaque coup (Ce qui fait 7*N parties en tout, car le puissance 4 a une largeur de 7 cases), on pouvait pas jouer seulement N parties, et en tirer des conclusions pour l'ensemble des 7 coups à évaluer....

    Par exemple, à partir d'une partie donnée, je veux savoir quel coup à le meilleur potentiel. Donc je jouerais N parties, puis à la fin de chacune, je regarderait combien de fois à était joué chaque coup que je cherche à évaluer, combien de fois en le jouant, on a gagné, ou on a perdu, etc...

    Si cette approche était valide, elle serait 7 fois plus rapide que la précédente, mais me ramènerais aussi au problème précédent: 

    Quelle formule dois-je utiliser pour tirer le maximum d'information de toute ces fin de parties, pour avoir une IA la plus efficace possible ??

    J’espère vraiment qu'il y a un moyen d'y répondre mathématiquement, sans que j'ai besoins d'expérimenter toutes ces combinaisons ^^'

    Merci d'avance à tout ceux qui auront le courage de ce plonger dans mon épineux problème :D

    -
    Edité par MrSiuol 9 mai 2020 à 22:57:59

    • Partager sur Facebook
    • Partager sur Twitter
      10 mai 2020 à 19:33:30

      Personne ne peut m'aider ? :(

      (Peut-etre que la question n'est pas assez bien formulée ? Ou que je ferais mieux de la poser dans le forum info ? :euh:)

      • Partager sur Facebook
      • Partager sur Twitter
        10 mai 2020 à 23:58:46

        Tu envisages :

        1) Nombre de victoire / Nombre de parties simulées ?

        2) Nombre de victoire / Nombre de défaite ?

        3) Score Moyen /  Nombre de parties simulées ?   (Score: -1 = perdu | 0 = match nul | 1 = Gagné )

        4) Nombre de tour moyen pour gagner / Nombre de tour moyen pour gagner ?

        Les 3 premières propositions sont strictement identiques.

        La 4ème n'a pas de sens.  

        Tu comprends maintenant pourquoi tu n'as pas eu de réponse ?

        • Partager sur Facebook
        • Partager sur Twitter
          11 mai 2020 à 2:37:46

          D'accord, merci beaucoup de m'avoir répondu :D

          Mais comment as tu vu que les 3 premières propositions étaient les même ?

          Nombre de victoire / Nombre de parties simulées = Nombre de victoire / (Nombre de victoire + match nul + défaites) =/= Nombre de victoire / Nombre de défaite

          Et: Score Moyen /  Nombre de parties simulées = (Nombre de victoire - Nombre de défaite) /  (Nombre de victoire + match nul + défaites) =/= Nombre de victoire / Nombre de défaite

          Donc mathématiquement, du moins, elles me semblent différentes, comment sais-tu quelles auraient le même résultat ? :euh:
          (Ou alors j'ai peut-être loupé quelque chose....? ^^')

          D'accords, la 4) est pas super, mais selon toi, est-ce qu'utiliser une évaluation que prenne aussi en compte, en plus de la proportion de victoire, le nombre de tour que la simulation à mis pour gagner ou pour perdre, ne pourrait pas améliorer l'IA ?

          Parce qu'intuitivement, j'ai envie de penser qu'une victoire au bout de 4 tour, à plus de valeur qu'un victoire au bout de 20, et qu'elle est plus "sur", car il y a beaucoup moins de "chemins" pour arriver à une victoire en 4 tours, qu'à une victoire en 20 tours, non ? ^^'

          (Après, je sais bien que l'intuition est souvent fausse en statistique.....)

          Et pour ma 2e idée, qui est de ne pas jouer le premier coup, et de tirer des conclusion sur l'ensemble des coup jouable de la partie, à partir des position finale: est-ce que cette approche est aussi équivalente à la 1er ?
          (Vu que dans cette approche, je ne prend plus en compte l'ordre des 1er coups, est-ce que cela peut changer des choses ?)

          • Partager sur Facebook
          • Partager sur Twitter
            11 mai 2020 à 10:42:55

            La comme ça, à ta place je confronterai tes différentes idées les unes contre les autres pour voir laquelle à le meilleur potentiel.

            Sur le principe, tes 3 premières propositions sont quasi identiques. Elles ne le sont pas complètement à cause des cas de matchs nuls, mais tout de même, elles sont pas loin d’être identiques.

            Ensuite, Pour ton histoire de victoire en 4 coups au lieu de 20, il faut relativiser.

            Imaginons un cas ou tu as 3 jetons d'une couleur à l'horizontal, dont 1 des jetons contre le bord. Pour le bloquer, c'est très simple, 1 jeton de l'autre couleur et c'est fini. Alors que si tu as 3 jetons d'une même couleur à l'horizontal, mais que l'ennemi peut jouer de chaque côté, il ne pourra jamais bloquer les 2 coups possibles, donc c'est victoire assuré.

            Personnellement, j’essaierais d'identifier un lot de cas où l'adversaire n'a aucune chance de gagner. C'est à dire les configurations à 2 coups possibles pour gagner, donc non contrable. Et je ferai en sorte que le bot essai d'arriver à ces combinaisons.

            En gros, pour moi le cas possible de "4 jetons empilés tout bêtement" n'a pas de valeur. Car sauf si tu tombes contre un mec qui connait pas les règles du jeu, ça gagnera jamais, et pourtant, ce cas fera augmenter ton score de réussite de l'IA car ca reste un cas de victoire potentiel. Donc pour moi c'est une configuration qui ne doit pas être considéré comme une config à atteindre pour ton bot. En gros, le score serait plutot la probabilité que j'arrive à une config d'échec et mat en gros.

            • Partager sur Facebook
            • Partager sur Twitter

            Utiliser la méthode de MonteCarlo ?

            × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
            • Editeur
            • Markdown