Make your own free website on Tripod.com

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:

Problems

            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

        When we need the static values to evaluate, this function will do this task. It will first put the disc on the board, check the move, and flip. Then it just counts the number of White on the board and returns the value.

Search Tree

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.

Download my Othello Game