Chomp
Chomp – gra dla dwóch graczy, którą rozgrywa się na prostokątnej planszy („tabliczce czekolady”). Plansza dzieli się na mniejsze, kwadratowe kostki. Gracz podczas ruchu musi wybrać jedną z kostek i „zjeść ją”, tj. usunąć ją z planszy razem z kostkami znajdującymi się poniżej i na prawo od niej. Kostka w lewym górnym rogu jest zatruta – ten gracz, który ją weźmie, przegrywa. Gra daje się uogólniać na plansze wielowymiarowe, a nawet nieskończone.
Przykładowa gra[edytuj | edytuj kod]
Poniżej przedstawiona jest przykładowa sekwencja ruchów w grze z użyciem planszy o wymiarach 3 × 5 kostek:
| Początek | Gracz A | Gracz B | Gracz A | Gracz B | ||||
|---|---|---|---|---|---|---|---|---|
  |
|
|
 |
| ||||
|
|
|
|
| ||||
|
|
|
|
|
Gracz A musi wziąć ostatnią kostkę, więc przegrywa.
Strategia wygrywająca[edytuj | edytuj kod]
Metodą „kradzieży strategii” można udowodnić, że pierwszy gracz zawsze ma strategię wygrywającą (czyli pozwalającą rozstrzygnąć rozgrywkę na jego korzyść niezależnie od postępowania drugiego gracza). Należy w tym celu przypuścić, że drugi gracz dysponowałby strategią wygrywającą. Niech pierwszy gracz rozpocznie grę, biorąc jedynie dolną prawą kostkę. Wówczas – zgodnie z założeniem – istnieje kostka x, którą może wziąć gracz drugi, aby ponownie postawić gracza pierwszego w pozycji przegrywającej. Można jednak zauważyć, że gracz pierwszy mógłby już w swoim pierwszym ruchu wziąć kostkę x, doprowadzając do dokładnie tej samej pozycji – stawiając gracza drugiego w pozycji przegrywającej. To uzupełnia dowód przez sprowadzenie do sprzeczności pokazujący, że drugi gracz nie może dysponować strategią wygrywającą. Jako że gra nie zawiera elementów losowych i zawsze zostaje rozstrzygnięta po skończonej liczbie ruchów (liczba kostek jest skończona, a w każdym ruchu trzeba „zjeść” przynajmniej jedną), któryś z graczy musi dysponować strategią wygrywającą, a zatem jest to gracz pierwszy.
To rozumowanie jest jednak niekonstruktywne: nie mówi nic na temat wyglądu owej strategii wygrywającej, w szczególności nawet na temat położenia kostki x, którą powinien wybrać gracz pierwszy w swoim pierwszym ruchu. Istotnie, wiadomo tylko, że strategia wygrywająca dla gracza pierwszego zawsze istnieje, a dla niewielkich plansz można ją określić przy użyciu obliczeń komputerowych; znalezienie opisującego ją jawnego wzoru jest jednak problemem otwartym.
Według stanu na rok 2018 strategia wygrywająca jest znana tylko dla przypadku planszy 2xn (należy zabrać prawą dolną kostkę, a następnie w każdym kolejnym ruchu utrzymywać sytuację, w której rząd drugi jest o jedną kostkę krótszy od pierwszego, co zawsze jest możliwe) oraz planszy kwadratowej nxn (należy zabrać kostkę drugą od lewej i drugą od góry, a następnie każdy ruch przeciwnika odbijać względem przekątnej i powtarzać). Badania nad przypadkiem 3xn są bardzo zaawansowane[1].