I det här arbetet undersöks och jämförs två olika sökalgoritmer när de används för implementation av AI-spelare till brädspelet Pentago. De två algoritmerna som användes var alfa-betabeskärning och en nyare algoritm som kombinerar genetiska algoritmer och minimax, kallad genetisk minimax. Utvärderingen av resultaten visar att alfa-betabeskärning passar bättre vid implementation av en AI till Pentago än genetisk minimax. Alfa-betabeskärning med ytterligare optimeringar har potential att lämpa sig väldigt väl för implementation av spelare till Pentago. Ytterligare visar resultaten att genetisk minimax inte är en passande algoritm för AI till Pentago. För eventuella framtida arbeten föreslås ytterligare arbete och förbättringar på implementationen av alfa-betabeskärning. Genetisk minimax har potential att fungera bättre vid implementation av AI till andra brädspel. Därför föreslås även framtida arbeten av implementationer av genetisk minimax inom områden och spel som kan vara mer passande.

Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves.

The forefront of game playing Artificial Intelligence (AI) has for the better part of 21st century been using an algorithm called Alpha-Beta Pruning (Alpha-Beta). In 2017, DeepMind launched a new AI, based on the algorithm Monte Carlo Tree Search (MCTS), which defeated the former Alpha-Beta based chess AI champion Stockfish. This accomplishment fueled up more excitement and interest for using MCTS to develop more complex and better performing game playing AI.This paper aims to compare the strengths of MCTS and Alpha-Beta by allowing them to play against each other in a classic game with no available robust AI - the Fox Game.The results showed an evident victory for the Alpha-Beta AI. Therefore, Alpha-Beta is the better suited algorithm for developing a simple AI for the Fox Game. Further optimizations would enhance the performance of both algorithms but it is unclear which of the algorithms would benefit from it the most. / Framkanten av Artificiell Intelligens (AI) som spelar spel har i större delen av 2000-talet använt sig av en algorithm vid namn Alpha-Beta-beskärning (Alpha-Beta). Denna bedrift höjde intresset för att använda MCTS i syfte att utveckla mer komplexa och bättre spelande AI.Denna rapport har som mål att jämföra styrkor hos MCTS och Alpha-Beta genom att låta dem spela mot varandra i ett klassiskt spel utan någon tillgänglig AI - Rävspelet. Resultaten visade på en klar seger för Alpha-Beta AI:n. Därför är Alpha-Beta den bättre lämpade algoritmen för att skapa en simpel AI. Fler optimiseringar hade förbättrat spelstyrkan hos bägge algoritmerna med det är oklart vilken av algoritmerna som hade gynnat mest utav det. / Kandidatexjobb i elektroteknik 2022, KTH, Stockholm

Il existe des algorithmes en meilleur d'abord efficace pour la résolution des jeux déterministes à deux joueurs et à deux issues.Nous proposons un cadre formel pour la représentation de tels algorithmes en meilleur d'abord.Le cadre est suffisamment général pour exprimer des algorithmes populaires tels Proof Number Search, Monte Carlo Tree Search, ainsi que l'algorithme Product Propagation.Nous montrons par ailleurs comment adapter ce cadre à deux situations plus générales: les jeux à deux-joueurs à plusieurs issues, et le problème de model checking en logique modale K.Cela donne lieu √† de nouveau algorithmes pour ces situations inspirés des méthodes Proof Number et Monte Carlo.La technique de l'élagage alpha-beta est cruciale dans les jeux à actions séquentielles.Nous proposons une extension de cette techniques aux stacked-matrix games, une généralisation des jeux à deux joueurs, à information parfaite et somme nulle qui permet des actions simultanées. / Efficient best-first search algorithms have been developed for deterministic two-player games with two-outcome.We present a formal framework to represent such best-first search algorithms.The framework is general enough to express popular algorithms such as Proof Number Search, Monte Carlo Tree Search, and the Product Propagation algorithm.We then show how a similar framework can be devised for two more general settings: two-player games with multiple outcomes, and the model checking problem in modal logic K.This gives rise to new Proof Number and Monte Carlo inspired search algorithms for these settings.Similarly, the alpha-beta pruning technique is known to be very important in games with sequential actions.We propose an extension of this technique for stacked-matrix games, a generalization of zero-sum perfect information two-player games that allows simultaneous moves.