7368841419
Jakub Cisło Teoria gier 28 czerwca 2013
nimber liczony standardowo dla gry 5 jest różny od zera i gra nie składa się z nieparzystej liczby stosów kamieni o wysokościach 1
Dowód. Otóż popatrzmy najpierw na grę, w której mamy n stosów tylko wysokości 1. Jeżeli n jest parzyste, to wygrywa gracz 1, w przeciwnym przypadku zawodnik 2 (jedynym możliwym ruchem dla każdego z graczy jest likwidacja kolejnych stosów).
Rozpatrzmy teraz grę, która składa się ze słupka z co najmniej 2 kamieniami, a pozostałe (jeżeli są) zawierają po 1 kamieniu. Strategię wygrywającą ma zawodnik numer 1, gdyż może doprowadzić przeciwnika do pozycji przegrywającej omówionej wcześniej (zależnie od ilości „jedynek” zabiera cały wysoki stos lub zostawia z niego jeden kamień). Ponadto zauważmy, że normalnie liczony nimber tej gry jest niezerowy.
Gracze mogą początkowo prowadzić rozgrywkę jak w normalnym Nimie. W pewnym momencie dojdą do wyżej opisanego stanu. Gracz, który dojdzie do tego stanu, wygra, a ponieważ stan ten ma nimber ^ 0, to dojdzie do niego zawodnik 1, jeśli na początku miał też niezerowy nimber, drugi gracz w przeciwnym wypadku. □
o o
Rysunek 6: Przykładowa rozgrywka w Antynima na 3 stosach - por. rys. 3
6 Podsumowanie
W tym artykule chciałem zapoznać z ciekawym działem matematyki jakim jest teoria gier. Gra Nim jest sztandarowym przykładem, o którym słyszał każdy, kto miał cokolwiek do czynienia z grami w matematyce. Często do tej gry wprowadza się wiele urozmaiceń, niektóre warianty pokazałem razem z dowodami strategii wygrywających. Czytelnik Zainteresowany znajdzie więcej materiałów, poniżej jednak podaję krótką ściągę.
—> Wykłady z Algorytmiki Stosowanej - Wykład 6. Teoria gier (http://was.zaa.mimuw.edu.pl/?q= node/19)
—* B. Szreder, „Elementarz chakiera”
—* W. Kuropatwa, W. Nadara, „O trzech grach na trzech stosach” (Delta 6/2013)
—* T. S. Ferguson, „Gamę Theory”
Słowa kluczowe: nim, nimber, nimliczba, nimsuma, xor, teoria gier.
Dla tych, którzy chcieliby jeszcze trochę pomyśleć, trzy zadania:
Zadanie 1 (Gra EasyChomp). Gra rozgrywa się na prostokątnej tabliczce czekolady n x m. Lewy górny kawałek jest zatruty. Gracze na przemian łamią czekoladę wzdłuż jednego nacięcia i zjadają jedną część. Przegrywa gracz, który musi zjeść zatruty kawałek. W jakim wypadku pierwszy z graczy wygra?
Zadanie 2 (Zad. 4 640M). Na tablicy narysowany jest 2012-kąt foremny. Michał i Jurek dorysowują na zmianę jedną przekątną, nie mającą wspólnych punktów wewnętrznych ani wspólnych końców z wcześniej narysowanymi przekątnymi. Przegrywa ten z graczy, który nie może wykonać ruchu. Grę rozpoczyna Michał. Który z graczy ma strategię wygrywającą?
Wyszukiwarka
Podobne podstrony:
Jakub Cisło Teoria gier 28 czerwca 2013 Ten przypadek jest trochę ciekawszy. Będziemy chcieli
Jakub Cisło Teoria gier 28 czerwca 2013 Dowód. Powyższe twierdzenie jest uogólnienieniem Tw. 1
Jakub Cisło Teoria gier 28 czerwca 2013 0 • 0 0 • 0 • 0 0 • 0 • 0 0
Jakub Cisło Teoria gier 28 czerwca 2013 Oczywistym jest, że gra kiedyś się zakończy (w każdym r
Jakub Cisło Teoria gier 28 czerwca 2013 Rysunek 7: Przykładowy ruch w grze EasyChomp Zadanie 3.
Jakub Cisło Teoria gier 28 czerwca 20131 Wstęp Teoria gier to niezwykle ciekawa dziedzina matem
Jakub Cisło Teoria gier 28 czerwca 20133 Dwa stosy Zajmijmy się teraz na chwilę podstawową wers
& Dr Łukasz Mikulski uczestniczył w dniach 24-28 czerwca 2013 roku w 34* International Conferenc
Projekt 28 czerwcu 2013 r. Rozporządzenie Ministra Transportu, Budownictwa i Gospodarki Morskiej1* z
Projekt 28 czerwca 2013 r.ROZDZIAŁ I.KWALIFIKACJE NIEOFICERSKIE 1.1. Ramowy program szkolenia i wyma
Projekt 28 czerwca 2013 r. 10. Odległość do widnokręgu, zasięgi widoczności
Projekt 28 czerwca 2013 r. Razem 4 4 II. Znać Podstawowe Systemy Nawigacyjne:
Projekt 28 czerwca 2013 r. 1.1.3.
Projekt 28 czerwca 2013 r. 1.1.4.
Projekt 28 czerwca 2013 r. 1.1.5.
Projekt 28 czerwca 2013 r. 1.1.6.
Projekt 28 czerwca 2013 r. 1.1.7.
Projekt 28 czerwca 2013 r. 1.1.8.
Projekt 28 czerwca 2013 r. 1.1.9.
więcej podobnych podstron