TechCodeview

• L'algoritme Mini-max és un algorisme recursiu o de retrocés que s'utilitza en la presa de decisions i la teoria de jocs. Proporciona un moviment òptim per al jugador assumint que l'oponent també està jugant de manera òptima.
• L'algoritme Mini-Max utilitza la recursió per cercar a través de l'arbre del joc.
• L'algoritme Min-Max s'utilitza principalment per jugar en IA. Com ara escacs, dames, tic-tac-toe, go i diversos jocs de jugadors de remolc. Aquest algorisme calcula la decisió minimax per a l'estat actual.
• En aquest algorisme hi juguen dos jugadors, un s'anomena MAX i l'altre MIN.
• Ambdós jugadors lluiten ja que el jugador oponent obté el benefici mínim mentre que ells obtenen el màxim benefici.
• Els dos jugadors del joc s'oposen l'un a l'altre, on MAX seleccionarà el valor maximitzat i MIN seleccionarà el valor minimitzat.
• L'algoritme minimax realitza un algorisme de cerca en profunditat per a l'exploració de l'arbre del joc complet.
• L'algoritme minimax continua fins al node terminal de l'arbre, i després fa marxa enrere de l'arbre com a recursivitat.

Pseudocodi per a l'algoritme MinMax:

 function minimax(node, depth, maximizingPlayer) is if depth ==0 or node is a terminal node then return static evaluation of node if MaximizingPlayer then // for Maximizer Player maxEva= -infinity for each child of node do eva= minimax(child, depth-1, false) maxEva= max(maxEva,eva) //gives Maximum of the values return maxEva else // for Minimizer player minEva= +infinity for each child of node do eva= minimax(child, depth-1, true) minEva= min(minEva, eva) //gives minimum of the values return minEva 

Trucada inicial:

Mínima màxima (node, 3, cert)

Funcionament de l'algoritme Min-Max:

• El funcionament de l'algorisme minimax es pot descriure fàcilment mitjançant un exemple. A continuació hem pres un exemple d'arbre de joc que representa el joc de dos jugadors.
• En aquest exemple, hi ha dos jugadors, un s'anomena Maximizer i l'altre Minimizer.
• Maximizer intentarà obtenir la puntuació màxima possible i Minimizer intentarà obtenir la puntuació mínima possible.
• Aquest algorisme aplica DFS, de manera que en aquest arbre de joc, hem de recórrer tot el camí per les fulles per arribar als nodes terminals.
• Al node terminal, es donen els valors del terminal, de manera que compararem aquests valors i retrocedirem l'arbre fins que es produeixi l'estat inicial. A continuació es mostren els passos principals per resoldre l'arbre de joc de dos jugadors:

Pas 1: En el primer pas, l'algoritme genera tot l'arbre del joc i aplica la funció d'utilitat per obtenir els valors d'utilitat per als estats terminals. Al diagrama d'arbre següent, prenem que A és l'estat inicial de l'arbre. Suposem que el maximitzador pren el primer torn que té el pitjor valor inicial =- infinit, i el minimitzador farà el següent torn que té el pitjor valor inicial = + infinit.

Pas 2: Ara, primer trobem el valor d'utilitats del Maximizer, el seu valor inicial és -∞, així que compararem cada valor en estat terminal amb el valor inicial del Maximizer i determinarem els valors dels nodes més alts. Trobarà el màxim entre tots.

• Per al node D max(-1,- -∞) => max(-1,4)= 4
• Per al node E max(2, -∞) => max(2, 6)= 6
• Per al node F max(-3, -∞) => max(-3,-5) = -3
• Per al node G max(0, -∞) = max(0, 7) = 7

Pas 3: En el següent pas, és un torn per al minimitzador, de manera que compararà el valor de tots els nodes amb +∞ i trobarà el 3^rdvalors dels nodes de capa.

• Per al node B= min(4,6) = 4
• Per al node C= min (-3, 7) = -3

Pas 4: Ara és el torn de Maximizer, i tornarà a triar el valor màxim de tots els nodes i trobarà el valor màxim per al node arrel. En aquest arbre de joc, només hi ha 4 capes, per tant arribem immediatament al node arrel, però en els jocs reals, hi haurà més de 4 capes.

• Per al node A màx (4, -3)= 4

Aquest va ser el flux de treball complet del joc minimax de dos jugadors.

Propietats de l'algorisme Mini-Max:

Completa-L'algoritme Min-Max està complet. Definitivament trobarà una solució (si n'hi ha), a l'arbre de cerca finit.òptim-L'algoritme Min-Max és òptim si els dos oponents juguen de manera òptima.complexitat temporal-Com que realitza DFS per a l'arbre del joc, la complexitat temporal de l'algorisme Min-Max és O (b^m) , on b és el factor de ramificació de l'arbre de joc, i m és la profunditat màxima de l'arbre.Complexitat espacial-La complexitat espacial de l'algoritme Mini-max també és similar a la de DFS Sobre .

Limitació de l'algoritme minimax:

El principal inconvenient de l'algoritme minimax és que es fa molt lent per a jocs complexos com ara escacs, go, etc. Aquest tipus de jocs té un gran factor de ramificació i el jugador té moltes opcions per decidir. Aquesta limitació de l'algoritme minimax es pot millorar poda alfa-beta que hem comentat en el següent tema.