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
edytujPoniż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
edytujMetodą „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].