Žingsnis po žingsnio, kaip sukurti paprastą šachmatų dirbtinį intelektą

Panagrinėkime keletą pagrindinių sąvokų, kurios padės mums sukurti paprastą šachmatų intelektą:

  • judėti karta
  • valdybos vertinimas
  • minimumx
  • ir alfa beta genėjimas.

Kiekviename žingsnyje patobulinsime savo algoritmą naudodami vieną iš šių laiko patikrintų šachmatų programavimo metodų. Aš pademonstruosiu, kaip kiekvienas veikia algoritmo žaidimo stilių.

Galutinį AI algoritmą galite peržiūrėti čia, „GitHub“.

1 žingsnis: perkelkite kartos ir plokštės vizualizaciją

„Chess.js“ biblioteką naudosime judesių generavimui, o „chessboard.js“ - lentos vizualizavimui. Judėjimo kartos biblioteka iš esmės įgyvendina visas šachmatų taisykles. Remdamiesi tuo, galime apskaičiuoti visus teisėtus veiksmus tam tikroje lentos būsenoje.

Šių bibliotekų naudojimas padės mums sutelkti dėmesį tik į įdomiausią užduotį: sukurti algoritmą, kuris surastų geriausią žingsnį.

Pirmiausia sukursime funkciją, kuri tiesiog grąžins atsitiktinį judėjimą iš visų galimų judesių:

Nors šis algoritmas nėra labai tvirtas šachmatų žaidėjas, tai yra geras atspirties taškas, nes iš tikrųjų galime su juo žaisti:

2 žingsnis: pozicijos vertinimas

Dabar pabandykime suprasti, kuri pusė yra stipresnė tam tikroje pozicijoje. Paprasčiausias būdas tai pasiekti yra suskaičiuoti lentos gabalų santykinį stiprumą naudojant šią lentelę:

Naudodami vertinimo funkciją, mes galime sukurti algoritmą, kuris pasirenka aukščiausią įvertinimą suteikiantį žingsnį:

Vienintelis apčiuopiamas patobulinimas yra tai, kad mūsų algoritmas dabar užfiksuos kūrinį, jei galės.

3 žingsnis: ieškokite medžio naudodami „Minimax“

Tada mes sukursime paieškos medį, iš kurio algoritmas gali pasirinkti geriausią žingsnį. Tai atliekama naudojant „Minimax“ algoritmą.

Šiame algoritme visų galimų judesių rekursinis medis tiriamas iki nurodyto gylio, o padėtis vertinama baigiantis medžio „lapams“.

Po to į tėvų mazgą grąžiname mažiausią arba didžiausią vaiko vertę, atsižvelgiant į tai, ar judėti reikia balta, ar juoda. (Tai yra, mes stengiamės arba sumažinti, arba maksimaliai padidinti kiekvieno lygio rezultatą.)

Kai nustatytas minimumx, mūsų algoritmas pradeda suprasti kai kurias pagrindines šachmatų taktikas:

Minimumx algoritmo efektyvumas labai priklauso nuo paieškos gylio, kurį galime pasiekti. Tai patobulinsime atlikdami kitą žingsnį.

4 žingsnis: Alfa-beta genėjimas

Alfa-beta genėjimas yra minimumx algoritmo optimizavimo metodas, leidžiantis nepaisyti kai kurių šakų paieškos medyje. Tai padeda mums daug giliau įvertinti „minimumx“ paieškos medį, tuo pačiu naudojant tuos pačius išteklius.

Alfa-beta genėjimas pagrįstas situacija, kai galime nustoti vertinti dalį paieškos medžio, jei rasime judesį, kuris veda į blogesnę situaciją nei anksčiau atrastas žingsnis.

Alfa-beta genėjimas neturi įtakos minimumx algoritmo rezultatui - jis jį daro tik greitesnį.

Alfa-beta algoritmas yra efektyvesnis, jei mes atsitikti aplankyti pirmą kartą tuos kelius, veda į gera juda.

Naudodami alfa-beta, mes reikšmingai padidiname minimumx algoritmą, kaip parodyta šiame pavyzdyje:

Spustelėkite šią nuorodą, kad išbandytumėte alfa-beta patobulintą šachmatų dirbtinio intelekto versiją.

5 žingsnis: patobulinta vertinimo funkcija

Pradinio vertinimo funkcija yra gana naivi, nes skaičiuojame tik lentoje esančią medžiagą. Norėdami tai pagerinti, prie vertinimo pridedame veiksnį, kuris atsižvelgia į kūrinių padėtį. Pavyzdžiui, lentos centre esantis riteris yra geresnis (nes jis turi daugiau galimybių ir todėl yra aktyvesnis) nei riteris ant lentos krašto.

Mes naudosime šiek tiek pakoreguotą kvadratinių lentelių versiją, kuri iš pradžių buvo aprašyta šachmatų programavimo-wiki.

Šitaip patobulinę, mes pradedame gauti algoritmą, kuris žaidžia kokį nors „padorų“ šachmatą, bent jau atsitiktinio žaidėjo požiūriu:

Išvados

Net paprasto šachmatų žaidimo algoritmo stiprioji pusė yra ta, kad jis nedaro kvailų klaidų. Be to, vis dar trūksta strateginio supratimo.

Taikydami čia pristatytus metodus, mes sugebėjome užprogramuoti šachmatų žaidimo algoritmą, kuris galėtų žaisti pagrindinį šachmatą. Galutinio algoritmo „AI dalis“ (išskyrus judėjimo generavimą) yra tik 200 kodo eilučių, o tai reiškia, kad pagrindines sąvokas įgyvendinti yra gana paprasta. Galutinę versiją galite sužinoti „GitHub“.

Keli tolesni algoritmo patobulinimai būtų, pavyzdžiui:

  • judesių užsakymas
  • greitesnė judėjimo karta
  • ir konkretaus žaidimo įvertinimas.

Jei norite sužinoti daugiau, peržiūrėkite šachmatų programavimo wiki. Tai naudingas šaltinis norint ištirti šias pagrindines mano čia pristatytas sąvokas.

Ačiū, kad skaitėte!