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 nauk technicznych, studiów inżynierskich
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_W01T1A_W01, T1A_W03, T1A_W07InzA_W02, InzA_W05C-1, C-2, C-3, C-4—M-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_U19T1A_U01, T1A_U02, T1A_U03, T1A_U04, T1A_U07, T1A_U08, T1A_U09, T1A_U11, T1A_U12, T1A_U13, T1A_U14, T1A_U15, T1A_U16InzA_U01, InzA_U02, InzA_U03, InzA_U05, InzA_U06, InzA_U07, InzA_U08C-1, C-2, C-3, C-4—M-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
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaT1A_W01ma wiedzę z zakresu matematyki, fizyki, chemii i innych obszarów właściwych dla studiowanego kierunku studiów przydatną do formułowania i rozwiązywania prostych zadań z zakresu studiowanego kierunku studiów
T1A_W03ma uporządkowaną, podbudowaną teoretycznie wiedzę ogólną obejmującą kluczowe zagadnienia z zakresu studiowanego kierunku studiów
T1A_W07zna podstawowe metody, techniki, narzędzia i materiały stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu studiowanego kierunku studiów
Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraInzA_W02zna podstawowe metody, techniki, narzędzia i materiały stosowane przy rozwiązywaniu prostych zadań inżynierskich z zakresu studiowanego kierunku studiów
InzA_W05zna typowe technologie inżynierskie w zakresie studiowanego kierunku studiów
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
Odniesienie do efektów zdefiniowanych dla obszaru kształceniaT1A_U01potrafi pozyskiwać informacje z literatury, baz danych oraz innych właściwie dobranych źródeł, także w języku angielskim lub innym języku obcym uznawanym za język komunikacji międzynarodowej w zakresie studiowanego kierunku studiów; potrafi integrować uzyskane informacje, dokonywać ich interpretacji, a także wyciągać wnioski oraz formułować i uzasadniać opinie
T1A_U02potrafi porozumiewać się przy użyciu różnych technik w środowisku zawodowym oraz w innych środowiskach
T1A_U03potrafi przygotować w języku polskim i języku obcym, uznawanym za podstawowy dla dziedzin nauki i dyscyplin naukowych właściwych dla studiowanego kierunku studiów, dobrze udokumentowane opracowanie problemów z zakresu studiowanego kierunku studiów
T1A_U04potrafi przygotować i przedstawić w języku polskim i języku obcym prezentację ustną, dotyczącą szczegółowych zagadnień z zakresu studiowanego kierunku studiów
T1A_U07potrafi posługiwać się technikami informacyjno-komunikacyjnymi właściwymi do realizacji zadań typowych dla działalności inżynierskiej
T1A_U08potrafi planować i przeprowadzać eksperymenty, w tym pomiary i symulacje komputerowe, interpretować uzyskane wyniki i wyciągać wnioski
T1A_U09potrafi wykorzystać do formułowania i rozwiązywania zadań inżynierskich metody analityczne, symulacyjne oraz eksperymentalne
T1A_U11ma przygotowanie niezbędne do pracy w środowisku przemysłowym oraz zna zasady bezpieczeństwa związane z tą pracą
T1A_U12potrafi dokonać wstępnej analizy ekonomicznej podejmowanych działań inżynierskich
T1A_U13potrafi dokonać krytycznej analizy sposobu funkcjonowania i ocenić - zwłaszcza w powiązaniu ze studiowanym kierunkiem studiów - istniejące rozwiązania techniczne, w szczególności urządzenia, obiekty, systemy, procesy, usługi
T1A_U14potrafi dokonać identyfikacji i sformułować specyfikację prostych zadań inżynierskich o charakterze praktycznym, charakterystycznych dla studiowanego kierunku studiów
T1A_U15potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla studiowanego kierunku studiów oraz wybrać i zastosować właściwą metodę i narzędzia
T1A_U16potrafi - zgodnie z zadaną specyfikacją - zaprojektować oraz zrealizować proste urządzenie, obiekt, system lub proces, typowe dla studiowanego kierunku studiów, używając właściwych metod, technik i narzędzi
Odniesienie do efektów kształcenia prowadzących do uzyskania tytułu zawodowego inżynieraInzA_U01potrafi planować i przeprowadzać eksperymenty, w tym pomiary i symulacje komputerowe, interpretować uzyskane wyniki i wyciągać wnioski
InzA_U02potrafi wykorzystać do formułowania i rozwiązywania zadań inżynierskich metody analityczne, symulacyjne oraz eksperymentalne
InzA_U03potrafi - przy formułowaniu i rozwiązywaniu zadań inżynierskich - dostrzegać ich aspekty systemowe i pozatechniczne
InzA_U05potrafi dokonać krytycznej analizy sposobu funkcjonowania i ocenić - zwłaszcza w powiązaniu ze studiowanym kierunkiem studiów - istniejące rozwiązania techniczne, w szczególności urządzenia, obiekty, systemy, procesy, usługi
InzA_U06potrafi dokonać identyfikacji i sformułować specyfikację prostych zadań inżynierskich o charakterze praktycznym, charakterystycznych dla studiowanego kierunku studiów
InzA_U07potrafi ocenić przydatność rutynowych metod i narzędzi służących do rozwiązania prostego zadania inżynierskiego o charakterze praktycznym, charakterystycznego dla studiowanego kierunku studiów oraz wybrać i zastosować właściwą metodę i narzędzia
InzA_U08potrafi - zgodnie z zadaną specyfikacją - zaprojektować proste urządzenie, obiekt, system lub proces, typowe dla studiowanego kierunku studiów, używając właściwych metod, technik i narzędzi
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