A step-by-step guide to building a simple chess AI

by Lauri Hartikka

fedezzünk fel néhány alapvető fogalmat, amelyek segítenek létrehozni egy egyszerű sakk AI:

move-Generation
board értékelés
Minimax
és alpha beta metszés.

minden lépésben fejlesztjük algoritmusunkat ezen időigényes sakk-programozási technikák egyikével. Megmutatom, hogy mindegyik hogyan befolyásolja az algoritmus játékstílusát.

a végső AI algoritmust itt tekintheti meg a Githubon.

1. lépés: Move generation and board visualization

fogjuk használni a sakk.js könyvtár move generáció, és sakktábla.js a tábla megjelenítéséhez. A move generation könyvtár alapvetően végrehajtja a sakk összes szabályát. Ennek alapján, tudjuk számítani az összes jogi mozog egy adott fórumon állam.

a move generation funkció megjelenítése. A kiindulási helyzet bemenetként szolgál, a kimenet pedig az összes lehetséges lépés ebből a helyzetből.

ezeknek a könyvtáraknak a használata segít abban, hogy csak a legérdekesebb feladatra összpontosítsunk: a legjobb mozdulatot kereső algoritmus létrehozására.

kezdjük egy olyan függvény létrehozásával, amely csak egy véletlenszerű mozdulatot ad vissza az összes lehetséges mozdulatból:

bár ez az algoritmus nem túl szilárd sakkjátékos, ez egy jó kiindulási pont, mivel valójában játszhatunk ellene:

Fekete véletlenszerű mozdulatokat játszik. Lejátszható https://jsfiddle.net/lhartikk/m14epfwb/4

2. lépés : Pozícióértékelés

most próbáljuk megérteni, melyik oldal erősebb egy bizonyos helyzetben. Ennek legegyszerűbb módja a táblán lévő darabok relatív erősségének megszámlálása a következő táblázat segítségével:

az értékelési funkcióval létrehozhatunk egy algoritmust, amely kiválasztja a legmagasabb értékelést adó lépést:

az egyetlen kézzelfogható javulás az, hogy algoritmusunk most rögzít egy darabot, ha képes.

a fekete az egyszerű értékelési funkció segítségével játszik. Játszható https://jsfiddle.net/lhartikk/m5q6fgtb/1/

3.lépés: keresés fa segítségével Minimax

ezután létrehozunk egy keresési fát, amelyből az algoritmus kiválaszthatja a legjobb lépést. Ez a Minimax algoritmus segítségével történik.

ebben az algoritmusban az összes lehetséges lépés rekurzív fáját feltárjuk egy adott mélységig, és a pozíciót a fa végső “levelein” értékeljük.

ezután visszatérünk a gyermek legkisebb vagy legnagyobb értékéhez a szülő csomóponthoz, attól függően, hogy fehér vagy fekete-e a mozgatáshoz. (Vagyis minden szinten megpróbáljuk minimalizálni vagy maximalizálni az eredményt.)

a minimax algoritmus mesterséges helyzetben történő megjelenítése. A legjobb lépés white számára a b2-c3, mert garantálhatjuk, hogy eljuthatunk olyan helyzetbe, ahol az értékelés -50

a minimax használatával algoritmusunk kezdi megérteni a sakk néhány alapvető taktikáját:

Minimax a 2.mélységi szinttel. Lejátszható: https://jsfiddle.net/k96eoq0q/1/

a minimax algoritmus hatékonysága nagymértékben az elérhető keresési mélységen alapul. Ezt a következő lépésben javítani fogjuk.

4. lépés: Alfa-béta metszés

az alfa-béta metszés a minimax algoritmus optimalizálási módszere, amely lehetővé teszi számunkra, hogy figyelmen kívül hagyjuk a keresési fa egyes ágait. Ez segít nekünk sokkal mélyebben értékelni a minimax Keresési fát, miközben ugyanazokat az erőforrásokat használjuk.

az alfa-béta metszés azon a helyzeten alapul, amikor abbahagyhatjuk a keresési fa egy részének értékelését, ha olyan lépést találunk, amely rosszabb helyzethez vezet, mint egy korábban felfedezett lépés.

az alfa-béta metszés nem befolyásolja a minimax algoritmus eredményét — csak gyorsabbá teszi.

az alfa-béta algoritmus akkor is hatékonyabb, ha először meglátogatjuk azokat az utakat, amelyek jó lépésekhez vezetnek.

azok a pozíciók, amelyeket nem kell feltárnunk, ha az alfa-béta metszést használják, és a fát a leírt sorrendben látogatják meg.

az alfa-béta segítségével jelentős lendületet kapunk a minimax algoritmushoz, amint azt a következő példa mutatja:

az értékeléshez szükséges pozíciók száma, ha 4 mélységű keresést akarunk végrehajtani, és a “gyökér” pozíció látható.

kövesse ezt a linket a Chess AI alfa-béta továbbfejlesztett verziójának kipróbálásához.

5. lépés: továbbfejlesztett értékelési funkció

a kezdeti értékelési funkció meglehetősen naiv, mivel csak a táblán található anyagokat számoljuk. Ennek javítása érdekében az értékeléshez hozzáadunk egy olyan tényezőt, amely figyelembe veszi a darabok helyzetét. Például egy lovag a tábla közepén jobb (mert több lehetősége van, és így aktívabb), mint egy lovag a tábla szélén.

a piece-square táblák kissé módosított változatát fogjuk használni, amelyeket eredetileg a sakk-programozás-wiki.

a megjelenített darab-négyzet alakú táblázatok láthatóvá. Csökkenthetjük vagy növelhetjük az értékelést, a darab helyétől függően.

a következő fejlesztéssel olyan algoritmust kapunk, amely valamilyen “tisztességes” sakkot játszik, legalábbis egy alkalmi játékos szempontjából:

továbbfejlesztett értékelés és alfa-béta metszés 3 Keresési mélységgel. Játszható https://jsfiddle.net/q76uzxwe/1/

következtetések

még egy egyszerű sakkjáték algoritmus erőssége is, hogy nem követ el hülye hibákat. Ez azt mondta, még mindig hiányzik a stratégiai megértés.

az itt bemutatott módszerekkel képesek voltunk egy sakk-játék algoritmust programozni, amely képes alapvető sakkot játszani. A végső algoritmus “AI-része”(move-generation kizárva) mindössze 200 sornyi kód, vagyis az alapfogalmak meglehetősen egyszerűek. Megnézheti, hogy a végleges verzió a Githubon található-e.

néhány további fejlesztés az algoritmuson például:

move-ordering
faster move generation
és end-game specifikus értékelés.

KGSAU