PROPOSAL FOR PROJECT
Title:
OTHELLO
Students:
Batch:
B4
TUTOR:
Dr. Harish Karnick
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:
- We wanted to make a game of some kind, if possible. Out of the
suggestions given on the ESC101 site, Chess and Go seemed to be too complex
and thus, impractical, while snake game, etc. did not require us to make a
challenging algorithm like these games. So we settled for Othello, as it
seemed to be a balanced idea for a project.
- Some seniors, etc have also done othello - related projects. eg. Anand
Sinha, 3rd year
- We saw some examples on the net also:
- Project by Itamar Faybish:
- Home page of Othello - playing program 'Hannibal'
- Some C++ code for Othello
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
References:
- www.cs.columbia.edu/~evs/ml/othello.html
- www.intersrv.com/~dcross/
- www.cs.columbia.edu/~evs/ml/OthelloStudProj/Yi%20George/data/
- www.site-constructor.com/othello/Present/Basic_Strategy.html
- www.nada.kth.se/~gunnar/howto.html
- www.cam.org/~bigjeff/Hannibal.html
- www.geocities.com/ifaybish/othello.html
- yoda.cis.temple.edu:8080/UGAIWWW/lectures97/search/minimax/
(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)