Fast Interpreter for Logical Reasoning in General Game Playing

Jacek Mańdziuk , Maciej Świechowski

Abstract

In this paper, we present an efficient construction of the Game Description Language (GDL) interpreter. GDL is a first-order logic language used in the General Game Playing (GGP) framework. Syntactically, the language is a subset of Datalog and Prolog, and like those two, is based on facts and rules. Our aim was to achieve higher execution speed than anyone’s of the currently available tools, including other Prolog interpreters applied to GDL. Speed is a crucial factor of the state-space search methods used by most GGP agents, since the faster the GDL reasoner, the more game states can be evaluated in the allotted time. The cornerstone of our interpreter is the resolution tree which reflects the dependencies between rules. Our paradigm was to expedite any heavy workload to the preprocessing step in order to optimize the real-time usage. The proposed enhancements effectively maintain a balance between the time needed to build the internal data representation and the time required for data analysis during actual play. Therefore we refrain from using tree-based dictionary approaches such as TRIE to store the results of logical queries in favor of a memory-friendly linear representation and dynamic filters to reduce space complexity. Experimental results show that our interpreter outperforms the two most popular Prolog interpreters used by GGP programs: Yet Another Prolog (YAP) and ECLiPSe respectively in 22 and 26 games, out of the 28 tested. We give some insights into possible reasons for the edge of our approach over Prolog.
Author Jacek Mańdziuk ZSIMO
Jacek Mańdziuk,,
- Department of Artificial Intelligence and Computational Methods
, Maciej Świechowski
Maciej Świechowski,,
-
Journal seriesJournal of Logic and Computation, ISSN 0955-792X
Issue year2016
Vol26
No5
Pages1697-1727
Publication size in sheets1.5
Keywords in EnglishFirst-order logic, General Game Playing, Game Description Language, Prolog, Logical Programming
Abstract in PolishW pracy przedstawiony jest sposób budowy efektywnego interpretera języka GDL (Game Description Language) wykorzystywanego w zagadnieniu General Game Playing (GGP). GDL jest jeżykiem logiki pierwszego rzędu, syntaktycznie stanowiącym podzbiór PROLOGa. Zaproponowany interpreter swoją szybkością przewyższa wszystkie znane autorom interpretery języka GDL oraz PROLOGa. Kluczowym elementem interpretera jest efektywne obliczeniowo drzewo wywodu opisujące zależności pomiędzy regułami.
DOIDOI:10.1093/logcom/exu058
URL http://logcom.oxfordjournals.org/content/early/2014/10/01/logcom.exu058.abstract
Languageen angielski
Score (nominal)30
ScoreMinisterial score = 25.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 30.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.909 (2) - 2016=0.853 (5)
Citation count*0
Cite
Share Share



* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back