Shannon-tallet: hvor mange skakpartier er mulige?

Shannon-tallet nævnes ofte for at illustrere skakspillets rigdom. Det er også et godt redskab til at arbejde med potenser af 10, videnskabelig notation og størrelsesordener, fra mellemskolen til gymnasiet. Men man skal vide, hvor det kommer fra, hvad det præcist måler, og hvad det ikke måler.

Shannon-tallet

Forsigtigt skøn, ca. 10¹²⁰, over antallet af mulige skakpartier, foreslået af den amerikanske matematiker og ingeniør Claude Shannon i artiklen »Programming a Computer for Playing Chess«, udgivet i 1950 i tidsskriftet Philosophical Magazine.

Shannon-tallet: hvor kommer beregningen fra?

Claude Shannon (1916-2001) er kendt som grundlæggeren af informationsteorien. I 1950 udgav han en af de første artikler om at programmere en computer til at spille skak. For at vise at en maskine ikke bare kan beregne alle trækfølger, lavede han et hurtigt skøn:

1. I en typisk stilling er der ca. 30 lovlige træk. Tallet forbliver nogenlunde konstant under en stor del af partiet.
2. Et hvidt træk efterfulgt af et sort træk giver altså ca. 30 × 30 = 900 muligheder, som Shannon rundede op til 10³.
3. Et typisk parti varer ca. 40 træk (40 hvide og 40 sorte træk) indtil en spiller giver op.
4. Antallet af trækfølger er altså ca. (10³)⁴⁰ = 10¹²⁰.

Shannon tilføjer, at en maskine, der undersøgte én variant per mikrosekund, ville bruge over 10⁹⁰ år på at beregne sit første træk. Han konkluderer, at et skakprogram må vurdere stillinger og vælge hvilke varianter der skal undersøges, ligesom et menneskeligt spiller gør.

Partier og stillinger: to forskellige tal

Man må ikke forveksle antallet af partier (trækfølger) med antallet af stillinger (placeringer af brikkerne på brættet). En og samme stilling kan nås via millioner af forskellige partier.

Shannon skønnede antallet af stillinger med formlen 64! / (32! × 8!² × 2!⁶), som tæller måderne at placere de 32 startbrikker på de 64 felter; resultatet er ca. 4,6 × 10⁴², som han rundede op til »ca. 10⁴³«. Johns Tromps moderne skøn, (4,82 ± 0,03) × 10⁴⁴ lovlige stillinger, er opnået på en anden måde: ved at trække to millioner stillinger tilfældigt fra en mængde, man kan tælle, og derefter kontrollere hvilke der reelt kan nås i et parti, med hjælp fra Peter Österlund til den computermæssige analyse.

De første træk: en nøjagtig optælling

I begyndelsen af partiet kan man tælle præcist. Hvid har 20 mulige træk (16 bondetræk og 4 springertræk). Sort har også 20. Man får:

Værdier genberegnet med program ud fra startstillingen (optælling af alle lovlige trækfølger).

Allerede efter to træk fra hver side overstiger man 197 000 mulige trækfølger. Multiplikationsfaktoren stiger derefter, fordi brikkerne kommer ud og har flere valgmuligheder: det er det, der begrunder antagelsen om ca. tredive træk per stilling.

Hvor kommer skønnet på 10¹²³ fra?

I 1994 gentog den hollandske forsker Victor Allis beregningen med andre antagelser: ca. 35 mulige træk per stilling og partier på 80 halvtræk (40 træk fra hver side). Det giver 35⁸⁰. For at skrive det som potens af 10 bruger man den briggske logaritme: 80 × log(35) ≈ 80 × 1,544 ≈ 123,5. Heraf størrelsesordenen 10¹²³. Metoden er præcis Shannons; kun parametrene ændrer sig, hvilket viser, hvor meget resultatet afhænger af antagelserne.

Med Shannons præcise parametre er 900⁴⁰ i øvrigt ca. 10¹¹⁸ og ikke 10¹²⁰: det er afrundingen af 900 til 1 000, der giver det pæne runde tal. For en størrelsesorden så gigantisk er forskellen uden praktisk betydning.

Sådan forklarer man det i klassen

Shannon-tallet er ideelt til at arbejde med potenser af 10, som står på pensum i 4^e. Nogle ideer:

• Skriv tallet: 10¹²⁰ skrives med en 1 efterfulgt af 120 nuller. Lad eleverne skrive det på tavlen … og mål hvor lang tid det tager.
• Regn med potenser: (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ er en direkte anvendelse af reglen (a^m)ⁿ = a^{m × n}.
• Sammenlign størrelsesordener: 10¹²⁰ divideret med 10⁸⁰ giver 10⁴⁰. Selv hvis hvert atom i universet var en computer, skulle hver af dem stadig behandle 10⁴⁰ partier.
• Diskuter antagelserne: hvorfor 30 træk per stilling? hvorfor 40 træk per parti? Hvad ændrer et parti på 60 træk? (Svar: (10³)⁶⁰ = 10¹⁸⁰.)

Antallet af korn på Sissas skakbræt, ca. 1,8 × 10¹⁹, virker lille i sammenligning: at sammenligne de to er en god øvelse. Se beregningen af Sissas skakbræt.

Kan man »løse« skak?

At løse et spil betyder at vide med sikkerhed, hvilket resultat (sejr til hvid, sejr til sort eller remis) et perfekt spil fra begge sider giver. Shannon-tallet viser, at det ikke kan gøres ved at undersøge alle partier. Computere har dog løst alle stillinger med få brikker, takket være endespilstabeller. For at se, hvor langt spørgsmålet er nået, har Le Palais des Échecs spurgt, om skak en dag kan blive løst.

Shannon-tallet og de andre store tal på skakbrættet

Skakbrættet er en lille fabrik for store tal: 2⁶⁴ − 1 korn fra Sissa, over 26 000 milliarder lukkede springerveje, 92 løsninger til otte dronninger, 204 kvadrater … Find dem på vores side de store hjernebrækkere på skakbrættet.