Na laboratoriach zadawane są prace domowe za punkty. Można oddawać wybrane prace domowe, aby uzyskać odpowiednią liczbę punktów do oceny.
Możliwe są też prace badawcze, które będą proponowane na laboratoriach lub można samemu zgłosić się z własnymi pomysłami. Projekty badawcze oznaczają skupienie się nad danym algorytmem bądź grą i niezależnie od wyniku, przy pewnym nakładzie pracy, może prowadzić to do zaliczenia na wysoką ocenę (najprawdopodobniej 5).
Podstawowymi sposobami zaliczania jest jednak napisanie programu grającego w jedną z gier. Na początek rozważamy grę z pełną informacją, ale wieloosobową z losowością: chińczyk. Możliwe, że jeszcze będzie kółko i krzyżyk na 3 w ciemno. Na koniec będzie uproszczony poker. Szczegóły poniżej w Pracach domowych.
Ostatnim sposobem zaliczania jest przystąpienie do ustnego egzaminu wiedzy. Należy wtedy zgłaszać się mejlem. Na egzaminie teoretycznym należy mi udowodnić, że nauczyliście się takich technik, za pomocą których potrafilibyście rozwalić grę, bądź napisać program grający optymalnie lub bardzo silnie, gdybyście mieli dosyć czasu :-).
Prace domowe to programy. Aby zaliczyć dany program trzeba ponadto przygotować raport. Raport powinien zawierać następujące informacje:
Jest strona poświęcona chińczykowi. Na niej są zasady, dostępny sędzia, opisany protokół, przykładowy bot i informacje o turnieju, który zrobimy sobie w ostatni weekend listopada.
Wyniki turnieju dostępne są pod games.mimuw.edu.pl/chinczyk/wyniki/glowny/. Uwaga strona waży 74 MB i niektóre przeglądarki mogą zeżreć całą pamięć.
Poniżej wskazówki jak będą wyceniane różne elementy w bocie do chińczyka.
| Zwykłe Monte-Carlo z formułą UCT | 3 pkt. |
| Monte-Carlo Tree-Search | 15 pkt. |
| Implementacja algorytmu expecti-maxn | 8 pkt. |
| Wzmacnianie symulacji (w MC lub w MCTS) przez zagnieżdżanie MC | 3 pkt. |
| Wzmacnianie symulacji heurystykami | 1-6 pkt. |
| Wzmacnianie symulacji przez płytkie przeszukiwanie expecti-maxn | 8 pkt. |
| Wysokie miejsce w turnieju | od +1 do +30 pkt. |
| Wyznaczenie równowagi Nasha w bardzo prostych grach przez sprowadzenie do postaci strategicznej i użycia LP | 3 pkt. |
| Wyznaczenie równowagi Nasha w trochę większych grach przez użycie LP bezpośrednio dla postaci ekstensywnej | 8 pkt. |
| Implementacja Information Set MCTS | 10 pkt. |
| Wyznaczanie epsilon równowag Nasha dla bardzo dużych gier z użyciem CFR | >=15 pkt. |
Gra może być dowolna byle była ciekawa. Dla przykładu może to być bardzo uproszczony poker z wykładu, kółko i krzyżyk w ciemno lub poniżej propozycja pewnej gry w kości.
W grze bierze udział dwóch graczy. Każdy gracz dostaję jedną kartę ze zbioru {1, 2, ..., n}, każdą z prawdopodobieństwem 1/n. Każdy z graczy w tajemnicy zapisuje ile obstawia. Pewien skończony zbiór możliwych stawek jest ustalony z góry. Następnie ujawniają swoje stawki. Jeżeli są one równe, to dochodzi do sprawdzenia: karty są porównywane i pulę zbiera gracz o większej karcie. Gdy gracze posiadają takie same karty, to pula jest dzielona, tzn. wypłata każdego gracza wynosi 0. W wypadku, gdy jeden gracz postawi większą kwotę, wtedy drugi ma decyzję, czy chce spasować i oddać swoją stawkę, czy sprawdzić. Jeśli chce sprawdzić, to wyrównuje swoją stawkę do stawki przeciwnika i dochodzi do sprawdzenia.
Na zajęciach rozważaliśmy wersję z n=3 i dwoma możliwymi stawkami: 1 i 3.
Pojedynczy gracz rzuca kośćmi tak, aby uzyskać jak najbardziej punktowaną kombinację. W grze używa się d kości k-ściennych. Ściany mają liczby od 1 do k i prawdopodobieństwo wyrzucenia każdej ściany wynosi 1/k. Wpierw gracz rzuca wszystkimi d kośćmi. Następnie może zatrzymać niektóre wybrane kości i rzucić jeszcze raz pozostałymi. Jest to drugi rzut. Następnie może jeszcze wykonać trzeci rzut, podobnie jak w drugim, tylko wybranymi kośćmi. Najdalej po trzecim rzucie przydzielane są punkty. Każdemu układowi przypisana jest pewna punktacja, np. suma liczb na każdej ścianie. Ciekawą funkcją jest np. max(sumy liczb, (k + 1) * d - suma liczb).
W grę gra jednak dwóch graczy, którzy dostają te same kości (tzn. wpierw arbiter losuje ciąg kości jakie będą rzucane, a następnie za każdym razem jak gracz rzuca pewną liczbą n kości, to arbiter udostępnia wartości n kolejnych kości z ciągu, przy czym ich kolejność tych n kości jest nieznana graczowi). Nie widzą oni decyzji swojego przeciwnika. Dopiero, gdy każdy z nich zakończy swoją grę, porównywane są ich wyniki. Wygrywa ten, który ma większy wynik. W przypadku równego wyniku jest remis. Zatem możliwe wypłaty końcowe, to -1, 0 i 1.
Docelowo można próbować rozwiązać wersję z d=5 i k=6. Może okazać się to trudne i w wypadku sukcesu przydzielona będzie odpowiednio większa liczba punktów.
Jest to przeróbka popularnej gry w kółko i krzyżyk na trzy. Gracze nie widzą co postawił przeciwnik, w związku z tym to przeprowadzenie rozgrywki potrzebny jest arbiter, który trzyma pełny stan planszy. Tak jak w normalnej grze gracze ruszają się na przemian. Ruch gracza polega na próbie postawienia pionka na wybrane pole. Arbiter odpowiada, czy to pole jest wolne, wtedy ruch udaje się wykonać i kolejka przechodzi na przeciwnika, bądź pole jest zajęte przez pionek przeciwnika, wtedy uzyskujemy tę informację i próbujemy wskazać inne pole (alternatywna trudniejsza odmiana, to strata ruchu). Wygrywa ten gracz, który jako pierwszy ułoży trójkę.
| Implementacja zasad, liczenie EHS | 5 pkt. |
| Kubełkowanie kart w wersji perfect information | 5 pkt. |
| Kubełkowanie kart w wersji imperfect information | 3 pkt. |
| Wyznaczanie epsilon równowagi Nasha z użyciem CFR dla abstrakcji z kubełkowaniem i ograniczeniem licytacji | ?, czyli pewnie 30 pkt. |
| Bot z modelowaniem przeciwnika podobnie jak w VexBocie | >= 10 pkt. |
| 3 | [15-18) pkt. |
| 3+ | [18-21) pkt. |
| 4 | [21-24) pkt. |
| 4+ | [24-27) pkt. |
| 5 | [27-30] pkt. |
Dla chętnych, możliwe są prace badawcze. Mogą one być również tematami prac magisterskich dla zainteresowanych. Poniżej lista przykładowych tematów.