Bitwa

Zasady gry

Zasady ogólne

Bitwa jest grą dla 2 graczy. Gra toczy się na prostokątnej planszy, na której gracze mają swoje oddziały. Oddziały są jednego rodzaju i są pogrupowane w dywizje.

Rozgrywka odbywa się w rundach. W każdej rundzie gracze ruszają się dokładnie raz każdą ze swoich dywizji. Przemieszczenie dywizji polega na wskazaniu miejsca docelowego, w kierunku którego wszystkie oddziały zostaną przemieszczone o jedno pole. W przypadku gdy oddział na drodze trafi na oddział przeciwnika, atakuje go.

Każdy oddział posiada określoną siłę, która może ulec zmniejszeniu w wyniku ataków przeciwnika. Oddział ulega zniszczeniu, jeżeli siła spada do zera.

Gra toczy się określoną liczbę rund, bądź do momentu zniszczenia wszystkich oddziałów przeciwnika. Wygrywa gracz, który będzie posiadał więcej oddziałów. W przypadku równej liczby oddziałów u obu graczy o zwycięstwie decyduje łącza siła wszystkich posiadanych oddziałów.

Plansza

Plansza jest prostokątna i składa się z m x n pól: jest m kolumn i n wierszy. Pola planszy są indeksowane parami liczb całkowitych (x, y), 0 ≤ x < m, 0 ≤ y < n, gdzie x oznacza kolumnę, a y wiersz. Pola mogą być puste bądź zablokowane. Na pustych polach mogą stać oddziały, a wchodzenie na zablokowane pola jest zabronione. Na jednym pustym polu może stać co najwyżej jeden oddział.

Przebieg rundy

Wszystkie dywizje obu graczy ustawione są w pewnym porządku, który obowiązuje przez całą grę. W jednej rudzie dywizje przemieszczane są w kolejności tego porządku. Każda dywizja przemieszczana jest tylko raz. Przemieszczenie dywizji polega na (1) wskazaniu przez gracza, do którego należy dana dywizja, miejsca docelowego, w kierunku którego dywizja ma się przemieścić i (2) przemieszczenie dywizji.

Przemieszczanie dywizji

Ogólny schemat

Pierwszym krokiem jest wskazanie miejsca docelowego, w którym mają poruszać się wszystkie oddziały dywizji. Na miejsce docelowe składa się m.in. pewne wskazane pole na planszy (jednak jest to bardziej skomplikowana struktura, szczegóły są podane dalej). Wszystkie oddziały dywizji są sortowane po odległości od miejsca docelowego od najbliższej do najdalszej. Następnie w tej kolejności są przemieszczane oddziały. Przemieszczenie oddziału polega na wybraniu jednego pola sąsiadującego, którego odległość do miejsca docelowego jest jak najmniejsza i przesunięcie oddziału na to pole. Wybrane pole nie może być zablokowane, ani zajęte przez sojuszniczy oddział. Jeżeli pole jest zajęte przez oddział przeciwnika, to dokonywany jest atak. W takim wypadku oddział jest przesuwany tylko wtedy, gdy jednostka przeciwnika zostanie zniszczona w wyniku ataku.

Miejsce docelowe

Pierwszym elementem miejsca docelowego jest pole docelowe. Jest to pole na planszy o współrzędnych (x_d, y_d). Współrzędne te mogą wskazywać na dowolne pole na planszy i nieważne jest to, czy jest to pole zablokowane lub czy coś na nim stoi. Odległość pola (x, y) do pola docelowego wyraża się wzorem:
(x - x_d)² + (y - y_d)².

Przy sortowaniu oddziałów po odległości od miejsca docelowego może zdarzyć się, że dwa oddziały będą równoodległe od pola docelowego. Aby uniknąć takich niejednoznaczności jako miejsce docelowe należy podać jeszcze dwa inne punkty niewspółliniowe z punktem docelowym. Zakładamy, że będą to punkty:
P_x = (x_d + dx, y_d) i
P_y = (x_d, y_d + dy),
gdzie dx i dy wynosi -1 lub 1. Podawanie miejsca docelowego polegać będzie ponadto na podaniu wartości dla dx i dy oraz który z punktów dodatkowych P_x i P_y jest pierwszy, a który drugi (nie wymagamy, aby punkty P_x i P_y były na planszy). Mając dwa dodatkowe punkty, w przypadku gdy odległości dwóch oddziałów do punktu docelowego są takie same, pierwszeństwo rozstrzygamy porównując odległości do pierwszego punktu dodatkowego. Jeżeli i to porównanie nie rozstrzyga kolejności, to wykonujemy ostateczne porównanie odległości do drugiego punktu dodatkowego, które już na pewno daje odpowiedź.

Przemieszczenie oddziału

Gdy już mamy posortowane oddziały po odległości do miejsca docelowego wykonujemy przemieszczanie poszczególnych oddziałów w danej kolejności. Przemieszczanie jednego oddziału polega na wybraniu sąsiedniego pola, które jest najmniej odległe od miejsca docelowego.

Jeżeli pole, na którym znajduje się oddział ma współrzędne (x_o, y_o), to pole o współrzędnych (x, y) nazywamy sąsiednim, jeżeli
max(|x - x_o|, |y - y_o|) ≤ 1.
Czyli pola sąsiednie, to jedno z ośmiu pól stykające się bokiem bądź rogiem, bądź też pole, na którym stoi oddział.

Wśród 9 pól sąsiednich przeglądamy wszystkie pola, które są puste, bądź na których stoi oddział przeciwnika (zakładamy, że pole na którym stoi nasz oddział jest też puste, czyli można myśleć o przemieszczeniu oddziału tak, że oddział znika, znajdujemy pole, na które ma się przemieścić i oddział tam umiejscawiamy; w ten sposób, w wyniku przemieszczenia, oddział może pozostać w miejscu). Porównujemy odległości tych pól do miejsca docelowego w taki sam sposób, w jaki porównywaliśmy odległości oddziałów z całej dywizji, co jest opisane powyżej. Wśród tych pól wybieramy pole najbliższe miejsca docelowego.

Przy przeglądaniu pól sąsiednich gracz może zażyczyć sobie, że jeśli dany oddział sąsiaduje z oddziałem przeciwnika, to zbiór przeglądanych pól ograniczamy do tych pól, na których stoją oddziały przeciwnika. Jeżeli w otoczeniu nie ma oddziałów przeciwnika, to przeglądamy wszystkie puste pola sąsiednie. Decyzję o tym, czy ograniczać się tylko do ataku przeciwnika, jeśli to możliwe, gracz podejmuje raz przy przemieszczeniu dywizji, tzn. podaje tę decyzję razem z miejscem docelowym.

Jeżeli wybrane pole do przemieszczenia oddziału jest puste, to oddział zostaje tam ustawiony. Jeżeli na polu tym stoi oddział przeciwnika to następuje atak.

Atak

Atak następuje, gdy przemieszczamy oddział na pole, na którym znajduje się oddział przeciwnika. W takim wypadku siła oddziału przeciwnika zmniejszana jest o 1. Jeżeli w wyniku zmniejszenia wartość ta osiągnęła 0, to oddział przeciwnika jest usuwany i nasz oddział zostaje przemieszczony na zwolnione pole. W przeciwnym razie nasz oddział pozostaje w miejscu i w ten sposób kończy się jego przemieszczanie.

Protokół

Komunikacja arbitra z programem zawodnika odbywa się przez standardowe wejście i wyjście. Komunikacja składa się z ciągu poleceń. Program zawodnika w pętli wczytuje ze standardowego wejścia polecenia w formie tekstowej od arbitra, generuje odpowiedź, a następnie wypisuje ją na standardowe wyjście.

Polecenia dotyczą konfiguracji gry, przemieszczeń dywizji i ustawień czasowych. Na początku arbiter wysyła konfigurację gry za pomocą polecenia: set_game, które odpowiednio informują o wyglądzie planszy, rozmieszczeniu oddziałów na planszy, kolejności dywizji i początkowej sile wszystkich oddziałów.

Następnie do końca gry arbiter wysyła polecenia związane z ruchem dywizji. W przypadku gdy któryś z graczy (przeciwnik lub my sami) ruszył dywizję, informacje o jej przemieszczeniu arbiter wysyła z użyciem polecenia play. Jeżeli jest to nasza kolej na przemieszczenie dywizji, to prośbę o wygenerowanie ruchu wysyła poprzez polecenie gen_move.

Dodatkowo każda prośba o podanie ruchu dywizji, poprzedzona jest informacją o pozostałym programowi czasie do dyspozycji poprzez wysłanie polecenia time_left.

Cały schemat komunikacji przedstawiony jest w poniższym pseudokodzie:

set_game
do końca gry, rób:
    play dla przemieszczenia dywizji przeciwnika, lub
    time_left, gen_move i play, gdy nasza kolej na przemieszczenie dywizji.

Składnia poleceń

Składnia poleceń zapożyczona jest z protokołu GTP.

Składnia każdego z poleceń może być inna, ale zawsze kończy się znakiem nowej linii.

Odpowiedź gracza zawsze zaczyna się znakiem '=' lub '?' po czym następuje właściwa odpowiedź oraz kończy się dwoma znakami nowej linii (czyli pustą linią).

W przypadku nieobsługiwanego polecenia przez program lub wykrycia innego błędu, gracz powinien zacząć odpowiedź od '?', po czym wypisać opis błędu i zakończyć odpowiedź dwoma znakami nowej linii.

Kolor niebieski oznacza linie wysyłane przez arbitra do gracza, a kolor zielony oznacza odpowiedź gracza.

W poniższych definicjach parametry podawane są w nawiasach trójkątnych.

Opisuje konfigurację gry. m i n oznaczają rozmiary planszy: liczbę kolumn i wierszy. r jest maksymalną liczbą rund podczas rozgrywki. s określa początkową siłę wszystkich oddziałów w grze.

Po tych liczbach występuje n łańcuchów znakowych, każdy o długości m, opisujących kolejne wiersze planszy. i-ty znak j-tego wiersza opisującego planszę określa pole o współrzędnych (i, j). Znak # oznacza, że pole jest zablokowane, znak . (kropka) oznacza, że pole jest puste, a mała lub duża litera alfabetu angielskiego oznacza, że jest to pole puste, na którym stoi oddział należący do dywizji odpowiadającej danej literze. Można założyć, że pola znajdujące się na brzegach planszy zawsze są zablokowane.

Duża litera oznacza dywizję gracza pierwszego, mała litera dywizję gracza drugiego. Kolejność przemieszczania się dywizji wyznaczona jest przez kolejność alfabetyczną przypisanych im liter, przy czym dywizja oznaczona dużą literą rusza się przed dywizją oznaczoną tą samą, ale małą, literą. Zatem dywizje ruszają się w kolejności: A, a, B, b, C, c, itd.

Przykładowe wywołanie set_game może być następujące:

set_game 8 6 100 2 ######## #.A..a.# #AA#.aa# #BB.#bb# #.B..b.# ########

Podaje graczowi, że pozostały czas do jego dyspozycji wynosi t milisekund. Jest to czas, w którym program musi wykonać wszystkie operacje aż do zakończenia gry. Polecenie to jest wysyłane przed każdym gen_move, aby gracz mógł łatwiej weryfikować ile rzeczywiście ma jeszcze dostępnego czasu. Program nie musi obsługiwać tego polecania, jeżeli nie chce kontrolować czasu. W takim wypadku jako odpowiedź może wysyłać '?'.

Prosi o podanie ruchu dla dywizji D. D jest literą alfabetu angielskiego oznaczającą dywizję. W tym miejscu gracz może rozpoznać, czy jest pierwszym graczem, czy też drugim.

Gracz powinien zwrócić wszystkie potrzebne informacje do przemieszczenia dywizji. A jest flagą oznaczającą, czy przy przemieszczeniu oddziału ma być brany pod uwagę tylko atak jeśli możliwy, czy też dowolne dozwolone sąsiednie pole. Wartość 1 oznacza, że preferowany jest atak, a 0 w p.p.

(x_d, y_d) są współrzędnymi pola docelowego.

Pozostałe parametry odpowiedzi określają pierwszy i drugi punkt dodatkowy. dx i dy muszą wynosić -1 lub 1. Określają one punkty P_x i P_y. Następnie flaga p mówi, który z nich jest pierwszy. Wartość 1 oznacza, że P_x jest pierwszy, a 0 oznacza, że P_y jest pierwszy.

Informuje o przemieszczeniu się dywizji (naszej lub przeciwnika) oznaczonej literą D. Pozostałe parametry mają takie same znaczenie jak przy poleceniu gen_move.

Uwagi

W przypadku, gdy program w odpowiedzi na gen_move zwróci nieprawidłowe wartości parametrów (współrzędne pola docelowego poza planszą, wartości flag różne od 0 i 1, wartości dx lub dy różne od -1 i 1) program zostanie ubity.

Polecenia play i gen_move nie będą wołane dla dywizji, w skład których nie wchodzi już żaden oddział (tzn. wszystkie oddziały z tej dywizji zostały zniszczone).

Jeżeli któryś z graczy zakończy swoje działanie przed końcem gry (np. w wyniku własnego błędu, przekroczenia czasu, błędów komunikacji, czy też w wyniku ubicia przez arbitra), to gra jest kontynuowana z udziałem jednego gracza. Polega to na tym, że dywizje ubitego gracza nie będą już w ogóle przemieszczane, czyli nie będą dla nich wołane polecenia play i gen_move.

Testowanie programu

W celu przetestowania swojego programu można użyć udostępnionego apletu. Aplet realizuje funkcjonalność arbitra z użyciem GUI, a nawet więcej. Mianowicie aplet umożliwia wysyłanie dowolnych innych poleceń do programu. Daje to możliwość debugowania własnego programu.

Przy zakończeniu gry, program nie będzie ubijany tak jak to się ma w przypadku arbitra, ale będzie do programu wysyłane polecenie quit. Da to możliwość zakończenia się programowi w normalny sposób, dzięki czemu można sobie na przykład zapisać logi z gry do pliku. Składnia polecenia quit:

Przebieg turnieju

Programy będą uruchamiane na komputerach Intel Core Duo od 2.4GHz do 3GHz. Dostępna pamięć dla programu wynosi 400 MB. Limit czasowy będzie zależał od ilości zgłoszeń i będzie z przedziału od 3 do 15 minut na partię.

W ramach turnieju rozgrywki będą prowadzone jedynie na 8 planszach dostępnych wraz z apletem (wszystkie pliki poza przyklad.bit). Na każdej z plansz każdy uczestnik będzie grał z każdym innym. Kolejność graczy (kto jest pierwszym graczem, a kto drugim) będzie losowana.

O kolejności w rankingu decyduje liczba wygranych minus liczba przegranych. Gdy dla pewnych uczestników te liczby są równe, decyduje suma liczb posiadanych oddziałów minus suma liczb oddziałów przeciwnika (z wszystkich rozegranych gier). Gdy i te są równe, decyduje łączna siła wszystkich posiadanych oddziałów z wszystkich gier minus łączna siła wszystkich oddziałów przeciwnika.