Java: Question IA

[Rockleader]

Salutation, une nouvelle fois je viens vous embêter avec mes réflexions :hum:

Bon, j'ai terminé la partie implémentant toutes les règles pour ce fameux jeu de go^^ j'ai quelques problèmes à régler mais ça ne devrait pas me poser de problèmes^^

Je me pose désormais la question de l'IA.

S'il est facile de faire un truc lambda qui jouera des coups complètement aléatoire, ce n'est pas intéressant vous en conviendrez :ptdr:

Tous le défis maintenant ça va être de réaliser une évaluation correcte afin de donner des valeurs à des coups. Bref, je vais pas spécialement rentrer dans les détails pour ce jeu en particulier, je vais rester général pour ma question^^


Je voudrais avoir votre avis sur la meilleure façon d'implémenter une IA; l'idée de base est en fait assez simple.


Je pensais construire un arbre qui aurait donc des noeuds et des feuilles.

Chaque noeud représenterait un avancement de la partie possible; et les feuilles correspondrait donc à une partie terminé à laquelle on va associer un score.
Ce qui permet ensuite de remonter l'arbre et de voir quelle branche obtient le meilleur score.


Ma question: Y a t'il une structure de donnée existante en java pour réaliser ce genre de chose ?

Ou bien faut il réaliser soit même une classe et la construire sous la forme d'un arbre; un peu comme la structure des arbres GRD que j'ai pu voir l'an dernier en c.


Merci pour vos conseils :lol3:

[Monsieur23]

Aloha,

J'y connais pas grand chose en Java, mais je pense que ta méthode de calculer toutes les parties possibles, pour ensuite choisir la meilleure, c'est irréalisable (ça passe si tu joues au tic-tac-toe, mais il y a beaucoup trop de possibilité au go).

Tu peux utiliser une méthode "tronquée" de ça :
- tu définis une fonction "domination" qui calcule à quel point la partie est proche d'être gagnée (qui vaut par exemple 0 si la partie est perdue à coup sûr, 100 si la partie est gagnée à coup sûr).
- tu calcules tous les coups possibles à un moment donné, et tu choisis celui qui maximise la domination (tu peux aussi calculer toutes les suites de deux, trois, quatre, etc coups pour que la stratégie soit meilleure)

[Rockleader]

Oui oui bien sur ce n'est pas réalisable au go; je ne voulais pas rentrer dans les détails et rester général.

Il est clair que ce n'est pas possible d'évaluer toutes les parties jusqu'au bout, on ne pourra faire que quelques niveau d'arbre à la fois, surtout au début.


Là, je me pose surtout des questions sur la structure pour le mettre en oeuvre plus que sur l'algo qui aura derrière.

[Zorro_X]

Sur les jeux à coup par coup, il s'agit de construire l'arbre des possibilités à partir du point de jeu en cours, ce que tu sembles soit avoir déjà codé soit avoir déjà envisagé.
L'astuce réside dans l'exploration de cet arbre, comme il est difficile de "résoudre" le jeu* (parcourir toutes ses possibilités), on utilise ce qui s'appelle une fonction "heuristique" qui n'est rien d'autre qu'une sorte de fonction qui donne une "note" de l'état de la partie (en fonctions des règles) à l'avantage du joueur IA, c'est ce que Monsieur23 a appelé "domination".
Avec cette fonction/méthode tu parcours l'arbre des possibilités en privilégiant les branches qui te sont plus avantageuses (pour vérifier, autant que possible, que c'est bien le cas et en gros, que la situation ne finit pas par se retourner). Par conséquent au moment de jouer, tu privilégies les branches qui ont une "meilleure note" (heuristique) car ce sont celles qui augmenteront tes chances de gagner.
Il est important de noter qu'il faut définir une limite à cette recherche heuristique, sinon tu ne t'arrêteras que lorsque t'auras résolu le jeu, ce qui n'est justement pas le but ! Pour ce faire, t'as plusieurs possibilités :
. Limite en temps : c'est la plus utilisée, elle permet de tirer parti de la puissance de l'ordinateur tout en demeurant "jouable". C'est malheureusement la méthode la plus difficile à mettre en place, elle requiert d'utiliser des opérations simples/courtes et ré-entrantes.
. Limite en profondeur : c'est la plus simple à mettre en œuvre et te permet aussi de définir aisément le niveau de difficulté de l'IA (plus tu parcours de niveaux, plus elle sera "forte", mais ca prendra plus de temps)
. Limite en nombre de nœuds : variante de la profondeur, qui permet de faire un meilleur compromis par rapport au temps que ca prend.

Il va sans dire que la fiabilité de ce parcours "guidé" par une heuristique dépendra aussi de la qualité de ton heuristique. Si tu tapes dans Google "heuristique pour jeu de Go" je suis sur que tu trouveras des astuces auxquelles tu n'avais pas encore pensé pour la concevoir...

A l'époque (il y a une 20e d'années maintenant), j'avais fait un jeu Othello en suivant ce même principe, j'avais même tenté de le résoudre, mais le limitations de stockage de l'époque ont eu raison de mon élan d'analyse...

*Résoudre un jeu : cela demeure assez possible pour les jeux simples (courts), mais si t'as plusieurs To de stockage tu peux tenter de résoudre ton jeu aussi. Pour résoudre un jeu "non-simple" il faut le pré-calculer : calculer tout l'arbre des possibilités de jeu, ce qui peut être titanesque car souvent le nombre de possibilités croît de manière exponentielle. Une fois que t'as tout ton arbre, tu fais remonter dans chaque nœud qui est gagnant au bout et l'IA ne prendra aucun temps de calcul. C'est intéressant et bluffant de voir ainsi, qu'à partir du moment où l'IA t'a emmené vers une branche où elle t'annonce qu'elle va gagner, t'es "foutu d'avance"...

[Ben314]

Salut,
Perso, sur les premier Apple ][, je m'était attaqué au "puissance 4" (à mon avis à peu prés équivalent en terme de complexité a l'othello-reversi) et je confirme que LE problème principal, c'est de trouver une "fonction d'évaluation" à peu prés pertinente.
Par exemple, au go, autant ça ne semble pas déraisonnable d'attribuer une note "tactique" à une situation donnée (nombre de pierres prises, nombre de liberté des différente chaînes de pierres, etc...) autant je vois pas trop comment s'y prendre pour évaluer la partie "stratégique" (i.e. la taille de la zone qu'on risque éventuellement de contrôler à la fin de la partie : ne pas oublier que le but n'est absolument pas de prendre le plus de pierres possible à l'adversaire...)

Sinon, concernant l'arbre dont tu parle, je ne suis pas certain qu'il soit intéressant dans un premier temps de le stocker dans une quelconque structure vu que tu n'a pas besoin de l'avoir "en entier" en mémoire : dans cet arbre tout ce dont tu as besoin, ce sont les évaluation des différentes branches partant de la racine (et pas plus) et tu peut parfaitement "parcourir" l'arbre uniquement à l'aide d'un appel récursif à une même fonction (qui ne stockera nulle part son "résultat" mais le renverra simplement à la fonction appelante, à savoir elle même)

Les seuls intérêt que je vois au fait de tout stocker, c'est :
- D'éviter d'évaluer deux fois la même situation, c'est à dire de constater que si par exemple les joueurs jouent les coups A,B,A' on est dans la même situations que s'il avait été joué A',B,A (sauf en ce qui concerne la règle do KO...) mais vu le temps que va prendre la gestion de l'arbre et la recherche pour savoir si le coup a déjà été évalué, je sais pas si c'est rentable.
- De pouvoir mettre en place une limite en temps de la recherche qui impose plus ou moins de parcourir l'arbre par niveau donc pas de façon récursive, mais je pense comme Zorro_X que ce n'est pas, et de loin, la méthode la plus simple donc pas celle à essayer de mettre en place pour son premier essai.

P.S. : En parlant de "premier essai", ça me fait quand même penser que, de commencer par le GO qui est sans doute le jeu où il est le plus difficile à trouver une "fonction d'évaluation" un peu pertinente, c'est pas forcément le meilleur truc à faire...