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

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

The automation of strategic thinking was covered by John von Neumann and Oskar Morgenstern in their book Theory of Games and Economic Behavior

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.

Something missing in the GGP course is a handy tutorial on how to write games in GDL. About the best I know of is Writing a game with GDL: Sim found via Google. The same author, Alex Landow, also put up a nice summary of GDL and an alternative version of chess.

Heuristic Search

Last updated on 12 Jan 2021
Published on 12 Jan 2021

Content Footer