Towards the unification of intuitive and formal game concepts with applications to computer chess

In computer game development, an interesting point which has been little or no studied at all is the formalization of intuition such as game playing concepts, including playing style. This work is devoted to bridge the gap between human reasoning in game playing and heuristic game playing algorithms. The idea is motivated as follows. In most chess-like games there exist many intuition-oriented concepts such as capture, attack, defence, threaten, blocked position, sacrifice, zugzwang position and different playing styles such as aggressive, conservative, tactical and positional. Most human players use to manage these concepts, pergaps in an intuitive way, as they were not well formalized in a precise manner. A good formalization of these concepts would be an important step towards the automation of human reasoning in chess (and other strategy games) for better understanding of the game, thus leading to better playing. The goal of this research is to take a first step towards the unification of both "paradigms", namely human reasoning in game play and more formal heuristic concepts. We focus on computer chess as an example but the result could be also applied to most two-player zero-sum perfect information games. The applications of such a formulation are practical, such as better game understanding and opponent modeling, as well as educational: it would be nice to have these concepts somehow formalized. Then we suggest a way of transfering these intuitions into formal definitions. We propose an interpretation technique for describing chess positions and evaluation functions. The technique consists of interpreting and mapping part of the algorithmic scenario into quantities such as integer numbers. With such a mapping a given concept is likely to be described in a very precise way. As an application we look for candidate definitions of the following concepts: attack, defence, threat, sacrifice, zugzwang, aggressive play and defensive play. For each one of them we use the previous technique and propose a formal definition. Thus we give the first formulation of game playing styles -at least to the author's knowledge- and we show how this definition goes through for the game of chess. We describe different possibilities when moving from intuition to the formal setting, varying from a simple formulation through a connectionist approach. Then we show as an application how an evaluation function can be modified in order to include a given concept. This new evaluation function should take into account the degree of presence of the given concept (eg. how defensive is a given position) and thus it can be incorporated into a computer chess program. An advantage of allowing one to modify in such a manner an evaluation function is that one can combine different evaluation functions and -perhaps- get the better of each one of them. Although this is a first step in the given direction, some more difficult tasks will remain, such as the formalization of the so called positional, strategic and tactical play. References B. Abramson. Learning expected-outcome evaluators in chess. In H. Berliner, editor, Proceedings of the AAAI Spring Symposium on Computer Game Playing, pages 26-28, Stanford University, 1988. B. Abramson. On learning and testing evaluation functions. Journal of Experimental and Theoretical Artificial Intelligence, 2(3):182-193, 1990. T. S. Anantharaman. Evaluation tuning for computer chess: Linear discriminant methods. International Computer Chess Association Journal, 20(4):224-242, 1997. E. B. Baum, Warren D. Smith. Best Play for Imperfect Players and Game Tree Search. 1993 J. Fürnkranz. Machine Learning in Computer Chess: The Next Generation Austrian Research Institute for Artificial Intelligence, Vienna, TR-96-11, 1996. A. Plaat, J. Schaeffer, W. Pijls and A. De Bruin. Best-First Fixed-Depth Game-Tree Search in Practice. IJCAI'95, Montreal. J. Schaeffer, P. Lu, D. Szafron and R. Lake. A Re-examination of Brute-Force Search Games: Planning and Learning, Chapel Hill, N.C., pp. 51-58, 1993. AAAI Report FS9302.