3784497993

Strategie wygrywające w grach

Urszula Pastwa i Joachim Jelisiejew

Strategia wygrywająca to sposób gry pozwalający, niezależnie od ruchów przeciwnika, wygrać rozgrywkę. Dowodząc, że dany gracz ma strategię wygrywającą, nigdy nie powinniśmy zakładać, że jego przeciwnik gra rozsądnie czy zgodnie z przewidywaniami. Strategia musi doprowadzić do zwycięstwa niezależnie od tego, jak gra przeciwnik.

Pozycją nazywamy stan gry w danym momencie rozgrywki. Kluczowe dla gier dwuosobowych są pojęcia pozycji wygrywającej i pozycji przegrywającej. Pozycja jest wygrywająca, jeżeli gracz rozpoczynający z niej może wygrać. Jest ona przegrywająca, jeżeli niezależnie od tego, jak rozpoczynający zagra, przegra, o ile jego przeciwnik gra optymalnie.

Z tych definicji wynika, że wykonanie ruchu z pozycji przegrywającej zawsze prowadzi do pozycji wygrywającej. Natomiast wykonanie pewnego „dobrego” ruchu z pozycji wygrywającej prowadzi do pozycji przegrywającej. Istotny jest tutaj fakt, że gracze wykonują ruchy na przemian, więc jeżeli gracz wykonuje ruch z pozycji wygrywającej, to zostawia swojemu przeciwnikowi pozycję przegrywającą.

Zauważmy, że o ile gra zawsze się kończy, to każda pozycja jest przegrywająca lub wygrywająca: zaczynając od pozycji końcowych, dla każdej pozycji kolejno sprawdzamy, czy da się z niej przejść do pozycji przegrywającej. Jeżeli tak, jest ona wygrywająca. Jeżeli nie, jest ona przegrywająca. Czytelnikowi pozostawiamy zastanowienie się, dlaczego w ten sposób sprawdzimy wszystkie pozycje. W szczególności pozycja startowa jest wygrywająca (i wtedy rozpoczynający gracz ma strategię wygrywającą) lub przegrywająca (wtedy drugi gracz ma strategię wygrywającą).

We wszystkich poniżej opisanych grach biorą udział dwaj gracze, Bolek i Lolek, wykonując ruchy na zmianę. Grę rozpoczyna Bolek. O ile nie jest napisane inaczej, nie ma remisów i przegrywa osoba, która nie może wykonać poprawnego ruchu. W każdym zadaniu należy rozstrzygnąć, czy gra zawsze się kończy. Dodatkowo, jeśli gra zawsze się kończy, trzeba znaleźć gracza, który posiada strategię wygrywającą (z dyskusji powyżej wynika, że taki gracz zawsze istnieje).

Zadanie 1. Mamy 100 zapałek. Ruch polega na zabraniu pewnej dodatniej liczby zapałek, jednak nie więcej niż 6.

Rozwiązanie

W każdym ruchu liczba zapałek zmniejsza się, więc wystarczy sprawdzić „kolejno”, które liczby zapałek odpowiadają pozycjom przegrywającym, a które wygrywającym.