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!

I'm working on something like this

After writing a chess engine I got the idea to make a product that supports lots of chess like games.

I took a look at zillions. Its language is somewhat based on a model where you move a cursor around the board and query the cursor to build up moves.

I tried mocking up something like that in lua, compiled with luajit. The design allows for games with boards of any size, any number of dimensions and any number of players (I came up with an alpha-beta like pruning algorithm for many players - the literature is missing an algorithm like that).

It worked but the performance is very disappointing. It's about 400 times slower than my special purpose engine in C++.

I'm trying over again, this time with a custom DSL, parsing with an antlr grammar, transcompiling to C and using an in-memory C compiler. It's not at a stage where I can test it yet.

I'd be interested in designing a larger library that could support more kinds of games and puzzles.

Isn't a chess engine a bit heavy?

Yes, that's Zillions. I've written a similar engine, but on Tic-Tac-Toe it can only evaluate about 10K positions per second, which is just too slow. [I don't believe in mini-max or alpha-beta pruning, but that's another story.]

But I really don't see the point in writing Yet Another Chess Program. The point of a DSL is to be able to quickly define new games or variants, test them computer to computer, and then play against them to see if they're fun!

I'm definitely interested in your custom DSL. We could debate the path of C generation vs my preferred custom VM but that's implementation. What does the DSL look like (assuming it's not Zillions)?

Game library for inexperienced programmers

The main engine will be for chess like games. There are a lot of chess like games and chess variants to cover.

I define that as games that have similar enough properties that chess algorithms work. That's mostly that they're games where material balance is a reasonably good estimate of who is ahead and where the branching factor is moderate and where you can make alpha beta efficient by ordering move by good captures. And games where there is usually a safe move to make allow for the null move optimization - that's somewhat useful.

Alternatives are games that are more nim-like. Othello is a game where you mostly win by making the other player run out of safe moves. Ultimately that makes for a terrible game. You can play a perfect game of othello and still lose at the end. Since the branching factor in Othello drops quickly at the end, the result is that at a certain point a computer will be able to see all the way to the end of play, and that will happen sooner for a computer than for a person - really it's a horrible game to play against a computer.

I have written othello engines before... I don't know if I'll include heuristics for games like that.

I may include a modified monty carlo tree search for games that have high branching factor parts. It's not a method that's good for tactics in general, there are problems. A version is used for Go, but I think that needs to be guided by Go specific heuristics. I won't include a Go engine, I don't have the expertise for that.

But I might use something like that to handle both openings (where play should be more strategic than tactical) and to handle games where you drop pieces one the board and thus have huge branching factors.

....

You asked if the language will be like zillions.

Well my goal is to make a system that won't totally overload someone who isn't a programmer.

I think zillions idea of building up moves with a cursor and commands to it is probably the only way of doing that that is simplified enough for naive programmers.

I would have liked to make something more abstract, but I think you have to be too much of a programmer to juggle lots of variables and types, and this design obviates the need for a lot of that.

The language itself is both easier and perhaps more to learn. It's somewhat Modula like or Pascal like.

One idea to make making games easier is to allow a graphical interface for specifying move types - if you can describe much of your game through a graphical interface and question answering wizard, then it can write scripts for you.

At this point none of the library for the new version is written. I've been somewhat overwhelmed by writing my first compiler.

I'll be grateful for ideas for the library.

The more I stick into the library, the more kinds of puzzles and games I can support.

One idea I have that's unlike zillions is allowing the user to give lots of hints or even traditional evaluation routines to the ai. It could be a kind of game to make your ai smarter.

It could be a meta-competition, coming up with ais and trying them against people or against each other. I could include routines for running tournaments or even tuning sessions.

Language for beginners

Edit: How do I get this to preserve tabs in code blocks?

This is a language for beginners.

It's a simple statically typed language.

Types are:
integers
real numbers
strings (which are really implemented as interned strings or atoms, because that was convenient for me)
position
direction
enumerated types, including some predefined ones like "player" and "piece_name" also piece(ie slot on the board holding a piece and a player) will be treated like an enumerated type even if the number of slots is variable. Also there are types like enumerated types that are not "enumerated" instead they're the names are learned from context.
sets
maps (something like an array but mapping from a finite type to any value)
arrays
record types - only used to initialize properties that the engine needs.

You can do arithmetic on some non-number types. A direction can be added or subtracted from a position to make a new position. A direction can be added or subtracted from a direction to make a new direction.

an enumerated type definition looks like

player IS { white, black }

a learned enumerator looks like:

zone IS LEARNED

A use of some of these types could be regions on the board where pawn promote and of the region where pawns can make an extra move.

Because those regions are different depending on the player that would be map from player to a list of sets of positions.

In a header of types the engine needs that's written as:

zone IS LEARNED
ENGINE CONSTANT region OF MAP player => MAP zone => SET OF position

Note that case is not significant for keywords. I make them upper case in these examples to set them apart.

A definition of region could look like:

region = {
white = {
promotion_zone=
{
a8, b8, c8, d8, e8, f8, g8, h8,
},
third_rank=
{
a3, b3, c3, d3, e3, f3, g3, h3,
},
},
black = {
promotion_zone=
{
a1, b1, c1, d1, e1, f1, g1, h1,
},
third_rank=
{
a6, b6, c6, d6, e6, f6, g6, h6,
},
},
}

Here promotion_zone and third_rank are the enumerated values that zone takes, and it's learned from use in context instead of being explicitly set out before hand.

A few slightly unusual innovations:
The boolean type is called "WHETHER x." and where "x" is a comment and the values are "YES" and "NO" not "true" and "false".

So a routine tests whether a piece if threatened might look like this:
FUNCTION slide_threaten(dir OF direction) RETURNING whether threatened.
shift(dir)
IF is_target() THEN RETURN YES ENDIF
WHILE empty() DO
shift(dir)
IF is_target() THEN RETURN YES ENDIF
ENDWHILE
RETURN NO
ENDFUNCTION

looking this over

That "LEARNED" idea is just one more thing you have to explain to the user.

Maybe I'll get rid of it. The fewer ideas I have to explain to the user the better.