teoria gier - ciekawa odmiana nim

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
tkostek
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 4 lip 2012, o 21:02
Płeć: Mężczyzna
Lokalizacja: Warszawa

teoria gier - ciekawa odmiana nim

Post autor: tkostek »

Wszyscy zapewne wiedzą jak wygląda zwykła gra w nim i jaka jest strategia wygrywająca. Mamy dwóch graczy i ileś kupek kamyków (niekoniecznie równych), gracze ruszają się na przemian wybierając jedną kupkę i zabierając z niej dowolną dodatnią liczbę kamyków. Wygrywa ten kto zabierze ostatni kamyk. Co jednak jeśli każdy z graczy może wybrać dwie kupki i z każdej zabrać dowolną liczbę kamyków (tak by w sumie zabrać co najmniej 1)? Jaka będzie wówczas strategia wygrywająca i kto ją posiada? Próbowałem jakoś przekształcić strategię dla zwykłej gry, ale obserwowanie zapisów binarnych wielkości kolejnych kupek jak na razie nic mi nie daje. Doszedłem tylko do tego, że dla 3 kupek strategia wygrywająca jest dla drugiego gracza tylko wtedy gdy są one równe.
Bardzo proszę o pomoc.
piotr5
Użytkownik
Użytkownik
Posty: 70
Rejestracja: 1 lip 2012, o 20:02
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 2 razy
Pomógł: 7 razy

teoria gier - ciekawa odmiana nim

Post autor: piotr5 »

Nie rozwiązałem jeszcze Twojego problemu, ale dam Ci wskazówkę: weź funkcję określoną rekurencyjnie dla każdej możliwej pozycji \(\displaystyle{ X}\):
\(\displaystyle{ f(X) = 0}\), gdy \(\displaystyle{ X}\) jest pozycją końcową,
w przeciwnym wypadku
\(\displaystyle{ f(X) = \inf N/f(R(X))}\), gdzie \(\displaystyle{ R(X)}\) to zbiór pozycji osiągalnych w jednych ruchu z pozycji \(\displaystyle{ X}\), \(\displaystyle{ \inf A}\) to najmniejsza wartość ze zbioru \(\displaystyle{ A}\).
Przykładowo dla gry nim na dwie kupki (mało ciekawej) \(\displaystyle{ f((0,0))=0}\), \(\displaystyle{ f((1,0))=1}\), \(\displaystyle{ f((0,1))=1}\), \(\displaystyle{ f((1,1))=0}\), \(\displaystyle{ f((2,0))=2}\) itd., ogólnie wynosi ona \(\displaystyle{ f((n,m))=\left| n-m \right|}\), co można łatwo dowieść przez indukcję.
Gdy wartość funkcji z początkowej pozycji wynosi \(\displaystyle{ 0}\) strategię wygrywającą ma drugi gracz, a gdy jest większa od zera - to pierwszy. Spróbuj znaleźć taką funkcję dla Twojej gry (np patrząc na jej początkowe wartości) i będziesz miał odpowiedź na Twoje pytanie Podejrzewam, że dla tej gry funkcja jest prosta, co zresztą zaraz sprawdzę
tkostek
Użytkownik
Użytkownik
Posty: 5
Rejestracja: 4 lip 2012, o 21:02
Płeć: Mężczyzna
Lokalizacja: Warszawa

teoria gier - ciekawa odmiana nim

Post autor: tkostek »

Wszystko fajnie tylko, że twoje rozwiązanie to zwyczajny nim. Funkcja, o której mówisz to dodawanie xor i można przeczytać o tym np. na wikipedii: . Mi natomiast zależy na takim rozwiązaniu gdzie można brać kamyki z dwóch kupek. Czyli dwie kupki to pozycja przegrywająca, trzy takie same kupki to też przegrywająca. A np. (1,2,3) to już wygrywająca.
piotr5
Użytkownik
Użytkownik
Posty: 70
Rejestracja: 1 lip 2012, o 20:02
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 2 razy
Pomógł: 7 razy

teoria gier - ciekawa odmiana nim

Post autor: piotr5 »

Taką samą funkcję można znaleźć dla Twojej gry - jej rekurencyjny opis znajduje się w moim poście, tyle, że będzie ona inna niż w klasycznej grze nim.
Np \(\displaystyle{ f((n,m,0))=n+m}\)
\(\displaystyle{ f((n,n,n))=0}\)
Nad jawną funkcją dla Twojej gry muszę jeszcze pomyśleć - ale sam możesz też spróbować ją policzyć dla początkowych liczb i znaleźć prawidłowość
ODPOWIEDZ