A few words about othello, chess and games programming

You will find in this page lot of informations I have gathered through the years regarding games programming, especially othello and chess.

About OTAGE, my othello program...

To play with OTAGE, follow this link

Games programming has always been a hobby of mine. I learned playing chess quite young, was a rated player in my teenage years, and learned to play Othello / Reversi when I was 14.

I wrote my first computer game program on a TRS-80 (a Z-80 based computer available in 1978) in assembly language, when I was a teenager. It was an othello program which was quite weak, but could defeat me from time to time. It used a classical alpha-beta algorithm, something I had read about in articles writen by the former chess master David Levy in the French Magazine "L'ordinateur individuel". The evaluation function was very bad at that time...

After some years dedicated to mathematics, I started again in 1984, in Fortran and on a mainframe system (a VAX-8600) at the Ecole Polytechnique. The evaluation function has improved, and the program was already much better. In 1987, I wrote a C/assembly 68000 version which ran on an amiga computer and on Sun 68020 based Workstations. The evaluation function was still static (and completely hand-made). It was tested by a quite good french player (ranked 10) and proved to be a good opponent.

After completing my PhD, I didn't have much time to work on games programming. However, a few years later, I returned to the field. I was working in global optimization, and genetic algorithms, and we had problems to devise probabilistic fitness functions. So I decided to dig out my old othello program and to try a few things for optimizing its evaluation function. The following article describes how we tried to tackle the problem. I am not that sure that this technic is really fitted for improving evaluation function, but we had some interesting successes in other fields, such as plane conflict resolution (look here ), or turbo code optimization for satellite digital transmissions (look here )!

The article above interested different people and I had some interesting remarks by my friend JC Weill about it, regarding the evaluation function and its poor structure (JCW wrote many computer games programs, and his chess program won, I think, a microcomputer championship). As I hadn't time to improve the function by hand, I tried a different technic, a complete start from nothing with only statistic evaluation of the geometrical structure of the board. That was how the OTAGE program was born.

The OTAGE evaluation function is extremely simple. There are two basic terms: one comes from the liberties values (see article above) and the other comes from a statistical evaluation of 8 areas of the board: the 4 edges and the 4 3x3 corners. In the beginning, the program doesn't know anything about the value of the different configurations. It plays a lot of games against itself, and statistically records the results in a very simple way. Then, it tries to reproduce winning configurations and to escape losing ones.

OTAGE was tested on the Internet Othello Server (IOS) and ranked as high as 5. It was however no match for the best programs (Logistello, by Michael Buro, Keyano from J. Schaeffer's team, Hannibal, etc). It definitely lacks an opening book (M. Buro approach to opening books in Othello is extremely interesting, but I never had the time to implement it).

OTAGE development has stopped for many reasons, mainly because I haven't the time to work on it. It might get revived if one of my students get a grant on this subject, but that doesn't seem very probable.

I don't provide the source code of the program. I still consider OTAGE as unfinished, with lot of tweaks and workarounds, and don't want to distribute such a mess...

If you want to learn more about Othello programming, visit Michael Buro's homepage. Logistello (his program) is definitely the reference.

A chinese checkers program

A few months ago, some friends decided to launch a chinese checkers computer tournament. Everyone was to write a program and to enter it. I decided to take the opportunity to try to write quickly something in Object Caml, which is now the language I am using, just to prove that OCAML was certainly the fastest way to have something running, and that the program would be quite competitive anyway. In fact, it turned out that I was the only one to complete the program... You lazy guys... The source code is here in OCAML. Have fun with it... Honestly, the program is not a too bad opponent, and there are some ideas about move generations in chinese checkers that I would have loved to discuss with other CC programmers. You need OCAML to compile the program.

An Awele program

Some of my students decided to write an Awele program in 2004. So I wrote mine... You can play online with it with this link .


Abalone is a very addictive game, and a project that my students had to complete last year. As I always write the program before, this is the source code of an Abalone program in tgz format. There again, you need OCAML to compile it. You can play online with it by following this link .


Quarto is a very interesting game to program as the evaluation function may be not symmetrical. You can play quarto online with my program by following this link .

About checkers

There are two other kind of checkers, american checkers (played on a 8x8 board) and international checkers (played on a 10x10 board). Rules are slightly different. If you want to learn everything about checkers, just go to J. Schaeffer's homepage. His program Chinook is currently unbeatable at 8x8 checkers...

I am currently writing an 10x10 checkers program (in OCAML again). I will probably put it on the net as soon as it is completed...

And chess ?

Chess and chess programming was my main interest. I was a rated player when I was younger and my parents bought me one of the first computer chess board, the Fidelity Electronics Chess Challenger. The program was written by the Spracklen, who later wrote the Sargon programs for microcomputers. I bought the Sargon III program for the apple II, and it was certainly a wonderful opponent at this time (early 80). I still used it on the Amiga. When I had my first PC, I bought the mychess program by Marty Hirsch. Now, I own the Chessmaster 7000, mainly for my kids. They learned to play with it and it has many pleasant features for children, such as having opponents with different personalities.

For playing myself, or for games analysis, I use the Rebel Decade 3.0 program. It is the free version of the excellent Rebel program by Ed Schroder. Have a look at its homepage. Rebel is definitely not what you want for fancy interfaces, but its way of playing is extremely interesting. For analysis, it is easy to use and the databases functions are really useful. Ed Shroder left his company a few years ago. His homepage is now here . You can download his new version of Rebel (which is now free), called ProDeo here .

It took me a long time to decide to write a chess program. Then in 2005, some of my students challenged me to write a chess program in full ADA based on the bitboard technique. I like challenges, so I wrote LOVELACE. The program is very bad (around 1800 ELO I would say), endgames are terrible, the evaluation function is poor, and no "good" heuristics are implemented, but that was the best I could do in one month and working only part time on it. It implements part of the xboard protocol and can be used as an xboard engine. The code is available here . It is mainly of interest for ADA students, or game programming students; ADA is still much more readable than C... I will design a JAVA interface for playing online when I have some time available.

For people interested, there is a much better souce code available for free: crafty. Have a look at its author homepage .

Recently the fruit program was also released in the public domain. It is extremely strong, even stronger than some commercial engines. The binaries and sources are available here for windows and here for linux.

General informations about games programming algorithms

I wrote a book about computer science and artificial intelligence "Intelligence Artificelle et Informatique Théorique" which included a large chapter about games programming. It is, I think, a quite concise and up-to-date description of modern algorithms in games programming, including SSS*, Nega-C*, MTD(f), Iter alpha-beta, hash and transposition tables, etc... There are also discussions regarding chess programming and classical problems in that area. The chapter is available in postscript and pdf, but it is in french... Sorry for english only readers...

However, there are also here a few articles written in english about games programming on this site. Two extremely interesting articles here and here by Aske Plaat, Jonathan Schaeffer and others comparing alpha-beta, SSS* and MTD(f). There is also Aske Plaat PhD thesis, which is an excellent introduction to games algorithms. There is also a good presentation of MTD(f) in HTML format. All of this comes from Aske Plaat excellent web site.

An article by Jean-Christophe Weill about the NegaC* algorithm along with the PhD thesis of JC Weill, which is extremely interesting, regarding parallelism and chess programming. The PhD thesis is in french however.

Philosophical discussions

In my younger days, I was extremely interested in Artificial Intelligence (I had my PhD in non-classical logic) and its philosophical implications. I think that most things related to chess, chess programming, or chess psychology are relevant to other human activities, and human activities modeling, and that's one of the reason of the major interest in that field. I wrote an article about the application to Air Traffic Control of such principles. It is more a funny thing than anything else, but you can have a look...

Chess playing has been one of the first topics studied by psychologists. The first studies were conducted by Binet around 1894. He considered blind playing and the masters' internal representation of the chessboard. In 1925, a sovietic team including Diakov, Petrovsky and Roudik conducted a survey during Moscow tournament, where Lasker, Tartacover, Reti, Torre and others were competing. Later, Miller in the US, de Groot in the Netherlands, and Nicolai Kroguious in the Soviet union, among the most famous, conducted similar works. Moreover, the original goal of Artificial Intelligence was to model human reasoning. Since chess playing is one of the most prestigious symbols of human intelligence, it is not surprising that some of the founding fathers of AI (Newell, Simon and Shaw, among others) very soon took active interest in chess playing (as soon as 1957). NSS, one of the very first AI computer programs, was a chess program. Since then, chess remained one of the most, if not the most commonly studied topics in AI. Some tremendous failures occurred, but some significant successes were obtained during the last years.

One of my favorite quote on that subject is from Hans Berliner:
"I consider the most important trend was that computers got considerably faster in these last 50 years. In this process, we found that many things for which we had at best anthropomorphic solutions, which in many cases failed to capture the real gist of a human's method, could be done by more brute-forcish methods that merely enumerated until a satisfactory solution was found. If this is heresy, so be it."
After completing my PhD, I was completely convinced by the above point of view. Efficient programs do not rely on human knowledge. This doesn't mean that knowledge modeling is not interesting. It can be useful, for example, to have a chess program playing more "like a human being", just because it would be more fun.

This subject was the center of the debate in AI for years (until the late 80). It is, for example, extremely interesting to search statistically the MIT AI lab bibliography database to see how many things were written on human knowledge modeling, and how the debate was hot in the 80's. Philosophers wrote articles about it (John Searle's "chinese room argument" was quite famous). Marvin Minsky was one of the most famous defender of the cognitive school of AI, and was one of the more harmful. There are lot of interesting books and you will find here a bibtex bibliography, which is quite messy, but contains lot of things.

Now the "cognitive" school of artifical intelligence is almost dead. Cognitive sciences have mainly returned to the field of neuro-sciences, and the war is over. However , discussions still arise from time to time about chess and AI. Just have a look at the rec.games.chess.computers newsgroup...

Other subjects

An old article on the elo classification system when I was young...

Return to my homepage

Last Update: