===== MiniMax =====

==== 1. Wprowadzenie do MiniMax ====

  * 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

{{tictactoe-minimax.jpg?direct&600|}} \\ 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): \\ {{minimax-abstract.png?direct&600|}}

==== 2. Ulepszenia MiniMax ====

  * 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//) \\ {{tictactoe-alphabeta.png?direct&600|}}

==== 3. Szachy? ====

  * 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 [[wp>Deep Blue (chess computer)|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 [[wp>AlphaZero|AlphaZero]] i wzorujący się na nim open source'owy [[wp>Leela_Chess_Zero|Leela Chess Zero]])
  * Ciekawe źródła dla zainteresowanych:
    * Film [[https://www.youtube.com/watch?v=P0jd8AHwjXw|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 "[[https://lubimyczytac.pl/ksiazka/4956697/ostatni-bastion-umyslu|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.

==== 4. Zadania do realizacji ====

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**: [[https://www.codingame.com/multiplayer/bot-programming/tic-tac-toe|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)