ABSTRACT

ANTCHESS

Gabor Tatai Department of Computer Science, UCL

The defeat of Garry Kasparov, the World Champion, by IBM's Deep Blue is considered a landmark in computer performance and even AI. The next great event, another milestone in chess and Internet history, namely the "The World vs. Kasparov" game organized by MSN. The Champion defeated the world in a match lasting for several months (Jun. 21-Oct. 25, 1999) and played over the Internet. It was a landmark of cooperative play - 58.000 individuals submitted moves, 3 million distinct visitors watched on-line, via 28 million page views read from 75 different countries. Analysts have remarked on this game as being one of the best public chess games ever documented. Since these events chess is more popular then ever.

Agent researchers have joined this AI tradition to the extent of discussing the possibility of building agent-based chess programs. However, we know only a single attempt to create one: by A. Drogoul, with MARCH (Multi-Agent Reactive Chess). His paper, "When Ants Play Chess" was one of the most referenced papers in multi-agent systems (MAS) research in its time, which is significant indeed, because it combines the current favourite ant concept with reactive behaviour as well as with emergence and ideas on local and global strategies.

We have decided to attempt a rational reconstruction, and replicate and improve his algorithm in order to draw more detailed conclusions on the behaviour and capabilities of such a MAS. In addition have developed a sophisticated ant-based chess program and played several thousands of games on the Free Internet Chess site (FICS). We have concluded that these simulated ants with some cooperative behaviour can play at a level of an average chessclub player in spite of the total lack of a global strategy and the 1 move "visiblity horizont".

During the seminar I briefly introduce the audience how this agent/ant-based chess program was built and what is the real significance of treating a traditionally graph-search game problem as a reactive, agent-based one. Attendees will have the chance to test the chess program. If time allows I will talk about how a new model of the chess "environment" and the introduction of entropy (or "antropy") can help the ants to play more efficiently than without them.


Maintained by rbennett@cs.ucl.ac.uk