En steg-för-steg-guide för att bygga en enkel schack AI

av Lauri Hartikka

låt oss utforska några grundläggande begrepp som hjälper oss att skapa en enkel schack AI:

Move-generation
board utvärdering
Minimax
och alfa beta beskärning.

vid varje steg förbättrar vi vår algoritm med en av dessa tidtestade schackprogrammeringstekniker. Jag ska visa hur varje påverkar algoritmens spelstil.

Du kan se den slutliga AI-algoritmen här på GitHub.

Steg 1: Flytta generation och styrelse visualisering

vi använder Schack.JS bibliotek för move generation, och schackbräde.js för att visualisera styrelsen. Move generation-biblioteket implementerar i princip alla schackregler. Baserat på detta kan vi beräkna alla juridiska drag för en viss styrelsestat.

en visualisering av funktionen move generation. Startpositionen används som ingång och utgången är alla möjliga drag från den positionen.

att använda dessa bibliotek hjälper oss att fokusera bara på den mest intressanta uppgiften: skapa algoritmen som hittar det bästa draget.

vi börjar med att skapa en funktion som bara returnerar ett slumpmässigt drag från alla möjliga drag:

Även om denna algoritm inte är en mycket solid schackspelare, är det en bra utgångspunkt, eftersom vi faktiskt kan spela mot det:

Svart spelar slumpmässiga drag. Kan spelas på https://jsfiddle.net/lhartikk/m14epfwb/4

steg 2 : Positionsutvärdering

låt oss nu försöka förstå vilken sida som är starkare i en viss position. Det enklaste sättet att uppnå detta är att räkna den relativa styrkan hos bitarna på brädet med hjälp av följande tabell:

med utvärderingsfunktionen kan vi skapa en algoritm som väljer det drag som ger den högsta utvärderingen:

den enda konkreta förbättringen är att vår algoritm nu kommer att fånga en bit om den kan.

Svart spelar med hjälp av den enkla utvärderingsfunktionen. Spelbar på https://jsfiddle.net/lhartikk/m5q6fgtb/1/

steg 3: sökträd med Minimax

nästa kommer vi att skapa ett sökträd från vilket algoritmen kan välja det bästa draget. Detta görs med hjälp av Minimax-algoritmen.

i denna algoritm utforskas det rekursiva trädet av alla möjliga drag till ett givet djup, och positionen utvärderas vid trädets slut ”löv”.

därefter returnerar vi antingen barnets minsta eller största värde till modernoden, beroende på om det är vitt eller svart att flytta. (Det vill säga vi försöker antingen minimera eller maximera resultatet på varje nivå.)

en visualisering av minimax-algoritmen i en artificiell position. Det bästa draget för white är b2-c3, eftersom vi kan garantera att vi kan komma till en position där utvärderingen är -50

med minimax på plats börjar vår algoritm förstå några grundläggande taktik för Schack:

Minimax med djupnivå 2. Spelbar på: https://jsfiddle.net/k96eoq0q/1/

effektiviteten hos minimax-algoritmen är starkt baserad på sökdjupet vi kan uppnå. Detta är något vi kommer att förbättra i följande steg.

steg 4: Alfa-beta beskärning

alfa-beta beskärning är en optimeringsmetod till minimax-algoritmen som gör att vi kan bortse från vissa grenar i sökträdet. Detta hjälper oss att utvärdera minimax-sökträdet mycket djupare, samtidigt som vi använder samma resurser.alfa-beta beskärningen baseras på situationen där vi kan sluta utvärdera en del av sökträdet om vi hittar ett drag som leder till en sämre situation än ett tidigare upptäckt drag.alfa-beta-beskärningen påverkar inte resultatet av minimax — algoritmen-det gör det bara snabbare.alfa-beta-algoritmen är också effektivare om vi råkar besöka först de vägar som leder till bra drag.

positionerna vi behöver inte utforska om alfa-beta beskärning äranvänds och trädet besöks i den beskrivna ordningen.

med alfa-beta får vi en signifikant ökning av minimax-algoritmen, vilket visas i följande exempel:

antalet positioner som krävs för att utvärdera om vi vill utföra en sökning med djup 4 och” root ” – positionen är den som visas.

Följ denna länk för att prova alfa-beta förbättrad version av schack AI.

Steg 5: förbättrad utvärderingsfunktion

den initiala utvärderingsfunktionen är ganska naiv eftersom vi bara räknar materialet som finns på brädet. För att förbättra detta lägger vi till utvärderingen en faktor som tar hänsyn till bitarnas position. Till exempel är en riddare i mitten av brädet bättre (eftersom den har fler alternativ och därmed är mer aktiv) än en riddare på kanten av brädet.

Vi använder en något justerad version av bit-fyrkantiga tabeller som ursprungligen beskrivs i chess-programming-wiki.

de visualiserade Bit-fyrkantiga tabellerna visualiseras. Vi kan minska eller öka utvärderingen, beroende på platsen för stycket.

med följande förbättring börjar vi få en algoritm som spelar lite” anständigt”Schack, åtminstone ur en casualspelares synvinkel:

förbättrad utvärdering och alfa-beta beskärning med sökdjup på 3. Kan spelas på https://jsfiddle.net/q76uzxwe/1/

slutsatser

styrkan i till och med en enkel schackspelningsalgoritm är att den inte gör dumma misstag. Detta sagt, det saknar fortfarande strategisk förståelse.

med de metoder jag introducerade här har vi kunnat programmera en schackspelsalgoritm som kan spela grundläggande Schack. ”AI-delen” (move-generation utesluten) av den slutliga algoritmen är bara 200 rader kod, vilket betyder att de grundläggande begreppen är ganska enkla att implementera. Du kan kolla in den slutliga versionen är på GitHub.

några ytterligare förbättringar vi kan göra till algoritmen skulle vara till exempel:

flytta-beställa
snabbare flytta generation
och slutspel specifik utvärdering.

KGSAU