Administracja Centralna Uczelni - Wymiana międzynarodowa (S2)
Sylabus przedmiotu Methods of Artificial Intelligence in Games:
Informacje podstawowe
| Kierunek studiów | Wymiana międzynarodowa | ||
|---|---|---|---|
| Forma studiów | studia stacjonarne | Poziom | drugiego stopnia |
| Tytuł zawodowy absolwenta | |||
| Obszary studiów | — | ||
| Profil | |||
| Moduł | — | ||
| Przedmiot | Methods of Artificial Intelligence in Games | ||
| Specjalność | przedmiot wspólny | ||
| 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 | angielski |
| Blok obieralny | — | Grupa obieralna | — |
Formy dydaktyczne
Wymagania wstępne
| KOD | Wymaganie wstępne |
|---|---|
| W-1 | mathematics |
| W-2 | algorithms and data structures |
| W-3 | programming |
| W-4 | object-oriented programming |
| W-5 | introduction to artificial intelligence |
Cele przedmiotu
| KOD | Cel modułu/przedmiotu |
|---|---|
| C-1 | Familiarization with elements of the game theory (in particular, the notions of optimal mixed strategy and Nash equilibrium). |
| C-2 | Demonstration of advanced techniques for searching game trees (perfect information games). |
| C-3 | Getting familiar with algorithms for games with random elements or imperfect information games. |
| C-4 | Demonstrating possible algorithms for controling agents in unknown environments. |
Treści programowe z podziałem na formy zajęć
| KOD | Treść programowa | Godziny |
|---|---|---|
| laboratoria | ||
| T-L-1 | Formulating the homework project - "Cops and thief": rules of the game, details of environment (engine), planning the tournament for future programs written by students. | 3 |
| T-L-2 | A trial round of playing "Cops and thief", testing the environment. | 3 |
| T-L-3 | The actual "Cops and thief" tournament (students' programs competing against one another). | 3 |
| T-L-4 | Homework project "Hay" (take as few tricks as possible) - a card game of imperfect information. Details of environment for students' programs. | 2 |
| T-L-5 | A trial round of play for "Hay" game. | 2 |
| T-L-6 | The actual "Hay" game tournament (students' programs competing against one another). | 2 |
| 15 | ||
| wykłady | ||
| T-W-1 | Stentz algorithm (D*) for the shortest (cheapest) path in an unknown environment. | 2 |
| T-W-2 | Selected elements of the game theory: game, strategy, finite game, zero-sum game, minimax theorem, dominated choices, unstable solution, optimal mixed strategy, Nash equilibrium (NEQ), Braess paradox. Game tree search problems. Measures of games complexities. Chinook project for checkers. Algorithms for games of perfect information. MIN-MAX, alpha-beta pruning (fail-hard, fail-soft versions). Knuth-Moore theorem. | 3 |
| T-W-3 | Quiescence algorithm. Moves sorting for alpha-beta pruning. Refutation table, killer heuristics. Transposition table. Progressive search. Zero-windows (scout windows) in searches. Scout algorithm. Negamax and Negascout variants. Remarks on genetic algorithms applied for discovering good heuristics. Double-dummy problem in bridge. | 2 |
| T-W-4 | Games of perfect information with random elements. Expectiminimax algorithm. Backgammon example. Games of imperfect information. Monte Carlo methods for generation of alternate trees and scores averaging. | 2 |
| T-W-5 | Reinforcement learning. Definition of V and Q functions (example). Searching for optimal strategy. Bellman equations. Algorithms: TD, Q-learning. | 2 |
| T-W-6 | Exam. | 2 |
| 13 | ||
Obciążenie pracą studenta - formy aktywności
| KOD | Forma aktywności | Godziny |
|---|---|---|
| laboratoria | ||
| A-L-1 | Participation in lab classes. | 15 |
| A-L-2 | Programming (in pairs) AIs for homework projects: "Cops and thief" game, and "Hay" game. | 18 |
| 33 | ||
| wykłady | ||
| A-W-1 | Participation in lectures and discussions. | 15 |
| A-W-2 | Self-preparation for final exam. | 23 |
| 38 | ||
Metody nauczania / narzędzia dydaktyczne
| KOD | Metoda nauczania / narzędzie dydaktyczne |
|---|---|
| M-1 | Lecture. |
| M-2 | Case study methods. |
| M-3 | Didactic games. |
| M-4 | Discussion. |
| M-5 | Demonstration. |
| M-6 | Computer programming. |
Sposoby oceny
| KOD | Sposób oceny |
|---|---|
| S-1 | Ocena formująca: Two grades for homework projects (programmed AIs for games). |
| S-2 | Ocena podsumowująca: Exam grade. |
| S-3 | Ocena podsumowująca: Final grade as the mean from lab grade and exam grade. |
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 | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| WM-WI_2-_null_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. | — | — | C-1, C-2, C-3, C-4 | — | M-1, M-4, M-5 | 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 | Cel przedmiotu | Treści programowe | Metody nauczania | Sposób oceny |
|---|---|---|---|---|---|---|
| WM-WI_2-_null_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. | — | — | C-1, C-2, C-3, C-4 | — | M-1, M-2, M-4, M-5 | S-2 |
Kryterium oceny - wiedza
| Efekt kształcenia | Ocena | Kryterium oceny |
|---|---|---|
| WM-WI_2-_null_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 |
|---|---|---|
| WM-WI_2-_null_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
- 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
- P. Klęsk, Electronic materials from: http://wikizmsi.zut.edu.pl, 2015
Literatura dodatkowa
- J. von Neuman, O. Morgenstern, Theory of Games and Economic Behavior, 1944
- D. Laramee, Chess Programming, 2011, tomy I-V