Każdy zna grę kółko i krzyżyk, zapewne każdy grał także w nią. Gra na 3 (czyli plansza 3x3) jest stosunkowo łatwa. Gdy gracz zaczyna pierwszy lub drugi to zawsze jest strategia nie przegrywająca. Napisanie takiego algorytmu, który nie da się pokonać jest łatwe (chyba, że ktoś chce zrobić tablice do rozpatrzenia wszystkich 3^9 przypadków).
Kółko i krzyżyk na 5
Też pewnie wiele osób grało w kółko i krzyżyk na, ale w wersji na 5 (nazwa chyba jest Gomoku). Na nieszczęście wymyślono strategię zawsze wygrywającą dla pierwszego więc zabawa mniej fajna jest, ale nie każdy ma komputer w głowie więc, aż tak źle nie jest. Trudniej jednak grać samemu w tą grę, także wymyślenie AI dla komputera nie jest już tak łatwe.
Zarys
W tym artykule zostanie opisany sposób na AI wymyśloną przez mnie. Nie jest ona doskonała, nie przewiduje ruchów, ani nie analizuje poprzednich, ale stara się wymyśleć jak najlepsze rozwiązania dal aktualnego stanu plansz (jednak nie przewiduje konsekwencji tego działania). Metoda polega na przeanalizowaniu sytuacji na planszy i każdemu polu przypisaniu pewnej liczby. Następnie komputer wybiera pole o największej liczbie i w nie wstawia swój znaczek, jeśli jest kilka pól to losuje jedno. To tak w skrócie. Artykuł opisuje wszystko w języku naturalnym, kod gry i modułu, który jest używany przez nią znajduje się tutaj.
Jak reprezentować kółko/krzyżyk na planszy
W pamięci komputera musimy przechowywać planszę wraz z aktualnym stanem planszy. Można to jednak zrobić na wiele sposobów, np. ustalić, że 0-puste, 1-krzyżyk, 2-kółko, jest to sposób, ale czy dobry? Aby sprawdzić czy np. ktoś wygrał musimy zrobić masę if-ów, aby mieć pewność, że każde pole to 2 lub 1. Trochę niewygodne, ale nie tylko to jest jedyna wada, gdy już sprawdzamy czy mamy 4 krzyżyki obok siebie i jest wolne pole w linii z nimi, to jakby musiał wyglądać sposób szukania i sprawdzania czy są 4 takie pola oraz jedno wolne, a to wolne przecież nie musi być obok nich, ale pomiędzy nimi ( X X _ X X czy X _ X X X), ilość if-ów jest straszna. Można to inaczej zrobić. Zauważmy że podczas wyszukiwanie takich piątek czy czwórek z pustym polem nie jest ważna kolejność (tycz się czwórek), ważne jest, że są 4 krzyżyki i jedno pole puste, a jaka kombinacja jest to już mniej ważne, będziemy nad tym się zastanawiać jak już znajdziemy 4 krzyżyki u puste pole.
Ta sama sytuacja, tylko puste pole w innym miejscu znajduje się
Pomysł, który tutaj zostanie zaprezentowany został tak skonstruowany aby widząc pięć pól od razu dało się stwierdzić ile jest kółek, a ile krzyżyków (no i ile pustych pól). Niech puste pole będzie 0, kółko 1, a krzyżyk 6. Czemu tak? Krzyżyk może być większy niż 6, ale nie mniejszy. Otóż dodając 5 pól obok siebie dostaniemy pewną liczbę, która jednoznacznie będzie wskazywała jakie pola się znajdują, jak wszystkie będą kółkami, to dostaniemy maks 5, czyli nie uzyskamy krzyżyka, a i jedne krzyżyk jest już większy niż 5. Tutaj mamy tabelkę, która reprezentuje wszystkie możliwe kombinacje:
| 0 | 1 | 2 | 3 | 4 | 5 | |
| 0 | 0 | 6 | 12 | 18 | 24 | 30 |
| 1 | 1 | 7 | 13 | 19 | 25 | 31 |
| 2 | 2 | 8 | 14 | 20 | 26 | 32 |
| 3 | 3 | 9 | 15 | 21 | 27 | 33 |
| 4 | 4 | 10 | 16 | 22 | 28 | 34 |
| 5 | 5 | 11 | 17 | 23 | 29 | 35 |
Wiersze to ilość kółek, kolumny krzyżyków.
Jak widać, żadna liczba się nie powtarza, więc jednoznacznie określa ile jakich pól jest w linii. Na takiej reprezentacji będzie opierała się idea algorytmu.
Komputer zaczyna
Czasami zdarza się, że to komputer zaczyna ruch, wtedy sytuacja jest klarowna, wiele nie ryzykuje. Jednak chcielibyśmy, aby komputer nie stawiał swego znaczka przy krawędzie, więc ustalmy, że komputer losuje swoje pole, ale nie może być ono w odległości nie mniejszej niż 5 pól (chyba, że sama plansza jest mała).
SI potrzebuje bliskości
Chcielibyśmy, aby komputer nie losował swojej pozycji dowolnie na planszy, ale żeby wyglądało, że stara się trzymać blisko przeciwnika. Dlatego na początku swojej tury wszystkim polom, które mają jakiegoś sąsiada (także na przekątnej) ustawiamy priorytet 1. Spowoduje to, że komputer będzie się "kleił" do gry, aczkolwiek może się później zdarzyć, że postawi swój znaczek w miejscu w które nie sąsiaduje z nikim.
Rozłożenie jedynek, aby komputer "się "kleił" do gry. Ruch X-a
Dążenie do zwycięstwa
Teraz dochodzimy do głównej części algorytmu. Mamy już wiedzę jak przechowywać dane o mapie, jak komputer ma zaczynać ruch i jak trzymać się blisko rozgrywki, teraz trzeba zrobić tak aby komputer odczuwał potrzebę wygrania i potrzebę nie przegania, innymi słowy aby dawał tak swój znaczek aby być bliżej celu oraz aby tak aby przeciwnik nie mógł zdobyć piątki lub czwórki. Cała idea opiera się na analizowaniu pięciu sąsiadujących pól w linii w poziomie, pionie i obu ukosach. Otóż czego będziemy poszukiwać w tych piątkach? Będziemy szukać czy aby nie ma dwóch naszych pól i 3 pustych pól w piątce, 3 naszych i dwóch pustych oraz 4 naszych i 1 pustych pól w tejże piątce. Także czy przeciwnik nie ma takiej kombinacji dla swoich pól. Co się stanie gdy są inne kombinacje? Nic, ponieważ jeśli my mamy swoje znaczki i przeciwnik też ma w takiej jednej piątce to nikt w niej nie może wygrać. Piątki wybieramy po kolei przesuwając się o jedno pole w poziomie, pionie czy w ukosie (zależy co badamy teraz). Co się stanie gdy znajdziemy interesujące nas kombinacje? Puste pola w piątce w której znaleźliśmy kombinacje zwiększamy o jakiś priorytet. Priorytet zależy od kombinacji, najwyższa jest gdy mamy 4 znaczki i jedno puste, bo daje nam zwycięstwo, następnie czwórka przeciwnika, aby go zablokować, potem nasza trójka bo jak do niej dodamy coś to mamy szansę aby mieć czwórkę. Priorytety muszą być odpowiednio dobrane, np. nasza czwórka powinna mieć tak wysoki aby nic innego nie mogło się z nią równać.
Dążenie do zwycięstwa
Przykładowe sytuacje
Rozważmy sytuacje powyżej. Na wstępie warto powiedzieć, że są one w poziomie, ale równie dobrze mogą być w pionie, na ukosy, tu jest tylko dla wygody. Najpierw te z niebieską numeracją. Punkt I to banalna sytuacja, gdy jest jeden niebieski i 4 puste widać, że nie ma problemu, dodatkowo jak się przesuniemy i jedno w prawo to też będziemy mieli dobrą piątkę, takie zachowanie algorytmu powoduje, że pola będące bliżej sytuacji będą miały wyższe priorytety bo częściej będą zwiększane. Sytuacja II jest podobna do pierwszej ale w rozpatrywanej piątce jest także kółko co powoduje, że piątka jest mało atrakcyjna, ale jeśli pole po lewej będzie wolne to piątka przesunięta o jedno w lewo będzie już dobra. Sytuacja III przedstawia sytuację, gdy w piątce są dwa krzyżyki, innym polom zwiększamy priorytet o pewną liczbę. Zauważmy, że jak przesuniemy się o jedno w prawo to dostaniemy piątką z jednym krzyżykiem i też zwiększymy priorytety, czyli najwyższy priorytet będą miały pola będące obok istniejących krzyżyków, bo też dają największą szansę. Jeśli na lewo od pierwszego krzyżyka znajdzie się kółko to warto zauważyć, że największy priorytet zdobędzie pole będące na prawo od prawego krzyżyka co jest lepszą sytuacją. W sytuacjach IV i V widać gdzie komputer powinien postawić swój znaczek aby zdobyć czwórkę lub też wygrać całą grę.
Jak łatwo się nie dać
Przejdźmy teraz do sekcji czerwonej, są w niej sytuacje gdy komputer musi się bronić. Sytuacja I przedstawia sytuacje gdy nie ma sensu stawiać krzyżyka, i koputer go nie postawi bo nie ma szans aby mieć piątkę krzyżyków. Może postawić, jeśli obok tych kółek będą inne kółka tak że zrobi się sytuacja niebezpieczna. Sytuacja II pokazuje jak krzyżyk blokuje zdobycie piątka kółek z lewej strony. Dodatkowo najwięcej podniesiony zostanie priorytet pola będącego na dwa od kółek w prawo co uniemożliwi zdobycie piątki a i mniej miejsca na taką piątkę zostaje po prawej. Oczywiście należy pamiętać, że jest więcej znaczków na planszy i masę piątek, więc znajdzie się pole mające wyższy priorytet oraz także są inne piątki które mogą zwiększyć priorytet pól i komputer gdzie indziej postawi krzyżyk. Sytuacja III pokazuje co by się działo gdyby były 3 kółka. Te 3 kółka uczestniczą w dwóch piątkach, ale tylko puste pole od nich na prawo uczestniczy w obu, to z lewej tylko w jednym dlatego komputer postawi krzyżyk na prawo bo tam priorytet więcej się powiększy, jest to nawet logiczne posunięcie bo dając po lewej stronie ciągle dajemy szansę przeciwnikowi na zdobycie piątki. Sytuacja IV pokazuję tę sytuację gdy są 4 kółka, komputer musi postawić na prawo od nich krzyżyk (chyba, że ma własną czwórkę). Dodatkowo priorytet tego pole może zwiększyć sytuacje, że w piątce jest jest trójka i dwójka (jeśli po prawej są jeszcze wolne miejsca). Sytuacja V jest odwrotna do I tylko, że w niej komputer już nie musi blokować kółek bo ma pewność że i tak piątki kółko nie zdobędzie.
Koniec
To już koniec artykułu. Przedstawiał on zagadnienie w sposób teoretyczny bez krzty kodu. Grę, która wykorzystuje powyższy algorytm oraz kod znajduje się tutaj.
Artykuł napisał Force
Pochodzi ze strony http://fp.unit1.pl.
Przedruk dokonany za zgodą autora. Dalsze kopiowanie zabronione.
Źródło: Force