Writing a game with GDL: Sim

I described the Game Description Language in an earlier post, but didn't show an example of a complete game description in practice. Today, I'll write a new game and record the process I use to make sure it's correct.

The game I'll write today is Sim, a simple graph coloring game I found on Wikipedia.
(Its list of abstract strategy games is an excellent source of new games for GGP.)

The first step is to figure out the exact rules of the game as you'd like to write it: figure out if any house rules should be applied, and how to resolve any ambiguities with scoring and the end of the game. (For example, certain games end when both players agree that no more useful moves can be made; this isn't suitable for a GDL game that is required to be finite. Such a game would probably need a step counter to end the game after a set number of turns in its GDL incarnation.)

Fortunately, the rules of Sim are straightforward, and it automatically ends after a certain number of turns, with a guaranteed winner. Here are the game rules, as explained in the Wikipedia entry:

The game of Sim is played by two players on a board consisting of six dots ('vertices'). Each dot is connected to every other dot by a line.

Two players take turns coloring any uncolored lines. One player colors in one color, and the other colors in another color, with each player trying to avoid the creation of a triangle made solely of their color; the player who completes such a triangle loses immediately .

Ramsey theory shows that no game of Sim can end in a tie.

With a clear set of rules, we have to go through a certain number of steps to turn it into a working .kif file.

1. Write a header

The first step I take when creating a .kif file is to write a header explaining what the game is, where to find the game rules, and who the author is. Anything after a semicolon is ignored in a .kif file, so we can include whatever human-readable text we want.

; Sim
; by Alex
; Rules of Sim: http://en.wikipedia.org/wiki/Sim_(pencil_game)

2. Add the roles

The next step is to figure out the roles for the players participating in the game. These are generally at the beginning of the game description. The Sim rules don't specify the colors, so I'll choose a couple arbitrarily.

(role red)
(role blue)

3. Figure out how game state will be expressed

Now it's time to get into the heart of the game. This game state has to include every piece of information that can distinguish between one state of the game and another, but it should also be as minimal as possible in most cases.

(Aside: As an example of why minimalism is good, the currently widespread chess.kif file expresses check as part of the game state, even though it can be computed from the rest of the game state. This means it gets computed on the previous turn while looking ahead to the state on the next turn. This approach left room for a bug in the game: if a player achieves checkmate due to a pawn promotion, the game fails to notice the check and treats the result as a stalemate.)

(Extra aside: When can minimalism be bad? As it turns out, counting and summation are difficult to get right in GDL, and sometimes it may be easier to maintain a running count throughout the game than to calculate the sum all at once, even if all the information is there.)

In the case of Sim, there are only two things we need to keep track of: which player's turn it is and what lines have been colored. Even so, there is a choice to make: Do we explicitly or implicitly keep track of which lines are uncolored?

Explicitly keeping track would mean that we start with true sentences like (line blank 1 3), which remain true until replaced by a sentence representing a color like (line red 1 3). The alternative would be to start with no line state and just add the colors as we go. This makes it a little harder to compute which moves are available, but also results in some tricky rules to determine whether a blank line should stay blank. I find the latter approach to be simpler overall, so let's stick with that.

4. Write the initial state

This gives us enough information to at least figure out the initial state of the game. Choosing to not include sentences for uncolored lines makes this easy. We'll let red be the first player.

(init (control red))

5. Figure out what moves players can make

Our players are going to be coloring lines on each of their turns. A simple way to identify a line is by its two endpoints (with the points numbered 1 through 6). We'll know what color to use based on which player's turn it is, so moves can look like (color 2 5).

However, there's something that could go wrong with the scheme I just suggested. As it stands, a player could make either the move (color 2 5) or (color 5 2). It would be much better to have a unique identifier for any given line (and lead to less confusion down the road). We'll add the requirement that the first number be less than the second number when referring to a line.

There's one more thing: remember, in GDL, every player must have an available move on every turn. That means the non-active player needs to have a move available to make, even if it does nothing. There is a standard name used for this type of move: noop, short for "no operation", a term borrowed from assembly programming.

6. Write the move legality rules

Now that we have some notion of the game state and the possible moves, we can start writing the rules that express how they interact with each other. The first piece to figure out: Given a state of the game, which moves are legal for each player?

Here we have to deal with the problem mentioned before of determining whether a line has already been colored. Your first instinct might be to write a rule that looks like this:

(<= (legal ?player (color ?i ?j))

    (true (control ?player)) ; It must be the player's turn

    (lt ?i ?j) ; i is less than j
    (not (true (line ?anyColor ?i ?j)))) ; The line isn't already colored

There is a problem with this approach: it isn't a valid GDL rule. The StaticValidator from the GGP-Base project will tell us why:

GDL validation error: Unsafe rule [...]: Variable ?anyColor is not defined in a positive relation in the rule's body

We need to define ?anyColor in a non-negated sentence. Now, consider what would happen if we naively added a source for the color as follows:

(<= (legal ?player (color ?i ?j))

    (true (control ?player)) ; It must be the player's turn

    (lt ?i ?j) ; i is less than j
    (role ?anyColor)
    (not (true (line ?anyColor ?i ?j)))) ; The line isn't already colored

The problem here is that the rule will apply for any value of the ?anyColor variable. This means that the active player can color a line unless every player has colored it, certainly not the intent here.

The way to solve this problem (which comes up frequently) is to break the notion of "this line has some color" into its own relation, so that we can reference its negation:

(<= (legal ?player (color ?i ?j))
    (true (control ?player))
    (lt ?i ?j)
    (not (isColored ?i ?j)))
(<= (isColored ?i ?j)
    (true (line ?anyColor ?i ?j)))

Note here that the less-than function provides our sources for the ?i and ?j variables. We would normally need some other relation to define which lines are valid, but in this case the less-than relation is enough.

Similarly, we need to remember to provide a source for the ?player variable in the noop rule:

(<= (legal ?player noop)
    (role ?player)
    (not (true (control ?player))))

7. Write the next-state rules

Now we need to say what the players' moves actually do. Rules defining next sentences will tell us how one state leads to the next. First, let's get the turn-taking rules out of the way:

(<= (next (control red))
    (true (control blue)))
(<= (next (control blue))
    (true (control red)))

We can define the next turn's state in terms of the current one using true sentences. We can also define it in terms of players' moves using does sentences:

(<= (next (line ?player ?i ?j))
    (does ?player (color ?i ?j)))

One last thing: Keep in mind that we need to explicitly say that colored lines stay colored. The only way to keep parts of the game state persistent is to make them so with explicit rules.

(<= (next (line ?player ?i ?j))
    (true (line ?player ?i ?j)))

8. Write the terminal and goal rules

The rules saying when the game ends and what the score is for each player are often closely connected, so I deal with them in a single logical step.

In this case, much like tic-tac-toe, we have a single possible feature of the game state that leads to the end of the game and a player's victory. (Unlike tic-tac-toe, we don't have to deal with the possibility of a closed-board draw at the end of the game; so much the better.) That's a good sign that it should have its own relation:

(<= (triangle ?player)
    (true (line ?player ?a ?b))
    (true (line ?player ?b ?c))
    (true (line ?player ?a ?c)))

Note the advantage that we gain here from keeping our line endpoints in a consistent ordering. Also note that we don't bother to include the location of the triangle in the result: what matters is who made the triangle, not where it is. This makes the remaining rules for ending the game easy:

(<= terminal
    (triangle ?player))

(<= (goal ?player 0)
    (triangle ?player))
(<= (goal ?player 100)
    (triangle ?opponent)
    (role ?player)
    (distinct ?player ?opponent))

9. Write any missing constants

We still haven't defined the less-than relation. Someday I'll write a post on doing arithmetic in GDL, but for now we use some arithmetic functions (successor and less-than) grabbed from other games.

(succ 1 2)
(succ 2 3)
(succ 3 4)
(succ 4 5)
(succ 5 6)
(<= (lt ?a ?b)
    (succ ?a ?b))
(<= (lt ?a ?c)
    (succ ?a ?b)
    (lt ?b ?c))

10. (Optional) Write base and input rules

Writing base and input rules can give players more information about the possible states of the game. This tends to be more relevant when the variety of sentences in the game state and legal moves is very large, so they are less useful here; but we can add them anyway for extra style points.

Notice that the base and input sentences are constants, so they must be defined in terms of constants.

(<= (base (control ?player))
    (role ?player))
(<= (base (line ?player ?i ?j))
    (role ?player)
    (lt ?i ?j))
(<= (input ?player noop)
    (role ?player))
(<= (input ?player (color ?i ?j))
    (role ?player)
    (lt ?i ?j))

11. Test the game with validation tools

Now that we have finished writing the game, we must test it if we want to be confident that it is correct. I mentioned the StaticValidator tool before; I wrote it a few years ago as a way of catching the fiddly little syntax errors that tend to work their way into games. (The original paper describing GDL had a syntax error in its sample implementation of tic-tac-toe.) Theorem-prover-based rules engines will tend to handle those cases "correctly", but anything dealing with GDL in a more complicated way could choke on the errors.

Our version of Sim passes with flying colors, but we're not done yet:

12. Think through semantic error cases

Although static validation can catch syntax errors, there are a variety of other errors that can't be caught through static analysis:

1. Is the game always guaranteed to terminate? (If the game state can get stuck in a loop, the answer is "no".)
2. Does every player have at least one move in every non-terminal state?
3. In every terminal state, does each player have one and only one goal value?

The first step to catching these errors is to carefully think through each of them. Hopefully you made sure that the answer is "yes" in every case, but it's always possible that your interpretation of the rules changed over the course of writing the game and opened up some room for error.

To eliminate the possibility of further errors, we need to take one more step:

13. Test the game with real gamers

I don't consider my testing of a game to be complete until I've had my gamer play it several times. This lets me look through some sample games and verify that the game behaves the way I expected. If your gamer provides error messages when reaching a violation of one of the semantic errors above, it can also search a wide swath of the game tree for errors.

There are some other valuable things to learn about a game by having a good gamer try it out. For example, it's difficult to know whether a game heavily advantages one player or the other without having a reasonably strong computer player play it against itself. (Sim is supposed to favor the second player, and my testing confirms this.) It's also a test of whether the game rules can be interpreted efficiently enough for intelligent-looking computer play.

(Remember, if you want to test a corner case -- like checkmating your opponent through pawn promotion -- sometimes the best gamer is... you! The PlayerPanel in GGP-Base includes a Human gamer option.)

I wouldn't send new software to a customer without testing it out myself, and neither would I publish a game without testing it. (Indeed, I found a dumb mistake in the rules I had written that I didn't find with simpler validation checks.)

Here is the end result, all together:

; Sim
; by Alex
; Rules of Sim: http://en.wikipedia.org/wiki/Sim_(pencil_game)

(role red)
(role blue)

(init (control red))

(<= (legal ?player (color ?i ?j))
    (true (control ?player))
    (lt ?i ?j)
    (not (isColored ?i ?j)))

(<= (isColored ?i ?j)
    (true (line ?anyColor ?i ?j)))
   
(<= (legal ?player noop)
    (role ?player)
    (not (true (control ?player))))
   
(<= (next (control red))
    (true (control blue)))
(<= (next (control blue))
    (true (control red)))

(<= (next (line ?player ?i ?j))
    (does ?player (color ?i ?j)))

(<= (next (line ?player ?i ?j))
    (true (line ?player ?i ?j)))

(<= (triangle ?player)
    (true (line ?player ?a ?b))
    (true (line ?player ?b ?c))
    (true (line ?player ?a ?c)))

(<= terminal
    (triangle ?player))

(<= (goal ?player 0)
    (triangle ?player))
(<= (goal ?player 100)
    (triangle ?opponent)
    (role ?player)
    (distinct ?player ?opponent))

(succ 1 2)
(succ 2 3)
(succ 3 4)
(succ 4 5)
(succ 5 6)
(<= (lt ?a ?b)
    (succ ?a ?b))
(<= (lt ?a ?c)
    (succ ?a ?b)
    (lt ?b ?c))

(<= (base (control ?player))
    (role ?player))
(<= (base (line ?player ?i ?j))
    (role ?player)
    (lt ?i ?j))
(<= (input ?player noop)
    (role ?player))
(<= (input ?player (color ?i ?j))
    (role ?player)
    (lt ?i ?j))