Wygrywająca strategia

Czas rozwiązać jakąś grę! Całkiem niezła wydaje mi się taka (pochodząca z regionalsów ACM ICPC w Ho Chi Minh City 2008): rozważamy planszę n\times n, na której niektóre kwadraciki są czarne, a niektóre… białe. Mamy dwóch graczy, który wykonują na przemian swoje ruchy, a ten, który nie jest w stanie wykonać poprawnego ruchu, przegrywa z kretesem. Poprawny ruch polega na wybraniu białego pola (x,y), gdzie x,y\in [1,n) i flipnięciu kolorów pól (x,y), (x',y), (x,y'), (x',y'), gdzie x'\in [0,x), y'\in [0,y) (gracz może wybrać dowolne x' i y', kolor pól (x',y), (x,y'), (x',y') nie ma tutaj najmniejszego znaczenia). Fajna? Fajna! Jak to zwykle w takich grach, najpierw zgadniemy jak wygląda optymalna strategia, a potem być może udowodnimy, że rzeczywiście tak jest.

W rozwiązaniu będzie nam potrzebne pojęcie nimbera i twierdzenie Sprague’a-Grundy’ego. Jeśli je znacie, to dobrze. Jeśli nie, to proponuję zajrzeć choćby tutaj, bo raczej nie jestem w stanie podać lepszego wyjaśnienia. Przypomnę jednak, że każda gra, w której mamy dwóch graczy, którzy wykonują na przemian swoje ruchy, a dozwolone ruchy zależą tylko od aktualnej pozycji, a nie tego, który gracz wykonuje aktualnie swój ruch, oraz w której przegrywa ten, kto nie jest w stanie wykonać żadnego ruchu, może być scharakteryzowana jedną liczbą, nazywaną nimberem. Ta liczba mówi w zasadzie tyle, że gra jest równoważna pewnej instancji gry w Nim. Co pewnie bardziej przydatne, liczby te mają taką własność, że nimber sumy dwóch gier jest xorem ich nimberów! Przez sumę gier rozumiemy tutaj grę składającą się z dwóch całkiem osobnych części odpowiadającą pierwotnym grom, w której ruch polega na wykonaniu ruchu w dokładnie jednej części.

Po tym krótkim wstępie możemy zająć się naszą grą. Oczywiste jest, że naszą grę można w pełni scharakteryzować jakimś nimber, ale jak go szybko wyznaczyć? Standardowym trikiem jest podzielenie planszy na mniejsze niezależne kawałki (na przykład w grach typu Nim, tymi kawałkami są stosy), ale tutaj przecież mamy jedną wielką planszę. Zdefiniujmy P(i,j) jako grę, w której zaczynamy z planszą n\times n, na której mamy dokładnie jeden biały kwadracik (i,j). Kuszące wydaje się powiedzenie, że nasza gra jest równoważna sumie gier P(i_k,j_k), gdzie (i_k,j_k) to kolejne białe pola na oryginalnej planszy. Ale chwila, przecież to wcale nie jest podział na niezależne kawałki! No nie jest, ale na szczęście nie jest to kłopot.

Lemat 1. Nasza gra jest równoważna sumie gier P(i_k,j_k), gdzie (i_k,j_k) to kolejne białe pola na oryginalnej planszy.

Dowód. Równoważność udowodnimy indukcyjnie (tutaj trzeba trochę uważać: indukcyjnie względem czego? Pewnie względem leksykograficznego porządku na opisach planszy, czyli liczbach wypisanych w odpowiedniej kolejności: z góry-do-dołu, z prawej-do-lewej). Musimy uzasadnić, że każdemu ruchowi w naszej grze odpowiada ruch w pewnej P(i_k,j_k), i odwrotnie. W tym wypadku jest nawet lepiej, możemy bowiem zdefiniować w naturalny sposób odpowiedność między tymi ruchami: wybranie białego pola (x,y) odpowiada wykonaniu (jedynego możliwego) ruchu w P(x,y). Jeśli flipnięciu ulegają pola (x,y), (x',y), (x,y'), (x',y'), w P(x,y) pojawiają się trzy białe pola (x',y), (x,y'), (x',y'), natomiast znika (x,y), czyli (z założenia indukcyjnego) sytuacja jest równoważna sumie P(x',y), P(x,y'), P(x',y'). Wykonując ruch w P(x,y) przechodzimy więc z sumy gier P(i_k,j_k) do sumy, w której zamiast pewnego P(x,y) mamy sumę P(x',y), P(x,y'), P(x',y'). Być może jest tak, że (na przykład) P(x',y) występuje teraz dwukrotnie w naszej sumie, bo x'=i_{k'}, y=j_{k'} dla pewnego k'. Łatwo się przekonać, że suma dwóch identycznych gier jest równoważna grze pustej (takiej, w której nie można absolutnie nic zrobić). Z tego wynika, że dla każdego białego pola (x,y) i x'\in[0,x), y'\in [0,y) gra, którą otrzymujemy po wykonaniu takiego ruchu jest równoważna sumie gier P(i'_k,j'_k), gdzie (i'_k,j'_k) to dokładnie białe pola po flipnięciu (x,y), (x',y), (x,y'), (x',y') na oryginalnej planszy.

Teraz z twierdzenia Sprague’a-Grundy’ego wynika, że do policzenia nimbera naszej gry (a więc i do stwierdzenia, kto wygrywa), trzeba tylko umieć policzyć nimber dowolnej P(x,y). W treści zadania n\leq 1000, więc pewnie chcielibyśmy po prostu policzyć takie wszystkie nimbery. Ale jak?

Warto zacząc od wydrukowania sobie tabelki Z P(x,y) dla, powiedzmy, x,y \leq 20. Taką tabelkę można łatwo wygenerować w czasie \mathcal{O}(n^4), gdyż dla każdego (x,y) mamy co najwyżej kwadratowo wiele ruchów.

   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0
   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16  17  18  19  20
   0   2   3   1   8  10  11   9  12  14  15  13   4   6   7   5  32  34  35  33  40
   0   3   1   2  12  15  13  14   4   7   5   6   8  11   9  10  48  51  49  50  60
   0   4   8  12   6   2  14  10  11  15   3   7  13   9   5   1  64  68  72  76  70
   0   5  10  15   2   7   8  13   3   6   9  12   1   4  11  14  80  85  90  95  82
   0   6  11  13  14   8   5   3   7   1  12  10   9  15   2   4  96 102 107 109 110
   0   7   9  14  10  13   3   4  15   8   6   1   5   2  12  11 112 119 121 126 122
   0   8  12   4  11   3   7  15  13   5   1   9   6  14  10   2 128 136 140 132 139
   0   9  14   7  15   6   1   8   5  12  11   2  10   3   4  13 144 153 158 151 159
   0  10  15   5   3   9  12   6   1  11  14   4   2   8  13   7 160 170 175 165 163
   0  11  13   6   7  12  10   1   9   2   4  15  14   5   3   8 176 187 189 182 183
   0  12   4   8  13   1   9   5   6  10   2  14  11   7  15   3 192 204 196 200 205
   0  13   6  11   9   4  15   2  14   3   8   5   7  10   1  12 208 221 214 219 217
   0  14   7   9   5  11   2  12  10   4  13   3  15   1   8   6 224 238 231 233 229
   0  15   5  10   1  14   4  11   2  13   7   8   3  12   6   9 240 255 245 250 241
   0  16  32  48  64  80  96 112 128 144 160 176 192 208 224 240  24   8  56  40  88
   0  17  34  51  68  85 102 119 136 153 170 187 204 221 238 255   8  25  42  59  76
   0  18  35  49  72  90 107 121 140 158 175 189 196 214 231 245  56  42  27   9 112
   0  19  33  50  76  95 109 126 132 151 165 182 200 219 233 250  40  59   9  26 100
   0  20  40  60  70  82 110 122 139 159 163 183 205 217 229 241  88  76 112 100  30

Co pewnie nie jest zaskakujące, tabelka jest symetryczna, to znaczy T[i][j]=T[j][i]. Ponadto T[1][i]=T[i][1]=i oraz T[0][i]=T[i][0]=0. Niestety trochę ciężko zauważyć coś więcej, spróbujmy więc wydrukować większą tabelkę, w której pokazany jest tylko ostatni bit każdego T[i][j].

red_pixel

Patrząc na ten obrazek można nabrać podejrzeń, że T[i][j] jest jakoś związane z zapisem i oraz j w systemie dwójkowym. W zwykłym Nimie jest tak, że stos o rozmiarze x jest równoważny sumie stosów, których rozmiary to kolejne potęgi 2 w zapisie x, może więc podobnie jest i tutaj? Pewnym problemem jest to, że my mamy dwa parametry x oraz y, no i raczej nie możemy zignorować żadnego z nich. Może by więc popatrzeć na sumę wszystkich P(2^i,2^j), gdzie 2^i występuje w zapisie x, a 2^j pojawia się w zapisie y.

Bingo! Wygląda na to, że (przynajmniej dla dość małych n), nimber P(x,y) jest xorem nimberów takich P(2^i,2^j). A to pozwala już na rozwiązanie całego zadania, bowiem możemy (brutalnie) wyznaczać kolejne P(2^i,2^j), każde w czasie \mathcal{O}(n^2), natomiast dla pozostałych P(x,y) skorzystać z rozkładu na P(2^i,2^j), których nimbery już znamy. Daje nam to czas \mathcal{O}(n^2\log^2 n), gdyż dla każdej pary (2^i,2^j) wykonujemy brutalne obliczenie wymagające czasu \mathcal{O}(n^2), a ponadto dla każdego (x,y) rozbijamy grę na \mathcal{O}(\log^2n) gier postaci P(2^i,2^j). Zakładając prawdziwość naszej hipotezy, to drugie można zrobić lepiej: jeśli x=x'+2^i, wystarczy rozbić P(x,y) na sumę P(x',y) i P(2^i,y) (oczywiście chcielibyśmy, żeby x'<x), podobnie gdy y=y'+2^j. Czyli nimbery wszystkich P(x,y) można wyznaczyć w czasie \mathcal{O}(n^2), o ile tylko mamy już nimbery wszystkich P(2^i,2^j). Każdy z tych drugich wydaje się wymagać czasu \mathcal{O}(n^2), ale przecież jest ich tylko \log^2n, można by je więc stablicować i zaszyć w kodzie, choć to pewnie oszustwo.

Wróćmy jednak do hipotezy.

Lemat 2. P(x,y) jest równoważna sumie wszystkich P(2^i,2^j), gdzie 2^i pojawia się w zapisie x, a 2^j pojawia się w zapisie y.

Dowód. Znów dowodzimy indukcjnie (względem leksykograficznego porządku na opisach planszy). Możliwe ruchy w P(x,y) polegają na wybraniu x'\in [0,x) i y'\in [0,y) i przejściu z P(x,y) do P(x',y)\oplus P(x,y')\oplus P(x',y'). \oplus oznacza tutaj sumę gier, lecz ze względu na Lemat 1 możemy na to patrzeć też tak, że dowolna gra jest sumą gier postaci P(2^i,2^j), czyli tak naprawdę podzbiorem S(x,y)\subseteq [0,\log n]\times [0,\log n]. Różnica symetryczna takich zbiorów odpowiada sumie orygialnych gier. Z kolei możliwe ruchy w sumie naszych wszystkich P(2^i,2^j) odpowiadają wybraniu jakiegoś konkretnej P(2^i,2^j), x''\in [0,2^i) i y''\in [0,2^j), no i przejściu z P(2^i,2^j) do P(x'',y'')\oplus P(2^i,y'')\oplus P(x'',2^j). Chcielibyśmy pokazać, że każdemu ruchowi w P(x,y) odpowiada ruch w sumie P(2^i,2^j) i na odwrót (bardziej precyzyjnie: odpowiadające sobie ruchy powinny prowadzić do równoważnych gier). Przydatne okaże się zauważenie, że S(a\oplus b,c\oplus d)=S(a,c)\oplus S(a,d)\oplus S(b,c)\oplus S(b,d). Oznaczając dx=x\oplus x' i dy=y\oplus y' i stosując założenie indukcyjne, ruchy w P(x,y) prowadzą do

S(x\oplus dx,y)\oplus S(x,y\oplus dy)\oplus S(x\oplus dx,y\oplus dy)

czyli (stosując wspomnianą równość) S(x,y)\oplus S(dx,dy). Jedynym warunkiem na dx i dy jest to, że najstarszy bit dx\in [0,x) musi być zapalony w x, oraz najstarszy bit dy\in[0,y) musi być zapalony w x. Z kolei ruch w sumie P(2^i,2^j) prowadzi do

S(x,y)\oplus S(x'',y'')\oplus S(x'',2^j)\oplus S(2^i,y'')\oplus S(2^i,2^j)

też stosując założenie indukcyjne (tym razem trzeba trochę uważać, ale darujemy sobie szczegóły), czyli (znów stosując równość) S(x,y)\oplus S(x''\oplus 2^i,y''\oplus 2^j). Jedynym warunkiem na i oraz j jest to, że 2^i występuje w zapisie x, 2^j występuje w zapisie y, oraz x''\in [0,2^i), y''\in [0,2^j). Teraz widać, ze warunki na dx,dy i i,j,x'',y'' są równoważne, czyli rzeczywiście dostajemy to co chcieliśmy.

Advertisements

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s