Introduction to Artificial Intelligence, Spring 1997
Final Project: Othello Game
Prof. Randy Beer
Download my Othello Game
Othello is a board game that two players play against each other. The two players, here called Black and White, try to win the game by having more number of discs than the other player.
Rules for Othello:
The problem I want to deal with in this project is that when the option "play against computer" is chosen, I want the computer to play intelligently by choosing legal and smart moves. Therefore, I would like to use artificial intelligence to solve the problem. I choose to use minimax approach in my project.
Minimax and Othello
Minimax is an algorithm to search for a best move. The minimax algorithm is a recursive algorithm that takes as arguments the current layout of the game board. However, in my project, I do not use recursion because I want to debug the program easily. Therefore, I use the function Computer_Choose_Move that will find the maximum cost which will evaluate the costs from the function Find_Min_Of_Black. The function Find_Min_Of_Black will find the minimum cost from the function Find_Max_Of_White, and the function Find_Max_Of_White will find the maximum cost from the function Eval_White_Number which will count the number of white in the board. If we want to search more than two minimax levels, we then can put more functions which will call one another to find minimum and maximum. To be clear, look at the figure how this program is done:
This figure shows how this minimax is approached. It is a simple idea that when I want a best move, I want to maximize my discs, but my opponent is trying to minimize my number of discs on the board, as shown as the minimize level. I also want to maximize the number of my discs on the board for the following move too. Therefore, the deeper the search goes, the more intelligent the computer is. The first approach I have tried has only two minimax levels.
After I had done with debugging my code errors, I tested my program with a computer Othello at the web site "http://www.netfront.net/othello/." The result of the game playing against the computer was my victory over the web Othello. I was satisfied with the test. However, I still wanted to try to develop the program to make the computer more intelligent.
Explanation of Code
This program allows players to choose choices from the option menu. There are options that players can choose: play against computer, play with another player, save game, load game, decide the winner, quit game, and even choose the level of the computer. However, I want to concentrate on explaining the code on AI components in this program. The following functions are the functions that are important to the AI components
This function will scan each position on the board to find all possible moves. Then it will determine the cost of the position in each direction. It will set the cost to be maximum cost if it is greater than the maximum. At this point the function will call another function, i.e. Find_Min_Of_Black. When all positions are checked and the function has the position that has the minimum. The function will pass the position as reference.
The algorithm of this function is the same as the above function (2) except that this function will find the maximum of the cost. Besides that, this function will have option of choosing the level of search. It can stop the level of search by just calling the function Eval_White_Number( ) which will evaluate the cost of every node or the function can call Find_Max_Of_White( ) to put some more levels of search.
The victory of my Othello game proves that the program does not make illegal or stupid move anymore. At least it could beat another computer level. During the last week before the due date of this program, I have tried to improve the program by putting several more search levels to the program. I now have four intelligent levels: Beginner (the first version), Semipro (three minimax levels), Pro (four minimax levels), and God of Othello (five minimax levels). However, I have found that the third and the forth level would take too long time to search. That is because the minimax algorithm will take a long time if there are many branches to search. The solution for this problem will be the alpha-beta approach which will take a lot less time than minimax. However, the minimax approach has been done successfully in this project.