Logistello

The othello program Logistello, written by Michael Buro as PhD thesis work for the University of Paderborn in Germany, was considered the great othello champion of its day. Logistello inspired many other programs.

In August 1997, Logistello defeated the human world champion, Takeshi Murakami (this is a Japanese-language blog, which still offers some new othello news as of 2013), by 6-0 in a match at long time controls. The Othello Match of the Year describes the event.

In January 1998, Logistello retired from active tournament play, though it did return in 2002 to play another match against human Kenta Tominaga.

I think that Logistello was a success because its design is principled and thorough. By principled I mean that there is sound thinking behind its design decisions, often mathematical reasoning. Many programs, even successful ones, are put together ad hoc, “this seems to work, let’s go with it.” But that path is less likely to lead to the persistant dominance that Logistello showed in its day. Thorough means that it covered everything, it did everything at least reasonably well. A champion cannot have any big weakness.

references

Logistello
Michael Buro
The official home page, with a link to the C/C++ source code (including a 2002 bug fix).

Michael Buro’s Publication List
The references below are selected from this page; there are more.

An overview of Logistello (1997 PDF)
Michael Buro
Concisely describes Logistello’s evaluation function, selective search, opening book learning, and development history. This is a good place to start learning about the program.

Statistical feature combination for the evaluation of game positions (1995 PDF)
Michael Buro
There is an online abstract at JAIR. Compares different statistical regression techniques to find the best one for constructing Logistello’s evaluation function.

ProbCut: An effective selective extension of the alpha-beta algorithm (1995 PDF)
Michael Buro
Despite the title, this is about selective pruning, not search extension. Subtrees which are shown, by shallow search, to have little probability of affecting the search are pruned away. This is similar to the null-move heuristic popular in chess programs, except that the pruning cutoffs are estimated from data by a statistical technique.

Techniken für die Bewertung von Spielsituationen anhand von Beispielen (1994 PDF)
Michael Buro
Written in German. Buro’s PhD dissertation. The title means “Methods for the evaluation of game positions using examples”.

An evaluation function for othello based on statistics (1997 PDF)
Michael Buro
A description of Logistello’s old evaluation function, since superceded by the stronger one described below.

Experiments with Multi-ProbCut and a new high-quality evaluation function for othello (2000 PDF)
Michael Buro
Describes a new table-estimation technique for constructing Logistello’s evaluation function. The technique takes into account correlations between the features, resulting in a much stronger evaluator. Also gives improvements on the ProbCut pruning algorithm.

Toward opening book learning (1999 PDF)
Michael Buro
Learning an opening book so your program doesn’t repeat its mistakes. This is an offline method that searches for promising deviations from lines that lost in the past.

Takeshi Murakami vs. Logistello (1997 PDF)
Michael Buro
Diary-style account of the match against the human world champion.