Sztuczna Inteligencja w Grach I 2013/14

Tematy poruszane na zajęciach

Zasady zaliczania

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).

Głównym zadaniem jest napisanie programu grającego w Piłkę. Za silny program, który zajmie wysokie miejsce wśród puli programów z konkursu ciągłego można dostać wysoką oceną (na pewno 5, gdy program będzie najlepszy), bądź dużą liczbą punktów.

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

Wyszukiwanie słów o możliwie największej liczbie różnych kwadratów.

Parę słów o tym problemie można znaleźć w doktoracie Jakuba Radoszewskiego w punkcie 1.2.

Kilka osób, które osiągnie najlepsze wyniki dla słów o długości 200 i 500 5 pkt.
Osoby bez lepszych wyników, ale wykażą się, że się napracowały 5 pkt.
Implementacja tylko NMCS lub NRPA 2 pkt.
Zrobienie z tego zadania pracy badawczej, próbowanie różnych podejść ≥5 pkt.

Siłowe rozwiązywanie gier

Rozwiązanie wszystkich możliwych wariantów gry w Pana ≥5 pkt.
Program optymalnie grający w Młynek ≥20 pkt.
Rozwiązanie innych znanych gier (wedle uznania) ? pkt.

Możliwe warianty gry w Pana powinny uwzględniać możliwości:

Czyli ogólnie możliwych wariantów jest 36. Rozwiązujemy tylko grę dla dwóch osób.

Stablicowanie gry powinno dawać dodatkowo statystyki w ilu ruchach jest wygrana bądź przegrana oraz umożliwić granie w tą grę w jakiś prosty tekstowy sposób.

Piłka

Więcej informacji znajduje się na stronie http://games.mimuw.edu.pl/pilka/. Znajdują się tam informację o zasadach, protokole, (oraz wkrótce o arbitrze).

Efektywna implementacja zasad 3 pkt.
Alfabeta ze zwiadowcą 3 pkt.
Użycie tablicy transpozycji w alfabecie 2 pkt.
Zrównoleglanie PVS 2 pkt.
Zrównoleglanie EPVS 4 pkt.
Zrównoleglanie DTS 30 pkt.
Funkcja oceniająca z automatycznie wyuczonymi wagami ≥5 pkt.
Automatyczne tworzenie konfiguracji do funkcji oceniających zależnie od metody możliwe nawet 30 pkt.
Monte-Carlo Tree-Search 3 pkt.
Użycie RAVE w MCTS 2 pkt.
Zrównoleglanie lock-free MCTS 2 pkt.
Proof Number Search 3 pkt.
Depth-first PN-Search (DFPN) 6 pkt.
Zrównoleglony DFPN 30 pkt.
Conspiracy Number Search (CNS) 10 pkt.
CNS w wersji depth-first 15 pkt.
CNS w specjalnej wersji Cp=Cd=1 (PV-CNS) 8 pkt.
PV-CNS w wersji depth-first 12 pkt.
Zajęcie czołowego miejsca w konkursie programów (druga połowa maja) 30 pkt.

Uwagi ogólne

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.

Skala ocen

3 [15-18) pkt.
3+ [18-21) pkt.
4 [21-24) pkt.
4+ [24-27) pkt.
5 [27-30] pkt.

Prace badawcze

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.

  1. Porównywanie algorytmów do problemów jednoagentowych.

    NMCS, NRPA z ławą i bez w akcji na łamigłówkach i problemach kombinatorycznych.

  2. Strategie rozwiązywanie kolizji w tablicy transpozycji.

    Głównie chodzi o przebadanie i porównanie z innymi metodami zachłannego decydowania ważności danych miarą: praca/czas od ostatniego dostępu.

  3. Efektywne zrównoleglanie alfabety na wielką skalę techniką TDS.

    W odróżnieniu od tego co zostało w literaturze zaproponowane, możliwe są znaczne i nietrudne do implementacji usprawnienia.

  4. Automatyczne budowanie konfiguracji na podstawie statystyk funkcji oceniającej.

    Rozszerzanie wzorców o dalsze ficzery nie do końca wiadomo jak efektywnie robić. W tym temacie chodzi o wypróbowanie paru strategii opartych na możliwie najlepszym poprawianiu funkcji oceniającej przez analizę statystyk.

  5. Zbadania statystycznych aspektów parametrów przekazywanych w wersji depth-first Monte-Carlo Tree-Search i zbadanie, czy nie da się stworzyć struktury, która szybko odpowiada, czy przeskoczymy do innego wierzchołku u góry ścieżki.

  6. Testowanie Conspiracy Number Search w dla różnych strategii ustalania przedziału.

  7. Sprawdzenie efektywności PV-CNS.

  8. Połączenie MCTS i CNS.

    Przy braku funkcji oceniającej podstawą są losowe rozgrywki. Jednak, aby ocena była wystarczająco dobra musi być odpowiednio dużo symulacji. Ten temat polega na próbie skonstruowania takiego algorytmu, który nominalnie uruchamia MCTS, ale dla wierzchołków z większą liczbą symulacji stopniowo przełącza się na CNS, aby propagować wartości lepiej niż to robi MCTS (co jest jego słabością).