Zachodniopomorski Uniwersytet Technologiczny w Szczecinie

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

Forma dydaktycznaKODSemestrGodzinyECTSWagaZaliczenie
wykładyW6 15 1,30,62zaliczenie
laboratoriaL6 15 1,70,38zaliczenie

Wymagania wstępne

KODWymaganie wstępne
W-1matematyka
W-2algorytmy i struktury danych
W-3podstawy programowania
W-4programowanie obiektowe
W-5wstęp do sztucznej inteligencji

Cele przedmiotu

KODCel modułu/przedmiotu
C-1Zapoznanie studentów z istotnymi elementami teorii gier (w szczególności z pojęciem strategii mieszanej i równowagi Nasha).
C-2Zapoznanie studentów z zaawansowanymi technikami przeszukiwania drzew gier o pełnej informacji.
C-3Zapoznanie studentów z algorytmami dla gier z elementami losowymi i gier o niepełnej informacji.
C-4Zapoznanie studentów z algorytmami sterowania postaciami/agentami w środowiskach o lokalnej informacji.

Treści programowe z podziałem na formy zajęć

KODTreść programowaGodziny
laboratoria
T-L-1Uzgodnienie reguł gry "Policjanci i złodziej" i ustalenie szczegółów środowiska do turnieju programów napisanych przez studentów.3
T-L-2Przeprowadzenie testowej rundy turnieju w grę "Policjanci i złodziej".3
T-L-3Przeprowadzenie turnieju w grę "Policjanci i złodziej".3
T-L-4Uzgodnienie reguł gry "Sianko" (o niepełnej informacji) i ustalenie szczegółów środowiska do turnieju programów napisanych przez studentów.2
T-L-5Przeprowadzenie testowej rundy turnieju w grę "Sianko".2
T-L-6Przeprowadzenie turnieju w grę "Sianko".2
15
wykłady
T-W-1Szczegół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-2Algorytm Stentz'a (D*) do znajdowania najtańszej ścieżki do celu w środowisku o niepełnej informacji.2
T-W-3Wybrane 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-4Algorytm 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-5Gry 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-6Uczenie 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-7Kolokwium zaliczeniowe.2
15

Obciążenie pracą studenta - formy aktywności

KODForma aktywnościGodziny
laboratoria
A-L-1Udział w zajęciach.15
A-L-2Napisanie w parach programów do gry w grę "Policjanci i złodziej" z wykorzystaniem własnych pomysłów heurystycznych.18
A-L-3Napisanie w parach programów do turnieju w grę "Sianko" z wykorzystaniem własnych pomysłów heurystycznych.18
51
wykłady
A-W-1Udział w wykładzie, w tym udział w dyskusji, proponowanie sposób rozwiązania problemów gier.15
A-W-2Przygotowanie się do kolokwium zaliczeniowego.23
38

Metody nauczania / narzędzia dydaktyczne

KODMetoda nauczania / narzędzie dydaktyczne
M-1Wykład informacyjny.
M-2Wykład problemowy.
M-3Metoda przypadków.
M-4Gry dydaktyczne.
M-5Dyskusja dydaktyczna.
M-6Pokaz.
M-7Metody programowane z użyciem komputera.

Sposoby oceny

KODSposób oceny
S-1Ocena formująca: Dwie oceny z laboratoriów za napisane programy.
S-2Ocena podsumowująca: Ocena z kolokwium zaliczeniowego.
S-3Ocena podsumowująca: Ocena z laboratoriów jako średnia z ocen za programy.

Zamierzone efekty kształcenia - wiedza

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposó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_W01C-1, C-2, C-3, C-4M-1, M-2, M-5, M-6S-2

Zamierzone efekty kształcenia - umiejętności

Zamierzone efekty kształceniaOdniesienie do efektów kształcenia dla kierunku studiówOdniesienie do efektów zdefiniowanych dla obszaru kształceniaOdniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraCel przedmiotuTreści programoweMetody nauczaniaSposó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_U19C-1, C-2, C-3, C-4M-1, M-2, M-3, M-5, M-6S-2

Kryterium oceny - wiedza

Efekt kształceniaOcenaKryterium 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,0Uzyskanie 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łceniaOcenaKryterium 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,0Zaprogramowanie 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

  1. J. Watson, Strategia. Wprowadzenie Do Teorii Gier., WNT, 2004
  2. D.E. Knuth, R.W. Moore, An Analysis of Alpha-Beta Pruning, Artificial Intelligence, 1975
  3. A. Reinefeld, An Improvement to the Scout Tree Search Algorithm, ICCA Journal, 1983
  4. L. Rutkowski, Metody i techniki sztucznej inteligencji, 2005
  5. P. Cichosz, Systemy uczące się, WNT, 2007

Literatura dodatkowa

  1. E. Feigenbaum, J. Feldman, Maszyny matematyczne i myślenie, 1963
  2. J. von Neuman, O. Morgenstern, Theory of Games and Economic Behavior, 1944
  3. D. Laramee, Chess Programming, 2011, tomy I-V
  4. P. Beling, Praktyczne aspekty programowania gier logicznych, 2006, praca magisterska napisana na Politechnice Łódzkiej

Treści programowe - laboratoria

KODTreść programowaGodziny
T-L-1Uzgodnienie reguł gry "Policjanci i złodziej" i ustalenie szczegółów środowiska do turnieju programów napisanych przez studentów.3
T-L-2Przeprowadzenie testowej rundy turnieju w grę "Policjanci i złodziej".3
T-L-3Przeprowadzenie turnieju w grę "Policjanci i złodziej".3
T-L-4Uzgodnienie reguł gry "Sianko" (o niepełnej informacji) i ustalenie szczegółów środowiska do turnieju programów napisanych przez studentów.2
T-L-5Przeprowadzenie testowej rundy turnieju w grę "Sianko".2
T-L-6Przeprowadzenie turnieju w grę "Sianko".2
15

Treści programowe - wykłady

KODTreść programowaGodziny
T-W-1Szczegół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-2Algorytm Stentz'a (D*) do znajdowania najtańszej ścieżki do celu w środowisku o niepełnej informacji.2
T-W-3Wybrane 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-4Algorytm 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-5Gry 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-6Uczenie 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-7Kolokwium zaliczeniowe.2
15

Formy aktywności - laboratoria

KODForma aktywnościGodziny
A-L-1Udział w zajęciach.15
A-L-2Napisanie w parach programów do gry w grę "Policjanci i złodziej" z wykorzystaniem własnych pomysłów heurystycznych.18
A-L-3Napisanie w parach programów do turnieju w grę "Sianko" z wykorzystaniem własnych pomysłów heurystycznych.18
51
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta

Formy aktywności - wykłady

KODForma aktywnościGodziny
A-W-1Udział w wykładzie, w tym udział w dyskusji, proponowanie sposób rozwiązania problemów gier.15
A-W-2Przygotowanie się do kolokwium zaliczeniowego.23
38
(*) 1 punkt ECTS, odpowiada około 30 godzinom aktywności studenta
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_O6/07_W01Zna 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.
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_W12ma podstawową wiedzę dotyczącą metod sztucznej inteligencji
I_1A_W01ma wiedzę z matematyki teoretycznej ze szczególnym uwzględnieniem jej stosowanych aspektów, matematyki dyskretnej oraz matematyki stosowanej
Cel przedmiotuC-1Zapoznanie studentów z istotnymi elementami teorii gier (w szczególności z pojęciem strategii mieszanej i równowagi Nasha).
C-2Zapoznanie studentów z zaawansowanymi technikami przeszukiwania drzew gier o pełnej informacji.
C-3Zapoznanie studentów z algorytmami dla gier z elementami losowymi i gier o niepełnej informacji.
C-4Zapoznanie studentów z algorytmami sterowania postaciami/agentami w środowiskach o lokalnej informacji.
Metody nauczaniaM-1Wykład informacyjny.
M-2Wykład problemowy.
M-5Dyskusja dydaktyczna.
M-6Pokaz.
Sposób ocenyS-2Ocena podsumowująca: Ocena z kolokwium zaliczeniowego.
Kryteria ocenyOcenaKryterium oceny
2,0
3,0Uzyskanie 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
PoleKODZnaczenie kodu
Zamierzone efekty kształceniaI_1A_O6/07_U01Potrafi 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.
Odniesienie do efektów kształcenia dla kierunku studiówI_1A_U01potrafi w zakresie podstawowym projektować, implementować i testować oprogramowanie
I_1A_U02potrafi aktywnie uczestniczyć w pracach projektowych zespołowych i indywidualnych
I_1A_U19ma umiejętność wyboru algorytmu i struktur danych do rozwiązania określonego zadania inżynierskiego
Cel przedmiotuC-1Zapoznanie studentów z istotnymi elementami teorii gier (w szczególności z pojęciem strategii mieszanej i równowagi Nasha).
C-2Zapoznanie studentów z zaawansowanymi technikami przeszukiwania drzew gier o pełnej informacji.
C-3Zapoznanie studentów z algorytmami dla gier z elementami losowymi i gier o niepełnej informacji.
C-4Zapoznanie studentów z algorytmami sterowania postaciami/agentami w środowiskach o lokalnej informacji.
Metody nauczaniaM-1Wykład informacyjny.
M-2Wykład problemowy.
M-3Metoda przypadków.
M-5Dyskusja dydaktyczna.
M-6Pokaz.
Sposób ocenyS-2Ocena podsumowująca: Ocena z kolokwium zaliczeniowego.
Kryteria ocenyOcenaKryterium oceny
2,0
3,0Zaprogramowanie 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