Minimaksalgoritme med alfa-beta beskæring

lige siden fremkomsten af kunstig intelligens (AI) har spillet været en af de mest interessante anvendelser af AI.

de første skakprogrammer blev skrevet af Claude Shannon og af Alan Turing i 1950, næsten så snart computere blev programmerbare.

spil som skak, tic-tac-toe og Go er interessante, fordi de tilbyder en ren abstraktion af konkurrencen mellem de to hære.

det er denne abstraktion, der gør spillet til et attraktivt område for AI-forskning.

i denne artikel vil vi gennemgå det grundlæggende i Minimaksalgoritmen sammen med algoritmens funktion.

vi vil også se på optimeringen af minimaksalgoritmen, alfa-beta beskæring.

hvad er minimaksalgoritmen?

Minimaks er en rekursiv algoritme, der bruges til at vælge et optimalt træk for en spiller, forudsat at den anden spiller også spiller optimalt.

det bruges i spil som tic-tac-toe, go, chess, Isola, checkers og mange andre to-spiller spil.

sådanne spil kaldes spil med perfekt information, fordi det er muligt at se alle mulige træk i et bestemt spil.

der kan være to-spiller spil, som ikke er af perfekt information som Scrabble, fordi modstanderens træk ikke kan forudsiges.

det ligner, hvordan vi tænker, når vi spiller et spil: “hvis jeg foretager dette træk, kan min modstander kun foretage disse træk,” og så videre.

Minimaks kaldes det, fordi det hjælper med at minimere tabet, når den anden spiller vælger den strategi, der har det maksimale tab.

terminologi

• Spiltræ: det er en struktur i form af et træ bestående af alle mulige træk, der giver dig mulighed for at flytte fra en tilstand af spillet til den næste tilstand.

et spil kan defineres som et søgeproblem med følgende komponenter:

• indledende tilstand: det omfatter bestyrelsens position og viser, hvis bevægelse det er.
• Efterfølgerfunktion: Det definerer, hvad de lovlige træk en spiller kan gøre er.
• Terminal tilstand: det er positionen af bestyrelsen, når spillet bliver over.
• hjælpefunktion: det er en funktion, der tildeler en numerisk værdi for resultatet af et spil. For eksempel i skak eller tic-tac-toe er resultatet enten en sejr, et tab eller en uafgjort, og disse kan repræsenteres af værdierne henholdsvis +1, -1 eller 0. Der er spil, der har et meget større udvalg af mulige resultater; for eksempel varierer hjælpeprogrammerne i backgammon fra +192 til -192. En hjælpefunktion kan også kaldes en payoff-funktion.

Hvordan fungerer algoritmen?

der er to spillere involveret i et spil, kaldet MIN og maks. Spilleren maks forsøger at få den højest mulige score, og MIN forsøger at få den lavest mulige score, dvs.min og maks forsøger at handle modsat hinanden.

den generelle proces med minimaksalgoritmen er som følger:

Trin 1: generer først hele spiltræet startende med den aktuelle position af spillet helt op til terminaltilstandene. Sådan ser spiltræet ud for spillet tic-tac-toe.

lad os forstå den definerede terminologi med hensyn til diagrammet ovenfor.

1. den oprindelige tilstand er det første lag, der definerer, at brættet er tomt, det er maks.
2. Efterfølgerfunktion viser alle mulige efterfølgerbevægelser. Det er defineret for alle lagene i træet.
3. Terminaltilstand er det sidste lag af træet, der viser den endelige tilstand, dvs.om spilleren maksimalt vinder, taber eller binder sig til modstanderen.
4. Hjælpeprogrammer i dette tilfælde for terminaltilstandene er 1, 0 og -1 som diskuteret tidligere, og de kan også bruges til at bestemme hjælpeprogrammerne for de andre noder.

Trin 2: Anvend hjælpefunktionen for at få hjælpeværdierne for alle terminaltilstande.
Trin 3: Bestem hjælpeprogrammerne for de højere noder ved hjælp af hjælpeprogrammerne i terminalnoderne. For eksempel i diagrammet nedenfor har vi hjælpeprogrammerne til terminaltilstandene skrevet i firkanterne.

lad os beregne værktøjet til venstre node(Rød) af laget over terminalen. Da det er bevægelsen af afspilleren MIN, vælger vi minimum af alle hjælpeprogrammer. I denne sag skal vi evaluere min{3, 5, 10}, som vi ved er helt sikkert 3. Så værktøjet til den røde knude er 3.

tilsvarende skal vi for den grønne knude i samme lag evaluere min{2,2}, som er 2.

Trin 4: Beregn hjælpeværdierne ved hjælp af blade, der overvejer et lag ad gangen indtil træets rod.
Trin 5: til sidst når alle de sikkerhedskopierede værdier til træets rod, dvs.det øverste punkt. På det tidspunkt skal maks vælge den højeste værdi.

i vores eksempel har vi kun 3 lag, så vi nåede straks til roden, men i faktiske spil vil der være mange flere lag og noder. Så vi er nødt til at evaluere maks{3,2}, som er 3.

derfor er den bedste åbningsbevægelse for maks. Dette træk kaldes minimaksbeslutningen, da det maksimerer værktøjet efter antagelsen om, at modstanderen også spiller optimalt for at minimere det.

for at opsummere,

Minimaksbeslutning = maks{min{3,5,10}, MIN{2,2}}
= maks{3,2}
= 3

Psuedocode:

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

Spiltræer er generelt meget tidskrævende at bygge, og det er kun for enkle spil, at det kan genereres på kort tid.

hvis der er \(b\) lovlige træk, dvs., \(b\) noder på hvert punkt, og træets maksimale dybde er \(m\), tidskompleksiteten af minimaksalgoritmen er af ordren \(b^m (O(b^m))\).

for at begrænse denne situation er der et par optimeringer, der kan føjes til algoritmen.

heldigvis er det levedygtigt at finde den faktiske minimaksbeslutning uden engang at se på hver knude i spiltræet. Derfor eliminerer vi knuder fra træet uden at analysere, og denne proces kaldes beskæring.

Alpha-beta beskæring

den metode, vi skal se i denne artikel, hedder alpha-beta beskæring.

hvis vi anvender alfa-beta beskæring til en standard minimaksalgoritme, returnerer den det samme træk som standard, men det fjerner (svesker) alle de noder, der muligvis ikke påvirker den endelige beslutning.

lad os først forstå intuitionen bag dette, og så formaliserer vi algoritmen. Antag, at vi har følgende spiltræ:

i dette tilfælde
Minimaksbeslutning = maks{MIN{3,5,10}, MIN{2, A, b}, min{2,7,3}}
= maks{3, c,2}
= 3

du ville blive overrasket!

hvordan kunne vi beregne maksimum med en manglende værdi? Her er tricket. MIN{2,A,b} ville helt sikkert være mindre end eller lig med 2, dvs.c<=2 og derfor skal maks{3, c,2} være 3.

spørgsmålet er nu, skal vi virkelig beregne c? Selvfølgelig ikke.

vi kunne have nået en konklusion uden at se på disse noder. Og det er her alfa-beta beskæring kommer ind i billedet.

et par definitioner:

Alpha: det er det bedste valg hidtil for spilleren maks. Vi ønsker at få den højest mulige værdi her.
Beta: Det er det bedste valg hidtil for MIN, og det skal være den lavest mulige værdi.

bemærk: hver node skal holde styr på sine alfa-og beta-værdier. Alpha kan kun opdateres, når det er maks tur, og på samme måde kan beta kun opdateres, når det er MIN chance.

Hvordan fungerer alfa-beta beskæring?

1. Initialiser alpha = -infinity og beta = infinity som de værst mulige tilfælde. Betingelsen for at beskære en knude er, når alfa bliver større end eller lig med beta.
2. Start med at tildele de oprindelige værdier af alpha og beta til root, og da alpha er mindre end beta, beskærer vi det ikke.
3. bær disse værdier af alfa og beta til barneknuden til venstre. Og nu fra nytteværdien af terminaltilstanden opdaterer vi værdierne for alpha og be, så vi behøver ikke at opdatere værdien af beta. Igen beskærer vi ikke, fordi tilstanden forbliver den samme. Tilsvarende er det tredje barn node også. Og så backtracking til roden sætter vi alpha=3, fordi det er den mindste værdi, som alpha kan have.
   
4. alfa=3 og beta = uendelig ved roden. Så vi beskærer ikke. Når vi bærer dette til centerknuden og beregner min{2, infinity}, får vi alfa=3 og beta=2.
5. beskær den anden og tredje barneknude, fordi alfa nu er større end beta.
6. Alfa ved roden forbliver 3, fordi den er større end 2. Når du bærer dette til højre barneknude,skal du evaluere min{infinity, 2}=2. Opdatering af beta til 2 og alfa forbliver 3.
7. beskær den anden og tredje barneknude, fordi alfa nu er større end beta.
8. derfor får vi henholdsvis 3, 2, 2 til venstre, midten og højre min-noder. Ved beregning af maks. {3,2,2} får vi 3. Derfor kunne vi uden at se på fire blade korrekt finde minimaksbeslutningen.

pseudokode (kilde: NPTEL kursus):

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

konklusion

spil er meget tiltalende, og det er måske endnu mere spændende at skrive spilprogrammer. Hvad Grand Price racing er for bilindustrien, spil er at AI.

ligesom vi ikke ville forvente en racerbil til at køre perfekt på en ujævn vej, bør vi ikke forvente spil spille algoritmer til at være perfekt til enhver situation.

så er minimaksalgoritmen. Det er måske ikke den bedste løsning på alle slags computerspil, der skal have AI.

men i betragtning af en god implementering kan det skabe en hård konkurrent.