Minimax-algoritme

Den minimaks-algoritmen (også kalt MinMax algoritmen ) er en algoritme som gjelder for spillteori for to spillere null sum (og fullstendig informasjon) spill for å minimere den maksimale tap (dvs. si i verste tilfelle). For en stor familie av spill sikrer von Neumanns minimax-teorem eksistensen av en slik algoritme, selv om det i praksis ofte ikke er lett å finne det. Hex- spillet er et eksempel der eksistensen av en slik algoritme er etablert og viser at den første spilleren alltid kan vinne, uten at denne strategien er kjent.

Det får datamaskinen til å gå gjennom alle mulighetene for et begrenset antall trekk og tildele dem en verdi som tar hensyn til fordelene for spilleren og for motstanderen. Det beste valget er da det som minimerer tapet til spilleren mens han antar at motstanderen tvert imot søker å maksimere dem (spillet er med null sum).

Det er forskjellige algoritmer basert på MinMax for å optimalisere søket etter det beste trekket ved å begrense antall noder som er besøkt i spilletreetViltreet , den mest kjente er alfa-beta-beskjæring . I praksis er treet ofte for stort til å bli utforsket fullt ut (som i spillet sjakk eller gå ). Bare en brøkdel av treet blir deretter utforsket.

Når det gjelder veldig store trær, kan en AI (ekspertsystem, evaluering ved å lære av eksempler osv.) Brukes til å beskjære visse grener basert på et estimat av deres nytteverdi. Dette er det som brukes for eksempel i sammenheng med go.

Prinsipp

Minimax-algoritmen besøker spilletreet for å hente en verdi (kalt "spillverdi") som rekursivt beregnes som følger:

$minimax ( p ) = f ( p )$ hvis $p$ er et blad av treet der $f$ er en evalueringsfunksjon av spillets posisjon;
$minimax ( p ) = max (minimax ( O 1 ),\dots, minimax ( O n ))$ hvis $p$ er en spillernode med barn $O 1 ,\dots, O n$ ;
$minimax ( p ) = min (minimax ( O 1 ),\dots, minimax ( O n ))$ hvis $p$ er en motsatt node med barn $O 1 ,\dots, O n$ .

Eksempel

I diagrammet over representerer de grå nodene spillernodene og de blå motsetningene. For å bestemme verdien av node A, velger vi maksimumsverdien til settet med noder B (A er en spillernode). Det er derfor nødvendig å bestemme verdiene til nodene B som hver mottar minimumverdien lagret i sine barn (nodene B er imot). C-noder er blader, slik at verdien kan beregnes av evalueringsfunksjonen.

Node A tar derfor verdien 5. Spilleren må derfor spille trekket og bringe den til B2. Ved å observere treet forstår vi at algoritmen anser at motstanderen vil spille på en optimal måte: han tar minimum. Uten dette predikatet ville vi velge noden C 1 som gir størst gevinst, og neste valgte trekk vil føre til B1. Men så tar vi risikoen for at motstanderen spiller C3 som bare gir en gevinst på 3.

I praksis kan ikke den teoretiske verdien av stillingen P generelt beregnes. Følgelig vil verdsettelsesfunksjonen bli brukt på ikke-terminale posisjoner. Det vil bli vurdert at jo lenger evalueringsfunksjonen blir brukt fra roten, jo bedre blir resultatet av beregningen. Det vil si at ved å undersøke flere suksessive slag, antar vi å oppnå en bedre tilnærming av den teoretiske verdien, derfor et bedre valg av bevegelse.

Negamax forenkling

Hvis verdisettet tatt av $f ( p )$ er symmetrisk med hensyn til 0, kan en funksjon $g ( p )$ defineres slik at:

$g ( p ) = f ( p )$ hvis vi er på en spillernode
$g ( p ) = - f ( p )$ hvis vi er på en motsatt node

Så vi definerer negamax fra denne nye funksjonen:

$negamax ( p ) = g ( p )$ hvis P er terminal
$negamax ( p ) = max (-NegaMax ( p i ))$ ellers

Fra samme eksempel som for Minmax-algoritmen, er det resulterende treet:

Pseudokode

Pseudokoden til den begrensede dybde-minimaksalgoritmen er vist nedenfor:

function minimax(node, depth, maximizingPlayer) is if depth = 0 or node is a terminal node then return the heuristic value of node if maximizingPlayer then value := −∞ for each child of node do value := max(value, minimax(child, depth − 1, FALSE)) return value else (* minimizing player *) value := +∞ for each child of node do value := min(value, minimax(child, depth − 1, TRUE)) return value (* Initial call *) minimax(origin, depth, TRUE)

applikasjoner

Minimax og statistisk valgteori

I den statistiske valgteorien har vi en estimator $δ$ som tar sikte på å finne en parameter $θ \in Θ$ . I denne sammenheng, $θ$ 'minimax' hvis:

{\ displaystyle \ sup _ {\ theta} R (\ theta, {\ tilde {\ delta}}) = \ inf _ {\ delta} \ sup _ {\ theta} R (\ theta, \ delta).}

Beskjæring av Alpha-beta

Denne algoritmen kan optimaliseres gjennom implementeringen av teknikken kjent som alfa-beta beskjæring . Alfa-beta-algoritmen fremskynder minimax-søkerutinen ved å eliminere tilfeller som ikke vil bli brukt. Denne metoden bruker det faktum at alle andre nivåer i treet vil bli maksimert og alle andre nivåer vil bli minimert.

Vedlegg

Merknader

Jean-Marc Alliot og Thomas Schiex , “The programmering of games” , i kunstig intelligens og teoretisk databehandling , Cepadues,1994( ISBN 2-85428-324-4 )
Men hvis spillerne ikke kjenner trekkene som motstanderen spiller, som i steinsaks-spillet , fører denne algoritmen bare til strategier som krever bruk av sjanse; se artikkelen om teoremet for mer informasjon

Bibliografi

A. Aho , J. Hopcroft, J. Ullman , Datastrukturer og algoritmer , Paris, InterEditions,1987, 450 s. ( ISBN 978-2-7296-0194-2 , merknad BnF n o FRBNF34973701 ) , "Algoritmiske forestillinger og strategier"

Relaterte artikler

Ekstern lenke

(no) forklaring av minimax-algoritmen for tronspillet som en del av en google ai-utfordring