Projekt semestralny z MP
========================
Opis gry
Jatekos nyilak (swawolne strzaly) jest rozgrywana na planszy prostokatnej MxN.
Niektore pola planszy moga byc od poczatku zajete.
Gracze na przemian dostawiaja po jednym pionku.
Pionki maja postac strzalki, ktora wskazuje na jedno z osmiu sasiednich pol.
Gracz kladzie kolejny pionek zawsze na pole wskazywane przez jego poprzedni
pionek. Zatem pionki kazdego gracza ukladaja sie w lancuch tak, jak pokazuja to
strzalki na pionkach.
W sytuacji poczatkowej kazdy gracz ma po jednym pionku ustawionym gdzies na
planszy.
Pionka nie wolno postawic
* na polu juz zajetym (od poczatku gry, lub przez wczesniej postawiony pionek)
* na polu wskazywanym przez ostatni pionek przeciwnika, czyli na polu,
na ktore przeciwnik ma postawic swoj pionek w najblizszym ruchu.
Gra toczy sie az do chwili, gdy ktorys z graczy
* nie ma mozliwosci wykonania ruchu. Przegrywa gracz zablokowany.
* wykorzystal caly dany mu czas do namyslu. Przegrywa ten, ktoremu
zabraklo czasu
===========================================================================
Zadanie semestralne
===================
Zadanie semestralne polega na napisaniu programu umozliwiajacego rozegranie
wyzej opisanej gry przez czlowieka z komputerem, z drugim czlowiekiem, lub
tez przez komputer z samym soba. Zakladamy, ze kazda plansza ma rozmiar
MxN, gdzie M,N sa z przedzialu [4,10]. Minimalne wymagania to:
- wygodny interfejs uzytkownika (przedstawienie aktualnej sytuacji na planszy
i wykonywanie ruch˘w),
- mozliwosc cofania ruch˘w
- mozliwosc wyboru tego, kto jest pierwszym a kto drugim graczem (czlowiek
czy komputer),
- mozliwosc wczytania opisu planszy z pliku (format pliku taki sam, jak w
opisie interfejsu modulu grajacego),
- lepszy niz losowy algorytm gry komputera.
Przed przystapieniem do pisania programu nalezy przedstawic jego PROJEKT do
akceptacji osobie prowadzacej grupe laboratoryjna. Nieodlaczna (i rowniez
podlegajaca ocenie!) czescia programu semestralnego jest jego DOKUMENTACJA.
===========================================================================
Opis interfejsu moduu grajacego
================================
Przeprowadzony zostanie konkurs modul˘w grajacych. Udzial w konkursie jest
NIEOBOWIAZKOWY, chociaz oplacalny: przewidziane sa liczne cenne nagrody w
postaci zwolnienia z egzaminu z piatka, dodatkowych punkt˘w z laboratorium,
a dla zwyciezcy - uscisk dloni Organizator˘w! (Szczegoly w osobnym pliku.)
Czesc interface moduu ma by nastpujca:
{--------------------------------------------------------------------}
type TPair = record
x,y: integer
end;
TFileOfPairs = file of TPair;
procedure InitGame(var f : TFileOfPairs; sec : longint);
procedure turn(var d : integer; sec: longint);
{--------------------------------------------------------------------}
Procedura InitGame przygotowuje modul do nowej partii. Plik f sklada si z
par liczb dodatnich opisujacych plansze gry jak nastepuje:
- pierwsza para okresla rozmiar planszy, tzn. M i N. (4<=M,N<=10)
- druga para okresla polozenie poczatkowego pionka pierwszego gracza
- trzecia para okresla polozenie poczatkowego pionka drugiego gracza
- czwarta para okresla kierunki, w ktorych zwrocone sa poczatkowe pionki,
odpowiednio, pierwszego i drugiego gracza (patrz nizej)
- nastepne pary okreslaja, kt˘re pola sa od poczatku zajete.
Parametr sec okresla, ile czasu (mierzonego w pewnych abstrakcyjnych
jednostkach) ma modul na "namyslanie sie" w ciagu calej partii. Jesli
modul wykorzysta caly sw˘j czas, to przegrywa. Czas inicjalizacji jest
wliczony w czas "namyslania sie".
Procedura turn otrzymuje ruch przeciwnika i daje w wyniku ruch wykonany
przez modul. Oto opis znaczenia wejsciowego i wyjsciowego parametru d:
we: d = 255: mozliwe tylko jesli wywolana po raz pierwszy w partii.
Oznacza, ze pierwszy ruch nalezy do nas.
d = 0..7: numer polozenia strzalki na wlasnie postawionym pionku
przeciwnika. Gdy wywolane po raz pierwszy w partii oznacza, ze
pierwszy ruch nalezal do przeciwnika, a my jestesmy drugim graczem.
wy: d = 255: ruch nie jest mozliwy.
d = 0..7: numer polozenia strzalki na naszym stawianym pionku.
7 0 1
Oznaczenia kierunkow: 6 2
5 4 3
Parametr sec okresla, ile czasu (mierzonego w tych samych abstrakcyjnych
jednostkach, co czas podany w InitGame) pozostalo modulowi do konca gry.
Uwagi:
- Modul nie moze wykorzystywac ZADNYCH innych modulow, ani plikow
pomocniczych.
- Laczny rozmiar danych statycznych modulu nie moze przekraczac 50KB.
- Czesc inicjalizacyjna modulu musi byc pusta. Cala inicjalizacja ma byc
przeprowadzana w InitGame.
- Modul powinien byc napisany tylko w Pascalu (bez wstawek w innych
jezykach, w tym w assemblerze) i dac sie kompilowac (TP 7.0) przy uzyciu
standardowych opcji kompilatora. Uzywanie dyrektyw kompilatora jest
zabronione. Modul nie moze wykonywac interakcji z uzytkownikiem. Nie
wolno uzywac port˘w wejscia/wyjscia. Og˘lnie, modul powinien grac fair
(nie kombinowa z ustawieniami czasu, nie pr˘bowac przeszkadzac w grze
innym).
- Kazdy modul ma okreslony czas na cala partie, wlacznie z inicjalizacja.
- Moduly ktore wielokrotnie przekrocza czas lub zawiesza sie, zostana
zdyskwalifikowane we wstepnej fazie konkursu.
- Dobra rada: przy testowaniu modulu warto go kompilowac z wlaczonymi
opcjami Range Checking i Overflow Checking.
Terminy:
========
projekt - 30.04.2001
program i dokumentacja - 16.06.2001
UWAGA: osoby, ktore oddadza zadanie semestralne dopiero w sesji
poprawkowej, moga uzyskac co najwyzej ocene dobra z laboratorium.
modul konkursowy - 21.05.2001
Pytania dotyczace zadania semestralnego i konkursu mozna kierowac do
A.Malinowskiego <amal@mimuw.edu.pl>.
Literatura
----------
"Handbook of Artificial Intelligence",
"Heuristics", Pearl,
"Algorytmy Kombinatoryczne", Deo i in. - algorytmy przeszukiwania drzewa gry.
"Algorytmy i struktury danych", Banachowski, Diks, Rytter
"Wprowadzenie do algorytm˘w", Cormen, Leiserson, Rivest
"Kombinatoryka dla programist˘w", Lipski - algorytmy grafowe.
"Pracownia Programowania I" - skrypt - wskaz˘wki dotyczace pisania projektu i
dokumentacji