En trinnvis guide for å bygge en enkel sjakk-AI

La oss utforske noen grunnleggende konsepter som vil hjelpe oss med å lage en enkel sjakk-AI:

  • bevegelsesgenerasjon
  • styreevaluering
  • minimax
  • og alfa beta beskjæring.

Ved hvert trinn forbedrer vi 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 generering og brettvisualisering

Vi bruker chess.js-biblioteket for å generere trekk, og chessboard.js for å visualisere tavlen. Flyttegenerasjonsbiblioteket implementerer i utgangspunktet alle sjakkreglene. Basert på dette kan vi beregne alle lovlige trekk for en gitt styretilstand.

Å bruke disse bibliotekene vil hjelpe oss å fokusere bare på den mest interessante oppgaven: å lage algoritmen som finner det beste trekket.

Vi begynner 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, ettersom vi faktisk kan spille mot den:

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 høyest evaluering:

Den eneste håndgripende forbedringen er at algoritmen vår nå vil fange et stykke hvis det kan.

Trinn 3: Søk i treet ved hjelp av Minimax

Deretter 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 til alle mulige trekk til en gitt dybde, og posisjonen blir evaluert ved slutten av "bladene" på treet.

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

Med minimaks på plass begynner algoritmen vår å forstå noen grunnleggende taktikker for sjakk:

Effektiviteten til minimax-algoritmen er sterkt basert på søkedybden vi kan oppnå. Dette vil vi forbedre i det neste trinnet.

Trinn 4: Alpha-beta beskjæring

Beskjæring av Alpha-beta er en optimaliseringsmetode for minimax-algoritmen som lar oss se bort fra noen grener i søketreet. Dette hjelper oss med å evaluere minimax-søketreet mye dypere, mens vi bruker de samme ressursene.

Beskjæringen av alfa-beta 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.

Beskjæringen av alfa-beta påvirker ikke utfallet av minimax-algoritmen - det gjør det bare raskere.

Alfa-beta-algoritmen er også mer effektiv hvis vi tilfeldigvis først besøker de banene som fører til gode trekk.

Med alfa-beta får vi et betydelig løft for minimax-algoritmen, som vist i følgende eksempel:

Følg denne lenken for å prøve den forbedrede alfa-beta-versjonen av sjakk AI.

Trinn 5: Forbedret evalueringsfunksjon

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

Vi bruker en litt justert versjon av firkantede bord som opprinnelig er beskrevet i sjakkprogrammeringswiki.

Med den følgende forbedringen begynner vi å få en algoritme som spiller litt "anstendig" sjakk, i det minste sett fra et tilfeldig spillers synspunkt:

Konklusjoner

Styrken til og med en enkel sjakk-spillalgoritme er at den ikke gjør dumme feil. Når det er sagt, mangler det fremdeles strategisk forståelse.

Med metodene jeg introduserte her, har vi klart å programmere en sjakk-spill-algoritme som kan spille grunnleggende sjakk. “AI-delen” (flytt-generasjon ekskludert) i 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 kan gjøre med algoritmen, kan for eksempel være:

  • flytt-bestilling
  • raskere bevegelsesgenerering
  • og spesifikk evaluering av sluttspill.

Hvis du vil lære mer, kan du sjekke wiki for sjakkprogrammering. Det er en nyttig ressurs for å utforske utover disse grunnleggende konseptene jeg introduserte her.

Takk for at du leste!