7368841415
Jakub Cisło Teoria gier 28 czerwca 2013
3 Dwa stosy
Zajmijmy się teraz na chwilę podstawową wersją Nima jednak na 2 stosach.
Zasady gry 4 (Nim na 2 stosach). Dane są 2 stosy kamieni. Dwaj gracze wykonują na przemian ruchy polegające na wybraniu jednego ze stosów i zabraniu z niego niezerowej liczby kamieni. Przegrywa ten, który nie może wykonać ruchu.
Po chwili namysłu możemy zauważyć, że jeśli stosy są równej liczności, to pierwszy zawodnik nie może wygrać. Dlaczego? Wystarczy, aby drugi kopiował jego ruchy, tzn. zabierał taką samą ilość kamieni, ale z drugiego stosu. Co jednak, gdy stosy nie są równe? Tym razem 1. gracz zawsze wygra - wyrównuje stosy i później naśladuje ruchy drugiego. Ta bardzo prosta strategia jest zaskakująco przydatna w najróżniejszych zadaniach z teorii gier! Czas więc na coś trudniejszego.
O
o
o
o
o
o
Rysunek 2: Strategia w Nimie na 2 stosach
4 Wiele stosów
Zasady gry 5 (Nim na n stosach). Danych jest n stosów kamieni. Dwaj gracze wykonują na przemian ruchy polegające na wybraniu jednego ze stosów i zabraniu z niego niezerowej liczby kamieni. Przegrywa ten, który nie może wykonać ruchu.
Zauważmy, że tak naprawdę mamy n podgier, na których toczy się rozgrywka, a w turze gracz wybiera jedną z gier i wykonuje w niej ruch. Całą grę będziemy nazywać sumą gier.
Grą 5 zajmowali się Sprague i Grundy, którzy niezależnie znaleźli sposób radzenie sobie z takim problemem. Najpierw wprowadźmy pewne działanie.
XOR (oznaczany ©) jest działaniem dwuargumentowym na liczbach naturalnych. Aby sksorować dwie liczby musimy:
a) zapisać obie liczby w systemie dwójkowym
b) wykonać pisemne dodawanie (w systemie binarnym) na tych liczbach, ale bez przenoszeń
Innymi słowy wynikiem w słupku jest 1, jeżeli w tej kolumnie jest nieparzyście wiele jedynek, 0 gdy jest ich parzysta liczba (przydaje się to przy liczeniu xora większego zbioru).
Oto przykład operacji 12 © 10 = 6:
110 0 © 1 0 1 0 0 110
Xorowanie jest przemienne, łączne, posiada element neutralny 0 (x® 0 = x), a elementem odwrotnym do x jest x (x © x = 0). Skoro znamy już operację © to czas poznać twierdzenie:
Twierdzenie 2 (Sprague-Grundy’ego). Nimber całej gry G (w grach typu Nim), składającej się z n podgier o nimberach x\,X2,—,xn, niech wynosi x\ © X2 © ••• © xn. Wtedy nim(G) = 0 jest równoważne, że gracz pierwszy nie ma strategii wygrywającej.
3.
Wyszukiwarka
Podobne podstrony:
Jakub Cisło Teoria gier 28 czerwca 20131 Wstęp Teoria gier to niezwykle ciekawa dziedzina matem
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 nimber liczony standardowo dla gry 5 jest różny od zera
Jakub Cisło Teoria gier 28 czerwca 2013 Rysunek 7: Przykładowy ruch w grze EasyChomp Zadanie 3.
egzamin-teoriaobwodow i KRAKÓW, 28 CZERWCA 2010 R. CZĘŚĆ DRUGA Dla obwodu pokazanego powyżej: 1.
Projekt 28 czerwca 2013 r. 4.2. Ramowy program szkolenia i wymagania egzaminacyjne na dyplom szypra
Slalom giganta w Biatce Tatrzańskiej - XXV OMNG W dniu 28 marca 2014 roku w NCK odbyło się szkolenie
MUZYCZNY POCZĄTEK WAKACJI W piątek 22 czerwca, w barze "Pod Kasztanem" odbył się koncert,
J. Marcinkowski5. Teoria gier Problem opanowania rynku na jednorodny produkt Macierz wypłat opisuje
Slajd26 4 ATMOSFERA KOPALNIANA SKŁAD GAZÓW Rozporządzenie Ministra Gospodarki z dnia 28 czerwca 2002
Oligopol i teoria gier 1 Przywództwo cenowe (rys. 7.1.) Rysunek 7.1. Optimum przedsiębiorstwa
więcej podobnych podstron