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!