Domain specific language for playing games

Writing computer games for people to play, even quite simple ones, is a surprisingly challenging task. Here I'm thinking of turn-based games like card and board games, puzzles, block-pushing and perhaps simple arcade games like Space Invaders. It would seem fairly obvious that large parts of the heavy lifting will be common from one to another and that differences in game play might well be encapsulated in a DSL.

Others have had the same thought. Here are links to some good reviews: https://chessprogramming.wikispaces.com/General+Game+Playing, https://en.wikipedia.org/wiki/Domain-specific_entertainment_language, https://en.wikipedia.org/wiki/General_game_playing. The GGP language GDL is a Datalog derivative, Zillions uses a Lisp dialect and Axiom is a kind of Forth. There are several others, including PuzzleScript, CGL and VGDL. GGP in particular is the focus of a lot of AI work, not so much the UI. Several of these projects appear dormant.

Considering the prevalence of games in the community and the number of people involved in writing them, this looks like surprisingly little effort in this direction. I was wondering if anyone is aware of or involved in any active work in this area, particularly on the language side, before I go and invent my own.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Take a look at...

the Ceptre language by Chris Martens.

It's a logic programming language based on linear logic for specifying game worlds and their dynamics. There's a paper describing it, and her Github (linked above) has a lot more examples, too.

Ceptre

Thanks -- exactly what I'm looking for. So many different language paradigms! Fertile ground, with few players it seems.

See also

http://lambda-the-ultimate.org/node/5216

Performance and Generic Game Competitions.

Performance is an issue, and programs to play games like chess and go/weichi tend to be written in low level languages like C/C++, as strong play without using a supercomputer is still a challenge. GGP and tends to be used for specialised generic game purposes, where the challenge is to develop a program that can play any game. Generic game competitions provide software with a game description file, where the particular game to be played by the software is unknown by the participants before the competition. The competition itself consists of entrants software playing games against all the other entrants software and the strongest software wins (by number of game wins or score).

Not all games need supercomputer performance

Chess is hard. Go is harder. But there are hundreds (thousands?) of games that a computer can play well on any modern device. GGP (and its DSL GDL) are well-suited to competitions and AI research, but I'm more interested in languages for expressing new interesting games, that the computer can play well enough, for a wider audience.

How about a nice game of chess?

Computers empowering humans to play games, makes sense to me. I admit, though, I'm not really clear that there's a recreational point in computers playing games. About forty years ago I wrote a program, and rewrote it in several languages as I learned them, to play Battleship against a human opponent. I was just learning to program, and found it an interesting exercise in modularity, and an interesting exploration of the differences between languages; but the most important and enduring thing I learned from that program was about the nature of competitive games. One day I sat down and played game after game, for hours, and learned that Battleship isn't about problem solving, it's about playing against a human opponent. Since I'd written the program, I knew just how it made its decisions, and I could choose my strategy and tactics to maximize my chances of winning; but so what? I might change the program and, depending on how it matched against my own cognitive strengths and weaknesses, it would win against me more or less of the time, statistically; but it would always be less fun than playing against a human being. In years since I've realized that with most games, even setting aside the social aspect of game playing, it's also most fun to play against someone with a reasonably comparable level of skill; which only makes it clearer, to me, why playing against a computer is futile: the computer's capabilities, and inabilities, are totally different from ours.

Go

Top rank Go players want to play against Google's machine to improve their play since it has beaten the top players. They generally have no interest playing against lesser software. As you say the software has to offer a challenge.

Incomplete information

Incomplete information games are even harder (poker for example). A good whist or bridge player, also hard.

Yes tic-tac-toe does not need this kind of performance, but it's not really an exciting game for humans to play either.

I would suggest that any game worth playing (as a human) requires as much performance for the computer player as you can get - except games that involve another skill like testing reflexes.

Edit: There probably is a class of games that are both interesting and don't require supercomputer performance. As games mostly consist of 'searching' the game tree, there are probably games where the search tree it tractable (has limited fan-out and depth) that would allow either an almost complete search in reasonable time, or a pre-computed game-tree to fit in memory. In order for the game to be interesting to Humans it probably requires the tree to be irregular, that is the positions cannot easily be classified into a small number of categories from which the best move could be memorised. I am not sure which games (if any) fall into this category. I think designing a new game specifically to be easy for a machine but hard for a human is an interesting topic.

There are hundreds of games like that

See my other comment below. Web search Zillions or GGP if you need a list.

Sure

I'm sure there are, although I don't really have any interest in playing them, apart from maybe backgammon, but you would have to include the score betting with the doubling dice as an incomplete information game, and that's the bit Zillions cannot do. It can't even do battleships :-)

The fact the machine can play them is clear, whether they are interesting games for human players is debatable. For example none of these games have 'grand masters' and player rankings, which more popular games do. I think really most of these are children's games which teach the principles of game playing before people move on to properly challenging games.

Most interest in GGP is from the computer games playing community as far as I can tell. However it could be a great educational tool for teaching AI and programmimg.

Possibly of interest

EGGG looks good

I agree, but it seems to be dead. If anyone knows Jon Orwant and could ask the question...?

Felix

My Felix system has user defined syntax, it generates C++, it has functional programming with parametric polymorphism, type classes, GADTs, procedural programming, and also has coroutines specifically designed for game like scenarios. Well actually, the design was originally for telco environment, but the design makes sense for an RPG with large numbers of NPC's/sprites as well. It also has a working partial binding to SDL (which was specifically created for games), and an out of date overly complex binding to OpenGL.

It's also (with some pain) embeddable in an external event loop which is essential on mobile devices running Android or iOS.

Felix is not really a DSL

Felix looks like an interesting language with many of the features needed for writing high performance games, but it isn't really a games DSL, is it?

DSL

No, its a general purpose language with high performance fibration and a facility to define any DSSL (Domain Specific Sub Language) you want.

Which means its 10x better than any special purpose games DSL. Because there's no such thing as a good DSL for all games.

Games are THE most varied and demanding kind of software. Any language which doesn't have features like parametric polymorphism, GC, low level operations, superior ability to bind to a large class of existing C libraries .. and fibration .. is automatically not suitable for "games". You need fold. And you need goto. :-)

Sure, you can do a DSL for a specific kind of game. Or a specific kind of financial calculation. Or a specific kind of mathematical operation. Or a specific kind of environment.

But the best kind of DSSL facility is one which allows you to save on boilerplate and represent algebras compactly, in other words, it won't have anything specific to games in it because there's no real need. For example, compact ways to handle motion and visual is pure mathematics.

So the point in Felix is, you can define one or more DSSLs. Which are domain specific *sub* languages, in other words they typically translate to native Felix and typically allow native Felix to be embedded in them.

Designing one or more good DSSL's is likely to be HARD. I have a few: there's one for regular definitions, one for a circuit model of fibration, one for context free parsing. So roughly if you wanted a DSSL for say Go or Chess you'd be asking about the algebra's used in path exploration and how they interact with pruning. If you were doing a MMP mil-strat game you'd probably be looking at ways to specify network load balancing algorithms.

It's not really about existing major games

The point of a DSL is to allow a certain class of problems to be expressed efficiently. For example, regex is a DSL, and while it doesn't suit all kinds of text matching, it does enough to be very useful.

The games most likely to suit a DSL are relatively small but still interesting to play. Examples that come to mind are Mancala, Morris games, Connect-4, Pentago, Gomoku (and their many variants), as well as variants of Chess, Draughts, Go, Tic-Tac-Toe and so on.

Given the right defining language a general purpose solver gives a human opponent a good challenge without the need to go to arcane lengths.

most likely?

Actually many common video games really DO have a DSL for programming NPC's and artefacts. The most commonly used one is actually Lua. Other games like Trains also use a DSL for programming behaviour.

Lua is general purpose, not

Lua is general purpose, not domain specific.

Not really a DSL but...

I rather think that big games will mostly have some kind of scripting language, and Lua seems a common choice. Although the language itself is GP, it's easy enough to extend the language and add bindings that make it pretty specific to the game itself. Not quite DSL, but...

But this is maybe 1% of what the game does. I guess I'm looking for a DSL that has a core role in the game as a whole.

One percent

I don't think you can say its "one percent" of what the game does. In fact its almost the whole of what the game does usually. The thing is there is a LOT of C/C++ code implementing graphics, sound, mouse interaction, network connectivity, database management, etc, all to create the scenario which is controlled by the DSL.

So in these games the Lua code really IS the game, the rest is just an "operating system" for the script to run in.

And this is why most video games are a load of crap. Because all the work is in pretty effects and none is done on the actual game play.

So for a serious Chess game, for example, the balance is the other way: not much code is required to render the pieces on the board or move them. All the work is in the DSL for the NPC (the opponent computer player). I wouldn't be using Lua for that :)

Aiming for 100 percent

What I meant is that Lua is used as a 1% scripting language in many large games, but I want a DSL that is a 100% description of a smaller game. Obviously the KLOC of C/C++ code is still down there somewhere, and the game genre will be restricted to what can be expressed by the DSL.

The genre of interest is turn-based, one or more players, perfect information, board and piece style games. I know of around 2000 games and variants that fit the genre. Lua and other GP languages are not well suited to that role.

And the choice of the implementing language is open. It's the design of the DSL I care about, not what is used to implement it.

Kartoffel and Sweeney

I've seen Kartoffel (Wouter) and Sweeney post here from time to time.

People have invested tons into programming languages for computer games and there are a myriad of scripting languages for that.

Gamemaker, by Mark Overmars, made it into a somewhat popular commercial product. As far as I know, that has a graphical interface with a scripting language underneath.

The problem doesn't seem to be that people didn't invest in this, the problem is that the Wikipedia page isn't very comprehensive or up to date.

And then there is Sweeney's conclusion, somewhere in the archives of this site, that a DSL for gaming is, in general, a 'Pretty Bad Idea' (tm).

(Wouter himself already wrote around 38 languages, a large portion of them for game logic. There's tons of investment in this.)

Pretty Bad Idea

This doesn't surprise me. My view is that you need a DSSL (Sub-language), which represents some library with a solid algebra behind it.

So LtU'ers will not be surprised Felix has well over 40 application operators. The DSSL for functional programming is heavily supported.

Consider this:

  regdef lower = charset "abcdefghijklmnopqrstuvwxyz";
  regdef upper = charset "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
  regdef digit = charset "0123456789";
  regdef alpha = upper | lower;
  regdef cid0 = alpha | "_";
  regdef cid1 = cid0 | digit;
  regdef cid = cid0 cid1 *;
  regdef space = " ";
  regdef white = space +;
  regdef integer = digit+;
  regdef sassign = 
    white? "var" white? 
    group (cid) white? "=" white? 
    (group (cid) | group (integer)) 
    white? ";" white?
  ;

  var rstr : string = sassign.Regdef::render;
  var ra = RE2 rstr;
  var result = Match (ra, " var a = b; ");

You can read that, right? You do not really want to write the combinators explicitly:

  
union regex =
  | Alts of list[regex]
  | Seqs of list[regex]
  | Rpt of regex * int * int
  | Charset of string
  | String of string
  | Group of regex
  | Perl of string
  ;

and you CERTAINLY don't want to write the regexp in Perl string regexp language, you'd never get it right, you'd never maintain it, and no one else would be able to read it. But, the render function above translates the combinators the parser generates from the regdef DSSL into a Goole RE2 regexp string (because they didn't provide a combinator interface).

So the DSSL represents an *algebra*, it hides a LOT of boilerplate machinery, and it presents a familiar interface: the standard regexp language, more or less.

Felix has a number of DSSLs, in fact the whole language is built out of DSSLs: only the grammar used to parse DSSL definitions is hard coded.

The reason I keep saying DSSLs is that the idea is that you have a simpler base system and build algebraic models with a combination of language features: types, functions, libraries, type classes, C bindings .. and grammar. You're representing something IN the language, not a separate language. So typically it is (a) embeddable and (b) has an anti-quoting syntax to escape out temporarily to the normal syntax.

Although Scheme does this exceedingly well, the base language is too primitive for most programmers (including me!). However .. if you look at the DSSL definitions:

  //$ Postfix star (*).
  //$ Kleene closure: zero or more repetitions.
  private sregexp[rpostfix_pri] := sregexp[rpostfix_pri] "*" =># 
    """`(ast_apply ,_sr ( ,(regdef "Rpt") (,_1,0,-1)))"""
  ;

you will not be surprised I used an embedded Scheme as the parse action code so the syntax generates Scheme which is executed to produce an S-expression representing the AST. As syntax macro language the grammar definition + Scheme combination is pretty awesome!

Anything more specific?

I found one post by Wouter, not relevant (type theory).

I found a couple of posts by Sweeney justifying Unreal dropping their scripting language and going back to C++.

None of this seems germane to the concept of a games DSL (obviously implemented in and supported by C++ etc).

Anything specific in mind?

Felix again

Nice to see you're committed to your language and that it can be used to implement DSLs. Any comments to make about my actual question, which is what a game-oriented DSL should look like?

Game oriented DSL

Well that depends on the game doesn't it?

I mean you might think of Go or Chess as a game, but I think of MilStrat or D&D as games.

FRP

I suspect FRP makes a good language for many games.

Multigame

John W. Romein, Henri E. Bal, Dick Grune:
An Application Domain Specific Language for Describing Board Garnes. PDPTA 1997: 305-314

"Multigame is an implicitly-parallel, domain-specific language for describing board games. The Multigame system automatically exploits parallelism (by searching game trees in parallel) , without any involvement from the programmer. The paper describes the language and its implementation on a Myrinet-based distributed system. It also gives performance results for Multigame applications."

It is a language for describing perfect-information deterministic games, which are then compiled into min-max search procedures. Might be of interest.

There is a copy cached on citeseer here.

Romein has done more

Thanks for the link. I found John Romein on chessprogramming.wikispaces with a number of related and more recent papers. Not much activity since 2000, unfortunately.

Kodu.

Kodu.

Sean, send me an email

I wanted to contact you about something a few months ago and then realized that you're no longer at Microsoft.

Sure, my public email is

Sure, my public email is mcdirmid@outlook.com. I moved to YCR in September.

Thanks

If it's public you could put it in your profile. Hope you're enjoying things at YCR!