Dwie gry w łączenie płytek, jedno pytanie: czy w którąkolwiek z nich da się grać bezbłędnie? Odpowiedź prowadzi przez róg planszy, przeciwnika, który nigdy się nie pojawia, i liczbę wysoką na siedemnaście wykładników.
Napisane i zredagowane po angielsku. Ta polska wersja powstała w wyniku tłumaczenia maszynowego; tam, gdzie liczy się precyzja, rozstrzygający jest angielski oryginał. Przeczytaj oryginał po angielsku →
Zacznijmy od gry, którą wszyscy znają. 2048, cztery kierunki, siatka 4×4, płytki, które podwajają się przy zetknięciu, jest ściśle rzecz biorąc nierozwiązana. Nikt nie napisał algorytmu, który grałby w nią idealnie. Mamy za to bardzo mocne przybliżenia. Przeszukiwanie expectimax, które zagląda mniej więcej osiem ruchów naprzód i ocenia każdą planszę garścią ręcznie dostrojonych heurystyk (wolne pola, duże płytki przyparte do krawędzi, gładkość), osiąga płytkę 32768 w ponad jednej trzeciej partii, 1 a najsilniejszy publicznie dostępny silnik sięga płytki 65536 w kilku procentach przypadków. 2 W uogólnieniu na planszę m×n samo rozstrzygnięcie, czy docelowa płytka jest osiągalna, jest NP-trudne. 3 Silna gra to nie to samo co rozwiązanie.
Jak wysoko może wspiąć się pojedyncza płytka? Na szesnastu polach odpowiedzią jest mały, elegancki kawałek kombinatoryki. Ułóż planszę jak schodzące schody: 65536, 32768, 16384 i tak dalej, aż do samotnej 2. Każda płytka jest dokładnie o jedną potęgę dwójki niższa od sąsiadki, więc szesnaście różnych potęg od 21 do 216 idealnie wypełnia planszę, a 65536 = 216 stoi na szczycie: jeden wykładnik na pole. Taki jest pułap, jeśli gra daje ci wyłącznie dwójki. Ale 2048 w co dziesiątym przypadku tworzy 4, a jedna dobrze wyczekana czwórka przemyca siedemnasty wykładnik, podnosząc prawdziwe maksimum do 131072 = 217, czyli potęgi warte siedemnastu płytek upakowane w szesnastu polach. 4 Żaden człowiek jej nie zbudował; kilka SI otarło się o nią.
Dlaczego te plansze nagradzają wciskanie największej płytki w róg? Płytkę w środku można pchnąć na cztery sposoby i ciągle zostaje ona rozdzielana z płytkami, z którymi chce się połączyć. Płytka w rogu dotyka dwóch ścian; pchnięcia w stronę ścian, do których już przylega, nie mogą jej ruszyć, a dopóki unikasz pchania od nich, stoi w miejscu, podczas gdy wszystko organizuje się wokół niej. Połącz resztę w monotonicznego węża, z najwyższą wartością w rogu, zawijającego tam i z powrotem w porządku malejącym, a jedno przeciągnięcie może wywołać kaskadę połączeń. 1 To heurystyka, która dominuje w niezobowiązującej grze ludzi, i niemal dokładnie to odkrywają na nowo SI, gdy pozwoli im się samodzielnie dostroić wagi.
Gra w łączenie z losowymi nowymi płytkami nie ma przeciwnika, jest tylko pogoda. „Rozwiązać” ją to pokonać kości średnio, a nie pokonać umysł.
Teraz przechyl planszę w trzy wymiary. 3927 to sześcienny kuzyn 2048: krata 3×3×3 złożona z 27 pól, sześć kierunków przesunięcia zamiast czterech i płytki, które łączą się trójkami, 3 w 9, 9 w 27, 27 w 81, w systemie o podstawie trzy tam, gdzie 2048 ma podstawę dwa. 5 Czy układanie w rogu przetrwa dodatkowy wymiar? Sześcian ma osiem narożników, a pole narożne dotyka teraz trzech ścian zamiast dwóch; powinno być więc jeszcze stabilniejsze, przyparte jednocześnie przez trzy ściany, choć sześć kierunków daje planszy więcej sposobów, by rozluźnić twoją konstrukcję. Wąż staje się złożoną ścieżką przeplatającą się przez wszystkie trzy warstwy. O ile mi wiadomo, nikt nie sprawdził, czy ta analogia rzeczywiście się sprawdza: to rozumowanie, a nie pomiar.
A pułap? Zasada „jeden wykładnik na pole” sugerowałaby 327 ≈ 7,6 biliona jako luźne ograniczenie górne. Analogia jednak mocno się strzępi. Dodatkowy wykładnik w 2048 pochodził ze szczęśliwej czwórki; 3927 zawsze tworzy tylko najmniejszą płytkę, gołą 3, więc premii nie ma. Co gorsza, potrójne połączenie wymaga trzech płytek ustawionych w linii, a każdy rząd, kolumna i słup w sześcianie 3×3×3 ma dokładnie trzy pola, więc każde połączenie pochłania całą linię. To ograniczenie gryzie znacznie mocniej niż cokolwiek w płaskiej grze i niemal na pewno spycha prawdziwe maksimum dużo poniżej 327. Jaka jest ta prawdziwa liczba, nie znalazłem nigdzie obliczonej. (Wyraźnie oznaczone rozumowanie; opisana wyżej mechanika pochodzi z dokumentacji projektowej gry).
Oto subtelność, która sprawia, że „idealna gra” jest pojęciem śliskim. Gra w łączenie z losowymi nowymi płytkami to jednoosobowa gra stochastyczna, pasjans przeciwko kostce, a nie pojedynek. Nic nie wybiera najgorszej nowej płytki, by cię zniszczyć; jest tylko obojętny generator liczb losowych. Właściwym pojęciem optymalnej gry jest więc expectimax: maksymalizacja oczekiwanego wyniku względem rozkładu nowych płytek. To zdecydowanie nie jest minimax: minimax zakłada przeciwnika, a jeśli rzeczywiście pozwolisz mu umieszczać każdą płytkę („złośliwe 2048”), gra staje się czymś okrutniejszym, co można być zmuszonym przegrać. Ponieważ kości mogą w zasadzie dać dowolną sekwencję, strategia gwarantująca daną płytkę może po prostu nie istnieć. Uczciwa odpowiedź na pytanie „czy istnieje idealna strategia?” brzmi więc tak: dla gry stochastycznej najlepsze, co w ogóle da się zdefiniować, to strategia najlepsza średnio, a jej dokładne obliczenie jest poza zasięgiem dla 2048 6 i pozostaje otwartą kwestią dla 3927.