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).
Ostatnim sposobem zaliczania jest przystąpienie do ustnego egzaminu wiedzy. Możliwe terminy, na które można się zapisywać, będą podane przed sesją. 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 :-).
| Implementacja zasad (wersja 5T) - już po terminie | 3 pkt. |
| Algorytm dfs_it | 2 pkt. |
| Algorytm Nested Monte-Carlo Search (NMCS) | 3 pkt. |
| Algorytm Nested Rollout Policy Adaptation (NRPA) | 5 pkt. |
| Pobicie któregoś rekordu w dowolnej z wersji 5D, 5T, 5T+ | 30 pkt. |
| Rozwiązanie wszystkich możliwych wariantów gry w Pana | 5 pkt. |
| Program optymalnie grający w Młynek | >=20 pkt. |
| Rozwiązanie Doubutsu Shogi | >=15 pkt. |
| Rozwiązanie innych znanych gier (wedle uznania) | ? pkt. |
W najbliższym czasie zajmujemy się powyższą grą i celem jest napisanie programu jak najlepiej grającego. Będzie robiony turniej programów i najlepsi dostaną nawet do 30 pkt. Więcej informacji o turnieju, arbitrze i środowisku jest tu. Najbliższe zadania to:
| Implementacja planszy, prostej funkcji oceniającej + alfabeta (termin do zajęć 30.XI!) | 3 pkt. |
| Za użycie tablicy transpozycji w alfabecie | 5 pkt. |
| Negascout (technika zwiadowcy) | 3 pkt. |
| Użycie GLEM w funkcji oceniającej | 10-20 pkt. |
| Sprawdzanie gróźb lub w ogólności przeszukiwanie przestrzeni gróźb (Threat Space Search) | >= 5 pkt. |
| Implementacja MCTS | 5 pkt. |
| Implementacja tablicy transpozycji w MCTS | 3 pkt. |
| Implementacja heurystyki RAVE w MCTS | 3 pkt. |
Możliwe są punkty częściowe za niepełne implementacje, bądź za jakość rozwiązania. Jeśli termin nie jest wyspecyfikowany, to dana praca domowa jest bezterminowa.
| 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. |
| 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. Poniżej podane są propozycję dwóch prostych gier.
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.
| 3 | [15-18) pkt. |
| 3+ | [18-21) pkt. |
| 4 | [21-24) pkt. |
| 4+ | [24-27) pkt. |
| 5 | [27-30] pkt. |