• Dwóch graczy
• Gra o sumie zerowej (+1 dla mnie = -1 dla przeciwnika)
• Przeglądanie (całego) drzewa gry
• Minimalizowanie maksymalnych strat / maksymalizowanie minimalnego zysku

Przykład: kółko i krzyżyk (powyżej)

• Aktualny stan planszy znajduje się w korzeniu (w pierwszym rzędzie na samej górze)
• Możliwe wartości gry: +1 (X wygrywa), 0 (remis), -1 (O wygrywa)
• Trzy możliwe ruchy dla X zaznaczone są w drugim rzędzie od góry
  • Każdy ruch otagowany jest minimalnym spodziewanym zyskiem na koniec gry po wyborze danej gałęzi
  • Pierwsze dwa ruchy otagowane są wartością -1 (czyli X zdobędzie min. -1, co w tym przypadku oznacza, że może przegrać); trzeci ruch oznaczony jest wartością 0 (czyli X zdobędzie minimum 0 = minimum będzie remis, ale X nie przegra)
  • Wybierając ruch dla X/siebie zawsze wybieramy największą wartość (maksymalizujemy minimalny zysk)
• Na każdy z trzech dostępnych ruchów, O może odpowiedzieć na dwa sposoby. Każdą z tych odpowiedzi widać w kolejnym poziomie drzewa (trzeci wiersz od góry)
  • Wybierając ruch dla O/przeciwnika zawsze wybieramy najmniejszą wartość (w związku z tym, że jest to gra o sumie zerowej, najmniejsza wartość jest najgorszą opcją dla nas, ale równocześnie najlepszą dla przeciwnika)
  • Intuicja jest prosta: zakładamy, że przeciwnik wybierze najlepszą dla siebie opcję
• Oczywiście, aby poznać wartości musimy rozwinąć drzewo do końca (ponieważ dopiero na końcu możemy ustalić czy wygrywa X/O czy jest remis)

Analogicznie działa to w przypadku szerszego zakresu wartości (na poziomach parzystych wybieramy ruch dla siebie = wybieramy wartość MAX; na poziomach nieparzystych wybieramy ruch dla przeciwnika = wybieramy wartość MIN):

• Zastosowanie heurystyk – możliwość oszacowania spodziewanej wartości dla każdego ruchu
• Iterative deepening – przy zastosowaniu heurystyk, można obciąć drzewo do określonego poziomu i przeszukiwać tak ograniczone drzewo
• Alpha-Beta prunning – obcinanie gałęzi, które nie zmienią wyniku
  • Alpha: dla węzłów MAX; Beta: dla węzłów MIN
  • Przykład: aktualnie najlepszy ruch (korzeń drzewa; wybierający najlepszą wartość z pierwszego poziomu) to 3.
    Będąc w węźle oznaczonym jako B będziemy wybierać najlepszy ruch dla przeciwnika (= wybierać najniższą wartość).
    Wiemy już, że w jednym poddrzewie węzła B wyliczona została wartość 0.
    Oznacza to, że wartością ustaloną dla B będzie 0 albo mniej (ponieważ tutaj minimalizujemy)
    Oznacza to, że cokolwiek nie wyliczymy w drugim poddrzewie i tak nie zmieni to wartości 3 w korzeniu drzewa, dlatego możemy przerwać liczenie (co oznaczono jako alpha cut)
    

• Klasyczne silniki szachowe “od zawsze” stosują zwykły Minimax z odpowiednimi usprawnieniami (heurystyki, obcinanie drzewa, ograniczanie głębokości, itd) – od czasu walki pomiędzy Kasparowem i Deep Blue w 1997 roku, algorytmy stawały się lepsze w szachach głównie dzięki zwiększającej się mocy obliczeniowej (same algorytmy pozostały bez większych zmian)
• Dopiero w ostatnich latach pojawiła się odmiana – algorytmy bazujące na sieciach neuronowych, których styl gry jest zupełnie inny niż klasycznych silników (komercyjny AlphaZero i wzorujący się na nim open source'owy Leela Chess Zero)
• Ciekawe źródła dla zainteresowanych:
  • Film How do chess engines work? – ogólne wprowadzenie w podstawowe metody (np. alfa-beta prunning czy podstawy uczenia maszynowego), pokazanie jak działają klasyczne algorytmy i porównanie ich z nowym podejściem bazującym na sieciach neuronowych; jest tutaj też pokazany przykładowy meczu pomiędzy klasycznym silnikiem (Stockfish), a Leela Chess Zero
  • Książka Garri'ego Kasparowa “Ostatni bastion umysłu” – opowieść o meczu z Deep Blue z perspektywy Kasparowa. Lektura nie wymaga doświadczenia z grą w szachy – autor bardziej skupia się na ukazaniu, że przede wszystkim była to wojna psychologiczna z IBM. Przy okazji w książce pojawia się dużo przemyśleń Kasparowa odnośnie współpracy człowieka z maszynami i rozwoju sztucznej inteligencji.

W ramach dzisiejszych zajęć implementujemy algorytm MiniMax dla gry w kółko i krzyżyk. Zadania można realizować w wybrany sposób:

• w p5js
  • język Processing (znany z drugich zajęć, na których implementowaliśmy poruszanie się sposobem Reynoldsa)
  • brak ograniczeń czasowych
  • można zdobyć do 7 EXP
• w CodinGame
  • w dowolnym języku (który jest wspierany przez platformę)
  • są krótkie timeouty, więc zanim uda się coś zagrać potrzeba wprowadzić optymalizacje do MiniMax
  • można np. pierwszą wersję MiniMax zaimplementować w p5js, aby się upewnić “że działa”, a później przenieść się do CodinGame i wprowadzać optymalizacje
  • można zdobyć max punktów (9 EXP)
  • nie da się prezentować podstawowej wersji zadania (bot nie rozegra gry jeżeli będą się pojawiać timeouty; ocena musiałaby się opierać na dokładnej analizie kodu)

Sketch w p5js: https://editor.p5js.org/kkutt/sketches/SjxwlN9RQ

• Jest: obsługa grafiki i sprawdzania warunków zwycięstwa
• Jest: dummy player, który zawsze gra ostatnie wolne pole
• Do napisania funkcja aiMove()

Problem na CodinGame: Ultimate Tic-Tac-Toe

• W pierwszej lidze (Wood) – klasyczna gra w kółko i krzyżyk (to nas interesuje na zajęciach)
  W dalszych ligach – Ultimate Tic-Tac-Toe: każde pole jest osobną grą; wygrana w “małej” grze to zajęcie tego pola w “dużej” grze (polecam dla zainteresowanych jako ciekawe wyzwanie; niepunktowane)
• Limit czasu – zwykły MiniMax, który przeszukuje całe drzewo, nie zmieści się w timeoucie; pomysły na ulepszenia (bazując na pomysłach przedstawionych wyżej):
  • wprowadzenie heurystyk, np. poza wygraną/przegraną (+1/-1) oceniamy stany pośrednie na podstawie tego w ilu rzędach/kolumnach/przekątnych znajdują się już dwa elementy (ilość można pomnożyć np. przez +0.1/-0.1)
  • sztywne ograniczenie przeszukiwania, np. obcięcie drzewa przeszukiwania do konkretnej głębokości albo przerywanie przeszukiwania po określonym czasie (i wybieranie najlepszego rozwiązania z przeliczonych)
  • alpha-beta prunning

Zadania do realizacji:

• [5 EXP] Implementacja podstawowej wersji MiniMax (przeszukuje całe drzewo; nie powinien nigdy przegrywać!)
• [2 EXP] Implementacja wybranego ulepszenia (może być któreś z ulepszeń opisanych powyżej, a może być inne, wymyślone samodzielnie bądź znalezione gdzieś w literaturze)
• [2 EXP] Przejście do brązowej ligi w CodinGame (zaliczenie tego punktu automatycznie zalicza powyższe dwa)