Teoria Gier

Opis zajęć

Prowadzący: Karol Pokorski

Dodałem zadania z warsztatów w dziale Pliki [Files]. Guziczek mało widoczny, zachęcam do przeczytania zadań i zmierzenia się z nimi.

Skupimy się na grach skończonych, pokazanych będzie wiele gier typu Nim (i nie tylko). Wyjaśnione zostanie twierdzenie Sprague-Grundy'ego oraz jakie ma znaczenie dla gier składających się z kilku podgier. Będzie dowód tego twierdzenia i wyjaśnienie dlaczego to wszystko działa. W miarę możliwości przedstawiona zostanie implementacja programu grającego w jedną z gier omówionych na wykładzie. Będziemy także wspólnie implementowali kilka programów, które będą stwierdzały, czy dany gracz posiada strategię wygrywającą lub określających wygrywający ruch z zadanej pozycji. Rozwiążemy także kilka zadań z jakiegoś znanego Online Judge z zakresu teorii gier.

Wymagania

  • znajomość pojęcia strategii wygrywającej i przegrywającej
  • znajomość operacji xor (alternatywy wykluczającej)
  • podstawy matematyki (umiejętność zrozumienia kilku nowozdefiniowanych funkcji)
  • wytrwałość i chęci zrozumienia dosyć skomplikowanych dowodów niektórych twierdzeń
  • znajomość podstawowych algorytmów przydatnych między innymi w Olimpiadach Informatycznych (nie trzeba być uczestnikiem tejże olimpiady)

Kwalifikacja

Należy rozwiązać co najmniej jedno z zadań i wysłać na adres karol.pokorski [na] gmail.com. Rozwiązaniem ma być algorytm w postaci listy kroków i krótkiego uzasadnienia poprawności (niekoniecznie jakiegoś formalnego dowodu) oraz kod źródłowy w języku C/C++/Pascal

1. Rozważamy grę, w której ze stosu k zapałek (k<=10^9), w jednym ruchu możemy zabrać jedną, dwie lub cztery zapałki. Dwóch graczy gra na przemian. Czy gracz rozpoczynający ma strategię wygrywającą? Na wejściu jedna liczba k, Na wyjściu TAK lub NIE.
2. Rozważamy grę, w której z trzech stosów zawierających kolejno a, b, c zapałek (a,b,c <= 10^9) możemy zabrać w jednym minimalnie jedną, a maksymalnie w zapałek (w <= 10^9), ale tylko z jednego stosu w danym ruchu (tj. wybieramy stosik i zabieramy zapałki). Dwóch graczy gra na przemian. Czy gracz rozpoczynający ma strategię wygrywającą? Na wejściu cztery liczby oddzielone spacjami a, b, c oraz w. Na wyjściu TAK lub NIE.

Gracz, który nie może wykonać ruchu przegrywa.

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License