EUROCAST 1999 Computer Aided Systems Theory: Automatic Players for Computer Games

Computer Aided Systems Theory – EUROCAST’99:
A Selection of Papers from the 7th International Workshop on Computer Aided Systems Theory Vienna, Austria, September 29 – October 2, 1999 Proceedings
Lecture Notes in Computer Science LNCS 1798

Automatic Players for Computer Games

Author: Werner DePauli-Schimanovich-Göttig
Edited: Franz Pichler, Roberto Moreno-Díaz, Peter Kopacek
Publisher: Springer International Publishing
Language: English
Publication: 26 July 2000
ISBN10: 3540678220
ISBN13: 9783540678229


Automatic Players for Computer Games (Werner DePauli-Schimanovich-Göttig pp. 588-600)

1 Introduction

One of the most important fields of research in computer science is the investigation of intelligent agents for the web which should search in the net for informations. Usually these agents are cooperating and form a working group of „multi agents“. But these groups or different agents can also stay in competition to each other. In both cases we have to model the behavior of the agents, i.e. to program a set of rules (consisting of preconditions and actions) which tells every agent what he has to do.

The present rapid development of the web (and other networks and information system) gives us the need to develop proper methods of modeling the intelligent agents. Sometimes these methods already exist more or less in principle, even when they are not yet in the final applicable form. An example for such a preliminary method is the design of automatic players for games. A lot of research has been done on this field, and the experiences and insights gained from this research can partially be used for the modelling of agents.

The following report presents an overview on different concepts and methods to program automatic players for games. The main focus in this presentation is on the methods developed by the author during his research and teaching on this field at the University Vienna.

2 Search Methods for Computer Chess

Norbert Wiener wrote in his famous book Cybernetics (first edition 1948) after the main chapters 1 to 8 an appendix about a chess playing machine. He quoted there the article „Theorie der Gesellschafts-Spiele” (i.e. theory of games) of Johann von Neumann, In this article von Neumann developed for the first time his theory of finite games with the main theorem: „Every finite game has an optimal strategy.” Later Oskar Morgenstern applied the von Neumann theory of games to economics and together they published the famous book „Game Theory and Economic
Behavior” (cf Neumann & Morgenstern). In the theory of games developed by von Neumann we distinguish between games in extensional form and games in normal form. For our investigation here we consider only the games in extensional form.


This game is similar to Kalaha, which contains 6 holes for each player with 6 stones in each hole at the starting position, and 1 kalah-hole. Kalah4 has only 4 holes with 4 stones, and 1 (empty) kalah-hole (for both players at the beginning). My student Wolfgang Wiesbauer and I programmed an optimal player for Kalah4. With this diminutive player we could test and improve the evaluation function of Kalah6. Therefore also our heuristic player for Kalaha was unbeatable for a long time.

Werner DePauli-Schimanovich-Göttig University of Vienna Institute for Statistics and Decision Support

F. Pichler, R. Moreno-Díaz, and P. Epraceh (G08) EUROCAST’99, LNCS 1798, pp. 588-600, 2000. © Springer-Verlag Belin Heidelberg 2000





Picture: Automatic Players for Computer Games