CMPS 391: Introduction to Artificial Intelligence, Spring 1997
Final Project: Othello Game
Jessada Wannasin
Prof. Randy Beer

Download my Othello Game

Introduction

            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:

• Every valid-move is to place your color on an empty position and can flip at least one opposing disc.
• A disc may outflank any number of discs in one or more rows - horizontally, vertically or diagonally - at the same time.
• Player may not skip over his own color disc to outflank an opposing disc.
• When it is no longer possible for either player to move, the game is over. Discs are counted and the player with the majority of his color discs face up on the board wins.

            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

• Computer_Choose_Move( int& Best_X, int& Best_Y);


        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.
 

• Find_Min_Of_Black( int x_in, int y_in );

 
        This function gets positions from the function Computer_Choose_Move( ) to evaluate the cost. The logical procedure is similar to the function but this function wants to find the minimum. When the function gets the value x_in and y_in, it will check the move and flip in the board. Then it will scan for the positions that Black can move and find the minimum cost for these moves. However, the cost will be evaluated by calling the function Find_Max_Of_White () to find the maximum in the next level of search.
 
• Find_Max_Of_White (int X_in, int Y_in);


        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.

• Eval_White_Number(int InX, int InY)

Conclusion

                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.