Zadanie polega na napisaniu programu grającego w grę Halma. Program zaliczeniowy ma umożliwiać grę, w której każdy z graczy może być człowiekiem lub komputerem. Dodatkowo zostanie zorganizowany turniej, w którym programy uczestników będą pojedynkowały się ze sobą. Udział w turnieju nie jest obowiązkowy, jednak dla autorów najlepszych programów przewidziane zostały cenne nagrody w postaci zwolnienia z egzaminu z Metod programowania z oceną bardzo dobrą oraz dodatkowe punkty na tym egzaminie.
Gra toczy się na kwadratowej planszy n × n. Graczy jest od 1 do 4. Każdy z graczy ma pewną ustaloną liczbę pionków. Pionki każdego z gracza są ustawione w rogu szachownicy w zadanym z góry układzie startowym. Pola na których stoją te pionki nazywamy polami domowymi gracza. Różni gracze mają przypisane różne rogi. Gracze poruszają się cyklicznie (gdy jest ich dwóch, to na przemian). Ruch polega na wybraniu jednego ze swoich pionków, jednego z czterech kierunków i przeniesieniu tego pionka na pierwsze wolne pole jakie znajduje się w tym kierunku. Błędem jest wybranie takiego pionka i kierunku, w którym nie ma wolnych pól. Celem każdego z graczy jest jak najszybsze przeprowadzenie swoich pionków do pól domowych w przeciwległym rogu. Wygrywa ten z graczy, który jako pierwszy przeniesie swoje pionki do przeciwległego rogu.
Poniższy rysunek przedstawia przykładową sytuację w grze z zaznaczonymi wszystkimi dozwolonymi ruchami białych pionków:
Pola są oznaczane za pomocą współrzędnych (x, y). Współrzędna x oznacza pozycję poziomą, a y pionową. Lewy dolny róg planszy ma współrzędne (1, 1), a prawy górny róg (n, n).
Poniższy rysunek przedstawia sytuację początkową dla n=8 i k=3.
Programy grające będą komunikowały się z programem sędziego przez standardowe wejście i wyjście.
Kierunki są oznaczane liczbami od 1 do 4 w sposób pokazany na rysunku:
Na początku program powinien wczytać parametry gry. Będzie to jeden wiersz zawierający pięć liczb całkowitych oddzielonych pojedynczymi odstępami. Liczby te to kolejno parametry n, k, N1, N2, nr. Pierwsze cztery zostały opisane powyżej, nr zaś jest numerem gracza (1 dla gracza białego i 2 dla gracza czarnego).
Gracz biały zaczyna grę od wykonania ruchu, a gracz czarny od wczytania ruchu przeciwnika. Wykonanie ruchu polega na wczytaniu ze standardowego wejścia jednego wiersza zawierającego jedną liczbę całkowitą będącą liczbą milisekund, jakie zostały programowi do końca partii, oraz wypisaniu na standardowe wyjście jednego wiersza zawierającego trzy liczby całkowite oddzielone pojednyczymi odstępami oznaczające kolejno współrzędną x wybranego pionka, jego współrzędną y oraz kierunek ruchu. Wczytanie ruchu przeciwnika polega na wczytaniu jednego wiersza w formacie takim, jak przy wypisywaniu własnego ruchu.
Program nie musi kończyć swojego działania po wczytaniu lub wypisaniu ruchu kończącego rozgrywkę. Sędzia sam wtedy przerwie działanie programów.
Można założyć, że ruchy przeciwnika oraz inne informacje podawane programowi na standardowe wejście będą poprawne i zgodne z opisaną składnią.
Turniej będzie rozgrywany na zasadach każdy z każdym przy różnych limitach czasowych na różnych planszach. Na całą partię każdy z programów będzie mieć określane ograniczenie na czas działania i będzie to liczba pomiędzy 1-15min. Każdych dwóch zawodników będzie grało ze sobą jedną lub więcej partii na różnych planszach. Limity czasowe i liczba rozgrywanych partii między dwoma zawodnikami jest odwrotnie proporcjonalna do kwadratu liczby uczestników. W przypadku bardzo dużej liczby uczestników może być przyjęty inny system rozgrywek niż na zasadach każdy z każdym.
Konkurs najprawdopodobniej zostanie przeprowadzony w dniach 28-29 maja.
Konkurs będzie przeprowadzony w systemie Linux na kumputerach znajdujących się u nas w laboratorium. Program grający będzie miał do własnej dyspozycji 96 MB RAM w tym 8 MB na stos. Program grający stanowi plik lub pliki z kodem źródłowym oraz pliki z danymi. Źródła programów grających będą kompilowane na komputerach u nas w labach.
Program będzie uruchamiany w katalogu, gdzie znajdują się pliki z danymi. Jedyne dozwolone operacje wejścia/wyjścia to: czytanie ze standardowego wejścia, czytanie z plików z danymi i pisanie na standardowe wyjście.
Dozwolone są dwa języki programowania:
Należy używać języka wykładanego na Metodach Programowania.
Źródła programu w Pascalu mogą się składać z jednego lub więcej plików o rozszerzeniu .pas. Dokładnie jeden z tych plików musi być kodem programu głównego, a pozostałe muszą być kodami modułów. Ponadto program będzie kompilowany za pomocą polecenia:
ppc386 -O2 program.pasgdzie program.pas jest nazwą kodu programu głównego.
Ograniczenia dla programów w Pascalu:
Źródła powinny składać się z jednego lub więcej plików z modułem grającym. Każdy plik powinien mieć rozszerzenie .ml lub .mli. Jeśli program składa się z więcej niż jednego pliku należy też dołączyć plik Makefile kompilujący program.
W przypadku braku pliku Makefile program powinien być zapisany w pliku program.ml i będzie kompilowany poleceniem:
ocamlopt program.ml -o program
Jeśli plik Makefile zostanie dostarczony, to program będzie kompilowany poleceniem:
makePowinno ono stworzyć w bieżącym katalogu wykonywalny plik o nazwie program.
Ograniczenia dla programów w Ocamlu:
Ponadto zabronione jest też wykorzystywanie jakichkolwiek dodatkowych modułów; w szczególności używanie mechanizmów wątków, dodatkowych procesów, dodatkowych zasobów systemowych, niedozwolonych operacji wejścia/wyjścia i wszelkiego innego rodzaju niesportowego wykorzystywania systemu operacyjnego i dostępnego środowiska.
Program można wysyłać w nieprzekraczalnym terminie 27.05.2005 do godziny 10:00 na adres pan@mimuw (adresat zażyczył sobie, by jego adres był skrócony w celu utrudnienia spamerom wykorzystania go; trzeba uzupełnić podany adres o to, co zazwyczaj stoi w adresach po słowie mimuw).
Należy przysyłać źródła (nie binarki). Źródła muszą się kompilować u nas w labach tak jak jest to omówione w sekcji Środowisko. Ponadto można wysyłać pliki z danymi (o ile są). Proszę nie wysyłać programów generujących te pliki.
Jedna osoba może wysłać co najwyżej jeden program grający.
Wszelkie błędy, które pojawią się w waszych programach nie będą usuwane. Nawet jeśli są to proste błędy komunikacyjne na przykład jeśli zapomnicie wykomentować kod debugujący. Najlepiej przetestować swój program przed wysłaniem przy użyciu sędziego.
Sędzia do rozgrywania jednej partii dla dwóch programów judge.
Sposób użycia:
judge [ -s, --silent ] [ -v, --verbose ] [ -h, --help ]
[ -i, --init initial_scheme_file ] [ -T, --time game_msec ]
[ -S, --stack stack_size ] [ -D, --data data_size ]
player_one player_two
Znaczenie poszczególnych argumentów:
| -s, --silent | nie wypisywanie niczego |
| -v, --verbose | wypisywanie stanu planszy oprócz standardowych komunikatów |
| -h, --help | wyświetlenie wszystkich opcji |
| -i, --init initial_scheme_file | wczytanie parametrów gry z pliku initial_scheme_file, przy czym plik pownien składać się z czterech liczb n, k, N1, N2 poodzielanych pojedynczymi odstępami; w przypadku podania nazwy pliku `-' (minus) opis parametrów gry będzie czytany ze standardowego wejścia |
| -T, --time game_msec | ustawienie limitu czasowego na mecz w milisekundach; możliwe są przyrostki h m s oznaczające odpowiednio liczbę godzin, minut lub sekund; na przykład 5m oznacza 5 minut na mecz, czyli 300000 milisekund |
| -S, --stack stack_size -D, --data data_size |
ustawienie limitów pamięciowych na rozmiar stosu oraz na rozmiar pamięci wirtualnej przeznaczonej dla programu w bajtach; możliwe są przyrostki m k b oznaczające odpowiednio liczbę megabajtów, kilobajtów lub bajtów |
| player_one player_two |
ścieżki do programów wykonywalnych |
Przykładowe wywołanie:
judge -v -i gra.in -T 5m -S 8m -D 48m halma1 halma2
Przykładowa zawartość pliku gra.in z n=8, k=3, N1=10, N2=100 wygląda tak:
8 3 10 100
Wszelkie uwagi dotyczące sędziego proszę słać na pan@mimuw (adresat zażyczył sobie, by jego adres był skrócony w celu utrudnienia spamerom wykorzystania go; trzeba uzupełnić podany adres o to, co zazwyczaj stoi w adresach po słowie mimuw).
procedure MojRuch;
begin
ReadLn(cz); { pozostały czas w milisekundach do końca partii }
WriteLn(x, ' ', y, ' ', d)
{ współrzędne pionka i kierunek wykonywanego ruchu }
end;
procedure JegoRuch;
begin
ReadLn(x, y, d)
{ współrzędne pionka i kierunek ruchu przeciwnika }
end;
begin
ReadLn(n, k, N1, N2, nr);
{ n, k, N1, N2, jak w opisie, nr -- numer gracza }
if nr=1 then
MojRuch;
while true do begin
JegoRuch;
MojRuch
end
end.
let split_string s =
let rec split s i a =
try
let j = String.index_from s i ' ' in
split s (j + 1) ((String.sub s i (j - i))::a)
with Not_found ->
List.rev ((String.sub s i ((String.length s) - i))::a)
in split s 0 []
let read_integers () =
List.map int_of_string (split_string (read_line ()))
let moj_ruch () =
match read_integers () with
[t] -> (* pozostały czas w milisekundach do końca partii *)
(* współrzędne pionka i kierunek wykonywanego ruchu *)
Printf.printf "%d %d %d\n" x y d
| _ -> failwith "błąd"
let jego_ruch () =
match read_integers () with
[x; y; d] -> (* współrzędne pionka i ruchu przeciwnika *)
| _ -> failwith "błąd"
let graj n k n1 n2 nr =
if nr = 1 then moj_ruch ();
while true do
jego_ruch ();
moj_ruch ()
done
let main () =
match read_integers () with
[n; k; n1; n2; nr] ->
(* n, k, n1, n2 jak w opisie, nr -- numer gracza *)
graj n k n1 n2 nr
| _ -> failwith "błąd"
main ()
14.02.2005 - pierwsza wersja
21.03.2005 - dodanie ograniczeń na n, k, N1 i N2
25.03.2005 - dodanie nazwy
05.05.2005 - dodanie szczegółów turnieju
30.05.2005 - wyniki