29 Jul 2015
In an attempt to brush up on my crypto understanding, I’ve decided to attempt the Matasano Crypto Challenges, aka the Cryptopals challenges. (Github repo) And since I want this to be a learning opportunity, I’m doubling down by choosing to implement all my solutions in language and paradigm that was unfamiliar with me, so that even if I saw a problem I was already familiar with, I would be forced to view it differently. I chose Haskell and Rust as my weapon of choice, since for all the buzz they seem to get (Haskell especially), I don’t really know that much about them.
(A note: while this post is about my experience learning Haskell, it is not a haskell tutorial. Some amount of familiarity with functional programming is assumed, but not much, since I’m still picking it up myself.)
I do think that functional languages like Haskell have a lot of useful features that are underemphasized in traditional education. One of my solutions to the Google Foobar Challenge was a memoized recursive function. It was giving me correct answers, but it wasn’t efficient enough to run within the time limit. I wanted to know the time complexity of the algorithm, but during the entire semester of my Algorithms class, we had not once touched on measuring the complexity of a function like this, while we’d spent a whole week on loop invariants. I had to puzzle it out by considering which subcases would actually be computed (not all of them, so translating this to a dynamic programming algorithm would be even less efficient.)
But has using Haskell saved me time? I don’t know. I considered measuring how long it took me to solve these problems versus solving similar imperative problems, but such measurements wouldn’t have accounted for the time it took me to learn the language as I went (you could say that my task of learning Haskell was being evaluated lazily.) I do know that in most cases, once I got the program to compile, it was correct for all inputs. But I also know that I had a lot more compile errors that took me a good amount of time to understand. From a design perspective, this was probably a good thing. Making it impossible to express bad code increases the quality of the code you create. But did it save me time? I don’t have the numbers, but I don’t think it did.
I also learned that there’s a difference between writing code in Haskell and actually understanding what Haskell can do. I wrote my initial solutions to the first couple problems with no understanding of monads, one of Haskell’s most useful features. And these solutions worked. But they wordy and had an awful lot of boxing/unboxing of Maybe values.
For example, here was my initial implementation of a function that converted a hex string into a list of bytes:
hexChars = "0123456789ABCDEF"
{- Converts a hex string into a byte array -}
hexToBytes :: String -> [Word8]
hexToBytes hexes = hexToBytes' (map toUpper hexes) 0
hexToBytes' (char1 : char2 : xs) pos = case (maybeByte1, maybeByte2) of
(Nothing, _) -> error ("Bad input at position " ++ show pos)
(_, Nothing) -> error ("Bad input at position " ++ show (pos+1))
((Just byte1), (Just byte2)) -> fromIntegral(byte1*16 + byte2) :: Word8 : hexToBytes' xs (pos + 2)
where maybeByte1 = char1 `elemIndex` hexChars
maybeByte2 = char2 `elemIndex` hexChars
hexToBytes' (char1 : []) pos = error "Input of odd length"
hexToBytes' [] pos = []
The idea behind the function was simple. Define it recursively, so that we take each pair of characters in the input and convert them to their byte values. But the expression of this wasn’t simple. The elemIndex function doesn’t return an value of type Int, it returns an value of type Maybe Int, which could contain an Int, or could contain Nothing. This is Haskell’s approach to operations that may not return a meaningful answer. Instead of returning an error code or throwing an exception, it returns a Maybe. This means that the possibility of the function not returning successfully is baked into the function’s signature. Extracting the value inside the Maybe requires several lines of pattern matching.
Maybe this is desired. It allows us to return helpful error messages on bad input. But since Haskell is evaluated lazily, there’s no way of predicting when these errors are going to be thrown. We can’t get a stack trace, so knowing that somewhere we’re calling hexToBytes with bad input isn’t necessarily that helpful for debugging. An error message that’s meaningless at the high level is only marginally better than no error message at all.
I could have avoided repeating the error message specification by including another function in the where block that pattern matched the Maybe and extracted it, but I would have had to pass the position into the function, where it really didn’t belong. The issue was that I wanted a meaningful error message that could only be generated at a lower level that didn’t have any understanding of the larger program in context. And I was bypassing the Maybe type to do it. I was actively wrestling with the language instead of trying to leverage its features. (Sure enough, I learned that using error in this context is discouraged.) Surely there was a more “Haskallian way to do it.”
This is where I learned about Monads, the bread and butter of Haskell
I first tried to learn Haskell by reading Learn You a Haskell For Great Good, which explained monads mostly in terms of the type signatures of their functions, which led me to see them as some sort of esoteric element of category theory. A few examples wasn’t enough for me to grasp why monads mattered, or why I would want to use them. It wasn’t until I read Real World Haskell that I understood how to think of monads in a way that could improve even simple code: monads represented a context in which an operation can take place, and they alleviate the need to give this context special consideration. Maybe, as a monad, represents a context where we expect a value, but it may not be there. List, as a monad, represents a context where we expect a value but may find an arbitrary number of values. Code that does not abstract this away would have to pattern match against every Maybe it comes across in order to access the inner value, manually handling every case where the Maybe is a Nothing. But functions on Monads allow the function to be oblivious to the context of the value, and allow passing the values within the monads to functions that are also unaware of the context. The possibility of a value being Nothing becomes someplace else’s problem, allowing functions to focus on their single responsibility. This is a powerful tool for terse readable code. Whereas before my function was cluttered with Nothing checks (not as cluttered as it could have been, certainly. If I wanted to demonstrate the ills of manually matching each Maybe, I could have come up with a much worse example). But now the function is cleaner, and its behavior is more obvious.
Instead of extracting a value from a Maybe as soon as I get it, I can keep the entire computation within the Maybe context, only extracting the value at the end. There’s no performance penalty, because if the initial elemIndex returns Nothing, lazy evaluation ensures that this Nothing propagates through the rest of the function without performing any unnecessary computations.
This was my final version of the same function, using Haskell’s do-syntax.
hexToBytes hexes = hexToBytes' (map toUpper hexes)
hexToBytes' (char1 : char2 : xs) = do
tail <- hexToBytes' xs
byte1 <- char1 `elemIndex` hexChars
byte2 <- char2 `elemIndex` hexChars
return ((fromIntegral(byte1*16 + byte2) :: Word8) : tail)
hexToBytes' [_] = Nothing
hexToBytes' [] = Just []
The do-block is actually syntactical sugar for binding a binding a bunch of monads together so that each one is built by applying a function to the result of the previous one. If we desugar this code block, we can see the nested functions that make up the final monad:
hexToBytes hexes = hexToBytes' (map toUpper hexes)
hexToBytes' (char1 : char2 : xs) =
hexToBytes' xs >>= \tail ->
char1 `elemIndex` hexChars >>= \byte1 ->
char2 `elemIndex` hexChars >>= \byte2 ->
return ((fromIntegral(byte1*16 + byte2) :: Word8) : tail)
hexToBytes' [_] = Nothing
hexToBytes' [] = Just []
This is still readable, but it’s easy to see how a more complicated function could get messy quickly, especially with the extra indentation that do-notation makes unnecessary.
Now, do we lose the ability to include a useful error message? Maybe. But keep in mind that the error message wasn’t that useful to begin with. The only value was that it gave us the position in the hex string that was invalid, which isn’t hard to figure out. But because haskell uses lazy evaluation, we wouldn’t even know which hex string it was! If we really need to display that information, there are other better ways to do it in Haskell. (The Either type as a monad can hold a result or an error message.) But in this case, we don’t need that. We can keep it simple. And this new code is a lot simpler, and a lot more readable. It does change our type signature (we now return Nothing on invalid input instead of throwing an error), but you know what? The new behavior makes sense. Nothing is for computations that may fail, and this computation can only fail in one way. If hexToBytes returns nothing, the fix is clear: Check you input! And if we use monads, we can detect and handle errors where we need to without having to resort to thrown exceptions.
16 May 2015
(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!
25 Dec 2014
The History
I’m a gamer. It’s a relatively recent change, but over the last year I’ve built a small collection of board games for my friends. (A collection that grew somewhat this morning.) So one of my major interests is how technology affects how we play games.
Around December of 2013, three things happened in approximate proximity to each other:
The first was a major server problem during the Magic: The Gathering Online Championship Series championship event. The all-day tournament drew over 300 players who competed for an invitation to the Magic Online Championships. In the eighth of nine rounds, the server crashed, removing some players from their matches and eventually ending the entire tournament prematurely. The day after, eight hours into a Pro Tour Qualifier event with over 700 players, Magic Online crashed again. In both cases, owning company Wizards of the Coast’s response was to refund players their entry fee and reschedule, wasting thousands of person-hours of the players involved. In the fallout of this catastrophic failure of the Magic Online software, Wizards disabled large events for half a year while they worked on the server.
The second event was the approaching final exam for my Intro to Computer Security class at UNC. I was trying to apply what I had learned by reading up on the Mental Poker Problem. In brief, the Mental Poker Problem concerns how to play a game involving randomness and hidden information over a network without the need of a trusted third party. (The name derives from Mental Chess, a variant of chess played without a board where the players recite their movements to each other and keep track of the pieces in their head. This is possible because in chess, moves are deterministic and all information available to all players, so a move can be instantly validated as legal or not. Mental Poker without a computer would be a lot more troublesome.)
Wizards’ biggest obstacle was servers that didn’t scale to accommodate large player loads. As the popularity of Magic grew, the cracks in their system grew. So while others blamed outdated software, or Wizard’s effective monopoly on online collectible card games, or Wizards’ practice of only hiring local programmers, I wondered if the problem was the existence of the server itself. Could Mental Poker be applied to allow users to play complex games like Magic without the need for a central server to validate the gamestate?
The Idea
Probably not.
As my reading uncovered, existing Mental Poker protocols are not designed for the large variety of actions available in games like Magic: actions like returning cards on the table to a player’s hand, searching a player’s deck for a specific card, revealing the contents of the deck to a single player, and so on. And they are efficient only when viewed with extreme optimism. But the research yielded possibilities.
Magic Online had its own microcosm of an economy, full of collectors and gamblers and speculators in an online marketplace. But no one truly owned the assets they were investing in; they were all data on Wizards’ servers, and if Wizards of the Coast decided to close up shop and shut them down, then these players would lose everything. (Certainly Wizards has no intention of doing something that would destroy all confidence in the company, and they aren’t showing any signs of financial distress, but this dependence on servers staying online doubtlessly discourages players from investing in new games.)
I wondered whether there was a way for the players to prove ownership of their digital collections without connecting to a trusted server. A system like this could even permit players to trade in-game items outside of official channels, allowing them to more easily sell these items for real money, or trade for items from a completely different game. The implications weren’t just limited to gaming. I realized I was trying to design a decentralized database for management of digital goods, be it game items or licenses or e-books, or more.
The third and final event that occurred that month was a bursting bubble in the bitcoin speculation market. After the exchange rate of the cryptocurrency reached an all-time high, the price plummeted to half that in a matter of days. Curious about the inner workings of Bitcoin and blockchain cryptography, I read the Bitcoin white paper. I was not interested in bitcoin as a currency, and the crash was painting a strong sign that it wouldn’t work out as a bank account or means of exchange (especially for someone who knew next to nothing about market forces, like me.) But I was interested in Bitcoin as a technology, and reading the white paper I came to understand that Bitcoin was attempting to solve the exact same problem I was. Provided the ability to differentiate between sets of coins (which several existing projects, such as Colored Coins, are already attempting to do), Bitcoin becomes a generic decentralized means of digital asset management.
This became the foundation of a project I obsessed over winter break that year. I later spun off into two new projects: BitToken, a blockchain-based cryptosystem designed for trading typed assets, and Delectables, a platform for designing collectable games that used BitToken to verify ownership of game pieces and Mental Poker to conduct games in a decentralized manner.)
The Reality
This was a year ago. Last December I was so excited to get started, but a year later I have nothing to show for it. No prototypes, no code repositories, not even a nailed-down list of features to support. And to a certain extent, this was to be expected. I had little knowledge of the cryptography involved, and the project would be leagues more complex than anything I had done before. I knew out of the gate that this would be a research spike of astronomical proportions. I knew that even if I failed to make a workable product, the experience would leave me primed to take advantage of any work on distributed cryptographic systems that emerged in the meantime.
But still, nothing? How could this happen?
As I pondered how to approach this problem, I gradually accumulated more goals and requirements, which I realized too late was a big mistake. Feature creep hit me before I had drafted a single spec.
For example, is it possible for a group of users to coordinate a tournament without outside assistance? (a problem less trivial than it seems, since players could contest the outcome of an individual match.) While this problem was unrelated to the initial problem of verifying ownership, it was worth considering if I wanted to really push serverless games.
Or another feature worth considering: In Magic and collectable games like it, players can buy booster packs, which contained random cards from a set. Unopened booster packs from the same set are indistinguishable, so Magic Online players use them as an alternate currency. Booster packs can be modeled as a cryptocurrency with one additional feature: they can be converted into a random selection of cards. Could BitToken support this type of conversion? If so, how?
The more I dug, the more I saw that I wanted to do with this project. And it suffocated me. I knew no matter how I allocate my time, BitToken and Delectables would demand more from me than I would be able to give it.
In the spring I focused on my schoolwork, in the summer I focused on my summer job, and in the fall I focused on schoolwork again. And I don’t regret that decision. But I still failed to make time for a project that not only personally inspired me, and would give me a much-needed portfolio. And understanding why I failed to produce anything is what will help me make strides.
Firstly, it was clear I had bitten off more than I could chew. Even if my goals were well-defined, they were broad and varied, without much of an existing platform to work from, so I had no place to start. At one point I discovered the Ethereum platform (http://www.ethereum.org), and suspected that it might be exactly what I needed. My mission statement became “Learn Ethereum”, a nebulous and distracting goal, especially given that Ethereum was still in beta at the time, and trying to work Ethereum ended up taking up my time and producing nothing.
My second problem was a lack of accountability. If I failed to keep to any goals I had set (not that I had taken the initiative to make goals either) I faced no consequences for my failure, and no one would even know that I had tried. I needed a stick.
And giving Google recruiters a link to this site before it was even up? That’s a stick if I’ve ever seen one.
The Project
The solution to this problem was to define smaller projects that would not produce the full specification of BitToken and Delectibles, but would provide me with not only the experience I would need to tackle a more extensive project, but would produce something I could show for my effort.
I will force myself to make weekly updates on this site about these projects, what approaches I took, and what I learned. Each post will link to a github repo containing any code I wrote that week, regardless of whether or not I think it’s worthy of uploading for the world to see. If I put off publicly demonstrating my project code until I feel it’s presentable, it will never see the light of day. If I’m going to chronicle my entire experience, I need to push aside that conservative perfectionist habit.
So that’s my goal now: Demonstrate (as much to myself as to anyone else) what I can learn and do. The only way to fail is to not produce anything.
Next time: I break up the monolithic concepts of BitToken and Delectibles into smaller, manageable projects, and I pick one.