Przeskocz do treści

Delta mi!

Loading

Informatyczny kącik olimpijski

Gra w karty

Tomasz Kazana

o artykule ...

  • Publikacja w Delcie: listopad 2017
  • Publikacja elektroniczna: 31 października 2017
  • Autor: Tomasz Kazana
    Afiliacja: Instytut Informatyki, Uniwersytet Warszawski
  • Wersja do druku [application/pdf]: (48 KB)

W tym odcinku IKO omówimy zadanie Gra w karty, które pojawiło się podczas pierwszej rundy konkursu "Potyczki Algorytmiczne 2016".

obrazek

Zadanie ma bardzo atrakcyjną warstwę fabularną, gdyż pojawia się w niej nie tylko popularny Bajtek, ale i inny amator gry w karty: Bitek. Obaj panowie pragną rozstrzygnąć, kto jest lepszy w karcianą grę Magiczne Stwory. Co ciekawe, dla ostatecznego wyniku ważniejsze od samej rozgrywki będzie to, co dzieje się jeszcze przed jej rozpoczęciem, a mianowicie wybór talii kart.

Zakładamy, że Bajtek dysponuje zestawem |n talii kart do gry w Magiczne Stwory, konkretnie taliami A1, Podobnie Bitek ma talie B1,...,Bn. Do gry potrzebne są dwie talie, a więc umówiono się, że jedna z talii pochodzić będzie od Bajtka, a druga - od Bitka. Gdy już ustalimy wybór kart, to sama rozgrywka będzie deterministyczna i łatwo potrafimy z góry powiedzieć (tzn: te informacje podane są jako dane wejściowe), kto wygra, ewentualnie, że będzie remis.

Metoda wyboru talii do gry jest następująca. Naprzemiennie, poczynając od Bajtka, każdy z graczy odrzuca jedną z talii przeciwnika. Prawdziwą rozgrywkę zaczynamy, gdy każdy z graczy ma już tylko po jednej talii. Celem zadania jest stwierdzenie, czy Bajtek ma strategię wygrywającą. Jeśli nie - to, czy chociaż potrafi zapewnić sobie remis.

Zanim przejdziemy do rozwiązania tego zadania, spróbujemy się pokusić o jego redukcję do problemu prostszego. Twierdzę, że jeśli wybór talii byłby inny (prostszy), to nie wpłynęłoby to na szanse Bajtka. Rozważmy więc taką wersję wyboru talii, gdzie najpierw Bajtek po prostu wybiera pewną talię |B j z zestawu Bitka, po czym Bitek dowolnie dobiera do niej jakąś talię Ai z zestawu Bajtka i obaj zaczynają grać kartami |Ai

Dlaczego taki wybór talii nie jest istotnie różny od oryginalnego?

Po pierwsze: w obu wersjach to Bajtek decyduje, która z talii Bitka (oznaczmy ją przez ¯B j ) weźmie udział w rozgrywce. Istotnie, w wersji uproszczonej jest to wprost powiedziane, natomiast w oryginalnej: to Bajtek kolejno odrzuca talie Bitka, a więc to właśnie on kontroluje, która na końcu zostanie.

Nieco trudniej dowieść drugiej własności, to znaczy tej, że Bitek może dowolnie dobrać talię A¯i do Bj. |¯ W wersji uproszczonej dostajemy to wprost z definicji, ale w oryginalnej nie jest to wcale jasne. Oczywiście, to Bitek odrzuca kolejno talie Bajtka, ale nie wie przecież z góry, jakie będzie  ¯ Bj , co niesie ryzyko odrzucenia A¯i na jakimś wczesnym etapie procesu wyboru. Wykażemy przez indukcję, że Bitek jest w stanie - mimo wszystko - zachować należytą ostrożność.

Dla n = 1 nie mamy żadnego wyboru, więc baza indukcji jest trywialna. Załóżmy więc, że n > 1 oraz że Bajtek zgłasza odrzucenie talii |Bk. Dodatkowo oznaczmy jako Am tę talię, którą dobrałby Bitek do |Bk. Mamy teraz dwa przypadki. Pierwszy jest wtedy, gdy Am nie byłaby dobrana dla żadnego innego B j poza Bk. Wówczas bez żalu Bitek może odrzucić A W przeciwnym przypadku zakładamy, że A jest dobrana do więcej niż jednego B j. Oznacza to, że funkcja dobierająca talie Ai do Bj | nie jest różnowartościowa, a więc istnieje talia |Az, która nigdy nie byłaby dobrana. Tym razem to z tą talią Bitek może się pożegnać i przejść indukcyjnie do problemu rozmiaru |(n− 1).

Skoro już uzasadniliśmy równoważność zadania dla znacznie prostszego modelu, możemy bardzo łatwo je rozwiązać. Po pierwsze: jeśli dla każdej talii |B j istnieje taka talia Ai, że karty Ai | dają zwycięstwo Bitkowi, to Bitek ma strategię wygrywającą. Po drugie: jeśli dla każdej talii |B j istnieje taka talia A że karty |A oznaczają remis, to Bitek może zapewnić sobie remis. Okazuje się więc, że Bajtek wygrywa tylko wtedy, gdy istnieje taka talia Bj , która w połączeniu z dowolnym Ai daje zwycięstwo Bajtkowi.

Sprawdzenie, w którym z powyższych przypadków się znajdujemy, jesteśmy w stanie wykonać bardzo prosto, po prostu analizując bezpośrednio (w czasie liniowym) wczytywane dane.