Kółko i krzyżyk z buczeniem jest grą, zbliżoną do klasycznej wersji, zawierającą jednak kilka utrudnień. Gra rozgrywa się na planszy 9x9, a ruchy przeciwnika nie są widoczne. W momencie kiedy jeden z graczy, chce postawić swój symbol na polu, zajetym już przez przeciwnika, zostaje o tym poinformowany i traci ruch. Stąd bierze się nazwa “buczenie”, gdyż program powinien wydawać w takim przypadku sygnał, świadczący o zajętości wskazywanego pola. W swojej grze, zamiast buczenia, ujawniam, po prostu graczowi symbol przeciwnika na planszy. Wygrywa gracz, który swoim symbolem wypełni wiesz albo kolumnę lub jedną z przekątnych.

Do realizacji użyłem algorytmu MiniMax dla gier. Węzłami w drzewie algorytmu są plansze 9x9 składające się z 81 pól. Ze względu na rozmiary i co za tym idzię chęć uzyskania rozsądnego czasu gry, ze strony komputera, algorytm dokonuje przeszukiwania drzewa do glębokości 3.

Najtrudniejszą częścią zadania było opracowanie dobrej funkcji oceny heurystycznej. Funkcja oceny pobiera planszę 9x9 i zwraca liczbę całkowitą będącą próbą oceny na ile sytuacja przedstawiona na planszy jest korzystna. Im mniejsza liczba, tym większa korzyść dla gracza-człowieka, im większa – tym sytuacja korzystniejsza jest dla komputera.

Funkcję heurystyczną starałem się dobrać drogą pewnych spostrzeżeń i eksperymentów. Najpierw próbując rozważać grę w kółko i krzyżyk bez buczenia, ale na planszy 9x9. Gra opiera się na kilku prostych spostrzeżeniach:

• w obronie: blokowanie przeciwnikowi kolumny lub wiersza, powinno odbywać się w taki sposób, aby zajmować do tej pory wolny wiersz lub wolną kolumnę,
• w ataku: zajmując wolny wiersz lub kolumnę, warto jednocześnie blokować zajmowaną przez przez przeciwnika kolumnę lub wiersz,
• symbole postawione na przekątnej są najcenniejsze, warto zacząć grę od zajęcia pola na środku planszy

Program stosując te heurystyki przy grze z jawnymi planszami, zawsze w najgorszym przypadku (przy rozsądnej grze człowieka) doprowadzał do remisu.

Wariant z ukrytą planszą.

Kiedy komputer nie widzi ruchów przeciwnika ma bardzo ograniczoną wiedzę na temat faktycznego stanu gry. Próbując zmaksymalizować szansę sukcesu komputera, oparłem się na kilku spostrzeżeniach, które miały na celu uzupełnić, te uwagi, które wymieniłem w wariancie z planszą jawną.

• program powinien bardziej skoncentrować się na obronie, gdyż niepełna wiedza o stanie gry, łatwo może doprowadzić do porażki,
• im komputer odkrywa więcej symboli przeciwnika, tym bardziej powinien koncentrować się na ataku, czyli zajmowaniu pewnego wiersza, kolumny lub przekątnej.

Funkcja oceny.

Heurystyczna funkcja oceny, powstawała w skutek wielokrotnych prób gier z komputerem. Polegało to na obserwacji gry przeciwnika i wymuszaniu pewnych strategii, jakie komputer ma stosować. Dla znalezienia jak najlepszej funkcji, testowałem program również w przypadku, gdzie komputer nie widział (mojej) planszy przeciwnika, natomiast gracz-człowiek mógł obserwować ruchy komputera. Plansza 9x9 jest oceniania poprzez funkcję zwracającą liczbę całkowitą. Funkcja skonstruowana jest według następującej idei:

• za każdy wiersz, kolumnę i przekątną, która nie zawiera symboli przeciwnika, dolicza się liczbę punktów proporcjonalną do kwadratu liczby symboli komputera,
• za każdy wiersz, kolumnę i przekątną, która nie zawiera symboli komputera, odejmuje się liczbę punktów proporcjonalną do kwadratu liczby symboli komputera, powiększoną o pewną stałą,
• dla każdego wiersza, kolumny, przekątnej, która zawiera tylko symbole komputera dolicza się do wartości funkcji losową liczbę z pewnego niewielkiego przedziału,
• sytuacja, w której komputer jest na pozycji wygrywającej, gratyfikowana jest dużą liczbą punktów, aby ruch prowadzący do zwycięstwa miał najwyższy priorytet.

Dokładne określenie funkcji (podanie wszystkich wspołczynników proporcjonalności i stałych) wymagało wielu testów, polegających na grze z komputerem.

Rezultaty

Program, ze względu na niepełną wiedzę o stanie gry, utrudnia przetestowanie jakości rozgrywek ze strony komputera. Miarą umiejętności maszyny, mogą być wyniki dłuższych serii gier.

Ogólnie program wygrywa z początkującymi graczami. Bardziej doświadczeni w 90% przypadków doprowadzają do remisu. Wygrane z komputerem zdarzają się bardzo rzadko. Strategia polegająca na zmniejszającej się losowości ruchów w miarę trwania rozgrywki, utrudnia grę człowiekowi w znacznym stopniu.

Charakter gry uniemożliwia zaprogramowanie superprogramu, który będzie wygrywał z każdym większość rozgrywek. Jakość gry komputera oceniam jako dobrą.