Formal Game Representations

There are a few different specialized “languages” out there now for describing games. Perhaps because Abstract Strategy games are often quite “simple” in terms of rules complexity, these sorts of game description languages typically have examples that are abstract strategy games. (But also, I think, there’s probably an overlap between people interested in this topic and people who are interested in games that require an extraordinary amount of logical analysis to play.)

I have been very interested in this topic many times over the years as I became aware of various projects and aspects of this topic, and this post will be my attempt to outline some of my findings.

Early game description work / History

There is a relevant “History” section of the Wikipedia article on General Game Playing (https://en.wikipedia.org/wiki/General_game_playing#History). This is a page on Artificial Intelligence (AI) that can play multiple games – as opposed to a specialized program that just plays a single game like Chess, for example. The article says that this concept was first proposed by AI researcher Barney Pell in 1992, with something the article called a “Metagame System”. Pell’s research, at least some of it, is still available via the wayback machine, and I read through one article called “Metagame: A New Challenge For Games and Learning” (https://web.archive.org/web/20070706185808/http://www.barneypell.com/papers/metagame-olympiadUCAM-CL-TR-276.pdf) from 1992 that was surprisingly readable (and fascinating). In it, Pell says:

“In order to write programs which can accept a set of different games, we must specify how these games will be represented. Although fully-general representation languages are possible (like first-order logic or Turing Machines), it is likely that classes of games will be much more specific, especially those which can actually be produced by a generator. So, any representation language can be used, so long as the games produced are guaranteed to be unambiguous in the chosen representation, and so long as the semantics corresponding to the representation is clear. A natural method of representation, pursued in ([Pel92]), is by means of a game grammar.”

Metagame: A New Challenge For Games and Learning

“[Pel92]” here refers to a companion article titled Metagame in Symmetric Chess-Like Games. This second article does get far more into the weeds with details about the game grammar used to define games that the Metagame-playing AI will learn to play. I found it actually kind of disappointing, because much of the article is dedicated to defining the types of game the grammar will describe, and it was surprisingly limited in scope.

It’s worth saying a bit about the context of these papers, and noting that this research is all about developing AI. The premise here is that an AI that can play multiple games would be more useful than an AI that can just play one game. The whole point of this project was to be able to pit different AI against one another in a tournament. This grammar was going to be used both to more easily facilitate the AI learning the games, but also to generate new games so the AI would be playing something never before encountered.

This is probably worth repeating: The earliest effort to formalize a language for describing games was only undertaken in service of an effort to teach games to computers.

Zillions of Games

I remember playing a program over 20 years ago now called Zillions of Games (http://www.zillions-of-games.com/). The copyright on the ZoG website says 1998. I remember using it to play Othello and many Chess variants, and (perhaps more importantly) explore a ton of other games that I’d never heard of before Zillions. They were probably also games that it would have been near-impossible at the time for me to hunt down in physical form.

Zillions of Games came bundled with ~250 games, each of which was described individually in a .zrf (presumably “Zillions Rules File”). If you owned the full unlocked copy of the game (this was the shareware era when game demos were near ubiquitous), you could import your own ZRFs, and there was (amazingly still is!) a community of folks who spent time implementing new games.

I have a very distinct memory of liking Zillions of Games enough that I wanted to learn how to develop games for it. But I was in college at the time, and distracted by many other things vying for my attention.

You can find some information about ZoG, and the language used to encode the games, on the website, but also on Wikipedia (https://en.wikipedia.org/wiki/Zillions_of_Games). The description language for ZoG is lisp-looking, (with parenthesis everywhere). I only call this out because it’s influenced future projects with this gaol. ZoG had lots of limitations. It was notably not suitable for card games or other games that required any hidden information, probably because ZRF had no concept of variables!

It’s worth noting that, while it’s not exactly the same thing, I do see a parallel between ZRF creation and other platform-specific game creation languages, like Game Maker Studio’s GML, or Godot’s GDScript. Zillions of Games was a Game Engine as well as a product that allowed the user to play the games made in that engine. The games just happened to be board games.

Ludii

More recently, (in the last few years), I’ve been aware of a project called the Ludii General Game System (https://ludii.games/). This is (at least partially) the brain child of Cameron Browne, a game designer, computer scientist, and author, who is very well known in some abstract strategy game design circles. He wrote a book on connection games that I have on my shelf.

Ludii has some very interesting project goals, but more importantly, the project has now written description files for literally over 300 games. (There are over 2,000 games with descriptions for use in Zillions of Games, but that software is quite old now, and I think Ludii is far more interesting.)

You can download Ludii now, and play all of the games it comes bundled with, and even create your own .lud files and load them into the player. There is a language reference for Ludii (https://ludii.games/downloads/LudiiLanguageReference.pdf) that is 386 pages long!

To really dive into Ludii development, unfortunately, I don’t think the language reference is going to be enough. There is also a Ludii tutorials document, but I found it a bit disappointing in its brevity. As of this blog post, there are really only two pages that are particularly relevant to writing your own .lud files. This one on the “basics”: https://ludiitutorials.readthedocs.io/en/latest/lud_format_basics.html and another one on recreating the game Amazons in Ludii: https://ludiitutorials.readthedocs.io/en/latest/tutorial_amazons.html I also watched a nice introduction to Ludii on youtube. (https://www.youtube.com/watch?v=pTkO8h8RBBI)

I’m in the process of posting a few different places (in various BGG forums) to see if there are better tutorials that I’ve just been missing.

Other systems

For the sake of putting everything I know about this subject into this post, it’s worth noting there is another competitor to Ludii that may have been around even before it, called GDL, or Game Description Language (https://en.wikipedia.org/wiki/Game_Description_Language) GDL looks like it was developed at Stanford, very likely in conjunction with some AI coursework. I’ve dug around some of the GDL related sites and there are broken links galore, but there’s lots of information about it online. Some of the earlier Ludii papers reference GDL, so I’m fairly certain it came first.

There is ALSO a javascript project called Dagaz (https://github.com/GlukKazan/Dagaz) which shows quite a bit of promise, and has been used to port all of the games at MindSports (https://mindsports.nl/) from java to javascript. The author of Dagaz write a very nice article on some of this stuff (which someone else translated to English), which you can read here: https://habr.com/en/post/481868/

One more footnote is that there is another comparatively young project aiming to do some of this same kind of stuff in python called Zero Play (https://donkirkby.github.io/zero-play/).

Conclusion

So it seems to me that there are a few reasons someone might be interested in describing games (in a language tailor-made for that purpose):

  1. To improve and teach generalist AI to play multiple games.
  2. To generate new games programatically.
  3. To use a common codebase to facilitate the playing of games.

I am interested in all of the above. Although the implementation details of AI optimization and improvement are not in the circle of my particular venn diagram, access to generalized AI is of interest to me. (I thought about splitting #1 into multiple bullet points.) It’s worth noting that the last project mentioned above (Zero Play) is named after AlphaZero, (https://en.wikipedia.org/wiki/AlphaZero) a general game playing AI that was created by the same team that made AlphaGo. (AlphaGo being the Go-playing AI that famously beat one of the best human Go players in a series of very public games in 2016.)

The second bullet point is definitely one of the goals of the Ludii project, and one that Cameron Browne has extensive experience in. Games which have been created by computers are listed in a “family” on Board Game Geek (https://boardgamegeek.com/boardgamefamily/22566/misc-computer-generated-games/linkeditems/boardgamefamily), (containing at this time only three entries, two of which have Browne listed as designer). Probably the most well-known AI-created game is Yavalath (http://cambolbro.com/games/yavalath/), which Browne created using an earlier program (called LUDI) while he was working on his Ph.D. in 2007. While the earlier work by Barney Pell definitely indicated this was an objective, I didn’t find any evidence that it succeeded.

Finally, it is the facilitation of a general platform for game playing (& playtesting!) that I think a description language will be most valuable to me, personally. This is the primary reason I am interested in Ludii. Ludii’s platform (java application, but also online multiplayer) seems very stable, and has an increasingly tantilizing list of features. There is a category of simple games in particular (with simple rules) that seem to be a very nice fit for the platform. On their forums, the Ludii team have said that web-playability is on their roadmap, and that will lower the barrier to entry even farther.

I am going to try and implement some games in Ludii, and evaluate whether it’s a good platform for playtesting new games. It already includes features for analyzing games like 1st player advantage, and branching factor. These are metrics for their games that every game designer will probably find interesting.

Update:

After writing this post (and promoting it on BGG), Cameron Browne actually pointed me to some additional resources relevant to this discussion, (which led me to even more resources) and thought I’d drop some additional bullet points in here.

  • Brown pointed me to an article by Jacques Pitrat from 1968 called “Realization of a General Game Playing Program”. In his words: “… doesn’t specify a GDL as such, but shows that the idea of GGP has been around for more than half a century!”(https://www.semanticscholar.org/paper/Realization-of-a-gener…) Alas, I haven’t yet found a way to access the paper.
  • Jon Orwant wrote his Ph.D dissertation in 2000 about what he calls the EGGG (Extensible Graphical Game Generator): https://dspace.mit.edu/handle/1721.1/9164
  • Stephen Travener’s program Ai Ai uses a description file type called MGL, for Modular Game Language (http://mrraow.com/index.php/aiai-home/mgl/). It’s worth noting that Stephen Travener is a person quite relevant to this discussion, as he has worked on both Zillions of Games and Ludii, as well as his impressive Ai Ai software, which is also capable of playing and analyzing hundreds of games.
  • Browne pointed out that there are description languages for card games (I haven’t done any research into this yet.) and Video Games. Specifically, he pointed me to General Video Game Description Language (GVGDL), which I haven’t been able to find in a quick search, although there are plenty of hits for VGDL, and I haven’t really looked into that yet either.
  • Finally (again), the Ludii project website has a history page that I hadn’t read until after posting this. It outlines the history of a few other projects that led to Ludii’s creation, including Browne’s previous project Ludi, which I at least mentioned earlier. Well worth a read if you’re interested in more on this topic. (https://ludii.games/history.php)