Lauri Hartikan askelohje yksinkertaisen shakkiälyn rakentamiseen

tutustutaan peruskäsitteisiin, joiden avulla voidaan luoda yksinkertainen shakkiäly:

move-Generation
Board evaluation
Minimax
ja alpha beta-karsinta.

jokaisessa vaiheessa parannamme algoritmiamme jollakin näistä ajan testaamista shakkiohjelmointitekniikoista. Näytän, miten kukin vaikuttaa algoritmin pelityyliin.

lopullisen TEKOÄLYALGORITMIN voit katsoa täältä Githubista.

Vaihe 1: Siirrä sukupolvi ja laudan visualisointi

käytämme shakkia.JS kirjasto move sukupolven, ja shakkilauta.js laudan visualisointiin. Move generation-kirjasto toteuttaa periaatteessa kaikki shakin säännöt. Tämän perusteella voimme laskea kaikki oikeudelliset siirrot tietylle hallituksen valtiolle.

move generation-funktion visualisointi. Lähtöasentoa käytetään syötteenä ja ulostulo on kaikki mahdolliset siirrot kyseisestä asennosta.

näiden kirjastojen käyttäminen auttaa meitä keskittymään vain kiinnostavimpaan tehtävään: parhaan siirron löytävän algoritmin luomiseen.

aloitamme luomalla funktion, joka vain palauttaa satunnaisen siirron kaikista mahdollisista siirroista:

vaikka tämä algoritmi ei ole kovin vankka shakinpelaaja, se on hyvä lähtökohta, koska voimme oikeasti pelata sitä vastaan:

Musta pelaa satunnaisia siirtoja. Pelattava https://jsfiddle.net/lhartikk/m14epfwb/4

Vaihe 2 : Aseman arviointi

nyt yritetään ymmärtää, kumpi puoli on vahvempi tietyssä asennossa. Yksinkertaisin tapa tämän saavuttamiseksi on laskea laudalla olevien kappaleiden suhteellinen vahvuus seuraavan taulukon avulla:

arviointifunktion avulla voidaan luoda algoritmi, joka valitsee korkeimman arvion antavan liikkeen:

ainoa konkreettinen parannus on se, että algoritmimme nappaa nyt palan, jos se voi.

Musta pelaa yksinkertaisen arviointifunktion avulla. Pelattava https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Vaihe 3: Hakupuu käyttäen Minimaxia

seuraavaksi luomme hakupuun, josta algoritmi voi valita parhaan siirron. Tämä tapahtuu Minimax-algoritmin avulla.

tässä algoritmissa kaikkien mahdollisten siirtojen rekursiivinen puu tutkitaan tiettyyn syvyyteen, ja sijainti arvioidaan puun päätteessä ”lehdet”.

tämän jälkeen palautetaan joko lapsen pienin tai suurin arvo vanhempaan solmuun riippuen siitä, onko siirrettävänä valkoinen vai musta. (Eli pyrimme joko minimoimaan tai maksimoimaan lopputuloksen kullakin tasolla.)

minimax-algoritmin visualisointi keinotekoisessa asennossa. Paras siirto valkealle on B2-c3, koska voimme taata, että pääsemme tilanteeseen, jossa arviointi on -50

minimaxin ollessa käytössä, algoritmimme alkaa ymmärtää jotain shakin perustaktiikkaa:

Minimax syvyystasolla 2. Pelattavaa: https://jsfiddle.net/k96eoq0q/1/

minimax-algoritmin tehokkuus perustuu vahvasti saavutettavaan hakusyvyyteen. Tätä parannamme seuraavassa vaiheessa.

Vaihe 4: Alfa-beeta-karsinta

alfa-beeta-karsinta on minimax-algoritmiin perustuva optimointimenetelmä, jonka avulla voidaan jättää joitakin hakupuun oksia huomiotta. Tämä auttaa meitä arvioimaan minimax – hakupuuta paljon syvemmin, samalla kun käytämme samoja resursseja.

Alfa-beta-karsinta perustuu tilanteeseen, jossa voimme lopettaa hakupuun osan arvioinnin, jos löydämme siirron, joka johtaa huonompaan tilanteeseen kuin aiemmin löydetty siirto.

alfa-beeta — karsinta ei vaikuta minimax-algoritmin lopputulokseen-se vain nopeuttaa sitä.

Alfa-beta-algoritmi on myös tehokkaampi, jos satumme käymään ensin ne polut, jotka johtavat hyviin liikkeisiin.

kantoja ei tarvitse tutkia, jos alfa-beta-karsintaa käytetään ja puussa käydään kuvatussa järjestyksessä.

Alfa-beetalla saadaan merkittävä lisäpanostus minimax-algoritmiin, kuten seuraavasta esimerkistä käy ilmi:

niiden paikkojen lukumäärä, joita tarvitaan arvioitaessa, jos haluamme suorittaa haun syvyydellä 4 ja ”juuri” – asema on se, joka esitetään.

seuraa tätä linkkiä ja kokeile shakin tekoälyn alfa-beta-paranneltua versiota.

Vaihe 5: parannettu arviointifunktio

alustava arviointifunktio on melko naiivi, sillä laskemme vain taululta löytyvän materiaalin. Tämän parantamiseksi lisäämme arviointiin tekijän, joka ottaa huomioon palasten sijainnin. Esimerkiksi ratsu laudan keskellä on parempi (koska siinä on enemmän vaihtoehtoja ja se on siten aktiivisempi) kuin ratsu laudan reunalla.

käytämme hieman muokattua versiota nappularuudullisista taulukoista, jotka on alun perin kuvattu Shakki-ohjelmointi-wikissä.

visualisoidut pala-neliötaulukot. Arviota voidaan pienentää tai lisätä kappaleen sijainnista riippuen.

seuraavan parannuksen myötä alamme saada algoritmia, joka pelaa jotain ”kunnollista” shakkia ainakin satunnaisen pelaajan näkökulmasta:

paransi arviointia ja alfa-beta-karsintaa hakusyvyydellä 3. Pelattava https://jsfiddle.net/q76uzxwe/1/

johtopäätökset

yksinkertaisenkin shakkia pelaavan algoritmin vahvuus on se, ettei se tee tyhmiä virheitä. Tämä sanoi, että siltä puuttuu vielä strateginen ymmärrys.

täällä esittelemilläni menetelmillä olemme pystyneet ohjelmoimaan shakkia pelaavan algoritmin, jolla voi pelata perusshakkia. Lopullisen algoritmin” AI-osa ” (move-generation poislukien) on vain 200 riviä koodia, eli peruskäsitteet ovat melko yksinkertaisia toteuttaa. Voit tarkistaa lopullinen versio on GitHub.

joitakin lisäparannuksia, joita algoritmiin voitaisiin tehdä, olisivat esimerkiksi:

siirtojärjestys
nopeampien siirtojen luominen
ja loppupelikohtainen arviointi.

KGSAU