Chop
Chomp to gra strategiczna dla dwóch graczy rozgrywana na prostokątnej siatce złożonej z mniejszych kwadratowych komórek, które można traktować jak bloki tabliczki czekolady. Gracze na zmianę wybierają jeden klocek i „zjadają” (zdejmują go z planszy) razem z tymi, które znajdują się pod nim i po jego prawej stronie. Lewy górny klocek jest „zatruty”, a gracz, który go zje, przegrywa.
Sformułowanie tabliczki czekolady Chompa pochodzi od Davida Gale'a , ale równoważna gra wyrażona w kategoriach wybierania dzielników ustalonej liczby całkowitej została wcześniej opublikowana przez Frederika Schuha .
Chomp to szczególny przypadek gry poset , w której częściowo uporządkowany zestaw , na którym toczy się gra, jest iloczynem całkowitych zamówień z usuniętym minimalnym elementem (trującym blokiem).
Przykładowa gra
Poniżej przedstawiono sekwencję ruchów w typowej grze rozpoczynającej się od paska 5 × 4:
Gracz A zjada dwa bloki z prawego dolnego rogu; Gracz B zjada trzy z dolnego rzędu; Gracz A wybiera blok na prawo od zatrutego bloku i zjada jedenaście bloków; Gracz B zjada trzy bloczki z pozostałej kolumny, pozostawiając tylko zatruty bloczek. Gracz A musi zjeść ostatni blok i przegrywa.
Zauważ, że skoro można udowodnić, że gracz A może wygrać, zaczynając od paska 5 × 4, przynajmniej jeden z ruchów A jest błędem.
Pozycje gry
Pozycje pośrednie w m × n Chomp są częściami całkowitymi (nierosnącymi ciągami dodatnich liczb całkowitych) λ 1 ≥ λ 2 ≥···≥ λ r , gdzie λ 1 ≤ n i r ≤ n . Ich to dwumianowy , który m i n
Zwycięstwo w grze
Chomp należy do kategorii bezstronnych gier informacyjnych dla dwóch graczy .
Dla dowolnej prostokątnej pozycji początkowej, innej niż 1×1, pierwszy gracz może wygrać. Można to pokazać za pomocą argumentu polegającego na kradzieży strategii : załóżmy, że drugi gracz ma zwycięską strategię przeciwko dowolnemu początkowemu ruchowi pierwszego gracza. Załóżmy więc, że pierwszy gracz bierze tylko prawe dolne pole. Zgodnie z naszym założeniem drugi gracz ma na to odpowiedź, która wymusi zwycięstwo. Ale jeśli taka zwycięska odpowiedź istnieje, pierwszy gracz mógł zagrać ją jako swój pierwszy ruch iw ten sposób wymusić zwycięstwo. Dlatego drugi gracz nie może mieć zwycięskiej strategii.
Komputery mogą łatwo obliczyć zwycięskie ruchy w tej grze na dwuwymiarowych planszach o rozsądnych rozmiarach. Ponieważ jednak liczba pozycji rośnie wykładniczo, jest to niewykonalne w przypadku większych tablic.
Dla kwadratowej pozycji początkowej (tj. n × n dla dowolnego n ≥ 2) zwycięską strategię można łatwo podać wprost. Pierwszy gracz powinien przedstawić drugiemu kształt litery L składający się z jednego rzędu i tylko jednej kolumny, o tej samej długości, połączonych trującym kwadratem. Następnie, cokolwiek drugi gracz zrobi na jednym ramieniu litery L , pierwszy gracz odpowiada tym samym ruchem na drugim ramieniu, zawsze ponownie prezentując drugiemu graczowi symetryczny kształt litery L. W końcu to L przekształci się w pojedynczy trujący kwadrat, a drugi gracz przegra.
Uogólnienia Chompa
j Trójwymiarowy Chomp ma początkową tabliczkę czekolady o prostopadłościanie z bloków oznaczonych jako (i, ,k). Ruch polega na wzięciu bloku razem z dowolnym blokiem, którego wszystkie indeksy są większe lub równe odpowiadającemu indeksowi wybranego bloku. W ten sam sposób Chomp można uogólnić na dowolną liczbę wymiarów.
Chomp jest czasami opisywany numerycznie. Podawana jest początkowa liczba naturalna , a gracze na przemian wybierają dodatnie dzielniki liczby początkowej, ale nie mogą wybrać 1 lub wielokrotności wcześniej wybranego dzielnika. Ta gra modeluje n- wymiarowy Chomp, gdzie początkowa liczba naturalna ma n czynników pierwszych , a wymiary planszy Chomp są podane przez wykładniki liczb pierwszych w jej rozkładzie na czynniki pierwsze . Ordinal Chomp jest rozgrywany na nieskończonej planszy z niektórymi wymiarami liczb porządkowych : na przykład słupek 2 × (ω + 4). Ruch polega na wybraniu dowolnego bloku i usunięciu wszystkich bloków, których oba indeksy są większe lub równe odpowiednim indeksom wybranego bloku. Przypadek ω × ω × ω Chomp jest godnym uwagi problemem otwartym; za znalezienie zwycięskiego pierwszego ruchu zaoferowano nagrodę w wysokości 100 $.
Mówiąc bardziej ogólnie, Chomp można zagrać na dowolnym częściowo uporządkowanym zestawie z najmniejszym elementem . Ruch polega na usunięciu dowolnego elementu wraz ze wszystkimi większymi elementami. Gracz przegrywa, biorąc najmniejszy element.
We wszystkie odmiany Chomp można również grać bez uciekania się do trucizny, stosując konwencję misère play: gracz, który zjada ostatni blok czekolady, nie zostaje zatruty, ale po prostu przegrywa z racji bycia ostatnim graczem. Jest to identyczne ze zwykłą zasadą podczas gry w Chompa w pojedynkę, ale różni się w grach z rozłączną sumą gier Chomp, w których przegrywa tylko ostatni ostatni blok czekolady.
Zobacz też
- ^ Zeilberger, Doron (2001). „Trójrzędowy CHOMP”. Postępy w matematyce stosowanej . 26 (2): 168–179. doi : 10.1006/aama.2000.0714 .
- Bibliografia _ 482 w: Gry bez szans (red. RJ Nowakowski), Cambridge University Press, 1998.
- Zeilberger, Doron (2004). „Chomp, nawroty i chaos (?)” . J. Diff. równanie Zastosuj . 10 (13–15): 1281–1293. doi : 10.1080/10236190410001652720 .
- Brouwer, AE; Horvath, Gabor; Molna-Saska, Ildiko; Szabo, Csaba (2005). „Na trójrzędowym Chompie” . liczby całkowite . 5 : #G07.
- Friedman, Eirc J. (2007). „Dynamika nieliniowa w grach kombinatorycznych: renormalizacja Chompa” . Chaos . 17 (2): 023117. Bibcode : 2007Chaos..17b3117F . doi : 10.1063/1.2725717 . PMID 17614671 .
- Khandhawit, Tirasan; Tak, Lynnelle (2011). „Chomp na wykresach i podzbiorach”. arXiv : 1101,2718 [ matematyka.CO ].
- Sołtys, Michał; Wilson, Craig (2011). „O złożoności obliczania zwycięskich strategii dla skończonych gier Poset”. Obliczenia teoretyczne. Syst . 48 (3): 680–692. doi : 10.1007/s00224-010-9254-y . S2CID 2720334 .
- Brouwer, AE (2017). „Gra w kotleta” .
- Cho, śpiewane (2018). „Zwycięskie strategie gry Chomp: praktyczne podejście”. J. Matematyka historii . 31 (3): 151–166. doi : 10.14477/jhm.2018.31.3.151 .