Il y a quelques temps, j'avais dû faire un truc pareil pour le jeu d'othello, j'avais trouvé pas mal de doc sur internet... Je ne sais pas si j'ai encore les liens, mais tu peux regarder sur des sites de jeux de dames (sites de fans, assoc de joueurs...), j'avais trouvé des bouts d'info dessus. Voire des sites d'othello ou d'échecs.
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)
# Quelques idées...
Posté par alf . En réponse au message Programmation d'un jeu de dames chinoises. É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)