Wydział Informatyki - Informatyka (S1)
specjalność: systemy komputerowe i oprogramowanie
Sylabus przedmiotu Metody sztucznej inteligencji w grach:
Informacje podstawowe
| Kierunek studiów | Informatyka | ||
|---|---|---|---|
| Forma studiów | studia stacjonarne | Poziom | pierwszego stopnia |
| Tytuł zawodowy absolwenta | inżynier | ||
| Obszary studiów | nauki techniczne, studia inżynierskie | ||
| Profil | ogólnoakademicki | ||
| Moduł | — | ||
| Przedmiot | Metody sztucznej inteligencji w grach | ||
| Specjalność | systemy komputerowe i oprogramowanie | ||
| Jednostka prowadząca | Katedra Metod Sztucznej Inteligencji i Matematyki Stosowanej | ||
| Nauczyciel odpowiedzialny | Przemysław Klęsk <pklesk@wi.zut.edu.pl> | ||
| Inni nauczyciele | |||
| ECTS (planowane) | 3,0 | ECTS (formy) | 3,0 |
| Forma zaliczenia | zaliczenie | Język | polski |
| Blok obieralny | 10 | Grupa obieralna | 6 |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | matematyka |
| W-2 | algorytmy i struktury danych |
| W-3 | podstawy programowania |
| W-4 | programowanie obiektowe |
| W-5 | wstęp do sztucznej inteligencji |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Zapoznanie studentów z istotnymi elementami teorii gier (w szczególności z pojęciem strategii mieszanej i równowagi Nasha). |
| C-2 | Zapoznanie studentów z zaawansowanymi technikami przeszukiwania drzew gier o pełnej informacji. |
| C-3 | Zapoznanie studentów z algorytmami dla gier z elementami losowymi i gier o niepełnej informacji. |
| C-4 | Zapoznanie studentów z algorytmami sterowania postaciami/agentami w środowiskach o lokalnej informacji. |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| laboratoria | ||
| T-L-1 | Uzgodnienie reguł gry "Policjanci i złodziej" i ustalenie szczegółów środowiska do turnieju programów napisanych przez studentów. | 3 |
| T-L-2 | Przeprowadzenie testowej rundy turnieju w grę "Policjanci i złodziej". | 3 |
| T-L-3 | Przeprowadzenie turnieju w grę "Policjanci i złodziej". | 3 |
| T-L-4 | Uzgodnienie reguł gry "Sianko" (o niepełnej informacji) i ustalenie szczegółów środowiska do turnieju programów napisanych przez studentów. | 2 |
| T-L-5 | Przeprowadzenie testowej rundy turnieju w grę "Sianko". | 2 |
| T-L-6 | Przeprowadzenie turnieju w grę "Sianko". | 2 |
| 15 | ||
| wykłady | ||
| T-W-1 | Szczegółowe przypomnienie algorytmów do przeszukiwania grafów: Breadth-First-Search, Depth-First-Search, Best-First-Search, A*, Dijkstry. Pojęcie heurystyki. Metryki: euklidesowa, Manhattan, dla siatki heksagonalej. Problemy: przechodzenie labiryntów, gonienie/uciekanie postaci, sudoku minimalne, układanka Rummikub. | 2 |
| T-W-2 | Algorytm Stentz'a (D*) do znajdowania najtańszej ścieżki do celu w środowisku o niepełnej informacji. | 2 |
| T-W-3 | Wybrane elementy teorii gier: gra, strategia, gra skończona, gra o sumie zerowej, twierdzenie o minimaksie, wybory zdominowane, rozwiązanie niestabilne, optymalna stragia mieszana, równowaga Nasha, paradoks Braess'a. Problemy przeszukiwania drzew gier. Mierniki złożoności gier. Projekt Chinook dla warcab angielskich. Algorytmy dla drzew gier o pełnej informacji. Przypomnienie algorytmu MIN-MAX. Algorytm przycinanie alpha-beta w wersjach fail-hard i fail-soft. Twierdzenie Knuth'a-Moore'a. | 3 |
| T-W-4 | Algorytm Quiescence. Sortowanie ruchów w przycinaniu alpha-beta. Heurystyki: tablica odrzucenia, killer heuristic. Tablica transpozycji. Progressive search. Zerowe okna przeszukiwań. Algorytm Scout. Warianty Negamax i Negascout. Wykrywanie heurystyk oceny liści za pomocą algorytmu genetycznego. Problem double-dummy w grze w brydża. | 2 |
| T-W-5 | Gry o pełnej informacji z elementami losowymi. Algorytm Expectiminimax. Analiza dla gry w backgammon. Gry o niepełnej informacji. Zastosowanie metody Monte Carlo generującej wiele drzew gier. | 2 |
| T-W-6 | Uczenie ze wzmocnieniem. Poszukiwanie strategii optymalnej. Agorytmy TD, Q-learning. Ruch osobników w środowiskach ciągłych. Zachowania stadne (klucze ptaków). Reguły Reynoldsa. | 2 |
| T-W-7 | Kolokwium zaliczeniowe. | 2 |
| 15 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| laboratoria | ||
| A-L-1 | Udział w zajęciach. | 15 |
| A-L-2 | Napisanie w parach programów do gry w grę "Policjanci i złodziej" z wykorzystaniem własnych pomysłów heurystycznych. | 18 |
| A-L-3 | Napisanie w parach programów do turnieju w grę "Sianko" z wykorzystaniem własnych pomysłów heurystycznych. | 18 |
| 51 | ||
| wykłady | ||
| A-W-1 | Udział w wykładzie, w tym udział w dyskusji, proponowanie sposób rozwiązania problemów gier. | 15 |
| A-W-2 | Przygotowanie się do kolokwium zaliczeniowego. | 23 |
| 38 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | Wykład informacyjny. |
| M-2 | Wykład problemowy. |
| M-3 | Metoda przypadków. |
| M-4 | Gry dydaktyczne. |
| M-5 | Dyskusja dydaktyczna. |
| M-6 | Pokaz. |
| M-7 | Metody programowane z użyciem komputera. |
Sposoby oceny
| KOD | Sposób oceny |
|---|---|
| S-1 | Ocena formująca: Dwie oceny z laboratoriów za napisane programy. |
| S-2 | Ocena podsumowująca: Ocena z kolokwium zaliczeniowego. |
| S-3 | Ocena podsumowująca: Ocena z laboratoriów jako średnia z ocen za programy. |
Zamierzone efekty kształcenia - wiedza
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|---|
| I_1A_O6/07_W01 Zna i rozumie: podstawowe pojęcia z teorii gier, zaawansowane techniki i algorytmy przeszukiwania drzew gier, algorytmy wspomagające podejmowanie decyzji w środowiskach/warunkach niepełnej informacji lub losowości. | I_1A_W12, I_1A_W01 | — | — | C-1, C-2, C-3, C-4 | — | M-1, M-2, M-5, M-6 | S-2 |
Zamierzone efekty kształcenia - umiejętności
| Zamierzone efekty kształcenia | Odniesienie do efektów kształcenia dla kierunku studiów | Odniesienie do efektów zdefiniowanych dla obszaru kształcenia | Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżyniera | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|---|
| I_1A_O6/07_U01 Potrafi biegle stosować algorytmy i odpowiednie struktury danych a także projektować heurystyki potrzebne do zaprogramowania sztucznych inteligencji grających w gry lub inteligentnych agentów zorientowanych na wypłatę w określonych warunkach środowiska. Samodzielnie realizuje tego typu oprogramowanie w wybranym języku programowania. | I_1A_U01, I_1A_U02, I_1A_U19 | — | — | C-1, C-2, C-3, C-4 | — | M-1, M-2, M-3, M-5, M-6 | S-2 |
Kryterium oceny - wiedza
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_1A_O6/07_W01 Zna i rozumie: podstawowe pojęcia z teorii gier, zaawansowane techniki i algorytmy przeszukiwania drzew gier, algorytmy wspomagające podejmowanie decyzji w środowiskach/warunkach niepełnej informacji lub losowości. | 2,0 | |
| 3,0 | Uzyskanie przynajmniej 50% punktów z kolokwium końcowego. Kolokwium sprawdza rozumienie pojęć i algorytmów przedstawionych w trakcie wykładów. | |
| 3,5 | ||
| 4,0 | ||
| 4,5 | ||
| 5,0 |
Kryterium oceny - umiejętności
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| I_1A_O6/07_U01 Potrafi biegle stosować algorytmy i odpowiednie struktury danych a także projektować heurystyki potrzebne do zaprogramowania sztucznych inteligencji grających w gry lub inteligentnych agentów zorientowanych na wypłatę w określonych warunkach środowiska. Samodzielnie realizuje tego typu oprogramowanie w wybranym języku programowania. | 2,0 | |
| 3,0 | Zaprogramowanie w ramach dwuosobowego zespołu dwóch programów - sztucznych inteligencji - pozwalających na wzięcie udziału w turnieju programów studentów z całej grupy. Programy powinny grać zgodnie z postawionymi regułami gry i wykazywać podstawowe inteligentne zachowania. | |
| 3,5 | ||
| 4,0 | ||
| 4,5 | ||
| 5,0 |
Literatura podstawowa
- J. Watson, Strategia. Wprowadzenie Do Teorii Gier., WNT, 2004
- D.E. Knuth, R.W. Moore, An Analysis of Alpha-Beta Pruning, Artificial Intelligence, 1975
- A. Reinefeld, An Improvement to the Scout Tree Search Algorithm, ICCA Journal, 1983
- L. Rutkowski, Metody i techniki sztucznej inteligencji, 2005
- P. Cichosz, Systemy uczące się, WNT, 2007
Literatura dodatkowa
- E. Feigenbaum, J. Feldman, Maszyny matematyczne i myślenie, 1963
- J. von Neuman, O. Morgenstern, Theory of Games and Economic Behavior, 1944
- D. Laramee, Chess Programming, 2011, tomy I-V
- P. Beling, Praktyczne aspekty programowania gier logicznych, 2006, praca magisterska napisana na Politechnice Łódzkiej