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
do uzupełnienia
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 poniżej.
Proszę zapoznać się szczegółowo z zasadami tej wersji warcabów, takimi jak: zasady promocji piona na damkę, zasady bicia przez piona i przez damkę, itp. Program, który w czasie gry spróbuje wykonać nielegalny ruch, automatycznie przegrywa tę rozgrywkę.