Powrót do strony głównej
SID LAB, semestr letni 2005/2006
środa, 12:15-13:45, sala 5470
prowadzący: Arkadiusz Paterek
<paterek@mimuw.edu.pl>
konsultacje: czwartek, 14:00-15:30, pok. 4010
Tematyka laboratorium:
1. Przeszukiwanie przestrzeni stanów:
- zadania z konkursów informatycznych,
- algorytm IDA*,
- programy grające w gry jednoosobowe.
2. Algorytmy przeszukiwania dla gier dwuosobowych z pełną informacją.
3. Sztuczna inteligencja w grach komputerowych RTS i FPP - języki
skryptowe i używane algorytmy.
4. Uczenie z nadzorem:
- naiwny klasyfikator bayesowski w zastosowaniu do klasyfikacji tekstu,
- regresja logistyczna z użyciem oprogramowania SAS pakietu R.
Na zajęciach będziemy rozwiązywać małe zadania z powyższych tematów.
Podstawą oceny będzie realizacja większego projektu (500-2000 linii kodu)
w wybranej dziedzinie.
Propozycje projektów zaliczeniowych:
A. Udział w Imagine Cup - Project Hoshimi - programming battle
B. Udział w ORTS RTS Game AI Competition
C. Szukanie najlepszych rozwiązań w grze Morpion Solitaire (krechy)
[1] Morpion Solitaire Progress
[2] Incremental Transpositions
[3] Morpion Solitaire
D. Program grający w wybraną grę dwuosobową z pełną informacją (np. piłkarzyki,
kropki) lub z niepełną informacją (np. nożyce-kamień-papier, okręty)
[1] Bruce Moreland's Programming Topics
[2] Fruit 2.1 - najsilniejszy program szachowy open-source
E. Rozwiązywanie kolizji jednostek w 2D
[1] Steering Behaviors For Autonomous Characters
[2] Queuing steering behavior
F. Rozwiązywanie pozycji w grze Antyszachy (Losing Chess, Antichess)
[1] Nilatac's Opening Book
G. Udział w wydziałowym konkursie gry w okręty
- Prototyp arbitra:
arbiter.cpp,
- Przykładowy program grający:
player.cpp.
Pierwszy turniej próbny - pon. 5 VI, godz. 16:00, sala 4010.
Drugi turniej próbny - pon. 12 VI, godz. 15:00, sala 4010.
Wyniki turniejów próbnych
Turniej główny - śr. 14 VI, godz. 15:00, sala 4010 (1000 rund,
5 minut na mecz dla zawodnika).
Wyniki turnieju głównego
Logi z arbitra dla wszystkich gier
[1] Iocaine Powder Explained
[2] RoShamBo Programming Competition
H. Udział w konkursie predykcji CoEPrA
I. Udział w konkursie predykcji Discovery Challenge
J. ...
Wymagania niefunkcjonalne dotyczące projektów zaliczeniowych:
A. Obowiązkowe:
- sprawdzanie argumentów funkcji asercjami,
- Makefile / scons.
B. Plusy:
- automatyczne testy:
a) więcej asercji
b) unit testy
c) testy regresji
d) sanity checks
- CVS / RCS
Zajęcia 1 - Przeszukiwanie dwukierunkowe
22.02.2006
Materiały:
[1] Wykład -
Przeszukiwanie przestrzeni stanów - algorytmy ślepe
Zadania do rozwiązania:
1. Solitaire
2. Colour Hash
Zadanie z * - zdobyć pierwsze miejsce w tym rankingu: Solitaire
pomocny skrypt: skrypt.sh
pomocna książka: Kris Kaspersky "Optymalizacja kodu. Efektywne wykorzystanie pamięci."
Zajęcia 2, 3 - Algorytmy A* i IDA*
01.03.2006, 08.03.2006
Materiały:
[1] Wykład -
Przeszukiwanie przestrzeni stanów - algorytmy heurystyczne
[2] Leonard Bolc, Jerzy Cytowski "Metody przeszukiwania heurystycznego. t.1,2", PWN, 1991
[3] A* w praktyce -
Smart Moves: Intelligent Pathfinding,
Towards more realistic pathfinding
[4] Algorytm IDA* -
Reimplementing A*
[5]
Disjoint pattern database heuristics
Zadania:
1. Solitaire
(Próbowaliśmy rozwiązać za pomocą IDA*. Bez sukcesu. Potrzebujemy lepszej heurystyki.)
2. 15-puzzle
Zajęcia 4 - Algorytmy minimax, alfa-beta cięć, PVS
15.03.2006
Algorytm alfa-beta cięć w wersji fail-soft, negamax:
int alphabeta(depth, alpha, beta)
if (cutoff(depth))
return evaluate() // funkcja oceniająca
best = -INF
for each move do
makeMove(move)
result = -alphabeta(depth + 1, -beta, -alpha)
unmakeMove(move)
if (result >= beta)
return result // beta cięcie
if (result > alpha)
alpha = result
if (result > best)
best = result
return best
Materiały:
[1] Wykład -
Przeszukiwanie przestrzeni stanów - gry
[2] Wprowadzenie do szachów komputerowych -
Bruce Moreland's Programming Topics
[3] Źródła prostego programu szachowego -
Tom Kerrigan's Simple Chess Program
[4] Michael P. Frank "Advances in Decision-Theoretic AI: Limited Rationality and Abstract Search" -
Chapter 2: Evolution of Computer Game Playing Techniques
Zadania:
1. Użyć algorytmów minimax, alfa-beta cięć (z sortowaniem ruchów)
i PVS do rozwiązania gry kółko i krzyżyk na planszy 3x3.
Porównać liczbę przeglądanych wierzchołków.
Zajęcia 5 - Ulepszanie algorytmu heurystykami na przykładzie
algorytmu alfa-beta cięć
22.03.2006
1) efekt horyzontu, technika quiescent search
2) tablica transpozycji, iteracyjne pogłębianie
3) sortowanie ruchów (heurystyka killer-move, heurystyka historii)
4) heurystyka pustego ruchu
Materiały:
[1] Bruce Moreland's Programming Topics
[2] Robert Hyatt's Online Publications
[3] Ed Schröder's Programmer Stuff
[4] Fruit 2.1 - najsilniejszy program szachowy open-source
[5] Crafty - inny silny program szachowy open-source
Zadania:
1. Zastosować wybrane techniki do zmniejszenia liczby wierzchołków
przeglądanych przez algorytm w grze kółko i krzyżyk na planszy 3x3.
Zajęcia 6 - Gry typu NIM, liczby Grundy'ego
29.03.2006
Materiały:
[1] Gra neutralna
[2] Liczby Grundy'ego - Wikipedia
[3] Liczby Grundy'ego - Mathworld
[4] John Conway "On Numbers and Games", Wellesley, 2000.
Zadania:
1. NIM
2.
Paski
Zajęcia 7 - Naiwny klasyfikator bayesowski
05.04.2006
Materiały:
[1] Wykład - Sieci bayesowskie 1, s.26
[2] Stuart Russell, Peter Norvig "Artificial Intelligence: A Modern Approach",
rozdział 20: Statistical Learning Methods, s. 718
[3] Naive Bayes classifier - Wikipedia
[4] Naiwny klasyfikator Bayesa - Internetowy Podręcznik Statystyki, Statsoft
Zadania:
1. Zaimplementować klasyfikację tekstu naiwnym klasyfikatorem bayesowskim.
Program ma realizować następujące przypadki użycia:
./naive_bayes add class_name <file.txt # dodanie nowego tekstu do zbioru treningowego do klasy "class_name"
./naive_bayes <file.txt # sklasyfikowanie tekstu - wypisanie par (klasa, wartość),
# posortowanych po wartości
Zajęcia 8 - Pakiety matematyczne i statystyczne
12.04.2006
- komercyjne:
Mathematica,
MATLAB i Simulink,
Maple,
S-Plus,
Statistica,
SPSS,
GAUSS,
SAS/STAT,
MS Excel,
- darmowe:
R (klon S-Plus),
Scilab,
GNU Octave (klon Matlaba).
Materiały:
[1] An Introduction to R
Zadania:
1. Przerobić Ten-minute Tutorial w programie Mathematica.
Zajęcia 9 - Histogram, estymatory jądrowe, klasyfikator bayesowski, metoda LDA
26.04.2006
Materiały:
[1] Jacek Koronacki, Jan Mielniczuk
"Statystyka dla studentów kierunków technicznych i przyrodniczych"
[2] Jacek Koronacki, Jan Ćwik
"Statystyczne systemy uczące się"
Zadania:
1. Zaimplementować w R klasyfikator LDA, bez użycia funkcji lda().
Przetestować klasyfikator na zbiorze punktów wygenerowanym z dwóch wielowymiarowych rozkładów normalnych.
Zajęcia 10 - Proof number search
10.05.2006
Materiały:
[1] Referat o proof number search
Zadania:
1. Użyć algorytmu Proof Number Search do rozwiązania gry kółko i krzyżyk
na planszy 3x3.
Porównać liczbę przeglądanych wierzchołków z algorytmem alfa-beta cięć.
Zajęcia 11 - Podsumowanie postępów w pracy nad projektami zaliczeniowymi
17.05.2006
Zajęcia 12 - Meta-strategie w grach z niepełną informacją
24.05.2006
Materiały:
[1] Iocaine Powder Explained
Zadania:
1. Napisać program grający w nożyce-kamień-papier, rozszerzający do
meta-strategii prostą predykcję na podstawie częstości ruchów przeciwnika
w ostatnich 10 grach.
Data ostatniej zmiany: 21.10.2006