Anders Hesselbom

Datorschack

2020-02-22

Det är förmodligen möjligt att bygga ett datorchack utan mer kunskap än själva spelreglerna. Man måste veta hur pjäserna får förflytta sig, inklusive specialdragen (uppgradering, passant, rockad), att inte egna kungen får ställas i schack och kriterierna för vinst, förlust eller möjligtvis remi (och kriterierna för remi).

Som mänsklig spelare kan man troligtvis inte analysera alla tänkbara drag speciellt långt in i framtiden (åtminstone kan inte jag göra det) utan får istället jobba med strategier som t.ex. skulle kunna vara att identifiera spelplanskonfigurationer där vissa drag tenderar att vara mer eller mindre lönsamma.

En dator som spelar mot en människa borde kunna göra en grundlig analys av spelplanen för att veta vilket drag som öppnar för ett framtida segerdrag, och tittar man på logiken bakom en sådan implementation så är den inte speciellt avancerad. Men det håller inte.

Låt säga att varje given konfiguration av schackbrädet har 40 rimliga drag. Det innebär att 40 bräden i nästa generation måste analyseras för att se vilket drag som är lönsamt eller ej. Men det ligger också i sakens natur att ett drag som inte direkt ger något, kan vara antingen förödande eller väldigt lönsamt längre fram. Så varför inte kosta på sig att titta på varje drags nästa generation?

I snitt har varje nästa generation 40 rimliga drag, vilket innebär att vi måste analysera ytterligare 40*40 (1600) drag. Men det är förmodligen inte slut där. För att hitta ljuset i tunneln behöver man troligen titta på draget därefter, där varje alternativ i sin tur har 40 rimliga konsekvenser (40 * 1600) vilket ger oss 64 000 spelplaner att analysera. Om matchen sträcker sig över tre drag måste vi titta på (64 000 * 40) 2,5 miljoner drag. Och så håller det på.

Låt oss fortsätta att anta att varje given situation i snitt bjuder 40 rimliga drag, så ger det följande effekt:

1 drag kräver 1 600 analyser.
2 drag kräver 64 tusen analyser.
3 drag kräver 2,6 miljoner analyser.
4 drag kräver 102 miljoner analyser.
5 drag kräver 4 miljarder analyser.
6 drag kräver 164 miljarder analyser.
7 drag kräver 6 554 miljarder analyser.
8 drag kräver 262 144 miljarder analyser.
9 drag kräver 10 485 760 miljarder analyser.
10 drag kräver 419 430 400 miljarder analyser.

Men eftersom vi inte vet vad den mänskliga spelaren tänker göra, måste vi efter varje tänkt drag skapa en gren för varje rimligt motdrag. Så egentligen ser 10 generationer ut så här:

1 drag kräver 1 600 analyser samt ytterligare 64 000 analyser av möjliga motdrag.
2 drag kräver 2,6 miljoner analyser samt ytterligare 102 miljoner analyser av möjliga motdrag.
3 drag kräver 4 miljarder analyser samt ytterligare 164 miljarder analyser av möjliga motdrag.
4 drag kräver 6 553 miljarder analyser samt ytterligare 262 144 miljarder analyser av möjliga motdrag.
5 drag kräver 10 485 760 miljarder analyser samt ytterligare 419 430 400 miljarder analyser av möjliga motdrag.
6 drag kräver 16 777 216 biljoner analyser samt ytterligare 671 088 640 biljoner analyser av möjliga motdrag.
7 drag kräver 26 843 triljoner analyser samt ytterligare 1 073 741 triljoner analyser av möjliga motdrag.
8 drag kräver 42 949 672 triljoner analyser samt ytterligare 1 717 986 918 triljoner analyser av möjliga motdrag.
9 drag kräver 68 719 476 triljarder analyser samt ytterligare 2 748 779 kvadriljoner analyser av möjliga motdrag.
10 drag kräver 109 951 kvadriljarder analyser.

Och eftersom en analys tar några bytes att hålla i datorns arbetsminne, kan man konstatera att det fallerar av den anledningen. Processtiden även på en väldigt stark dator kommer vara ett annat problem.

Genom att lära sig strategier kan man identifiera vilka situationer man bör undvika och vilka situationer man bör premiera, och på så vis reducera antalet analyser som behöver göras. Vilka öppningar är bra? Kanske ungefär 5 över 2 generationer. Då har vi åtminstone i startsituationen reducerat från över hundra miljoner analyser till en handfull. Ju fler sådana strategier man har, desto fler nonsensanalyser skär man bort. Men frågan är hur långt man kan komma genom att slumpa vilka analyser som faktiskt ska göras? Kan ett enkelt C#-program vinna mot en seriös schackdator genom att slumpmässigt välja vilka grenar som ska analyseras på vilket djup?

Categories: General