Othello Simulator

To make the AI opponent in my simulator looked at multiple different decision making algorithms for example different implementations of Monte Carlo methods but I ended up with a Minimax algorithm. I choose Minimax mainly because of limited amount of moves that are available for a player in Othello. This would lead the opponents AI not having such a high branching factor leading to less process time. 

A Minimax algorithm works by making a tree where each node represents an available decision for its parent node and the game state if that decision is chosen. It continues making branches down to a desired depth then i gives a value to the end state. The method of choosing this value depends on the game but essentially a large positive value is good and a large negative value is bad. Then it works up with it assuming that when it is the opponents turn (reprisented by the min areas) the opponent while chose the less favorable for the AI and on the AIs turn it choses the more favorable one. Then when it returns to the original parent node it choses the one with the highest value.

When it comes to the code that draws the Minimax tree I made a iterative function that creates a node then it checks if this node is at the desired search depth if not it creates a new node based on an available decision then it changes the game board based on the decision. It then checks again if it is at the desired depth it continues like that until it reaches the desired depth. It will when check get the return value that is represented by the AIs number of pieces subtracted by the players number of pieces. It then returns value to its parent node and then replaces the current value saved by the parent node if is greater then the old value and it is the AIs turn or if it is lesser then the current value and it is the players turn. If every decision that the parent has have been explored then it returns its value to its parent until it reaches the top. Then it choses the option with the highest value.