Nie wszystko zrobią algorytmy. Fascynująca tajemnica tasowania kart
Algorytmy to ważna rzecz, ale jak się okazuje - nie wszędzie są w stanie odwzorować rzeczywistości. Wystarczy jedynie spojrzeć na coś tak trywialnego jak... tasowanie kart.
Kiedy algorytmy nie są w stanie dogonić rzeczywistości
Jeśli tasowaliśmy kiedyś talię kart to jest duża szansa na to, że jesteśmy jedną osobą w historii ludzkości, która właśnie w taki sposób przetasowała karty. Przy 52 kartach działa to w taki sposób, że gdy mamy całą przetasowaną talię, to po pierwszej karcie z wierzchu istnieje 51 możliwości, jaka karta będzie następna. A potem mamy kolejną kartę, po której jest 50 kolejnych możliwości i tak dalej. Całość prowadzi nas do liczby wariacji ułożenia 52 kart będącego silnią 52. A takie działanie da nam wynik mający aż 67 zer (8 x 10⁶⁷). To kwadrylion razy więcej niż wszystkich atomów na Ziemi.
W praktyce więc szansa na to, że druga osoba po przetasowaniu stworzy taką samą sekwencję kart wcale nie równa się 1/52! Jedynka podzielona przez silnię z 52 wskaże nam jedynie na prawdopodobieństwo otrzymania jednego bardzo konkretnego rozdania kart.
W praktyce prawdopodobieństwo stworzenia tej samej talii kart przez dwie osoby wyrażone w procentach to 0,00000000000000000000000000000000000000000000000000000008 procent (8 x 10⁻⁴⁹). Nawet jeśli założymy, że każdy tasowałby talię kart 100 razy, to szanse wzrosną jedynie marginalnie (8 x 10⁻⁴³).
Po co tyle zachodu z liczbami i silnią? Zapytajcie twórców stron do grania w pokera online – np. PlanetPoker. Jak się okazuje, w późnych latach 90. stworzono algorytmy tasowania, które oferowały jedynie 200 tysięcy możliwych sekwencji przetasowanych kart, a nie silnię z 52.
Oprogramowanie odpowiedzialne za tasowanie używało generatora losowych liczb, który był zintegrowany z czasem systemowym komputera. Mechanizm tasowania wyliczał ile sekund minęło od północy i na bazie czasu, który aktualnie minął – tworzył konkretne przetasowania. Początkowo programiści myśleli, że można stworzyć 86 milionów wersji przełożeń kart. Jednak wyszło na to, że jeśli zorientujemy się, że przetasowania są dokładnie powiązane z aktualną godziną, dało się w 100 proc. rozgryźć, jakie karty wyjdą na wierzch – za każdym razem.
Na domiar złego, ówczesny algorytm resetował się co 24 godziny, a to ograniczało pulę unikatowych przetasowań. W praktyce strona PlanetPoker pozwalała jedynie na wygenerowanie 200 tysięcy unikatowych talii.
Kiedy w roku 1999 pracownicy firmy Reliable Software Technologies wykryli te potencjalne luki, twórcy pokerowych stron online wprowadzili nowy algorytm, zwany algorytmem Fishera-Yatesa (lub tasowaniem Knutha). Ten rodzaj algorytmu usunął synchronizację z zegarem systemowym komputera i przez to każda kombinacja 52 przetasowanych kart ma równe szanse pojawienia się w jednej sekwencji. Jest mały haczyk – nadal nie będzie to tyle kombinacji co przy silni z 52, będzie to 2¹²⁸. To dlatego, że generatory liczb losowych (RNG) w środowiskach programistycznych zazwyczaj korzystają z mechanizmów pseudolosowych (PNRG), które mają ograniczenia, w tym 128-bitowy stan liczb, a więc maksimum wyników to 2¹²⁸. Nie jest to ułomność algorytmu, ale raczej techniczne ograniczenie, choć mimo wszystko nadal prowadzi to do minimalnego skrzywienia uzyskiwanych wyników.
To wszystko pokazuje, że nie wszystko da się w pełni zastąpić algorytmem, ponieważ mają one również pewnego rodzaju ograniczenia. Podobna sytuacja ma miejsce z symulowaniem rzutów kostek. Wniosek jest taki, że lepiej grać w Warhammera albo Dungeons and Dragons na żywo.
