Update 1 - What is a game?

(Note: I apoligize in advance that the code samples in this post automatically line wrap. I’m a mess when it come to front-end web and haven’t figured out how to stop it yet. I’d love for the code blocks to have shiny little scroll bars instead.)

(The github project containing all the code from this post can be found here)

In my last post, I outlined a project I called Delectibles (A contraction of ‘Digital Collectibles’) that would allow users to play turn-based games with digital collections by allowing the users to verify each other’s collections and use Mental Poker to prevent cheating (the discovery or manipulation of random or hidden information). But this was clearly several independant codebases. Permitting a user to bring a game piece into the game by verifying that they actually own said piece is a completely separate problem than preventing cheating by manipulating pieces that are already in the game. And Mental Poker can authenticate actions taken by users, but it says nothing at all about whether those actions are consistent within the rules of the game that is being played. So what was proposed as one monolithic library is actually three: one to prove ownership of game pieces, one to prevent cheating, and a third to actually lay out the rules of the game.

This third piece, which I call Multigame, is this focus of this update.

Layer 1: Delectibles
Layer 2: Mental Poker
Layer 3: Multigame

Our goal is to create a platform that can be used to implement generic turn-based games. Different games would be represented by different data files that would be read by the platform. By what should the format of these files be? Should they be written in a platform-specific scripting language, or should they be allowed to execute arbitrary code? If we use the scripting language approach, we can control what the game files can do and what resources they can access, reducing the trust in the game developers. And if we make the language not Turing complete, we can analyze a game file and better reason about what it might do.

There’s certain behavior that we definitely don’t want game files to handle on their own, like randomness. If we replicate the game for every player (meaning every player has an identical copy of the game they’re playing on their own machine), then each copy of the game needs to stay in sync. But we want to have games with random elements. The most sensible solution is to have all randomness handled by a network-aware part of the Mental Poker layer that is guarenteed to give the same random results to each replicated game instance. And creating a platform whose only means of nondetemrinistic behavior is calling into this layer is the most obvious and foolproof way to prevent game developers from pulling in a random number generator from someplace else.

But designing a scripting language like this is a pretty hefty task, whose requirements could very well change as we refine the structure of the project. So for now we choose the approach that gives developers more flexibility: allowing game files to execute arbitrary code. For this proof-of-concept, I decided that the game files (and the rest of the implementation) would be Coffeescript scripts, a language that compiles down to Javascript. I chose this so that any examples included here could be easily tested and modified by readers any device without needing to install anything.

Just a note: This is my first time using Coffeescript, so I may not be taking full advantage of the language.

Ideally, we want this platform to be able to support as wide a variety of games as possible. When designing an API for this library that game scripts will call into, we don’t want to rule out a specific game or type of game because the library provides no way to receive necessary input or convey necessary information to the player. This requires us to define “game” in an unambiguous, mathematical sense.

So, what is a game? We want a definition that can describe as many different games as possible, for flexibility.

First off, a game must present players with choices. This is the key quality that makes something a game or not. If you’re not influencing the game’s outcome in some way, you’re not playing, you’re just watching. These choices are made based on information made available to the players. We call this available information at a specific point in time a game state.

The game state is the sum of all information available to any player about the state of any game piece and the value of any other variables that could influence decision-making (such as players’ scores.) It’s a flexible definition, but it must be in order to accommodate many different games. For any game, there are a (potentially infinite, but enumerable) number of game states.

One necessary component of the game state is the active player, the player who must make the next decision. Informally, this is the player whose turn it is. There are some games that require players to make decisions simultaneously, but this can be simulated through the use of cryptographic commitment schemes (which I will discuss in a later post, when we actually start implementing cryptographic features).

While a game is being played, it moves through a sequence of different game states, with the exact sequence determined by choices that the players make, (and in some games, by chance). For any given game state, there are several choices the active player can make, each of which will cause the game to transition to a new game state. Each of these choices, or options, can be formally represented as a pair (s, t), where s is the game state before the option is chosen, and t is a (possibly nondeterministic) function that transforms the game state s.

We can formally represent a game as a tuple (S, ?), where S is the set of all possible game states, and ? is the set of all options. In this way, a game becomes a state machine. (A formal state machine requires that each state transition be a pair of an input and output state. We can achieve this by saying that if any option is nondeterministic, then each possible resulting state has its own edge in the state machine.)

This notation allows us to completely describe any game in a table, merely by listing the possible game states and listing all transitions. This doesn’t mean that such a table will necessarily be short (or even have finite length!) For example, the game of Tic-Tac-Toe has 5,478 possible board states and 549,946 different possible options. (http://www.mathrec.org/old/2002jan/solutions.html) A more complicated game like chess could still be reperesented in this manner, but chess has 10^47 possible board states, and listing them all would be extremely impractical.

What is practical is calculating the part of the table that is immediately relevant for a given game state. Let’s say that we have a tic-tac-toe board in the following position:

 X |   | X 
   | X | O 
   |   | O 
board = {X: [[0,0], [0,2], [1,1]], O: [[1,2], [2,2]]} (This is just one possible way we could represent the board as a data object.)
    
activePlayer = 'O'

We could create a table mapping each legal move to a transformation function and the resulting game state:

Choice   Transformation Function            New active player    New Game State
    
[0,1]        (board) -> board.O.push [0,1]    X                    {X: [[0,0], [0,2], [1,1]], O: [[1,2], [2,2], [0,1]]}
[1,0]        (board) -> board.O.push [1,0]    X                    {X: [[0,0], [0,2], [1,1]], O: [[1,2], [2,2], [1,0]]}
[2,0]        (board) -> board.O.push [2,0]    X                    {X: [[0,0], [0,2], [1,1]], O: [[1,2], [2,2], [2,0]]}
[2,1]        (board) -> board.O.push [2,1]    X                    {X: [[0,0], [0,2], [1,1]], O: [[1,2], [2,2], [2,1]]}

Viewing games as a group of generated tables like this suggests an API: Instead of listing every possible game state, a game descriptor file needs to be able to do one of the following:

Option 1: (Functional Programming Approach)

• For a given game state, enumerate the possible Options and assign each one a unique id.

• For a given game state and an option id, check whether the given option is possible and return a new game state object that shows the result of choosing that option.

Option 2: (Imperitive Programming Approach)

• For a given game state, enumerate the possible Options and assign each one a unique id.

• For a given game state, check whether the given option is possible and apply the option to the game state, transforming it.

What’s so deceptive here is that at a first glance, it doesn’t even seem like there’s a choice to be made. In my initial draft, the rules script created the functions and data structures that governed how the game was played, and created and stored a singleton initial game state, which would be transformed by submitted options. Instead of exporting an object that contained the entire game state, parts of the game state were only referenceable through function closures in the Option objects. This was for all practical purposes a strictly worse version of the second option. I came to realize that this was a violation of “separation of concerns”, the maxim that any unit of code (be it function or library or file) should do one thing and do it well. But my rules script was trying to do two things when really, it should lay down the rules and nothing more. It should describe how to create the initial game state, but should not actually do it.

This is perhaps the most important design decision in this update, even though it doesn’t immediately seem like one. In my experience, the most important decisions are usually the ones that don’t even look like decisions. Learning to recognize these hidden opportunities is an important skill for any software engineer.

So how do we proceed from here?

Both of the options outlined above offer several advantages over my original naive implementation:

• Building test cases is much easier when the test case can supply an already built game state.

• The rules file only has to be loaded and processed once, and several games can be run simultaneously.

• The game state can be saved out to a file or data structure and loaded back in, allowing games to be paused and resumed, or a game to begin from a configuration other than its normal initial configuration.

There are programmers today that push strongly for a functional programming approach in everything. And it does have its benefits. For example, the first option has additional advantages over the seocond:

• Making the game state object immutable means that a reference to the game state can be kept as a snapshot of the game at a particular point in time, without having to worry about the object being modified or having to create a deep copy of it. This is useful for recording purposes.

• A player can simulate future outcomes from a particular game state without having to worry about mutating the game state or manually creating copies of it. This is useful for AI or for a user interface that lets a player experiment with future possible outcomes.

But this method has drawbacks, related to the process of creating a new game state from the existing one:

• Creating a new game state from an old one can require knowledge of how the game state is structured, and this isn’t necessarily trivial.

• If a new game state object is created every time an option would change it, this can lead to lots of unnecessary object creations and destructions, a performance penalty that scales with the complexity of the game state. It could be equally foolish to focus on optimizing something that hasn’t been proven to be a problem yet, so this penalty is something to keep in mind, but is not outright a reason to dismiss this approach.

These two drawbacks are wholly dependant on how the game state object is represented internally. If we can devise a representation that can easily be instantiated from an old game state and an applied Option, without adding restrictions or complications to the process of creating a rules file, then the drawbacks are inconsequential, and it becomes better to take the functional programming approach.

One option comes from recognizing that any game state is created by sequential effects to an initial game state, where an effect is the outcome of executing an option. It’s possible for us to represent the game state as this list of effects. If the list is a linked list, we can append new effects to the front of the list, creating the new game state in constant time.

But now, every time we want to read a value from the game state, we must iterate through the list until we find the relevant bit of information. We could potentially overcome this by caching read values at the front of the list so that the next read won’t take as long. But for right now, we won’t worry about this. Until we have a finalized model for how game state will be internally represented, we don’t need to worry about optimizing our approach. Knowing that the approach works will be enough for now.

With all this research and planning behind us, let’s start writing code. We need to nail down an API to be used by the rules file to convey the rules for a game to the game engine. The best way to create a sensible and predictable API is to create a use case first: let’s create a prototype rules file and see how we would instinctively want to express the rules for a simple game like Tic Tac Toe. (The rules file is currently a coffeescript script that is loaded and executed in a special environment. The major downside is that this requires that the rules file be trusted, so this is by no means a final solution.)

What’s the most important part of a game? The players. So let’s tell the engine about the players.

X = new Player("X")
O = new Player("O")

The string parameters are ids that we can use to reference the players later, since the variables X and O will only exist in this local scope.

Like all objects in coffeescript, X and O can have arbitrary properties defined on them. We can do that now:

X.opponent = O
O.opponent = X

There is no builtin way to dictate turn order, since not all games settle for something as simple as “clockwise around the table.” We will handle turn order by having each player pass the baton to the player listed as their opponent. (We’ll get to that in a bit.)

The main building block of the game is the Piece, an object that represents a manipulatable part of the game, such as a card or space on a board. Any options that a player can choose are granted by pieces in play. Actions that should always be available or variables that are always present are owned by Pieces that are created at the start of the game and cannot be removed. For our game of Tic Tac Toe, each space on the grid is its own Piece. Since the behavior of each grid space is effectively the same, we can subclass the Piece class. Below is the entire class definition:

class GridSpace extends UnownedPiece
    constructor: (@i, @j) ->
        super
        @id = [@i, @j]
        @controller = null
        @addOption
            id: [@i, @j]
            condition: (player) ->
                @controller == null
            playerCondition: -> true
            effect: (gameState, player) ->
                @controller = player
                if win(gameState.pieces, @i, @j)
                    gameState.ended = true
                    gameState.winner = player
                else if draw(gameState.pieces)
                    gameState.ended = true
                    gameState.winner = null
            nextActivePlayer: (player) ->
                player.opponent

Let’s go through this line by line:

class GridSpace extends UnownedPiece
    constructor: (@i, @j) ->
        super

Oftentimes, a Piece has one player that owns it. In a card game, you own the cards in your hand, for example. But board spaces aren’t owned by any player, so we subclass a special class UnownedPiece (which itself subclasses Piece). We override the constructor so that it takes two values, a row and column of the space in the grid, which we will use to construct the space’s unique id. We then call the superclass’s constructor because as far as I can tell, this isn’t done automatically in Coffeescript.

    @id = [@i, @j]
    @controller = null

We create the id instance variable. I chose to keep it as an array, but due to Javascript’s weak typing it will be coerced into a string automatically when it’s used as a key. Just remember that every piece’s id should be unique when coerced to a string.

We also create the instance variable @controller to denote which player has claimed the space. At the start of the game, neither player has the space, so it’s equal to null. We could have tried to combine the notion of a controller with the notion of an owner as outlined above, but changing a Piece’s owner changes some of its default behavior (for example, by default players can only choose options on Pieces they own and UnownedPieces), so it’s better to keep these two ideas separate.

        @addOption
            id: [@i, @j]
            condition: (player) ->
                @controller == null
            playerCondition: -> true
            effect: (gameState, player) ->
                @controller = player
                if win(gameState.pieces, @i, @j)
                    gameState.ended = true
                    gameState.winner = player
                else if draw(gameState.pieces)
                    gameState.ended = true
                    gameState.winner = null
            nextActivePlayer: (player) ->
                player.opponent

The option to claim a space on the board is closely related to the state of the space itself, so we add the option to the space (recalling that every option must belong to a space in order for the game to access it.)

We use the addOption instance method to create a new option connected to that piece. We pass a dictionary containing the following fields:

• id: A unique id for this option. When a player queries the options they have available, they are not given the actual option objects, but an array of ids. Like the ids for pieces, each of these ids must be distinct when coerced to a string, so it’s best to use only primitives and arrays of primitives when constructing an id. Since each piece here has exactly one option, we use the same ids we used for the pieces.
• condition: A condition that must hold for the option to be available to a player. In this case, the space must not be claimed by any player.
• ownershipCondition: An additional condition that must hold for the option to be available to the player. If ommitted (like we did here), it returns true for UnownedPieces and checks whether the owner is the same as the player calling it otherwise. This is used in complex games where your own pieces give your opponents additional options.
• effect: A function that will be called when the option is chosen that changes the game state. In our case, we change the controller of the grid space to the player choosing the option, then check to see whether that player has won or whether the game has drawn. If the game is over, we set the corresponding fields in the gameState variable so that our gui will be able to detect it.
• nextActivePlayer: The player who will make the next choice. In this case, once a player claims a space their turn is over, and their opponent makes the next choice.

Next let’s go on ahead and define those win and draw functions we just used:

win = (pieces, i, j) ->
    if(pieces[[i, 0]].controller is pieces[[i, 1]].controller is pieces[[i, 2]].controller)
        return true
    if(pieces[[0, j]].controller is pieces[[1, j]].controller is pieces[[2, j]].controller)
        return true
    if(i == j and pieces[[0, 0]].controller is pieces[[1, 1]].controller is pieces[[2, 2]].controller)
        return true
    if(i + j == 2 and pieces[[0, 2]].controller is pieces[[1, 1]].controller is pieces[[2, 0]].controller)
        return true
    return false    

draw = (pieces) ->
    for i in [0..2]
        for j in [0..2]
            if pieces[[i, j]].controller is null
                return false
    return true

Finally, we must define a function that will create the initial game state:

Rules(
    startingPlayer: X
    initialize: ->
        pieces = {}
        (((pieces[[i, j]] = new GridSpace(i, j) for i in [0..2]) for j in [0..2]))
        return pieces
)

The Rules callback function takes an object with two named fields: startingPlayer, which is equal to the player who goes first, and initialize, which is called whenever a game begins and which creates and returns the pieces on the starting board (and does anything else that needs to be done to set up the game.) We could have alternatively had the user script return a data object (since the user script will be wrapped in a function), but this way the Rules callback can appear anywhere in the script, not just at the end.

And this is it for the rules definition file. Everything outlined above should be sufficient to fully describe the rules of Tic Tac Toe.

So now how would an application use this system to run a simple Tic Tac Toe game? The entire code of the basic web app included on the github repo is below:

Multigame.load("scripts/tictactoe.rules.js", (rules) ->
    gameState = rules.newGame()
    $("#activePlayerFrame").html("It's player " + gameState.activePlayer.name + "'s turn")
    global "chooseSpace", (i, j) ->
        if gameState.ended
            return
        activePlayer = gameState.activePlayer
        symbol = activePlayer.name
        commitResult = gameState.commitOption(activePlayer, [i, j], [i, j])
        if commitResult.success
            gameState = commitResult.newState
            $("#board").children().eq(3*i+j).html(symbol)
            if gameState.ended
                if gameState.winner?
                    alert("Player " +  gameState.winner.name + " wins!")
                else
                    alert("It's a draw!")
            else
                $("#activePlayerFrame").html("It's player " + gameState.activePlayer.name + "'s turn")
        else
            console.log(commitResult.error)
)

There are three more method calls of importance here that we will have to implement:

Multigame.load(uri, callback) - this method loads the rules file from the supplied location, parses it to create a rules object, and then calls the callback with the rules object as the parameter.

rules.newGame() - this method creates and returns a new initial gamestate.

gameState.commitOption(player, pieceID, optionID) - this method attempts to apply an option equivalent to the given player choosing the option with the given ID on the piece with the given ID.

Now we need to implement the interface we used in these files. Let’s start with some of the classes:

class Player
    constructor: (@name) ->
    
class Piece
    constructor: () ->
        @options = {}
        
    addOption: (option) ->
        @options[option.id] = option

Right now, a player is just an object with a name field that we use as a tag for that player, while a Piece just wraps a list of options. (And an option is just the dictionary we passed into @addOption in the GridSpace constructor.)

class OwnedPiece extends Piece
    constructor: (@owner) ->
        super
        
    getOptions: (player) ->
        options = {}
        (options[option.id] = option) for option in @options when option.condition.call(this, player) and (if ownershipCondition in option then option.ownershipCondition.call(this, player) else player == @owner)
        return options

Even though we don’t have any owned pieces in the Tic-Tac-Toe rules, it’s clear how an owned piece should behave. It has an owner variable which is set during construction, and it has a getOptions method that returns every option on the piece that is a legal choice given the current game state. We do this by filtering the set of options via the option.condition and option.ownershipCondition methods (or of option.ownershipCondition is not set, checking that the current player matches the piece’s owner.)

UnownedPiece is very similar, except it doesn’t have an ownership condition or an owner:

class UnownedPiece extends Piece
    getOptions: (player) ->
        options = {}
        (options[oid] = option) for oid, option of @options when option.condition.call(this, player)
        return options

The only remaining class is the GameState class, which needs to contain all information to describe the current game state, as well a method for querying what options are available for the active player, and a method for applying a chosen option and returning the new modified game state. The GameState right now is a basic data structure containing the set of pieces on the board and the active player:

class GameState
    constructor: (@pieces, @activePlayer) ->

We need a way to query a game state for all legal moves for the active player. This just requires us to iterate over each piece in the game state and look at its options. I chose to represent this as a map from piece ids to a map from allowable option ids to the corresponding option, although other representations are possible and may be preferable:

    getOptions = (player) ->
        options = {}
        for pid, piece of @pieces
            options[pid] = {}
            for oid, option of piece.getOptions(player)
                options[pid][oid] = option
        return options

The most important part is the commitOption method, which generates a new game state from an old state and an option. Without this, the game can never advance beyond the opening move!

    commitOption: (player, pieceId, optionId) ->
        options = getOptions.call(this, player)
        if pieceId not of options
            return {success: false, newState: this, error: "bad piece" }
        if optionId not of options[pieceId]
            return {success: false, newState: this, error: "bad option" }
        option = options[pieceId][optionId]
        newPieces = Object.create(@pieces)
        newGameState = new GameState(newPieces, option.nextActivePlayer(player))
        newPiece = Object.create(@pieces[pieceId])
        newGameState.pieces[pieceId] = newPiece
        option.effect.call(newPiece, newGameState, player)
        return {success: true, newState: newGameState }

The first two if statements just check that the committed option is actually a legal option to take. (This is more to prevent accidents than it is to stop any real malicious behavior, since this code may be running on the same machine used by a player, in which case a player could easily modify the generated javascript. Stopping players from cheating is an entirely different beast and requires us to consider how the game will actually be accessed by players. We save worrying about that for a higher layer.)

The magic is in the Object.create method, which makes use of javascript’s prototype-based inheritance to effectively make a shallow copy without incurring the cost of copying each value. The new object references the old one as it’s prototype, so when the javascript interpreter tries to dereference a field that doesn’t exist on the new object, it moves up the prototype chain and checks the old one.

This isn’t optimized. A property that exists many levels up the prototype tree will take longer to access every time. Worse, if we try to modify another piece, or a property of a piece or option has its own fields, we could very easily end up modifying a reference shared by several different game state objects, which breaks our guarantee that game states not be modified after they are created. It’s much better to use a dedicated immutable data structures library, but as the maxim goes, premature optimization is the root of all evil. For now, we settle for having a rule that in an option’s effect, if you would modify any piece other than the piece belonging to the option, or if you would modify a property on the piece with more than one level of indirection, you clone the appropriate objects to guarantee that you don’t modify shared values.

Lastly, we need to create the Multigame.load method, which reads in a provided rules script and executes it.

Multigame =
	load: (filename, callback) ->
		$.ajax
			url: filename
			dataType: "text"
		.done (data) -> 
			rules = {}
			Rules = (r) ->
				rules = r
			(new Function("Player", "Option", "OwnedPiece", "UnownedPiece", "Rules", data))(Player, Option, OwnedPiece, UnownedPiece, Rules)
			rules.newGame = ->
				pieceList = @initialize()
				initialGameState = new GameState(pieceList, @activePlayer)
				return initialGameState
			callback(rules)

And that’s it. This is all we need to run a game of Tic Tac Toe on top of the Multigame model, and all the code here is available as a github project. (https://github.com/nicktobey/multigame/)

Looking back on everything I just wrote, I’m beginning to question whether it was really valuable to talk about every line of code in this comparitively simple project. If I give this same attention to detail to every update, I’ll spend more time explaining myself then actually working. But I do think it was important to lay down the theory, explore what could constitute a good API, and consider the ramifications of my design choices. This code sample was small enough that I could touch on everything, but I won’t have that priviledge for long. Going foward, I’ll probably spend most of each post discussing a particular subproblem of interest that came up, or a specific design goal, or something similar.

If we think ahead to the end goal of making a decentralized networked game, we realize there’s a certain level of trust here. The rules script can potentially access the top-level window object, or modify the classes we just made. But that’s okay, since in a networked game, the javascript client wouldn’t be trusted anyway. There won’t be any values hidden in the javascript runtime that wouldn’t already be available to the player. And opening up the runtime to modifications like this can have benefits, like scripts that analyze the game and provide strategic information to players.

And this is enough to describe any game that is deterministic and has a finite number of choices at each position. We did Tic Tac Toe, but we could theoretically implement a more complicated game like Chess or Go, just using what we have right now. The constraint that we are limited to games with finite choices at each branch is a result of our implementation, and I may try to improve it in a later update.

With this model, we can’t make games that hide information from the players. The model doesn’t even let us express the idea of hidden information: every detail in the model is available to anyone who looks at it. So how can make it so that certain information is only available to certain players, even when every player must share the same view of the model? This suggests a solution with cryptography: hidden information is encrypted, and players only have the keys to decrypt the information they are supposed to be able to see. But this begs the question of how these keys can be created and distributed in a secure manner.

Likewise, making a game with nondetermistic elements is going to require some consideration about how this model will be used and what we’re trying to accomplish. It’s not enough to just throw in a random number generator, as this would make it impossible to replicate the game model across multiple devices, which we’ll need if we want to make a networked multiplayer game. It would also make it harder to use the model to study possible outcomes, when the random elements are hidden away instead of being incorporated into the framework. Again, cryptography may help us solve some of these problems. Specifically, we need to use a branch of cryptography called Secure Multiparty Communication.

Sooner or later, if we want to make a networked game, we’re going to have to tackle these problems. But that’s getting ahead of ourselves. Before we can tackle these bigger problems, we should work on perfecting this model. That’s why in the next update, I’ll discuss improvements to the model, both in terms of API design and efficeincy. I will discuss possible use cases and create unit tests that verify that the guarentees I claim this model provides (such as protection from inadvertantly mutating game states) are actually provided.

Next up: Immutable data types, decision trees, and unit testing!