ITPW

Trójkąty

Zasady gry

W tym roku gramy w trójkąty - prosta gra geometryczna dla dwóch osób, do której wystarcza kartka i długopis.

Zasady ogólne

Na początku gry rysuje się n punktów, rozmieszczonych w dowolny sposób na płaszczyźnie. Następnie gracze wykonują posunięcia na przemian. Posunięcie polega na połączeniu dwóch punktów odcinkiem prostym, ale tak, żeby nie przeciąć dotychczas narysowanych odcinków. Jeżeli w wyniku dodania odcinka powstanie nowy trójkąt, to gracz, których wykonywał ruch dostaje jeden punkt. Gra kończy się, gdy nie można już narysować żadnego odcinka. Celem gry jest zdobycie większej liczby punktów od przeciwnika.

Szczegóły

Liczba punktów n nie przekracza 100. Punkty reprezentowane są przez parę dodatnich liczb całkowitych (x,y). Liczby te nie przekraczają 100. Dany zbiór punktów będziemy nazywać konfiguracją początkową.

Posunięciem jest dodanie odcinka łączącego dwa różne punkty. Wnętrze odcinka nie może zawierać innego punktu z konfiguracji początkowej. Odcinek nie może przecinać żadnego z wcześniejszych odcinków. Dwa odcinki się nie przecinają, wtedy i tylko wtedy, gdy część wspólna zbioru punktów, które reprezentują te odcinki, jest pusta, bądź składa się z jednego punktu - wierzchołka wspólnego.

Gracz zdobywa punkty przez tworzenie trójkątów. Trójkąt musi składać się z trzech odcinków takich, które parami mają punkty wspólne. Gracz dostaje punkt za każdy trójkąt utworzony w wyniku wykonania jego posunięcia, z wyjątkiem trójkątów o niepustym wnętrzu. Trójkąt ma niepuste wnętrze wtedy i tylko wtedy, gdy wewnątrz trójkąta znajduje się jakiś punkt z konfiguracji początkowej.

Jeżeli nie można narysować już żadnego odcinka następuje zakończenie rozgrywki. Każdy z graczy podlicza liczbę zdobytych punktów. Wygrywa ten, który ma ich więcej. W przypadku, gdy obaj gracze zdobyli taką samą liczbę punktów, mamy remis.

Przykład

Na rysunku widzimy 9 punktów i 6 narysowanych odcinków. Odcinki już narysowane zaznaczone są linią ciągłą. Dozwolone odcinki, jakie można dopiero narysować, zaznaczone są linią przerywaną. Połączenie punktów 1 i 5, bądź 5 i 8 utworzy trójkąt o pustym wnętrzu dając jeden punkt. Połączenie punktów 1 i 9, bądź 2 i 4 da dwa nowe trójkąty o pustym wnętrzu, więc takie posunięcie daje dwa punkty. Pozostałe odcinki nie tworzą żadnych nowych trójkątów o pustym wnętrzu. W szczególności połączenie punktów 8 i 9 daje nowy trójkąt, ale w jego wnętrzu znajduje się punkt 7, zatem wnętrze tego trójkąta jest niepuste. Zauważmy, że wśród dozwolonych posunięć nie ma odcinków łączących punkty 1 i 6, bądź 3 i 8, gdyż oba odcinki zawierają inne punkty: 3 w pierwszym przypadku i 5 w drugim.

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 polecenie w formie tekstowej od arbitra, generuje odpowiedź, a następnie wypisuje ją na standardowe wyjście.

Polecenia dotyczą konfiguracji początkowej, wykonywanych posunięć i ustawień czasowych. Na początku arbiter wysyła konfigurację początkową poleceniem set_points. Następnie przeprowadzana jest rozgrywka. W pętli arbiter wysyła polecenie play informujące o ostatnim posunięciu wykonanym przez przeciwnika (o ile nie jest to początek gry), następnie polecenie time_left mówiące ile zostało czasu graczowi i polecenie gen_move - prośba o wygenerowanie ruchu. Ten schemat komunikacji przedstawiony jest poniżej:

set_points
tak długo aż się skończy gra, rób:
    jeśli był ruch przeciwnika, to play
    time_left
    gen_move
// gdy gra jest skończona program jest ubijany

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.

Puste linie wysyłane przez arbitra powinny być ignorowane.

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.

set_points <n> <x1> <y1> ... <xn> <yn>
=
 
Ustawia konfigurację początkową punktów. n oznacza liczbę punktów, a (x1,y1), ..., (xn,yn) oznacza dany zbiór punktów. Podane punkty są parami różne. Wszystkie współrzędne są dodatnimi liczbami całkowitymi.

time_left <t>
=
 
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ć '?'.

play <i> <j>
=
 
Informuje, że przeciwnik połączył ze sobą punkty (xi,yi) i (xj,yj). Liczby i,j są liczbami całkowitymi z przedziału [1,n].

gen_move
= <i> <j>
 
Prosi o podanie posunięcia. Gracz powinien zwrócić numery i,j punktów oznaczające, że odcinek połączył punkty o współrzędnych (xi,yi) i (xj,yj).

Polecenie play jest wysyłane tylko jeśli przeciwnik wykonał ruch. Zatem play nie będzie wysyłane do gracza na początku rozgrywki. Ponadto play nie będzie wysyłane, gdy program przeciwnika zakończy z nieokreślonych powodów swoje działanie przed końcem gry. W takim przypadku arbiter umożliwi rysowanie odcinków pozostałemu graczowi.

Jeżeli obaj gracze zakończą swoje działanie przed końcem rozgrywki, to gra zostaje zakończona przedwcześnie i o wyniku decyduje dotychczasowa liczba zdobytych punktów przez obu graczy.

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:

quit
=
 

Aplet będzie pozwalał na edycję planszy, tzn. edycję punktów i narysowanych odcinków. Po ustawieniu planszy przez użytkownika, jej stan będzie wysyłany do programu za pomocą poleceń set_points i play. Polecenie set_points informuje o konfiguracji punktów, a następnie informacja o wszystkich odcinkach jest wysyłana za pomocą ciągu poleceń play. W ten sposób będzie działało też wbudowane undo.

Rozgrywki

Programy będą uruchamiane na komputerach Intel Core Duo 2.4GHz. 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ę. Rozgrywki będą przeprowadzane dla kilku konfiguracji początkowych. Każda konfiguracja będzie losowa, w tym sensie, że prawdopodobieństwo wylosowania dowolnego punktu jest jednakowe. Każdy program rozegra po dwa mecze z każdym programem dla każdej konfiguracji początkowej - jeden jako gracz zaczynający i jeden jako gracz drugi.

Liczba zdobytych punktów, tzn. liczba utworzonych trójkątów, będzie decydowała o zwycięstwie pojedyńczej partii. Gracz, który zdobędzie więcej punktów wygrywa partię. W przypadku, gdy obaj gracze zdobędą tę samą liczbę punktów występuje remis. Za każdy mecz będą przydzielane duże punkty: za wygraną 2 pkt., za remis 1 pkt., za przegraną 0 pkt. O ostatecznym miejscu w turnieju będzie decydowała łączna liczba zdobytych dużych punktów.

ITPW, KNI TEAM