Computer Aided Systems Theory – EUROCAST 2011: Extended Abstracts
13th International Conference on Computer Aided Systems Theory
Las Palmas de Gran Canaria, Spain, February 6-11, 2011
Problems and Games as Models for AI-Systems
Author: Werner DePauli-Schimanovich
Edited: Alexis Quesada-Arencibia, José Carlos Rodríguez, Roberto Moreno-Díaz jr., Roberto Moreno-Díaz
Publisher: Universidad de Las Palmas de Gran Canaria
Language: English
Publication: 06 February 2011
ISBN10:
ISBN13: 9788469395608
Description:
The two-volume proceedings, LNCS 6927 and LNCS 6928, constitute the papers presented at the 13th International Conference on Computer Aided Systems Theory, EUROCAST 2011, held in February 2011 in Las Palmas de Gran Canaria, Spain. The total of 160 papers presented were carefully reviewed and selected for inclusion in the books. The contributions are organized in topical sections on concepts and formal tools; software applications; computation and simulation in modelling biological systems; intelligent information processing; heurist problem solving; computer aided systems optimization; model-based system design, simulation, and verification; computer vision and image processing; modelling and control of mechatronic systems; biomimetic software systems; computer-based methods for clinical and academic medicine; modeling and design of complex digital systems; mobile and autonomous transportation systems; traffic behaviour, modelling and optimization; mobile computing platforms and technologies; and engineering systems applications.
Article:
Problems and Games as Models for AI-Systems
Werner De Pauli-Schimanovich
Vienna University of Technology, Department Of Databases and A.l
Extended Abstract
Games and especially 1-Person- Games are defined exactly in mathematical language, and therefore often used to medialize problems in natural science or economics, maybe even of daily life. The following paper deals mainly with the different formalizations of problems and games in the natural sciences. Here a special focus is made onto Sprague-Grundy Theory SGT (see [1], [2] and [4]) which is translated into First Order Logic FOL, what yields an system of 5 axioms called Calculus of Winning CW (see [5]): this has the advantage that we mostly do not need to use Arithmetics, but only FOL or a theorem prover.
This way we can define classes of games with special proporties in a completely abstract way, or optimal strategies, but also counter-strategies to the opponent’s play, e.g. if the player is on the looser-street, or if both players have a drawn-strategy, which is not considered in SGT. Some classes of counterstrategies are discussed, and the decision which one would be the best to choose depends of course from heuristic criterions: First we have to guess the opponents strategy, e.g. assuming him as rational player (e.g. see [7]) using the alpha-beta-search (see [6]), secondly we have to decide what would be the best strategy to play against this. For both we need suitable heuristics (see [10]).
With the CW it is often more easy to find the core/kernel of a game, than with SGT. But it is more difficult to decomposit a game into 2 parts or to construct the sum of 2 given games. From the predicate-logical axioms and definitions of the CW the algorithms are deduced to construct the core of a game, e.g. end game of chess with 6 figures in about 50 hours (calculated by my student Wolfgang Wiesbauer), for what Ken Thompson needed some years ago 2 month.
Once you have the core you can construct the counter-strategies. This is e.g. very important for strong computer chess programs participating on the World Computer Chess Championship e.g., because they can set up on such an end-game database already in the middle game with about 12 to 15 figures or pawns.
Another important point investigated in this paper is the Relative Problem Solving RPS (see [8] and [9]), i.e. the solution of a problem using the solution-knowledge of another problem. Instead of the construction of an own solution-strategy for a problem P one can also seek an equivalent problem P*, which is already solved, and to which P can be reduced.
If one knows e.g. a solution-strategy for Rubik’s magic cube, which can shift and turn the corner cubies, than one can also use it for the solution of the baby cube 2x2x2, simulating the baby cube on the Rubik-Cube.
If one wants to solve the Master-Cube 4x4x4, he can only use a part of the known algorithms of the 3x3x3 cube (and also the 2x2x2 cube). We will try to use our knowledge about the 3x3x3 cube solution for the 4x4x4 cube, to search and learn as few as possible algorithms new. Such a solution will possibly be not very efficient, but works with only a little bit additional knowledge. Let’s call it therefore “knowledge-minimal“.
After the problems we study the games, of course in extensional form, because normal form is only interesting in economics. In this paper the SGT is important for Artificial Intelligence but e.g. also for semantics of predicate logic. E.g. for the quantifier game where one player is the Verifier and tries to verify a given formula, while his opponent, the Falsifier, tries to falsify it. Since such games can be infinitely long, the theorem of Zermelo-Neumann is no longer valid, because of the Axiom of Choice (AC) in set theory we have here the theorem of Gale-Stuart and therefore it may happen that neither of both players have a winning strategy, i.e. the formula is undecidable (see [3] and [11])!
References
[1] Banerji, Ranan A.l.: A Theoretical Approach, North Holland, N.Y. & Oxford, 1980.
[2] Cull, Paul, Ecklung Jr. E. F. Towers of Hanoi and Analysis of Algorithms, American Mathematical Monthly, Vol. 92, No. 6, June/July 1985.
[3] Casti, John, DePauli, Werner Gödel: A Life of Logic, Perseus Books, CambridgeMA, 2000.
[4] DePauli-Schimanovich, Werner Automatic Players for Computer Games. In: Springer LNCS1798, 2000. Reprint in: EUROPOLIS3, novum Verlag, 2005.
[5] DePauli-Schimanovich, Werner Calculus of Winning. In: Annals oft he Kurt Gödel Society, Vol.4, 2001. Reprint in: EUROPOLISS, 2005.
[6] Gaschnig, John. Performance Measurement and Analysis of certain Search Algorithms.
[7] Mishlove, Jeffrey. The Roots of Consciousness, Random house Bookworks, N.Y. & Berkeley, 1975. Newell, Allan& Ernst, Georg.
[8] GPS: A Case Study in Generality and Problem Solving, AP, NY, 1969.
[9] Nilsson, Nils.
Article: Problems and Games as Models for AI-Systems
Google: https://books.google.at/books?id=nTqqCAAAQBAJ
