Minimax-algoritmi Alfa-beta-karsinnalla

tekoälyn (AI) tulemisesta lähtien pelien pelaaminen on ollut yksi kiinnostavimmista tekoälyn sovelluksista.

ensimmäiset shakkiohjelmat kirjoittivat Claude Shannon ja Alan Turing vuonna 1950, lähes heti tietokoneiden tultua ohjelmoitaviksi.

pelit kuten shakki, tic-tac-toe ja Go ovat mielenkiintoisia, koska ne tarjoavat puhtaan abstraktion kahden armeijan välisestä kilpailusta.

juuri tämä abstraktio tekee pelaamisesta houkuttelevan alueen TEKOÄLYTUTKIMUKSELLE.

tässä artikkelissa käydään läpi Minimax-algoritmin perusteet algoritmin toiminnan ohella.

tarkastelemme myös minimax-algoritmin optimointia, alfa-beta-karsintaa.

mikä on Minimax-algoritmi?

Minimax on rekursiivinen algoritmi, jolla valitaan pelaajalle optimaalinen siirto olettaen, että myös toinen pelaaja pelaa optimaalisesti.

sitä käytetään muun muassa tic-tac-toe -, go -, Shakki -, Isola -, tammi-ja monissa muissa kahden pelaajan peleissä.

tällaisia pelejä kutsutaan täydellisen tiedon peleiksi, koska on mahdollista nähdä kaikki tietyn pelin mahdolliset siirrot.

voi olla kahden pelaajan pelejä, joista ei ole täydellistä tietoa, kuten Scrabble, koska vastustajan siirtoa ei voi ennustaa.

on samantapaista, miten ajattelemme peliä pelatessamme: ”jos teen tämän liikkeen, niin vastustajani voi tehdä vain näitä liikkeitä” ja niin edelleen.

Minimaxia kutsutaan niin, koska se auttaa minimoimaan tappion, kun toinen pelaaja valitsee strategian, jolla on suurin tappio.

terminologia

• Pelipuu: se on puun muotoinen rakenne, joka koostuu kaikista mahdollisista siirroista, joiden avulla voi siirtyä pelin tilasta seuraavaan tilaan.

peli voidaan määritellä hakuongelmaksi seuraavilla komponenteilla:

• alkutila: se sisältää kannan hallituksen ja osoittaa, kenen liikkua se on.
• Seuraajafunktio: Se määrittelee, Mitä laillisia siirtoja pelaaja voi tehdä.
• Terminaalitila: se on laudan asema, kun peli loppuu.
• Hyötyfunktio: se on funktio, joka antaa numeerisen arvon pelin lopputulokselle. Esimerkiksi shakissa tai tic-tac-toessa tulos on joko voitto, tappio tai tasapeli, ja näitä voidaan esittää vastaavasti arvoilla +1, -1 tai 0. On pelejä, joilla on paljon suurempi valikoima mahdollisia tuloksia; esimerkiksi backgammonin apuohjelmat vaihtelevat +192: sta -192: een. Hyödyllisyysfunktiota voidaan kutsua myös payoff-funktioksi.

miten algoritmi toimii?

pelissä on mukana kaksi pelaajaa, nimeltään MIN ja MAX. Pelaaja MAX yrittää saada korkeimman mahdollisen pistemäärän ja MIN yrittää saada pienimmän mahdollisen pistemäärän, eli MIN ja MAX yrittävät toimia vastakkain.

Minimax-algoritmin yleinen prosessi on seuraava:

Vaihe 1: luo ensin koko pelipuu alkaen pelin nykyisestä sijainnista aina päätetiloihin saakka. Tältä riistapuu näyttää pelissä tic-tac-toe.

Ymmärtäkäämme yllä olevan kaavion määrittelemä termistö.

1. alkutila on ensimmäinen taso, joka määrittelee, että levy on tyhjä on Maxin vuoro pelata.
2. Seuraajafunktio listaa kaikki mahdolliset seuraajasiirrot. Se määritellään kaikille puun kerroksille.
3. Terminaalitila on puun viimeinen kerros, joka näyttää lopullisen tilan eli sen, voittaako, häviääkö pelaaja MAX vai sitooko hän vastustajan.
4. tässä tapauksessa Päätetilojen apuohjelmat ovat 1, 0 ja -1, kuten aiemmin mainittiin, ja niiden avulla voidaan määrittää myös muiden solmujen apuohjelmat.

Vaihe 2: Käytä utility-toimintoa saadaksesi apuohjelman arvot kaikille päätetiloille.
Vaihe 3: määritetään ylempien solmujen apuohjelmat päätesolmujen apuohjelmien avulla. Esimerkiksi alla olevassa kaaviossa, meillä on apuohjelmia terminaalin valtioiden kirjoitettu neliöt.

Lasketaanpa päätelaitteen yläpuolella olevan kerroksen vasemman solmun(punainen) apuohjelma. Koska se on siirto pelaaja MIN, valitsemme vähintään kaikki apuohjelmia. Tässä tapauksessa meidän on arvioitava MIN{3, 5, 10}, jonka tiedämme olevan varmasti 3. Joten apuohjelma punainen solmu on 3.

vastaavasti saman kerroksen vihreälle solmulle joudumme arvioimaan MIN{2,2} , joka on 2.

Vaihe 4: Laske hyötyarvot lehtien avulla harkiten kerros kerrallaan puun juureen asti.
Vaihe 5: lopulta kaikki varmistuneet arvot ulottuvat puun juureen eli ylimpään pisteeseen. Siinä vaiheessa Maxin on valittava korkein arvo.

esimerkissämme meillä on vain 3 kerrosta, joten pääsimme heti juureen, mutta varsinaisissa peleissä kerroksia ja solmuja tulee paljon lisää. Meidän on siis arvioitava MAX{3,2} , joka on 3.

näin ollen paras avausliike Maxille on vasen solmu(tai punainen). Tätä siirtoa kutsutaan minimax-päätökseksi, koska se maksimoi hyödyllisyyden olettaen, että vastustaja pelaa myös optimaalisesti minimoidakseen sen.

yhteenvetona,

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

Psuedokoodi:

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

optimointi

Pelipuut ovat yleensä hyvin aikaa vieviä rakentaa, ja vain yksinkertaisiin peleihin se voidaan luoda lyhyessä ajassa.

jos on \(B\) laillisia siirtoja, ts., \(b\) solmut kussakin pisteessä ja puun suurin syvyys on \(m\), minimax-algoritmin ajallinen monimutkaisuus on luokkaa \(B^M (O(B^M))\).

tilanteen hillitsemiseksi algoritmiin voidaan lisätä muutama optimointi.

onneksi on mahdollista löytää varsinainen minimax-päätös katsomatta edes pelipuun jokaista solmua. Siksi poistamme solmut puusta analysoimatta, ja tätä prosessia kutsutaan karsimiseksi.

alfa-beeta-karsinta

tässä artikkelissa käsiteltävää menetelmää kutsutaan alfa-beeta-karsinnaksi.

jos sovellamme alfa-beta-karsintaa standardiin minimax-algoritmiin, se palauttaa saman liikkeen kuin standardi, mutta poistaa (karsii) kaikki solmut, jotka eivät mahdollisesti vaikuta lopulliseen päätökseen.

Ymmärtäkäämme ensin intuitio tämän takana ja sitten virallistamme algoritmin. Oletetaan, että meillä on seuraava pelipuu:

tässä tapauksessa
Minimax Decision = MAX{MIN{3,5,10}, MIN{2, a, B}, MIN{2,7,3}}
= MAX{3, c,2}
= 3

yllättyisit!

miten voisimme laskea maksimin puuttuvalla arvolla? Tässä on juju. MIN{2, a, B} olisi varmasti pienempi tai yhtä suuri kuin 2, eli c<=2 ja näin ollen MAX{3, c,2} on oltava 3.

kysymys kuuluu nyt, pitääkö c todella laskea? En tietenkään.

olisimme voineet tehdä johtopäätöksen katsomatta noita solmuja. Tässä kohtaa kuvaan astuu alfa-beta-karsinta.

muutama määritelmä:

Alpha: se on toistaiseksi paras valinta pelaaja Maxille. Haluamme saada täällä mahdollisimman suuren arvon.
beeta: Se on paras valinta tähän mennessä MIN, ja sen on oltava pienin mahdollinen arvo.

Huomautus: jokaisen solmun on pidettävä kirjaa alfa-ja beeta-arvoistaan. Alpha voidaan päivittää vain, kun on Maxin vuoro, ja vastaavasti beta voidaan päivittää vain, kun se on Minin mahdollisuus.

miten alfa-beta-karsinta vaikuttaa?

1. alustetaan alfa = -äärettömyys ja beta = äärettömyys pahimpina mahdollisina tapauksina. Ehtona solmun karsimiselle on, että alfa on suurempi tai yhtä suuri kuin beta.
2. Aloita antamalla alkuarvot alfa ja beta juurelle ja koska alfa on pienempi kuin beeta, emme karsi sitä.
3. siirrä nämä alfa-ja beeta-arvot vasemmalla olevaan lapsisolmuun. Ja nyt päätetilan hyötyarvosta päivitämme alfa-ja be-arvot, joten meidän ei tarvitse päivittää beta-arvoa. Taaskaan emme karsi, koska tila pysyy samana. Samoin kolmannen lapsen solmu myös. Ja sitten takaisin juureen asetamme alfa=3, koska se on pienin arvo, että alfa voi olla.
   
4. alfa=3 ja beta=ääretön juuressa. Emme siis karsi. Kun tämä viedään keskussolmuun ja lasketaan MIN{2, infinity}, saadaan alpha=3 ja beta=2.
5. Karsi toisen ja kolmannen lapsen solmut, koska alfa on nyt suurempi kuin beeta.
6. Alfa juuressa pysyy 3, koska se on suurempi kuin 2. Vie tämä oikeanpuoleisimpaan lapsisolmuun, arvioi MIN{infinity,2}=2. Päivitä beta 2: een ja alpha pysyy 3: ssa.
7. Karsi toisen ja kolmannen lapsen solmut, koska alfa on nyt suurempi kuin beeta.
8. näin saadaan 3, 2, 2 vasemmalla, keskellä ja oikealla MIN solmut vastaavasti. Ja laskemalla MAX{3,2,2}, saamme 3. Näin ollen, edes katsomatta neljä lehdet voisimme oikein löytää minimax päätös.

pseudokoodi (lähde: NPTEL-kurssi):

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

johtopäätös

Pelit vetävät hyvin ja peliohjelmien kirjoittaminen on ehkä vielä jännittävämpää. Mitä Grand Prix-kilpa on autoteollisuudelle, peli on tekoälylle.

aivan kuten emme odottaisi kilpa-auton kulkevan täydellisesti kuoppaisella tiellä, emme myöskään odottaisi pelialgoritmien olevan täydellisiä jokaiseen tilanteeseen.

niin on minimax-algoritmi. Se ei välttämättä ole paras ratkaisu kaikenlaisiin tietokonepeleihin, joissa pitää olla tekoäly.

, mutta hyvällä toteutuksella se voi luoda kovan kilpailijan.