Celem projektu było napisanie programu komputerowego, który byłby w stanie prowadzić z człowiekiem równorzędną rozgrywkę w grę zwaną popularnie Piłkarzykami. W oryginalnej wersji tej gry rozgrywka toczy się na kratkowanej kartce papieru. Boisko ma zazwyczaj wymiar 6 na 10 kratek plus po dwie dodatkowe kratki na bramki. Gra rozpoczyna się na środku boiska. Gracze wykonują swoje ruchy na przemian. Dozwolonymi położeniami piłki są punkty przecięcia kratek kartki. Ruch polega na przeniesieniu piłki z pozycji aktualnej na sąsiednią, co wiąże się z narysowaniem kreski stanowiącej ślad ruchu piłki. Można wykonywać ruchu pionowe, poziome i po skosie, przy czym dane przejście pomiędzy dwoma pozycjami może zostać wykorzystane tylko raz. Ruchy wzdłuż bandy są zabronione. Jeżeli po wykonaniu przez gracza danego ruchu piłka znajdzie się w pozycji uprzednio odwiedzonej lub na bandzie, gracz wykonuje kolejny ruch (w żargonie mówi się, że się "odbija"). W przeciwnym przypadku prawo do ruchu uzyskuje przeciwnik. Oczywiście wygrywa ten zawodnik, który jako pierwszy umieści piłkę w bramce rywala. W sytuacji, kiedy piłka znajdzie się w pozycji, z której nie można wykonać już dozwolonego ruchu, gra kończy się remisem.
Program został napisany w języku Java w wersji JDK 1.5.06 przy użyciu środowiska NetBeans 5.0. Stworzenie programu w formie appletu umożliwiło jego przenośność i łatwą dystrybucję w celu przeprowadzenia testów. Program składa się z czterech podstawowych klas (nie licząc klas wewnętrznych będących odbiorcami zdarzeń interfejsu użytkownika). Klasa Stan służy do pełnego opisu stanu gry oraz dostarcza metody służące do jego sprawdzania i modyfikacji. Klasa Gracz zawiera implementacje metod sztucznej inteligencji. Zadaniem obiektów klasy GeneratorRuchow jest, jak wskazuje nazwa, generowanie listy dozwolonych dla zadanego stanu ruchów. Ostatnia z klas - Pilkarzyki - jest klasą dziedziczącą po JApplet odpowiedzialną za graficzny interfejs użytkownika.
Stan rozgrywki w każdej chwili może być jednoznacznie opisany poprzez położenie piłki oraz listę wszystkich wykorzystanych do tej pory ruchów. W celu ułatwienia implementacji metod sztucznej inteligencji (w tym przede wszystkim wyszukiwania dozwolonych ruchów) oraz wizualizacji rozgrywki zdecydowano się jednak na pewną nadmiarowość w opisie stanu gry. Dla każdej pozycji na boisku pamiętane jest, czy dane pole zostało już odwiedzone, lista pozycji, do których z tego pola istnieje możliwość przejścia (pojedynczym ruchem), jak również lista przejść z pola już wykorzystanych.
- Podejście pierwsze - algorytm minimax
W przypadku stosunkowo prostej gry dwuosobowej, jaką są Piłkarzyki, zastosowanie algorytmu minimax wydaje się podejściem jak najbardziej naturalnym. Co więcej, lektura sprawozdania Bartosza Tarnowskiego, który dwa lata temu pisał podobną grę, utwierdza w tym przekonaniu. Napisany przez wymienionego wyżej studenta program, korzystając z prostej heurystyki, przeszukiwał drzewo dopuszczalnych ruchów aż do szóstego poziomu. W raporcie czytamy, iż już przy głębokości przeszukiwania równej 3 poziom gry programu jest zadowalający. Jednak autor wyżej wymienionego sprawozdania przyjął, że jeden ruch odpowiada przejściu na najbliższe pole, a ruch po "odbiciu" jest już ruchem kolejnym. Wydaje się, że bardziej naturalnym podejściem jest traktowanie jako jednego ruch sekwencji przemieszczeń na planszy aż do momentu zmiany gracza. Tak też ruch jest rozumiany w opisywanym programie.
Zastosowano standardowy algorytm minimax w wersji takiej, jak przedstawiona na stronie [3]. W pierwszym podejściu zastosowano bardzo prostą heurystykę oceniającą jakość pozycji osiąganej przez dany ruch: wartość funkcji wynosiła 0 na środku boiska lub w przypadku remisu, rosła liniowo wraz ze zbliżaniem się do bramki przeciwnika, malała przy zbliżaniu do bramki gracza. Pozycja ze zdobytym golem to duża liczba dodatnia, ze straconym - ujemna. Przeszukiwanie minimaxowe już przy głębokości 2 dawało zadowalające efekty. Pojawił się jednak problem innego rodzaju: nieoczekiwana eksplozja kombinatoryczna. Przy takim zdefiniowaniu pojedynczego ruchu, jak opisano powyżej, jeden ruch może składać się z sekwencji nawet kilkunastu przesunięć. Co gorsze, przy niekorzystnym stanie na boisku, liczba generowanych na jednym poziomie dopuszczalnych ruchów może osiągać setki. Jak wiadomo, algorytm minimax ma wykładniczą złożoność obliczeniową. W praktyce prowadziło to do tego, że już przy głębokości przeszukiwania równej 2 czas reakcji programu przy skomplikowanej sytuacji na boisku wzrastał niekiedy nawet do kilkudziesięciu sekund, co było dla gracza bardzo irytujące. - Podejście drugie - stworzenie skutecznej heurystyki
W związku z niedogodnościami związanymi z użyciem minimaxu postanowiono sprawdzić zachowanie programu przy przeszukiwaniu tylko na głębokości 1 (tylko pierwszy ruch "maxa"), przy jednoczesnym rozbudowaniu heurystycznej funkcji oceniającej. Doświadczenie w grze Piłkarzyki pozwala wysnuć następujące przesłanki inteligentnego zachowania komputerowego przeciwnika:
- podstawowa zasada - im bliżej bramki przeciwnika, tym lepiej
- jeżeli możesz, odcinaj przeciwnikowi drogę do swojej bramki
- staraj się nie odcinać sobie możliwości ataku
- staraj się uniemożliwić przeciwnikowi wykonywanie długich ruchów
- nie powtarzaj zawsze tych samych zachowań, zaskakuj gracza
Zaproponowana na podstawie tych przesłanek heurystyczna funkcja oceniająca ruch wygląda następująco:
- jeżeli ruch prowadzi do zdobycia bramki zwróć wysoką wartość dodatnią (10000)
- jeżeli ruch prowadzi do utraty bramki zwróć niską wartość ujemną (-10000)
- w przeciwnym przypadku zwróć wartość będącą sumą:
- oceny odległości od bramki, opisanej wcześniej, przemnożonej przez 100
- wartości 50, jeżeli z osiągniętej pozycji przeciwnik nie może wykonać ruchu dłuższego niż 1
- długości ruchu, jeżeli końcowa pozycja znajduje się na połowie przeciwnika
Zastosowany algorytm sprowadza się więc do wyboru posunięcia, którego ocena jest najwyższa. W przypadku, gdy kilka ruchów ocenianych jest tak samo, jeden z nich wybierany jest losowo (jest to szczególnie ważne w początkowym etapie gry).
Napisany applet został umieszczony na stronie internetowej, w celu rozpowszechnienia go do testów i zebrania informacji zwrotnej od testujących. Testującym pozostawiono możliwość wyboru algorytmu ("łatwy" - przeszukiwanie dla głębokości 1, "trudny" - dla głębokości 2). Jak napisano wcześniej, testowanie programu na poziomie "trudnym" jest uciążliwe ze względu na możliwy długi czas reakcji.
Stosując "łatwą" wersję algorytmu pokonanie programu jest możliwe, jakkolwiek nietrywialne i wymagające od gracza skupienia i dokładnej analizy sytuacji na boisku. Ze względu na wprowadzenie losowego wyboru równo ocenianych ruchów niemożliwa jest gra z programem "na pamięć". Można śmiało stwierdzić, że program realizuje cele projektu - bilans wyników meczów w przypadku każdego testującego był korzystny dla gracza komputerowego. Co więcej - wszyscy testujący wypowiadali się pozytywnie o poziomie rozgrywki. Należy zwrócić uwagę, że wpływ na częstość zwycięstw ma to, która ze stron rozgrywki wykonywała pierwszy ruch - łatwiej wygrać z komputerem rozpoczynając mecz.
W przypadku "trudnej" wersji rozgrywki otrzymano tylko jedną wiadomość o przegranej komputera. Należy jednak wziąć pod uwagę to, że mecze na tym poziomie często były przerywane ze względu na brak cierpliwości testujących (również autora programu).
Nie można było przeprowadzić konfrontacji napisanego programu z dostępną w internecie grą Inteligentna Piłka autorstwa Damiana Pasternaka ze względu na różniący te gry rozmiar boiska. Jednak po przegraniu serii partii z oboma programami, autor ośmiela się twierdzić, iż jego algorytm jest nie mniej wymagający (jakkolwiek jest to jego subiektywna opinia).
Poniższe screeny przedstawiają kilka przykładowych typowych przebiegów rozgrywki przy przeszukiwaniu do głębokości 1.
Bramka górna to bramka atakowana przez komputer.
 |  |
Zastosowany algorytm próbuje odciąć przeciwnikowi drogę do swojej bramki. Jak widać, niekiedy skutecznie mu się to udaje.
 |
 |
 |
| Typowa, szybka wygrana komputera w przypadku nieuważnej gry przeciwnika. | Zakończony golem, bardzo długi atak z kontry. Komputer z łatwością wychwytuje długie sekwencje ruchów często niewidoczne dla oka niewprawionego gracza. | Oczywiście z komputerem można wygrać. Wygrana po długiej walce smakuje najlepiej. |
Poniżej znajduje się napisany applet. Jeżeli w czasie gry przestanie reagować - poczekaj, myśli. Prawdopodobnie po chwili zaskoczy Cię niespodziewanym ruchem.
Miłej gry!
Planuje się dalszy rowój appletu. Aktualną wersją można znaleźć na stronie autora programu.
- Raport z projektu wykonanego przez Bartosza Tarnowskiego.
- Strona domowa Damiana Pasternaka, autora programu "Inteligentna Piłka".
- Opis algorytmu minimax.
- Środowisko programistyczne NetBeans.