Discussion :

[ANappa]

Bonjour à tous,

Je me suis recemment mis en tete de créer une IA (un sujet qui me passionait pendant mes études d'infos, mais je m'étais finalement orienté vers le web qui était beaucoup plus accesible) pour un jeu de cartes mais je ne pas trop par où commencer.

Pour faire simple, chaque joueur a 4 cartes visibles. Le jeu se joue au tour par tour et chaque joueur a 12 jetons, à répartir comme bon lui semble, pour booster ses cartes. A chaque round (il y en a 4 donc, chaque joueur joue sa carte en premier à tour de rôle), 2 cartes s'opposent et la carte victorieuse (en fonction de ses caractéristiques & nombre de jetons posés) inflige des dégats a l'adversaire. Le but étant bien évidemment d'enlever tous (ou le plus possible) ses points de vie à l'adversaire.

Ma première idée était "4 round c'est pas énorme, je dois pouvoir calculer l'intégralité des coups jouables". Pour en avoir le coeur net, j'ai ecrit vite fait un prog qui parcours l'intégralité des combinaisons et fait un "echo" à chaque coup. Et ben, il n'a toujours pas fini de s'exécuter

Donc je cherche un peu sur le net (et les seuls réponses à priori intéressantes sont sur developpez !) et je trouve déjà 2 axes de réflexion :
- reduire la profondeur : sur un jeu qui se joue en 4 tours, je ne suis pas sûr que ça soit le meilleur moyen de réduire le temps de calcul ?
- réduire la largeur : la c'est déjà plus facile, enormement de cas sont improbables et généralement perdants (comme utiliser tous ses jetons d'un coup, ...) et permettent de réduire au moins de moitié le nombre de coups à analyser à chaque niveau.

Mais là, nouveau dilemne : est-ce que ça sera toujours intéressant d'optimiser la partie élagage de l'algo ? (en gros est-ce que la réduction du nombre de cas à analyser compense l'augmentation du temps de calcul pour chacun)

Et est-ce que les algos de type MinMax / AlphaBeta sont les plus adaptés à ce type de jeux ?

Et sinon je suis preneur de toute suggestion pour bien débuter ma quete d'IA

[Rakken]

A priori, tu es entrain de creer un jeu de carte, et tu veux au choix modifier les règles du jeu pour qu'il soit plus facile à calculer, ou trouver un algo performant, c'est bien ca ?

Si tu veux un arbre "plus petit", les deux composantes que tu cites agissent. Plus tu as de nombre de coup, plus l'arbre est profond (donc plus il y a de choses à calculer), et plus du as de coup possible, plus chaque niveau est large.
Le problème, c'est qu'a moins de faire des règles ultra-basique (et donc sans interêt ?) ton arbre va de toute manière exploser avec un parcours classique.

MinMax et Alphabéta sont les algos que j'ai eu spontanément en tête en lisant ton post. L'interet est justement de ne pas faire un parcours complet, mais d'éliminer des branches.
Après, tu peux éventuellement les améliorer en trouvant des heuristiques adaptées pour couper des branches plus rapidement en te basant sur des suppositions (par exemple si utiliser ses deux jetons sur la même carte au premier tour fait perdre 95% du temps, alors c'est une branche que tu peux couper direct, sans la calculer).
C'est clairement adapté à ton problème ou visiblement tu as un nombre fini de coups possibles.

[ANappa]

Merci pour la réponse. Et en continuant à réfléchir à mon problème (en me concentrant sur la façon d'élaguer sérieusement le bas de l'arbre) je pense avoir trouvé une solution décente.
Dans beaucoup de cas l'exploration de l'arbre pourra s'arrêter au 2ème ou 3ème round (si en gagnant le reste la partie est perdante ou si en perdant le reste la partie est gagnante - je suppose que du coup j'ai aussi trouvé ce qui me servira de fonction d'évaluation). Et dans le même ordre d'idée, si l'adversaire dépense plus de jetons sur les premiers rounds, ça donne beaucoup de situations où je peux déterminer facilement le chemin "Max" sans avoir a explorer l'arbre (et idem dans la situation inverse)

Me reste plus qu'à commencer l'implémentation pour vérifier tout ça