AI - Minimax

L'algorithme minimax est un classique quand il s'agit d'optimiser une prise de décision. Comme souvent, c'est hyper simple à appliquer, et par forcément évident à comprendre et à en saisir l'essence (le plus simple si vous galérer, c'est de coder et expérimenter).

La principe est depuis une situation initiale qui oppose deux acteurs de déterminer quelle est la meilleure solution, au fur et à mesure des alternances d'action possible entre chaque opposant.

Au final cela conduit à construire un arbre alternant la sélection du maximum et du minimum...



Attention il s'agit d'un algorithme récursif. En partant de l'état initial on voit le nombre de choix qu'on a... puis ceux de l'adversaire, etc... Le but étant a terme d'évaluer le dernier choix et de le garder comme candidat possible ou le disqualifier, puis au final de trier le meilleur candidat. Bien sur on ne peut pas évaluer trop de coup en avance, comme pour le jeu de go, ou pour une partie complète la quantité de calcul à faire serait réellement astronomique au sens littéral du terme. Mais pour des jeux plus simples des prises de décision ou des négociations avec moins de choix cela marche très bien.

il faut aussi comprendre qu'on applique cet algorithme à chaque tour. Etant limité en nombre de coups possibles (en fonction de la capacité mémoire, mais aussi de sa fonction d'évaluation, on a un effet d'horizon. A chaque tour nous avançons dans l'arbre et nous repoussons notre horizon....

Au passage il est possible d'optimiser cela en appliquant des cutoffs (en ignorant certaines branches)

Ci dessous un GIF ANIME qui explique le minimax (c'est lent, mais lent mais bien, trop boonnnnn)


pour finir, voir aussi un exemple d’implémentation pour faire une IA pour le jeu d'échec :-)  




Références :

https://tonypoer.io/2016/10/28/implementing-minimax-and-alpha-beta-pruning-using-python/ 
https://en.wikipedia.org/wiki/Minimax
http://www.pressibus.org/ataxx/autre/minimax/node2.html

Commentaires

Articles les plus consultés