Bonjour,
Voila je réalise actuellement un jeu de dames chinoises avec intelligent artificielle, mais j'ai beaucoup de mal a percevoir la manière dont je vais le concevoir, d'un niveau algorithmique mais aussi au niveau de la programmation.
Les algorithmes seraient un minimax muni d'un algorithme alpha-beta. Mais je suis encore à me demander quelle structure je vais utiliser pour concevoir le plateau pour pouvoir appliquer une évaluation pour chaque joueur.
Si vous pouvez me donner un petit coup de pousse pour démarrer voir si vous avez des parties de codes commentés.
Merci
Forum Programmation.autre Programmation d'un jeu de dames chinoises
28
nov.
2005
# As tu bien définit ton algorithme
Posté par jeje99 . Évalué à 0.
Pour commencer définit ton algorithme d'IA, choisit ton langage et en définit ta structure...
[^] # Re: As tu bien définit ton algorithme
Posté par mat3o . Évalué à 3.
Le language utilisé sera le C++
# jeu
Posté par Pooly (site web personnel) . Évalué à 3.
(L'abalone a aussi un plateau hexagonal, et j'avais codé ça avec une matrice, simple efficace, rapide).
# Idée
Posté par mac_is_mac (site web personnel) . Évalué à 3.
donne comme premier lien
http://www.csc.calpoly.edu/~team_2fk/F05/Milestone-Week-8.ht(...)
qui a l'air assez intéressant
# Quelques idées...
Posté par alf . Évalué à 1.
Pour en revenir à ton problème, bah ça dépend. min-max permet de trouver un coup à jouer dans une situation donnée, en maximisant une fonction f, censée indiquer, à partir de l'état de la partie (état de l'échiquier et joueur ayant la main), si la situation est bonne ou pas, en lui associant une valeur numérique.
Le premier problème, avant la structure de données, est donc de définir cette fonction f... et donc de définir ce qui est une bonne situation pour un joueur ! On peut déjà poser qu''elle renvoie +infini pour un échiquier ou le joueur qui a la main gagne, et -infini s'il a perdu. Ensuite, pour les situations où la partie n'est pas encore finie, il faut déterminer si la situation est plutôt bonne (>=0) ou mauvaise (<=0). Et c'est là qu'on doit connaître le jeu, et les différentes stratégies.
Je ne connais pas trop les stratégies du jeu de dames, mais pour montrer à quoi ça ressemble: dans l'othello, la fonction f "naïve" consiste à compter les pions d'une couleur, puis de l'autre, et à faire la différence. f renvoie tout bêtement le nombre de pions à toi moins le nombre de pions à l'adversaire.
Sauf que le nombre n'est pas sufffisant: un seul coup de l'adversaire peut renverser plusieurs de tes pions, par exemple. Ou, avec un peu de pratique, on se rend compte qu'avoir les coins est important. Or, pour placer ton pion sur le coin, il faut que l'adversaire place un pion sur une case à côté; et inversement tu ne DEVRAIS pas, à moins d'y être obligé, placer un de tes pions sur une case adjacente à un coin libre. On aboutit alors à donner une importance relative à chaque case: les coins valent beaucoup plus que les cases qui leur sont adjacentes; le reste des bords vaut plus que les cases du rang interne (pour la même raison). Je suppose qu'aux dames, on peut arriver à des raisonnement similaires. On peut alors donner une valeur (numérique) à chaque case, et la fonction f ferait la somme des valeurs de cases que tu occupes moins celle des cases qu'occupe l'adversaire.
Il faut ensuite savoir si l'importance relative de chaque case peut évoluer en cours de partie (je sais pas si ça existe, on n'avait pas implémenté ça). Mine de rien, c'est important, vu que toutes les données variables doivent être passées en paramètres récursivement dans ton min-max... et donc ça consomme de la mémoire (et du temps pour les copies de données), alors que les données fixes peuvent être crées une fois pour toutes (il existe aussi l'optimisation de ne garder qu'une copie de l'échiquier, et de jouer les coups directement dessus quand tu fais ton min-max, en annulant le coup à chaque retour. On ne l'avait pas utilisée, parce qu'on pensait qu'elle était trop compliquée à coder, mais c'set une possibilité à envisager).
Par ailleurs, au jeu de dames, on a 5 états pour une case: reine blanche, pion blanc, vide, pion noir et reine noire. On peut leur affecter, par ex, des valeurs +N, +1, 0, -1 et -N. Il faut donc aussi choisir la valeur relative d'un pion et d'une reine, le N (en othello, c'était plus simple de ce côté ;-).
On arrive donc à donner dans chaque case deux infos: une importance (numérique), et un état. Et f pourrait, par exemple, parcourir le damier et sommer le produit de la valeur de chaque case par sa "couleur" (ou autre variante).
Au damier, contrairement à l'othello et aux échecs, seulement une moitié du terrain est utile... donc une matrice 10x10 ferait perdre de la mémoire, un bête vecteur de taille 50 peut suffire, sauf que l'algo de déplacement serait un poil plus compliqué. Après, il faut étudier la consommation mémoire vs. le temps de calcul. Même avec alpha-bêta, descendre à 5 ou 6 demi-coups avec othello rend le programme peu "réactif", et ça empire vite (je ne me souviens plus de la complexité exacte du min-max avec élagage alpha-beta, mais c'est beaucoup).
Pour la "couleur" : 3 bits suffisent pour dire si une case est reine blanche/pion blanc/vide/pion noir/reine noire (un bit qui dit si la case est vide, l'autre qui dit la couleur, et le dernier si c'est pion ou reine). Tu peux donc utiliser, par ex:
- un long[5] :un long tient sur au moins 32 bits, si je me souviens bien. Or, 10*3 = 30 bits, tu peux donc coder deux lignes entières dans un long, donc les 10 lignes dans un long[5]. Question mémoire, c'est presqu'optimal, mais ça complique la difficulté d'implémentation (décalages et masque binaires...)
- ou un vecteur de 50 structures avec des champs de bits. La perte mémoire par rapport à la première solution ne doit pas être énorme, et le codage est probablement plus simple.
Pour les valeurs repectives des cases, ça dépend du nombre de valeurs différentes que tu veux donner. Si ces valeurs n'évoluent pas durant la partie, tu n'en gardes qu'une en mémoire, et donc tu n'es pas obligé de rogner des bits de partout ;) Tu prends juste le type C qui est le plus adapté à tes calculs en terme de vitesse (int ?). Si elles évoluent... Tu peux établir à l'avance une liste finie de tableaux que tu crées une fois pour toutes, ce n'est pas beaucoup plus compliqué.
Par ailleurs, ça ne joue pas sur la structure de données, mais la fonction f peut aussi compter le nombre de coups possibles: si tu peux forcer ton adversaire à choisir à chaque fois entre un faible nombre de coups possibles, tu as un avantage sur lui.
Après, mais vraiment après, on peut encore optimiser en gardant en mémoire les résultats d'évaluation (état du damier, joueur ayant la main, nombre de demi-coups calculés), par exemple avec une table de hachage. Mais ça sort du cadre de ta question... (sans parler de l'effet d'horizon, tout ça)
[^] # Désolé...
Posté par alf . Évalué à 1.
Du coup, il y a un nombre de types de cases un peu différent... 6 joueurs plus la case vide, donc 7 cas, donc quatre bits suffisent.
Et la forme de la table de jeu n'est pas la même, vu que c'est un pavage d'hexagones... Bon, bah tant pis, je m'a gourré. Là, le calcul du déplacement est plus compliqué, en effet.
De plus, la fonction f est un poil plus compliquée: tu as jusqu'à 5 adversaires. Même si tu n'en préfères pas un par rapport aux autres, ça complique un chouia l'algo.
Bon, pour le coup, j'ai ps trop d'idées...
--
alveric qui ferait mieux de lire les questions avant de répondre...
[^] # Re: Désolé...
Posté par mat3o . Évalué à 1.
[^] # Re: Désolé...
Posté par alf . Évalué à 1.
http://ramal.free.fr/cc_fr.htm
qui renvoie sur
http://www.csis.hku.hk/~kao/spc/cc_rule.html#introduction
J'ai trouvé d'autres liens, mais peu informatifs...
Le deuxième lien numérote les cases du plateau, mais je pense que le représenter en mémoire sous forme de vecteur de 1 à 121 n'est pas forcément une bonne solution: l'algo qui détermine un coup possible serait très compliqué... Une matrice devrait faire l'affaire: tu perds un peu de mémoire (les coins et une partie des bords ne sont pas utilisés), mais l'algo de déplacement est plus facile à implémenter (et plus rapide probablement), si on fait attention aux bords du plateau. Tu peux considérer que, dans ta matrice, un déplacement à gauche revient à un délacement à gauche sur le plateau, idem à droite, un déplacement en haut sur ta matrice revient à haut-gauche sur le plateau, et prendre la case dans la diagonale haut-droit représente un déplacement haut-droit sur le plateau. idem en bas... C'est bien sûr une représentation, à toi de choisir la tienne (en s'assurant qu'elle soit cohérente (par ex, un coup puis le coup inverse te ramène dans la même case))
Comme je l'ai dit, tu as entre 2 et 6 joueurs, donc tu as 7 possibilités par case. Définir un type contenant un champs de 4 bits serait donc suffisant (je pense que le C++ permet de le faire, non ?). Ensuite, tu établis ta matrice avec ce type comme "base".
Ta fonction d'évaluation doit attribuer le score maximal au plateau où tes 10 cases d'arrivée sont prises par tes propres pions; et un score minimal si un des adversaires remplit son coin. Pour le début, il vaut mieux construire une fonction d'évaluation simple comme je l'ai décrit, mais qui marche; une fois que ton programme fonctionnera, tu pourras la faire évoluer.
D'ailleurs, un petit truc: tu peux créer plusieurs IA dans ton programme. Il suffit de définir un prototype fixe pour ces fonctions, une option de paramétrage de la difficulté, et une fonction appelée par ta boucle de jeu principale qui va appeler la bonne fonction d'évaluation en fonction de la difficulté. (du style: facile -> la fonction f naîve, moyen -> une fonction plus évoluée, difficile -> f plus compliquée, avec plus de demi-coups d'avance). Ca permet, de plus, de faire jouer une IA contre une autre... et donc de vérifier si une IA est plus efficace qu'une autre.
De tête, le prototype peut ressembler à ça:où "coup" est le type représentant un coup à jouer, "damier" je te laisse deviner, "joueur" le joueur qui va jouer et "profondeur" le nombre de demi-coups d'avance.
De plus, ça permet de faire en sorte que ta fonction evalue() puisse utiliser n'importe quel algo, même autre-chose que min-max (le paramètre "profondeur" pouvant être utilisé pour régler ton algo d'une autre manière). Tu sépares ta partie IA du reste, donc tu gagnes en modularité. Tu peux même imaginer ensuite une IA pour laquelle une structure de données différente de celle que tu as choisi au départ est optimale: alors la fonction evalue() peut convertir les paramètres dans le bon format de données avant d'executer l'algo "pour de bon". Pas besoin de tout casser le jour où tu auras trouvé la fonction d'évaluation optimale ;)
J'avais fait ça en C pour le othello, en C++ tu peux faire de la même manière en procédural, ou en objet (avec chaque IA représentée par une classe ayant une méthode evalue() )
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.