# Monte Carlo Tree Search Bot for Ultimate Tic Tac Toe

## Popis algoritmu

Monte Carlo Tree Search (MCTS) je heuristický vyhľadávaci algoritmus. Funguje na princípe expanzii stromov možných
pohybov, ktorý postupne expanduje a následným vyhodnocovaním náhodných priebehov hry z daného stavu ohodnocuje.
Každý uzol stromu predstavuje stav hry, a je spojený hranou s ďaľšími uzlami, kde hrana je valídny ťah v hre ktorý k tomuto stavu vedie.

Delí sa na štyri fázy:
1. Výber - niektorý z listov stromu je vybraný na základe danej metriky (v našom prípade Upper Confidence bounds applied to Trees).
2. Expanzia - daný list je expandovaný. Sú k nemu pripojené listy, jeden pre každý validný ťah z daného stavu.
3. Simulácia - Hra je simulovaná až po koniec náhodnými ťahmi. 
    Je možné voliť rôzne prístupy, najčastejšie sa ťahy vyberajú vždy s uniformným rozdelním.
4. Spätná propagácia - výsledok hry je propagovaný späť do koreňa stromu, uzly si držia informáciu o počte navštívení a počte víťazstiev.

Tento proces prebieha opakovane, podľa alokovaného času. Následne je vybraný najúspešnejší uzol / ťah. 
Koreň stromu sa potom posunie do tohoto uzlu.

## Návod na instalaci a spuštění

### Pre použitie na codingame.com
Webová stránka očakáva ako vstup len jediný súbor / kód nakopírovaný do rozhrania webovej stránky.

Je preto potrebné sekvenčne nakopírovať súbory State.kt, Moves.kt, MonteCarloTreeUtils.kt, MonteCarloBot.kt a Main.kt do
rozhrania stránky a vymazať prebytočné importy.

### Pre hranie proti botovi
Je potrebné mať nainštalovanú javu.
Príkazy očakávajú workdir nastavený na vrchný adresár projektu.

Pre skompilovanie projektu: `./gradlew clean jar`
Pre spustenie : `java -jar build/libs/uttt-1.0-SNAPSHOT.jar`


## Vyhodnotenie
Hrubé čísla botov hrajúcich proti sebe v priloženej prezentácii.

- Plne funkčná.
- Dosahuje 131. miesta v zlatej (2. najvyššej) lige, odpovedá top 10 % najlepších riešení.
- Simuluje 12000 hier v prvý ťah,
- v nasledovné ťahy je to 2000-3000 hier, rastie ako sa blíži hra ku koncu.
- Dokáže poraziť všetkých benchmark botov až na posledného.

- Príklad hry na codingame.com za modrého hráča: https://www.codingame.com/replay/453826731 
- Príklad hry na codingame.com za žltého hráča: https://www.codingame.com/share-replay/455335244

## Dokumentácia

Hlbšia dokumentácia v samotných súboroch

### Popis súborov ./src/main/kotlin/muni.fi

- BotComparison.kt - Jednoduchý framework umožnujúci porovnávanie rôznych iterácii botov proti sebe

- HeuristicMCBot.kt - Rozšírenie základného bota o drobnú heuristiku

- Main.kt - Rozhranie pre codingame.com

- MonteCarloBot.kt - Hlavná implementácia základného bota, obsahuje celý algoritmus MCTS

- MonteCarloTreeUtils.kt - Pomocné triedy a funkcie pre vytváranie stromu pre algoritmus MCTS

- Moves.kt - Triedy a funkcie pre spracovávanie a vyhodnocovanie možných ťahov pre dané stavy hry

- PlayerVsBot.kt - Trieda ktorá umožňuje človeku hrať proti základnému botu

- RandomBot.kt - Bot ktorý vždy volí náhodný ťah

- State.kt - Trieda na reprezentovanie stavov hry, obsahuje hlavnú časť logiky hry

- StatePrinter.kt - Trieda na vypisovanie stavu hry do textovej podoby 

### Popis súborov ./src/test/kotlin/muni.fi

- BotEvaluation.kt - Nejde o skutočné testy, ale o spustiteľný interface,
    ktorý za pomoci funkcie z BotComparison.kt testuje rôzne iterácie botov proti sebe. Priebeh trvá veľmi dlho.
    
- GameTests.kt - Testuje náhodné hrania hry, kontroluje korektnosť generovania možných ťahov a logiku ich spracovávania,
  meria čas za aký sa odohrá určité množstvo hier.

- MonteCarloTests.kt - Len hrubý test funkcionality MCTS, zaručuje že dokáže odohrať hru.

- MovesTests.kt - Testy na vyhodnocovanie logiky ťahov, či sa správne vyhodnocujú valídne ťahy pre dané stay a podobne.

- StateTests.kt - Testy na vyhodnocovanie logiky stavov, či sa správne vytvárajú nové stavy na základe zahraných ťahov.