2024-04-29 - wymagania wersja beta-1
To jest wstępna wersja wymagań do zadania nr 3. Pewne szczegóły mogą się zmienić. Gdy pojawi się ostateczna wersja tego dokumentu to nie będzie miała oznaczenia beta, tylko będzie oznaczona jako wersja ostateczna.
do uzupełnienia
wymagania w przygotowaniu - proszę o kontakt indywidualny
W tym wariancie zadania należy przygotować graf do przechowywania drogowej mapy Polski (częściowej i uproszczonej). Węzły grafu reprezentować będą miejscowości (miasta) a łuki połączenia drogowe między nimi.
Miasta będą miały jednowyrazowe identyfikatory stanowiące ich nazwy uproszczone przez sklejenie nazw wieloczłonowych i eliminację znaków z polskimi ogonkami (to znaczy Łódź pojawi się jako Lodz, a Kąty Wrocławskie jako KatyWroclawskie). Opis miasta musi zawierać, poza jego pełną nazwą (w encodingu UTF-8), współrzędne geograficzne jego centrum (w formacie czysto liczbowym, w stopniach; szerokości północne i długości wschodnie jako liczby dodatnie, a szerokości południowe i długości zachodnie jako liczby ujemne). Reprezentację miejscowości upraszczamy do punktowej. Identyfikatory miast muszą być globalnie unikalne (jeśli w zbiorze danych pojawią się różne miejscowości o tej samej nazwie, to należy dodać do nazwy określenie rozróżniające).
Opis każdego łuku grafu musi zawierać nazwę drogi, dwa identyfikatory węzłów które dany łuk łączy, klasę drogi (autostrady, drogi szybkiego ruchu, drogi krajowe, drogi powiatowe, i połączenia promowe), oraz długość drogi w kilometrach (długość każdego odcinka drogowego powinna być w miarę dokładna, jest to liczba zmiennoprzecinkowa). Zatem na przykład nie będzie jednej takiej drogi jak autostrada A4, natomiast będzie wiele połączeń drogowych klasy autostrada o nazwie A4, jedno z nich między węzłami KatyWroclawskie i Wroclaw. Reprezentacja dróg będzie uproszczona przez zasadę, że każde połączenie drogowe jest dwukierunkowe i ma tę samą długość liczoną w obie strony.
W dodatku do wymagań sformułowanych w zadaniu, niezbędne będzie napisanie prostego programu interaktywnej nawigacji na bazie wczytanej mapy. Program powinien pozwalać na wielokrotne wyszukiwanie połączeń pomiędzy zadanymi miejscowościami, oraz na ustawianie opcji takich jak: wyszukiwanie połączenia najkrótszego lub najszybszego, oraz niezależnie od tego możliwość unikania autostrad (rozumianych jako połączenia płatne). Dla potrzeb obliczania czasu przejazdu przyjmujemy standardowe prędkości poruszania się: dla autostrady 130 km/h, dla drogi szybkiego ruchu 110 km/h, dla drogi krajowej 90 km/h, dla drogi powiatowej 70 km/h, i dla połączeń promowych 10 km/h.
Znajdowanie najkrótszej drogi na mapie może być realizowane algorytmem Dijkstry, lub algorytmem A* z odległością geometryczną jako funkcją heurystyczną. Możliwe są również inne podejścia po uzgodnieniu z prowadzącym.
Interakcyjna nawigacja może być zrealizowana z interfejsem graficznym lub tekstowym.
Ponieważ dla realistycznej implementacji i testowania tego programu potrzebna jest nietrywialnej wielkości mapa (graf), częścią zadania w tym wariancie będzie przygotowanie zbioru danych. Aby umożliwić utworzenie realistycznej i praktycznej mapy, częścią zadania w tym wariancie będzie przygotowanie takiego zbioru w oparciu o rzeczywiste dane dla Polski.
Proszę osoby zainteresowane realizacją tego wariantu zadania o kontakt indywidualny emailem, oraz niezależnie od tego na zajęciach, w celu ustalenia zasad współpracy i koordynacji między grupami nad tworzeniem tej mapy.
Należy przygotować program, który pozwala grać człowiekowi z heurystyką wbudowaną w program za pomocą indywidualnie opracowanego interfejsu. Ten interfejs może być okienkowy wykorzystujący wyłącznie bibliotekę/i dostępne na Linuksie, bądź może być tekstowy input-output, wyświetlający stan planszy do gry po każdym ruchu wykonanym przez program.
Program musi grać w wybraną grę za pomocą zaimplementowanej w nim heurystyki
oszacowującej stan planszy na D ruchów do przodu (łącznie obu stron),
wybierając najlepszy ruch algorytmem MinMax z odcięciami alfa-beta.
Głębokość analizy D będzie parametrem wywołania programu (depth).
Część programu gdzie generowane jest drzewo stanów o głębokości D musi
być napisana bardzo czytelnie i szczegółowo okomentowana, aby dało się
sprawdzić, że program rzeczywiście analizuje dokładnie takie drzewo. Poza
tą analizą minimaksową program może posługiwać się tabelami otwarć i/lub
końcówek gry, ale nie może przeprowadzać żadnych innych analiz ani
symulacji ruchów.
Ruchy wybierane przez program muszą być w pełni zrandomizowane w tym sensie, że jeśli z analizy minimaksowej wynika, że kilka różnych ruchów gracza komputerowego ma dokładnie tą samą wartość funkcji oceny, to program musi wybrać ruch wylosowany spośród tych kilku z rozkładem równomiernym.
Z tego wymagania randomizacji wynika, że odcięć alfa-beta w algorytmie MinMax należy dokonywać tylko gdy występuje ostra nierówność w porównaniu parametrów alfa i beta. Gdy parametry są równe, odcięcia nie dokonujemy.
UWAGA: w zadaniu na ocenę bdb nie ma opcji gry w kółko i krzyżyk. Większość wariantów gry w kółko i krzyżyk jest generalnie rozwiązana, strategie wygrywające dla różnych wariantów są różne, i ogólnie ta gra nie stanowi dobrego pola do implementacji podejścia heurystycznego.
Zatem wybierając ten wariant zadania należy zaimplementować warcaby.
Ze względu na organizację rozgrywek pomiędzy programami konieczne jest ustandaryzowanie wersji warcabów. Będą to warcaby angielskie (checkers), patrz link poniżej.
W czasie rozgrywki sieciowej gracze przesyłają swoje ruchy zgodne z przenośną notacją dla warcab (patrz link poniżej). Wykorzystujemy tylko część tej notacji opisującą ruchy graczy w sekcji Movetext. Numery pól w tej notacji odnoszą się do standardowej reprezentacji pól warcabnicy pokazanej na angielskiej stronie wikipedii. W tym układzie warcabnicy czarne grają na górze.
Uwaga: reguły notacji ruchów dopuszczają zapis wielokrotnego bicia w postaci pełnej, np. 11x18x25 lub skróconej, np. 11x25. Na potrzeby tego projektu dopuszczamy jednak wyłącznie notację pełną, to znaczy zapis wszystkich pól pośrednich wielokrotnego bicia, nawet gdyby zapis skrótowy był w pełni jednoznaczny. Próba wykonania wielokrotnego bicia przedstawionego w zapisie skrótowym będzie traktowane jako wykonanie ruchu nielegalnego.
Opis wariantu warcabów:
https://en.wikipedia.org/wiki/English_draughts
Notacja dla warcab - identyfikacja pól warcabnicy
https://en.wikipedia.org/wiki/English_draughts#Notation
Przenośna notacja dla warcab - sekcja Movetext
https://en.wikipedia.org/wiki/Portable_Draughts_Notation#Movetext
Wprowadzenie do tworzenia strategii gry i heurystyk dla warcab, i kilka
podstawowych funkcji heursytycznych:
https://cs.huji.ac.il/~ai/projects/old/English-Draughts.pdf
Ten raport przestał być dostępny pod podanym linkiem, ale daje się znaleźć w Internecie.
Wszechstronna analiza metod budowy heurystyk dla warcab:
https://onlinelibrary.wiley.com/doi/abs/10.1111/j.1468-0394.2007.00429.x
Wstępna wersja tego artykułu jest dostępna tutaj:
https://www.mini.pw.edu.pl/~mandziuk/PRACE/es_init.pdf
W katalogu przedmiotu udostępnione są dwa programy do tego zadania: w pełni funkcjonalny program brokera, który będę wykorzystywał do organizacji rozgrywek pomiędzy programami generującymi ruchy (klientami), i demonstracyjny program klienta, który zawiera pełną implementację sieciowej warstwy komunikacyjnej do wykorzystania w realizacji zadania. Programy te można samodzielnie skompilować i uruchamiać w celach informacyjnych. Program klienta ma zakodowaną na twardo pewną szczególną rozgrywkę, i można go uruchomić przeciwko samemu sobie, żeby obejrzeć proces gry:
./broker ./client ./client
Można też uruchomić dowolny program klienta ręcznie, w tym również na innym komputerze, podając mu adres komputera i wyświetlony numer portu:
./broker - -
Wtedy w roli klienta można nawet wykorzystać program telnet, podłączyć
się nim do brokera, i grać interakcyjnie z jakimś programem, aczkolwiek nie
jest to wygodne ani polecane, poza jakimś krótkim testem.
Programy opracowane do tego zadania, poza możliwością gry sieciowej przez wymianę ruchów w sposób opisany poniżej i zrealizowany w demonstracyjnym programie klienta, powinny mieć zdolność gry interakcyjnej z heurystyczną funkcją oceny realizowaną przez program. Jak wyjaśniałem na zajęciach, ta funkcja gry interakcyjnej nie będzie oceniana jako część zadania. Zatem jest dopuszczalne, aby ten fragment programu skądś przekopiować, pod warunkiem, że będzie to opisane w raporcie. W ocenie zadania będę przyznawał tylko symboliczny 1 punkt za poprawnie funkcjonujący interfejs.
Zadanie będzie oceniane w skali 1-25 punktów. Podstawowa ocena 0-20 punktów będzie przyznawana normalnie za realizację zadania, raport i pakiet uruchomieniowy. Ponadto będę przyznawał premię za za skuteczność opracowanej heurystyki. Wszystkie programy zostaną uruchomione w masowych rozgrywkach każdy z każdym, i końcowy ranking uzyskany w tych rozgrywkach zdecyduje o punktacji za skuteczność. Poprawnie grające programy otrzymają premię w zakresie 0..5 punktów. Punkty ujemne (od 1 do 3 punktów) będą przyznawane w następujących przypadkach: gdy program wykona istotną liczbę ruchów nielegalnych (10% gier lub więcej), oraz gdy program w rozgrywkach okaże się porównywalny lub gorszy z programem referencyjnym. Zasady budowy programu referencyjnego wyjaśniałem na zajęciach.
Tabela ocen za zadanie:
0..10p - poprawna, zgodna z wymaganiami konstrukcja programu
(minimaks, odcięcia alfa-beta, głębokość przeszukiwania, randomizacja
ruchów, interfejs TUI/GUI, itp.)
5p - czytelna, dobrze wydzielona i dobrze okomentowana funkcja
heurystycznej oceny stanu gry
3p - raport zwięzły, zawierający wszystkie wymagane elementy
2p - pakiet uruchomieniowy: minimalny, pozwalający skompilować program
-3..5p - extra ocena za wynik gry
Uwaga: w trakcie realizacji zadania bardzo proszę o zgłaszanie mi ewentualnie znalezionych błędów w moim programie brokera. Program brokera od wersji 202405120918 uważam za gotowy i każda osoba, która pierwsza znajdzie i zgłosi mi emailem znaleziony w nim błąd, otrzyma dodatkowo 3 punkty za to zadanie. Błąd musi być powtarzalny i udokumentowany przykładowym wywołaniem. Oczywiście jeżeli ja sam znajdę jakiś błąd i opublikuję nową wersję z tym błędem poprawionym, to nie będą się już liczyły zgłoszenia tego błędu.
Program budowy grafu mapy Polski powinien realizować następujący interfejs:
prog town1 town2 [ (LENGTH|TIME) [maxclass [minclass]] ]
Program może być wywołany bez żadnych argumentów i wtedy wchodzi w tryb nawigacji interakcyjnej sterowanej przez menu. Powinno ono umożliwiać ustawianie opcji, takich jak: optymalizacja długości drogi lub czasu przejazdu, unikanie autostrad/promów (patrz poniżej), itp. No i oczywiście powinno dawać możliwości znajdowania połączeń i wyświetlanie ich w jakiś sposób (nie mam specjalnych wymagań jak ten wynik ma być prezentowany).
Program może mieć dodatkowe opcje interakcyjne, np. takie jak możliwość wyszukiwania miejscowości według prefiksów (np. WROC), albo wyrażeń regularnych (np. WROC.AW). Wynikiem wyszukiwania byłaby lista pasujących miejscowości, z której możnaby byłoby wybrać tę właściwą. Ale żadne takie opcje nie są obowiązkowe w tym zadaniu.
Gdy pojawią się argumenty wywołania to muszą one być zgodne z powyższym formatem, i wtedy program nie uruchamia trybu interakcyjnego, tylko znajduje połączenie drogowe (ścieżkę na grafie), wyświetla wyniki, i kończy. Ścieżkę należy wyświetlić w jednym wierszu, jako listę miejscowości oddzielonych spacjami, zakończonych liczbą float, która oznacza długość ścieżki lub czas przejazdu.
Byłoby nieźle, gdyby na końcu tego wiersza pojawiła się jeszcze jedna liczba (tym razem int) wyrażająca liczbę węzłów grafu przeanalizowanych w trakcie wyszukiwania tego połączenia. Węzeł jest uznany za przeanalizowany w trakcie wyszukiwania gdy były sprawdzane drogi z niego wychodzące. Jeżeli ktoś nie potrafi poprawnie tego obliczyć, to proszę w tym miejscu wyświetlić liczbę 0 - nie będzie za to kary.
W przypadku gdyby nie udało się znaleźć połączenia spełniającego podane wymagania, to proszę wyświetlić tylko słowo NOTFOUND, i również liczbę węzłów przeanalizowanych w trakcie przeszukiwania grafu.
Obowiązkowe są dwa argumenty pozycyjne: town1 i town2. Określają one
nazwy miejscowości (identyfikatory węzłów grafu) pomiędzy którymi ma być
znaleziona ścieżka. Pomimo iż łuki grafu są nieskierowane, to drogę
znajdujemy od town1 do town2.
Argumenty trzeci, czwarty, i piąty są nieobowiązkowe, ale gdy któryś z nich się pojawi (wtedy oczywiście muszą również pojawić się wszystkie poprzedzające), to ustawia on pewną modyfikację działania programu.
Gdy trzeciego argumentu nie będzie, lub będzie nim słowo LENGTH, to
optymalizowana jest długość drogi. Gdy natomiast trzecim argumentem będzie
słowo TIME to optymalizowany będzie czas.
Gdy pojawi się argument czwarty to określa on maksymalną klasę drogi, która może być wybierana, a gdy pojawi się argument piąty to określa on minimalną klasę drogi, która może być wybierana.
Oznaczenia klas dróg:
Opracowany program powinien obsługiwać następujące pozycyjne parametry wywołania:
prog interface turn depth random_seed ip-address ip-port
Wyjaśnienia poszczególnych parametrów:
interface wybiera wariant działania programu spośród: GUI i NET
GUI oznacza wariant gry interakcyjnej na terminalu z człowiekiem
NET oznacza wariant gry sieciowej za pośrednictwem programu brokera
Prosta wersja programu brokera zostanie udostępniona później.
Ponadto udostępniony będzie wzorcowy kod interfejsu sieciowego.
turn oznacza wybór roli gracza obsługiwanego przez program spośród:
WHITE lub BLACK
Jeżeli wartością argumentu będzie BLACK to program gra czarnymi i
wykonuje pierwszy ruch. W tym przypadku program powinien od razu
wygenerować swój pierwszy ruch oraz wyświetlić go na planszy w GUI lub
wysłać do interfejsu sieciowego.
Jeżeli wartością argumentu będzie WHITE to program gra białymi i czeka
na ruch partnera - otrzymany albo z GUI albo z interfejsu sieciowego - i
dopiero potem wykonuje swój ruch.
depth oznacza głębokość analizy algorytmu MinMax. Program powinien
zbudować drzewo wszystkich możliwych stanów wynikających z depth
dopuszczalnych ruchów obu graczy (czyli depth/2 ruchów każdego z
graczy).
random_seed parametr opcjonalny; jeśli istnieje, to zadaje ziarno
generatora liczb losowych które należy użyć do zainicjowania generatora
liczb pseudolosowych do generowania ruchów. Oznacza to, że wielokrotne
wywołanie programu z tą samą wartością ziarna (i parametru
turn) spowodują wykonanie identycznych ruchów programu, tak długo jak
długo przeciwnik również będzie wykonywał te same ruchy co wcześniej.
Jeśli ten parametr nie zostanie zadany, to ziarno należy wygenerować w
sposób przypadkowy. Proszę postarać się wygenerować je taką metodą, aby
każde wywołanie programu z bardzo dużym prawdopodobieństwem otrzymało
inne ziarno.
ip-address, ip-port parametry opcjonalne - oznaczają adres
internetowy i numer portu brokera gry do którego należy się podłączyć
aby wysyłać własne ruchy i otrzymywać ruchy przeciwnika. Mają one tylko
znaczenie gdy parametr interface będzie miał wartość NET. Jeśli te
parametry się nie pojawią, to domyślną wartością dla ip-address jest
localhost, a domyślną wartością dla ip-port jest 12345.
do uzupełnienia
Uwaga: proszę nie stosować spacji ani polskich liter w nazwach plików źródłowych. Ja przy rozpakowywaniu przysłanego oprogramowania automatycznie zamieniam w nazwach plików wszystkie spacje na podłogę i wszystkie polskie litery na odpowiedniki bez ogonków. Jeśli pliki Makefile albo CMakeLists.txt będą zawierały nazwy ze spacjami albo polskimi literami, to nie będą działały poprawnie.