Discussion :

[shidosh]

Bonjour,

Je debute en C# et je cherche (pour le fun) a implementer un algorithme (appele Monte Carlo Tree Search) pour un jeux type TCG (Magic, HearthStone, Hex, Pokemon etc...).
La premiere etape de l'algo consiste a trouver tous les etats possibles a la fin du tour.

Pour simplifier les choses, j'ai voulu calculer toutes les actions possibles sachants que chaque carte peut effectuer une attaque ou ne rien faire.

J'ai fais une premiere implementation qui ressemble a cela:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
 
namespace KillEnnemy
{
 
    public class Minion
    {
        int Atk;
        int HP;
        public string Name;
 
        public Minion()
        {
            this.Atk = 0;
            this.HP = 0;
            this.Name = ""; 
        }
 
        public Minion(int Atk, int HP, string Name)
        {
            this.Atk = Atk;
            this.HP = HP;
            this.Name = Name;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            List<Minion> MyMinionList = new List<Minion>();
            List<Minion> EnnemyMinionList = new List<Minion>();
 
            MyMinionList.Add(new Minion(1, 2, "1/2"));
            MyMinionList.Add(new Minion(2, 1, "2/1"));
            MyMinionList.Add(new Minion(3, 2, "3/2"));
 
 
            EnnemyMinionList.Add(new Minion(1, 1, "1/1"));
            EnnemyMinionList.Add(new Minion(2, 2, "2/2"));
            EnnemyMinionList.Add(new Minion(3, 3, "3/3"));
            EnnemyMinionList.Add(new Minion(4, 4, "4/4"));
 
            foreach (Minion i in MyMinionList)
            {
                string str = i.Name + " ne fait rien.";
                Console.WriteLine(str);
 
                foreach (Minion j in EnnemyMinionList)
                {
                    string str2 = i.Name + " attaque "+ j.Name;
                    Console.WriteLine(str2);
                }
            }
            Console.ReadLine();
        }
    }
}

Bien sur cette implementation est fausse car j'ai bien toutes les actions possibles mais pas toutes les combinaisons possible.
Si je ne me trompe pas, il existe, pour cette exemple, 125 combinaisons.
1/2 ne fais rien, 2/1 ne fais rien, 3/2 ne fait rien
1/2 ne fais rien, 2/1 ne fais rien, 3/2 attaque 1/1
1/2 ne fais rien, 2/1 ne fais rien, 3/2 attaque 2/2
etc....
Je ne sais pas si il existe en C# un moyen simple pour pouvoir obtenir l'ensemble des combinaisons possible quelque soit le nombre de cartes sur le board.
Je sais que toutes les combinaisons ne seront pas bonne (par example si la 1/2 attaque la 1/1, elle sera detruite et il sera inutile que la 2/1 et la 3/2 l'attaque), mais c'est une autre histoire...

Si une personne a une idee ou me pointer une meilleure structure a utiliser, je suis preneur.

Merci.

[BorisTheBear]

Pas de choix que de parcourir les deux listes.
Par contre j'ai l'impression que ton problème est plus complexe que tu ne le penses si tu veux faire une IA ou une aide de jeu.
La première question a te poser ça sera : comment chiffrer le résultat pour savoir si une action est rentable ou non.
Sacrifier un saprobiante 1/1 contre un une 20/1 , ça le fait.

Autre truc.. Plusieurs créatures peuvent attaquer l'ennemi par tour. Et dans ton algorithme tu vas sûrement devoir faire des retours en arrière. Il te faut une classe qui memorise un état de jeu complet ( avec une copie des listes de minions et une copie de leur PV). A chaque état tu lui associe un nombre estimant ton avantage sur l'ennemi. Ça peut être par exemple la somme de l'attaque et def de tes monstres moins ceux des ennemis.

Créé une classe ou tu vas lier un état source du jeu, a une liste de couples (action , état final).
Tu vas avoir un arbre. Le sommet est l'État courant.
Ton objectif est de faire les actions qui vont te mener a l'État que tu as estimé le plus favorable.

[shidosh]

Merci pour ta reponse.
En effet, le probleme n'est pas si simple (et donc plus fun) et je m'en suis rendu compte ce WE.
En effet, l'ordre des attaques joue aussi un role, ce qui augmente les possibilites encore plus.

L'algorithme MCTS (http://www.wikiwand.com/en/Monte_Carlo_tree_search) est tres different du classic alpha-beta. Pour ce dernier, on a une notion d'evaluation des mouvement, ici c'est tres different.
C'est en gros:
- De ma position, je calcul tous les etats possible apres mon tour.
- Je choisi un etat au hasard (Expansion) et je fais une partie en jouant au hasard (Simulation)
- Je regarde si je gagne ou pas et je remonte l'information (Backpropagation)
- Suivant le resultat obtenu et le nombre d'etat visite (selection), je continue ou change d'etat
Et je repete ces phases jusqu'a la limite du nombre d'essais que j'ai choisi ou du temps imparti.

L'avantage est qu'il faut juste decrire les regles du jeux et laisse l'algo tourner.
Ce dernier ayant tendance a converger vers les mouvements les plus prometteur.

J'ai repense le code et reecris le tout mais malheureusement ma carte mere a rendu l'ame hier et impossible d'acceder au code.

Merci encore pour ta reponse.
J'essaierai de poster l'algo et tout le reste quand j'aurais fini