Framework for Monte Carlo Tree Search-related strategies in Competitive Card Based Games

FACULDADE DE ENGENHARIA DA UNIVERSIDADE DO PORTO Framework for Monte Carlo Tree Search-related strategies in Competitive Card Based Games Pedro Ricardo Oliveira Fernandes Mestrado Integrado em Engenharia Informática e Computação Supervisor: Hugo Sereno Ferreira (PhD) Second Supervisor: Ivo Timóteo (MSc) June 27, 2016 Framework for Monte Carlo Tree Search-related strategies in Competitive Card Based Games Pedro Ricardo Oliveira Fernandes Mestrado Integrado em Engenharia Informática e Computação Approved in oral examination by the committee: Chair: Prof. dr. Henrique Lopes Cardoso External Examiner: Prof. dr. Pedro Ribeiro (Universidade do Porto, FCUP) Supervisor: Prof. dr. Hugo Sereno Ferreira June 27, 2016 Abstract 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, e.g., 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." [BPW+12] 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 which allow the development of a MCTS based implementation that features enhancements effective in 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 [WCPR13a] and Skat [FB13]. The end result aims toward a framework that offers a competitive AI implementation for the card games Sueca, Bisca and Hearts (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. i ii Resumo Nos últimos anos, o algoritmo de Monte Carlo Tree Search (MCTS) tem sido aplicado com sucesso como uma nova abordagem de inteligência artificial (IA) em jogos, obtendo excelentes resultados no jogo de tabuleiro "Go", jogos de estratégia em tempo real e, também, jogos de cartas. O MCTS foi desenvolvido como uma alternativa a algoritmos clássicos de pesquisa adversarial (como, por exemplo, Minimax (MM) e abordagens baseadas em regras de conhecimento de jogo). O MCTS consegue alcançar bons resultados apenas com a declaração de regras de jogo, permitindo, assim, o avanço do estado da arte em inteligência artificial para domínios de alta complexidade, enquanto que as abordagens tradicionais de IA não prescidem do uso de heurísticas com base em conhecimento do domínio. Em alguns casos, as heurísticas são complexas de formular, inviabilizando o uso destas abordagens. No entanto, a aplicação de MCTS também apresenta as suas desvantagens, nomeadamente: os resultados são geralmente considerados fracos se a versão básica do algoritmo não for melhorada. Para obter um desempenho aceitável num domínio, não existe, atualmente, melhor alternativa do que o estudo manual e empírico dos efeitos de melhorias no algoritmo [BPW+12]. Consequentemente, o primeiro objetivo desta dissertação é elaborar um estudo do estado da arte de melhorias para o MCTS, aplicadas ao domínio de jogos de cartas. A experimentação com melhorias permite obter uma implementação competitiva que será avalidada e testada contra outros algoritmos como, por exemplo, o MM. Jogos de cartas em vaza, onde cada jogador coloca cartas sequencialmente no centro da mesa, como a Sueca e a Bisca, serão o foco deste estudo. Existem semelhanças nestes jogos que permitem a partilha de melhorias numa abordagem MCTS. A aplicação deste algoritmo já alcançou bons resultados no domínio de jogos de cartas, nomeadamente em Espadas [WCPR13a] e Skat [FB13]. O objetivo final é desenvolver uma framework que oferece uma implementação de IA para os jogos de cartas Sueca, Bisca e Copas, com análise e validação contra diferentes abordagens. Aframework irá permitir a programadores ou investigadores a integração dos seus próprios jogos de cartas, servindo como um ponto de partida para testar e avaliar a eficiência de diferentes implementações de agentes de IA. iii iv Acknowledgements Firstly I would like to thank both my supervisors, Prof. Hugo Sereno and Ivo Timóteo, for offering me this challenge, which sparkled my interest in the field of artificial intelligence, and also for their guidance and support throughout this dissertation. I want to thank my girlfriend, Isabel, who accompanied me through all my years of study and work, including both good and bad times. Her love and patience has always been my tower of strength, and with her support, I am always ready to embrace tougher challenges every day. I also want to thank my family, especially my parents, for their love and support, as well as my brother, Luís, who never hesitated to help whenever I needed the most, always ready and willing to share his knowledge and lend a hand. I would also like to thank my company, Blip, for providing me with excellent working conditions while studying, and for always letting me prioritize studies when necessary. I specially thank my co-workers from the Avengers Team, namely, Bárbara Salgado, Gonçalo Matos, Hugo Bacelar, João Cunha, Nuno Estrada, Pedro Santos, Sandrine Mendes, Tiago Alves and Tiago Morais. The team accompanied me through every step of this journey, always sharing my triumphs and worries. Working with them was an experience that I will personally treasure and be thankful for. Last, but not least, I would like to thank my friends, André and Débora, for their care and attention. They were always present through many hard times, and we are thankful for having them as our second family. Pedro Fernandes v LIST OF FIGURES xii Abbreviations MCTS Monte Carlo Tree Search ISMCTS Information Set Monte Carlo Tree Search MM Minimax PIMC Perfect Information Monte Carlo UCT Upper Confidence Bound 1 applied to Trees UCB1 Upper Confidence Bound 1 AI Artificial Intelligence NAST N-gram Average Sampling Technique EPIC Episodic Information Capture and reuse EBF Effective Branching Factor xiii Chapter 1 Introduction This chapter serves as an introduction to the problem and scope of this dissertation. Section 1.1 details the context in which the problem is relevant. Section 1.2 properly defines the main issues to solve. Section 1.3 explains the reasons that motivate this work and goals that have been set as an end result. Section 1.4 lists the full report structure by specifying the topics of each chapter. 1.1 Context In recent years, advances in AI research have developed strong adversarial tree search methods, specifically the Monte Carlo Tree Search (MCTS) family of algorithms. These algorithms have proven to be very efficient in combinatorial games such as the board game Go, where previous attempts at artificial intelligence did not produce results capable of challenging human players. Since the official proposal of MCTS in 2006 [Cou06], many enhancements and variations have been studied and experimentated on several game domains, including games of hidden information, where tree search complexity is relatively high and classic algorithms, such as expectimax, can not give the optimal move in a feasible amount of time, due to the large branching factor of hidden information game trees. MCTS variations such as Determinized UCT and Information Set MCTS (ISMCTS) have shown great results in card games such as Spades [WCPR13b], surpassing state of the art rule based systems specifically built with game domain knowledge. Rule based AI systems are difficult to create, requiring a large amount of research and experimentation on specific game rules, while MCTS algorithms are aheuristic, i.e. they do not require specific domain knowledge to work, and thus variations of MCTS that are found to produce good play on certain games can be re-used on games that share similar characteristics, facilitating AI development for programmers and researchers. 1 Introduction 1.2 Problem Definition MCTS has proven to be efficient in many different game domains, but the most basic implementation, UCT, usually yields simple and rudimentary playing strategies that are incapable of challenging strong human players. To improve the playing strengh of MCTS, there are several algorithm variations and enhancements that can be of use, improving performance on specific domains. The problem of selecting which variations are best applied to a specific game domain, in order to achieve champion status, is still very challenging. Most search dynamics are not yet fully understood and thus, there is currently no better way than a manual experimentation and analysis of enhancement performance on each specific game [BPW+12]. Games of hidden information add complexity to the tree search due to an increased branching factor, since there is a greater amount of possible states, corresponding to all different combinations of what the hidden information might reveal to be. The final decision process must then be weighted according to the probabilities associated with each possible game state. The common approach to address this issue is through what we define as a determinization: the process of transforming a stochastic game of hidden information into a deterministic one. Afterwards, we can apply algorithms that have been extensively researched for deterministic games, such as MCTS or Minimax, averaging the best move over many determinized games. However, these approaches are ineffective in some game domains due to adverse issues of determinization, such as strategy fusion and non-locality. Also, bluffing strategies are difficult to develop if hidden information is removed from a game. In light of the previous issues, a few questions are now proposed: Q1. Which MCTS variations and enhancements are best applied to trick taking card games? Q2. Can an enhanced MCTS develop strong play against traditional AI techniques in trick taking card games? Q3. Do the advantages of determinization outweigh its shortcomings when applied to trick taking card games? Can the shortcomings be efficiently diminished through specific enhancements? All three questions require analysis and research on state of the art MCTS enhancements. With the study of successful MCTS implementations in different trick taking games (e.g.: Spades and Hearts), it’s possible to gather a list of most promising algorithm variations and enhancements, as well as conclusions regarding game characteristics that most influence algorithm performance. This process will then facilitate testing and experimentation in specific domain of games studied in the scope of this dissertation. 2 Introduction 1.3 Motivation and Goals The motivation behind this dissertation starts with the application of MCTS variants to card games that are not explored in scientific literature, such as Sueca, that is very popular in portuguese speaking countries. There is also a lack of open source initiatives that promote code re-use of MCTS algorithms and allow developers to implement and experiment with their prefered game domains. A platform that enables easy integration of different AI agents and testing their relative efficiency would benefit the community of game developers and AI researchers alike. Such initiatives can accelerate the discovery of new MCTS enhancements and allow fine tuning of variations applied to specific domains, speeding up experimental research for several games. Knowledge of the best kind of MCTS implementation applied to a specific game context can lead to a profitable commercial use of an AI for mobile device games. As an example, a MCTS variation has been applied to the card game Spades, producing strategies mostly perceived as strong and intelligent, leading to very positive application reviews and a large amount of downloads [WCPR13b]. Taking into account the motivation, the main goals regarding the scope of this dissertation can be elaborated as follows: G1. Elaborate a study on the best known MCTS implementations applied in the context of trick taking card games; G2. Create a framework with some MCTS variations and enhancements, with application in card games; G3. Develop a framework that enables different AI agents to compete against each other and evaluate relative performance and quality of play; G4. Use the developed framework to experiment and analyse the best performing MCTS enhancements in a selection of three trick taking card games. 1.4 Report Structure This report is composed by 7 main chapters. The first chapter gives an introduction to the problem and scope of this dissertation, detailing the context in which the problem is relevant, how to properly define the main issues to solve, what are the reasons that motivate this work and goals that have been set as an end result. The second chapter offers a literature review of scientific research that is relevant to the problem at hand, including an analysis of Monte Carlo Tree Search algorithms and enhancements, along with some required background, namely Game Theory, Decision Theory and the multi armed bandit problem. Other subsections detail what algorithms can be applied in adversarial search for imperfect information games. 3 Introduction The third chapter details the main characteristics of trick taking card games and introduces the rules for all three proposed card games, as well as some insight on common playing strategies. The fourth chapter presents implemented work throughout the dissertation. Specifically, a new determinization algorithm is proposed, and an overall architecture overview is given on both the Botwars framework and the developed MCTS framework for card games. The fifth chapter describes all algorithms that are used in the experimental results, detailing pseudocode and a quick analysis on their application to the proposed trick taking card games. The sixth chapter presents the experimental setups and obtained results, with charts and commented analysis of the observed efficiency for all tested algorithms and enhancements. The seventh and last chapter gives a conclusion to the developed work, starting with an overview of the achieved goals and then an overall reflection on observed results, while proposing guidelines for possible future work. 4 Chapter 2 Related Work This chapter introduces the main topics associated with artificial intelligence for trick taking card games. Section 2.1 and 2.2 introduce the concepts of Decision Theory and Game Theory respectively, defining some important formalizations that are the foundation for artificial intelligence in games. Section 2.3 explains the multi armed bandit problem, which is the underlying theory behind Monte Carlo Tree Search methods. Section 2.4 introduces MCTS with a quick overview of how the algorithm works, with subsections describing the most relevant properties of the algorithm, how UCT balances exploration with exploitation and what enhancements can be applied in the context of card games. Section 2.5 includes a list of algorithms that can be applied to games of imperfect information, such as card games. 2.1 Decision Theory Decision theory mixes probability theory with utility theory, providing a complete and formal framework for decisions made under uncertainty [RN10, Ch.13]. Problems with an utility value defined by decision sequences are pursued in operations research and the study of Markov decision processes. AMarkov Decision Process (MDP) models sequential decision problems in enviroments with total observability, through the use of four components: [RN10, Ch.17] •S: a set of states, where s0is the initial state; •A: a set of possible actions to apply •T(s,a,s’): a transition model that gives the probability of reaching state s0if action a is applied in state s •R(s): a reward function 5 Related Work Decisions are then modelled as sequences of (state,action)pairs, where the next state is given by a probability distribution, taking into account a given state-action pair. A policy determines which action will be choosen from a given state in Sand the aim is to find the policy πthat yields the highest expected reward. If the state is not fully observable, then a Partially Observable Markov Decision Process (POMDP) model is required, where an extra component O(s,o)is an observation model used to give the probability of perceiving observation oin the state s. 2.2 Game Theory Game theory combines situations where multiple agents interact with the concepts of decision theory. A game can be defined as a set of rules that allow interaction between a number n>0 of players to produce specified outcomes. The following components can describe a specific game: •S: a set of states, where s0is the initial state; •ST⊆S: the set of terminal states; •n∈N: the number of players; •A: a set of possible actions to apply; •f:S×A→S: the state transition function; •R:S→Rn: the utility function; •p:S→(0,1,...,n): the player that will act in each state A game starts in the initial state s0and advances over time t∈Nuntil a terminal state in STis reached. Any given player kiselects and performs an action (i.e. a move in the game) that causes the transistion of state stto the next state st+1through the application of function f. Every player receives a reward value, which is the game-theoretic value of a terminal state, obtained through the utility function R, according to the player performance in the game. The values are specific to different games, but usually a notation of +1, 0 or -1 can be used to respectively represent wins, draws and losses. A player’s strategy, i.e. policy, determines the selection probability of a given action ato apply in state s. A Nash Equilibrium is reached when all players combine their strategies in a way that no individual player will benefit from unilaterally changing their own strategy [RN10, Ch.17]. A Nash Equilibrium always exists in a game, but computing it is generally considered an intractable problem for games with a large set of states. Games can be classified by various properties, some of which are [RN10, Ch.2.4]: •Zero-sum: if the summed game reward for all players totals zero (e.g.: two player games where a player wins and another loses); 6 Related Work •Information: if the game state is fully visible to all players, or only partially observable (e.g.: card games where players hide their cards from opponents); •Determinism: if there are factors of chance affecting players strategy, causing uncertainty over rewards (e.g: board games with dice rolls determining the result of actions); •Sequential: if actions are sequential or simultaneous (e.g.: whether all players act at the same time or in their own turn); •Discrete: if actions and effects are well determined and defined or with an infinite set of actions and unpredictable results, i.e. continuous. In this dissertation, the main focus will be toward card games of imperfect information (the game state is partially observable by players) and non deterministic nature (card deck is shuffled at the start of each game), where actions always occur sequentially (each player puts a card face up on the table in their own turn) and in a discrete manner. 2.3 Multi Armed Bandits In the multi-armed bandits problem, a gambler must choose which bandit machine to play, taking into account that each machine has arms with different probabilities of giving away a prize. The objective of this problem is to maximize the player gain, and this can be achieved by spending the biggest amount of time in the machine with highest reward probability, but the player must also spend time evaluating which machine actually has the highest probability. This is a specific example of the exploitation versus exploration dilemma: one needs to balance exploitation of actions that are currently believed to be optimal with the exploration of other apparently suboptimal actions that may turn out to be superior in the future. The problem amounts to selecting which bandit arm should be attempted next, taking as an input all the rewards received on all previous trials. When playing a sub-optimal arm, it is possible to measure the incurred loss between the current received reward and the expected reward from the optimal arm. This measure is called regret, and the regret acumulated on all previous trials of the player is called the cumulative regret. Multiarmed bandit policies, also known as bandit algorithms, can have their strength evaluated by the expected value of the cumulative regret after a specified number nof trials. Auer et al propose upper confidence bound (UCB) policies, of which the simplest policy, UCB1, has an expected logarithmic growth of cumulative regret uniformly over nnumber of trials [ACbF02]. In MCTS algorithms, the move selection problem can be interpreted as a multi-armed bandit problem, where each move is considered a different arm, with unknown reward probabilities. As such, research in the domain of bandit problems can be effectively reused in the context of Monte Carlo Tree Search algorithms. 7 Related Work •N-gram average sampling technique (NAST) is a generalisation of the MAST enhancement, proposed by Powley et al [PWC13], where instead of learning values only for a single move, NAST learns values for sequences of consecutive moves in the game, with Nequal to the length of the sequence. This enhancement is shown to improve win rate in card games Dou Di Zhu and Hearts [PCW14], with results visible in figures 2.4 and 2.5. Powley et al proposed a framework for describing and combining MCTS enhancements called Information Capture And ReUse Strategy (ICARUS) [PCW14], allowing to better understand existing enhancements, mixing them in the same implementation and designing new enhancements. It’s thus possible to combine all of the previously described enhancements into a single MCTS implementation, with policies that use a weighted decision between all the enhancements’ statistics. In experiments, it is shown that EPIC and NAST increase the win rate of MCTS implementations in the card games Dou Di Zhu and Hearts, while RAVE, MAST and LGR are mostly detrimental [PCW14], with results visible in figures 2.4 and 2.5. 2.5 Adversarial Search in Imperfect Information Games This section is focused on algorithms specially created to handle games of uncertainty and hidden information. Subsection 2.5.1 introduces determinization techniques with PIMC, with subsections detailing drawbacks of the approach and how to determine when a game has characteristics that benefit from this method. Subsection 2.5.2 introduces minimax and its most important variation for games with chance events, expectimax. Subsection 2.5.3 introduces ISMCTS, which is another variation of MCTS that also uses determinization, but overcomes some drawbacks of Perfect Information Monte Carlo (PIMC), with a subsection detailing parallelization enhancements. 2.5.1 Perfect Information Monte Carlo According to game theory, in games of imperfect information, states are combined into an information set when some player has a perspective of the game state that another player does not. Using card games as an example, players hide their cards from opponents and as such, the information set accounts for states that represent all the possible combinations of opponent cards. Thus, the player will aim to maximize their expected reward taking into account all the possible game states, since it is impossible to distinguish in which specific state he is in. Determinization, also know as Perfect Information Monte Carlo (PIMC) is a possible approach for handling stochastic and imperfect information games [LSBF10]. In such games, a determinization is an instance of the equivalent game of perfect information where all chance events are known in advance by choosing a current state of the game from the observer’s possible information set. These determinizations can be sampled multiple times from a game state and in each determinized version of the game, AI algorithms for perfect information games can be applied, such as MCTS or Minimax. The overall best decision is achieved by combining the best found moves for each determinized game. 14 Related Work Successful uses of PIMC include Ginsberg’s GIB program, which plays the card game Bridge at the level of human experts [Gin01]. GIB starts by sampling possible set of cards D, that are consistent with the observed state of the game so far, taking into account game rules. For every deal of cards d∈Dand for every move m∈M, in which Mis the candidate set of possible moves, the perfect information game is searched with a highly optimised exhaustive search to evaluate the score s(m,d), which is the result of applying move mwith the deal d. The last step involves choosing the move mwhich maximizes ∑d∈Ds(m,d). Bjarnason et al propose a UCT algorithm variation to handle stochastic games, named Sparse UCT, and applied it to the single-player card game Klondike Solitaire [BFT09]. Bjarnason et al also proposed an ensemble variant of the same algorithm, where several search trees are explored independent from each other and statistics for every move at root nodes are averaged to find the best overall move, with one specific variant of this technique called HOP-UCT. In Sparse UCT and variants of the algorithm, the game is handled as perfect information game, but instead of determining all possible chance events at the start of the game, these are only determined in the point where information is about to be revealed (e.g.: when face down cards are turned over). This approach works well in single player games where hidden information does not influence the game until it is revealed, but this is generally not the case in multiplayer card games, where hidden information greatly influences style of play right from the beginning of the game and not only when cards are played by opponents. 2.5.1.1 Drawbacks of Determinization Determinization approaches have proven to be very successful in card games such as Bridge [Gin01], Klondike Solitaire [BFT09] and the trick taking card game Skat [FB13]. However, the approach has some flaws that hinder its usefulness in certain game domains. Russel and Norvig describe PIMC as "averaging over clairvoyance" [RN10] and point out determinization will never make an information gathering play nor an information hiding play (i.e. it will never force opponents to reveal their information nor try to hide information from them), since the game is treated as a perfect information game, where all possible moves are visible to all players. Effectively, the algorithm is hindered in terms of bluffing capabilities. Frank and Basin have identified two other key issues with determinization: [FB98] •Strategy Fusion: arises because PIMC incorrectly assumes it is possible to use a different strategy for differents states in the same information set. However, a player can not distinguish between states in his information set, and must choose the same strategy in each situation. An example situation where this is highly detrimental to the algorithm is described as follows in figure 2.6 (a): at the root of the game tree, the maximizing player can choose a move to the right, leading to the terminal state cwith a reward of 1. If the option on the left is choosen, the player can receive a reward of 1 or -1 depending on the world he is in and what second choice is made, leading to terminal nodes aor b. An analogous situation 15 Related Work (Frank and Basin 1998). They showed that the nature of PIMC search makes it prone to two distinct types of errors, irrespective of the number of hypothetical worlds examined. The first of these errors is termed strategy fusion.Strategy fusion arises because PIMC search (incorrectly) believes it can use a different strategy in each world, whereas in reality there are situations (or information sets) which consist of multiple perfect information scenarios. In the full imperfect information game, a player cannot distinguish between these situations, and must choose the same strategy in each one; but PIMC search erroneously assumes that it can choose a strategy tailored to each individual scenario. We illustrate strategy fusion in Figure 1(a). The maximizing player is represented as an upward pointing triangle, and the minimizing player by a downward triangle. Terminal nodes are squares with payoffs for the max player below them. There are two worlds which would be created by a chance node higher in the tree. We assume neither player knows whether they are in world 1 or 2, so we do not show this information in the tree. At the root, the maximizing player has the choice of moving to the right to node (c) where a payoff of 1 is guaranteed, no matter the world. The maximizing player can also get a payoff of 1 from the nodes marked (a) in World 1 and the nodes marked (b) in World 2. PIMC search will think that it can always make the right decision above nodes (a) and (b), and so both moves at the root look like wins. However, in reality the max player is confused between worlds 1 and 2 and may actually make a mistake in disambiguation on the left side of the tree. We note that there are two conditions required for strategy fusion to actually cause an error in the play of PIMC search. First, there must be moves which are anti-correlated values (nodes (a) and (b)) on one portion of the tree, and second, there must be a move which is guaranteed to be better on the other side of the tree. If node (c) had the value -1, PIMC search would make the correct decision, although it would overestimate the value of the tree. The second error identified by Frank and Basin is termed non-locality.Non-localityisaresultofthefactthatina perfect information game, the value of a game tree node is afunctiononlyofitssubtree,andthereforethevalueofa node is completely determined by a search starting with its children. In an imperfect information game, a node’s value may depend on other regions of the game tree not contained within its subtree, primarily due to the opponent’s ability to direct the play towards regions of the tree that he knows (or at least guesses) are favorable for him, using private information that he possesses but we do not. This phenomenon creates non-local dependencies between potentially distant nodes in the tree. We illustrate non-locality in Figure 1(b). In this figure there is a chance node at the top of the tree. The maximizing player knows the chance action, but the minimizing player cannot distinguish between the states within the dotted rectangle. In this tree PIMC search would make a random move for the minimizing player. But, in fact, the minimizing player can always know the correct move. Because the maximizing player will take the win in world 1 if possible, the minimizing player will only have an opportunity to Figure 1: Examples of strategy fusion and non-locality. play if he is in world 2, when the maximizing player moves to the left to avoid the immediate loss. Thus, the minimizing player can infer the correct world and the correct action. While we will not create these structures explicitly in our game model, we will be able to tune the probabilitythat they occur and that PIMC search will be confused. We can also measure how often this occurs in actual game trees. Domains We use two illustrative domains in this paper. The first is aclassoftrick-basedcardgames.Thepreciserulesforthe domain are not important for our purposes, but the actions in the domain are. In a trick-based card game an action is to play a card from one’s hand onto the table face up. This has two implications. First, informationis revealed and information sets are split when actions take place. Second, there are many possible legal actions. Most western games use a 52 card deck, allowing up to 52 possible actions at each node in the game tree. Some European card games use a short deck of 32 cards, resulting in at most 32 actions in each state. The second domain we examine is Poker. Again, there are many variants of poker which we will not discuss here. What is important is that there are a limited number of actions (bet, raise, call, fold), and actions do not directly reveal 135 (Frank and Basin 1998). They showed that the nature of PIMC search makes it prone to two distinct types of errors, irrespective of the number of hypothetical worlds examined. The first of these errors is termed strategy fusion.Strategy fusion arises because PIMC search (incorrectly) believes it can use a different strategy in each world, whereas in reality there are situations (or information sets) which consist of multiple perfect information scenarios. In the full imperfect information game, a player cannot distinguish between these situations, and must choose the same strategy in each one; but PIMC search erroneously assumes that it can choose a strategy tailored to each individual scenario. We illustrate strategy fusion in Figure 1(a). The maximizing player is represented as an upward pointing triangle, and the minimizing player by a downward triangle. Terminal nodes are squares with payoffs for the max player below them. There are two worlds which would be created by a chance node higher in the tree. We assume neither player knows whether they are in world 1 or 2, so we do not show this information in the tree. At the root, the maximizing player has the choice of moving to the right to node (c) where a payoff of 1 is guaranteed, no matter the world. The maximizing player can also get a payoff of 1 from the nodes marked (a) in World 1 and the nodes marked (b) in World 2. PIMC search will think that it can always make the right decision above nodes (a) and (b), and so both moves at the root look like wins. However, in reality the max player is confused between worlds 1 and 2 and may actually make a mistake in disambiguation on the left side of the tree. We note that there are two conditions required for strategy fusion to actually cause an error in the play of PIMC search. First, there must be moves which are anti-correlated values (nodes (a) and (b)) on one portion of the tree, and second, there must be a move which is guaranteed to be better on the other side of the tree. If node (c) had the value -1, PIMC search would make the correct decision, although it would overestimate the value of the tree. The second error identified by Frank and Basin is termed non-locality.Non-localityisaresultofthefactthatina perfect information game, the value of a game tree node is afunctiononlyofitssubtree,andthereforethevalueofa node is completely determined by a search starting with its children. In an imperfect information game, a node’s value may depend on other regions of the game tree not contained within its subtree, primarily due to the opponent’s ability to direct the play towards regions of the tree that he knows (or at least guesses) are favorable for him, using private information that he possesses but we do not. This phenomenon creates non-local dependencies between potentially distant nodes in the tree. We illustrate non-locality in Figure 1(b). In this figure there is a chance node at the top of the tree. The maximizing player knows the chance action, but the minimizing player cannot distinguish between the states within the dotted rectangle. In this tree PIMC search would make a random move for the minimizing player. But, in fact, the minimizing player can always know the correct move. Because the maximizing player will take the win in world 1 if possible, the minimizing player will only have an opportunity to Figure 1: Examples of strategy fusion and non-locality. play if he is in world 2, when the maximizing player moves to the left to avoid the immediate loss. Thus, the minimizing player can infer the correct world and the correct action. While we will not create these structures explicitly in our game model, we will be able to tune the probabilitythat they occur and that PIMC search will be confused. We can also measure how often this occurs in actual game trees. Domains We use two illustrative domains in this paper. The first is aclassoftrick-basedcardgames.Thepreciserulesforthe domain are not important for our purposes, but the actions in the domain are. In a trick-based card game an action is to play a card from one’s hand onto the table face up. This has two implications. First, informationis revealed and information sets are split when actions take place. Second, there are many possible legal actions. Most western games use a 52 card deck, allowing up to 52 possible actions at each node in the game tree. Some European card games use a short deck of 32 cards, resulting in at most 32 actions in each state. The second domain we examine is Poker. Again, there are many variants of poker which we will not discuss here. What is important is that there are a limited number of actions (bet, raise, call, fold), and actions do not directly reveal 135 Figure 2.6: Examples of strategy fusion and non-locality. 4and 5respectively denote the maximizing and minimizing player decision nodes. Squares represent terminal game states with respective reward. represent chance nodes. [LSBF10] would be the maximizing player guessing which side of the coin would be up after a coin toss. For PIMC, both choices would seem equal and thus randomly picked, since it can not distinguish the expected reward between nodes a,band c, because determinizations lead the algorithm to believe it can always choose the best node in every situation (the coin toss is simulated before the choice is carried out). This is a very poor decision since always choosing the end state cwould give a guaranteed positive reward of 1, while the left branch only leads to an expected average reward of 0 (if the coin toss yields a 50% chance of success). •Non-locality: occurs when some determinizations lead to very unlikely situations of play due to opponents’ ability to direct play away from these corresponding states, which renders solutions irrelevant to the final decision process. An example situation where this effect is prejudicial to the algorithm is visually demonstrated in figure 2.6 (b): there is a chance node at the root of the tree. The maximizing player knows the chance action, and can distinguish if he is located in world 1 or 2. In world 1, the maximizing player has the ability to win the game instantly by choosing terminal state c0or he can let the adversary play. In world 2, the player loses if he chooses terminal state cand thus should let the adversary play. An analogous situation would be in a card game, where the maximizing player could have a game winning card or instead a losing one, as well as cards that would resume the play. PIMC can not distinguish which world the minimizing player is in between states displayed in the dotted rectangle, when in reality it is possible to infer that if the maximizing player had the game winning card, he would rationally make the decision to immediately win, and thus the only plausible state where the minimizing player would have an opportunity to play would be in world 2. Any 16 Related Work Figure 5: Performance gain of PIMC search over random against a Nash equilibrium. Darker regions indicate minimal performance gain for using PIMC search over random play. Disambiguation is fixed at 0.3, bias at 0.5 and correlation at 0.75 in figures a, b and c respectively. Figure 6: Parameter space estimation for Skat game types and Hearts. Dark regions correspond to a high density of games with those measured parameters. Values were sampled using 10000 games for each skat type and 3000 games for hearts. Bias is given in terms of score w.r.t. a fixed player. Real Games To test the predictive powers of our three properties, we estimated the distribution of those parameters for actual games. The first game so measured is Skat. Although the exact rules are unimportant, the specific type of Skat game varies depending on an initial auction phase. The winner of the auction (the soloist)choosesthegametypeandcompetes against the two other players (who now form a temporary coalition). The two most common game types are suit games and grand games; both have a trump suit and are concerned with taking high-valued tricks. The third type of game is null,inwhichthesoloisttriesnottowinanytricks(and loses if even one trick is won). For each game type, 10000 human-bid games were explored using random actions from the start of the cardplay phase. In each game correlation and bias were measured 1000 times near the leaves. To do this, we walk down the tree, avoiding moves which lead to terminal positions (after collapsing chains of only one legal move). When all moves lead directly to terminal positions we take their value to be the game value with respect to the soloist (to emulate the values of the fixed depth synthetic trees). We say these “pre-terminal” nodes are correlated if all move values are the same, and compute bias as the fraction of correlated nodes which are soloist wins. Disambiguation was measured by comparing the change in the number of possible (consistent) worlds since the current player was last to move. Only 10 disambiguation rollouts were performed per world, since the resulting ratios were tightly clustered around df =0.6.Theobserveddistributions are shown in Fig. 6. In this figure, we also display results for Hearts, which, like Skat, is a trick-taking card game, but played with a larger deck and different scoring rules. 3000 Hearts games using 500 sample points per game were used to generate this data. For both the skat and hearts games, the resulting graphs show a very high level of correlation (from 0.8 to nearly 1.0),with bias varyingmorewidely and disambiguationvery close to 0.6, as mentioned above. Examining Figures 3(b) and 5(b) puts skat in a parameter space where the PIMC player loses only 0.1 points per game against equilibrium and gains 0.4 points over random play (recalling that our synthetic trees use payoffs from -1 to 1), with perhaps plus or minus 0.05 points depending on the bias of the individual hand. This seems like relatively good performance for PIMC search, which coincides with our motivating evidence that PIMC search seems to perform well in these games in practice. The second game we measured is Kuhn poker, a highly simplified poker variant for which Nash-optimal solutions are known. In this game two players are each dealt one card out of a deck of three. The game proceeds as: both players ante; player 1 may check or raise; player 2 may fold, check, call, or raise as appropriate; if the game is still proceeding, 139 Figure 2.7: Performance gain of PIMC search over random against a Nash equilibrium. Darker regions indicate minimal performance gain for using PIMC search over random play. Disambiguation is fixed at 0.3, bias at 0.5 and correlation at 0.75 in figures a, b and c respectively [LSBF10] simulations carried out on world 1 for that unlikely state would not be useful for the overall decision and strategy. 2.5.1.2 Measuring Effectiveness of Determinization in Games Long et al identified three distinct parameters of game trees characteristics and analysed the correlation between the parameters and the effectiveness of determinization [LSBF10]. The parameters are as follows: •Leaf Correlation: the probability of all sibling terminal nodes have equal reward value. Low correlation is present in games where a player can always affect their payoff even very late in the game. •Bias: the probability that the game will favor a specific player over another. •Disambiguation factor: determines how quickly the number of nodes in a player’s information set shrinks with regard to the depth of the tree, i.e. how quickly hidden information is revealed as the game progresses. In trick taking card games, a player reveals a card on every move, which means the number of states in each players information set is reduced as the game is being played, leading to a high disambiguation factor. Conversely, in poker, no information is revealed until the end of the round, which translates into a low disambiguation factor. By performing experiments on synthetic game trees, generated to satisfy different values for each of the three parameters, Long et al have compared the effectiveness of PIMC against random play, with results shown in figure 2.7 [LSBF10]. PIMC search is at its best in games with a high disambiguation factor coupled with a high leaf correlation, which suggests that trick taking card games like Hearts and Skat are ideal candidates for a successful application of determinization techniques, while games such as Poker will most likely show very weak results. 17 Related Work 2.5.2 Minimax The minimax algorithm [RN10, Chapter 6] is a popular tree search method for combinatorial games and has been successfully applied in many domains of perfect information games, producing for example the first program capable of beating a chess grandmaster [Hsu04]. There are variations of the minimax algorithm that handle games of stochastic nature, starting with the expectimax search, where values of chance nodes correspond to the value of child nodes multiplied by the probabilities of the chance outcome. Other variations include for example ∗-minimax trees [Bal83], which also handles chance events and miximax search, and is similar to a single player expectimax [BDS+04]. Unfortunately, expectimax and its’ variations are not well suited for trick taking card games, where there is a single chance node at the root of the tree with a very high branching factor, that corresponds to all possible combinations of opponent distribution cards. As an example, in the card game Sueca, there are 40 initially shuffled cards, of which every player receives 10. This means that there are 30 10∗20 10∗10 10=5 550 996 791 340 possible combinations of opponent hands in the start of the game. 2.5.3 Information Set MCTS Whitehouse et al studied the performance of deterministic game search algorithms, namely a cheating minimax (that could observe opponents cards), a determinized minimax (PIMC) and expectimax in a simplified version of Dou Di Zhu. [WPC11] In their experiments, they find that expectimax outperforms determinized minimax by around a 30% higher win rate, while only 10% lower win rate against a cheating minimax, which leads the authors to conclude that the benefit of cheating algorithms, i.e. with the ability to see adversaries’ cards, has less to do with having access to hidden information and more with overcoming the weaknesses of determinization, at least for the case of a simpler version of Dou Di Zhu. When applying PIMC, strategy fusion arises since the value of moves is estimated according to specific determinized states. To overcome this effect, Cowling et al propose a new variation of MCTS named Information Set MCTS (ISMCTS) [CPW12], where only a single decision tree is used, in which nodes correspond to information sets instead of game states. Since searching a tree with nodes for each unique information set is intractable for large games, ISMCTS groups information sets into single nodes as much as possible to reduce tree complexity. Also, on each iteration of the algorithm, only one determinization is generated to avoid biasing the value of nodes for specific states. The main differences between ISMCTS and PIMC, besides the removal of strategy fusion, are the use of a single decision tree instead of multiple trees (comparable in figures 2.8 and 2.9), resulting in lower memory use, and the removal of the need to balance determinizations and simulations, since a PIMC coupled with MCTS requires the specification of the number of iterations per each generated determinization, while ISMCTS uses only one determinization per iteration. However, ISMCTS is more complex compared to a UCT search and thus the amount of simulations done in 18 Related Work the same time frame is significantly reduced. This fact can make PIMC more efficient in specific game domains, were the advantage of more simulations outweigh the effects of strategy fusion. Both algorithms do not address the issue of non-locality (inference) and bluffing, each requiring additional specific enhancements to the algorithm. 126 IEEE TRANSACTIONS ON COMPUTATIONAL INTELLIGENCE AND AI IN GAMES, VOL. 4, NO. 2, JUNE 2012 Fig. 3. A game tree for a simple two-player game. Nodes shaped denote player 1 decision states, player 2 decision states, environment states, and terminal states labeled with reward values for player 1 (the game is zero-sum, so player 2’s rewards are the negation of those for player 1). Player 1’s information set relation is shown by dashed lines for selected nodes. The partitioning of the remaining nodes is determined by their positions in subtrees: if two nodes occupy the same position in two subtrees, and the roots of those subtrees are in the same information set as each other, then the two nodes are in the same information set as each other. The remaining nodes are partitioned in the obvious way. Player 2 has perfect information, i.e., her information sets are singletons. the rest of this paper, the word cheat refers specifically to observing information that is supposed to be hidden or uncertain, rather than any other violation of the game rules.) Cheating in this way is not a valid approach to AI for games of imperfect information, but it provides a useful benchmark for other algorithms since it is an approach which is expected to work very well compared to approaches that do not cheat. For fair comparison with our other algorithms, we consider two cheating UCT agents: one using plain UCT with a single search tree, and one using ensemble UCT [32] with several independent search trees whose root statistics are combined at the end of the search. As we will see, these are cheating versions of information set MCTS and determinized UCT respectively. D. Determinized UCT Our simplest noncheating agent uses a determinization approach, as described in Section III-B1. It samples a number of (not necessarily different) states from the current information set uniformly at random, constructs independently a UCT tree rooted at each of these states, and chooses a move for which the number of visits from the root, summed across all trees, is maximal. E. Single-Observer Information Set MCTS (SO-ISMCTS) To overcome the problems associated with the determinization approach, we propose searching a single tree whose nodes correspond to information sets rather than states. In single-observer information set MCTS (SO-ISMCTS), nodes in the tree correspond to information sets from the root player’s point of view, and edges correspond to actions (i.e., moves from the point of view of the player who plays them). The correspondence between nodes and information sets is not one–one: partially observable opponent moves that are indistinguishable to the root player have separate edges in the tree, and thus the resulting information set has several nodes in the tree. We address this in subsequent sections. Fig. 1 shows a game tree for a simple single-player game of imperfect information. The root information set contains two states: and . The player first selects one of two actions: or . Selecting yields an immediate reward of and ends the game. If the player instead selects , he must then select an action or .Ifthegamebeganinstate ,then and lead to rewards of and , respectively (this information being revealed by means of environment action or ); if the game began in state , then the rewards are interchanged. If states and are equally likely, action has an expectimax value of 0: upon choosing ,both and have an expectimax value of 0. Thus, the optimal action from the root is . However, a determinizing player searches trees corresponding to each state and individually and assigns aminimax value of in each (by assuming that the correct choice of or can always be made), thus believing to be optimal. This is an example of strategy fusion (Section III-B1). Fig. 2 shows the tree searched by SO-ISMCTS for this game. In this case, each node is in one–one correspondence with an information set. After a sufficiently large number of iterations the algorithm assigns each environment node an expected value of 0 and thus assigns the same value to action , thus overcoming strategy fusion and correctly identifying as the optimal move. Fig. 3 shows a game tree for a more complex, two-player game. The game starts in one of three states: ,,or .These states are distinguishable to player 2 but not to player 1. Player 1first selects an action or .Ifhechooses ,player2 then selects an action ,,or .However,onlytwoofthese actions are available, and which two depends on the initial state. Player 1 then selects or , and both players receive rewards as shown. Note that if player 2 chooses or ,thentherewards do not depend on the initial state, but if player 2 chooses ,then the rewards do depend on the initial state. Fig. 4(a) shows the tree searched by SO-ISMCTS for this game. For an information set where the observer is not the player about to act, i.e., ,theset of available actions can differ for different states .Theset of legal actions may depend on information to which another player does not have access. When searching trees of information sets, this creates a problem at opponent nodes. There must Figure 2.8: An example game tree for a simple 2-player game. Nodes shaped 4denote player 1 decision states, 5player 2 decision states, environment states, and terminal states labelled with reward values for player 1 (the game is zero-sum, so player 2’s rewards are the negation of those for player 1). Player 1’s information set relation is shown by dashed lines for selected nodes. The partitioning of the remaining nodes is determined by their positions in sub-trees: if two nodes occupy the same position in two sub-trees, and the roots of those sub-trees are in the same information set as each other, then the two nodes are in the same information set as each other. the remaining nodes are partitioned in the obvious way. Player 2 has perfect information, i.e. his information sets are singletons. [CPW12] COWLING et al.: INFORMATION SET MONTE CARLO TREE SEARCH 127 Fig. 4. An information set search tree for the game shown in Fig. 3. (a) The entire tree. (b) The restriction of the tree to determinization . Fig. 5. Information set search trees for the game shown in Fig. 3 with partially observable moves, where player 2 cannot distinguish from or from and player 1 cannot distinguish between ,and : (a) the tree searched by SO-ISMCTS; (a) and (b) the pair of trees searched by MO-ISMCTS, where (a) is from player 1’s point of view and (b) from player 2’s point of view. be a branch for every action that can possibly be available from that information set; this is illustrated in Fig. 4(a), where the opponent decision node has branches for all three actions , , even though only two of those three actions are available in each state , , in the corresponding player 1 information set. However, the exploitation and exploration of actions must be balanced with how likely those actions are to be available. For example, we wish to avoid overexploiting an action that is a certain win for the opponent but is only available with probability 1/100 (i.e., in only one of 100 states in the information set). To address this, at the beginning of each iteration, we choose adeterminization,andrestrictthatiterationtothoseregions of the information set tree that are consistent with that determinization. Thus, the branches at opponent nodes are available for selection precisely as often as a determinization is chosen in which the corresponding actionisavailable.Inotherwords, the probability of an action being available for selection on a given iteration is precisely the probability of sampling a determinization in which that action is available. The set of actions available at an opponent node can differ between visits to that node, and thus action selection is a subset-armed bandit problem (Section IV-B). Fig. 4(b) demonstrates such a restriction of the search tree shown in Fig. 4(a). High-level pseudocode for the SO-ISMCTS algorithm is presented in Algorithm 1. More detailed pseudocode is given in part A of the Appendix. In this and other pseudocode in this paper, it is assumed that player 1 is conducting the search. The pseudocode does not specify which bandit algorithm is used during selection. The experiments in this paper all use UCB modified for subset-armed bandits as described in Section IV-B, or EXP3 as described in Section III-C-I at nodes with simultaneous moves (which only occur in LOTR:C, Section V). Algorithm 1: High-level pseudocode for the SO-ISMCTS algorithm. More detailed pseudocode is given in part A of the Appendix. For the variant of this algorithm with partially observable moves (SO-ISMCTS+POM) simply replace the word “action” below with “move (from player 1’s viewpoint),” and see the more detailed pseudocode in part B of the Appendix. 1: function SO-ISMCTS Figure 2.9: An information set search tree for the game shown in (a) shows the entire tree; (b) shows the restriction of the tree to determinization x. [CPW12] ISMCTS works similar to pure UCT implementation: every node includes children for all possible moves at that game state, according to the available information sets. However, at each 19 Related Work iteration of the algorithm, a determinization is generated and the selection policy is then restricted to nodes that are coherent with the determinized state (visible in figure 2.9). Each node stores the number of times it was available during the selection policy, and UCB1 selection formula is modified to take into account the node availability count: Xi+Cslnn0 i ni(2.2) where n0 iis the number of times the child node was available after determinization, nithe number of times child ihas been visited, Cis a constant (higher than 0), and Xiis the average reward obtained after nisimulations from child i. Effectively, n, the number of times the parent node was visited is simply replaced by the child availability count. However, this means the selection of the most urgent child node is no longer identical to the multi-armed bandit problem: it is actually a variation where only a subset of the arms are available on each trial, named a subset-armed bandit. Whitehouse pointed out that the subset-armed bandit problem introduces some theorical issues with ISMCTS: the value of a move for an opponent may be different for each information set [Whi14, Chapter 5.2.1]. In cases with large number of information sets, it is assumed that the average value accross all opponent information sets can be used to measure the utility of an opponent move, but this leads to the inverse problem of strategy fusion, strategy fission, where the opponent is assumed not to be able to choose different actions depending on which information set they are in. Cowling et al experimented with the ISMCTS algorithm in different hidden information games, specifically the board game Lord of the Rings: The Confrontation (LOTR:C), Phantom (4, 4, 4) game and the chinese card game Dou Di Zhu [CPW12]. It is shown that ISMCTS significantly outperforms PIMC only in LOTR:C, and consistenly performs slightly worse than PIMC in the other domains. The authors conjecture that this discrepancy is due to the fact that ISMCTS can perform a deeper search in the same computational budget, since it utilizes a single tree. They conclude that domains where deep search is possible and beneficial or where strategy fusion is detrimental, ISCMTS will most likely offer a better performance. In domains where information sets have large numbers of legal moves and where the effect of strategy fusion is not clear (such as Dou Di Zhu), ISMCTS does not offer any immediate benefit over other determinization approaches. 2.5.3.1 Parallelization ISMCTS and other variants of MCTS, such as UCT can be enhanced to distribute processing power across multi-threading hardware environments, speeding up the overall decision process. However, there are multiple proposed enhancements to approach parallelization of MCTS, of which some are detailed as follows: 20 Related Work •Root Parallelization: multiple threads run MCTS independently from the same game state but with different random seeds, and the results for each root node are combined to determine the overall most visited node [CJ07]; •Tree Parallelization: a single tree is shared between threads, that add nodes and update node statistics. Thread safety is maintained using concurrency mechanisms to avoid writing at the same time in the same memory and also to avoid reading altered memory [CWH08]; •Tree Parallelization with Virtual Loss: a variation of Tree Parallelization to discourage selection of nodes that are currently locked by adding losses in the node statistics, reducing the time spent waiting for a lock; •Leaf Parallelization: a single tree is searched by a single master thread that orders worker threads to run simulations when a child node is selected. Sephton et al have experimented the use of these 4 enhancements in the strategic card game Lords Of War, both using PIMC and ISMCTS [SCPW12], and found that root parallelization is the most time efficient approach, but improvements were only visible up to 4 to 5 threads. Tree parallelization is less effective when applied to ISMCTS, possibly due to the large branching factor of the tree. The reasoning is that the root node has a bigger number of children (since ISMCTS has nodes for all possible moves given the information set) and thus more time is spent waiting for synchronization in the initial phase of the algorithm. 21 Related Work 22 Chapter 3 Trick Taking Card Games In this chapter, an introduction is made for all three proposed card games that are used in the experimental results. For each game, the rules are thoroughly explained and a quick analysis is done on possible playing strategies, for a better understanding of game mechanics. 3.1 Main Characteristics A simple standard deck of 52 cards allows to play a multitude of different games. However, many dificulties arise when attempting to classify card games [Par90, p.61-64]. A possible perspective for classification is to group games by their mechanism, i.e. what action is carried out when a player turn is up. This kind of classification can be useful when experimenting with adversarial search algorithms, since games with similar mechanics and branching factors can possibly benefit from the same algorithms and enhancements. As such, trick taking games consist of a category in mechanism classification, where each player in turn plays one card face up on the table, composing a trick. Many other subgroups can be descendants of this category, such as Point Trick Games, where the score won from a trick depends on each individual card value, and players attempt to maximize points won through collected tricks [Pag16b]. Most card games share two important characteristics: they are non-deterministic and of imperfect information, since the deck of cards is usually shuffled at the beginning of each game and players hide their cards from each other. In artificial intelligence research for games of imperfect information, good results have been achieved in trick taking card games such as Hearts [Stu08], Spades [WCPR13b], Skat [FB13] and Bridge [FB98]. However, many of these games feature bidding phases or simultaneous moves (such as passing cards and then performing a trick in Hearts). These situations add greater complexity and require specific algorithm enhancements and variations. For simplicity, only the simplest form of trick taking card games will be analysed in this dissertation, where players can only complete the current trick, without bidding or taking other possible lines of action, as is the case of the card game Sueca. 23 Implementation run out of certain suits, and near the end, despite having a low number of cards, the algorithm will likely spend more time generating invalid assignments, since many restrictions are set (e.g.: player 1 does not have spades, player 2 does not have diamonds, and so forth). These delay issues with determinization can be tolerable, but there are certain scenarios that can occur in the beginning of a game which completely halt the search algorithm: it is possible to shuffle the deck in such a way that the distribution of suits is very unbalaced. A simple scenario with four players would be as follows: •Player 1 is the current player and can lead the trick with a card of any suit; •Player 2 does not have spades but can have any other suit; •Player 3 does not have spades but can have any other suit; •Player 4 can have any suit; •Each player has 8 cards, and in Player 1’s perspective, there are 6 unknown cards of each suit (spades, diamonds, hearts and clubs). To generate a valid assignment, we must shuffle an array of 24 possible unknown cards. The first 8 cards of the array go to Player 2, the next 8 go to Player 3 and the last 8 cards go to Player 4. To create a valid assignment folowing this premise, the last 8 cards can not have a single spade. In short, there are 24P8∗16 P8∗8P8u6,204×1023 possible permutations, of which only 18P8∗10 P8∗8P8u1,291×1020 are valid. Using a uniformly distributed random number generator, this yields a success rate of about 1 4807, which means that on average we will require 4807 attempts to reach a single valid assignment. Also, we must bear in mind that an algorithm such as ISMCTS must generate a assignment for each iteration, and in the experiments we use 10 000 iterations as a standard. For this specific use case, it would require on average 48 070 000 array shuffles and validity checks. As such, a new approach is required to quickly generate valid card assignments that make up a uniform sample from the set of all possible assignments, i.e. not biasing the generation of specific card assignments. As such, an approach is proposed to handle the generation of valid card assignments, without exploring the invalid search space. 4.1.0.1 Randomize non-deterministic game states in card games In the beginning of a Sueca game, the playing deck usually starts with 40 unique cards, and 4 players. The following notation is used: •Xiis a vector of cards that represents the player ihand. Cards contained in this vector may be known or unknown from the current player’s perspective; 30 Implementation Let the following be true: •C=K∪U, in the perspective of a single player, the total set of cards Cis composed by the subgroup of cards K(known cards) and U(unkown cards). Every card c∈Uis held in the hand of the other players and is concealed from the player perspective. •Poss(Xi,c) = 0∨1, the possibility of player hand Xito contain card ccan be represented by 0 (impossible) or 1 (possible). In other words this represents if c∈Xi. The objective then is to assign every card in Uto all unknown Xi. This is similar in nature to the assignment problem of Operations Research. However, instead of generating a single valid assignment in a deterministic manner, we must sample a variety of possible assignments in an uniform way. To run the algorithm, an input matrix with the possibilities associated with the problem must be elaborated as follows: •The rows correspond to Xi, which is the hand of player i •The columns correspond to a card cto assign •Each cell represents the value of Poss(Xi,c)(the possibility of c∈Xi) As an example, if we are trying to assign six cards to three different players, where we are Player 1, Player 2 has no restrictions, Player 3 can not have cards of the hearts (♥) nor diamonds (♦) and Player 4 can not have spades (♠), then we have the following possibility matrix: M1=   A♥7♥K♠Q♠J♠2♦ X21 1 1 1 1 1 X30 0 1 1 1 0 X41 1 0 0 0 1    To solve this, we start by summing the columns and rows: •The sum of a column represents how many players can a specific card be assigned to. If there is a column for which the sum is equal to 1, this means the card can only be held by one player, and should thus be immediately assigned (e.g.: between three players, only one can possibly hold this specific card); •The sum of a row represents how many possible cards the player can receive, to which we can subtract the amount of cards a player still needs to receive (cards left to assign). If the result is equal to 0, then all cells with value of 1 in that row represent cards that should be immediately assigned to the respective player (e.g.: there are only 2 possible cards that player might hold, and we still need to assign 2 cards to him). 31 Implementation Taking both sums and cards left for each player, we have the following: M2=      A♥7♥K♠Q♠J♠2♦RowSum−CardsLeft X21 1 1 1 1 1 6−2 X30 0 1 1 1 0 3−2 X41 1 0 0 0 1 3−2 ColSum 2 2 2 2 2 2       Since there is no ColSum =1 nor RowSum −CardsLeft =0, we must start to assign cards to certain players randomly. However, we must not assign a card that would compromise the restrictions of another player. Using the matrix above as an example: if we began by choosing A♥ and 2♦for X2and then K♠and Q♠for X3, we would reach a dead end: only 7♥and J♠are left for X4, but this player can not have spades. To avoid situations where restrictions are broken, we follow a simple rule of thumb: always start by assigning cards to the most restricted players. With the example matrix above: X2needs 2 cards and has 6 possibilities, X3and X4need 2 cards and have 3 possibilites. This means that X3 and X4are the most restricted players (RowSum−CardsLeft =1, which is the minimum current value). After choosing one of these players randomly, we then have to pick a random card where P(Xi,c) = 1. As an example, by picking X3: we have the following choices: [K♠,Q♠,J♠]. If we would then choose K♠we would have the following matrix (notice that the K♠column is now 0 filled and Cards Left for X3decreased by 1): M3=      A♥7♥K♠Q♠J♠2♦RowSum−CardsLeft X21 1 0 1 1 1 5−2 X30 0 0 1 1 0 2−1 X41 1 0 0 0 1 3−2 ColSum 2 2 0 2 2 2       Applying the same rule as before, we choose between X3or X4. Assuming we assign randomly Q♠to X3, we have the next matrix (notice that X3is now a 0 filled row: he can no longer hold any other card): M4=      A♥7♥K♠Q♠J♠2♦RowSum−CardsLeft X21 1 0 0 1 1 4−2 X30 0 0 0 0 0 0−0 X41 1 0 0 0 1 3−2 ColSum 2 2 0 0 1 2       32 Implementation Now we see that ColSum(J♠) = 1. This means that J♠can only be held by one player, which is X2, so we must assign it immediately, leading to the following matrix: M5=      A♥7♥K♠Q♠J♠2♦RowSum−CardsLeft X21 1 0 0 0 1 3−1 X30 0 0 0 0 0 0−0 X41 1 0 0 0 1 3−2 ColSum 2 2 0 0 0 2       We should now choose player X4, and we can randomly assign A♥to him, leading to: M6=      A♥7♥K♠Q♠J♠2♦RowSum−CardsLeft X20 1 0 0 0 1 2−1 X30 0 0 0 0 0 0−0 X40 1 0 0 0 1 2−1 ColSum 0 2 0 0 0 2       Now we can choose between X2or X4. Let’s assign X2with 7♥, leading thus to the final assignment of 2♦to X4.: M7=      A♥7♥K♠Q♠J♠2♦RowSum−CardsLeft X20 0 0 0 0 0 0−0 X30 0 0 0 0 0 0−0 X40 0 0 0 0 1 1−1 ColSum 0 0 0 0 0 1       Following these steps guarantees that we will never assign a card that would eventually be required by another player: we always start with the column that has the least possibilities, and if a situation arises where a card can only be held by a single player, then it is automatically assigned. One can argue that this approach does not generate samples in a randomly uniform way due to certain branching decisions: in M4we were forced to choose only one card because of the decision we took before on M3. If we were to choose a different card in M3then another decision branch would occur in M4. Since we are always starting with the most restricted players, the least restricted ones might only reach certain combinations of cards through multiple previous decisions in the restricted players, making these combinations rarer. However, we must take into account that the order of assignments is irrelevant, and that the search space can be so vast that 10 000 randomizations would not be enough to bias a distribution space of over 1×1020 possibilities. With these aspects in mind, it is possible to assume that even if some bias toward certain combinations occurs, it would be negligible compared to the strenghts of this approach: it is guaranteed that we reach a valid distribution in only one attempt, so we have a clear upper bound on the worst case scenario, making it on average faster than the pure random Accept-Reject approach. Another positive aspect is that it only uses simple matrix operations. 33 Implementation Algorithm 1 Pseudocode of proposed Uniform Assignment Sampling with Restrictions Algorithm 1: function ASSIGNWITHRESTRICTIONS(unknownCards,players) 2: possibilityMatrix ←GENERATEPOSSIBILITYMATRIX(unknownCards,players) 3: for each index in [0,size of unknownCards]do 4: if the sum of a column in the matrix is equal to 1 then 5: select card of the respective column to the only player where the cell value =1 6: ASSIGNCARDTOPLAYER(card,player,possibilityMatrix) 7: else 8: randomly select a player where (rowSum−playerCardsLeft)is min. and >0 9: choose a random card from the player’s respective row, where the cell value =1 10: ASSIGNCARDTOPLAYER(card,player,possibilityMatrix) 11: return players with assigned cards 12: 13: function GENERATEPOSSIBILITYMATRIX(playerHands) 14: initialize matrix with size (players∗unknownCards) 15: for each card in unknownCards do 16: for each player in playerHands do 17: select cell in matrix where col =cardIndex and row =playerIndex 18: if player has unknown cards in hand and might hold card by the game rules then 19: set selected cell value to 1 20: else 21: set selected cell value to 0 22: return matrix 23: 24: function ASSIGNCARDTOPLAYER(card,playerHand,matrix) 25: decrease playerCardsLeft by 1 26: zero all elements in the respective card column 27: if playerCardsLeft =0then 28: zero all elements in the respective player row 29: return updated matrix 34 Implementation Table 4.1: Comparison of samples generated with the proposed generator approach versus acceptreject method, using a Chi Squared test with H0=sample is uniform and H1=sample is not uniform. Distribution Expected Accept-Reject Proposed Approach h2♦,J♠i,hK♠,Q♠i,h7♥,A♥i 1111 1113 1117 h2♦,K♠i,hJ♠,Q♠i,h7♥,A♥i 1111 1087 1114 h2♦,Q♠i,hJ♠,K♠i,h7♥,A♥i 1111 1130 1114 h7♥,J♠i,hK♠,Q♠i,h2♦,A♥i 1111 1137 1114 h7♥,K♠i,hJ♠,Q♠i,h2♦,A♥i 1111 1129 1099 h7♥,Q♠i,hJ♠,K♠i,h2♦,A♥i 1111 1102 1118 hA♥,J♠i,hK♠,Q♠i,h2♦,7♥i 1111 1097 1119 hA♥,K♠i,hJ♠,Q♠i,h2♦,7♥i 1111 1113 1111 hA♥,Q♠i,hJ♠,K♠i,h2♦,7♥i 1111 1092 1094 χ20 2.3246 0.548 d f 8 8 8 p-value 0 0.9694 0.9998 Reject H0? (p-value <0.05) no no no A simple experiment can be conducted to analyse a sample that was produced from both random generators and check if it is uniform. Using the specific example matrix presented previously, where the search space is relatively small (only 9 possibilities), we can check if there is any bias directed toward specific assingnments. For these trials, a sample of 10 000 distributions was created using each generator. A Chi squared test was performed, considering that H0=sample is uniform and H1=sample is not uniform. The results are visible in Table 4.1 and demonstrate that we can not reject the null hypothesis for both samples, which means that we can not state, with a 95% confidence interval, that both generators did not generate a uniform sample (at the 0.05 significance level). The previous experiment only verified if a single sample from each generator is not uniform, and it can be the case that those samples were favourable by luck. To verify if the generators are consistent over a large number of samples, we now repeat the previous experiment 1000 times with the same sample size of 10 000 assignments. Results in table 4.2 show that both generators do not create perfectly uniform samples, since we can reject the null hypothesis in about 4.5% of samples for each one. Note that both generators give reasonably the same results, which is the most important aspect to take into account: the new proposed approach seems to have the same behaviour as the accept-reject method. However, this is not actual proof that both generators are uniform, it is a simple experiment to assess if both produce good enough results so that assignment bias does not become a significant issue in the determinization process. Theoretical proof to justify that the generator is uniform will be considered as future work. However, we will propose some reasoning to support the hypothesis that samples are generated in a uniform way through the proposed algorithm: 1. Firstly, when applying the algorithm, we must assume there is at least one possible valid assignment for a given list of cards and players; 35 Implementation Table 4.2: Uniform Sampling analysis with Chi Squared test for each 1000 samples, with each sample of size 10 000 Approach Rejected H0Rejected H0Rejected H0Samples Generated Accept-Reject 44 8 0 1000 Proposed Approach 46 5 0 1000 Significance Level 0.05 0.01 0.001 2. The order of card assignment does not change the set of possible assignments. With the notation [X7→N], where card X is assigned to player N, from a possible set of cards [A,B,C,D] to assign players [1,2], choosing the assignment order [A7→1,B7→1,C7→2,D7→2]yields the same result as [C7→2,D7→2,A7→1,B7→1], since player 1 is assigned with [A,B]and player 2 with [C,D]; 3. Given 2., it is possible to choose any order of card assignments to reach the full set of all possible assignments; 4. The proposed algorithm provides an order of card assignments that is guaranteed to always terminate in a number of iterations equal to the count of unknown cards; 5. When the algorithm reaches a non-deterministic assignment decision, it determines the choice using uniform random number generators; 6. By making random uniform decisions regarding the selection of individual card assignments, we achieve an overall general assignment that was uniformly sampled. 4.1.0.2 Biasing randomized game states based on game knowledge Although it is important to achieve uniform samples of deterministic game states, there are certain use cases where bias can be of use. In a Sueca game, if the player always followed the suit that started the trick, then by the game rules, the player might still hold any specific card of that suit. But we might be perceptive of clues that indicate the player actually does not have that suit. Imagine the following situation in the start of a Sueca game: the trick started with Player 1 pushing an A♣. Player 2 played a low card, 2♣, Player 3 played a high card J♣. The last player was going to lose the round, but still played a card that gave his adversaries 2 points: the Q♣. This gives us two possible assumptions: either Player 4 has cards of clubs (♣) with a higher value than a Queen, or he does not have any card left of that suit (assuming that Player 4 played rationally and is not bluffing). This is actually a lot of information: the remaining cards of clubs above a Queen are K♣and 7♣. If we are Player 1 and hold the 7♣, we can ascertain with a degree of confidence that Player 4 does not hold any clubs other than the King. As such, if we generate samples of assignments that are biased toward Player 4 not having any clubs lower than a Queen, we are selecting a more probable reality according to game rules and rationality, which then significantly narrows the determinized MCTS search space. However, we should not simply reuse the previous algorithms using a possibility equal to 0, since Player 4 can actually be bluffing 36 Implementation or playing irrationaly. As such, we can not be 100% sure of our assumptions, but can have a certain degree of belief. To support this type of sample bias towards player having certain cards, it is possible to modify the Accept-Reject method. We can increase rejections by adding another validity check: if a card was assigned with low odds of belonging to a player, we can reject the whole assignment with a certain probability. However, this increases the number of rejections, leading to a more delayed and troublesome execution. However, the proposed sampling algorithm referenced in section 4.1.0.1 can be easily adapted to bias certain card assignments, with little overhead to the algorithm. Instead of generating a possibility matrix, we create a probability matrix, where each cell specifies in a range of [0,1] the belief that a certain player holds a specific card. When summing the values inside a row or column, we must take into account that if a number is higher than 0, it should count as a 1. After selecting a player row, in order to choose the card to assign, we select one of the possible cards based on their odds. For example, a card with 0.8 has higher odds of selection than another with 0.4, but both are still valid options. This means that instead of making random uniform individual decisions (probability equal to all choices), we bias some individual card assignments with a higher probability. Although this proposed alternative has some potential, specific domain knowledge is required in order to use it: taking into account the previous example, the Sueca implementation needs to provide heuristics that determine odds of each player possessing certain cards. While the study in this dissertation is more toward aheuristic enhancements, this approach might be useful for researchers looking into enhancements tailored for just a specific game. 4.2 Botwars Framework In this section, an overall description and architecture overview will be given on the framework used to conduct experiments throughout this dissertation. The Botwars framework was developed by Rui Gonçalves [Gon16] to handle communication between different AI agent implementations, allowing such agents to challenge each other in a myriad of unique games. The framework offers a web app client for game visualization in real time and also enables interaction between human players and the developed AI programs. The framework also serves as an orchestrator for automated competitions between different agents, allowing to set up and monitor a long running number of games, in order to assess the relative efficiency of each agent. Some open source contributions were done throughout this dissertation to enable database storage support, facilitating the distribution of experimental results in a transparent and verifiable way. Whenever a competition is carried out, all game state changes are stored in a document oriented database (for this specific case, Couchbase). This means that the experimental results are simply database backups that can be shared and restored by any user. This allows for every agent action and game state to be fully queriable through a SQL-like language (N1QL), enabling any 37 Implementation user to aggregate and analyse results with custom perspectives, without requiring experiments to be re-run. After restoring a database, the framework can reload the stored states, allowing for total inspection down to every single move of each played game, through the web client. If agents store the necessary data to replay a move (e.g.: random number generators state), then stored moves can be replayed in a deterministic manner, allowing to inspect data structures created by the algorithms (e.g. search trees) and debug any errors or exceptions. The framework is not specifically tailored to card games, as any discrete and sequential game can be supported. To implement a new game, a developer must create two different files: the game logic class and the rendering logic class. The game logic class must override specific inherited functions such as: •isValidMove: check if a given move can be applied by the next player in the current game state; •move: apply a given move to the current game and return the resulting new game state; •isEnded: check if game is over; •getNextPlayer: return the next player that must perform an action in the current game; •getWinners: if the game is over, return the players that won the game; •getFullState: return all state variables from the current game state; •getStateView: return variables visible to a specific player (e.g.: hide hands of other players in a card game). Afterwards, the rendering logic class must be able to receive any given game state (returned by getStateView) and draw the game with HTML and CSS (in this specific case, React framework is used to facilitate DOM manipulation). With both game logic and rendering implemented, the framework then handles the remaining work: it exposes a REST API that agents must communicate with, in order to find and register in hosted games or competitions. After the registration is done, the server opens a websocket connection with each agent and constantly sends events, such as announcing when the game starts, what actions the other players performed, what is the current game state in the perspective of each agent, and also querying each client for the move he wishes to apply (validating everything in the process, to avoid reaching invalid game states). As such, a developed agent program must simply create an interface of communication that sends HTTP requests in order to find and register in a competition, and then use a websocket library for listening and reacting to events sent by the server. The resulting work gives some advantages to AI developers. Much of the synchronization between agents as well as game setup is automatically handled by the framework, and running experiments simply involves creating scripts to boot the application, backup and clean the database, and then spawn the amount of agents required to play. It allows developers to choose whichever 38 Implementation Figure 4.1: The botwars client UI while playing a Sueca game. programing language they find most adequate to implement their agents, and offers a simple UI for users to play and see competition results. 4.3 MCTS Framework for Trick Taking Card Games In this section, an overview will be given of the AI agent framework developed specifically for the work carried out in this dissertation [Fer16], that integrates with the Botwars framework described in section 4.2. The main focus of the MCTS framework is to offer different algorithm implementations and allow runtime modification of core steps through initialization parameters. The framework also facilitates move replayability, enabling deterministic debugging and offering a search tree visualization tool for further inspection on a move decision. The distribution of source code and datasets generated from all conducted experiments is a critical step towards Reproducible Research. This term refers to the idea of publishing papers that are product of academic research along with the full computational environment used to produce the experimental analysis, such as the source code, datasets, scripts and any other required tools [FC09]. This enables other researchers to reproduce the results and create new work based on the existing research. Note that most papers cited throughout this work do not share the necessary 39 MCTS Algorithms applied to Trick Taking Card Games To calculate the state space, we must consider the order of cards in the deck. As such, the first player receives 9 cards out of 40, the second gets 9 cards out of 31, and the remaining 22 are in the deck, where the order of cards is important to the gameplay. Thus, we have the following number of possible assignments: 40 9×31 9×22! u6.20×1036 5.2 ISMCTS Information Set MCTS was proposed by Cowling et al [CPW12], and the algorithm offers an approach that directly handles the issue of stochastic events, while mitigating the effect of strategy fusion. There are different variations of ISMCTS that are suited to support partially observable moves, however, the chosen experimental games do not have these particular moves (note that in Hearts, card switching was simplified), and as such only the standard Single Observer ISMCTS (SO-ISMCTS) is used, which is detailed in algorithm 3. The notation used in the pseudocode is as follows: •f(d,a)returns the determinization d0reached by applying action ato determinization d (state transition function); •For each node vthere is an associated state sv, the incoming action av, the total simulation reward Q(v), the visits count N(v), and the child nodes c(v) •∆is the reward vector for a finished game; ∆(v)is the reward for the player that performed action av; •cis a factor of the standard exploration constant, i.e. with c=1.0, the exploration constant is equal to 1/√2; •A(d) = set of possible moves in determinization d; •IS0=the current game information set, i.e. the set of all possible states in which the game can be, given the player’s observed information; •N0(v) = availability count for node v; •c(v,d) = {v0∈c(v):av0∈A(d)}, the children of vcompatible with determinization d; •u(v,d) = {a∈A(d):@v0∈c(v,d)with av0=a}, the actions from dfor which vdoes not have children in the current tree. Note that c(v,d)and u(v,d)are defined only for vand d such that dis a determinization of (i.e., a state contained in) the information set to which v corresponds. 46 MCTS Algorithms applied to Trick Taking Card Games Algorithm 2 The UCT Algorithm 1: function UCTSEARCH(s0) 2: create a root node v0with state s0 3: while within computation budget do 4: vl←TREEPOLICY(v0) 5: ∆←DEFAULTPOLICY(svl) 6: BACKUP(vl,∆) 7: return a(BESTCHILD(v0,0)) 8: 9: function TREEPOLICY(v) 10: while vis nonterminal do 11: if vnot fully expanded then 12: return EXPAND(v) 13: else 14: v←BESTCHILD(v,c) 15: return v 16: 17: function EXPAND(v) 18: choose a∈untried actions from A(sv) 19: add a child v0to v 20: sv0←f(sv,a) 21: av0←a 22: return v0 23: 24: function BESTCHILD(v,c) 25: return arg max v0∈children of v Q(v0) N(v0)+cq2lnN(v) N(v0) 26: 27: function DEFAULTPOLICY(s) 28: while sis nonterminal do 29: choose a∈A(s)uniformly at random 30: s←f(s,a) 31: return reward for state s 32: 33: function BACKPROPAGATE(v,∆) 34: while vis not null do 35: N(v)←N(v)+1 36: Q(v)←Q(v)+∆(v) 37: v←parent of v 47 MCTS Algorithms applied to Trick Taking Card Games The tree complexity of ISMCTS is significantly higher because using information sets implies consideration of all possible moves at any given point, with the known information at hand, leading to large branching factors. In Determinized UCT, all other player cards were visible, and thus, at most 10 different moves could be played by all adversaries. In the case of ISMCTS, each adversary has the possibility to use any unknown card in game at that point, which means that in the beginning of a game, an adversary can have at most 30 different possible moves. By analysing tree complexity of ISMCTS when applied to Sueca, there are 10!·30! =9.63×1038 leaf nodes. At the first branch, the root player knows his cards, therefore there are 10 possible branches. At the second branch, the next player can play at most 30 different moves, since there are 30 unknown cards at that point, from the root player perspective. Analogously, the third and fourth branch will have 29 and 28 available moves. The fifth turn belongs to the root player again, now with 9 possible moves. The next branches will have 27, 26 and 25 available moves, and so on until the end. Note that we consider the root player always as the leading player in every trick, but the order of play is irrelevant to the final calculation. To calculate the number of total nodes in the tree, we can use a formula similar to the one in section 5.1, that summed the total number of nodes at each depth level in the tree: 1+ 10 ∑ i=1 4 ∑ j=1 10 ∏ x=i x30 ∏ y=3(i−1)+j y=2.78×1039 Note that when i=10∨j=4⇒y=31, resulting in ∏30 y=31 y=1. This is intended behaviour for the first level of depth, since the iteration with i=10∨j=4 yields 10·1, which corresponds to the 10 initial possibilities of the root player. To demonstrate how this formula will develop, we calculate the number of nodes in the tree up to the seventh level of depth, with each level in parenthesis (starting with i=10 and j=4, both in a decreasing order): (1)+(10)+(10·30)+(10·30·29)+(10·30·29·28)+(10·30·29·28·9)+ +(10·30·29·28·9·27) = 61 639 811 When applying ISMCTS to Sueca, leaf nodes represent 34.64% of the total nodes, with a tree depth of 40, and EBF of 9.66. The state space of the game is not going to differ when compared to Determinized UCT, but we can obtain the Information-Set Space (ISS) by multiplying the number of initial states with the total number of nodes in the ISMCTS tree, thus totalling 2.78×1039 ·4.71×1021 =1.31×1061 information sets. It is important to note that the calculated values are exact and not upper bounds on the tree size, even considering the rule that players must follow the leading suit if possible. As an example, imagine the first move were the root player leads with an A♠. Considering the current information set, the next player might have spades or not, and as such, any card from the full set of 30 unknown cards can actually be played in that specific moment. Odds might tell that not having spades in the first round is an unlikely event, but it is still a possibility in the current information set. The calculations for Hearts are the same as Sueca, with the number of cards changing from 10 to 13. However, Bisca needs an adaption for the 11 initial rounds, where two players always 48 MCTS Algorithms applied to Trick Taking Card Games Table 5.2: Complexity values of ISMCTS search algorithm applied to Sueca, Hearts and Bisca. Game ISS Tree nodes Leaf nodes Tree depth EBF Sueca 1.31×1061 2.78×1039 9.63×1038 40 9.66 Bisca 2.01×1073 3.25×1036 8.39×1035 40 8.15 Hearts 1.97×1085 3.67×1056 1.27×1056 52 12.22 start with 9 cards each. The initial trick outcomes are 9·31, since there are 31 unknown cards. The second trick is 9·29, as one card is revealed from the adversary, and another is taken from the deck. Repeating this until the 11th round, we have 911 ·∏11 x=1(9+2x)possible outcomes. After this point, each player can deduce what cards the other has, since there are 9 unknown cards, and the adversary holds 9 cards. Both play a card per trick, translating into (9!)2different outcomes. The final result gives the amount of leaf nodes: 911 · 11 ∏ x=1 (9+2x)·(9!)2=8.39×1035 To calculate the total amount of nodes in the tree until the deck runs out, we must develop the following sum of nodes at each depth level: (1)+(9)+(9·31)+(9·31·9)+(9·31·9·29)+... And the total node count for the full tree can be formulated as: 1+ 11 ∑ x=1 9x·11 ∏ n=13−x (9+2n)+ 11 ∏ n=12−x (9+2n)+ 9 ∑ x=1( 9 ∏ t=x+1 t)2·(x+x2)·(911 · 11 ∏ n=1 (9+2n)=3.25×1036 Where the first summand is the root node, the second corresponds to the 11 first tricks (while the deck is not empty), and the last summand returns the remaining 9 tricks. Note that when x=9⇒t=10, resulting in ∏9 t=10t2=1, and also when x=1⇒n=12, giving ∏11 n=12(9+2n) = 1. Both are intended behaviour to calculate the initial move in each phase. 5.3 Reward Functions For every MCTS algorithm, the reward function is a very important component of the UCT formula, which guides the search toward the most promising moves. By changing the definition of reward achieved by a simulated finished game, we effectively alter what is the search notion of the best move. As such, three different reward functions are proposed as follows: 49 MCTS Algorithms applied to Trick Taking Card Games Algorithm 3 ISMCTS 1: function ISMCTS(IS0,n) 2: create a single-node tree with root v0corresponding to IS0 3: for n iterations do 4: d0←randomly choose determinization from IS0 5: (v,d)←SELECT(v0,d0) 6: if u(v,d)6=/0 then 7: (v,d)←EXPAND(v,d) 8: ∆←SIMULATE(d) 9: BACKPROPAGATE(r,v) 10: return acwhere c∈arg maxc∈c(v0)N(c) 11: 12: function SELECT(v,d) 13: while dis nonterminal and u(v,d) = /0 do 14: for all v0∈c(v,d)do 15: N0(v0)←N0(v0)+1 16: v←BESTCHILD(v,d,c) 17: d←f(d,av) 18: return (v,d) 19: 20: function BESTCHILD(v,d,c) 21: return arg maxv0∈c(v,d)Q(v0) N(v0)+cq2lnN0(v0) N(v0) 22: 23: function EXPAND(v,d) 24: choose a∈u(v,d)uniformly at random 25: add a child v0to v 26: av0←a 27: d←f(d,a) 28: return (v0,d) 29: 30: function SIMULATE(d) 31: while dis nonterminal do 32: choose a∈A(d)uniformly at random 33: d←f(d,a) 34: return reward for state d 35: 36: function BACKPROPAGATE(v,∆) 37: while vis not null do 38: N(v)←N(v)+1 39: Q(v)←Q(v)+∆(v) 40: v←parent of v 50 MCTS Algorithms applied to Trick Taking Card Games •Positive Win or Loss (PWL) is the standard definition of reward used by UCT Search. If a player is the winner of a simulated game, then the reward is equal to 1, otherwise a loss is valued as 0. Ties are counted as 0.5. Note that the UCT formula also takes into account the number of times a node was visited (effectively, the number of simulations that took place after the move associated to the node was selected). This means that the reward component of the UCT formula for a given node will equal to the average win rate achieved by simulations from the node and its children. •Win or Loss (WL) gives negative weight to losses. Simulated game victories count as 1, but losses will incur a penalty of -1, while ties are equal to 0. This may not seem very different between PWL, but the exploitation component of the UCT formula will now be equal to: wins−losses wins+losses+ties. As such, moves that yield more losses than victories will have a negative reward. Moves with a higher win to loss ratio are positively rewarded, but note that the overall reward is lesser in the exploitation component of the UCT formula, compared to PWL. This gives more weight to the exploration component, favouring less tried moves until a significant win to loss ratio is found, and thus an experimental analysis is required to find a proper exploration constant. •Score Difference (SD) is a measure of score difference between the winner and player. For the case of Sueca, wins are ranked as three different outcomes: normal victory (over 60 points equals 1 match point), a significant win (over 90 points equals 2 match points) and total victory (120 points equals 4 match points). We can apply this same victory scale logic to Bisca, since both scoring systems are very similar. However, in order to adapt this reward logic to Hearts, the difference between player and winner score is also discretized into values of [-4, -2, -1, 0, 1, 2, 4], with 4 being the best possible score, corresponding to 0 points in difference (i.e. the player is also the winner), and -4 is the worst score, corresponding to -26 points in difference (i.e. the winner scored 0 while the player has 26 points). Having a score difference higher than −13 points yields a positive reward. The full table of scores difference is shown as follows (each cell contains the value or range of winner score−player score): Reward -4 -2 -1 0 +1 +2 +4 Sueca -120 [-118, -62] [-60, -2] 0 [+2, +60] [+62, +118] +120 Bisca -120 [-118, -62] [-60, -2] 0 [+2, +60] [+62, +118] +120 Hearts -26 [-25, -19] [-18, -13] -13 [-12, -7] [-6, -1] 0 51 MCTS Algorithms applied to Trick Taking Card Games Note that this may not be the most adequate reward function for both Bisca and Hearts, since there is no scoring system that values results as 1, 2 or 4. However, if we used the actual score difference instead, we would see maximum score differences of 120 in Bisca and 26 in Hearts, which would require experimentation with very high values of the UCT exploration constant, complicating the experimental analysis setup. As such, having the reward function return discrete values in the range of [−4,4]for all three games allows to test similar exploration constants, and the discretization of scores will not greatly harm the overall perception of reward. 5.4 NAST Simulation Enhancement The N-gram average sampling technique was first proposed by Powley et al [PWC13] and builds upon previous work by Stankiewicz et al [SWU12] and Tak et al [TWB12]. In the context of games, an N-gram is a sequence of N consecutive actions (for the case of card games, N consecutively played cards). The enhancement works by learning a value for each sequence of moves, independent of the context in which they are played. With specific selection policies, the learned sequence evaluations are used to sample more successful moves during the MCTS simulation step. A sequence of 1 action is simply the move itself and using n-grams of this length effectively is the same as applying the Move-Average Sampling Technique (MAST) [FB10], which evaluates the quality of a single move, independent of when it is applied in a game. Using n-grams of N=2 can be thought of as a generalisation of the last good reply principle [Dra09], since evaluating the average reward for any given sequence of actions ha1,a2iwill indicate if a2is a good reply to a1. In more general terms, the average reward for an n-gram ha1,...,an−1,aniindicates whether action anis a good response to ha1,...,an−1i. When applying this concept to trick taking card games, it makes some sense that there is a good reply to any given trick. For example, in Sueca, the sequence of actions hA♠,7♠i is generally considered as a bad move, independent of when it is applied, since teams play in alternating turns, and the 7 loses to the Ace. There can be situations where the trick can still be won, but this reply is considered as very risky and should be avoided. However, the sequence hK♠,7♠i might not be necessarily good: there can still be an Ace of Spades in play that would overthrow the trick and make the player lose points. If this is the case, then for example hK♠,7♠i will likely have negative reward when h7♠,A♠i occurs next in the simulation. As such, a reply is choosen by the move sequence, but there is still some notion of context, since later sequences in the simulation will likely affect the reward obtained by previous ones. Note that a sequence can occur in any step of the game, which means that it might be composed of moves from different tricks. During the backpropagation phase in MCTS, the full sequence of moves from the root node down to last move of the finished simulated game is split into n-gram sequences of Nlength. For each sequence, the reward function used by MCTS gives the result obtained in the finished game relative to the player that performed the last move in the sequence. This calculated reward is then 52 MCTS Algorithms applied to Trick Taking Card Games stored in a table of sequences for a specific player, where any given sequence corresponds to a number of times it appeared and total obtained reward from all appearances. During the simulation phase of MCTS, a move is not randomly picked from the list of all possible moves to apply. Instead, each possible move is concatenated with the previous N−1 moves that occured in the simulated game, generating a list of possible sequences with Nlength. A simulation policy determines what is the most promising sequence in the list so far, and applies it in the simulated game. This step is iteratively performed until the simulation ends. 5.4.1 Simulation Policies There are multiple policies with different criteria for selecting the most adequate move to apply next in any given step of a simulation. These policies are not strictly related to NAST and ngram sequences, as they can be applied with any set of actions A(s), where each action ahas the following information: •Q(a) = the total reward achieved by applying action a; •N(a) = the total number of times action awas applied A policy yields a probability distribution πover A(s). As such, a random uniform number generator must be used to sample an action awith probabilities π(a). Note that a MCTS simulation policy should strike a balance between the exploitation of good actions with exploration of other actions, in order to ensure the simulation reward accurately reflects the game theoretic value. With the notation detailed so far, the following policies are described as follows: •Gibbs distribution sampling is the original formulation proposed by MAST [FB08] and defines the simulation by means of a Gibbs distribution: π(a) = expQ(a) N(a)/τ ∑b∈A(s)expQ(b) N(b)/τ(5.1) Where τ>0 is considered as a factor of greediness because as τ→0, the policy will give higher probabilities to actions with maximal reward Q(a) N(a), and as τ→∞, the probabilities all become equal. As such, the value of τmust be tuned through experimentation. Powley et al tested values of τ∈{0.05,0.1,0.15,0.2,0.25,0.5,1,1.5,2,4}, and found τ=1 gave strongest play in Hearts and Dou Di Zhu [PWC13]. •ε-greedy is proposed by Tak et al [TWB12] as an alternative simulation policy for MAST. Let Amax be defined as the subset of A(s)for which reward is maximal: Amax =arg max a∈A(s) Q(a) N(a)(5.2) 53 MCTS Algorithms applied to Trick Taking Card Games The policy is then defined by: π(a) =    1−ε |Amax|if a∈Amax ε |A(s)|−|Amax|if a/∈Amax (5.3) In this policy, εis a tunable greedy factor, with values between [0,1]. The action of maximal reward is choosen with a probability of 1−ε, or any other action with probability of ε. With ε=0, the policy always chooses the action of maximal reward, while ε=1 gives an uniform random sampling. Powley et al tested values of ε∈{0,0.1,0.2,0.3,0.4,0.5,0.6}and found ε=0.2 to be best for Hearts and Dou Di Zhu [PWC13]. •Roulette Wheel selects moves with a probability proportional to the average reward of each action. It has no tunable parameters and is defined as: π(a) = Q(a) N(a) ∑b∈A(s) Q(b) N(b) (5.4) •UCB1 can be applied to balance exploitation of high reward actions with the exploration of less explored actions without requiring random sampling. As such, let Aucb be the subset of A(s)for which the UCB1 value is maximal: Aucb =arg max a∈A(s)Q(a) N(a)+csln∑b∈A(s)N(b) N(a)(5.5) The simulation policy is given by: π(a) =    1 |Aucb|if a∈Aucb 0 if a/∈Aucb (5.6) That is, an action that yields maximal UCB1 value is choosen uniformly. By adjusting the exploraction constant c, the search will tend toward moves that are unexplored, and if c→∞, all actions with less N(a)will be selected uniformly, independent of their reward. Powley et al tested values of c∈{0.2,0.5,0.7,1.0}and found c=0.7 to be best for Hearts and Dou Di Zhu [PWC13]. 54 MCTS Algorithms applied to Trick Taking Card Games 5.5 Minimax Minimax can not be directly applied to games of imperfect information. However, there are variations such as Expectimax that handle situations of stochastic nature, by introducing the concept of chance nodes at any given point in the search tree. For the case of all three trick taking card games, the only chance event happens in the game start, where the card deck is shuffled. Assuming the deck is shuffled in a uniform way, every possible card distribution has an equal chance of appearing. This means that applying Expectimax at the root node is actually the same as using Determinized Minimax, also known as PIMC coupled with minimax, similar in nature to the Determinized UCT described in section 5.1. All possible card assignments are generated, and a minimax search is run on each version of the game where all player cards visible (note that this way, certain optimizations such as αβ-pruning can be applied). Each search returns the best move for that given game, and counts as a vote for the best overall move. Once all searches end, the most voted move is returned. Note that this strategy suffers the same effects as Determinized UCT, most notably strategy fusion and non-locality, described in section 2.5.1.1. The implemented minimax pseudocode is detailed in Algorithm 4. It is unfeasible to calculate a minimax search from the beginning of a card game without a proper heuristic function to evaluate any given game state, even if we know other players cards. To further complicate this problem, there is a multitude of possible card assignments that are contained in the current information set, and a minimax search for each possible assignment is necessary to properly evaluate the best overall move. As such, we can only apply minimax search at a certain point near the last move. For the case of Sueca and Hearts, a feasible point of application is at 13 moves before the end. For Bisca, this number increases to 15, but note that at this point the game is deterministic: the adversary can only hold what cards are left in play. 55 Experimental Results Figure 6.4: Results for reward function experiment with ISMCTS (10 000 iterations) using Positive Win or Loss (PWL) reward function as baseline. Alternatives against the baseline use Win or Loss (WL) function and Scores Difference (SD) function. Regarding the UCB1 exploration constant, the baseline PWL used 0.7 both Sueca and Hearts, and 0.25 for Bisca. WL used 1.75, 0.25 and 1.50 for Sueca, Bisca and Hearts, respectively, while SD used 0.50, 0.25, 0.25. least score. However, the upper bound on the winning rate for an official Hearts game can actually be higher, since a game would significantly last more moves (i.e. until one player scores 100 points), minimizing the effect of luck. 6.4 Reward Functions The reward functions used by the MCTS algorithms are a fundamental part of the tree search and greatly impact what is the current perception of the optimal move. Standard UCT Search usually defines rewards with the Positive Win or Loss function (PWL), where a loss would equal 0 and victories are valued as 1. Also, it has been demonstrated that the optimal UCB1 exploration constant is 0.7 for reward values between 0 and 1 [KSW06]. However, the definition of victory may not be so linear for certain games due to scoring systems. Results for the initial analysis using the proposed Win or Loss (WL) and Scores Difference (SD) functions are visible in figure 6.4. Also, two experiments were conducted to find the best UCB1 constants in the range of [0,2]for SD (fig. 6.5) and WL (fig. 6.6). 62 Experimental Results Figure 6.5: Results for best UCB1 exploration constant using Scores Difference reward function. The baseline agent uses 0.7 as the UCB1 exploration constant. All agents use ISMCTS with 2 500 iterations and Scores Difference as the reward function. For Sueca, both WL and SD slightly worsen the win rate. A possible explanation is that good players should initially focus on winning and afterwards prioritize minimizing or maximizing the score difference (depending if they are the winner). With SD, maximizing score is the first priority, and as such, the agent will likely attempt greedy moves, and assumes the adversaries will also be greedy (i.e. risking high value cards to open chances of a victory by 2 or 4 match points). No result regarding the exploration constant gave significant differences, but 1.75 seems to be the best constant for WL, while SD reached good results with 0.50 and 1.00. In the case of Bisca, WL gives a 3% advantage in win rate. The exploitation component of the UCB1 formula already takes into account the reward of a move with respect to the number of simulated games. With PWL, the exploitation value will equal to the simulated win rate of applying a given move. WL lowers the exploitation value and accentuates the difference between simulated wins and defeats, accelerating the UCT search convergence to moves that apparently have a superior win to loss ratio (while favouring exploration of unknown moves until a superior win to loss ratio is not found). In Bisca, this effect seems to be beneficial. With SD, win rates seem to be equal, however, the number of scored points is lower, possibly due to excessive greediness. Regarding constant values, the best found value was 0.25 for both functions. In fact, the use of a very low exploration value was even used for the baseline PWL, as using 0.7 significantly worsened the results. Exploitation of good moves seems to be the important in this game, possibly due to the fact that in the first 11 tricks, any card can be played. Exploring the use of most cards is fruitless, since only a fraction of the 9 cards in hand are relevant for the best move. Sueca and Hearts players must always follow the leading suit, and as such, exploration is restricted to a small set of relevant cards, effectively narrowing down the search. Bearing this aspect in mind, a constant value between 0 and 0.25 could possibly give better results. 63 Experimental Results Figure 6.6: Results for best UCB1 exploration constant using Win or Loss reward function. The baseline agent uses 0.7 as the UCB1 exploration constant. All agents use ISMCTS with 2 500 iterations and Win or Loss as the reward function. In Hearts, both WL and SD only improve win rate by 1%, but SD allowed to score less points, which is the main objective in an official game of Hearts. Regarding constants, no value gave significant differences, but 1.50 seems best for WL and 0.25 for SD. A common problem is apparent in all tested games: random play takes over the end game decisions because victory is more often than not decided before the last move. But SD does not provide a good overall response to the win rate. We can hypothesize that the best reward function might be of hybrid nature. By using PWL or WL from the game start, the agent will attempt its best to win. After victory is decided, a SD function will try to maximize or minimize the difference, avoiding loss by a great score gap or a win by a small margin. 6.5 NAST Enhancement The simulation phase is a very important step in the MCTS algorithm, and relies on a fundamental concept: that "the true value of an action may be approximated using random simulation" [BPW+12]. However, pure randomness can consider lines of play that will likely never happen if we assume the adversary always acts in a way that maximizes their utility, i.e. they play rationally. NAST changes the simulation phase in order to favour moves that have proven to be more sucessful, based on previous simulations. The calculation method to select the next simulated move is called a simulation policy, and in this section four different policies are tested: ε-greedy, Gibbs Distribution, Roulette Wheel and UCB1, with results visible in figure 6.7. Furthermore, NAST groups moves into sequences of varying length. In these experiments, n-grams of size 1, 2, 3 and 4 are tested, with results displayed in figure 6.8. 64 Experimental Results Figure 6.7: Results for best NAST simulation policy. All agents use ISMCTS with 10 000 iterations, with the baseline not using any enhancement. NAST agents use n-gram sequences of length 2 with different simulation policies, namely ε-greedy, Gibbs, Roulette, or UCB1. Overall results show that NAST somewhat impacts performance in all three games. The UCB1 and Roulette Wheel policies yield better results than the baseline in Sueca, while UCB1, ε-greedy and Gibbs Distribution give a boost in performance for Bisca. In Hearts, Roulette seems to make the best improvement, but not by significant margins. Using n-grams of length 2 provides good results for Sueca and Bisca, while lengths of 2, 3 and 4 do not affect performance for Hearts in a statistically significant matter. One can argue that NAST would not improve playing performance because it is based on the assumption that good moves are somewhat independent of the context in which they are applied. Taking Sueca as an example, playing the Ace of trumps in the first round does not have the same effect as saving it for the last rounds (where it is likely applied best in most situations). However, note that simulations are purely random in the baseline ISMCTS, and this creates very unlikely and irrational situations. Imagine that a trick is lead with a high card, such as Ace of Spades (not the trump suit). It would make no sense for the next player to use a very high card, such as a 7, because there is a very low chance to actually win the trick this way. Using NAST of length 2, the sequence would be grouped as hA♠, 7♠i and a statistic would be stored, counting the number of times it appeared in a simulation, and how many simulations with this sequence turned out as a victory. The negative impact of the action would easily be perceptible by the simulation policy, since throwing away 10 points greatly hinders chances of success. With these statistics, simulations are biased toward the best found moves so far, but are still mixed with some randomness (depending on the chosen policy). Sueca and Bisca benefit most from the 65 Experimental Results Figure 6.8: Results for best NAST N-gram length. All agents use ISMCTS with 10 000 iterations, with the baseline not using any enhancement. Nast agents use different number of N-grams length with the UCB1 simulation policy. exploitation of good move sequences with exploration of untried sequences (UCB1), while Sueca also benefits from a random exploration of sequences, biasing the more sucessful ones (Roulette Wheel). While we only used the example of discarding high value cards, the reverse situation still gives good insight: h7♠,A♠i would indicate that using an Ace is highly rewarding, and the agent would avoid a simulation that leads with a 7 since it has very low chances of winning. This eventually improves the quality of a simulation, since a reward for any given move would not have so much interference from such irrational moves. Note that at least some historical information is still present: statistics for hA♠, 7♠i would only be considered if the Ace is held by the first player and the 7 is held by the second player. If one of these cards is already out of the game, then the statistics for this sequence would not even be taken into account. The available cards in the determinized game make up the eligible set of move sequences used to calculate the simulation policy. While the overall result is positive, there might be some negative effects due to lack of contextual information. For example, examining the situation with h7♠,A♠i: we can not guarantee that the sequence is actually in the same trick. If the 7 was used as the last card in the previous trick, and the new trick is initiated with Ace, then there is a different interpretation of value. Many simulations would indicate that playing an Ace is a good response after a 7, but there is not much value in initiating a trick with an Ace after the 7 came out in the last trick. While this may not greatly influence the result, it could be mitigated by borrowing concepts of other simulation en66 Experimental Results Figure 6.9: Results for hybrid use of Minimax and ISMCTS. All baseline agents use ISMCTS with 10 000 iterations, with the variant switching to Minimax search in the last 13 moves (Sueca and Hearts) or 15 moves (Bisca). hancements such as EPIC, which groups sequences of moves into episodes that in this case are tricks. 6.6 Hybrid ISMCTS with Minimax The main objective of this section is to test the effectiveness of applying Minimax in conjunction with ISMCTS. UCT Search is proven to eventually converge into the Minimax evaluated move, even if slowly [KSW06], but there is no guarantee for the case of non deterministic games. However, due to the computational complexity required by Minimax, we can only apply it near the end game, where only a reduced number of cards is left, and thus the best move can be evaluated in a feasible amount of time. Until that point is reached, ISMCTS is used instead. The upper bound time limit was established at around one minute. For Sueca and Hearts, responses under a minute in the experimental environment are reached with 13 moves left, while in Bisca this is achieved in 15 moves. Note that the heuristic function used with these games does not use any domain knowledge: a victory yields 1000 points, while defeat returns -1000 instead. The game score for the own agent is then added to this heuristic evaluation (higher scores are more valuable). As such, Minimax must run until the last move to properly calculate the score (i.e. with a depth level of 13 or 15). Also note that the game up to this point is still non deterministic for the case of Sueca and Hearts. With 13 moves left, there can be around 4200 different possible card assignments (10 67 Experimental Results cards left for 3 players, 10 4∗6 3∗3 3=4200), and a Minimax of depth 13 must run for each assignment. In the case of Bisca, the game is deterministic: after the deck runs out, one player can known exactly what the adversary holds, but branching factors are much higher, since each player has 7 or 8 cards when there are 15 moves left. Results in figure 6.9 show that win rates do not change in statistically meaningful way. However, note that in all games the overall score improved significantly. This still can be explained by the same hypothesis detailed in section 6.4: the reward function used by ISMCTS is not the most appropriate. In the late game moves, victory is more often than not already decided, and players are simply trying to maximize the end score, but ISMCTS evaluates all moves as 100% reward or 0%, so any choosen move will not affect the game outcome. Also, note that many end game moves do not have any decision process involved: if the leading player uses a suit that others have, it is very likely that only 1 possible card can be played, and in that case, Minimax can not make a difference. For the case of Bisca, note that win rate for Minimax increased slightly, even if not in a statistically significant manner. This gives some insight into a problem with the use of ISMCTS: after the last card of the deck is taken, the game becomes deterministic, since there is only one possible card assignment in the information set. This likely means that the hybridization technique would be best applied with a conjunction of ISMCTS with normal UCT Search once determinization is no longer required. From this experience, we can infer that Minimax in the final game phase does not make a meaningful impact, is significantly slower than ISMCTS, and a more appropriate reward function would likely minimize the score difference seen in the results. 68 Chapter 7 Conclusions This final chapter presents the conclusions of this research. Initially defined goals and questions are answered according to the observed results, and an overview of guidelines for future research is given. 7.1 Goals The initial goals defined in chapter 1.3 are now addressed as follows: G1. Elaborate a study on the best known MCTS implementations applied in the context of trick taking card games. All the research related to the topic is covered in chapter 2. Overall, it was concluded that much of the scientific experimentation with card games has surfaced in very recent years due to integration of determinization techniques with MCTS. In 2001, Ginsberg proposed the use of determinization to create an agent that challenged champion level human players in the card game Bridge [Gin01]. Later experiments showed that this approach was affected by shortcomings such as strategy fusion and non-locality, which compromised performance in certain card games, but still allowed champion play in others. A 2010 study on game characteristics allowed to better understand when determinization was best applied, supporting its use in trick taking card games [LSBF10]. ISMCTS was first proposed in 2012 [CPW12], as an alternative to Determinized UCT that removes effects of strategy fusion. Both ISMCTS and Determinized UCT have proven to be very effective algorithms in trick taking card games, with experimentation done in recent years for Hearts [PCW14], Dou Di Zhu, [PCW14] Spades [WCPR13b] and Skat [FB13]. Finally, in 2013, some enhancements such as NAST [PWC13] have been proposed and tested in card games, showing improved results for Hearts and Dou Di Zhu. 69 Conclusions G2. Create a framework with some MCTS variations and enhancements, with application in card games. The developed framework for card games is described in chapter 4.3, with a focus toward reproducible research. This design decision was carried out mainly due to the lack of required resources to reproduce results published throughout the researched scientific literature. While the framework might not satistify all developer needs, it is considered as a step in the right direction to aid other researchers in building on top of existing work and further improve the current state of the art artificial intelligence for card games and MCTS in general. Some ideas surfaced with the development of this framework, such as move replayability for faster debugging and hypothesis experimentation, as well as unit testing specific game states to understand and fine tune playing quality of agents before running long term experiments. As an end result, the framework can be used by other researchers to explore the datasets generated in the experimentation chapter, and allow them to run experiments of their own, with any modification to the source code. G3. Develop a framework that enables different AI agents to compete against each other and evaluate relative performance and quality of play. After researching possible projects, the Botwars framework (described in chapter 4.2) was choosen as the best alternative to acomplish the proposed goal. Some contributions were done to enable its use in this dissertation, namely the support of database storage for games and their full history of states. The framework serves as a solid foundation for researchers to run their experiments on, since it enables freedom of choice in the choosen programming language for agent development, allowing AI programs to compete against each other, independent of the language in which they are written. With the implementation of both playing and rendering logic, new games can be integrated into the framework, allowing for humans to play against developed AI’s and easily coordinate long running experiments to evaluate the relative efficiency of each agent. G4. Use the developed framework to experiment and analyse the best performing MCTS enhancements in a selection of three trick taking card games. Both frameworks were used in conjunction to run the experiments described in chapter 6. Overall the proposed goal was achieved with success, since all experiments ran without any setbacks. Initially, the experiments were run in an iterative and manual way, but much of the setup process was later automated through bash scripts, while result aggregation and chart generation was automated with scripts using the R programming language. While some 70 Conclusions observed results did not show statistically significant differences against the baseline algorithm, enough data was gathered to draw interesting conclusions for most of the cases. Taking the achieved goals into account, the questions proposed in the beginning of this work are now answered as follows: Q1. Which MCTS variations and enhancements are best applied to the trick taking card games Sueca, Bisca and Hearts? Results obtained in experimental section 6.1 compare the use of two popular algorithms, Determinized UCT and ISMCTS. Although the three proposed games are somewhate similar in nature, intricacies in the gameplay of each game often lead to different results. For the case of Hearts, Determinized UCT gives very similar win rates, while ISMCTS shows better results in Sueca and Bisca. Another important aspect for both these algorithms is the reward function, which is evaluated in section 6.4. It is likely that all three games do not benefit from having a static reward function. While winning is the primary focus at the beginning, victories are almost always decided before the last move, which translates to poor playing quality when the outcome is already known. Win or Loss yields the best win rate in Bisca with very low exploration constants, while the standard Positive Win or Loss function gives the best win rates in Sueca and Hearts. The NAST simulation enhancement was also tested with different policies and move sequence lengths in section 6.5, with length of 2 proving to be the best alternative for all three games. Simulation policies have different effects for each game, as best results in Sueca, Bisca and Hearts were achieved with Roulette, UCB1 and Roulette, respectively. Q2. Can an enhanced MCTS develop strong play against traditional AI techniques in trick taking card games? As explained in section 2.5.2, traditional techniques such as Minimax are computationally intensive and can not be effectively applied without proper domain knowledge. It has been proved that MCTS converges to the Minimax solution [KSW06], but it is not possible to guarantee the same when applying determinization techniques. However, results visible in section 6.6, where Minimax is mixed with ISMCTS, show that the use of Minimax near the end game does not affect the outcome in a significant manner. Also, there is, to the best of our knowledge, no known scientific literature regarding rule based systems or game evaluation heuristics for Sueca and Bisca. As such, an enhanced ISMCTS with NAST of length 2 is so far the best researched aheuristic approach that can develop a good playing quality in these games. 71 REFERENCES [SWU12] Jan A. Stankiewicz, Mark H. M. Winands, and Jos W. H. M. Uiterwijk. MonteCarlo Tree Search Enhancements for Havannah. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. [TWB12] M. J. W. Tak, M. H. M. Winands, and Y. Bjornsson. N-grams and the last-goodreply policy applied in general game playing. IEEE Transactions on Computational Intelligence and AI in Games, 4(2):73–83, June 2012. [WCPR13a] Daniel Whitehouse, Peter I. Cowling, Edward J. Powley, and Jeff Rollason. Integrating Monte Carlo Tree Search with Knowledge-Based Methods to Create Engaging Play in a Commercial Mobile Game. Proc. Artif. Intell. Interact. Digital Entert. Conf., pages 100–106, 2013. [WCPR13b] Daniel Whitehouse, Peter I. Cowling, Edward J. Powley, and Jeff Rollason. Integrating Monte Carlo Tree Search with Knowledge-Based Methods to Create Engaging Play in a Commercial Mobile Game. Proc. Artif. Intell. Interact. Digital Entert. Conf., pages 100–106, 2013. [Whi14] Daniel Whitehouse. Monte Carlo Tree Search for games with Hidden Information and Uncertainty. PhD thesis, University of York, 2014. [WPC11] Daniel Whitehouse, Edward J Powley, and Peter I Cowling. Determinization and information set Monte Carlo Tree Search for the card game Dou Di Zhu. In 2011 IEEE Conference on Computational Intelligence and Games, CIG 2011, pages 87– 94, 2011. 78