The Game of Hex - An Interim Report - Dissertation Example

? The Game of Hex Interim Report [4013 words] Table of Contents Introduction Motivation Project Aims/Objectives 2 Project Requirements 2 The Gameof Hex 3 Literature Survey 4 Design 6 Performance Analysis 8 Monte-Carlo Tree Search (MCTS) 9 Implementation 1 Challenges 5 Reflective Analysis 6 Dissertation Outline 6 Bibliography 7 List of Figures Figure 1 The Game of Hex 4 Figure 2 System Design 7 Figure 3 High level architecture of Hex game 8 Figure 4 Test Scenarios 8 Figure 5 Hex Game Flow Chart 1 List of Tables Table 1 Hex_Game Methods 3 Table 2 Data Structure for Human Player 3 Table 3 Data Structure for System Player 4 Strategy is generally defined as a course of action or policy designed for achieving an aim.1 Games are designed on basis of strategies. Every game has an objective/goal and a set of rules/policies that are to be abided by while reaching that objective/goal. 2 These strategy based games are generally of two kinds; turn-based where each player takes turn to perform a step towards the goal or real-time where all the players play simultaneously. 3 Board game is one where pieces are placed and moved on a marked board in accordance with a set of rules. These games maybe based on strategies, on luck or partially on both. Board games may have a theme/narrative or may be goal oriented involving some strategy. Strategy based games usually have opponent parties where score is tracked to decide a winner. Motivation As the trend has shifted to computer games, the traditional board games have been digitized to be played on computers.4 In order to personify human minds, various artificial intelligence techniques are utilized to program the underlying strategies of these games. This project is one such endeavor of digitizing a board game through an artificial intelligence algorithm. The project revolves around the task of digitizing a turn-based strategy game called Hex. This report discusses the aim of the game, analyses the design details, and presents the existing implementation strategies that have been employed in its development for computers, how this project aims to develop the game and how the developed application’s performance can be evaluated. It also discusses the implementation progress since the initiation of the project and presents an overview of reason of shift from the initially defined project scope and development plan. Project Aims/Objectives The aim of the project is to implement a Hex game using NxN board, where N depicts the number of hexes in a side. The player would be able to specify the number of hexagons on a side i.e. size of board that will be used in the game. The board would be diamond shaped. The gaming mode could also be selected i.e. the two players could be two humans, a human against the system or two systems against each other with opposite sides. The player will select a side. If white is selected, then the player himself begins, else the opponent (player or system) plays the first move. Project Requirements The requirements of this project are divided into three parts: 1. Essential requirements The development language for the project would be Java (oracle JDeveloper 11). All functionalities will be developed using JDeveloper 11. AI algorithm called MCTS algorithm shall be used to support the high level of knowledge required by the Hex game. MCTS shall be implemented on the Hex game board whereon the data structures would be transferred. The game would have playing options. These options will be implemented though MCTS. The game will be played by two human players, or one human against the system. 2. Recommended requirements A new playing mode option can be added. In this playing mode, the game would be played between two systems. Adobe flash player can be used for designing a helper application to guide computer players as to how to play the Hex game. The guide would be simple enough to assist anyone in learning the game rules and playing. 3. Optional requirement: The MCTS algorithm which is used for building this game shall be compared with another algorithm e.g. Negamix algorithm. The Game of Hex This section presents a technical overview of the Hex game. It highlights its historical background and rules for Hex. The game of Hex was invented by Piet Hein, a Danish mathematician, while working with a four-colour topological problem, in 1942. It became popularly known as ‘polygon’ during the time. In 1948, the game was independently invented by John Nash from Princeton University and was marketed by the Princeton Brothers, Incorporation, in 1950, under the name of ’Hex’.5 The game of Hex is a turn-based board game that has two players. The board is rhombus shaped consisting of an array of hexagons, as shown in Figure 1. 6 The optimal suggested size for rhombuses is 14x14. However, the size could vary. After choosing a one of the two colors (e.g. black or white), each player takes turn to place a piece on any one of the unoccupied hex. The goal of the game is that a player has to connect the two opposite sides of the board with an unbroken chain of his/her colored pieces. For a player that selected white, a chain of white pieces has to run from one edge to the other. Similarly, for the player with black pieces, a connected chain of pieces has to run across the other two edges (Figure 1-a). There is no predefined path for the chain. It can freely twist and turn on its path between the two edges (Figure 1-b). The player with white pieces always makes the beginning move. However, the player cannot place the piece on the hex in the center (Figure 1-c). (a)Player Sides (b) Black Wins (c) White starts but never from the central hex Figure 1 The Game of Hex The game continues till one a side has won. The game never ends in a draw. This follows from the topological fact that if there is no vacant hex on the board, there necessarily exists a connected path in between the two opposite sides. Literature Survey This section presents a discussion regarding the implementation techniques used in digitizing board games. The strategy of Hex is such that the winning moves may be different for every player and the game never ends in a draw. One player always wins. This is due to Brouwer fixed-point theorem for 2D squares.7 Computer programs where a game of two players is solved generally comprise of exploration of a hierarchy of positions on the board. This hierarchy (called game tree) is a tree with a root, where its nodes represents the valid position on the board and the edges represent the valid moves.8 The extensive techniques for game-tree search developed over the last 3 to 4 decades are mostly aimed at programming Chess.9 These techniques have further been utilized in games like Checkers.10 However, due to the large branching factor in Hex, the techniques developed for Chess could not be used for Hex. Many skilled game players believe that intelligent decisions can be made by deep strategic analysis of the few game positions in Hex, instead of having to keep a massive game tree. The first machine to play Hex was developed in 1953 by Shannon and Moore where the board was an electric circuit and decisions were made on basis of minimum resistance values of connections made.11 A sound evaluation function for the Hex game must be able to estimate how close Black is from building a winning black-chain than the White is from building a winning white-chain. A technique mostly used to estimate how close a player is from building the winning chain is by calculating the number of pieces that would be minimally required for connecting the two board sides. The approach used in the machine did not take into consideration the potential chain numbers. So the idea of Shanon was enhanced to utilize this technique and a computer program was made where the actual electronic connections were replaced by virtual connections.12 Generally computer programs that solve strategic games like Go, Chess or Hex search their game trees through algorithm like minimax search algorithms with pruning.13,14 This pruning is used well if those moves are searched first that trigger the prunes. A good ordering of moves reduces the number of searches. Move generators are algorithms that order moves in a way to maximize pruning. They may be static (generate moves as function of single board position) or dynamic (generate moves as function of some or all board positions in the game tree).15 A number of computer programs for the Hex game have been developed over the last decade.16 These programs include BiTaHex, Hexy, MIMHex, etc. These program are based on algorithms like minimax search, alpha-beta search, Monte-Carlo tree search and Upper Confidence bounds applied to Trees (UCT) algorithms.17,18 Alpha-Beta search algorithm is an enhanced version of the minimax search algorithm where its branch-and-bound techniques without missing any good moves, eliminates the need of searching large game tree portions. Alpha is the minimum score that maximizes the player and Beta is the maximum score that minimizes the player. Monte-Carlo Tree Search (MCTS) is basically a Best-First search algorithm that is based on random runs which is successfully used in conjunction with the UCT for evaluating positions in Hex. It randomly explores the search space and grows the game tree on basis of the results, and therefore increases in accuracy for estimating good moves. Design The basic design of this project consists of two parts (Figure 2); a user friendly interface and the underlying computational module. There would be three modes of playing (1) human vs. Human (2) human vs. System (3) system vs. System. In mode (3), the user would only be able to watch the game. Figure 2 System Design The interface would be operable through mouse with proper indication of players’ turns. The option to selecting the colour of pieces and the playing mode (player vs. player, player vs. system or system vs. system) would be present. Proper colours and buttons to start stop or reset the game at any time, would also be present. An interactive guiding tutorial on playing the game could also be added as part of the interface. Computational Module would be transparent to the player. It would be based on an intelligent algorithm that would be able to take the game from any instant towards the goal and a fast programming language to implement the algorithm. Figure 3 shows the high level architectural diagram of the Hex game. It illustrates the fact that the game is based on Java In the figure, environment and using its libraries to support the basic game functionality. In the figure, Game engine is working on the MCTS algorithm, Graphic user interface enables the players’ interaction the playing options e.g. playing between two human players and the Game Management supports the core functionality of the game e.g. giving each player his turn then wait for the second player to play. Figure 3 High level architecture of Hex game Performance Analysis Like every computer program, three parameters shall be used to assess performance of the project; speed, memory and accuracy. Complex scenarios could be designed to assess how the game moves towards the goal in situations of particular difficulty level. Figure 4 shows a few scenarios where the response of the program could be assessed. (a)W to play and win (b) W to play and win (Hard) (c) B to play and win (Very hard) Figure 4 Test Scenarios In order to know if the game is correctly implemented, it must never end in a draw. One player must always win. Another criterion is to measure the speed of the developed program with some existing Hex programs. Monte-Carlo Tree Search (MCTS) Monte-Carlo Tree Search (MCTS)19 is a best-first search method which does not need any positional evaluation function. MCTS is based on exploring a search space at random. On basis of the previously explored results, MCTS gradually builds up the game tree in memory, and successively increases in accuracy while estimating the values of the moves that would be most-promising. MCTS can be used if the following three conditions are met: 1. Payoffs (game scores) are bounded 2. Rules are completely known 3. Simulations end at a faster rate i.e. limited game lengths In MCTS, each node ‘i’, represents a position of the game i.e. state of game and signifies two attributes; current value of the position, Vi, ( which in simulated games is generally the average of the results that visited the node, i)and the count of visits of this position, ni. In the start of the game, the MCTS has only one node i.e. the root node. MCTS comprises of four strategic phases, which are repeated till the game ends or the time for game expires: 1. Selection phase: In this phase the tree continues to be traversed starting from the root node until a leaf node, E, is reached. Here a child node, which is not part of the tree yet, is selected. 2. Expansion phase: involves adding the selected child of leaf node, E, to the tree. 3. Simulation phase: involves the self-play of the moves in until the end of the game is reached. The result, R, of this simulated game is either 1 (the starting player wins), 0 (draw) and -1 (the second player wins). 4. Backpropagation phase: involves propagation of the result, R, backwards, through all the previously traversed node of the tree. In the end, the best move selected to play is that child node of the root that had the highest visit count. The Selection Phase Algorithm Several selection strategies have been designed for the MCTS. UTC (Upper Confidence bounds applied to Trees) strategy is one of them. UCT adapts the UCB (Upper Confidence Bounds) method and works as follows.20 If I, is the set of nodes reachable from the current node, p, UCT would select a child, k, of the node p which satisfies equation 1. (1) where Vi = value of the node i ni = visit count of i np = visit count of p C = a coefficient that handles the trade-off between exploration and exploitation (has to be set experimentally) Once the values of all the children have been calculated, the child with the highest score is selected. Moreover, a small random value is added to every node's value to ensure that the selection does not bias the child that was added first. Implementation The computational algorithm selected comprised of Monte-Carlo Tree Search (MCTS) technique (see above for detail). In the selection phase, the value of C was set to 2.5. The underlying programming language selected for developing the interactive and computational module of the project is Java (JDeveloper 11g). For the supporting interactive game guide, adobe flash player was used. For designing the background and logo on interface, adobe Photoshop was used. Figure 5 shows the flowchart of the game. It also gives an overview of the class involved in generation of board and running the game. Figure 5 Hex Game Flow Chart Table 1 gives an overview of the Hex_Game call which is the controller for the game. Table 1 Hex_Game Methods Method Description Public void run(){} Check whether there is a board and AI set up. If there are any and start a game. Public void doTurn(){} Carries out all the operations for a turn to happen. Public Hex_Player getPlayer(){} Returns a player by its identifier There are two players; the human player and the system player. Tables 2 and 3 give an overview of the data structures for the two classes; the data members and member functions. Table 2 Data Structure for Human Player Data Members Description Public static GeneralPath [][] hexagons; Contains all hexagons that are drawn in the board private int [] MousePoint; Initiated when Mouse Action Listener is attached to a board. At Mouse Pressed action Listener: If mouse pressed in any location of the board, then Create Rectangle 2D called mouseHandle. Defined by the location that is occurred player (e.getX(),e.getY()) and dimensions (1,1). If any board hexagons are intersected by mouse Handle from player then, save the move of the player: MousePoint = new int [](i,j); At Mouse Released action Listener: Here we also create a Rectangle 2D. The x,y of points that are intersected on the board are checked for and saved. Move is set for the active player. int [] move; Saves the move: int [] move = {x,y} where x and y are for hexagons that is clicked Member Function Description setNextMove(move) Sets the move getActivePlayer() Returns the player with the turn to select a move getForNextMove() Game should call this method whenever it needs a new “move” from the player. setStartGame() Specifies the game board that the player will use to calculate its next move. This should be set once by the game when it is started setPlayerId() Specifies the player that is playing Table 3 Data Structure for System Player Data Members Description Public MonteCarloNode* rootNode; The root node for MCTS tree. Instantiated as MonteCarloNode rootNode = new MonteCarloNode(); Public MonteCarloNode parent; Represents the root of each Monte carlo tree search Public ArrayList rootChilds; Represents the children of each root in Monte carlo tree search public int [][] blanckFields Array of all possible moves. Initiated as rootNode.blankFields = getBlanckFields(board); public ArrayList Un_simulationNodes ArrayList of all nodes that are not simulated yet Public ArrayList Un_propagationNodes ArrayList of all nodes that are not propagation yet Member Functions Description select() Selects a node ExpandAll() Expands all children nodes of the node Simulate() Runs simulation for all recently expanded nodes SimulateGame() Recursively simulates a random game. Backpropagation() Back-propagates the results of recently simulated games. getBlackFeilds() Returns all possible moves of the board *The MonteCarloNode class represents a node. Challenges In order to accomplish this project, there are a few implicit challenges besides learning the Hex game manually: 1. A hand on experience of Java language is required for creating user friendly interfaces for effective interaction with users. 2. Designing of the board to enable the stones to be placed. 3. Artificial Intelligence programming techniques would have to be learnt. From the available AI algorithms, the most appropriate intelligent algorithm would have to be selected. Furthermore its implementation has to be fast enough to not cause any noticeable computational delays. The task of Implementing MCTS on the system has its complexities that would have to be dealt with. 4. In order to validate and verify the hex game, test suites will be drafted and performance of the game shall be evaluated on basis of that. These test cases must cover all the important aspects of the game e.g. the game never ending in a draw, white never starting from the central board position, when the system itself is player, only those moves should be adopted that take the system player closer towards the goal, etc. Reflective Analysis While dealing with the challenging nature of the problem domain, the initial plan that was devised for the project development has been extended 1- Re-work was needed with designing the board of the game and playing options. 2- A Clonable method was used for designing the board to enable placement of the stones. 3- UCT was used in the selection phase of MCTS Algorithm to guarantee the highest score of node is chosen by the system. Dissertation Outline An outline for the dissertation is given below. Chapter 1: Introduction ? Defines the problem domain of Hex Game Chapter 2: Motivation ? Outlines the intent of taking up the project. Chapter 3: Project Aim and Objectives ? Defines the goal of the project. Chapter 4: Challenges ? Defines the challenges that were to be addressed while formulating the system Chapter 5: Literature Survey ? Defines the methodologies suggested in literature for solving the problem. Chapter 6: Methodologies Adopted ? Gives a background study of the methodology adopted for developing the system. Also gives a comparison of Monte-Carlo Tree Search (MCTS) Algorithm and Negamax Algorthim, their advantages and advantages, the technical implementation when employed for the Hex game. And lastly provides the reasons why MCTS was chosen to be implemented. Chapter 7: System Design ? Gives an overview of the modules that the system would comprise of and how the users will interact with the system Chapter 8: System Implementation ? Gives implementation details of the developed system. Chapter 9: Performance Evaluation ? Gives an overview of the validation and verification measures. The time takes in particular game scenarios. And comparisons with another developed and recognized system. Chapter 10: Conclusion ? Summarizes what was developed in the project, how the goals and challenges were met. Highlights the performance of the developed system. Also gives details of any observations. Appendix ? Gives screenshots of the developed game (Maybe a manual), Installation and configuration details. Bibliography [1]. Definition of ‘Strategy’ from Dictionary.com. Viewed on 5 August 2011. URL http://dictionary.reference.com/browse/strategy [2]. Salen, K. and Zimmerman, E. ‘Rules of Play: Game Design Fundamentals’. 2003, MIT Press. pp. 80.  [3]. Johnson, S., ‘Analysis: Turn-Based Versus Real-Time’. Gamasutra, November 2009. Viewed on 5 August 2011. URL http://www.gamasutra.com/php-bin/news_index.php?story=25920 [4]. Millington, I and Funge, J. ‘Artificial Intelligence for Games’. 2nd Edition, 2009. Morgan Kaufman. [5]. ‘About Hex’. MazeWorks. Viewed on 5 August 2011. URL http://www.mazeworks.com/hex7/about/index.htm [6]. Gardener, M. ‘The game of hex’. In: The Scientific American Book of Mathematical Puzzles and Diversions, 1959, Simon and Schuster, New York [7]. Gale, D. ‘The Game of Hex and the Brouwer Fixed-Point Theorem’. American Mathematical Monthly, 1979, Vol. 86, pp. 818-827. [8]. Rijswijck, JV. ‘Computer Hex: Are Bees Better than Fruit-flies?’. Master of Science, 2000, University of Alberta [9]. Marsland, T. A., ‘A Review of Game-Tree Pruning. Journal of the International Computer Chess Association, 1986, 9(1):3-19. [10]. Schaeffer, J.; Lake, R.; Lu, P.; and Bryant M. ‘Chinook: The World man-Machine Checkers Champion’ in AI Magazine, 1996, Vol. 17(1), pp.21-29 [11]. Shannon, C. E. ‘Computers and Automata’. Proceedings of Institute of Radio Engineers, 1953, Vol. 41, pp. 1234-1241 [12]. Anshelevich, V.V. ‘The Game of Hex: An Automatic Theorem Proving Approach to Game Programming’. By American Association for Artificial Intelligence, 2000. [13]. Hayward, R., Bjrnsson, Y.,M.Johanson, Kan,M., Po, N., Rijswijck, J.V., ‘ Advances in Computer Games: Solving 7x7 HEX: Virtual Connections and Game-State Reduction’. IFIP International Federation of Information Processing, 2003, Vol. 263 , Kluwer Achedemic Publishers, Boston [14]. Hayward, R., Bjornsson, Y., Johanson, M., Po, N., Rijswijck, J.V., ‘Solving 7x7 hex with domination, fill-in, and virtual connections’. In Theoretical Computer Science, 2005, Elsevier Science [15]. Rasmussen, R., Maire, F. and Hayward, R., ‘A Move Generating Algorithm for Hex Solvers’. Sattar, A. and Kang, B.H. (eds), AI 2006, LNAI, Vol. 4304, pp. 637–646, Springer-Verlag Berlin Heidelberg. [16]. ICGA Tournaments. Viewed on 1 August, 2001. URL http://www.grappa.univ-lille3.fr/icga/game.php?id=7 [17]. Arneson, B., Hayward, R. & Henderson, P., ‘Monte Carlo Tree Search in Hex’. IEEE Transactions on Computational Intelligence and AI in Games, 2010, Vol. 2, No. 4. [18]. Raiko, T. and Peltonen, J. ‘ Application of UCT Search to the Connection Games of Hex, Y, *Star, and Renkula!”. In Proceedings of the Finnish AI Conference (STeP 2008), Espoo, Finland. [19]. Chaslot, G.M.J-B. , Bakkes, S., Szita, I. and Spronck, P.H.M. ‘Monte-Carlo Tree Search: A New Framework for Game AI’. Proceedings of the Fourth Artificial Intelligence and Interactive Digital Entertainment Conference, 2008, pp. 216–217. [20]. Kocsis, L. and Szepesvari, C. ‘Bandit Based Monte-Carlo Planning’. In FAurnkranz, J., Sche®er, T. and Spiliopoulou, M. (eds) Machine Learning: ECML 2006, Lecture Notes in Artificial Intelligence, 2006, Vol. 4212, pp. 282-293. Read More