Matematyka w grach – Dobble i Znaj Znak Ten tekst przeczytasz w 5 minut

Metody matematyczne mogą być wykorzystywane nie tylko do analizowania przebiegu rozgrywki, ale także do stworzenia odpowiedniego zestawu rekwizytów.  Czasami jednak są z tym pewne problemy, bo zagadnienia kombinatoryczne mają tendencje do niesamowicie szybkiego wzrostu.

Jakie to może wywołać efekty, pokazuje wypowiedź, która pojawiła się w kwietniu 2012 na forum grupy Monsoon, podczas prac nad grą Znaj znak:

„Niestety algorytm „brute force” w tym przypadku zupełnie odpada, oszacowałem czas generowania wszystkich kart w ten sposób i wyszła liczba rzędu 10^9 lat.”

Zapewne nie każdy zna grę Znaj znak, ale chyba prawie każdy zna Dobble. Karty do obu tych gier spełniają takie same warunki:

• na każdej karcie jest n różnych symboli
• każdy symbol występuje na co najmniej dwóch kartach
• każda para kart ma dokładnie jeden wspólny symbol

Zobaczmy więc, w jaki sposób powstają karty do tych gier i skąd się wziął tak ogromny czas ich tworzenia. Oczywiście nie chodzi mi o fizyczne powstawanie kart w drukarni, tylko o algorytm tworzenia ich matematycznej struktury.

Zacznijmy od najprostszego, wręcz trywialnego przypadku n=2. Oznaczając symbole na kartach kolejnymi literami alfabetu, możemy przedstawić jedyny możliwy układ w postaci: AB, AC i BC. Wszystkie trzy warunki są jak widać spełnione. Łatwo zauważyć, że nie można dodać ani kolejnego czwartego symbolu, ani kolejnej karty.

Rozpatrzmy teraz przypadek n=3, czyli trzy symbole na karcie. Pierwsza karta będzie miała np. postać ABC, a druga ADE. Jeżeli na trzeciej karcie ma być symbol B, to nie może być na niej ani A, ani C i może być tylko jeden symbol z pary DE. Żeby na tej karcie były także trzy symbole, musimy wprowadzić szósty symbol F. Trzecia karta będzie miała zatem postać BDF, a czwarta CEF. Otrzymaliśmy w rezultacie następujący układ czterech kart z sześcioma symbolami: ABC, ADE, BDF i CEF. Dużo ładniej wygląda to na obrazku, pochodzącym z artykułu „Dobble et la  géométrie finie”, którego autorem jest francuski matematyk Maksym Bourrigan.

Zamiast liter, występują tu kolorowe symbole, a każdej karcie odpowiada kółko z trzema symbolami. Kolorowymi paskami połączone zostały karty, zawierające symbole w kolorze pasków.

Dla n=3, czyli trzech symboli na karcie, mamy 6 różnych symboli i 4 karty. Dla dowolnego n wzór na liczbę różnych symboli będzie miał postać n(n+1)/2, a liczba kart będzie opisana wzorem k=n+1. Dla 4 symboli na karcie będzie zatem 10 różnych symboli i 5 kart, dla 5 symboli – 15 różnych symboli i 6 kart, a dla n=8 (tak, jak w grze Dobble) – 36 symboli i 9 kart. Talia kart do gry Dobble złożona z 9 kart? Trochę mało. Przecież powinno być ich ponad 50. Skąd ta różnica? Wszystko przez to, że drugi postulat (każdy symbol występuje na co najmniej dwóch kartach) został zrealizowany w granicznej postaci tzn. każdy symbol wystąpił na dokładnie dwóch kartach.

Przyjrzyjmy się dokładnie obrazkowi powyżej. Można zauważyć, że na żadnej karcie nie występuje jednocześnie niebieski i zielony symbol, czarny symbol nie występuje razem z żółtym, a czerwony z białym. Podobna sytuacja jest w zapisie literowym – na żadnej karcie nie ma jednocześnie A i F, B i E ani C i D. Dołączając siódmy symbol G, możemy utworzyć trzy nowe karty: AFG, BEG i CDG. Wraz z czterema poprzednimi tworzą one idealnie symetryczny układ, w którym każda para symboli występuje na jakiejś karcie. Graficznie (za tym samym źródłem co poprzednio) można to przedstawić tak:

 

 

Jak widać, mamy teraz 7 kart i 7 różnych symboli (doszedł fioletowy znak ∞), a każdy symbol występuje na trzech kartach, połączonych kolorowym paskiem. Jako ciekawostkę dodam, że matematycy nazywają taki obiekt płaszczyzną Fano.

Po dodaniu warunku „każda para symboli występuje raz na jakiejś karcie”, który jak można zaobserwować, został zrealizowany na drugim rysunku, wzór na liczbę różnych symboli oraz na liczbę kart (bo te dwie wielkości są teraz równe) ma postać k=n^2-n+1. Dla n=8 daje to 57 różnych symboli i 57 kart. W talii Dobble kart jest 55, więc jak ktoś ma ochotę, może sprawdzić, jakich dwóch zestawów symboli brakuje.

Wciąż jednak nie widać jakichś przerażająco wielkich liczb, a zależność kwadratowa we wzorze na liczbę kart, to wręcz marzenie twórców algorytmów. Niestety, tak dobrze to wygląda tylko dlatego, że z góry założyliśmy, jak mają wyglądać karty. Dla małej liczby symboli na kartach (w naszym przypadku trzech) da się to zrobić bez trudu „ręcznie”. Ale przy większej liczbie już to takie proste nie jest.

Pozostańmy jeszcze przez chwilę przy trzech symbolach na kartach. Wiemy już, że wszystkich symboli jest wtedy 7. Ile różnych kart można stworzyć z tych siedmiu symboli, jeżeli na każdej karcie mają być trzy różne? Jest to kombinacja bez powtórzeń trzech elementów ze zbioru siedmiu i takich kombinacji może być 35, czyli mamy 35 różnych kart. Wiemy, że kart ma być w zestawie 7. Na ile sposobów można z talii 35 kart wybrać 7? Okazuje się, że jest to 6.724.520 czyli już liczba całkiem spora. A tylko 30 sposobów prowadzi do właściwego rozwiązania, czyli takiego, w którym każda para kart ma dokładnie jeden wspólny symbol.

Jak to wygląda dla kolejnych liczb symboli na kartach, aż do 8, czyli tylu, ile jest w grze Dobble, pokazuje poniższa tabelka:

 

Liczba symboli na karcie	Liczba różnych symboli	Liczba możliwych kart	Liczba sposobów wyboru kart
2	3	3	1
3	7	35	6.724.520
4	13	715	1,8 x 10^27
5	21	20.349	6 x 10^70
6	31	736.281	9 x 10^147
7	43	32.224.114	1 x 10^270
8	57	1.652.411.475	7 x 10^448

 

Uwaga: Nie wiem, czy da się skonstruować układ 43 kart z 7 różnymi symbolami na każdej. Dla innych liczb symboli z tabelki jest to na pewno możliwe. Ogólnie da się to zrobić dla każdej takiej liczby n, dla której n-1 jest liczbą pierwszą i dla niektórych innych, np. dla 5.

A jak to wygląda dla gry Znaj Znak, w której na każdej karcie jest 12 symboli? Okazuje się, że musimy wtedy użyć 133 różnych symboli. Z tych 133 symboli można utworzyć przeszło 3,8×10^16 różnych kart (dokładnie 38.359.579.905.883.600). Liczby sposobów, na jakie spośród tych kart można wybrać 133 nie będę dokładnie podawał, bo liczy ona blisko 2000 cyfr. Nic więc dziwnego, że próba rozwiązania tego zagadnienia metodą „brute force” musiałaby trwać nie tyle latami, co wręcz milionami lat.

Na szczęście istnieje algorytm, który pozwala zautomatyzować proces tworzenia kart, działający dla każdej liczby symboli na karcie, która jest większa o 1 od liczby pierwszej.  Zarówno Dobble (8 symboli), jak i Znaj znak (12 symboli) warunek ten spełniają, a algorytm jest na tyle szybki, że stworzenie zestawu kart do gry Znaj znak trwało poniżej jednej sekundy.