Nim to najpewniej chińska gra sięgająca swoją historią bardzo dawnych czasów (bardzo nieprecyzyjne, jednak prawdziwe określenie!). W jej oryginalnej wersji mamy dwóch graczy i kilka (w zależności od wyboru opcji gry) grup przedmiotów np. kamieni, ułożonych obok siebie. Gracze na przemian biorą z wybranego stosu jeden bądź dwa kamienie. Przegrywa ten, który zabierze ostatni kamień. Oczywiście jest wiele różnych odmian tej gry (możemy zmienić zasadę wygrywania, liczbę kamieni, którą możemy zabrać, liczbę stosów itp). Do analizy tej gry przyjmiemy prostsze zasady i opracujemy strategię wygrywania!
Nasza uproszczona gra ma jeden stos i pięć kamieni. Każdy z dwóch graczy może zabrać jeden bądź dwa kamienie w swojej kolejce. Przegrywa gracz, który weźmie ostatni kamień. Dla czytelności wykresu niech gracz pierwszy będzie psem, a drugi - słoniem. W pierwszym etapie pies może zabrać jeden kamień i zostaną 4 lub wziąć dwa kamienie i pozostaną 3. Sytuacja ta jest przedstawiona na grafie.
W drugim kroku (wybór słonia) można wykonać również dwa ruchy - zabrać jeden bądź dwa kamienie. Na grafie wzięto pod uwagę wybór psa, na tym etapie nie ma on wpływu na możliwość wzięcia kamienia bądź nie.
Drugi ruch psa polega na wzięciu pozostałych kamieni aż w trzech przypadkach, co zakończyłoby się jego przegraną. Dodajmy, że na tym etapie nie rozsądzamy, czy gracz wykonał sensowny ruch. Tym zajmiemy się po przeanalizowaniu wykresu. Tak więc po trzeciej kolejce nasz graf wyborów przedstawia się następująco:
Mamy po cztery możliwości wygranej dla każdego z graczy. Załóżmy, że jesteśmy psem i zastanawiamy się jakiego wyboru w pierwszym ruchu dokonać, by finalnie wygrać. Przeanalizujmy graf od dołu, to znaczy spójrzmy na trzeci ruch (drugi ruch psa). Mamy tu trzy ruchy, które doprowadzą do zwycięstwa słonia, czyli naszej przegranej. Dwa z nich są nielogiczne z punktu widzenia gracza I, gdyż wzięcie dwóch kamieni od razu powoduje przegraną. Możemy zatem uznać te ruchy za nieudane (nielogiczne). Kolorem czerwonym oznaczać będę ruchy wymuszone, tzn. takie, że inny ruch powodowałby doprowadzenie do przegranej. W drugim ruchu psa ruchem wymuszonym będzie więc wzięcie dwóch kamieni, bo w przeciwnym przypadku słoń wygra. W pozostałych przypadkach ruchami wymuszonymi będą te drogi, które doprowadzają nas do wygranej psa (jesteśmy zmuszeni nimi pójść, żeby wygrać). Biorąc pod uwagę nasze powyższe rozważania dolna część grafu wygląda następująco:
Teraz sytuacja jest ciekawa, bo gdziekolwiek nie poszedłby słoń (lewa gałąź), to zawsze doprowadzimy do wygranej psa. Zatem w pierwszym ruchu pies musi wziąć jeden kamień, żeby zmusić słonia do wykonania jednego z ruchów doprowadzających go do zwycięstwa (kolor zielony). W drugiej gałęzi ruchem wymuszonym (przez słonia) będzie wybór dwóch kamieni i wtedy słoń wygrywa. My jednak wybierając w pierwszym ruchu jeden kamień pozbawiamy go tej możliwości, a zatem zawsze jesteśmy w stanie wygrać. Oto pełny graf z wyznaczonymi na czerwono ruchami wymuszonymi i na zielono - dowolnym ruchem słonia, który zawsze doprowadzi go do porażki.
Opracowaliśmy tym samym strategię wygrywania, ale tylko jeśli możemy rozpocząć grę. Oczywiście w przeciwnym przypadku możemy liczyć wyłącznie na pomyłkę drugiego gracza. Myślę, że w najbliższym czasie na blogu pojawi się jeszcze kilka postów związanych z matematyczną teorią gier.
Brak komentarzy:
Prześlij komentarz