Liczba Shannona: ile partii szachowych jest możliwych?

Liczba Shannona jest często przywoływana, by pokazać bogactwo gry w szachy. Jest też świetnym materiałem do ćwiczenia potęg liczby 10, zapisu naukowego i rzędów wielkości, od gimnazjum po liceum. Warto jednak wiedzieć, skąd się wzięła, co dokładnie mierzy i czego nie mierzy.

Liczba Shannona

Ostrożny szacunek, około 10¹²⁰, liczby możliwych partii szachowych, zaproponowany przez amerykańskiego matematyka i inżyniera Claude'a Shannona w artykule „Programming a Computer for Playing Chess”, opublikowanym w 1950 roku w czasopiśmie Philosophical Magazine.

Liczba Shannona: skąd się wziął rachunek?

Claude Shannon (1916-2001) jest znany jako twórca teorii informacji. W 1950 roku opublikował jeden z pierwszych artykułów o programowaniu komputera do gry w szachy. Aby pokazać, że maszyna nie może po prostu obliczyć wszystkich ciągów posunięć, przedstawił szybki szacunek:

1. W typowej pozycji jest około 30 legalnych posunięć. Liczba ta pozostaje mniej więcej stała przez dużą część partii.
2. Ruch białych i następujący po nim ruch czarnych dają zatem około 30 × 30 = 900 możliwości, które Shannon zaokrągla do 10³.
3. Typowa partia trwa około 40 posunięć (40 posunięć białych i 40 czarnych) aż do poddania się jednego z graczy.
4. Liczba ciągów posunięć wynosi zatem około (10³)⁴⁰ = 10¹²⁰.

Shannon dodaje, że maszyna badająca jeden wariant na mikrosekundę potrzebowałaby ponad 10⁹⁰ lat, by obliczyć swój pierwszy ruch. Wnioskuje stąd, że program szachowy musi oceniać pozycje i wybierać warianty do zbadania, tak jak robi to człowiek.

Partie i pozycje to dwie różne liczby

Nie należy mylić liczby partii (ciągów posunięć) z liczbą pozycji (ustawień bierek na szachownicy). Tę samą pozycję można osiągnąć na miliony różnych sposobów.

Shannon szacował liczbę pozycji wzorem 64! / (32! × 8!² × 2!⁶), który zlicza sposoby ustawienia 32 bierek startowych na 64 polach; wynik wynosi około 4,6 × 10⁴², które zaokrąglił do „rzędu 10⁴³”. Nowoczesny szacunek Johna Tromપa, (4,82 ± 0,03) × 10⁴⁴ legalnych pozycji, uzyskano inaczej: losując dwa miliony pozycji ze zbioru, który potrafimy zliczyć, a następnie sprawdzając, które z nich są rzeczywiście osiągalne w partii, z pomocą Petera Österlunda przy analizie komputerowej.

Pierwsze posunięcia: dokładne policzenie

Na początku partii można policzyć dokładnie. Biali mają 20 możliwych posunięć (16 ruchów pionami i 4 ruchy skoczkami). Czarni także. Otrzymujemy:

Wartości przeliczone programem od pozycji początkowej (zliczenie wszystkich legalnych ciągów posunięć).

Już po dwóch posunięciach każdej ze stron przekraczamy 197 000 możliwych ciągów. Mnożnik rośnie potem, bo bierki wychodzą na pole i mają więcej wyborów: to właśnie uzasadnia założenie około trzydziestu posunięć w pozycji.

Skąd wzięło się oszacowanie 10¹²³?

W 1994 roku holenderski badacz Victor Allis przeliczył to z innymi założeniami: około 35 możliwych posunięć w pozycji oraz partie liczące 80 półruchów (po 40 posunięć każdej ze stron). Otrzymujemy 35⁸⁰. Aby zapisać to w postaci potęgi 10, używamy logarytmu dziesiętnego: 80 × log(35) ≈ 80 × 1,544 ≈ 123,5. Stąd rząd wielkości 10¹²³. Metoda jest dokładnie taka sama jak u Shannona, zmieniają się tylko parametry, co pokazuje, jak bardzo wynik zależy od przyjętych założeń.

Przy dokładnych parametrach Shannona 900⁴⁰ wynosi zresztą około 10¹¹⁸, a nie 10¹²⁰: to zaokrąglenie 900 do 1000 daje ładną okrągłą liczbę. Przy tak ogromnym rzędzie wielkości ta różnica nie ma praktycznego znaczenia.

Jak to wyjaśnić na lekcji

Liczba Shannona świetnie nadaje się do ćwiczenia potęg liczby 10, czyli do materiału z klasy 4^e. Oto kilka pomysłów:

• Zapisać liczbę: 10¹²⁰ zapisuje się jako jedynkę i 120 zer. Można kazać uczniom zapisać ją na tablicy… i zmierzyć, ile to zajmie czasu.
• Liczyć z potęgami: (10³)⁴⁰ = 10^{3 × 40} = 10¹²⁰ to bezpośrednie zastosowanie reguły (a^m)ⁿ = a^{m × n}.
• Porównywać rzędy wielkości: 10¹²⁰ podzielone przez 10⁸⁰ daje 10⁴⁰. Nawet gdyby każdy atom we Wszechświecie był komputerem, każdy z nich musiałby i tak przetworzyć 10⁴⁰ partii.
• Dyskutować założenia: dlaczego 30 posunięć w pozycji? dlaczego 40 posunięć w partii? Co zmienia partia liczące 60 posunięć? (Odpowiedź: (10³)⁶⁰ = 10¹⁸⁰.)

Liczba ziaren na szachownicy z Sissy, około 1,8 × 10¹⁹, wydaje się przy tym drobna: porównanie obu liczb to dobre ćwiczenie. Zobacz obliczenia dla szachownicy z Sissy.

Czy można „rozwiązać” szachy?

Rozwiązać grę to wiedzieć z pewnością, jaki będzie wynik (wygrana białych, czarnych lub remis) przy idealnej grze obu stron. Liczba Shannona pokazuje, że nie da się tego zrobić, przeszukując wszystkie partie. Komputery rozwiązały jednak wszystkie pozycje z niewielką liczbą bierek, dzięki tablicom końcówek. Aby sprawdzić, na jakim etapie jest ta kwestia, Palais des Échecs zastanawiał się, czy szachy będą kiedyś rozwiązane.

Liczba Shannona i inne wielkie liczby szachownicy

Szachownica to mała fabryka wielkich liczb: 2⁶⁴ − 1 ziaren Sissy, ponad 26 bilionów zamkniętych dróg skoczka, 92 rozwiązania problemu ośmiu hetmanów, 204 kwadraty… Znajdziesz je na naszej stronie wielkie łamigłówki szachownicy.