Spela schack | Om dataschack | Koda spelbräda | Öppningsspel | Evalueringsfunktion | Draggenerator | Minimax & Alfabeta-reducering | Dragsortering | Slutspel | Schackregler | Javascript | Länkar/referenser

Vi som sett filmen Terminator med Arnold Schwarzenegger vet ju att The Turk var en schackspelande dator som kom att utvecklas till skynet som sedan förklarade krig mot människan. Men The Turk, orginalet, finns faktiskt utanför Hollywood mitt i den karga verkligheten. Eller fanns, snarare. Som tur är förklarade den aldrig krig mot mänskligheten. Den skapades 1770 och existerade i ägo hos varierande folk fram till 1820.

Man skulle kunna säga att The Turk var den första schackspelande maskinen. Åtminståne såg den ut att vara en sådan. Den var ett ambulerande framträdande, jippo, bedrägeri, effektsökeri, trolleri, eller vad man nu vill kalla det, som kan illustrera den magi och de drömmar som började byggas upp i slutet av 1700-talet när människan började förstå - alternativt inbilla sig - att bara fantasin sätter gränsen för de maskiner människan kommer att skapa till sin hjälp. Industrialismen började koka och låta i form av bl.a. ångmaskiner.

The Turk var ett bord med ett schackbräde på. Bordet innehöll en hel del mekanik som gjorde det möjligt för personen som gömde sig inuti att fullborda ett schackparti inför en intet ont anande publik. När man flyttade på pjäserna ovanpå bordet flyttades de samtidigt på en bräde inuti bordet. När personen inuti flyttade på pjäserna så rörde de sig ovanpå bordet. Magiskt och obegripligt för de flesta på 1700-talet, som däremot visste de mesta om kor och grisar. Maskinen skapades av den matematik och fysikintresserade Wolfgang von Kempelen.

Det dröjde till 40-talet innan Konrad Zuse gjorde seriösa försök att designa en riktig schackdator. Programmets algoritmer skissades ner i hans egenutvecklade högnivåspråk "plankalkul" (plan-kalkyl ?) men implementerades aldrig i någon då existerande rör-dator. Eftersom det aldrig implementerades till ett riktigt schackprogram brukar äran för det första datorschacket tillskrivas Claude Shannon.

Själva kunskapen om hur man kan få datorer att spela schack är ganska väl dokumenterat sedan Shannon på 50-talet beskrev hur man kunde använda minimax och en evalueringsfunktion [PDF: Programming a computer for playing chess (Shannon, 1950)] för att beräkna ett schackdrag. Den matematiska teorin bakom minimax går tillbaka till John von Neumann 1928 och hans forskning. Vad det handlar om är att låta datorn söka fram ett optimalt drag givet vissa antaganden om hur motspelaren kan tänkas resonera, något som är möjligt att gissa då schack är ett nollsummespel.

Datorn som till slut skulle komma att besegra världsmästaren i schack, Gary Kasparov, 1996, byggde på Shannons algoritmer. Vad man gjorde för att försöka bemästra lite av nedanstående beskrivna problem var att bygga en specialkonstruerad dator där vissa av algoritmerna och sökning var optimerade i form av hårdvara (kretsar). Programmet innehöll också en en hel del och några till av de optimeringar som är beskrivna på dessa sidor.



Schack är ett sökproblem. Vi testar många kombinationer av drag och motdrag för att vaska fram det bästa. Men vi kan inte söka fram till slutet. Vi kan bara söka några få drag fram. En total utömmande sökning, alltså den rymd som en dator skulle behöva söka för att göra en uttömmande sökning fram till slutet kräver ett mycket stort antal kalkyler. Shannon uppskattade denna siffra till:



För ett parti på 40 drag handlar det alltså om 10 000 000 000 000 000 000 000 000 000 000 000 000 000 000 olika schackbräden. Detta är naturligtvis helt omöjligt att söka igenom ens för snabb en dator. Om man i framtiden lyckas göra en dator 1 miljard gånger snabbare än dagens datorer skulle det fortfarande ta 317 097 919 837 645 865 år att räkna igenom allting. Så glöm det där med att datorn kan söka igenom allting.

Vad vi kan göra är att försöka skapa en smart sökfunktion som kan titta några drag framåt. Det finns olika skolor kring om man skall satsa på rå brutal sökning eller om man skall göra ett program som bygger på kunskap.

Att skriva datorprogram som spelar schack är fortfarande en urban konstform där det skiljer stort mellan bra och dåliga program. Det finns tävlingar i denna sport där bara datorprogram spelar mot varandra.

Schackprogrammet behöver algoritmer som kan räkna ut ett smart schackdrag. Att göra ett schackprogram handlar i allt väsentligt om att koda följande saker.

• En draggenerator som givet en uppställning och historia kan ge alla legala drag för en spelare.
• En dragsortering som avlastar sökfunktionen.
• En eller flera möjligheter att göra sökningar.
• En evalueringsfunktion som kan uppskatta hur bra en spelare ligger till i ett givet ögonblick.

Ett schackparti består av tre olika delar. När människor spelar delas schackpartiet upp på detta vis och det gäller också datorer.

• Öppningsspelet - ett mindre bibliotek med drag från kända partier.
• Mellanspelet - en sökfunktion tar fram bästa draget.
• Slutspelet - speciella algoritmer.

Öppningsspelet handlar mycket om att studera tidigare partier och lära sig av vad som var framgångsrikt och inte. Resultatet av denna forskning är databaser med öppningsspel. Människor som spelar lär sig av tidigare schackpartier och datorprogram använder samma information. Man ska lägga märke till att det finns inte så mycket att räkna på när det gäller de första dragen, varken för människor eller datorer, så man behöver inte fundera över detta så mycket. Det fungerar på detta vis varken mer eller mindre.

Ju längre in i öppningsspelet man kommer desto mer flyter partiet över i ett strategispel. Senare delen av öppningsspelet handlar för människor om att utveckla resten av spelet. För datorn är senare delen av öppningsspelet samma sak som mellanspelet.

Det kommer inte finnas utrymme till någon större databas med öppningar, det finns inte ens utrymme för en liten databas. Men jag förseställer mig ändå att man kan göra en minimalistisk databas för de 1-3 första vanligaste inledningsdragen.

Mellanspelet sköts av den stora schackmotorn som jag kommer lägga ner mest energi på. Det är mellanspelet nästan hela denna sajt handlar om när vi talar om draggenerering, evaluering och sökfunktioner.

Slutspelet är en känslig bit. När detta skrivs är jag lite osäker på om den skall integreras med mellanspelet eller om man skall skriva speciella algoritmer för det.