På ett allmänt sätt använder schackmotorer ett beslutsträd. Trädets rot är den aktuella positionen och har en barnnod för varje position som kan göras genom att göra ett lagligt drag. Var och en av dessa noder har i sin tur en underlig nod för positionerna som kan nås genom att göra ett lagligt drag från dem. Motorn skjuter ut trädet till ett djup som definieras av dess förmåga och den tid det får "tänka". Positioner som kan nås på mer än ett sätt är helt enkelt korsrefererade så att de inte behöver övervägas mer än en gång. När trädet har skapats använder datorn en uppsättning viktade regler för att analysera de slutliga positionerna i trädet och börjar ta bort de som är oönskade eller som motståndaren kan förhindra att det når. Trädet klipps ned på detta sätt tills bara ett drag återstår och datorn gör det.

http://www.chess.com/blog/zaifrun har serier eller artiklar om hur du skapar en schackmotor om du vill ha en mer ingående titt på hur de fungerar.

Du ställer en ganska komplex fråga, men det är bra att gå tillbaka till grunderna. Det finns ett par begrepp att tänka på:

Utvärdering

Om en (riktig) spelare visas en position och frågar "vem vinner det här spelet?", Hur går de till beslutar? Troligtvis kommer de att kontrollera några grundläggande saker, såsom: materialskillnader, i vilken grad bitar har utvecklats eller är placerade "bra", dubbla / isolerade / anslutna / passerade bönder, (kontrollerade) öppna filer, hur långt upp brädan är bönderna.

Nu, om du var tvungen att göra det, kan du komma på ett systematiskt sätt att beräkna en positionsscore baserat på ovanstående. Du kan till exempel bestämma att en bonde är värt 1 poäng och att en godkänd bonde är värt 0,3 poäng mer. Isolerade eller dubbla bönder kan vara värda lite mindre etc. Om du lägger till allt får du ett uppskattningsvärde för den omedelbara positionen till hands.

Detta är känt som utvärdering, och i princip har alla schackprogram ett sätt att utvärdera positioner (ignorera nyskapande AI-schackmotorer som vanligtvis är mycket svaga).

Men hur är det med subtila, djupa positionella rörelser?

Nåväl, vi har bara knappt klarat av ytan för positionsvärderingen. Det faktiska genomförandet av en utvärderingsfunktion kan vara förenklat för att möjliggöra att fler positioner utvärderas per sekund (om än på grovt sätt), eller mer komplicerat, vilket leder till färre positioner utvärderade, men med högre grad av självförtroende. Det är inte ovanligt att utvärderingsfunktionen tar hänsyn till hundratals eller till och med tusentals separata bitar av information.

Sök

Jag har specifikt utelämnat något från ovanstående, som är mest verkligt spelare kommer omedelbart att tänka på - finns det något sätt att omedelbart vinna spelet för vardera sidan? Några kompisar eller "hängande" bitar synliga? Även om det är lätt att bagatellisera detta är det allt annat än trivialt.

Vad betyder det för en spelare att ha fullt förtroende för en kombination? I slutändan handlar det om att ha beräknat alla alternativ. Riktiga spelare kommer vanligtvis inte att göra detta (förutom triviala eller mycket tvungna kompisar), för det mesta kommer vi bara att överväga en handfull alternativ och utesluta andra som verkar vara "icke-konstruktiva" eller uppenbarligen leder till förlust . Vi gör ofta misstag under denna beräkning, t.ex. vi kanske inser att en förändring i dragorder gör att hot förångas osv. Poängen är att för att vara helt säker på en kombination måste du faktiskt beräkna hela vägen till dess slutsats, förutsatt att varje spelare bara gör bästa möjliga drag tillgängliga till dem (detta kallas "min / max").

Nu med tanke på att schack har ett mycket större sökutrymme (det är det som "alla möjliga drag i framtiden" hänvisas till) än vad som är möjligt för en dator att beräkna, måste kompromisser göras. Precis som människor kan datorer besluta att bortse från hela tankelinjer baserat på vissa kriterier. Detta kallas heuristik . Det är värt att notera att även om du bara kan vara riktigt säker på en kombination om du råkar tvinga den, kan en komplex utvärderingsfunktion ofta upptäcka förekomsten av hot (t.ex. vi kan räkna gafflar, spettmöjligheter osv. För att styra en sökning i den riktningen ).

I slutändan, även om datorer är extremt snabba, är det heuristiken som gör att de kan beräkna så djupt. Med detta sagt kan du bli förvånad över hur djupa moderna motorer räknar ut helt, vanligtvis är det bortom tre drag, även i snabba spel.

Sammanfattning / kombinera allt

Så, för att sammanfatta - utvärderingsfunktioner har mycket intelligens inbyggda i sig (dvs de tar hänsyn till fler saker än din genomsnittliga mänskliga spelare), heuristik gör det möjligt för datorn att avlägsna tankesätt som den bestämmer förmodligen inte kommer att slutar bra, och datorer är extremt, extremt snabba. Lägg till dem så är de ganska svåra att slå.

Jag instämmer i svaren.

Jag kommer ihåg att GM Roman Dzindzichashvili pratade om det, i en av Romans labs -videor, det gör jag inte kom ihåg vilken video det var (om någon vet detaljerna kan du redigera mitt svar).

Roman sa att utvecklaren av Fritz engine är hans vän. Så Roman testade Fritz för att se hur bra det var, och utvecklaren sa till Roman att för att Fritz skulle kunna ta komplexa beslut (offra material i utbyte mot exempelvis positionell fördel) var de tvungna att ändra bitarnas värde, som att berätta om programmet att en dålig biskop är värt 1 poäng, en biskop på en öppen diagonal är värt 7 poäng, riddare är värda 5 poäng i nära positioner ...

Jag vet inte exakta siffror för varje bit men så fungerar det, och nu har din motor inga problem att offra en dålig biskop eller vad som helst om du kan berätta för honom om värdet av varje bit i varje position.

EDIT

Se även The Chess Programming Wiki.

Det är bara omöjligt för datorer att se tillräckligt djupt (25 lager och mer) och kontrollera alla möjliga drag.

Det som möjliggör är tekniken som kallas Alpha-beta-beskärning vilket innebär att datorer som liknar människor (men mycket bättre) bara följer de lovande fortsättningarna.

De utvärderar positionerna ständigt (baserat på några förkodade regler, värderingsmaterial, kungssäkerhet, aktivitet, bonde strukturer etc. ) och titta på variationer som verkar leda dem till den bästa positionen.

Det är fortfarande nära magi hur de lyckas göra det tillräckligt effektivt för att utvärdera miljoner av dessa positioner på en sekund.

Så för att sammanfatta - du har rätt, de kan inte titta på alla drag om de spelar strategiskt schack, men de kan mycket snabbt titta på anständiga drag. Problemet är fortfarande med de mycket långsiktiga planerna och horisonten som de kan se, men detta jobbar på (Rybka analyserar mycket långsammare, men spelar mycket mer positionsschack, medan Houdini är romantisk i sitt "mekaniska hjärta" och beräknar fler drag och spela mer aggressivt). Även datorer har sina egna stilar!

Alpha-beta-beskärning betyder helt enkelt att om du hittar en linje som visar sig vara dålig för dig, slutar du titta på kandidatrörelsen och istället försöker andra. Det är en typ av bakåt beskärning vilket innebär att du aldrig kommer att missa ett bra drag som ett resultat. Beskärning framåt bygger däremot mer på gissningar. Meningslös beskärning, sena rörelsereduktioner och rakhyvel är typer av beskärning framåt, och alla förlitar sig på programmerarens känsla för vilken typ av rörelser som ska övervägas. Ett program som gör mycket beskärning framåt kan missa uppseendeväckande offer som leder till kompis, men å andra sidan eliminerar det många riktigt dåliga drag, och så kan det gå djupare när man tittar på de rörelser det gynnar.

De flesta motorer söker de första rörelserna på full djup och undersöker alla möjligheter. Om inget drag misslyckas högt (dvs. verkar tydligt värre än ett drag du redan har övervägt), utvidgar du sökningen lite mer. Generellt fortsätter du att utforska varje rad tills du når en viloläge (utan kontroller, fångar, kompishot etc.) och gör sedan din utvärdering. Lugna rörelser kan inte övervägas när de är djupt i sökträdet, men när du väl har kommit till den faktiska positionen i spelet ser motorn på alla rörelser, tyst och skarpa lika. Du kan faktiskt se detta i motoreffekten ibland, när en motor plötsligt gynnar ett drag som det inte hade övervägt några drag tillbaka.

Motorer beräknar så snabbt att det inte är så viktigt för dem att överväga som rör sig för att se först, men för människor är detta en nyckelfråga. Jonathan Tisdall svarar på detta i sin bok, Förbättra ditt schack nu. När du är på attacken föreslår han att du tittar på de mest våldsamma drag först. När du försvarar tittar du först på de svåraste linjerna. Han citerar också tumregler (t.ex. centralisering, samordning) när han bestämmer vilka rörelser man ska titta på först.

Andra böcker som kan vara relevanta är Emmanuel Neimanns Invisible Chess Moves och Charles Hertans Forcing Chess Moves, som båda argumenterar för vikten av att överväga osannolika eller överraskande drag i skarpa positioner. Hertan talar till och med om att utveckla "datorögon" för sådan taktik.