Home

Multigame A Very High Level Language for Describing Board Games

Multigame - A Very High Level Language for Describing Board Games, John W. Romein, Henri E. Bal, Dick Grune. First Annual ASCI Conference, 1995.

Languages with implicit parallelism are easier to program in than those with explicit parallelism, but finding and efficiently exploiting parallelism in general-purpose programming languages by parallelizing compilers is hard. A compiler for a Very High Level Language, designed for a specific application domain, has more knowledge about its application domain and may use this knowledge to generate efficient parallel code without requiring the programmer to deal with explicit parallelism. To investigate this idea, we designed Multigame, a Very High Level Language for describing board games. A Multigame program is a formal description of the rules of a game, from which the Multigame compiler automatically generates a parallel game playing program.

An amusing DSL, and an interesting investigation of implicit parallelism.

Also see this later paper.

It would be nice to find a downloadable implementation, by the way.

By Ehud Lamm at 2005-10-19 14:22 | DSL | Fun | Parallel/Distributed | other blogs | 10312 reads

Comment viewing options

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

Thesis

A quick google search turns of John's Multigame thesis page from 2001 or so. A quick browse of the linked ftp server does not turn up a Multigame implementation, sadly.

By shapr at Wed, 2005-10-19 15:52 | login or register to post comments

Yes, I googled it before post

Yes, I googled it before posting, naturally ;-)

By Ehud Lamm at Wed, 2005-10-19 16:01 | login or register to post comments

Dungeons & Dragons

I've been brainstorming about writing a formalized definition of the Dungeons & Dragons rules. They are notoriously complicated and ad-hoc. I'm not imagining a AI program to play D&D, but more of a "rules lawyer/oracle" expert system that humans can query. Most D&D message boards are filled with endless debates interpreting vague language and contradictions in the D&D rulebooks. If there was an open-source or wiki D&D DSL reference, then gamers could query it with questions about the rules and self-appointed experts can debate the rules in a much formal language.

Any thoughts about an appropriate language or design for such a system? Or any similiar existing game DSL projects? I've briefly explored Prolog and RDF/OWL, but they are very heavyweight (and neither are quite my forte). :)

By runtime at Thu, 2005-10-20 00:47 | login or register to post comments

Consider yourself lucky

In a few years time, you might be trying to write a lawyer oracle for Amber Diceless Role-Playing Game :)

By David Teller at Thu, 2005-10-20 13:09 | login or register to post comments

AD&D and similar

I'm not convinced that it makes sense to create a "Rules Lawyer" for AD&D - especially seeing as it's usually recognised that a good Dungeon Master will bend or even outright ignore "rules" in order to produce a fun evening's play. They should be taken as guidelines, not absolutes. (Speaking as a DM since 1981).

On the other hand, a game like Magic The Gathering absolutely needs such an oracle. I know that friends and I have had to contact Tournament Organisers and the like in order to get definitive rulings on certain aspects of card play.

By David B. Wildgoose at Thu, 2005-10-20 07:52 | login or register to post comments

MtG oracle

Funny, I almost decided I want Magic: the Gathering formal rules as a topic of my Master thesis back when I needed a topic :)

I was pretty uneducated then, and naive, now I see that I could not succeed in it. The problem is, each newly printed card can introduce its own rules (possibly conflicting with others), and while the general rules try to resolve such conflicts, I don't see how any sane logic can apply to MtG. Would be glad to be proven wrong...

By Andris Birkmanis at Thu, 2005-10-20 11:23 | login or register to post comments

There is magic online (almost totally OT)

Magic online deals with this problem. There is a clear interpretation of every possible situation. This wasn't always the case, magic came into being with a much more informal set of rules which definitely admited ambiguity, but these have since been cleared up. (google and compare the "magic" comprehensive rules with the "vs system" comprehensive rules for a vivid example of the benefits of starting out with a formal definition of a game).

I'm not sure how new cards are implemented in magic online, but I assume they have a card definition language which allows them to do so without rewriting the game engine. In fact the problem with formally defining magic is not that new cards add new rules. That is solved, and all new cards behave unambiguously within the rules. The problem is that with each new set of cards, the designers add new rules outside of individual cards.

By robbie at Thu, 2005-10-20 17:48 | login or register to post comments

Of course they have a card de

Of course they have a card definition language, but many cards do stuff no card has done before so the card definition language only get you so far. So you sometimes have to rewrite the game engine, even without a rule change. And yes this has been a big problem with magic online.

By Felicia Li Svilling at Thu, 2005-10-20 22:46 | login or register to post comments

clear interpretation of every possible situation?

When you say WotC's Magic Online has a "clear interpretation of every possible situation", do you mean they have a huge formalized spreadsheet or that they have message boards to answer questions?

By runtime at Fri, 2005-10-21 00:34 | login or register to post comments

Clear interpretation

When you say WotC's Magic Online has a "clear interpretation of every possible situation", do you mean they have a huge formalized spreadsheet or that they have message boards to answer questions?

MO is a computer game with no human judging. However their rule engine chooses to respond to a given situation is the aforementioned "clear interpretation". :)

By the way, it seems to me that all rules I can remember from M:TG are "local" and should require no forward or backward chaining to resolve. This should at least make it easier to disambiguate the rules. (Of course, M:TG is tricky if only due to the sheer amount of released cards.)

With a rule system that has inference rules such that chaining would be required in judging, it would be a lot easier for disambiguities to sneak in through the backdoor.

By Per Vognsen at Fri, 2005-10-21 13:17 | login or register to post comments

Magic: the Gathering formal rules?

What was your planned approach to formalize the rules? What subject was your Master thesis in? Sounds like a unique thesis subject! :)

By runtime at Fri, 2005-10-21 00:32 | login or register to post comments

Not very relevant to LtU

Unfortunately those papers contain very little about the actual language. They just give some small bits of example code. And the thesis is not much better. I guess these guys are more into parallel computations that designing languages.

It's a shame though. I would've liked to read more about these kinds of languages. Their ideas are good.

By Josef Svenningsson at Thu, 2005-10-20 22:41 | login or register to post comments