Home / Artykuły / Felietony / Matematyka w grach – Dobble i Znaj Znak

Matematyka w grach – Dobble i Znaj Znak

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.

Cztery karty

Cztery karty

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:

 

Siedem kart

Siedem kart

 

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.

13 komentarzy

  1. WRS

    Pysznie się to czyta! :)

  2. Dla nie znających francuskiego rzekomo w podobnym tonie pisze ten profesor matematyki:
    http://www.deltami.edu.pl/temat/matematyka/gry_zagadki_paradoksy/2014/03/30/Naprawde_ciekawa_gra/
    Piszę ,,rzekomo”, bo nie wgryzałem się w pierwszy ani drugi artykuł.

    • MichalStajszczak

      Zarówno linkowany przeze mnie francuski artykuł, jak i podlinkowany przez bodziosława artykuł polskiego profesora pokazują, że strukturę gry Dobble można opisać, posługując się pojęciami geometrii rzutowej i dzięki temu wykorzystać do analizy gry wyniki prac z tego działu matematyki. Ja w swoim tekście nie chciałem pisać o klasach abstrakcji, ciałach skończonych i działaniach modulo nie tylko dlatego, że dla sporej części osób z naszego forum byłoby to kompletnie nieprzystępne, ale przede wszystkim dlatego, że cel mojego artykułu był całkiem inny.

  3. MichalStajszczak

    Drobne sprostowanie do jednej informacji z mojego tekstu: zamiast „nie wiadomo, czy się da stworzyć talię 43 kart z 7 symbolami” powinienem napisać „udowodniono, że sie nie da”

    • Na jakimś forum znalazłem ten algorytm + wyliczenie dla 7 liczb i 43 kart. Jest błędne?

      1,2,3,4,5,6,7,
      1,8,9,10,11,12,13,
      1,8,9,10,11,12,13,
      1,14,15,16,17,18,19,
      1,14,15,16,17,18,19,
      1,20,21,22,23,24,25,
      1,20,21,22,23,24,25,
      1,26,27,28,29,30,31,
      1,26,27,28,29,30,31,
      1,32,33,34,35,36,37,
      1,32,33,34,35,36,37,
      1,38,39,40,41,42,43,
      1,38,39,40,41,42,43,
      2,8,14,20,26,32,38,
      2,8,14,20,26,32,38,
      2,9,15,21,27,33,39,
      2,9,15,21,27,33,39,
      2,10,16,22,28,34,40,
      2,10,16,22,28,34,40,
      2,11,17,23,29,35,41,
      2,11,17,23,29,35,41,
      2,12,18,24,30,36,42,
      2,12,18,24,30,36,42,
      2,13,19,25,31,37,43,
      2,13,19,25,31,37,43,
      3,8,15,22,29,36,43,
      3,8,15,22,29,36,43,
      3,9,16,23,30,37,38,
      3,9,16,23,30,37,38,
      3,10,17,24,31,32,39,
      3,10,17,24,31,32,39,
      3,11,18,25,26,33,40,
      3,11,18,25,26,33,40,
      3,12,19,20,27,34,41,
      3,12,19,20,27,34,41,
      3,13,14,21,28,35,42,
      3,13,14,21,28,35,42,
      4,8,16,24,26,34,42,
      4,8,16,24,26,34,42,
      4,9,17,25,27,35,43,
      4,9,17,25,27,35,43,
      4,10,18,20,28,36,38,
      4,10,18,20,28,36,38,
      4,11,19,21,29,37,39,
      4,11,19,21,29,37,39,
      4,12,14,22,30,32,40,
      4,12,14,22,30,32,40,
      4,13,15,23,31,33,41,
      4,13,15,23,31,33,41,
      5,8,17,20,29,32,41,
      5,8,17,20,29,32,41,
      5,9,18,21,30,33,42,
      5,9,18,21,30,33,42,
      5,10,19,22,31,34,43,
      5,10,19,22,31,34,43,
      5,11,14,23,26,35,38,
      5,11,14,23,26,35,38,
      5,12,15,24,27,36,39,
      5,12,15,24,27,36,39,
      5,13,16,25,28,37,40,
      5,13,16,25,28,37,40,
      6,8,18,22,26,36,40,
      6,8,18,22,26,36,40,
      6,9,19,23,27,37,41,
      6,9,19,23,27,37,41,
      6,10,14,24,28,32,42,
      6,10,14,24,28,32,42,
      6,11,15,25,29,33,43,
      6,11,15,25,29,33,43,
      6,12,16,20,30,34,38,
      6,12,16,20,30,34,38,
      6,13,17,21,31,35,39,
      6,13,17,21,31,35,39,
      7,8,19,24,29,34,39,
      7,8,19,24,29,34,39,
      7,9,14,25,30,35,40,
      7,9,14,25,30,35,40,
      7,10,15,20,31,36,41,
      7,10,15,20,31,36,41,
      7,11,16,21,26,37,42,
      7,11,16,21,26,37,42,
      7,12,17,22,27,32,43,
      7,12,17,22,27,32,43,
      7,13,18,23,28,33,38

      • 1 1 2 3 4 5 6 7
        2 1 8 9 10 11 12 13
        3 1 14 15 16 17 18 19
        4 1 20 21 22 23 24 25
        5 1 26 27 28 29 30 31
        6 1 32 33 34 35 36 37
        7 1 38 39 40 41 42 43
        8 2 8 14 20 26 32 38
        9 2 9 15 21 27 33 39
        10 2 10 16 22 28 34 40
        11 2 11 17 23 29 35 41
        12 2 12 18 24 30 36 42
        13 2 13 19 25 31 37 43
        14 3 8 15 22 29 36 43
        15 3 9 16 23 30 37 38
        16 3 10 17 24 31 32 39
        17 3 11 18 25 26 33 40
        18 3 12 19 20 27 34 41
        19 3 13 14 21 28 35 42
        20 4 8 16 24 26 34 42
        21 4 9 17 25 27 35 43
        22 4 10 18 20 28 36 38
        23 4 11 19 21 29 37 39
        24 4 12 14 22 30 32 40
        25 4 13 15 23 31 33 41
        26 5 8 17 20 29 32 41
        27 5 9 18 21 30 33 42
        28 5 10 19 22 31 34 43
        29 5 11 14 23 26 35 38
        30 5 12 15 24 27 36 39
        31 5 13 16 25 28 37 40
        32 6 8 18 22 26 36 40
        33 6 9 19 23 27 37 41
        34 6 10 14 24 28 32 42
        35 6 11 15 25 29 33 43
        36 6 12 16 20 30 34 38
        37 6 13 17 21 31 35 39
        38 7 8 19 24 29 34 39
        39 7 9 14 25 30 35 40
        40 7 10 15 20 31 36 41
        41 7 11 16 21 26 37 42
        42 7 12 17 22 27 32 43
        43 7 13 18 23 28 33 38

        • Michał Stajszczak
          Michał Stajszczak

          Niestety, „zacytowany” układ kart nie spełnia podstawowego warunku: każda para kart musi mieć dokładnie jeden wspólny symbol. A np. karty o numerach 30 i 43 żadnego wspólnego symbolu nie mają, a karty 31 i 43 maja dwa wspólne symbole (13 i 28)

  4. Witam, bardzo ciekawy artykuł :) Długo go szukałem ale w końcu znalazłem!

    A czy gdzieś można zdobyć ten algorytm? Czy raczej program w którym ten algorytm zadziała? Czy to jest darmowe czy raczej trzeba bulić za taką zabawę? :)

    Jestem ciekaw bo miałem pomysł stworzyć coś swojego właśnie z 7 symbolami i ugrzązłem już przy trzecim symbolu:) Bo ja głupi myślałem, że da się to ręcznie jakoś wykombinować :D

    Pozdrawiam i czekam na odpowiedź ;)

    • MichalStajszczak
      MichalStajszczak

      Oczywiście program można kupić :) Ale można też znaleźć najistotniejszy jego fragment (w języku Visual Basic) schowany w spoilerze we wpisie z Cz kwi 12, 2012 8:48 pm w wątku „Regularne spotkania testowe – Monsoon Group”

  5. Macie może link do tego a algorytmu?

  6. Proszę – tu git z pythonem github.com/WRadigan/pySpot-It a tu są linki do podbrania pdf z algorytmem radiganengineering.com/2013/01/spot-it-howd-they-do-that/

  7. I tu jeszcze krok po kroku jak zrobić sobie własną grę – lilioweprojekty.pl/zabawki/zrobmy-sobie-dobble/

  8. Wszystkie pary w dollbe się zgadzają -,-

Leave a Reply

Your email address will not be published. Required fields are marked *

*