Warcaby angielskie - środowisko badania heurystyk

inż. Mateusz Sawicki
Raport wykonany w ramach projektu z kursu "Metody sztucznej inteligencji"
Data: 01.02.2013

English draughts - the analysis environment for evaluation functions

inż. Mateusz Sawicki
The project described in this report has been completed to fulfill the requirements for the course: 'Methods of artificial intelligence'.
Date: February 1st, 2013


Abstract

Main goal of this project was to implement analysis environment for evaluation functions, which could be used by students during the 'Methods of artificial intelligence' course. Final product of this project should show how changes in implementation of evaluation function affect the quality of found state.





Cel projektu

Głównym celem projektu było stworzenie środowiska dydaktycznego, pozwalającego studentom na poznanie zasad działania heurystycznych metod oceny stanu. Powstała aplikacja udostępnia interfejs, przez który użytkownik może wprowadzić własną implementację heurystycznej funkcji oceny, którą potem program wykorzystuje w generowanym przez siebie drzewie przeszukiwań przestrzeni stanów. Dla uatrakcyjnienia środowiska zdecydowano, że stworzony program będzie pozwalał na grę w warcaby angielskie, a decyzję o wyborze ruchu będzie podejmował na podstawie przyjętej od użytkownika heurystyki.

Podstawowa funkcjonalność programu

Szczegółowy opis funkcjonalności programu znajduje się TUTAJ. Podstawowe funkcje programu to:
  • gra w warcaby (człowiek-człowiek, człowiek-SI, SI-SI)
  • edycja bieżącego stanu planszy
  • okno pozwalające śledzić historię gry oraz zmiany dokonane w programie
  • interfejs pozwalający na zdefiniowanie heurystycznej funkcji oceny osobno dla każdego z graczy (opis API funkcji oceny znajduje się TUTAJ)
  • możliwość włączenia trybu gry wielokrotnej

Internacjonalizacja

Aby umożliwić pracę z programem dla obcokrajowców, środowisko przetłumaczono na cztery języki - polski, angielski, hiszpański i rosyjski. Tłumaczenia dla poszczególnych języków, dzięki wykorzystaniu klasy ResourceBundle, są zawarte w osobnych plikach *.properties, więc edycja poszczególnych fraz, dodawanie nowych i usuwanie starych oraz dodawanie obsługi kolejnych języków są bardzo uproszczone.

Interfejs użytkownika

Interfejs użytkownika składa się z czterech okien:
  • okno główne gry przedstawiające widok na warcabnicę. Pasek menu zawiera opcje zmiany rodzajów graczy (ludzki, bądź sterowany przez sztuczną inteligencję), edycji stanu planszy, zmiany języka oraz inne
  • okno kontroli gry pozwala na rozpoczęcie, zatrzymanie i zresetowanie przebiegu gry oraz uruchomienie trybu gry wielokrotnej. Ponadto przechowuje informacje o statystykach zwycięstw poszczególnych graczy
  • okno log przechowuje informacje na temat historii ruchów, zmian ustawień gry oraz komunikaty użytkowników, jeżeli takie zostaną przesłane z funkcji heurystycznej, dostarczonej przez użytkownika
  • okno heurystyki dostarcza interfejs pozwalający na przekazanie wybranym graczom zdefiniowanej przez użytkownika, bądź wewnętrznej funkcji heurystycznej. Szczegółowy opis API funkcji oceny znajduje się TUTAJ.

    Szczegółowy opis interfejsu użytkownika znajduje się TUTAJ.

gui

Widok na interfejs użytkownika

Implementacja - podstawowe informacje

Środowisko zostało w całości oprogramowane w języku Java w wersji 6. Ważniejsze wykorzystane mechanizmy języka to:
  • JavaCompiler - pozwala na skompilowanie wprowadzonej przez użytkownika funkcji oceny
  • mechanizm refleksji - pozwala na załadowanie i wykonanie, uprzednio skompilowanej, zdefiniowanej przez użytkownika funkcji oceny
  • wielowątkowość - zrównoleglenie obliczeń uzyskano poprzez interfejs Runnable
Implementacja funkcjonalności odpowiedzialnej za ładowanie dynamicznie stworzonej klasy okazała się najtrudniejszą częścią projektu, ze względu na bardzo słabe udokumentowanie tego procesu w internecie. Metodą prób i błędów udało się wypracować odpowiednią metodologię, która pozwoliła osiągnąć zamierzony cel. Opracowane rozwiązanie wymagało stworzenia własnej implementacji klasy odpowiedzialnej za kompilację dostarczonego przez użytkownika kodu źródłowego (wykorzystującą klasę JavaCompiler), klasy rozszerzającej klasę ClassLoader oraz wykorzystanie mechanizmu refleksji.

Sztuczna inteligencja rozwija drzewo przeszukiwania w przestrzeni stanów w oparciu o wielowątkowy algorytm cięć alfa-beta. Wprowadzona modyfikacja do klasycznej wersji tego algorytmu, polega na uruchomieniu przeszukiwania przestrzeni stanów, za pomocą klasycznej wersji tego algorytmu, dla wszystkich następników badanego stanu wyjściowego w sposób równoległy.

Możliwe dalsze modyfikacje

Dalszy rozwój projektu wymagałby dostarczenia dodatkowej funkcjonalności. Funkcjonalność, która powinna zostać dostarczona w pierwszej kolejności to:
  • pomiar czasu przeszukiwania przestrzeni stanów - celem wymuszenia wykonania ruchu w przypadku zbyt długiego czasu przeszukiwania przestrzeni stanów
  • moduł turniejowy - celem udostępnienia możliwości seryjnego porównywania heurystycznych funkcji oceny
Pełna lista pomysłów zmodyfikowania środowiska znajduje się TUTAJ.

Wymagania systemowe

Aby oprogramowanie działało w pełni sprawnie należy zapewnić w systemie obecność środowiska java JDK w wersji co najmniej 6.

Uruchomienie

Aby program udostępniał pełną funkcjonalność, należy uruchomić go za pomocą JDK. Pod systemem z rodziny Windows, dla domyślnej ścieżki instalacji środowiska java JDK i wersji 1.6.0_38 tego środowiska, wywołanie w konsoli wygląda następująco:

"C:\Program Files\Java\jdk1.6.0_38\bin\java.exe" -jar Checkers.jar

W przypadku istnienia różnic w podanych założeniach, ścieżkę należy odpowiednio zmodyfikować. W przypadku wywołania tradycyjnego (poprzez JRE):

java -jar Checkers.jar

program się uruchomi, ale nie pozwoli na kompilację heurystycznej funkcji oceny zdefiniowanej przez użytkownika.

Wykorzystane narzędzia

1. Java SE Development Kit 6 Update 38 - zestaw narzędzi dla programistów, wymagany dla tworzenia programów w języku Java

2. NetBeans IDE 7.2.1 - zintegrowane środowisko programistyczne

3. Interactive native2ascii - do internacjonalizacji programu

4. Convert Case - do internacjonalizacji programu

Materiały źródłowe

1. Piotr Beling: Praktyczne aspekty programowania gier logicznych. Praca magisterska, Politechnika Łódzka, 2006

2. Arthur L. Samuel: Some Studies in Machine Lerning Using the Game of Checkers, 1959

3. Jacek Mańdziuk, Magdalena Kusiak, Karol Walędzik, Evolutionary-based heuristic generators for checkers and give-away checkers, Politechnika Warszawska, 2007

4. Jacek Mańdziuk, Magdalena Kusiak, Karol Walędzik, Evolution of heuristics for give-away checkers, Politechnika Warszawska, 2005

5. Jacek Mańdziuk, Magdalena Kusiak, Karol Walędzik, Evolutionary approach to the game of checkers, Politechnika Warszawska, 2007

6. Wikipdedia, zasady gry