Bonjour,
je suis en ce moment en train de réaliser un jeu de dames.
J'ai pour le moment coder tout (déplacement, capture, conditions de fin de partie...).
Mais il me reste un gros probleme, la réalisation de l'inteligence artificiel!
J'ai pas mal fouillé sur internet, et j'ai trouvé des document, mais rien de très claire.

Donc si quelqu'un a des infos a me donné je suis prenneur.

PS: Pour l'instant j'ai réfléchis un peu a l'algo qui permettrais de faire ce que je veut, et je suis sur un system de points. Chaque cou possible rapporte des points:

• possibilité de capturer : +5pts
• possibiliter de se déplacer + 2pts
• ne pas être en position de capture après avoir joué: +6pts...

Mais ensuite je ne voi pas trop comment écrire ca en algorithme.

l'idée je pense est comme au échec est de prévoirs un certain nombre de coup de l'adversaire en fonction de ce qu'il fait et donc il en déduira le déplacement qui à long terme lui donnera la victoire

en gros il essaye un coup => victoire alors poid max puis après tu donne un poids au différente action.

maintenant concrétement, ben je passe la main

salut,

pour le IA de jeux on distingue souvent deux types de jeu

• les jeux ouverts
• les jeux fermés

Les jeux ouverts (comme le jeu de dame par exemple) sont les jeux ou à tout instant tu à la connaissance à la fois de ton jeu et de celui de tes opposants. Les jeux fermés (comme le bridge, le tarot, généralement des jeux de cartes) sont ceux ou tu n'as pas connaissance du jeux de tes opposants dans leur totalité.
Il est plus facil de développer une IA pour un jeu ouvert car tu n'a pas besoin de faire d'hypothèses sur le jeu du voisins ou de maintenir une connaissance annexe à celle de l'état du plateau de jeu de dame au moment ou tu souhaite jouer.

Arbre de décision
Un arbre est constitué de noeuds et de feuilles, ainsi que d'une racine qui est un noeud particulier. Dans les intelligences artificielles, ces structures sont utilisées pour prévoir les incidences d'un coup sur la suite du jeu et te permettent de prendre une décision sur le coup à jouer.
Pour faire simple, à un moment donné de ta partie tu as la possibilité de jouer 5 pions, et en fonctions du nombre variable dont ils peuvent avancer on va supposer que tu as 20 coups possibles à jouer !!!!
Tu va construire un arbre de la maniere suivante.

• ta racine est le jeu tel qu'il est actuellement
• tes noeuds de niveau 1 (ceux attachés à la racine, appelés aussi fils de la racine) vont correspondre à ton jeu apres avoir jouer un coup. Tu auras donc 20 noeuds de niveau 1
• tu vas ensuite t'intéresser aux coups de ton adversaire et procéder de la même façon. Chacun de tes noeuds de niveau 1 auras donc autant de fils que ton adversaire aura de coup à jouer dans la configuration de ton jeu correspondant au noeud de niveau 1
• et ainsi de suite...

On se rend compte que rapidement on arrive à un nombre assez grand de noeuds et java n'est pas très généreux en mémoire... Il va donc falloire indiquer une profondeur maximale c-a-d arreter l'algorithme aux noeuds de pronfondeur n. Les noeuds qui n'ont pas de fils sont appelés des feuilles.
Généralement le niveau de difficulté d'un adversaire de type 'bot' dont le choix est géré avec un arbre de décision correspond justement à la profondeur. Facil: n=2, moyen: n=3, dur: n=4 (par exemple).
Tout ça c'est bien beau mais a quoi ca sert ?

Le poid des noeuds comme critère de choix.
Supposons que tu ai construit ton arbre. Tu as k feuilles. Donc k configurations à noter.
Dans l'idéal tu as construit un arbre complet et toutes les feuilles correspondent à des situation ou soit toi, soit l'ordi a gagné. Note que les feuilles ne sont pas forcément toute de même profondeurs car tu peus gagner en plus ou moins de coups. (il te faudra gérer cela dans ton arbre car si tu peus gagner en deux coups, il ne faudra pas chercher les fils du noeud correspondant à cette situation de victoire...)
Il te faut alors analyser chacune de ses k configurations en fonction des avantages et inconvénients qu'elle donne.
Par exemple:

• si tu crées une dame à un noeuds N de profondeur P tu attribues x/P points à toutes les feuilles issues de ce noeuds (c-a-d les feuilles qui sont fils d'un fils d'un fils ... d'un fils de N)
• si tu prends un pions à l'adversaire à un noeuds N de profondeur P tu attribues y/N points à toutes les feuilles issues de ce noeud
• si une feuille de profondeur P te permet de gagner tu lui attribues z/P
• etc... selon les critères que tu veus

au final, tu vas donner à chacun de tes noeuds de niveau 1 une valeur égale à la somme des points des feuilles issues de ce noeuds. le coup que tu joues est celui qui correspond au noeud de niveau un avec le plus gros score
Dans l'exemple idéal les points attribués à une feuille valent 1 si victoire et 0 si défaite. Si tu as f feuilles et que t est la somme des valeurs des feuilles pour un noeud de profondeur 1 alors tu as t/f% de chance de gagner en jouant le coup correspondant à ce noeud.


Quelques trucs
Les arbres de décisions sont consommateurs en ressources, aussi lors de la construction des branches d'un tel arbre il est intérressant de ne pas conserver les branches inintérressantes. Imaginons que tu ais trois coups jouables, t'as racine va avoir trois fils (3 noeuds de profondeur 1) ton noeud un à un poid de 5 le second de 2, tu n'as pas besoin de conserver la seconde branche de ton arbre, tu sais déja que tu va jouer soit le coup correspondant au noeud un soit celui correspondant au noeud 3.
De plus si au final ton arbre te dit de joueur le coup 1 (noeud 1), tu peus conserver la branche en mémoire car une partie te servira pour ton prochain coup.
Pour éviter les problème de dépassement de mémoire il est important que tu test ton programme avec une profondeur grande et que tu compte le nombre de noeuds étudiés. dans un try catch tu récupère le nombre de noeuds à partir duquel java sature. Et tu fixe une limite absolue à ton algorithme en nombre de noeuds calculés.

Et pour compléter ce qui a déjà été dit : MiniMax :]
(par ailleurs, en général, on fixe une limite temporelle; c'est plus simple/souple et le résultat est le même.)

Le problème de la limite temporelle c'est que le jeu n'est pas égal devant les machines. Si high score il y a, on pourra le mettre sur le dos de la configuration.
D'un autre coté, le problème de la limite en profondeur ou nombre de noeuds c'est que parfois ca s'éternise.

Je suis débutant en Java, et ce sujet m'intéresse, mais je trouve bizarre que la mémoire puisse saturer avec un jeu de type dames/échecs.
Est-ce que prévoir, disons 3 coups à l'avance, consomme autant de mémoire ?
De plus, je ne suis pas d'accord sur le fait de supprimer une branche dont le premier coup possède un petit score : exemple : ça peut être un sacrifice qui permet de gagner la partie...

OK, déja ca me donne une petite idée de la facon de faire.
Merci beaucoup.

Citation : tatrefthekiller

Je suis débutant en Java, et ce sujet m'intéresse, mais je trouve bizarre que la mémoire puisse saturer avec un jeu de type dames/échecs.
Est-ce que prévoir, disons 3 coups à l'avance, consomme autant de mémoire ?
De plus, je ne suis pas d'accord sur le fait de supprimer une branche dont le premier coup possède un petit score : exemple : ça peut être un sacrifice qui permet de gagner la partie...

Tu n'es pas obligé de garder tout ton arbre en mémoire, et peus ne conserver que la branche la plus intéressante pour la comparer à la suite.

Maintenant pour un jeu de go tu as 13*13 cases, soit 169 coup possible au début, puis 168, ... pour faire une grosse approximation on dira qu'une partie ne dure que 10 coups, soit 169!/159!=1,4*10^22 soit pour 10 coups stocké sur 1 bit (soyons pas réaliste) un arbre de profondeur 10 occupant 1810GO !!!
c'était juste pour te faire une idée...

Alors d'un coté tu peus gagné du temps en gardant en mémoire la partie de l'arbre qui correspond au coup que tu joues, d'un autre tu ne peus pas en garder trop...

mais bon là s'était l'exemple extrême, faut trouver un juste milieu