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.
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...
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.
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.
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...
An old article on the elo classification system when I was young...
Return to my homepage