Monday 27 June 2005
'Talisman' and Programming Language Semantics
On Friday night I got together with some of my old old buddies, guys I first met in high school, plus my brother, for a game of Talisman. Not a game of great intellectual challenge, but tons of fun. Having the gang back together for the first time in about 11 years made it so much better.
It's interesting to think about how one would implement Talisman in software. The issue is that Talisman revolves around cards --- "adventure cards", "spells", and "characters" --- many of which modify game rules in some way. (Many other games also have this form, of course.) For example, a card might say "adds 2 to your strength in combat with dragons", or "magic objects have no effect against the owner of this object", or "you may roll twice when moving and choose the larger value". Of course if you know the complete set of cards ahead of time, you can have every step of the game check for all cards which may be in effect. But this is not really a faithful encoding of the game. A faithful encoding would give the source code the same modular structure that the game has. In particular you would have a small core corresponding to the core rules, and one module for each card which fully describes the effects of that card.
The natural thing to do is then to identify a set of "extension points" where cards may modify game behaviour, each with a defined interface, and have each card "plug in" to one or more extension points. This works well for many kinds of applications, but unfortunately it doesn't work well here because again it is not very faithful to the structure of the original game. The real game does not define such extension points; instead almost everything is implicitly extensible. We take it for granted that the English text of the rules can be later modified by the text on cards and we don't have to say anything about the possibility beforehand.
Can we have a programming language that supports this sort of implicit extensibility? I think it would be very useful, not just for these sorts of games but also in other situations. One question is whether the problem is "AI-complete" --- that is, whether you need human-level language processing and general-purpose intelligence to resolve ambiguities and contradictions, the sort of intelligence that would probably let you pass a Turing test. I don't think you do, but the only way to be sure is to demonstrate a non-AI-complete solution. I think you could design a language and toolchain so that at least at program composition time, when all the extensions are known, all ambiguities and contradictions are automatically and precisely identified.
Another question is whether a language with implicit extensibility already exists. As far as I know the only languages that come close are those that expose the program's code to the program reflectively, allowing modification. I think some LISP interpreters allow that, and some languages with "eval" can be thought of as supporting it. But self-code-surgery seems like an incredibly crude and not very expressive way to address this problem.
I first considered this problem over ten years ago, it was even in my .project file back then. Now I wish I'd done my thesis on it. It's a bit off the wall but it would have been more fun and maybe had a lot more impact than the fairly pedestrian work I ended up doing.
It's interesting to think about how one would implement Talisman in software. The issue is that Talisman revolves around cards --- "adventure cards", "spells", and "characters" --- many of which modify game rules in some way. (Many other games also have this form, of course.) For example, a card might say "adds 2 to your strength in combat with dragons", or "magic objects have no effect against the owner of this object", or "you may roll twice when moving and choose the larger value". Of course if you know the complete set of cards ahead of time, you can have every step of the game check for all cards which may be in effect. But this is not really a faithful encoding of the game. A faithful encoding would give the source code the same modular structure that the game has. In particular you would have a small core corresponding to the core rules, and one module for each card which fully describes the effects of that card.
The natural thing to do is then to identify a set of "extension points" where cards may modify game behaviour, each with a defined interface, and have each card "plug in" to one or more extension points. This works well for many kinds of applications, but unfortunately it doesn't work well here because again it is not very faithful to the structure of the original game. The real game does not define such extension points; instead almost everything is implicitly extensible. We take it for granted that the English text of the rules can be later modified by the text on cards and we don't have to say anything about the possibility beforehand.
Can we have a programming language that supports this sort of implicit extensibility? I think it would be very useful, not just for these sorts of games but also in other situations. One question is whether the problem is "AI-complete" --- that is, whether you need human-level language processing and general-purpose intelligence to resolve ambiguities and contradictions, the sort of intelligence that would probably let you pass a Turing test. I don't think you do, but the only way to be sure is to demonstrate a non-AI-complete solution. I think you could design a language and toolchain so that at least at program composition time, when all the extensions are known, all ambiguities and contradictions are automatically and precisely identified.
Another question is whether a language with implicit extensibility already exists. As far as I know the only languages that come close are those that expose the program's code to the program reflectively, allowing modification. I think some LISP interpreters allow that, and some languages with "eval" can be thought of as supporting it. But self-code-surgery seems like an incredibly crude and not very expressive way to address this problem.
I first considered this problem over ten years ago, it was even in my .project file back then. Now I wish I'd done my thesis on it. It's a bit off the wall but it would have been more fun and maybe had a lot more impact than the fairly pedestrian work I ended up doing.
Comments
Now, how should the rules be represented?
The key thing rules do is change the state of the game. So they should be expressed in a transformation language, that has rules of precedence (precedence to the most specific rules).
XSLT seems a good candidate, with the game state represented in XML.
The cards themselves, that need to modify the rules, do not need to be expressed in a declarative fashion. They should modify the rules' XSLT, this can be done with javascript and the DOM or with another XSLT namespace.
For example, the card "adds 2 to your strength in combat with dragons" would append a new <template> tag to a player specific XSLT (that <include>s the global one, like overlays). It would match on the game state (if the current state tag is <combat>); it would match the opponenent tag for a dragon, match the strength tag below the player tag, use XPATH to increment it.
Other cards could apply to a global rules XSLT, or to a player- and turn-specific rules XSLT.
The card that changes the way dice are rolled is less obvious; it should match on the moving state, and write two tags for rolling dice; these should be transformed into values outside of XSLT, and another transformation will take the greater of both.
Writing a game like this sounds like fun!
Syntactically it's similar to an if-else, but I suppose if the compiler let you spread the definition of a function out over multiple files then you could get what you want.
Here's a simplistic example (pretend the function bodies are properly indented for readability):
-module(math).
-export([perimeter/1]).
perimeter({square, Side}) ->
4 * Side;
perimeter({circle, Radius}) ->
3.141592 * Radius * 2;
perimeter({triangle, A, B, C}) ->
A + B + C;
perimeter(Other) ->
{invalid_object, Other}.
You can see how it uses the argument (which has to be a list or you get the final form) as a typed object, and does something different based on the value of the first element in that list.
Plus the built in network-transparent IPC would be good for doing the multiplayer. :)
Still, it's not quite what you want. I'd be hard pressed to design a system that didn't explicitly define phases (in this case by defining a function for each of them, etc) which you probably don't want to do since a card could theoretically alter their order, introduce new ones, skip some, etc.
What you probably want is lisp, which conflates data and code so throughly (a good thing!) that the cards are each represented by some code that modifies not just the state of the game, but that can add code to the list of things to execute next (thus letting you add phases, skip them, etc) or even edit them, as would be the case for your +2 str vs dragons card.
Anyway, that sort of data driven programming can usually be done in any language, just with varying amounts of pain.
As for XSLT, all I can say is "bleh."
I'll quit rambling now :)