Frontier Software

Robert Laing's programing notes

Strategy Games

By Robert Laing

Concerned with the other end of the man-to-machine communication problem, predicate logic derives from efforts to formalise the properties of rational human thought. — Predicate Logic as Programming Language, Robert Kowalski

Getting computers to play strategy games has been a long standing hobby of mine, and two MooCs, both given by Stanford University’s Michael Genesereth, have been invaluable to me:

  1. Introduction to Logic
  2. General Game Playing

Games help thingify dry and academic logic theory. Developing GGP software has encouraged me to study the classics in artificial intelligence, which has an Atlantic divide in that European AI textbooks tend to use Prolog whereas US AI textbooks tend to use Lisp. This nationalism is extremely silly considering Prolog’s primary developer, Robert Kowalski, is an American expat while Lisp-AI-guru Berthold Horn was a classmate of my mom’s at the Deutsche Schule Johannesburg.

Genesereth encourages learning both Prolog and Lisp by offering two styles of Game Description Language (GDL):

Infix GDL (Prolog) Prefix GDL (Lisp)
p(a,Y) (p a ?y)
~p(a,Y) (not (p a ?y))
p(a,Y) & p(Y,c) (and (p a ?y) (p ?y c))
q(Y) :- p(a,Y) & p(Y,c) (<= (q ?y) (and (p a ?y) (p ?y c)))
q(Y) :- p(a,Y) & p(Y,c) (<= (q ?y) (p a ?y) (p ?y c))

The Lisp-style uses a format called Knowledge Interchange Format, and there are dozens of games available in foo.kif files via the public game repositories. There is supporting software at github, mainly written in Java which I’m not fond of.

Parenthetical Datalog Module Language describes a Racket library integrating Datalog, a US variant of Prolog, which as far as I understand it mainly differs in implementation in that it is akin to SQL in working from permanent rather than temporary storage.

Another MooC, also offered by Stanford, Jeff Ullman’s Automata Theory, was another aid to understanding this fascinating field.

Last updated on 12 Jan 2021
Published on 12 Jan 2021

Content Footer