| Resumo: | In recent years, Monte Carlo Tree Search (MCTS) has been successfully applied as a new artificial intelligence strategy in game playing, with excellent results yielded in the popular board game Go, real time strategy games and card games. The MCTS algorithm was developed as an alternative over established adversarial search algorithms, i.e., Minimax (MM) and knowledge-based approaches.MCTS can achieve good results with nothing more than information about the game rules, and can achieve breakthroughs in domains of high complexity, whereas in traditional AI approaches, developers might struggle to find heuristics through expertise in each specific game.Every algorithm has its caveats, and MCTS is no exception, as stated by Browne et al: "Although basic implementations of MCTS provide effective play for some domains, results can be weak if the basic algorithm is not enhanced. (...) There is currently no better way than a manual, empirical study of the effect of enhancements to obtain acceptable performance in a particular domain."Thus, the first objective of this dissertation is to research various state of the art MCTS enhancements in a context of card games and then proceed to apply, experiment and fine tune them in order to achieve a highly competitive implementation, validated and tested against other algorithms such as MM.By analysing trick-taking card games such as Sueca and Bisca, where players take turns placing cards face up in the table, there are similarities that allow the development of a MCTS based implementation that features effective enhancements for multiple game variations, since they are non deterministic imperfect information problems. Good results have been achieved in this domain with the algorithm, in games such as Spades and Hearts.The end result aims toward a framework that offers a competitive AI implementation for at least 3 different card games (achieved with analysis and validation against other approaches), allowing developers to integrate their own card games and benefit from a working AI, and also serving as testing ground to rank different agent implementations.
|
|---|