Salut à tous, j'ai besoin de votre aide.
Suite à la 10ème "game jame" de DVP. J'ai voulu réaliser un "Puissance 10" (j'ai été gourmand sur ce coup). Ce qui m'a amené à explorer l'algorithme "MiniMax" pour ce type de jeux. En effet, on peut utiliser cet algo dans énormément de jeux de plateau avec des jetons : Morpion, Puissance 4/5, Go, Hotello, échecs, backgammon, dames, Marelle et toutes les variantes possibles. Ce qui rend cet algo très intéressant à comprendre.
Je me suis vite rendu compte que cet algo a des limites. Après quelques recherche, je suis tombé sur cette source de Fabien Torre, mise à jour par Roland.
J'ai donc exploité ce code et l'ai remanié et un peu optimisé à ma sauce, pour utiliser l'algo "MiniMax Alpha-Beta pruning".
Dans l'ensemble, l'IA fonctionne et le moteur fonctionne assez bien pour un puissance 4.
Les deux gros problèmes :
- Si je modifie les règles du jeux, comme par exemple, le nombre de jeton à aligner (3 ou 5), alors l'IA devient assez "bête". Idem si je modifie la taille de la grille (Tant que c'est 4 jetons à aligner ça va)
- Si j'augment la profondeur de recherche des solutions par l'IA, au-delà de 6 les temps de résolution sont exponentiellement plus beaucoup, mais beaucoup plus long
Donc
- J'aimerai que l'IA s'adapte mieux en fonction des règles. Si vous avez des suggestions, une autre manière de faire je suis preneur de vos conseils.
- J'aimerai optimiser les temps de réflexion de l'IA.
Après pas mal de recherche sur le web, sur le sujet, il existe plusieurs manières :
table de transition avec des hashs, cache des coups déjà évalué dans une précédente analyse, utilisation de l'algo NegaMax ou variante NegaScout/MTD(f), réseaux de neurones.
Bref, pas mal de solutions et d'améliorations possibles différentes.
J'aimerai implémenter, dans un premier temps une table de transition, mais je ne sais pas encore trop comment les mettre en place, donc si vous avez des suggestions je suis preneur
J'allais oublier, j'ai également un petit soucis avec la méthode de vérification si un joueur gagne (surtout lorsque c'est le tour de l'IA) elle me renvois des "Faux" "Positif" par moment (L'IA ne gagne pas mais elle me dit que Oui) Ce comportement est assez aléatoire
Voila je pense avoir à peu près tout dit.
Je vous met le zip du projet de test. Il contient l’exécutable pour Win10 64bit si vous voulez faire quelques parties
Dans l'unité "P4AI.pas" vous trouverez également un série de liens en relation avec mes problématiques.
Merci d'avance de votre aide
Jérôme
Partager