Last updated : July, 2006.

All rights reserved.

@F.Pittner

mail@tothello.com

How Tothello works

If you are interested in how Tothello learned to play reversi please read the part Tothello: learn to play.

Search

Tothello now uses a combination of Alpha-beta, Negascout and Multi ProbCut search methods. To have a good search mechanism you need the algorithm, a hash table and a very good evaluation function. I would say the latter is the most important. Having a perfect evaluation function you don’t even need the first two . Unfortunately this is not the case with the othello game. 

Evaluation function

Tothello uses a combination of pattern based evaluation and additional features’ evaluation. I worked out some special patterns which presumably are very useful. In addition to this Tothello evaluates parity and six types of mobility. Despite the fact that Tothello’s normal game evaluation function is not as accurate as evals of other top player programs. This is the reason why Tothello achieved “only“ 2300 points on the CGS server (random normal othello game mode). Top player programs achieved 2500-2600 points. Eventually I intend to perfect the evaluation function.

Notwithstanding Tothello achieved 2819 points in reversed games due to the fact that its evaluation function is more accurate in reversed games. Up to now there were no real opponent programs to compete with on the CGS server, therefore I presume that the real strength level of Tothello in anti games is between 2500 and 2600 points.

Hash table

Tothello uses a hash table whereby both the upper and lower evaluation bounds are stored into the hash table along with the best move, search depth, etc.

Learning

There is only one learning task built into Tothello which adds the current solved game to its opening book. A separate program was used for sophisticated learning.

Meta programming

Tothello was developed in assembly and Visual C++. When I started to develop Tothello one of my goals was to make it able to play all of the 4x4, 5x5, 6x6,7x7, 8x8, normal and reversed game types. It would have been hard to write manually all necessary routines for these different board sizes. It could have also led to lots of bugs and errors. When a program is written, in addition to the working routines verification and testing routines are also needed. Therefore I developed a separate routine generator program written in Visual Basic for which I generated the board size & game type dependent routines (assembler and Visual C++): i.e. to calculate board position dependent coefficients, verify these coefficients, calculate the evaluation function and initialize the given game type & size. This allows me to change the pattern based evaluation functions very quickly, because the generation is done automatically (without further programming). Of course at the end the coefficients need to be tuned. But this meta-programming helped a lot and reduced the development time as well as the testing time.

Artificial intelligence

Even though I don’t consider Tothello to be artificially intelligent, and despite the fact that it will definitely beat you in your first anti game (playing against the computer), I think we still need some time to properly understand and evaluate the fact that game playing knowledge is comprised in a few megabytes of coefficients. This is really interesting.

At this stage kindly allow me to raise a point: this game – like some others – does not seem to have an equivalent and exact mathematical solution. In addition the mathematical representations - I have seen so far - are fairly inaccurate and that’s why it is difficult to build a good program. I am not referring here to the fact that the game tree is fairly big, but to the perfect representation of a single board position. We don’t have an exact formula, equation which would provide us with the perfect outcome of the game.

We keep searching for mathematical models for all the problems and phenomena we encounter in our lives.  What if there is no perfect mathematical representation of what we are looking for and even the approximations are not so good. So what if there is a problem with our mathematics because it doesn’t represent nature too well? If someone says this is obvious, then I would argue against such a proposition, because everyone first tries to fit a new problem into already existing or new mathematical models without attempting first to change the basics of the mathematics used.

Graphics

The graphic user interface of Tothello was partially designed by A. Pollák.