Last fall at my local board game meetup I was introduced to A Game of Thrones The Board Game. Originally based on Diplomacy, A Game of Thrones places three to six players in charge of the great houses of Westeros to vie for control of the continent. With a minimal element of luck1 players spread influence with diplomacy, card selection, and strategic planning. I am fascinated by this game and have played a few dozen times in person and one hundred games online2.

Now that we have dispensed with the pleasantries we can get on to the purpose of this post: expanding the game to support up to nine players. There are a few variants available online - “A Feast For Crows” Expansion3, “The Winds of Winter” Expansion, and Essos4. I went for the “Essos” expansion since it was the first one I found. I intend to try the other two when my regular playing group gets tired of the Essos version.

The Map

In order to make room for three more players/houses the territories in the central portion of Westeros have been divided and rearranged and the western portion of Essos has been introduced. There have also been some other balance adjustments (e.g. rearranging resources, borders, and strongholds) as fallout from introducing many new territories. The wildlings track has changed to increments of 3 to account for the new players5. The supply track has also been expanded up to 8 barrels since there are potentially more territories to cover on the path to seven castles. Click on the map for a full resolution version.

the map

Essos

The most obvious change when looking at the new map is the addition of a new continent on the eastern portion of the map: Essos. Hence the name of this expansion. Essos consists of eight territories with two strongholds and two castles. Braavos starts with a neutral force of 8 to eliminate a quick rush but is a valuable position late in the game for many houses.

The more interesting change accompanying the new continent is the additional sea zones. Now there are four sea zones off the east coast of Westeros which allow for three houses to participate in combat. In the official six player map it is common for sea zones to fall into a stalemate where players continually place support and raid tokens in alternating sea zones which completely eliminates sea zones from play6. With three players the dynamic changes to incentivize diplomacy and/or strategy.

The Riverlands

Move over Lannister time to make room for another house. Divided into eight territories and covered with castles, strongholds, and resources - the Westerlands now serve as the home for two houses. This change requires drastic changes to Lannister, Greyjoy, and Tyrell strategies while bringing more of the story to life by turning the Riverlands into a war-torn countryside.

The Vale

The Vale has been littered with resources and is no longer the stomping grounds for House Stark. There are now two strongholds and two castles east of the river along with a new sea zone, The Bay of Crabs. The impassable borders and rivers along with no single central region make navigating and holding the Vale a significant challenge. If you can muster enough strength there are plenty of resources and easy access to Essos.

Impassable Borders

The official map contains rivers denoted as blue borders between regions. Rivers break the adjacency between otherwise neighboring spaces. So units cannot move between, raid, or support spaces across a river. Unless there is a bridge. The Essos map introduces the concept of impassable borders which are black lines between spaces. These are functionally equivalent to rivers but lack the thematic motivation. The impassable borders were introduced since the central region of the board is now crowded with two additional houses.

Balance Adjustments

There are less drastic, but equally important, changes throughout the rest of Westeros in order to keep the game balanced. Starting at the top and working our way down through each of the remaining houses, first we have House Stark. Since the Vale is now occupied by a new house the resources that the Starks’ traditionally rely on have been redistributed across a newly partitioned north.

The Shivering Sea now extends to Braavos and due to the newly added sea zone The Byte loses the ability act as unraidable support7. That honor has moved to the west coast with the addition of “Bear Island” and the division of the Bay of Ice into two sea zones. No longer touching either ocean, Winterfell is dramatically smaller. Instead Deepwood is added to the west coast with a castle and a port.

Continuing down the western coast we reach House Greyjoy. The castle at Flint’s Finger and stronghold at Seagard have swapped places. No other changes beyond the modifications for the Tullys and Lannisters.

Continuing the counterclockwise tour of Westeros, House Tyrell. The castle previously The Reach is now further from King’s Landing making it easier to hold, while the extra supply in from Blackwater is now further from Highgarden forcing House Tyrell to look elsewhere for supply.

Next up: the Martells. Storm’s End is no longer adjacent to the Sea of Dorne but the Rainwood has been added and includes a supply. Lys is a nearby island and Essos is only one sea zone away.

Finally House Baratheon whose seat has been moved from Dragonstone to Storm’s End. This is to allow for separation between all three new neighbors. Tarth is a new island added to the east of Storm’s End and provides the opportunity for a quick supply grab. The rest of the changes that affect House Baratheon have been discused previously.

Printing the Map

By replacing the tracks with Essos the expanded map is nearly identical in size to the original. Extra printouts can be placed anywhere around the table to track the influence and victory status for each house. I went to the FedEx Office store across the street from my apartment to print the map. Two hours and $50 later I walked out with a freshly minted map.

The New Houses

The three new houses are House Arryn, House Targaryen, and House Tully. Each house needs cards, power tokens, track markers, and a shield (to hide which orders have yet to be used). The original designer produced a few pdfs containing all of the required images. My wife and I spent two nights at the FedEx Office store printing, cutting, and laminating all of the pieces. Lamination is not necessarily the best production method, but it was the cheapest that provided any level of durability. I plan to try a different method next time.

House Arryn

The House Arryn cards place a strong emphasis on power tokens. In fact, every card with text deals with power tokens. This provides an interesting twist to bidding since tokens are easier to come by but are also valuable in battle. house arryn cards

House Targaryen

The House Targaryen cards either increase strength of units in combat or allow you to place/move orders after resolving combat. Daenerys is the only card in the game (aside from the awful Tides of Battle cards) with a skull symbol. The skull kills one unit even in the presence of towers. house targaryen cards

House Tully

Since the designers could not settle on seven cards House Tully is the only house to have eight. Staying true to the theme, many of the cards provide tactical advantages if you are able to predict what card your opponent will play. house tully cards

The Units

I have recently obtained a Printrbot Simple Metal 3D printer for projects just like this one. To create the pieces I found and printed these pieces by Srokap for each house at 30% infill to match the weight of the official pieces. Purple for House Targaryen, sky blue for House Arryn, and orange for House Tully. Purple and blue work thematically, but orange was the only other color of plastic I had on hand. the pieces, 3d printed

References and Files

I have uploaded the resources required to make the game to Dropbox (tar.gz or zip). If you try the game or have any suggestions for improving it let me know.


  1. The game has only one element of randomness - the ordering of events in the Westeros decks.
  2. Thronemaster
  3. Not to be confused with the official “A Feast For Crows” expansion with House Arryn and scenarios.
  4. Video overview from the designer
  5. The wildling track still follows the 1 power token per three players per space ratio. This leaves bidding strategies relatively untouched.
  6. The Raid/Support stalemate would be a great topic for a future blog post.
  7. Support placed in an area which cannot be raided since the player controls all neighboring zones.

The Fibonacci sequence is the sequence of integers where the next number is the sum of the previous two. While there are numerous examples in nature and many applications this post will focus on algorithms for computing any given number in the sequence. Determining the nth number in the Fibonacci sequence is a common exercise in computer science courses and interviews.

The first method is a direct translation of the recurrence relation definition.

func recursive(n int) int {
  switch n {
    case 0:
      return 0
    case 1:
      return 1
    default:
      return recursive(n-1) + recursive(n-2)
  }
}

The computational complexity of this method is O(n^2) which can be derived by counting the number of stack frames generated in an example run. Many of these function calls are repeated and therefore could benefit from memoization.

func memoize(n int) int {
  cache := make(map[int] int)
  cache[0] = 0
  cache[1] = 1
  return memoizeInternal(n, cache)
}

func memoizeInternal(n int, cache map[int] int) int {
  if res, ok := cache[n]; ok {
    return res
  }

  res := memoizeInternal(n-1, cache) + memoizeInternal(n-2, cache)
  cache[n] = res
  return res
}

Memoization will reduce the complexity to O(n), one addition per number in the sequence. For ever other stack frame we will return the cached answer. The memoized method will also need linear memory. The next approach can compute F(n) in linear time with constant memory.

func iterative(n int) int {
  a := 0
  b := 1
  for i := 0; i < n; i++ {
    a += b
    a, b = b, a
  }
  return a
}

By using a different form of the definition for the Fibonacci sequence, the result can be computed in O(lg(n)) time.

        n
| 1 1 |      | F(n+1)  F(n)   |
|     |   =  |                |
| 1 0 |      | F(n)    F(n-1) |

Taking advantage of the fact that the matrix is always 2x2 we can compute the answer without a fully generic implementation of matrix chain multiplication.

type matrix [][]int

func qmatrix(n int) int {
    cache := make(map[int] matrix)
    return qmatrixInternal(n, cache)
}

func qmatrixInternal(n int, cache map[int] matrix) int {
    if n < 2 {
        return n
    }

    var q matrix
    q = append(q, []int{1,1})
    q = append(q, []int{1,0})
    fmt.Printf("%d %d\n%d %d\n", q[0][0], q[0][1], q[1][0], q[1][1])


    var matricies []matrix
    i := 0
    for n > 0 {
        exp := n & 0x1
        n = n >> 1
        pow := exp << uint(i)
        i += 1
        if exp != 0 {
            matricies = append(matricies, matrixPowerOfTwo(q, pow, cache))
        }
    }

    fmt.Println("%q\n", matricies)

    for len(matricies) > 1 {
        m1 := matricies[len(matricies)-1]
        matricies = matricies[:len(matricies)-1]
        m2 := matricies[len(matricies)-1]
        matricies = matricies[:len(matricies)-1]
        matricies = append(matricies, matrixMultiply(m1,m2))
    }
    return matricies[0][0][1]
}

func matrixMultiply(a, b matrix) matrix {
    c11 := a[0][0]*b[0][0] + a[0][1]*b[1][0]
    c12 := a[0][0]*b[0][1] + a[0][1]*b[1][1]
    c21 := a[1][0]*b[0][0] + a[1][1]*b[1][0]
    c22 := a[1][0]*b[0][1] + a[1][1]*b[1][1]
    var c matrix
    c = append(c, []int{c11, c12})
    c = append(c, []int{c21, c22})
    return c
}

func matrixPowerOfTwo(m matrix, p int, cache map[int] matrix) matrix {
    if p == 1 {
        return m
    }
    if val, ok := cache[p]; ok {
        return val
    }

    k := matrixPowerOfTwo(m, p/2, cache)
    res := matrixMultiply(k,k)
    cache[p] = res
    return res
}

All of the code samples in this post can be found at src.rampantmonkey.com/fibgo.

(Inspired by http://viccuad.me/blog/GPG-transition-statement/ and https://www.dennogumi.org/2015/06/gpg-transition-statement/)

The exact same text can be found at this location.

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA256

Sun 14 Jun 2015

For a number of reasons, I've recently set up a new OpenPGP key, and will be transitioning away from my old one.

The old key will continue to be valid for some time, but I prefer all future correspondence to come to the new one. I would also like this new key to be re-integrated into the web of trust. This message is signed by both keys to certify the transition.

The old key was:

pub   rsa4096/41DE81A9 2013-07-03
      Key fingerprint = 42E4 3543 BBC6 AC9B D99D  6E10 92A7 599A 41DE 81A9

And the new key is:

pub   rsa4096/D119CD2B 2015-06-14 [expires: 2016-06-13]
      Key fingerprint = 35BC BE03 CA63 87B5 2349  5EE0 BAD7 5204 D119 CD2B

To fetch the full key you can get it with:

  wget -q -O- http://rampantmonkey.com/gpg/caseyrobinson.public.gpg-key | gpg --import -

Or, to fetch my new key from a public key servery, you can simply do:

  gpg --keyserver pgp.mit.edu --recv-key D119CD2B

If you already know my old key,  you can now verify that the new key is signed by the old one:

  gpg --check-sigs D119CD2B

If you don't already know my old key, or you just want to be double extra paranoid, you can check the fingerprint against the one above:

  gpg --fingerprint D119CD2B

If you are satisfied that you've got the right key, and the UIDs match what you expect, I'd appreciate it if you would sign my key:

  gpg --sign-key D119CD2B

Lastly, if you could upload these signatures, I would appreciate it. You can either send me an email with the new signatures (if you have a functional MTA on your system):

  gpg --armor --export D119CD2B | mail -s 'OpenPGP Signatures' casey at rampantmonkey.com

Or you can just upload the signatures to a public keyserver directly:

  gpg --keyserver pgp.mit.edu --send-key D119CD2B

Please let me know if there is any trouble, and sorry for the inconvenience.

Regards,
  Casey Robinson


-----BEGIN PGP SIGNATURE-----
Version: GnuPG v2

iQEcBAEBCAAGBQJVfjzCAAoJEPpdmdoZJ3eMogYH/3RskhZ9JXEqDl+ncU6Igbfp
+12XIWLfrVQMfi57E/YTKfIiZjEFscZK0+/EXysmOCcmLaEhXuuEwlvQ4spYvgLN
d6/dNLgkm4+/Jnfs8sBCd4/vsZfREgGlJpk4kzOOlJZ3Vc80pb4Jv59lM4Tgo//4
XH2n3gT19/U/dKssAGMjxVDe9VnkynmmT0xtq12drwifwQEn34yTqK0RCxMaPI9b
JYPRXw2pLlOedgqnaf2rcCHdv8tDZcVEcnO2wxjW6/EbbLadfMgJg8+ThpurJt9/
J9kQ7DX0k1DVOgJ9ktuIdyJRku+2kpEVS34zNld5Q1Wg5A4LeRh7/yTGGfLf8Qs=
=yeEH
-----END PGP SIGNATURE-----

Two factor authentication has become commonplace amongst the multitude of web services I use on a daily basis. The goal of two factor authentication is to increase security by requiring two pieces of information to authorize yourself. First you use the traditional username/password combination to establish identity. Then you use a second, time sensitive code. This code is delivered by text message or generated by using an authenticator application.

To amuse myself, and reduce my dependence on my phone, I decided to implement my own one time password generator. Of course it will be a command line application implemented in go. Let's look at the most common application - Google Authenticator - for inspiration. This screenshot taken on my iPhone shows three accounts and their respective codes.1 Each account has a code and a countdown timer (shown as a circular progress meter). The goal: reproduce the same code and same timing for each account. google authenticator screenshot

The first step is to research the algorithm used. Wikipedia provides a brief overview and a link to the RFC (#6238). The algorithm used is called Time OTP, or TOTP. TOTP takes one input, a secret string.2 The secret string is then hashed3 with the current unix time4. The output is then truncated, modded, and padded to return a 6 digit code. That covers the criteria for generating a single code. What about one for every site?

Run the algorithm multiple times - once for each site. Done. Well, not quite. We want to display the time remaining for each code in place to avoid scrolling. The terminal provides a mechanism for this exact scenario - escape codes.

Terminal escape codes are a string of characters, from stdout, that are interpreted by the terminal as behavior rather than displayed to the user. For example, coloring text can be done with terminal escape codes. echo "this is \x1b[0;32mgreen\x1b[0m text"5 Aside from color, and more relevant to this project, are the collection of escape codes for moving the cursor and clearing text. Two are of particular interest - move cursor up (\0x1b[A) and clear current line(\0x1b[2k).6

Every half second I clear the output and redraw7. After a draw the cursor sits at the beginning of the next line. To clear the output move the cursor up and clear the current line. Repeat len(sites) times.

Since TOTP is time sensitive a token generator can be frustrating to debug. Essentially, the clocks have to be in sync on both the server side and the authenticator application side. Otherwise, the tokens would not match and login would fail. A handy tool for this (at least on linux) is NTP8. In my case the clocks were out of sync by 40 seconds. This was the most frustrating part. Since the time difference was only slightly longer than the token lifetime I would occasionally see correct tokens further back in the output9. Long story short, time is hard.

When I started this project I only expected to learn about a hash function. NTP, base32 encoding, and terminal escape codes are three tools that were previously mysterious but crucial to implementing onetime. Overall, I would call it a success. There are still many areas to explore in the future (profiling memory usage, cross platform testing, output to file instead of terminal, ...).


  1. Don't worry, they are generated from old secrets. No security issue here. 

  2. The secret is encoded in base32. Some sites (looking at you Hover) decide to provide a key with an odd number of characters. be sure to pad it with '='. 

  3. Google Authenticator uses HMAC-SHA1

  4. Well, the time is computed as number of 30 second periods since the Unix Epoch for UI. It would be hard to copy and paste if the code was valid for only one second. 

  5. Run it in a VT/100 compatible terminal. 

  6. \0x1b is the hex literal for ESC (keycode 27). 

  7. Half second redraw time instead of second to reduce timing inaccuracies. 

  8. This protocol is on the implementation list. 

  9. This was ultimately the clue to fixing it.