Vaiheittainen opas yksinkertaisen shakki-tekoälyn rakentamiseen

Tutkitaan joitain peruskäsitteitä, jotka auttavat meitä luomaan yksinkertaisen shakin tekoälyn:

  • liikkua sukupolvi
  • hallituksen arviointi
  • minimx
  • ja alfa-beeta-karsiminen.

Parannamme jokaisessa vaiheessa algoritmiamme yhdellä näistä testatuista shakkiohjelmointitekniikoista. Esittelen, kuinka kukin vaikuttaa algoritmin pelityyliin.

Voit tarkastella lopullista tekoälyn algoritmia täällä GitHubissa.

Vaihe 1: Siirrä sukupolven ja piirilevyn visualisointi

Käytämme chess.js-kirjastoa siirron luomiseen ja chessboard.js taulun visualisointiin. Siirrä sukupolven kirjasto toteuttaa periaatteessa kaikki shakin säännöt. Tämän perusteella voimme laskea kaikki lailliset siirrot tietylle hallituksen tilalle.

Näiden kirjastojen käyttäminen auttaa meitä keskittymään vain mielenkiintoisimpaan tehtävään: luomaan algoritmin, joka löytää parhaan liikkeen.

Aloitamme luomalla toiminnon, joka palauttaa vain satunnaisen siirron kaikista mahdollisista liikkeistä:

Vaikka tämä algoritmi ei ole kovin vakaa shakkipelaaja, se on hyvä lähtökohta, koska voimme itse asiassa pelata sitä vastaan:

Vaihe 2: Sijoituksen arviointi

Yritetään nyt ymmärtää, mikä puoli on vahvempi tietyssä asennossa. Yksinkertaisin tapa saavuttaa tämä on laskea aluksella olevien kappaleiden suhteellinen lujuus seuraavan taulukon avulla:

Arviointitoiminnon avulla voimme luoda algoritmin, joka valitsee korkeimman arvion antavan siirron:

Ainoa konkreettinen parannus on, että algoritmimme sieppaa nyt kappaleen, jos se pystyy.

Vaihe 3: Hae puusta Minimax-sovelluksella

Seuraavaksi aiomme luoda hakupuun, josta algoritmi voi valita parhaan siirron. Tämä tehdään käyttämällä Minimax-algoritmia.

Tässä algoritmissa kaikkien mahdollisten liikkeiden rekursiivinen puu tutkitaan tietylle syvyydelle ja sijainti arvioidaan puun loppupäässä.

Sen jälkeen palautamme joko pienimmän tai suurimman lapsen arvon vanhemmalle solmulle sen mukaan, onko se valkoinen vai musta liikkua. (Toisin sanoen yritämme joko minimoida tai maksimoida lopputuloksen kullakin tasolla.)

Kun minimx on paikallaan, algoritmimme alkaa ymmärtää joitain shakin perustaktiikoita:

Minimix-algoritmin tehokkuus perustuu voimakkaasti saavutettavaan hakusyvyyteen. Tätä parannamme seuraavassa vaiheessa.

Vaihe 4: Alfa-beeta-karsiminen

Alfa-beeta-karsinta on optimointimenetelmä minimx-algoritmille, jonka avulla voimme jättää huomiotta jotkut hakupuun haarat. Tämä auttaa meitä arvioimaan minimx-hakupuuta paljon syvemmälle samalla kun käytämme samoja resursseja.

Alfa-beeta-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-karsiminen ei vaikuta minimx-algoritmin tulokseen - se vain nopeuttaa sitä.

Alfa-beeta-algoritmi on myös tehokkaampi, jos sattuu käymään ensin niillä poluilla, jotka johtavat hyviin liikkeisiin.

Alfa-beetalla saamme merkittävän lisäyksen minimx-algoritmiin, kuten seuraava esimerkki osoittaa:

Seuraa tätä linkkiä kokeillaksesi alfa-beeta-parannettua versiota shakin tekoälystä.

Vaihe 5: Parannettu arviointitoiminto

Alustava arviointitoiminto on melko naiivi, koska laskemme vain taululta löytyvän materiaalin. Tämän parantamiseksi lisätään arviointiin tekijä, joka ottaa huomioon kappaleiden sijainnin. Esimerkiksi ritari levyn keskellä on parempi (koska sillä on enemmän vaihtoehtoja ja on siten aktiivisempi) kuin laudan reunalla oleva ritari.

Käytämme hiukan säädettyä versiota palaneliötaulukoista, jotka on alun perin kuvattu shakki-ohjelmointi-wikissä.

Seuraavan parannuksen avulla alamme saada algoritmin, joka pelaa "kunnollista" shakkia, ainakin rento pelaajan näkökulmasta:

Päätelmät

Jopa yksinkertaisen shakkipelialgoritmin vahvuus on, että se ei tee typeriä virheitä. Tästä huolimatta sillä ei vielä ole strategista ymmärrystä.

Tässä esitellyillä menetelmillä olemme pystyneet ohjelmoimaan shakkipeli-algoritmin, joka voi pelata shakkia. Lopullisen algoritmin "AI-osa" (poislukien sukupolvi) on vain 200 koodiriviä, mikä tarkoittaa, että peruskäsitteet on melko helppo toteuttaa. Voit tarkistaa, että lopullinen versio on GitHubissa.

Joitakin lisäparannuksia, joita voimme tehdä algoritmiin, ovat esimerkiksi:

  • siirtojen tilaaminen
  • nopeampi siirtää sukupolvi
  • ja pelikohtainen arviointi.

Jos haluat oppia lisää, tutustu shakkien ohjelmointivikiin. Se on hyödyllinen resurssi tutkimaan näitä tässä esittämäni peruskäsitteitä.

Kiitos lukemisesta!