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