Lambda the Ultimate

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

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

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.

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.

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 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.

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

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.

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

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?

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.

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.

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 domain specific.

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.

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 :)

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.

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!

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?

You can find Wouter's/Kartoffel's gaming projects on his website strlen.com. He's got a ton of gaming related stuff he worked on, for example, the scripting language for the Far Cry game.

I agree my post wasn't very clear. My points being: A) There are far more game DSLs (than the Wikipedia page lists or the original poster seems aware of), it seems to be in the range of at least several thousand. B) Extrapolating from Sweeney's experience, it looks to me that if you implement a game DSL you run into the risk that it simply 'doesn't cut it' for several reasons and you're better of with a library.

As an addendum, I don't think Wouter is into type theory that much and I don't care much for his academic work. In a nice manner, that is. All the relevant research and development is in industry, I care more about what he did there than the rest. And he did a lot, it seems.

Games is where a lot of money is made so that's a sweet spot for industrial research and development and tons of effort are poured into that, including DSLs.

The original author seems blissfully unaware of how the world works^tm.

Oh sorry for my tone. I thought it was a student. But David, seriously.

Games are a hundred billion dollar industry, and they pour a lot of that money into R&D. So, I always look at the technology the games I play use and I have played games which implement DSLs for nearly everything. Special purpose scripting languages (The Unreal Engine with the scripting language by Sweeney comes to mind), small logic games which use esoteric languages, Game Maker style things as by Mark Overmars, and then of course languages which just use general purpose scripting tools (Lisp was used in a game called Descent I think, Lua and Python are used in the Civilization series, I think I even played a game which used a Prolog back-end.)

No research? Never buy into that since industry isn't a meritocrazy based on pushing paper around nobody reads that there is no research. Again, it's a hundred billion dollar industry where experts, often with more than twenty years of experience, work and they are certain to implement DSLs for everything.

The only thing is that these experts don't publish, so they don't pop up in the meritocrazy LtU seems to be the herald of. But who cares what a 24-year-old, who yesterday learned what a catamorphism is, writes?

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.

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.

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 mcdirmid@outlook.com. I moved to YCR in September.

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

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)?

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.

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

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.

Sounds interesting, but you really have to decide whether you're producing a full programming language that happens to provide a game type system and library built in, or whether you can prune it down to something a novice or non-programmer could use to hack together a new game or modify an existing one. I prefer the latter.

I now have a working Monte Carlo Tree Search with pruning and win-lose-draw (which I found rather hard); it plays OK; but (a) I hate waiting while it's thinking and (b) I hate getting beaten. I'm going back to focus on single player games/puzzles. I think there is more user interest. Check out PuzzleScript.