ITPW

Planowanie

Zasady gry

W tym roku gramy w Planowanie - popularną grę karcianą. Do gry wystarczy talia kart i może w niej uczestniczyć od 2 do 4 graczy.

Gra składa się z pewnej określonej liczby rozdań.

W danym rozdaniu gracze otrzymują pewną liczbę kart. Każdy z graczy otrzymuje ich tyle samo. Rozdanie składa się z dwóch faz:

  • deklaracje,
  • rozgrywka.
W wyniku rozdania każdy z graczy otrzymuje pewną liczbę punktów. Celem całej gry jest zdobyć więcej punktów od przeciwników.

Deklaracje

Każdy z graczy deklaruje liczbę lew jaką zamierza wziąć w tym rozdaniu. Deklarowana liczba lew powinna być między zero, a liczbą posiadanych kart. Gracze robią swoje deklaracje równocześnie, tzn. bez żadnej wiedzy o tym ile deklarują przeciwnicy. Gdy już każdy z graczy przygotuje swoją deklarację zostają one ujawnione.

W praktyce fazę deklaracji przeprowadza się za pomocą kartek. Każdy z graczy, w tajemnicy przed innymi graczami, zapisuje na kartce liczbę lew. Na koniec każdy pokazuje swoją kartkę.

Rozgrywka

Po deklaracjach występuje właściwa rozgrywka. Składa się ona z takiej liczby lew, ile kart posiada każdy z graczy.

Gracz, który zaczyna pierwszą lewę jest ustalony z góry przed rozdaniem. Takiego gracza nazywamy graczem zaczynającym. Wykłada on dowolną wybraną przez niego kartę. Następnie karty dokładają pozostali gracze zgodnie z ustaloną kolejnością (zgodnie z ruchem wskazówek zegara). Pozostali gracze muszą dokładać kartę do koloru. Jeśli nie mają żadnej karty w kolorze wyjściowym, to mogą wyłożyć dowolną kartę.

Lewę bierze ten gracz, który położy najstarszą kartę w kolorze wyjściowym, chyba że któryś z graczy wyłoży kartę w kolorze atutowym; jeśli zrobi to więcej graczy, to lewę bierze ten, który wyłoży najstarszą kartę w tym kolorze. Kolor atutowy jest zawsze taki sam w każdym rozdaniu i jest z góry ustalony na początku całej gry. Gracz, który wziął lewę, wykłada pierwszą kartę w następnej lewie.

Punktacja

Za dane rozdanie gracz otrzymuje tyle punktów ile wziął lew plus ewentualny bonus za wzięcie dokładnie tylu lew ile zadeklarował na początku rozdania. Bonus równa się liczbie kart, którą otrzymał każdy z graczy, czyli tyle ile było lew w całym rozdaniu.

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, wykonywanych zagrań i ustawień czasowych. Na początku arbiter wysyła konfigurację gry za pomocą trzech poleceń: set_deck, set_players i set_game, które odpowiednio informują o wyglądzie talii, ustawieniu graczy i rozkładzie rozdań. Następnie przeprowadzane są rozdania.

W danym rozdaniu arbiter wysyła graczowi karty jakie otrzymał z użyciem polecenia set_cards. Następnie przeprowadzane są fazy deklaracji i rozgrywki.

W fazie deklaracji arbiter wysyła wpierw prośbę o podanie deklaracji poleceniem gen_declare. Następnie dla każdego z graczy wysyłane jest polecenie declare informujące o ich deklaracjach.

W fazie rozgrywki arbiter wysyła tylko dwa polecenia: play i gen_move. Pierwsze polecenie informuje o położeniu karty przez któregoś z graczy, drugie jest prośbą o wygenerowanie karty do położenia. Arbiter te dwa polecenia generuje zgodnie z zasadami gry, tzn. ich kolejność zależy od tego, kto jest graczem zaczynającym i kto wziął ostatnią lewę. Nie ma żadnych dodatkowych poleceń informujących o tym kto wziął lewę, czy też ile lew zostało już rozegranych. Program sam powinien zadbać o poprawną implementację zasad gry i interpretowanie informacji podanych przez powyższe polecenia. Polecenie gen_move powinno tylko generować kartę do położenia, ale nie powinno wykonywać tego posunięcia. Można je wykonać przy odebraniu polecenia play, które jest wysyłane dla każdego z graczy (również dla naszego posunięcia).

Dodatkowo przed każdą prośbą arbitra o podjęcie decyzji, czyli przed wywołaniem poleceń gen_declare, bądź też gen_move, jest wysyłane polecenie time_left podające pozostały czas programowi.

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

set_deck
set_players
set_game
dla każdego rozdania, rób:
    set_cards
    deklaracje()
    rozgrywka()
// gdy gra jest skończona program jest ubijany

deklaracje()
{
    gen_declare
    dla każdego z graczy, rób:
        declare
}

rozgrywka()
{
    w pętli do końca rozgrywki, rób:
        play dla każdej położnej karty,
        gen_move, gdy nasza kolej
}

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_deck <V> <C>
=
 
Ustawia talię kart. V jest łańcuchem znakowym oznaczającym dostępne wartości kart. Każda wartość reprezentowana jest pojedynczym znakiem w kolejności starszeństwa. W grach turniejowych V będzie zawsze wynosić 23456789TJQKA.

C jest łańcuchem znakowym oznaczającym dostępne kolory kart. Każdy kolor reprezentowany jest pojedynczym znakiem. Pierwszy znak w łańcuchu reprezentuje kolor atutowy. W grach turniejowych C będzie zawsze wynosić CDHS.

set_players <n> <i>
=
 
Mówi, że w grze uczestniczy n graczy, a program dostaje numer i. Wszyscy gracze numerowani są liczbami od 0 do n-1. Numeracja mówi o kolejności graczy (zgodnie z ruchem wskazówek zegara). Po graczu o numerze 0 występuje gracz numer 1, po graczu o numerze 1 występuje gracz numer 2, itd. Po graczu o numerze n-1 występuje gracz numer 0. W grach turniejowych będzie zawsze czterech graczy.

set_game <d> <c1> <s1> ... <cd> <sd>
=
 
Mówi jakie będą rozdania w całej grze. d oznacza liczbę rozdań. W i-tym rozdaniu, każdy z graczy dostaje po ci kart, a graczem zaczynającym jest gracz si.

W grach turniejowych konfiguracja będzie stała. Liczba rozdań wynosi 13. Liczba kart w kolejnych rozdaniach rośnie od 1 do 13. Graczem zaczynającym w pierwszym rozdaniu jest gracz o numerze 0, a w kolejnych rozdaniach graczem zaczynającym jest gracz następny w kolejności. Zatem w grach turniejowych będzie zawsze wywoływane polecenie:
set_game 13 1 0 2 1 3 2 4 3 5 0 6 1 7 2 8 3 9 0 10 1 11 2 12 3 13 0

set_cards <c> <K1> ... <Kc>
=
 
Opisuje karty otrzymane przez gracza w bieżącym rozdaniu. c oznacza liczbę kart. Następne parametry K1, ..., Kc opisują karty i każdy z nich jest dwuznakowym łańcuchem. Pierwszy znak oznacza wartość karty, a drugi kolor. Przykładowe poprawne karty w konfiguracji turniejowej: 2C, AS, TD.

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_declare i 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ć '?'.

gen_declare
= <l>
 
Prosi o deklarację. Zwrócona liczba całkowita l powinna być z przedziału [0,c], gdzie c oznacza liczbę kart u gracza.

declare <i> <l>
=
 
Informuje, że gracz o numerze i zadeklarował, że weźmie l lew.

gen_move
= <K>
 
Prosi o kartę do wyłożenia. K powinno być dwuznakowym łańcuchem opisującym poprawną kartę.

play <i> <K>
=
 
Informuje, że gracz o numerze i wyłożył kartę K. K jest dwuznakowym łańcuchem opisującym kartę.

W przypadku, gdy program w odpowiedzi na gen_declare poda nieprawidłową liczbę, bądź w odpowiedzi na gen_move zwróci nieprawidłową karę (nie istniejącą, nie posiadaną przez gracza, bądź nie do koloru) program zostanie ubity.

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 zostaje zakończona przedwcześnie i taki gracz przegrywa, a pozostali gracze zostają zwycięzcami.

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 wprowadzanie alternatywnych konfiguracji gry, tzn. innych talii, innej liczby graczy, czy też innej konfiguracji kolejnych rozdań. Celem takich dodatkowych możliwości jest ułatwienie testowania programu z mniejszą talią, z mniejszą liczby graczy i z mniejszą liczbą rozdań.

Przebieg turnieju

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 rundami. W każdej rundzie wszystkie programy będą dzielone na grupy po 4 programy. Ewentualnie organizatorzy dodadzą do puli programów własne boty tak, aby liczba wszystkich programów była podzielna przez 4. Następnie dla danej rundy karty będą losowane w ten sposób, że we wszystkich meczach pojawią się dokładnie takie same układy kart. Zrealizowane to będzie przez ustawienie na sztywno seedu (zarodka losowości) w arbitrze. Dodatkowo, w danej rundzie, każda czwórka rozegra 4 mecze - wszystkie przesunięcia cykliczne tak, aby każdy gracz grał dokładnie raz z numerami od 0 do 3.

Ranking programów będzie tworzony za pomocą BayesElo. Program ten liczy ranking ELO programów na podstawie wyników meczów. Wyniki przekazywane na wejście tworzone są w następujący sposób. Dla danego meczu 4 programów, dla każdej pary programów porównywane są ich końcowe wyniki. W danej parze program, który ma więcej punktów jest zwycięzcą, natomiast jeśli programy zdobyły tą samą liczbę punktów, to jest to traktowane jako remis. W ten sposób w jednym meczu, dla każdego programu zostaną utworzone aż 3 wyniki, które są przekazywane BayesElo. Wyjątkiem są mecze, które kończą się przedwcześnie w wyniku błędu jednego z programów. W takim wypadku dla całego meczu tworzone są tylko 3 wyniki: przegrana wadliwego programu z pozostałymi. Nie są wtedy tworzone wyniki dla par pozostałych programów.

W pierwszych 10-20 rundach programy będą dzielone na grupy po 4 programy całkowicie losowo. W kolejnych rundach programy będą dzielone w taki sposób, aby minimalizować wariancję ich rankingów ELO. Mianowicie liczony jest ranking ELO na podstawie wszystkich dotychczasowych meczów, a następnie dla danego programu staramy się dobrać takich przeciwników, którzy są możliwie blisko rankingu i dodatkowo liczba rozegranych meczy między tymi graczami jest możliwie najmniejsza. Taki efekt osiągany jest następującą metodą. Bierzemy pierwszego gracza A, który jest najwyżej w rankingu i nie został jeszcze przydzielony do żadnej czwórki. Dla każdego możliwego przeciwnika B symulujemy partie między A i B, a następnie patrzymy jak się zmieniła wariancja rankingu gracza A. Jako przeciwników gracza A wybieramy tych, dla których wariancja średnio najbardziej się zmniejszyła. W symulacji partii między A i B prawdopodobieństwo wygranej, remisu bądź przegranej wyliczane jest na podstawie ich rankingu i przeszłych wyników między tylko tą dwójką graczy.

Szczegółowy opis algorytmu i dokładne wzory pomijamy, gdyż nie są one aż tak istotne przy tworzeniu strategii. W każdym razie, aby dostać się do grona zwycięzców, należy pisać takie programy, które będą dobrze grały przeciwko trudnym przeciwnikom. Nie należy się skupiać na tym, aby maksymalizować swoje szanse ze słabymi programami. Nie mniej z gorszymi przeciwnikami też należy raczej wygrywać z dużym prawdopodobieństwem, gdyż zbyt częste porażki z nimi obniżają ranking.

Liczba rund w całym turnieju będzie nie mniejsza niż 100. W miarę dostępności zasobów sprzętowych będziemy się starać rozegrać jak najwięcej rund. System rankingu ELO jest uznawany na świecie za najbardziej wymierny i jest stosowany w najpopularniejszych grach takich jak Szachy i Go.

ITPW, KNI TEAM