Minimax algoritm med alfa-beta beskärning

ända sedan tillkomsten av artificiell intelligens (AI), har spelande varit en av de mest intressanta tillämpningar av AI.

de första schackprogrammen skrevs av Claude Shannon och av Alan Turing 1950, nästan så snart datorerna blev programmerbara.

spel som schack, tic-Tac-toe och Go är intressanta eftersom de erbjuder en ren abstraktion av konkurrensen mellan de två härarna.

det är denna abstraktion som gör spelet ett attraktivt område för AI-forskning.

i den här artikeln kommer vi att gå igenom grunderna i Minimax-algoritmen tillsammans med algoritmens funktion.

vi kommer också att titta på optimeringen av minimax-algoritmen, alfa-beta beskärning.

Vad är Minimax-algoritmen?

Minimax är en rekursiv algoritm som används för att välja ett optimalt drag för en spelare förutsatt att den andra spelaren också spelar optimalt.

det används i spel som tic-Tac-toe, go, chess, Isola, checkers och många andra tvåspelarspel.

sådana spel kallas spel med perfekt information eftersom det är möjligt att se alla möjliga drag i ett visst spel.

det kan finnas två spelare spel som inte är av perfekt information som Scrabble eftersom motståndarens drag inte kan förutsägas.

det liknar hur vi tänker när vi spelar ett spel: ”om jag gör detta drag, kan min motståndare bara göra bara dessa drag” och så vidare.

Minimax kallas så eftersom det hjälper till att minimera förlusten när den andra spelaren väljer strategin med maximal förlust.

terminologi

• spelträd: det är en struktur i form av ett träd som består av alla möjliga drag som gör att du kan flytta från ett tillstånd av spelet till nästa tillstånd.

ett spel kan definieras som ett sökproblem med följande komponenter:

• ursprungligt tillstånd: det innefattar styrelsens position och visar vems drag det är.
• efterföljande funktion: Den definierar vad de juridiska drag en spelare kan göra är.
• terminaltillstånd: det är styrelsens position när spelet blir över.
• Utility funktion: Det är en funktion som tilldelar ett numeriskt värde för resultatet av ett spel. Till exempel i schack eller tic-Tac-toe är resultatet antingen en vinst, en förlust eller en rita, och dessa kan representeras av värdena +1, -1 respektive 0. Det finns spel som har ett mycket större utbud av möjliga resultat; till exempel varierar verktygen i backgammon från +192 till -192. En verktygsfunktion kan också kallas en utbetalningsfunktion.

hur fungerar algoritmen?

det finns två spelare som är involverade i ett spel, kallat MIN och MAX. Spelaren MAX försöker få högsta möjliga poäng och MIN försöker få lägsta möjliga poäng, dvs min och MAX försöker agera mittemot varandra.

den allmänna processen för Minimax-algoritmen är som följer:

Steg 1: generera först hela spelträdet som börjar med spelets nuvarande position hela vägen upp till terminaltillstånden. Så här ser spelträdet ut för spelet tic-Tac-toe.

Låt oss förstå den definierade terminologin i termer av diagrammet ovan.

1. det ursprungliga tillståndet är det första lagret som definierar att brädet är tomt, det är Maxs tur att spela.
2. efterföljande funktion listar alla möjliga efterföljande drag. Det definieras för alla lager i trädet.
3. terminaltillstånd är det sista lagret i trädet som visar det slutliga tillståndet, dvs om spelaren MAX vinner, förlorar eller knyter till motståndaren.
4. verktyg i detta fall för terminaltillstånden är 1, 0 och -1 som diskuterats tidigare, och de kan användas för att bestämma verktygen för de andra noderna också.

steg 2: Använd verktygsfunktionen för att få verktygsvärdena för alla terminaltillstånd.
steg 3: Bestäm verktygen för de högre noderna med hjälp av verktygen för terminalnoderna. I diagrammet nedan har vi till exempel verktygen för terminalstaterna skrivna i rutorna.

låt oss beräkna verktyget för den vänstra noden(Röd) av skiktet ovanför terminalen. Eftersom det är flytten av spelaren MIN, vi kommer att välja ett minimum av alla verktyg. För det här fallet måste vi utvärdera min{3, 5, 10}, vilket vi vet är verkligen 3. Så verktyget för den röda noden är 3.

på samma sätt, för den gröna noden i samma lager, måste vi utvärdera MIN{2,2} vilket är 2.

Steg 4: Beräkna verktygsvärdena med hjälp av löv med tanke på ett lager i taget tills trädets rot.
Steg 5: så småningom når alla säkerhetskopierade värden till trädets rot, dvs den översta punkten. Vid den tiden måste MAX välja det högsta värdet.

i vårt exempel har vi bara 3 lager så vi nådde omedelbart till roten men i faktiska spel kommer det att finnas många fler lager och noder. Så vi måste utvärdera MAX{3,2} vilket är 3.

därför är den bästa öppningsrörelsen för MAX den vänstra noden(eller den röda). Detta drag kallas minimax-beslutet eftersom det maximerar verktyget efter antagandet att motståndaren också spelar optimalt för att minimera det.

för att sammanfatta,

Minimax beslut = MAX{MIN{3,5,10}, MIN{2,2}}
= MAX{3,2}
= 3

Psuedokod:

function minimax(node, depth, maximizingPlayer) if depth = 0 or node is a terminal node return the utility of the node if maximizingPlayer bestValue := ?? for each child of node v := minimax(child, depth ? 1, FALSE) bestValue := max(bestValue, v) return bestValue else (* minimizing player *) bestValue := +? for each child of node v := minimax(child, depth ? 1, TRUE) bestValue := min(bestValue, v) return bestValue

optimering

spelträd är i allmänhet mycket tidskrävande att bygga, och det är bara för enkla spel att det kan genereras på kort tid.

om det finns \(b\) lagliga drag, dvs.,\ (b\) noder vid varje punkt och trädets maximala djup är\ (m\), tidskomplexiteten för minimax-algoritmen är av ordningen\(b^m(o (b^m))\).

för att begränsa denna situation finns det några optimeringar som kan läggas till algoritmen.

lyckligtvis är det lönsamt att hitta det faktiska minimax-beslutet utan att ens titta på varje nod i spelträdet. Därför eliminerar vi noder från trädet utan att analysera, och denna process kallas beskärning.

alfa-beta beskärning

metoden som vi ska titta på i den här artikeln kallas alfa-beta beskärning.

om vi tillämpar alfa-beta beskärning till en standard minimax algoritm, returnerar den samma drag som standard, men det tar bort (prunes) alla noder som eventuellt inte påverkar det slutliga beslutet.

Låt oss förstå intuitionen bakom detta först och sedan kommer vi att formalisera algoritmen. Antag att vi har följande spelträd:

i detta fall
Minimax beslut = MAX{MIN{3,5,10}, MIN{2, a, b}, MIN{2,7,3}}
= MAX{3, c,2}
= 3

du skulle bli förvånad!

Hur kan vi beräkna det maximala med ett saknat värde? Här är tricket. MIN{2,a, b} skulle säkert vara mindre än eller lika med 2, dvs c<=2 och därmed MAX{3, c,2} måste vara 3.

frågan är nu behöver vi verkligen beräkna c? Självklart inte.

vi kunde ha nått en slutsats utan att titta på dessa noder. Och det är här alfa-beta beskärning kommer in i bilden.

några definitioner:

Alfa: det är det bästa valet hittills för spelaren MAX. Vi vill få högsta möjliga värde här.
Beta: Det är det bästa valet hittills för MIN, och det måste vara det lägsta möjliga värdet.

Obs: varje nod måste hålla reda på dess alfa-och betavärden. Alpha kan uppdateras endast när det är MAX tur och, liknande, beta kan uppdateras endast när det är MIN chans.

hur fungerar alfa-beta beskärning?

1. initiera alfa = -oändlighet och beta = oändlighet som värsta möjliga fall. Villkoret att beskära en nod är när Alfa blir större än eller lika med beta.
2. börja med att tilldela initialvärdena för alfa och beta till rot och eftersom alfa är mindre än beta Beskär vi inte det.
3. bär dessa värden av alfa och beta till barnnoden till vänster. Och nu från nyttjandevärdet för terminaltillståndet kommer vi att uppdatera värdena för alpha och be, så vi behöver inte uppdatera värdet på beta. Återigen Beskär vi inte eftersom tillståndet förblir detsamma. På samma sätt, den tredje barnnoden också. Och sedan backtracking till roten ställer vi alfa=3 eftersom det är det minsta värdet som alfa kan ha.
   
4. nu, alfa = 3 och beta=oändlighet vid roten. Så vi Beskär inte. Genom att bära detta till mittnoden och beräkna MIN{2, oändlighet} får vi alfa=3 och beta=2.
5. Beskär andra och tredje barnnoden eftersom alfa nu är större än beta.
6. Alfa vid roten förblir 3 eftersom den är större än 2. Bär detta till den högsta barnnoden, utvärdera MIN{oändlighet, 2} = 2. Uppdatera beta till 2 och alfa förblir 3.
7. Beskär andra och tredje barnnoden eftersom alfa nu är större än beta.
8. därför får vi 3, 2, 2 till vänster, mitt och höger min noder. Och beräknar MAX{3,2,2}, vi får 3. Därför, utan att ens titta på fyra löv, kunde vi korrekt hitta minimax-beslutet.

pseudokod (källa: NPTEL kurs):

evaluate (node, alpha, beta) if node is a leaf return the utility value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return beta return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return alpha return alpha

slutsats

spel är mycket tilltalande och att skriva spelprogram är kanske ännu mer spännande. Vad Grand Prix racing är att bilindustrin, spelande är att AI.

precis som vi inte förväntar oss att en racerbil ska springa perfekt på en ojämn väg, borde vi inte förvänta oss att spelalgoritmer är perfekta för varje situation.

så är minimax-algoritmen. Det kanske inte är den bästa lösningen för alla typer av dataspel som behöver ha AI.

men med tanke på en bra implementering kan det skapa en tuff konkurrent.