En trin-for-trin guide til opbygning af en simpel AI-skak

Lad os udforske nogle grundlæggende koncepter, der hjælper os med at skabe en simpel skak AI:

  • bevægelsesgeneration
  • bestyrelsesevaluering
  • minimax
  • og alfa beta beskæring.

Ved hvert trin forbedrer vi vores algoritme med en af ​​disse tidstestede skakprogrammeringsteknikker. Jeg demonstrerer, hvordan hver påvirker algoritmens spillestil.

Du kan se den endelige AI-algoritme her på GitHub.

Trin 1: Flyt generation og kortvisualisering

Vi bruger chess.js-biblioteket til flytning og chessboard.js til visualisering af tavlen. Flytgenerationsbiblioteket implementerer dybest set alle reglerne for skak. Baseret på dette kan vi beregne alle lovlige træk for en given bestyrelsesstat.

Brug af disse biblioteker hjælper os med kun at fokusere på den mest interessante opgave: at skabe den algoritme, der finder det bedste træk.

Vi starter med at oprette en funktion, der bare returnerer et tilfældigt træk fra alle de mulige træk:

Selvom denne algoritme ikke er en meget solid skakspiller, er den et godt udgangspunkt, da vi faktisk kan spille imod den:

Trin 2: Positionsevaluering

Lad os nu prøve at forstå, hvilken side der er stærkere i en bestemt position. Den enkleste måde at opnå dette på er at tælle stykkernes relative styrke på tavlen ved hjælp af følgende tabel:

Med evalueringsfunktionen er vi i stand til at oprette en algoritme, der vælger det træk, der giver den højeste evaluering:

Den eneste håndgribelige forbedring er, at vores algoritme nu fanger et stykke, hvis det kan.

Trin 3: Søg i træet ved hjælp af Minimax

Dernæst opretter vi et søgetræ, hvor algoritmen kan vælge det bedste træk. Dette gøres ved hjælp af Minimax-algoritmen.

I denne algoritme udforskes det rekursive træ for alle mulige bevægelser til en given dybde, og positionen evalueres ved slutningen af ​​"blade" på træet.

Derefter returnerer vi enten den mindste eller den største værdi af barnet til forældrenoden, afhængigt af om det er en hvid eller sort at flytte. (Det vil sige, vi forsøger enten at minimere eller maksimere resultatet på hvert niveau.)

Med minimax på plads begynder vores algoritme at forstå nogle grundlæggende taktikker ved skak:

Effektiviteten af ​​minimax-algoritmen er stærkt baseret på den søgedybde, vi kan opnå. Dette forbedrer vi i det følgende trin.

Trin 4: Alfa-beta beskæring

Beskæring af Alpha-beta er en optimeringsmetode til minimax-algoritmen, der giver os mulighed for at se bort fra nogle grene i søgetræet. Dette hjælper os med at evaluere minimax-søgetræet meget dybere, mens vi bruger de samme ressourcer.

Alfa-beta beskæring er baseret på den situation, hvor vi kan stoppe med at evaluere en del af søgetræet, hvis vi finder et træk, der fører til en værre situation end et tidligere opdaget træk.

Alfa-beta-beskæring påvirker ikke resultatet af minimax-algoritmen - det gør det kun hurtigere.

Alfa-beta-algoritmen er også mere effektiv, hvis vi tilfældigvis først besøger de stier, der fører til gode træk.

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

Følg dette link for at prøve den forbedrede alfa-beta version af skak AI.

Trin 5: Forbedret evalueringsfunktion

Den indledende evalueringsfunktion er ret naiv, da vi kun tæller det materiale, der findes på tavlen. For at forbedre dette tilføjer vi til evalueringen en faktor, der tager hensyn til brikkernes position. For eksempel er en ridder i midten af ​​tavlen bedre (fordi den har flere muligheder og dermed er mere aktiv) end en ridder på kanten af ​​tavlen.

Vi bruger en lidt justeret version af firkantede tabeller, der oprindeligt er beskrevet i skak-programmering-wiki.

Med den følgende forbedring begynder vi at få en algoritme, der spiller noget "anstændigt" skak, i det mindste set fra en afslappet spillers synspunkt:

Konklusioner

Styrken ved selv en simpel skakspilalgoritme er, at den ikke laver dumme fejl. Når det er sagt, mangler det stadig strategisk forståelse.

Med de metoder, jeg introducerede her, har vi været i stand til at programmere en skakspil-algoritme, der kan spille grundlæggende skak. Den "AI-del" (udelukket bevægelsesgenerering) af den endelige algoritme er kun 200 linjer kode, hvilket betyder, at de grundlæggende begreber er ret enkle at implementere. Du kan tjekke den endelige version er på GitHub.

Nogle yderligere forbedringer, vi kunne gøre for algoritmen, vil f.eks. Være:

  • flytning-bestilling
  • hurtigere flytning af generation
  • og slutspilsspecifik evaluering.

Hvis du vil lære mere, skal du tjekke skakprogrammeringswiki. Det er en nyttig ressource til at udforske ud over disse grundlæggende begreber, jeg introducerede her.

Tak for læsningen!