Lépésenkénti útmutató egy egyszerű sakk-AI felépítéséhez

Fedezzünk fel néhány alapvető fogalmat, amelyek segítenek egy egyszerű sakk-AI létrehozásában:

  • lépés-generáció
  • tábla értékelése
  • minimumx
  • és alfa béta metszés.

Minden lépésben javítani fogjuk algoritmusunkat az időzített sakk-programozási technikák egyikével. Bemutatom, hogy mindegyik befolyásolja az algoritmus játékstílusát.

A végső AI algoritmust itt a GitHubon tekintheti meg.

1. lépés: Mozgassa a generálás és a tábla megjelenítését

A chess.js könyvtárat használjuk az áthelyezéshez, a chessboard.js pedig a tábla megjelenítéséhez. A move generációs könyvtár alapvetően a sakk összes szabályát végrehajtja. Ez alapján kiszámíthatjuk az összes törvényi lépést egy adott táblaállapotra vonatkozóan.

Ezeknek a könyvtáraknak a használata csak a legérdekesebb feladatra koncentrálhat: a legjobb lépést megtaláló algoritmus létrehozására.

Először létrehozunk egy olyan függvényt, amely véletlenszerű mozgást ad vissza az összes lehetséges lépésből:

Bár ez az algoritmus nem túl megbízható sakkozó, jó kiindulópont, mivel valójában játszhatunk ellene:

2. lépés: Helyzetértékelés

Most próbáljuk megérteni, hogy melyik oldal erősebb egy bizonyos helyzetben. Ennek elérésének legegyszerűbb módja, ha az alábbi táblázat segítségével megszámolja a táblán lévő darabok relatív szilárdságát:

Az értékelési funkcióval képesek vagyunk létrehozni egy algoritmust, amely kiválasztja a legmagasabb értékelést adó lépést:

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

3. lépés: Keressen fát a Minimax segítségével

Ezután létrehozunk egy keresési fát, amelyből az algoritmus kiválaszthatja a legjobb lépést. Ez a Minimax algoritmus használatával történik.

Ebben az algoritmusban az összes lehetséges lépés rekurzív fáját egy adott mélységig feltárják, és a helyzetet a fa végződő „levelein” értékelik.

Ezt követően a gyermek legkisebb vagy legnagyobb értékét visszaküldjük a szülőcsomópontra, attól függően, hogy fehér vagy fekete mozgatni. (Vagyis megpróbáljuk minimalizálni vagy maximalizálni az eredményt minden szinten.)

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

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

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

Az alfa-béta metszés egy optimalizálási módszer a minimumx algoritmushoz, amely lehetővé teszi számunkra, hogy figyelmen kívül hagyjuk a keresőfa néhány ágát. Ez segít abban, hogy a minimumx keresési fát sokkal mélyebben értékeljük, ugyanazon erőforrások felhasználása mellett.

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

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

Az alfa-béta algoritmus akkor is hatékonyabb, ha véletlenül először meglátogatjuk azokat az utakat, amelyek jó mozgásokhoz vezetnek.

Az alfa-béta segítségével jelentős lendületet kapunk a minimumx algoritmuson, amint az a következő példában látható:

Ezt a linket követve próbálja ki a sakk AI alfa-bétával továbbfejlesztett változatát.

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 vesszük számba. Ennek javítása érdekében hozzáadunk az értékeléshez egy olyan tényezőt, amely figyelembe veszi a darabok helyzetét. Például a tábla közepén lévő lovag jobb (mert több lehetősége van és így aktívabb), mint a tábla szélén lévő lovag.

A darab-négyzet táblák kissé módosított változatát fogjuk használni, amelyeket eredetileg a sakk-programozás-wiki ismertet.

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

Következtetések

Még egy egyszerű sakkozó algoritmus erőssége, hogy nem követ el hülye hibákat. Ennek ellenére még mindig hiányzik a stratégiai megértés.

Az itt bemutatott módszerekkel sikerült sakkjáték-algoritmust programozni, amely képes az alapvető sakkozásra. A végső algoritmus „AI-része” (a mozgásgenerálást kizárva) csupán 200 kódsor, 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, amelyet az algoritmusban megtehetnénk, például:

  • mozgás-rendezés
  • gyorsabb lépés generáció
  • és a végjáték-specifikus értékelés.

Ha többet szeretne megtudni, nézze meg a sakk programozás wiki-t. Hasznos forrás az itt bemutatott alapfogalmakon kívüli feltáráshoz.

Köszönöm, hogy elolvasta!