En steg-for-steg guide til å bygge en enkel sjakk AI

Av Lauri Hartika

la oss utforske noen grunnleggende begreper som vil hjelpe oss å lage en enkel sjakk AI:

flytte-generasjon
styret evaluering
minimax
og alfa beta beskjæring.

på hvert trinn vil vi forbedre algoritmen vår med en av disse tidstestede sjakkprogrammeringsteknikkene. Jeg skal demonstrere hvordan hver påvirker algoritmens spillestil.

du kan se den endelige AI-algoritmen her på GitHub.

Trinn 1: Flytt generasjon og bord visualisering

vi bruker sjakk.js bibliotek for flytte generasjon, og sjakkbrett.js for å visualisere styret. The move generation library implementerer i utgangspunktet alle reglene for sjakk. Basert på dette kan vi beregne alle juridiske trekk for en gitt styrestat.

en visualisering av funksjonen flytt generasjon. Startposisjonen brukes som inngang og utgangen er alle mulige trekk fra den posisjonen.

Ved å Bruke disse bibliotekene vil vi bare fokusere på den mest interessante oppgaven: å skape algoritmen som finner det beste trekket.

Vi starter med å lage en funksjon som bare returnerer et tilfeldig trekk fra alle mulige trekk:

Selv om denne algoritmen ikke er en veldig solid sjakkspiller, er Det et godt utgangspunkt, da vi faktisk kan spille mot det:

Svart spiller tilfeldige trekk. Kan spilles på https://jsfiddle.net/lhartikk/m14epfwb/4

Trinn 2 : Posisjonsevaluering

la Oss nå prøve å forstå hvilken side som er sterkere i en bestemt posisjon. Den enkleste måten å oppnå dette på er å telle den relative styrken til brikkene på brettet ved hjelp av følgende tabell:

med evalueringsfunksjonen kan vi lage en algoritme som velger det trekket som gir den høyeste evalueringen:

den eneste konkrete forbedringen er at vår algoritme nå vil fange et stykke hvis det kan.

Svart spiller Ved hjelp av den enkle evalueringsfunksjonen. Spillbar på https://jsfiddle.net/lhartikk/m5q6fgtb/1/

Trinn 3: Søketre ved Hjelp Av Minimax

Neste skal vi lage et søketre som algoritmen kan velge det beste trekket fra. Dette gjøres ved Å bruke Minimax-algoritmen.

i denne algoritmen utforskes det rekursive treet av alle mulige trekk til en gitt dybde, og posisjonen vurderes ved slutten av» bladene » av treet.

deretter returnerer vi enten den minste eller den største verdien av barnet til foreldreknoden, avhengig av om det er hvitt eller svart å flytte. (Det vil si, vi prøver å enten minimere eller maksimere utfallet på hvert nivå.)

en visualisering av minimax-algoritmen i en kunstig posisjon. Det beste trekket for hvit er b2-c3, fordi vi kan garantere at vi kan komme til en posisjon der evalueringen er -50

med minimax på plass, vår algoritme begynner å forstå noen grunnleggende taktikk av sjakk:

Minimax med dybde nivå 2. Spillbar på: https://jsfiddle.net/k96eoq0q/1/

effektiviteten til minimax-algoritmen er tungt basert på søkedybden vi kan oppnå. Dette er noe vi vil forbedre i neste trinn.

Trinn 4: Alpha-beta beskjæring

Alpha-beta beskjæring er en optimaliseringsmetode til minimax algoritmen som tillater oss å se bort fra noen grener i søketreet. Dette hjelper oss med å evaluere minimax søketreet mye dypere, mens du bruker de samme ressursene.alfa-beta beskjæring er basert på situasjonen der vi kan slutte å evaluere en del av søketreet hvis vi finner et trekk som fører til en verre situasjon enn et tidligere oppdaget trekk.

alfa-beta-beskjæring påvirker ikke utfallet av minimax-algoritmen — det gjør det bare raskere.alfa-beta-algoritmen er også mer effektiv hvis vi først besøker de stiene som fører til gode trekk.

stillingene vi ikke trenger å utforske om alfa-beta beskjæring er brukt og treet er besøkt i den beskrevne rekkefølgen.

med alpha-beta får vi et betydelig løft til minimax-algoritmen, som vist i følgende eksempel:

antall stillinger som kreves for å evaluere om vi vil utføre et søk med dybde på 4 og «root» – posisjonen er den som vises.

Følg denne linken for å prøve alpha-beta forbedret versjon av chess AI.

Trinn 5: Forbedret evalueringsfunksjon

den første evalueringsfunksjonen er ganske naiv da vi bare teller materialet som finnes på brettet. For å forbedre dette legger vi til evalueringen en faktor som tar hensyn til stykkets posisjon. For eksempel er en ridder på midten av brettet bedre (fordi den har flere alternativer og er dermed mer aktiv) enn en ridder på kanten av brettet.

Vi bruker en litt justert versjon av kvadratiske tabeller som opprinnelig er beskrevet i sjakk-programmering-wiki.

de visualiserte stykkefirkantede tabellene visualisert. Vi kan redusere eller øke evalueringen, avhengig av plasseringen av stykket.

med følgende forbedring begynner vi å få en algoritme som spiller litt «anstendig» sjakk, i hvert fall fra synspunktet til en uformell spiller:

Forbedret evaluering og alfa-beta beskjæring med søkedybde på 3. Spilles på https://jsfiddle.net/q76uzxwe/1/

Konklusjoner

styrken til selv en enkel sjakkspillalgoritme er at den ikke gjør dumme feil. Dette sa, det mangler fortsatt strategisk forståelse.

med metodene jeg introduserte her, har vi vært i stand til å programmere en sjakk-spiller-algoritme som kan spille grunnleggende sjakk. «AI-delen» (flyttegenerering ekskludert) av den endelige algoritmen er bare 200 linjer med kode, noe som betyr at de grunnleggende konseptene er ganske enkle å implementere. Du kan sjekke ut den endelige versjonen er på GitHub.

noen ytterligere forbedringer vi kunne gjøre til algoritmen ville være for eksempel:

flytte-bestilling
raskere flytte generasjon
og end-game spesifikk evaluering.

KGSAU