Witam, znów mam problem z teorią gier, otóż mam grę NIM1(m,k) - na stosie znajduje się n zapałek. Dwaj gracze na przemian zabierają ze stosu 1 lub 2 lub...k zapałek. Gracz który weźmie ostatnią zapałkę przegrywa.
Pytanie - Ile strategi ma każdy z graczy?. Mam dwie wskazówki : Rozpatrzeć NIM1(m,3) oraz druga - Podać wzór w postaci indukcyjnej.
Nie wiem czy to coś pomoże ale to zadanie pojawiło się przy drzewach gry - mniemam że trzeba będzie jakoś to wykorzystać?
Teoria gier - Ile strategi ma każdy z graczy.
-
Jacek_Karwatka
- Użytkownik
- Posty: 351
- Rejestracja: 2 maja 2012, o 16:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 94 razy
Teoria gier - Ile strategi ma każdy z graczy.
ogólnie każda strategia (deterministyczna) może być opisana regułą (tabelą)
jeśli na stosie jest x zapałek - mam zabrać y
dla \(\displaystyle{ x>k}\) mam zawsze k możliwości wyboru ile wezmę zapałek. W sumie \(\displaystyle{ k ^{n-k}}\) rożnych strategii.
dla \(\displaystyle{ x \le k}\) mam tylko x możliwości wyboru ile wezmę zapałek. W sumie \(\displaystyle{ k!}\) rożnych strategii.
Razem mamy \(\displaystyle{ k ^{n-k}k!}\) rożnych strategii, każda opisana konkretną tabelą.
np w grze NIM(5,3) mam takie możliwości wyboru
x y
5 1,2,3 - 3 możliwości wyboru strategi na tym etapie
4 1,2,3 - 3 możliwości wyboru strategi na tym etapie
3 1,2,3 - 3 możliwości wyboru strategi na tym etapie
2 1,2 - 2 możliwości wyboru strategi na tym etapie
1 1 - 1 możliwości wyboru strategi na tym etapie
w sumie jest \(\displaystyle{ 3 ^{2}*3! = 54}\) różnych strategii
tabla:
x y
5 1
4 1
3 1
2 1
1 1
opisuje strategię (niezbyt mądrą) zawsze bierz jedną zapałkę
Strategia gwarantująca wygraną jest jedna. Ten co pierwszy zostawi po sobie x(k+1)+1 zapałek wygrywa
Tu opisałem strategię gry NIM
297409.htm
jeśli na stosie jest x zapałek - mam zabrać y
dla \(\displaystyle{ x>k}\) mam zawsze k możliwości wyboru ile wezmę zapałek. W sumie \(\displaystyle{ k ^{n-k}}\) rożnych strategii.
dla \(\displaystyle{ x \le k}\) mam tylko x możliwości wyboru ile wezmę zapałek. W sumie \(\displaystyle{ k!}\) rożnych strategii.
Razem mamy \(\displaystyle{ k ^{n-k}k!}\) rożnych strategii, każda opisana konkretną tabelą.
np w grze NIM(5,3) mam takie możliwości wyboru
x y
5 1,2,3 - 3 możliwości wyboru strategi na tym etapie
4 1,2,3 - 3 możliwości wyboru strategi na tym etapie
3 1,2,3 - 3 możliwości wyboru strategi na tym etapie
2 1,2 - 2 możliwości wyboru strategi na tym etapie
1 1 - 1 możliwości wyboru strategi na tym etapie
w sumie jest \(\displaystyle{ 3 ^{2}*3! = 54}\) różnych strategii
tabla:
x y
5 1
4 1
3 1
2 1
1 1
opisuje strategię (niezbyt mądrą) zawsze bierz jedną zapałkę
Strategia gwarantująca wygraną jest jedna. Ten co pierwszy zostawi po sobie x(k+1)+1 zapałek wygrywa
Tu opisałem strategię gry NIM
297409.htm
Teoria gier - Ile strategi ma każdy z graczy.
Czyli obaj gracze mają po \(\displaystyle{ k^{n-k} k!}\) ? Czy jeden?
-
Jacek_Karwatka
- Użytkownik
- Posty: 351
- Rejestracja: 2 maja 2012, o 16:16
- Płeć: Mężczyzna
- Lokalizacja: Polska
- Podziękował: 1 raz
- Pomógł: 94 razy
Teoria gier - Ile strategi ma każdy z graczy.
W zasadzie tak, chociaż ten co wybiera jako drugi nigdy nie będzie musiał patrzeć do pierwszego wiersza swojej tabeli, opisującej strategię, który mówi co zrobić jeśli przeciwnik zostawi po sobie dokładanie n zapałek. Pierwszy zawodnik musi wziąć co najmniej jedną zapałkę. Dla drugiego gra zaczyna się od co najwyżej n-1 zapałek. Drugi ma więc \(\displaystyle{ k ^{(n-1)-k}k!}\) strategii. Jednak pełna strategia to opis gry w każdej sytuacji. Jeśli zawodnik może zastać na stole od 1 do n zapałek ma \(\displaystyle{ k ^{n-k}k!}\) strategii do wyboru.