Piękno kombinatoryki

Ilość rzeczy w porównaniu do ilości wzajemnych kombinacji tychże rzeczy jest na ogół zdumiewająco mała. Weźmy na przykład grę w Go, która – znana od tysiącleci – stała się ostatnio jeszcze bardziej popularna, a to za sprawą AlphaGo, który rozgromił niedawno 4:1 Lee Sedola, jednego z arcymistrzów światowej klasy.

Albo na przykład ilość możliwych obrazów na matrycy złożonej z dwunastu pikseli (3×4), i z 24-bitową paletą kolorów – niby nic nadzwyczajnego, a jednak ilość możliwych do uzyskania na takiej matrycy obrazów jest większa – mniej więcej dziesięć milionów razy – od ilości atomów w naszym Kosmosie. I bardzo zbliżona do ilości możliwych potasowań talii 52-karcianej.

Porównywanie różnych rzeczy do ilości atomów w Kosmosie jest dość popularnym chwytem, mającym unaocznić słuchaczowi stopień komplikacji danego zjawiska. Jednak – chociaż mamy do czynienia z liczbami o ponad-astronomicznych rozmiarach – dziś już nikogo one nie dziwią. Każdy miał kombinatorykę gdzieś tam w okolicach późnej podstawówki lub wczesnej szkoły średniej, nic nadzwyczajnego.

Ale czasem jednak trafiają się perełki, które potrafią zaskoczyć nawet starych wyjadaczy.

Wróćmy do Go. W Go gra się na planszy 19×19 pól, aczkolwiek początkujący uczą się na ogół na mniejszej planszy, 13×13 pól. Również tutaj ilość możliwych ustawień planszy jest niewyobrażalnie wielka.

A co, gdybyśmy zmniejszyli planszę jeszcze bardziej?

Pójdźmy w ekstremum i zobaczmy, jak wygląda sytuacja na planszy 2×2.

(Plansza 1×1 nie ma za bardzo sensu, ponieważ nikt nie może wykonać pierwszego ruchu i każda gra kończy się remisem, zanim się zacznie)

Na każdym z czterech pól może być albo biały kamień, albo czarny, albo może ono być puste. A więc ilość ustawień kamieni na planszy 2×2 wynosi 3^4=81.

Jednak część z tych ustawień jest nielegalna: w Go każda grupa kamieni musi mieć co najmniej jeden oddech. Automatycznie eliminujemy więc wszystkie ustawienia czterech kamieni (jest ich 16) oraz część ustawień 3 kamieni (dokładnie 8 z nich jest nielegalnych). Pozostaje nam 57 możliwych legalnych ustawień.

No i teraz proste pytanie: na ile sposobów można rozegrać partię w Go na planszy 2×2 pola?

Mając tylko 57 możliwych ustawień… No nie wiem. Kilkaset? Kilka tysięcy? Bo chyba nie miliony, prawda?

Prawda. Z tym, że – jak się już Czytelnik domyśla – gówno prawda 😉

Partię Go na planszy 2×2 można rozegrać na 386356909593 różnych sposobów.

Tak. 386 miliardów ze sporym hakiem.

Ech, kombinatoryka…

Na zakończenie jeszcze jedna duża, kompletnie bezużyteczna liczba, a mianowicie ilość legalnych pozycji (czyli ustawień kamieni) dla największej planszy Go, czyli 19×19 pól. Ilość ta wynosi dokładnie 20 816 819 938 197 998 469 947 8633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935 pozycji.

Żartowałem z tym zakończeniem 😉 Jeszcze jeden drobiażdżek, tym razem „ciut” większy od poprzedniego: skoro na planszy 2×2 jest ponad trzysta miliardów możliwych rozegrań, to na ile sposobów można rozegrać partię w Go na planszy 19×19 pól?

Otóż dokładna wartość nie jest znana i nie zapowiada się, żeby została ona wyznaczona za naszego żywota. Jednak możemy przynajmniej próbować znaleźć jakieś dolne i górne ograniczenie tej kompletnie nikomu niepotrzebnej wielkości.

Najpierw wróćmy do ww. ilości możliwych pozycji: trochę ponad 2 x 10^170.

Jeżeli wyeliminujemy cykle (a więc takie partie, w których jakieś ustawienie kamieni powtarza się), oraz przyjmiemy, że po każdym ruchu przeciwnik ma nie więcej niż 361 możliwych odpowiedzi, absolutny górny limit na ilość rozegranych partii możemy określić jako 361^(2×10^170), czyli liczba mniej więcej (5.3 x 10^170) – cyfrowa. Ale takie górne ograniczenie jest kompletną bzdurą, bo zupełnie nie eliminuje rozgrywek niezgodnych z przepisami.

Paru jajogłowym udało się wykombinować dolną granicę ilości możliwych gier, jako 10^(10^48), czyli jedynka i 10^48 zer.

Gdyby chcieć rozegrać pojedynczą partię, która miałaby 10^48 ruchów, należałoby wykonywać około dziesięciu kwintylionów ruchów na sekundę, żeby gra została ukończona w czasie, jaki upłynął od chwili powstania naszego Wszechświata, do chwili, w której piszę te słowa. Jak widać rozegranie takiej pojedynczej partii mogłoby sprawiać odrobinę problemów technicznych. A co dopiero rozegranie wszystkich 10^(10^48) partii…

Tak, Moiściewi, kombinatoryka to bydlę nienażarte, powiadam Wam.

Autor: xpil

Po czterdziestce. Żonaty. Dzieciaty. Komputerowiec. Krwiodawca. Emigrant. Rusofil. Lemofil. Sarkastyczny. Uparty. Mól książkowy. Ateista. Apolityczny. Nie oglądam TV. Uwielbiam matematykę. Walę prosto z mostu. Gram na paru instrumentach. Lubię planszówki. Słucham bluesa, poezji śpiewanej i kapel a’capella. || Kliknij tutaj po więcej szczegółów ||

Dodaj komentarz

Bądź pierwszy!

Powiadom o
avatar
wpDiscuz