Bonjour tout le monde,
Je suis élève dans une école d'ingénieur en première année de cycle préparatoire intégré, et j'ai un projet à réaliser sur les 2 années qui est le suivant : réalisation d'un jeu de dames chinoises avec une intelligence artificielle (voila j'ai raconté ma vie, et la maman ours des pyrénnées ...). Pour le moment mon collègue et moi sommes dans l'étude des différentes méthodes et algorithmes qui nous permettrait de résoudre le problème du "meilleur" coup à jouer pour l'ordinateur. Nous avons étudié les définition et principes du minimax associé à la coupure alpha-beta, des algorithmes génétiques, des systèmes experts, de la logique floue, de l'algorithme des colonies de fourmis, des réseaux bayésiens.
Mais jusque la, nous n'avons aucun algorithme concret. Je m'étais dirigé vers les algorithmes génétiques pour "résoudre le problème", mais après discussion avec mon prof, il m'a dit de regarder vers les problèmes NP-Complet... alors je me lance dans ces fameux problèmes : bouquins, site web. Mais bon, je me borne a des définitions, démonstrations un peu barbares ( nettement au dessus de mes connaissances en algorithmique )sans vraiment avoir d'exemple du comment il faut raisonner, ou du comment résoudre un certain type de problème. J'aimerai savoir si quelqu'un connaît des sites qui serait susceptibles de m'aider, ou si quelqu'un pourrait m'indiquer dans quel voix partir pour commencer à réaliser l'algorithme.
Merci.
Forum Programmation.autre Programmation d'une IA pour le jeu des dames chinoises
13
mar.
2005
# IA des jeux
Posté par BAud (site web personnel) . Évalué à 3.
tu peux compléter, c'est du wiki. Je ne me rappelle plus s'il y avait des algos :-(
# Pour Min/Max
Posté par Jean-Marc (site web personnel) . Évalué à 4.
J'ai codé les dames chinoises pour un TP d'algo l'année derniere, je te donne l'adresse du sujet qui est très bien fichu :
http://www710.univ-lyon1.fr/~jciehl/Public/educ/lil/2003/algotp7.ht(...)
Il y a l'algo minmax que tu peux appliquer quasiment tel quel aux dames (c'est pas très long à coder) et des liens pour approfondir.
[^] # Re: Pour Min/Max
Posté par mat3o . Évalué à 1.
[^] # Re: Pour Min/Max
Posté par Jean-Marc (site web personnel) . Évalué à 2.
Mais je peux t'aider sur la fonction d'évaluation.
Le but de cette fonction c'est de donner une probabilité de gagner dans une disposition de jeu donnée. Donc si tu as gagné, c'est à dire que tous tes pions sont en position finale, alors P = 1. Les valeurs indiquent le meilleur chemin à prendre dans l'arbre d'évaluation min-max. Elles jouent le rôle de "panneau indicateur", on parle d'"heuristiques" (c'est le terme savant).
Le problème c'est qu'il n'y a pas UNE meilleure façon de faire (du moins on ne la connait pas), c'est donc à toi d'essayer différentes heuristiques et de trouver la meilleure.
Le plus simple c'est d'associer un score à chaque emplacement du jeu, score d'autant plus élevé que l'emplacement est proche de la position finale du pion.
Pour le joueur d'en haut, ça peut donner quelque chose comme ça (disclaimer : j'ai pas testé ces valeurs, c'est pas dit que ce soient les meilleures)
0.40
0.15 0.15
0.06 0.06 0.06
0.03 0.03 0.03 0.03
Et les valeurs suivantes vont en décroissant quand tu t'approche du bas.
Pour avoir le score d'un joueur à un moment donné, il suffit de faire la somme des valeurs de toutes les cases sur lesquelles sont ses pions.
Évidemment, pour le joueur n°2 , les valeurs seront pas les mêmes.
Ça c'est la version la plus simple, après c'est à toi d'avoir de l'imagination, je connais pas assez bien les dames chinoises pour proposer la meilleur façon de faire :-)
De mémoire, je faisais de la façon suivante :
- additionner les scores associés aux coordonnées de chaque pion
- soustraire ceux de l'adversaire
- compter les pions qui ont le droit de se déplacer (l'idée c'est qu'une position où on est libre de se déplacer est meilleure qu'une où on s'est retrouvé bloqué dans un coin ou par l'adversaire)
- soustraire les déplacement de l'adversaire
Avec ça, tu verras que tes pions s'organisent tous seul pour faire des "saute-moutons", c'est assez marrant à voir :-)
# IA
Posté par Bruno Michel (site web personnel) . Évalué à 2.
Par contre, les algorithmes de type minmax et alpha-beta sont des algorithmes efficaces pour ce genre de jeux, à condition d'avoir une bonne fonction d'évaluation. Par exemple, les meilleurs jeux d'échecs utilisent ces algorithmes (avec des optimisations). Tu ne devrais pas avoir de mal à trouver de la doc sur ce sujet sur internet.
Implémenter un tel algorithme n'est pas très difficile, mais il faut trouver une bonne fonction d'évaluation. Pour cela, tu peux utiliser les algorithmes génétiques (si tu en as le temps). Je pense que cette méthode peut donner de très bons résultats, genre battre ton prof lors de la soutenance.
Sinon, les systèmes experts, c'est bien quand on a un expert sous la main.
La logique floue ne devrait pas t'être très utile.
Les algorithmes de type colonie de fourmis, je veux bien, mais je vois mal comment utiliser cela.
Et pour les réseaux bayésiens, je ne sais pas du tout ce qu'ils peuvent donner sur un ce genre de problèmes.
Un dernier domaine que tu pourrais éventuellement explorer est l'apprentissage.
[^] # merci
Posté par mat3o . Évalué à 1.
Encore merci de votre aide !
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.