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 ruchw), - mozliwosc cofania ruchw - 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 modulw grajacych. Udzial w konkursie jest NIEOBOWIAZKOWY, chociaz oplacalny: przewidziane sa liczne cenne nagrody w postaci zwolnienia z egzaminu z piatka, dodatkowych punktw z laboratorium, a dla zwyciezcy - uscisk dloni Organizatorw! (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, ktre 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 swj 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 portw wejscia/wyjscia. Oglnie, modul powinien grac fair (nie kombinowa z ustawieniami czasu, nie prbowac 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 . 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 algorytmw", Cormen, Leiserson, Rivest "Kombinatoryka dla programistw", Lipski - algorytmy grafowe. "Pracownia Programowania I" - skrypt - wskazwki dotyczace pisania projektu i dokumentacji