MONTE CARLO TREE SEARCH OCH MINIMAX : En jämförelse i tidseffektivitet i ett matcha-3-spel

Sammanfattning: I arbetet implementerades två algoritmer som utvärderades genom att spela ett matcha-3-spel mot varandra. Den första algoritmen var Minimax som väljer sina drag genom att evaluera de möjliga dragen från ett tillstånd. För att inte sökrymden ska bli för stor begränsas algoritmen med ett sökdjup. Den andra algoritmen var en MCTS som utför flera simuleringar där den utför slumpmässiga drag till ett spelslut för att få en uppskattning över resultatet från de olika dragen. Spelet som de utvärderas på är av typen matcha-3-battle. Flera experiment utfördes sedan på de två algoritmerna, där de spelade flera matcher motvarandra på olika stora bräden, sökdjup och utforskningskonstanter. Testerna visade att i denna implementation var Minimax överlägsen i de fall. När sökrymden blev större presterade MCTS bättre än i mindre rymder, men lyckades aldrig nå en majoritet av vinster.