Gra w odejmowanie – rozwiązanie.

Zgodnie z obietnicą przyszedł czas na odpowiedź na pytanie, jak żyć… znaczy grać. Jeśli udało Wam się wygrać w grze w odejmowanie piłeczek, to gratuluję, jeśli wygrywacie za każdym razem, to winszuję jeszcze bardziej i zapytuję dlaczego nie spróbowaliście nacisnąć zielonego przycisku? Tak, w wersji, w której komputer zaczyna nie da się wygrać. Komputer się nie myli i jego pierwszy ruch determinuje wygraną. Zatem, żeby wygrać trzeba zaczynać, zrobić dobry pierwszy ruch i konsekwentnie dobre wszystkie następne ruchy.
Dobre, czyli jakie, zapytacie?

Odpowiedź na to pytanie porusza ciekawe zagadnienie, które jakoś podświadomie od zawsze mnie interesowało. Chodzi o proces dochodzenia do rozwiązania jakiegoś zadania, zagadki czy problemu oraz stopień w jakim odkryte rozwiązanie naprawdę rozumiemy. Na pewno tylko dotknę tego tematu teraz, ale myślę, że będę do niego wracał już w następnych postach.

Miałem to szczęście, że pokazałem Grę w Odejmowanie kilku osobom i mogłem przyjrzeć się temu, jak podchodzą do rozwiązania problemu w niej zawartego. Parę osób było mi wcześniej nieznanych i tym bardziej nie mogłem nawet zgadywać, jak się zabiorą za zadanie. Pierwszym sposobem podejścia do rozwiązania była oczywiście metoda prób i błędów. Po obserwacji jakie ruchy prowadzą do jakich konsekwencji oraz przetestowaniu skrajnie prostych przypadków, osoba stosująca tę metodę dochodziła do wniosku, że np. trzeba wybierać za każdym razem 2 piłeczki. Co oczywiście czasem prowadziło do wygranej, a czasem nie. Jednak kilka prób wystarczyło, żeby usatysfakcjonować gracza wygraną. Oczywiście przy tej metodzie utrudnione zadanie mieli gracze ze skłonnością do wybierania opcji, że komputer zaczyna.

Zdarzył mi się jednak gracz, który zauważył, że skoro komputer zawsze wygrywa, jeśli zaczyna, to w tej opcji gry najłatwiej będzie mu sprawdzić, co robi komputer żeby wygrać, a później spróbuje to zastosować w swojej grze, czyli kiedy sam robi pierwszy ruch. No i rzeczywiście, po kilku próbach, okazało się, że prawdopodobnie komputer zawsze zaczyna od wzięcia dwóch piłeczek, a następnie jeśli my weźmiemy jedną, to on bierze dwie, jeśli zaś my bierzemy dwie, to on bierze jedną. Zawsze na odwrót, albo inaczej mówiąc, żeby, nie licząc pierwszego ruchu, ruch gracza i komputera w sumie zabierał trzy piłeczki.
I to jest właściwie prawidłowe rozwiązanie!

Ale czemu tak jest i czy naprawdę to rozumiemy? Możemy to sprawdzić, na przykład poprzez zwiększenie liczby piłeczek o 2, wtedy niby gra jest ta sama, ale biorąc na początku dwie piłeczki, zmieniamy grę w taką, jakby przy dwunastu piłeczkach zaczynał komputer. Dodatkowo możemy jeszcze bardziej utrudnić sobie i zwiększyć liczbę piłeczek, które można wziąć w jednym ruchu. Na przykład, co by było gdyby można było wziąć jedną, dwie lub trzy piłeczki.
Zachęcam do poeksperymentowania poniżej, przygotowałem specjalną wersję gry gdzie można ustawić dowolną liczbę piłeczek na początku i dowolną liczbę piłeczek do wzięcia w jednym ruchu. W ten sposób ustawiając te parametry na początku, tworzycie własną wersję gry z całego zbioru gier o zabieraniu piłeczek.

OK. Poeksperymentowaliśmy – czy nam to pomogło w zrozumieniu czy raczej zagmatwało sytuację bardziej? Zauważmy, jak ważne jest to kto zaczyna. Pierwszy ruch determinuje, kto weźmie dwunastą piłeczkę po jeszcze conajmniej pięciu ruchach. Jak z kolei wygląda końcówka? Żeby wygrać trzeba po prostu zostawić przeciwnikowi ostatnią piłeczkę. Jeśli zostały dwie, to bierzemy jedną. Jeśli zostały trzy, to bierzemy dwie. No a jeśli zostały cztery, to nie jesteśmy w stanie zostawić jednej, to co robimy? Niestety w tej sytuacji nie mamy już wyjścia i co nie zrobimy, to przeciwnik ma jeszcze szansę nie wziąć ostatniej piłeczki, bo zostawiamy mu więcej niż jedną, ale mniej niż cztery, więc ma w jednym ruchu możliwość pozostawienia nas z ostatnią piłeczką.

W tym momencie powinno nas olśnić, że jeśli zostawiamy przeciwnikowi ostatnią piłeczkę to wygrywamy, ale też kiedy zostawiamy mu do wzięcia czwartą piłeczkę, to też w jakimś sensie wygrywamy, wygrywamy pewien etap, który umożliwia nam wygranie kolejnego.

Zatem możemy spojrzeć na problem inaczej. Skoro trzeba wygrać czwartą od końca piłkę (wygrać czyli zmusić przeciwnika do jej wzięcia), żeby wygrać ostatnią, to możemy w myślach usunąć 3 ostatnie piłki i do tego etapu grać, jakby czwarta od końca piłka była ostatnią.
No i stąd prosty pomysł, żeby tak zrobić (w myślach) z kolejnymi grupami po trzy piłeczki, aż zostaną pierwsze trzy piłeczki (lub mniej). A tu problem jest prosty, trzeba wziąć tyle piłeczek, żeby została tylko jedna, wtedy wiemy na pewno, że przeciwnik ją weźmie, a z drugiej strony z następnej grupy zostawi nam więcej niż jedną.

I tak gramy, aż do samego końca. Na poniższym rysunku zobaczcie proszę, jak podzieliłem piłeczki na grupy. To samo trzeba zrobić myślowo podczas gry i konsekwentnie zostawiać ostatnią piłeczkę z każdej grupy przeciwnikowi.

Rys. 1 – Podział na grupy.

Spróbujcie teraz jeszcze raz zagrać w powyższą wersję gry i sprawdzić czy potraficie uogólnić ten sposób grania na dowolne liczby piłeczek.
Dla ułatwienie liczenia i dzielenia na grupy, dodałem informacje podczas gry ile piłeczek zostało i ile aktualnie jest wybranych przez Ciebie lub komputer.

Myślę, że na tym etapie jesteśmy już trochę zmęczeni tematem piłeczek i tej gry, więc pozwolę sobie go zakończyć na dłuższy czas mimo, że miałem jeszcze w planie opisać zagadnienie drzewa decyzji oraz eleganckiego matematycznie algorytmu gry. Zrobię to, ale może przy innej okazji, tymczasem trzeba iść do przodu!

Jak zwykle proszę o komentarze i ciekawą dyskusję 🙂