Othello A.I

A class also has objects which contain data and methods that act on data, this functionality allows the reuse of code, which models and organize very large applications. The classes defined for this game handles all the initializations, logging of moves played and the actual game. The game reads a size in an input text file that will generate the board with the dimensions it reads from the file. The naming of functions and initializations a style of camel case is used for better reading and understanding the functionality of functions.

The class Game that receives the size of the game as its parameter consists of various functions and initializations. Firstly, this class initializes the board matrix (placing four pieces in the middle of the board, two black initialized as B and two white initialized as W), the rest of the matrix will be an empty grid initialized as E. The board matrix controls its storage and access as it is initialized as a dynamic array.

There are eight possible directions each piece can move in; top, bottom, left, right, top right, top left, bottom right and bottom left. this function is the random number generator which plays as W. Taking a random move without doing any evaluation, the move is in the most basic version chosen among all possible legal moves available to a player, every move is likely to be taken as the next. This can be considered as the play of an inexpert human player or as an AI without implemented intelligence, during testing of this purely random player gave a terribly bad opponent. The algorithms start close to each other, then there is a change as the board size increases. The change observed in the figure above is expected since the minimax algorithm has logic for every move it plays, in that instance, minimax always plays the best moves causing it to outplay random algorithm. However, at larger board sizes the random algorithm managed to get away with a few games. Every time the minimax maximises its winning chance the random algorithm always has a chance to flipping more pieces on the board so that is a huge advantage for the random algorithm. The main aim of this experiment was the implementation of a board game Othello. The intent was to examine the performance of two different algorithms playing against each other and record the history of moves to determine the best algorithm. The method of approach was the usage of the C++ programming language.

The implementation of the Othello game is a success, every requirement is met and the programme performs as expected. The approach used for the implementation which involves the usage of classes and various functions was a good approach to produce suitable results during testing. A game tree has become the majority approach method for most game solvers, most algorithms are based on minimax tree search. The intelligence lies in the valuation function which uses operations for utilising a deep neural network that finds an ideal move among the valid choices [3]. Fundamentally, the minimax tree search and other tree search techniques find best next move by reckoning all probable passages and pick the one that can bring the maximum constructive solution [3]. The deeper the search depth, so is its effectiveness [3]. However, time complexity grows exponentially with search depth, which limits the run-time performance of the algorithm [3]. Reversi, also known as Othello, is a two-player game, where players take turns placing black and white pieces black always going first in empty blocks on the grid of an N?N board. When two pieces of one player flank a consecutive row, column, or diagonal of an opponent’s pieces, they may be flipped over. Once the board is filled or neither player has a legal move, the player with the most pieces wins [1]. The field of Artificial Intelligence (AI) is formerly at the cutting edge in Computer Science and Software development [2]. AI systems are part of many of the world’s devices and technologies, such as AI in games. AI in games is used to analyse and play board games, by evaluating the possible moves a player can make and choosing the most optimal move. The approach has been used to create AIs capable of playing board games such as Chess, Tic Tac Toe and Gomoku [2]. The main progression of this report is focused on creating two AI algorithms using a C++ programming language that can play the board game Reversi, which is based around placing black and white pieces on the N?N board where N is 4 ? N ? 16 while flipping the opponent’s pieces. Once the board is filled or neither player has a legal move, the player with the most pieces wins. This is achieved by the implementation of the Random Function Generator and the Minimax search algorithm, which uses operations for utilising a deep neural network that finds an ideal move among the valid choices [3]. The implemented algorithm for algorithm 1 is a minimax search algorithm which plays as black, whereas the implemented algorithm for algorithm 2 is a random number generator which plays a while. Minimax is a depth-search recursive algorithm. Minimax is an exhaustive search approach to find the ideal move among the valid choices. The algorithm works by searching down to the leaves at a previously set depth in the game three. For every one of the player’s valid moves is evaluate, so on constructing a tree of board states. Minimax uses a method that evaluates a game’s decision to ensure that the move chosen maximises a favourable outcome for the next move [1]. In this Othello game as the minimax algorithm evaluates the best move the algorithm will return a move that increases the player’s score by two points over the one that increases the score by one point. So, the minimax search will always optimise the winning condition. The Othello game starts with four pieces placed in the middle of the board, two black and two white. A legal move must be adjacent to other pieces on the board, and be placed such that it flocks over at least one piece. Black takes the first turn followed by white [!]. Black has at least four legal moves, flipping one piece of the opponents. The figure below illustrates the opening move. The figure above demonstrates a 4?4 Othello with black and white pieces in the middle of the board.

Taking the first move has no winning advantage, so whether an algorithm takes the first or second move does not guarantee a win at the end of the game. The random generator algorithm has no impeccable evaluation function but rather uses the function; rand () % size of the board which randomises any position within the dimensions of the board given it sees empty space. See source code below. The randomness of the result is determined by the choice of the seed. In this Othello game, a time seed is used to which uses the computer’s internal clock to control the choice of the seed [?]. As time is continuously changing, the seed is forever changing, which will make the random algorithm generate different results every time it runs [?]. Using specific seed for every test will generate a predictable sequence of values. By default, the random generator algorithm has no impeccable intelligence in any form. The algorithm merely recognises a fork (two winning ways). The random generator algorithm, for that matter, it has a number of disadvantages as a winning algorithm, it does not have the best decision making when it has to maximise its winning move. The main feature in this Reversi game implementation is the usage of Object-Oriented Programming (OOP) or simply a class and utility functions to test the implemented code. A class is a user-defined data type, which has its own data members and member functions, in that instance; a class make the code more maintainable.