Wrocław 19 czerwca 2001

Krzysztof Piotrowski

Dokumentacja do projektu Reversi
na pracownię ze Sztucznej Inteligencji

1 Wstęp

1.1 Obiekt badań

Przedmiotem mojego projektu jest gra logiczna Reversi, zwana też Othello.
Jest to gra dla dwóch graczy na planszy o 64. polach (8x8) z pionkami (po jednej stronie czarnymi, po drugiej białymi). Gracze stawiają na przemian pionki na wolnych polach planszy oflankowując pionki przeciwnika z jednej strony nowo postawionym pionkiem i z drugiej istniejącym(i) już na planszy w linii poziomej, pionowej lub na ukos. Oflankowane pionki przeciwnika są przewracane na druga stronę (zmieniają kolor na kolor gracza).
Celem gry jest zdobycie jak największej liczby pionków swojego koloru.

1.2 Strategie

Znanych jest kilka strategii gry w Reversi. Pozwolę sobie przytoczyć kilka opisywanych przez Francuską Federację Othello (FFO):

  1. strategia maksymalna (zachłanna) - gracze w każdym ruchu starają się zdobyć jak najwięcej pionków przeciwnika. Jest to strategia początkujących graczy.
  2. strategia pozycyjna - gracze mają ustalone z góry wartościowanie poszczególnych pól i starają się zawsze grać w polach o największej wartości np. narożniki czy krawędzie planszy, omijają natomiast pola o niższej wartości np. pola przylegle do narożników. Jest to strategia średnio zaawansowanych graczy, często urozmaicona elementami kontroli środka, wbijania klina czy pełzania po krawędziach.
  3. strategia kontroli mobilności - polega na kontrolowaniu ruchów przeciwnika, ograniczając liczbę możliwych jego posunięć w następnych kolejkach. W szczególności redukuje się liczbę możliwości zmuszając przeciwnika do gry tam gdzie nam zależy lub w ogóle nie pozwolić zrobić żadnego ruchu. Jest to niewątpliwie zaawansowana strategia.

2 Algorytmika i Implementacja

2.1 Algorytmika

Gra Reversi jest typową grą, w której można badać posunięcia przeciwnika w przód o kilka ruchów. Naturalne jest zatem zastosowanie algorytmu Minimax z cięciami alfa-beta. Algorytm ten można po krótce opisać tak:

function Minimax-AB(N: węzeł, Alfa, Beta)
  A=Alfa, B=Beta
  if N jest liściem lub maks. głębokość badania then
    return wartość funkcji heurystycznej dla tego węzła
  else
    if N jest węzłem typu MIN then
      for każdego węzła-potomka Ni węzła N do
        Val=Minimax-AB(Ni, A, B)
        B=min(B, Val)
  if B<=A then Wyjdź z pętli
      return B
  else
    if N jest wezłem typu MAX then
      for każdego węzła-potomka Ni węzła N do
        Val=Minimax-AB(Ni, A, B)
        A=max(A, Val)
        if A>=B then Wyjdź z pętli
      return A

Istotną sprawą jest określenie heurystycznej funkcji oceny w tymże algorytmie, gdyż algorytm Minimax jest dość ogólnym algorytmem (tak jak np. algorytm symulowanego wyżarzania). Funkcja oceny opisuje stan planszy biorąc pod uwagę elementy takie jak:

Można wyrazić ją wzorem:

gdzie b jest tablicą z aktualnym stanem gry:

    1, gdy na pozycji [i, j] znajduje się własny pionek
b[i, j] =   0, gdy na pozycji [i, j] nie znajduje się żaden pionek
  -1, gdy na pozycji [i, j] znajduje się pionek przeciwnika

w jest tablicą wag dla pól z ustalonymi wartościami jak w tabelce:

a b d d d d b a
b c e e e e c b
d e f f f f e d
d e f f f f e d
d e f f f f e d
d e f f f f e d
b c e e e e c b
a b d d d d b a

Powyższe pogrupowanie jest można opisać:

a Pola narożne - najbardziej korzystne
b Pola krawędziowe przynarożne - niezbyt korzystne
c Pola przynarożne - najbardziej niekorzystne
d Pola krawędziowe - korzystne
e Pola przykrawędziowe - niekorzystne
f Pola środkowe - neutralne

Kolejnym elementem wzoru jest element mobilności:
c - liczba możliwych ruchów
v - waga powyższego testu

Gdy v=0 wtedy wyłączony jest test mobilności. Gdy współczynniki b[i, j]=1 wtedy nie brane są pod uwagę pozycje pionków, wówczas mamy do czynienia ze strategią maksymalną.
Znajdowanie odpowiednich wartości powyższych współczynników można traktować jak pewien problem optymalizacyjny. Możliwe jest zatem zastosowanie metody metaheurystycznej takiej jak algorytm genetyczny. W programie zastosowano pewnego rodzaju algorytm genetyczny, który działa w ten sposób:

  1. Dla danych n funkcji oceny dokonaj kopii ich z pewną modyfikacją ich współczynników, tworząc kolejne n funkcji. Wyzeruj współczynniki skuteczności wszystkich funkcji.
  2. Dokonaj względnego porównania tych 2n funkcji poprzez rozgrywki każdy z każdym zapamiętując rezultaty gry. Gdy dana funkcja zwycięża zwiększ jej współczynnik skuteczności, gdy przegrywa zmniejsz. W sytuacji remisowej nic nie zmieniaj.
  3. Posortuj funkcje według współczynników skuteczności.
  4. Do dalszej analizy zostaw n najlepszych funkcji a pozostałe funkcje odrzuć.
  5. Powróć do punktu 1.

Algorytm ten może działać w pętli wiele razy. Efektem tego będzie zbiór nowych n funkcji oceny o prawdopodobnie lepszej skuteczności.

2.2 Implementacja

Program został zaimplementowany w Delphi 5.0. Został zaprogramowany algorytm Minimax z cięciami alfa-beta jak i algorytm poszukujący dobrych funkcji oceny dla algorytmu Minimax jako modyfikacja algorytmu genetycznego.
Możliwości programu:

3. Testy

3.1 Testy zewnętrzne

Pierwsze testy, które wykonałem polegały na wielu seriach rozgrywek człowiek-komputer. Celem tych testów było wstępne określenie wartości współczynników funkcji oceny a także wychwycenie błędów programu. Zmiany polegały głównie na dużych zmianach wartości współczynników aby stwierdzić ich istotność. Już czwarta modyfikacja funkcji oceny pozwoliła na uzyskanie około 70% skuteczności. Wartości współczynników, które uzyskałem otrzymały wartości:

Współczynnik a b c d e f v
Wartość 60 -30 -40 25 -25 1 5

Kolejnym etapem było porównanie skuteczności pomiędzy innymi programami.
Najlepsze wyniki program uzyskał w starciu z programem Othello, Alexandra Espina. Na 30 partii Reversi wygrała 12 razy i raz zremisowała. Jednak nie jest to szczyt osiągnięć gdyż gra ta nie należy do zbyt dobrych.
Najgorzej program wypadł w porównaniu z programem Wzebra, Gunnara Anderssona i Larsa Ivanssona. Na 25 rozgrywek tylko 2 były wygrane. Jednak program ten jest uznany w świecie za najlepszą grę a ja sam rzadko kiedy z nim wygrywam.

3.2 Testy wewnętrzne

Program jest dostosowany do gry z samym sobą a poprzez wbudowaną losowość jest w stanie dokonywać wielu starć z różnymi funkcjami oceny. Losowość jest określana poprzez zaburzenie funkcji oceny. W ten sposób niektóre ruchy, które byłyby odrzucone, są brane pod uwagę. Ich ocena znacznie nie odbiega od oceny ruchów potencjalnie najlepszych, mamy jednak pewien niedeterminizm czyli wiele różnych partii przy tych samych współczynnikach. Poprzez opisany wcześniej algorytm genetyczny program jest w stanie modyfikować swoje współczynniki tak by grać coraz lepiej. Dokonałem wielu testów porównując ze sobą różne funkcje. Zostało wykonanych około 3 tys. porównań funkcji by znaleźć odpowiednie wartości współczynników. Przykładowe wyniki jakie uzyskałem:

Współczynnik a b c d e f v
Wartość pierwotna 60 -30 -40 25 -25 1 5
Po 20 pokoleniach testów 52.66 -25.42 -45.53 29.01 -25.24 0.99 5.10
Po 50 pokoleniach testów 53.15 -32.97 -43.33 24.61 -26.26 1.04 4.10

Skuteczność programu nieco wzrosła co zauważyłem podczas samodzielnych testów. Program zaczął stosować pewne taktyki, które nie zostały jawnie zaimplementowane. Zauważyłem też poprawę w stosunku do gry Othello, z którą Reversi wygrało 11 razy na 20 rozgrywek. Nie zauważyłem natomiast poprawy w stosunku do Wzebry. Tam jedna gra była wygrana na rozegranych 15.
Ostatecznie skuteczność można określić:

Gra z przeciwnikiem człowiek Othello WZebra
Pierwotna funkcja oceny 27/40=67.5% 12/30=40% 2/25=8%
Wyuczona funkcja oceny 23/30=76.7% 11/20=55% 1/15=6.6%

4 Wnioski

Podczas pracy nad projektem, poznałem pewne istotne techniki sztucznej inteligencji takich jak algorytmy przeszukujące - Minimax z cięciami alfa-beta, algorytmy genetyczne, poznałem również tajniki procesu uczenia się. Miałem również możliwość próby przelania do komputera mojej wiedzy na temat gry Reversi, co było pierwszym moim osiągnięciem w tej dziedzinie. Spędziłem też wiele godzin przy komputerze gdy testowałem program. Jednak istotne są pewne spostrzeżenia co do co sposobu rozumowania programu. Udało mi się zauważyć pewne różnice w sposobie myślenia człowieka a analizowania problemów przez program. Człowiek kieruje się często intuicją przy pewnych zagadnieniach np. grach logicznych, nie zawsze kieruje się ścisłą logiką. Programy natomiast stosują naturalne dla siebie sposoby logicznej analizy problemu. Postrzeganie i kojarzenie faktów przez człowieka jest w dużej mierze niezbadane a na pewno nieprzewidywalne. Algorytmy komputerowe są ściśle określone, jedynie sztucznie dodana losowość jest w stanie dać poczucie niedeterminizmu. Nie wszystkie jednak problemy łatwo jest zaimplementować, dlatego komputer jest w stanie nadrobić tą ułomność poprzez niezawodną pamięć oraz szybkość i dużą ilość obliczeń.
Podczas testów zauważyłem jednak, że program stosował pewne taktyki, które nie były zaimplementowane wprost. To pokazuje, że im bardziej złożony model obliczeniowy, tym większa szansa na to, że pojawią się nowe elementy, zatem programy takie są w stanie adaptować się w nieprzewidywalnych sytuacjach.
Pytanie zatem brzmi. Czy ludzki umysł to wielki komputer? Z całą pewnością tak, ale zbyt złożony dla dzisiejszej nauki.

Valid HTML 4.01!