Créer une IA correcte sur un jeu de plateau

[Ekilio]

Bonjour à tous,

Je suis en train de réfléchir au moyen de créer une IA correcte pour mon jeu, Aluren. Les règles sont assez simples, vous pourrez au besoin les trouver ici en détails.

Je les rappelle tout de même rapidement : vous commencez avec une case sur le plateau. Votre adversaire aussi. Chaque tour, vous pouvez prendre n'importe quelle case qui touche une case que vous possédez déjà, sauf si elle est déjà prise par votre adversaire. Chaque case rapporte un point, le joueur qui ne commence pas a cinq points d'avance, celui qui joue le dernier coup perds 10 points d'un coup. Celui qui a le plus de points gagne. La partie se termine quand il n'y a plus de cases qui soient prenables par les deux adversaires.

Donc, le problème que j'ai est que j'aimerais trouver une IA pour le jeu, capable de faire des parties un minimum intéressantes. J'avais pensé à plusieurs systèmes :

- Une IA qui joue totalement au hasard : chaque tour, elle choisi au hasard ce qu'elle va faire.
Avantage : C'est simple à faire.
Inconvénient : C'est pas top, au niveau de l'interet de la partie.
- Une IA qui joue en essayant de calculer le nombre de territoires (cases) restantes et à lui : En gros, l'idée serait : analyser le résultat de tous les coups jouables. Pour chaque coup possible, compter le nombre de cases qu'il aurait à lui et le nombre de cases restantes prenables par les deux adversaires. Si le nombre en question est 0, ne pas jouer le coup sauf si il y en a pas d'autres. Sinon, jouer le coup qui rapporte le plus de territoires juste à lui (c'est à dire que l'autre ne peut pas prendre).
Avantage : L'IA serait probablement la meilleure sur la fin de la partie.
Inconvénients : au début de la partie, tous les coups se valent en "nombre" pur vu qu'il faut plusieurs coups pour entourer completement des cases et donc être le seul à pouvoir les prendre. Qui plus est, l'algo serait très lourd pour le serveur vu que le calcul des territoires est récursif et que c'est la partie la plus lourde de tout le jeu.
- Une IA qui "apprends" : A chaque coup joué par n'importe quel joueur, on enregistre dans une base de données l'état du plateau avant le coup, le numéro de la partie, le joueur qui a joué, et le résultat de la partie. Le but ? Que face à une configuration, le système cherche si quelqu'un a déjà joué d'une manière gagnante cette configuration. Si oui, il joue le coup gagnant la fois précédente, sinon il joue au hasard (je pense que ce sera le hasard, combiner cette méthode avec le calcul est vraiment trop lourd). (c'est plus ou moins le principe pour les IA des jeux d'echecs)
Avantage : L'IA s'améliorera au fil du jeu. Il est assez simple de régler la difficulté de l'IA en lui donnant une chance d'agir au hasard au lieu de reprendre la méthode gagnante. On peut obtenir une IA vraiment très douée.
Inconvénients : Le jeu contient des sorts qui ne peuvent pas être gérés de cette manière (mais peuvent être gérés au hasard). L'IA au début du jeu sera très faible, et c'est justement au début du jeu qu'elle est le plus importante (vu que quand le jeu sera plus connu, il y aura plus de monde et il sera donc possible de jouer contre un joueur humain).

Voila, j'envisage vraiment la troisième option parce qu'elle me semble la meilleure, mais j'aimerais avoir votre avis... Est-ce que vous en verriez d'autre ?

[Melimelo]

Alors personellement je pencherais pour la solution de calcul couplé avec la solution d'apprentisage, bon maintenant au plus il y aura de case dans ton jeu au plus ca sera long a calculer,

Cordialement Melimelo

[Ekilio]

Le truc, c'est qu'il y a 100 cases sur le plateau. Et le calcul est vraiment lourd (presque 1 seconde sous flash sur un plateau vraiment complexe), donc je ne peux pas me permettre de le demander très souvent

Je suis en train de coder, pour tester, une solution apprentissage + sort si pas de coup connu et un sort possible + hasard sinon, je vais voir ce que ça va donner.

[Melimelo]

t'es sur que flash est le plus adapté pour le calcul ?
Et peux tu poser ton calcul en francais, pour être sur qu'il n'y ai pas d'etape en trop

puis imagines, si tu stockait les résultat des calcul à chaque fois que tu les fait, comme ca y a une sorte de cache, bon après ca fait une grosse bdd

[Harparine]

Salut ! Je bosse aussi sur un projet en Flash... Je n'utilise pas d'IA, mais je te conseille de faire tous les calculs critiques (comme ici) sur le serveur. Personnellement, je ne fais que des calculs d'affichage avec Flash. Pour des raisons de sécurité, surtout, et parce que je trouve plus logique de faire des calculs dans le même scripts que mes accès à la base de données... @+

[Ekilio]

Je me suis mal exprimé, concernant Flash : je n'effectue bien évidemment aucun calcul critique dans Flash. Simplement, le calcul des cases libres et prenables se fait deux fois, une fois dans flash et une fois dans Php, parce qu'il serait trop compliqué et trop lourd de récupérer les cases dans flash, donc je le lui refait calculer pour l'affichage. Mais bien sûr, c'est PHP qui gère le calcul amenant à l'enregistrement.

Pour l'IA, je teste en ce moment l'IA qui apprends, en fait elle est assez simple d'un point de vue code (probablement plus que celle qui calcule d'ailleurs). Le problème est que justement, comme tu le dis, les IA efficaces pour un jeu de Go n'existe pas parce qu'il y a trop de solutions à calculer. Et c'est le cas parce que contrairement au jeu d'echec, le jeu de Go se complexifie au fil de la partie : le début de la partie suit souvent un ordre déterminé selon quelques ouvertures, mais la fin est très complexe parce que de la complexité s'ajoute à chaque coup. Aux echecs, au contraire, on diminue la complexité à chaque prise de pièces.

Le problème donc est que mon jeu est du même type que le Go sur ce point : chaque coup augmente les possibilités de jeu pour un joueur et donc rends la partie plus complexe. J'ai fait le calcul hier, à priori il y a 10^48 possibilité de coups au maximum... Ca fait un petit peu trop pour que je les test toutes Alors qu'une recherche SQL dans une table, même si elle contient ce nombre d'enregistrement, c'est plus jouable je pense

Là est vraiment le problème, coder l'IA qui test les possibilités est faisable, mais ça implique de faire dans un situation "simple" (vers le dixieme tour) plusieurs millions de tests... et je suis pas sûr que PHP soit adapté à ça

[Ter Rowan]

Pour l'IA, je teste en ce moment l'IA qui apprends, en fait elle est assez simple d'un point de vue code (probablement plus que celle qui calcule d'ailleurs).

Je pense effectivement qu'il est plus intéressant de faire une IA qui apprend qu'une IA qui calcule tout (plus intéressant intellectuellement et probablement en performance aussi)

par contre, je ne suis pas sur que ce soit plus simple que le calcul des possibilités

quel algorithme utilises tu ?

[Ekilio]

L'algo pour la calcul des possibilités ou celui pour le calcul d'apprentissage ?

Celui pour l'apprentissage, c'est en trois parties. Il faut savoir que l'IA est toujours le joueur 2 (pour des raisons pratiques au niveau de la création de la partie et du jeu, c'est plus simple pour moi).

- Quand un coup est joué :

SI le joueur à jouer EST le joueur 1
POUR CHAQUE case DE plateau
NouveauPlateau = inverser_le_proprietaire(plateau, case)
FIN DU POUR
SINON
NouveauPlateau = plateau
FIN DE SI

enregistrer(NouveauPlateau, coup_joué, par_qui)

- Quand la partie se termine :

SI gagnant EST joueur 1
supprimer_tous_les_coups_joués_par(joueur 2)
SINON SI gagnant EST joueur 2
supprimer_tous_les_coups_joués_par(joueur 1)
SINON
supprimer_tous_les_coups()
FIN DE SI

- quand l'IA doit jouer un coup

chercher(coup_joué) SI NouveauPlateau = plateau
SI (nombre de résultat) == 0
jouer_au_hasard()
SINON
jouer_un_des_coups_trouvés_au_hasard();
FIN DE SI

Et pour ceux qui trouveraient mon explications fumeuse : http://rafb.net/p/vlow1m91.html

Pour l'ia par calcul, j'aurais du executer ma fonction casesLibres() à chaque fois en modifiant le plateau puis en le ramenant à son état initial, et ça aurait fait très très lourd je pense Alors que là c'est assez léger

[Ter Rowan]

effectivement ^^

Perso je trouve cette IA un peu "basique" et surtout, il n'y a pas réellement d'apprentissage , de jugement par la machine, juste un aléatoire filtré

Voilà l’idée que je te propose

A chaque décision (situation initiale + coup joué) tu enregistres le nombre de fois où la décision a été prise et le nombre de fois où cette décision a été la bonne (ie où la partie a finalement été gagnée).

Cela tu le fais pour les deux joueurs, gagnant comme perdant

A partir de la tu peux définir un score nb gagné / nb joué

De là tu peux définir le choix comme étant :

Si, parmi toutes les décisions possibles connues, il y a des scores > 50% alors choisir la meilleure (ou bien, au hasard parmi les n meilleures > 50%, ou fonction de la « distance » entre le meilleur score et ses suivants, à toi de voir si tu veux de l’aléatoire)
Si, parmi toutes les décisions possibles connues, aucune n’a un score > 50% alors choisir au hasard parmi les décisions non connues

Cela devrait éviter deux trois critiques à ton algo précédent :
En effet
- si un coup complètement nul a été joué mais que la partie a été gagnée parce que l’adversaire joue comme un pied, alors ce coup sera statistiquement joué aussi souvent que la super stratégie qui marche à tous les coups
- tu ne t’enrichis que de l’expérience du gagnant et pas du perdant
- à très long terme je pense que toutes les possibilités ou presque seront jugées gagnantes par l’algorithme (en effet il suffit d’une victoire)


(y a plus compliqué encore, apprentissage de bayes, etc.. mais là faudrait que je me replonge dans des bouquins que j'ai perdu il y a dix ans :p)

[pascal]

le résultat de la partie (victoire / défaite ) n'est pas le seul indicateur à prendre en compte.

par exemple :
- le nombre de cases que le joueur peut conquérir au prochain tour
- le nombre de cases que l'adversaire peut conquérir au prochain tour
- le nombre de cases que l'on est sûr d'avoir / de ne pas avoir

A+

Pascal