Minimax (en)

The minimax algorithm is a classic when it comes to optimizing decision making. As often, it is super simple to apply, and necessarily obvious to understand and to grasp the essence (the simplest if you galore is to code and experiment).

The principle is since an initial situation that opposes two actors to determine what is the best solution, as and when alternating action possible between each opponent.

In the end, this leads to the construction of a tree alternating the selection of the maximum and the minimum ...



ONE Warning !  This is a recursive algorithm. Starting from the initial state we see the number of choices we have ... then those of the opponent, etc ... The goal being in the end to evaluate the last choice and to keep it as possible candidate or disqualify him, and finally sort out the best candidate. Of course we can not evaluate too many moves in advance, as for the game of go, or for a complete part the amount of calculation to do would be really astronomical in the literal sense of the term. But for simpler games of decision-making or negotiations with fewer choices it works very well.

we must also understand that we apply this algorithm every turn. Being limited in number of possible moves (depending on the memory capacity, but also its evaluation function, we have a horizon effect.) At each turn we advance in the tree and we push our horizon ....

By the way it is possible to optimize this by applying cutoffs (ignoring certain branches)

Below an ANIME GIF that explains the minimax (it's slow, but slow but good, "trop bon")



to finish, see also an example of implementation to make an AI for the chess game :-)




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

Posts les plus consultés de ce blog

Quand Google fait un KIT AI hyper débutant !!!

50 niveaux de RaspBerry Pi

Netflix AlphaGo - le documentaire à voir absolument