Sztuczna Inteligencja - laboratorium

Przyklady dobrego kodu mozna znalezc tutaj:

• Engine szachowy Fruit i wersja rozpakowana
• Engine grajacy w Go libEGO

Skrypt do profilowania programem oprofile opop.sh .

Wyniki turnieju

Pierwsze trzy miejsca naleza do: Marcina Czyzyka, Grzegorza Kulewskiego, Marka Stepniowskiego (kolejnosc alfabetyczna). Na zajeciach oglosze pelne wyniki oraz w ramach ciekawostki wyniki na komputerach red, ktore roznia sie dosyc istotnie.

W czasie nastepnego weekendu przeprowadze kolejny turniej, tym razem na komputerach red i z odrobine dluzszymi limitami czasowymi liczonymi na partie. Ponadto bedzie mozna wyslac po 2-3 wersje swojego programu.

Turniej koncowy odbedzie sie prawdopodobnie na komputerach klasy red.

Zadanie

• Przyslac problem, w ktorych gracz na ruchu ma dokladnie jeden dobry ruch. Dolaczyc ilosc wezlow po ktorych PNS / DF-PN znajduje rozwiazanie oraz ktory to dobry ruch.
• Rozwiazac ten zbior problemow za pomoca PNS.
• Zaimplementowac DF-PN'a i sprawdzic czy zwraca dokladnie takie same wyniki jak PNS.
• W implementacji PNS i DF-PN przy dodawaniu lisci od razu sprawdzac czy nie sa win/loss i ew. wstawiac nieskonczonosci.
• Przepchnac swoj program na turniej przez te strone.

Zadanie 7

• Zaimplementowac Proof-Number search z alokowaniem pamieci z pool i z tablica transpozycji.
• Sytuacje remisowe lamiemy wybierajac ruch pionka ktory jest: wyzej na planszy, bardziej na lewo na planszy, rusza sie w lewo, rusza sie w dol ( w tej kolejnosci ).
• Dodac do GTP komende pneval plik.brd N uruchamiajaca algorytm PNS doklady (z uzyciem pool) wykonujacy dokladnie N rozwiniec drzewa (startujemy od korzenia (1,1)).
• PNS z TT nie ma sensu, on dziala dopiero gdy sa thresholdy, wiec zrobimy go dopiero na nastepnych zajeciach.

Zadanie 6

• Skupic sie na sile programu poprzez dostrajanie funkcji oceniajacej i innych *prostych* usprawnien.
• Przygotowac program na turniej. Program ma wykonywac kazdy ruch w czasie ponizej 5 sekund na komputerch w labach.
• Zrobic stronke WWW ze: zrodlami, loginem na littlegolem.net i raportem (o ile cos jest :) ).
• Wyslac mi adres strony z tagiem w temacie [SILAB]. (bez spacji, myslnikow i malych liter).

Zadanie 5 (10 pkt + 10 pkt za raport (zmniejszone))

• Zalozyc konto, brac udzial w min. 10 grach i wyslac mi mailem swoj login na www.littlegolem.net.
• Zaimplementowac killer move heuristics.
• Zaimplementowac iteracyjne poglebianie.
• Zintegrowac tablice transpozycji, uzyc jej do odciec i jako heurystyke najelpszego ruchu.
• Zaimplementowac protokol komunikacji z sedzia (ignorujemy time_left, hardcodujemy czas na ruch).
• (najwazniejsze) Przeprowadzic eksperymenty i napisac tresciwy raport opisujacy wplyw zaimplementowanych heurystyk (do wyboru) na sile gry. Np. wlaczenie jakiejs heurystyki, zmiana w funkcji oceniajacej, kolejnosc uwzgledniania heurystyk, porownanie 1 lub 2 killer ruchy, 1 lub 2 ruchy z tablicy transpozycji, poglebienia przeszukiwania dla niektorych galezi, itd. Mozna sie wzorowac na artykulach konferencyjnych np: tym (sekcja 4 i 5, tabelki i wykresy).

Zadanie 4 (1 tydzien, 10 pkt)

Zaimplementowac tablice transpozycji i hashowanie Zobrista (bez integracji w program)

Na zajeciach przetestujemy tez najszybasze wersje waszego kodu z wylaczanymi cieciami alfa-beta i z opcja kompilacji -O3. Przetestujemy predkosc i poprawnosc.

• Zwracam uwage na klase vertex_t i vertex_t::map_t w tym pliku .
• Polecam tez przesledzenie uzycia struktury danych skladajacej sie z: empty_v, empty_v_cnt oraz empty_pos w pliku board.cpp .

Zadanie 3 (1 tydzien, 10pkt)

• Naprawic alfe-bete tak zeby zwracala poprawne wyniki. Plansze oraz docelowe wyniki:

  bialek.brd          10196
  czyzyk.brd             84
  gorczynska.brd         18
  konieczny.brd         -36
  michalska.brd       10409
  niedabylski.brd     10134
  paszt.brd             -22
  pk236053.brd           -7
  stepniowski2.brd     9946
  zaborowski.brd        -35 
  zydor.brd               0 
  

• Przyspieszyc plansze alfabete poprzez inkrementalne utrzymywanie listy pionkow graczy (w celu szybkiej generacji ruchow). Oraz inkrementalne utrzymywanie wartosci funkcji oceniajacej. Wydajnosc testowac minimaxem bez ciec (zeby kolejnosc ruchow nie miala znaczenia). Porownac z innymi uczestnikami zajec czy minimax (bez ciec) przeszukuje ta sama liczbe wierzcholkow.

Zadanie 2a (10 pkt, 2 tygodnie)

• Zaimplementowac algorytm alfa-beta. Algorytm ma przeszukiwac zadana pozycje do glebokosci 4 i wypisywac znaleziona wartosc. Funkcja oceniajaca pozycje ma zwracac wartosc rowna roznicy oceny pionkow bialego i pionkow czarnego. Ocena pionkow gracza to suma wartosci z PST (tablicy piece-square) z tych pol na ktorych znajduja sie pionki tego gracza. Tablice PST dla Bialego (idacego do gory) podaje ponizej:

  130 138 146 160 160 146 138 130
  100 107 114 131 131 114 107 100
   75  81  87 102 102  87  81  75
   55  60  65  78  78  65  60  55
   40  44  48  59  59  48  44  40
   30  33  36  41  41  36  33  30
   25  27  29  32  32  29  27  25
   20  21  22  23  23  22  21  20
  

  Uwaga: do oceny pozycji wygranych (czyli do pierwszego wiersza) dodajemy 10000.

  Tablica PST dla czarnego jest taka sama jak dla bialego tylko "do gory nogami".

• Niech wszyscy stworza Makefile, ktory na polecenie "make" stworzy plik wykonywalny alfabeta, taki ze polecenie: ./alfabeta plansza.brd wypisze dokladnie jedna linie (zakonczona znakiem nowej linii) w ktorej beda dwie liczby oddzielone spacja: wynik alfy-bety z punktu widzenia gracza na ruchu. oraz liczbe przeszukanych wierzcholkow.

• Oprocz tego kazdy przygotuje jedna pozycje do testow w standardowym formacie i przesle mi mailem do konca niedzieli.

Zadanie 2b (5 pkt, 1 tydzien)

Wykonac crosstesting pliku board.cpp z czworka innych uczestnikow zajec w sposob omowiony na zajeciach. (przesylamy board.cpp zawierajacy/rozszerzajacy podany przeze mnie naglowek do 4 osob)

Zadanie 1 (10 pkt, 1 tydzien)

Zaimplementowac logike gry Breakthrough omawianej na zajeciach wg zadanego interfejsu. Oraz napisac automatyczny tester, ktory od zadanej pozycji, bedzie wykonywal losowe ruchy ( kazdy ruch z tym samym prawdopodobienstwem ) az do konca gry. Tester powinien powtorzyc taki playout zadana liczbe razy oraz wypisac dwie statystyki: procent wygranych bialego oraz srednia dlugosc gry. Tester powinien znalezc sie w osobnym pliku tester.cpp , ktory zawiera linie #include "board.cpp". Testery powinny sie cross-kompilowac ze wszystkimi planszami spelniajacymi interfejs.

• Plik z interfejsem board.cpp
• Plansza startowa initial.brd

Wszelkie usterki interfejsu i uwagi przesylajcie na moj adres (lew at mimuw).