Table of Contents
- Rules of The Game
- The Goal of the Project
- Game Representation
- The Minimax search with αβ-pruning
- Game Strategies
- The maximizing disc advantage
- Weighed square advantage
- Possible future work
In this paper, we describe the functionality of the program that plays the game Othello against a human opponent. It explains the game rules and the basic strategy of playing Othello. The paper also describes the board representation and the structures that represent the board the discs and the moves associated with it. The evaluation function, Game tree and minimax algorithm with α-β pruning is the heart of the game they are the main functionalities of the program. The usage of the program is very simple because of the user interface and can be easily understood if somebody knows the game rules and know how to play the game, Othello.
This paper includes an overview of the Othello game including some game strategies. The game is implemented in Java because we are more familiar with it and it provides a GUI which made the program more user-friendly. The paper also explains the board and the representation of the board with the discs that represent the scoring criteria for each player. Our paper describes the gameplay between the computer and the human player and is capable of identifying the various evaluations for the win strategy. The paper represents the search strategies with an outline of the minimax algorithm with alpha-beta pruning which may be considered as one of the main implementations for the game. This paper also identifies some of the future aspects of the game that can be implemented to make the game more intelligent.
Rules of The Game
Othello is a relatively modern game. It is also called as Reversi. Othello falls into the category of 2 players, zero-sum games, with no imperfect information. The 2-player description speaks for itself and zero-sum, whilst an obscure term, simply means that the gains for one of the players will exactly match the losses for another. It is played on an 8*8 unchecked board. There are 64 game pieces called discs which are light on one side and dark on the other side. Players take turns placing discs on the board with their assigned color facing up. At the start of the game, there are four discs in the center of the grid. White in the top-left and bottom-right. Black in the top-right and bottom-left, with black taking the first move. The discs must be placed on an empty square so that it sandwiches at least 1 of their opponent’s discs between another of their own discs in any direction (up/down, left/right and diagonally except for in corners and edges where the board limits the options). If a player cannot move (no legal moves) then he misses his turn and his opponent takes another move. The objective of the game is to have the majority of the discs turned to display the color the player chose when the last playable square is filled.
The Goal of the Project
We intended to create a program that is:
- Easily understandable
- Can play against a human opponent
- Looks good
- Could beat players who knew how to play Othello, mostly beginners i. e. some background on the rules of game playing, in general, is needed.
Seeing as how Othello is played on an 8 by 8 square board we represented our board as an 8×8 integer array. Each position in the array represents a different square on the board and values on the game could be changed based on a player’s decision. The board discs are weighed in such a way that they give an advantage to positions with higher adversarial strategy.
Discs placed in these positions cannot be flipped by an opponent. The positions adjacent to the corners are usually bad to be the first to take since this gives your opponent a good chance of taking over the corner and reducing your options of taking the corner to yourself. Also, the squares one step away from the corner are also good to take, to take a striking position for the corner. As the next advantage rule, we take over the edges (they cannot be flipped from all directions, they can only be flipped from two separate directions. Therefore, we decided to give a higher weight to these positions than the interior positions. For positions that are affected both by the corner rule and edge rule, the weights are higher than for positions which belong to one of these rules.
When considering the game to play, a player may have many possibilities to play which are legal moves. These choices of moves can be represented as a tree referred to as a game tree. The root node shows the representation of the current board state For example, if the first move is played by Black discs who opt to place his disc from the initial board state. Once Black discs take his turn, the board situation resulting his move is now the root node representation for White. As a player can possibly move in seven different directions, and the game can be finished at a maximum of sixty moves assuming the majority of games end when the board is full. This means that there will be many branches representing the results so, the time taken for evaluating the move made by the player will produce a very slow response.
This is the reason why in spite of creating a game tree for the whole game it is more viable to create sub-trees of the game to a certain depth. The concept of selecting the best move for the computer rests on the use of search algorithms and significant knowledge given by sub-trees.
The Minimax search with αβ-pruning
The Minimax function is a recursive function that generates a scenario of looking ahead multiple moves. This function allows a step by step scoring process in which it maximizes the computer player’s score opportunity and minimizes the human player’s score opportunity.
When applying this function in the Othello, it recognizes the possible moves a computer player can have, simulates these moves and at the same time it recognizes the possible moves for the opponent or the human player. This way the function allows the program to search the smallest score for the human opponent’s recognized moves and search for the largest score for the computer player’s recognized moves, this defines which move will maximize the computer player’s score and minimize the human opponent’s score.
The Minimax algorithm is applied along with the alpha-beta pruning, which allows reducing the search space by pruning the nodes away which would not be chosen for either minimizing or maximizing levels, this will help to get the lookahead.
A game “is any set of interactions governed by a set of rules specifying the moves that each participant may make and a set of outcomes for each possible set of moves. ” Othello, as we’ve stated earlier, is a game of strategy. The focus of this project is to optimized an Othello computer player to make intelligent moves at a particular game state, given a set of predefined rule. Placing a disc on the board is so crucial and must be well thought of. Having only a few poorly placed discs can be disastrous, even in a situation where the player has the majority of discs with a high margin against his opponent. A number of strategies have been suggested for Othello game playing. A few are maximizing disc advantage, minimizing disc advantage, and weighted square strategy.
The maximizing disc advantage
This approach is, essentially, a greedy search. It plays moves that capture the most discs. The static evaluation function was implemented by maximizing the difference between the difference in the number of discs for each side. If the player has more disc, it returns a positive number. If the opponent has a majority, a negative number is returned. A zero is returned when there is a tie. For Othello, this strategy turned out to be a failure.
This approach is converse to maximizing disc advantage. It is, as well, essentially, a greedy search. It minimizes the number of his own disc while maximizing the number of his opponent’s disc. The result gotten from evaluating the above is what informs the heuristics decision. This, however, was not optimal.
Weighed square advantage
From the Game Board discussion earlier, we know that not all squares on the Othello board are equal. Reiterating from our previous section, the corner squares once occupied, cannot be recaptured by an opponent while the ownership of other squares almost always allows the opponent to capture the adjacent corner. Thus the corner squares are weighted more.
As opposed to maximizing and minimizing disc advantage, a sum is computed according to the weight/value of the squares which it occupies. The difference is computed and used as a playing strategy. It is essential to note that these square values can be constant or variable; changing dynamically.
So many human players have their own playing styles; aiming for the diagonals or the north and south squares at the early stage of the game. Some styles may differ significantly from others, however, they all employ similar strategies.
Game theorist will often use the values of positive infinity and negative infinity to denote a winning and a losing position respectively with the assumption that these positions are the very best and worst positions. We implement this theory by assigning values to each square on the Othello board based on the criteria highlighted in section 4. 1. Based on the different game strategies we employed, we implemented and tinkered with the minimax alpha beta pruning. Minimax was used to determine which move was optimal given the evaluation function. We tried minimax depth from 3 to 10, hoping to get a more competitive Othello computer player. It turned out that the depth difference did not significantly increase the players chance of winning the game, it however, increase the amount of search. Among the three game strategies we implemented, weighed square advantage was most optimal. We, however, began to experience a bit of a lag when depth gets greater than 6. Essentially, the game tree search will cost approximately 1056 milliseconds if we were to consider all the opponents possible moves. Competing with an intermediate class human Othello player, the program was able to secure some wins. We, however, could not implements some ideas we had in mind such as computer vs computer playing each other, learning move advantages and saving (or recording) it’s experiences for future use.
After running or playing the game several times we came onto a conclusion saying that the game is not of a professional level, it plays like an average human player. Since for every 5 games, we found that human player won almost 3 of them. The game actually played quite well with the human player who was new to the game, even if they develop some simple strategies.
While talking about the performance of the game we can say that the performance or the time taken by the program to implement a move is quite reasonable. The program at an average took 15-20 seconds if we try to increase the heuristics and at the hardest level.
Possible future work
We can try to put more playing strength as a future aspect of the game. One of the ways of achieving this is by boosting the playing capability with the use of an opening book. A book containing the common opening that can become advantages and can declare positions that are not advantages so the program should not play it.
Another way to make the game more competitive is by making the game learn, which means remembering the moves that made the computer player win the game in the past. The program could be made more realistic for a player by allowing the player to retrace the game once finished and trying to tell the wrong moves that the player made while playing the game. This can make the program not just a playing game but the game with teaching abilities.