Discussion :

[BeanzMaster]

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

1. 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.
2. 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

[Roland Chastain]

Bonjour Jérôme !

Je viens seulement de voir ton message. J'aimerais bien t'aider mais mes compétences sont assez limitées dans le domaine. Pour moi, arriver à faire un programme qui me bat si je joue au hasard, et qui peut faire un grand nombre de parties sans se planter, est déjà une satisfaction. Mes ambitions ne sont jamais vraiment allées au-delà. Les programmes que j'ai faits utilisent un algorithme très basique, avec une profondeur de recherche fixe. Les techniques sophistiquées dont tu parles, je les connais de nom mais pas plus.

Il y a dans la rubrique sources du forum C les petits programmes de Bernard Helmstetter qui sont très bien faits, et qui pourraient peut-être t'inspirer :

• Morpion minimax
• Morpion negamax
• Morpion élagage alpha-beta
• Othello negamax

J'avais traduit les deux premiers en Pascal. Je les mets en pièces jointes (quoique je ne doute pas que tu saches lire le C).

Autrement, si tu veux creuser le sujet, tu pourrais peut-être regarder le code de quelques moteurs d'échecs. Par exemple Booot, qui est écrit en Pascal, et qui est très fort.

Je regarderai ton source dès que possible.

Voilà, bonne chance !

[BeanzMaster]

Bonjour Roland,

merci pour les liens je vais regarder ça de plus près. Les deux derniers code en C et le moteur d'échec on l'air intéressant.
Mon but final, est d'avoir une classe généraliste qu'il suffirait d'hériter et ou on surchargerai les méthodes de décisions pour s'adapter aux différents type de jeu.

A+

Jérôme