Tło zadania

Keep up your bright swords, for the dew will rust them. ——《Othello》

Othello patrząc na wszystko, czego dokonał, czuje w sercu wielki żal. Odkłada miecz i rozmyśla o wzlotach i upadkach swojego życia, o burzliwych emocjach. Jego zazdrość i podejrzliwość ostatecznie zniszczyły wszystko, co posiadał.

A czyż nie jest tak z każdym z nas? Nieszczęście może stać się źródłem szczęścia, a szczęście nieszczęścia – losy ludzkie nieustannie się przeplatają. Dzisiejszy sukces jest wynikiem działań podjętych w przeszłości, które mogą otworzyć drzwi do wielu przyszłych możliwości. Życie jest jak partia szachów, pełna czarno-białych kontrastów – pionki, które kiedyś postawiłeś, mogą stać się przeszkodami na twojej drodze. Podobnie jak w Reversi (znanym również jako Othello), gdzie między czernią a bielą panuje nieustanna zmienność, tylko ci, którzy patrzą w przyszłość i panują nad całą sytuacją, mogą wyjść zwycięsko.

Treść zadania

Reversi rozgrywane jest na planszy $8\times 8$, gdzie $(x,y)$ oznacza wiersz $x$ i kolumnę $y$ (indeksowanie od $0$). Początkowy układ planszy składa się z czterech pionków naprzemiennie ułożonych w centrum — $(3,3)$ oraz $(4,4)$ to białe pionki, a $(3,4)$ oraz $(4,3)$ to czarne pionki. Gracze wykonują ruchy naprzemiennie, zaczynają czarne. Po postawieniu nowego pionka, wszystkie pionki przeciwnika znajdujące się w linii między nowym pionkiem a innym pionkiem tego samego koloru (już znajdującym się na planszy) zostają odwrócone. Można przejmować pionki w poziomie, pionie lub po skosie. Linia między pionkami musi składać się wyłącznie z pionków przeciwnika, nie może zawierać pustych pól. Ruch musi przejmować co najmniej jeden pionek, w przeciwnym razie jest nielegalny. Jeśli gracz nie ma żadnego legalnego ruchu, jego tura jest pomijana. Jeden ruch może odwracać pionki w wielu kierunkach jednocześnie; wszystkie przejęte pionki muszą zostać odwrócone, gracz nie ma prawa wyboru. Jeśli gracz ma przynajmniej jeden legalny ruch, musi go wykonać i nie może spasować. Gra trwa do momentu zapełnienia planszy lub sytuacji, w której żaden z graczy nie może wykonać ruchu. Wygrywa gracz, który posiada więcej pionków na planszy.

Szczegóły implementacji

Nie musisz, a nawet nie powinieneś implementować funkcji main. Należy jedynie zaimplementować funkcję Play(Taskid,yourside), gdzie Taskid oznacza numer podzadania, a yourside określa Twoją stronę (yourside=0 dla czarnych, yourside=1 dla białych). Możesz wywoływać poniższe dwie funkcje, aby komunikować się z biblioteką interakcyjną:

1. MakeMove(position): Funkcję tę należy wywołać w swojej turze, aby wskazać ruch na pozycji position. Musisz zagwarantować, że $0\leq \texttt{position.first},\texttt{position.second}< 8$ oraz że ruch jest legalny. Jeśli nie masz żadnego dostępnego ruchu, wywołaj MakeMove(make_pair(-1,-1)). Jeśli gra już się zakończyła, nie powinieneś wywoływać tej funkcji. Funkcja nie zwraca wartości.
2. ReceiveMove(): Funkcję tę należy wywołać w turze przeciwnika, aby otrzymać jego ruch. Funkcja zwraca zmienną typu std::pair<int,int> reprezentującą współrzędne ruchu przeciwnika. Wartość $(-1,-1)$ oznacza, że przeciwnik nie mógł wykonać ruchu. Nie powinieneś wywoływać tej funkcji po zakończeniu gry.

Jeśli gra się zakończyła, powinieneś powrócić z funkcji Play.

Podczas oceny biblioteka interakcyjna wywoła Play dokładnie $10$ razy. W pierwszych $5$ przypadkach grasz czarnymi, w kolejnych $5$ białymi. Pamiętaj o wyczyszczeniu niezbędnych zmiennych po każdym wywołaniu Play. Twój wynik będzie zależał od liczby nierozstrzygniętych porażką (zwycięstwa lub remisy) partii z tych $10$ rozgrywek. Uwaga: wykonanie nielegalnego ruchu skutkuje otrzymaniem $0$ punktów.

Gwarantuje się, że biblioteka interakcyjna zużywa mniej niż $5\,\mathrm{s}$ czasu oraz $10\,\mathrm{MB}$ pamięci, co oznacza, że masz do dyspozycji co najmniej $5\,\mathrm{s}$ czasu oraz $502\,\mathrm{MB}$ pamięci.

Jak debugować program

Zadanie wspiera wyłącznie język C++.

Nazwij swój program reversi.cpp.

Upewnij się, że na początku programu znajduje się #include "reversi.h".

Interfejs, który musisz zaimplementować:

void Play(int Taskid,bool yourside);

Interfejsy, które możesz wywoływać:

void MakeMove(std::pair<int,int> position);

std::pair<int,int> Receive();

Aby skompilować program, uruchom w katalogu zadania:

g++ grader.cpp reversi.cpp -o reversi -O2 -lm

Dostarczone pliki to grader.cpp, reversi.h, template-reversi.cpp oraz gamelauncher.

gamelauncher to program umożliwiający grę na własnym komputerze według zasad tego zadania. Zaleca się używanie go wyłącznie do zapoznania się z zasadami. Nie próbuj uzyskiwać punktów w zadaniu poprzez wykorzystanie tego programu (np. wywołując go jako część interakcji). Ze względu na różnice platformowe, nie gwarantuje się poprawnego działania programu i interfejsu użytkownika na wszystkich systemach. Jeśli program nie chce się uruchomić, spróbuj wykonać:

chmod +x gamelauncher

Punktacja

Zadanie składa się z czterech podzadań, w których mierzysz się z AI o różnym poziomie trudności.

AI (1)

To AI wykonuje losowy legalny ruch (jeśli istnieje). To podzadanie jest warte $10$ punktów.

AI (2)

To AI wykonuje losowe ruchy w początkowej fazie gry, a w końcowej fazie przeszukuje drzewo gry aż do końca, aby wybrać optymalną strategię. To podzadanie jest warte $20$ punktów.

AI (3)

To AI w początkowej fazie przeszukuje wszystkie możliwe ruchy o jeden krok do przodu i wybiera ruch według określonej heurystyki, a w końcowej fazie zachowuje się jak AI (2). To podzadanie jest warte $30$ punktów.

AI (4)

To AI jest ucieleśnieniem doskonałości, stworzonym przez autorów zadania, aby rzucić wyzwanie uczestnikom. To podzadanie jest warte $40$ punktów.

Dostarczona biblioteka interakcyjna korzysta z AI (1). Biblioteka używana podczas właściwej oceny różni się implementacją, dlatego nie pisz kodu zależnego od szczegółów implementacji biblioteki. Pamiętaj, że biblioteka używana podczas oceny jest losowa, podczas gdy dostarczona biblioteka ma stałe ziarno losowości. Jeśli chcesz przetestować więcej losowych danych, możesz zmodyfikować zmienną seed w bibliotece. Możesz poprawić swój wynik poprzez wielokrotne wysyłanie rozwiązań.

Tabela punktacji w zależności od liczby przegranych partii: