======================== Program semestralny z MP ======================== Opis gry ======== Gra "Szewc" jest rozgrywana na siatce toroidalnej o rozmiarze MxN (prostokat MxN ze sklejonymi brzegami: gorny z dolnym i lewy z prawym), np. Ŀ Ĵ <- siatka 3x4 (po sklejeniach 3*4 pionowych krawedzi, Ĵ 4*3 poziomych) Niektore krawedzie na planszy moga byc od poczatku zajete (patrz reguly ponizej). W grze uczestnicza dwaj gracze, ktrzy wykonuja ruchy na przemian. Ruch polega na WYMUSZONYM PASOWANIU lub zajeciu na siatce jednej, dotad nie zajetej krawedzi (pionowej lub poziomej). Jesli wskutek ruchu gracza wszystkie krawedzie wokol jakiegos pola na siatce zostaly zajete, to gracz uzyskuje za to pole 1 punkt (zatem w jednym ruchu mozna uzyskac od 0 do 2 punktow). Jesli w wyniku ruchu gracz uzyskal dodatnia liczbe punktow, to w nastepnym ruchu jego przeciwnik MUSI SPASOWAC. Gra toczy sie az do chwili, gdy zostana zajete wszystkie krawedzie - wtedy zwyciezca zostaje gracz, ktory uzyskal wiecej punktow (czasem mozliwy jest remis), lub do chwili przekroczenia limitu czasu do namyslu przez ktoregos z graczy. 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 [1,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! Czesc interface moduu ma by nastpujca: type TPair = record x,y: integer end; TFileOfPairs = file of TPair; procedure InitGame(var f : TFileOfPairs; sec : integer); procedure turn(var x,y : integer); 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. (1<=M,N<=10) - nastepne pary okreslaja, ktre krawedzie sa od poczatku zajete. Przyjmujemy nastepujacy sposob numerowania krawedzi: KRAWEDZ PIONOWA (i,j), gdzie 1<=i<=M, 1<=j<=N znajduje sie w i-tym wierszu oraz w j-tej kolumnie. (stanowi ona lewy bok pola (i,j)) KRAWEDZ POZIOMA (i,j), gdzie M+1<=i<=2M, N+1<=j<=2N znajduje sie w (i-M)-tym wierszu oraz w (j-N)-tej kolumnie. (stanowi ona gorny bok pola (i-M,j-N)) Przyklad: xxxĿ X Ĵ <- siatka (M=3)x(N=4) z dwiema zajetymi krawedziami Ĵ (1,2) (pionowa) (4,7) (pozioma) xxx Parametr sec okresla, ile sekund 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. Jesli w wyniku ruchu przeciwnika zostala mu przyznana dodatnia liczba punktow, zwrocona wartoscia MUSI byc para (0,0), w przeciwnym przypadku - zajeta krawedz (numeracja krawedzi - j.w.). Jesli procedura zostala wywolana z argumentami (x=0,y=0) to oznacza to, ze przeciwnik musial spasowac (lub nie bylo jeszcze zadnego ruchu przeciwnika). Uwagi: - 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 - 19.04.99 program i dokumentacja - 12.06.99 UWAGA: osoby, ktore oddadza zadanie semestralne dopiero w sesji poprawkowej, moga uzyskac co najwyzej ocene dobra z laboratorium. modul konkursowy - 24.05.99 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