Créer une IA correcte sur un jeu de plateau

[Lord-Gargoyle]

Hello,

Bon tout d'abord pour programmer une bonne IA, il y a une chose inévitable, il faut être un bon joueur dans le jeu concerné...

Pour un programme qui apprend, personnellement je n'en ai jamais vu. Je suis assez dubitatif sur l'efficacité de ces algorithmes. Si quelqu'un à un exemple d'algorithme du genre qui marche sur un jeu de stratégie, je serais curieux de voir comment ça fonctionne.

Bon alors il y a plusieurs façon de coder une IA :

Soit un algorithme glouton, genre je joue à Othello, je choisis parmis tous les coups immédiats celui qui retourne le plus de pion à l'adversaire... En général c'est pas top (l'adversaire peut les re-retourner le tour d'après si ils sont mal placés)

Soit un algorithme du genre min-max. C'est une recherche arborescente. Il faut avoir une fonction d'évaluation, et la recherche tente de la maximiser quand c'est ton tour, et de la minimiser quand c'est au tour de l'adversaire... On obtient une sorte d'arbre, mais le problème si le jeu est combinatoire, ça devient vite assez lent si on veut avoir un horizon de vue de plusieurs niveaux... C'est ce genre d'algorithme qui est utilisé pour les échecs. Et le problème se pose pour certains jeux, quelle fonction d'évaluation choisir ??

Pour le GO, il y a quelques années les algorithmes étaient assez mauvais (genre 1er ou 2è dan pour les meilleurs). Mais maintenant, de nouveaux algos sont apparus, et ils tendent à devenir aussi forts que ceux des échecs.... Il faudrait que je me renseigne pour savoir comment ils marchent...

En plus dans ton jeu, il y a les pouvoirs qui compliquent tout... Dur de prendre en compte ce genre de truc dans l'IA.

En espérant t'avoir aidé un peu. Si j'ai des idées je reviens poster.

[Lord-Gargoyle]

Bon, je suis allé voir comment fonctionne les nouveaux algorithmes de GO (vu que ton jeu y ressemble un peu). Tout d'abord il utilise une évaluation de la position par la Méthode de Monte Carlo. En fait à chaque coup possible, des parties virtuelles sont effectuées (les mouvements des joueurs contiennent une part de hasard, ce qui fait que le résultat est différent à chaque fois)(je cite "a fast random player plays the game until the end") Si une majorité des parties simulées sont gagnées, la position est évaluée favorablement, si c'est le contraire elle est évaluée négativement (et si les résultats ne sont pas concluant, l'évaluation est moyenne). Ensuite on ne retient lors de la recherche arborescente que les coups les plus intéressants.

Voila, l'algorithme peut être stoppé à tout moment, le coup retenu est celui qui à la meilleure évaluation...

[Plume]

Plop !

l'algorithme peut être stoppé à tout moment, le coup retenu est celui qui à la meilleure évaluation...

Donc tu ne peux pas stopper car sinon comment sais-tu qu'il n'y a pas un coup avec une meilleure évaluation derrière ?

@tchaOo°

[Ekilio]

Salut,

Voici comment j'ai fait pour l'instant sur mon jeu (sachant que je joue assez bien au jeu en question, je pense ^^ Mais en même temps, le nombre de joueurs est assez faible, donc c'est dur de m'évaluer).

Tout d'abord, je prends en compte le fait que l'IA est un "entrainement" pour le cas où il n'y aurait pas de joueurs : je n'ai donc pas besoin qu'elle soit parfaite, c'est plus pour apprendre à jouer, tester un sort ou une stratégie...

L'idée est donc :

- Si l'IA connait la situation qui se présente (donc l'a enregistrée dans sa base de données), elle joue le coup qu'elle connait. Sachant que si elle a "vu" plusieurs fois la situation indiquée, elle choisi au hasard un des coups qui ont été joués ; donc si il y a 14 bons coups et 1 mauvais, les bons coups auront 14 fois plus de chances d'être joués.
- Si l'IA ne connait pas la situation, elle va tester sur un seul niveau tous les coups possibles. Si parmi tous les coups possibles il y en a un qui donne un avantage (plus de territoires possibles, moins de territoires disputés mais sans faire perdre la partie), l'IA va le jouer.
- Si aucun coup ne donne un avantage, l'IA va chercher la situation qui va la rapprocher le plus possible de l'autre joueur : en effet, c'est généralement la meilleure solution (pour bloquer l'autre).

Sachant que je réfléchis à ajouter les sorts, avec une chance d'en lancer un à chaque tour, au hasard (puisque la plupart des sorts agissent avec une part de hasard, il est impossible de calculer leur effet par une IA).

Voila voila... Actuellement, ça tiens. J'ai aussi essayé d'augmenter les coups, c'est à dire de faire calculer à l'IA les cinq prochains coups et de voir quelle série de cinq serait la plus avantageuse, mais c'est trop lent.

[Ter Rowan]

Plop !

l'algorithme peut être stoppé à tout moment, le coup retenu est celui qui à la meilleure évaluation...

Donc tu ne peux pas stopper car sinon comment sais-tu qu'il n'y a pas un coup avec une meilleure évaluation derrière ?

@tchaOo°

tu rajoutes "parmi les coups évalués" et tu comprends ce qu'il veut dire