|
Othello ... What can be said about this game ? It is one of the simplest to learn, and yet it is very difficult to master. In a way, much the same as Go - except that telling when a game is over is easy. The rules being simple, and the number of moves usually limited to seven or so, it is ideal to learn computer games programming. Almost since the dawn of computer games, people have started with Othello. It is the next game one usually tries to program after tic-tac-toe. The ultimate goal being to maximize your color, there seems to be an obvious strategy: try to maximize it right from the start. As anyone who as played more than a few games will tell you, this is actually one of the worst strategies. Once you understand that the corners are important, you can do better. From that point, you can devise many refinements, leading to a whole theory on the way of playing on the borders. Second idea, you might understand that having many legal moves (with possibly good ones) to choose from is better than having a few (possibly only bad ones). And so is it for your opponent. Othello is not at all like tic-tac-toe: it is not an easy game. It is closer to Chess or Go. Back in 1991, there were Othello tournaments between players and machines. My math teacher, Marc Tastet, was a champion (he later became World Champion in 1992 (or is it 1993?)). Together with a friend of mine, Christophe Lanuit , we decided that we could try to write a computer program that wouldn't be so bad. The next tournament was five weeks later, and we wanted to compete. Christophe was a good player, and he wrote the so-called "evaluation function" -- the heart, the "feeling", the "knowledge of the game" of the machine. This tells the machine what the game is: what is a good position, what is not, on a static point of view, just by "having a look" at the board. I learned some AI techniques, namely alpha-beta, that added the "brain", the "intelligence", the "depth of thought". This way, building on its "heart", the machine could explore many of the possible moves, predicting the way the opponent would play, and deciding what to play. There was some handcrafted assembler to help the poor Turbo Pascal compiler, and we stole a few things from another competing program (the Thor openings library). It was about 4000 lines long, including about 400 lines of assembler, and ran on my 286/12Mhz under MS-DOS 3.3. This was a time where there was no graphic interface to worry about, so programs were short. I feel strange to feel so old at my age. We were ready on time, and decided to name the program "Cinq Semaines" (Five Weeks). Most other programs had taken moths or even years to develop. The first tournament was not a complete success; however, we won the second one, running on the already old 286/12Mhz, on July 6, 1991. I can tell because I still have the little cheap trophy. The program had the following features, for those who know:
A few years later, in 1995, a new technique was introduced to enhance alpha-beta: basically, the idea is to compute an evaluation at a certain depth and use it as an "biased evaluator" for the next depth. This way one can statistically "cut" whole branches of the search tree, leading to a large increase in the maximum possible depth. I had had some thoughts about doing something like this, but at the time I did not have enough knowledge of probabilities. Of course you do not have to believe me on this ! There are no more computer vs humans tournaments. From what I have heard, computer programs, though they have not "resolved" the game (the way it has been done for some other simpler games), are considered invincible. I do not know if this a good thing, and it makes me sad in some way. A few computer tournaments are still organized.
Last modified June 16, 1997. Stephane Belmon (sbelmon@cse.ucsd.edu)
|