PROPOSAL FOR PROJECT






Objective:
COMPUTER PLAYS A GAME OF OTHELLO AGAINST A HUMAN. WE WANT THE BEST ALGORITHM FOR THE GAME OF THE COMPUTER. TO FIND BEST MOVE OF COMPUTER, WE INTEND TO USE SEARCH ALGORITHMS LIKE MINIMAX WITH ALPHA - BETA PRUNING FOR EFFICIENCY. IT SHOULD BE GOOD ENOUGH TO EVALUATE THE GAME 3-4 MOVES IN ADVANCE MOST OF THE TIME. BUT WE WILL SEARCH AS MUCH AS WE CAN WITHIN THE LIMITS OF PRACTICAL WORKING OF PROGRAM.

RULES OF OTHELLO

BASIC STRATEGY OF OTHELLO

Motivation:

Notation used in Othello:





INPUT AND OUTPUT:

BOUNDARY CONDITIONS, ETC.

Input is done through mouse. If the mouse is over a square where a move can be made by the human player, the colour of the square will change. Only in this state, if the human left - clicks on the mouse, the move will be made. So incorrect input is avoided. We also intend to have an option of 'forfeit move'. This must be used when the user has no valid move. However, there should be no need to indicate to the user when such a situation has occured: we can asssume that when no valid move is available, the human will always forfeit the move. If the computer finds no valid move, then its response should depend on whether the previous move by the human was forfeited, or not. If not, the computer forfeits its move, but otherwise, we can say that no more valid moves are possible for anyone. So the game ends.



Division of project into parts, etc.

WE SHOULD BE ABLE TO DIVIDE THE PROJECT INTO SOME MAIN PARTS. eg. GRAPHICS ( INPUT / OUTPUT ), CHECKING FOR CORRECTNESS OF A MOVE, FINDING THE ALGORITHM WE WILL USE, ETC. BUT THE MAIN PARTS SEEM TO BE : GRAPHICS AND FINDING BEST ALGORITHM. OTHER ASPECTS ARE DEPENDENT ON THESE AND SHOULDN'T BE WORKED ON UNTIL THESE ARE COMPLETED. MOST PROBABLY I WILL WORK ON THE GRAPHICS WHILE GOPALK AND DJADHAV WILL WORK ON THE ALGORITHM, ETC FOR NOW. ONCE THE BASIC FOUNDATION FOR THE PROJECT HAS BEEN LAID, WE CAN WORK ON THE REST. IF POSSIBLE, WE INTEND TO HAVE DIFFERENT FILES FOR DIFFERENT PARTS OF THE PROGRAM



Details of graphics, etc.

For graphics, we will need to create an applet. Each time we get an input, we have to redraw the board. The board itself can be made into an object. All the mouse operations, and the responses to them can be made into another object. The two objects have to interact with each other. We can also have methods for these objects, like drawBoard(), highlightValidSquare(), getValidInput(), etc.



Details of algorithms, etc.



It is said that there is no one best algorithm for Othello. But these are some useful algorithms we found on the net:
Something called the minimax search algorithm seems to be very useful for games like Othello:
Minimax Algorithm

But it is very time - consuming and impractical. So it is used with alpha - beta pruning. These are some of the links that we got for it:

TO GET THE EXACT VALUES OF ALPHA, BETA, ETC. THAT WORK BEST, WE WILL HAVE TO DO SOME EXPERIMENTATION OURSELVES, LIKE PLAYING ONE ALGORITHM AGAINST ANOTHER.

Here is a list of named openings in Othello: Click Here

Here is a page on the inner workings of strong Othello programs: Click Here




(MOST OF THESE PAGES PAGES ARE GIVEN JUST AS EXAMPLES. SO IT IS POSSIBLE THAT SOME IMAGES, ETC. MAY BE MISSING FROM SOME OF THEM. BUT THE FILES USED TO DEMONSTRATE INPUT AND OUTPUT ARE COMPLETE)

BACK TO INDEX