Furious Coder

There is a certain pain that comes with picking up an abandoned project.  The code must be scoured to determine what was implemented and what remains to write.  The design must be reevaluated, and the notes must be located, read, and understood.  Most importantly, however, the correct version must be picked up and modified, which is important if one installed a source version control system immediately prior to dropping the project, and this caused the project to be located in a new directory.  Otherwise, valuable time can be wasted wondering why the code one is clearly editing is not actually compiling the way one expects it would, when in fact the code editor is using the mixed files from both the new and old location because the developer was carelessly mixing "open recent" and "open file from location that one believes is recent, but is actually stale".

Also, when the free version control client crashes, the updated version must be installed.

These are fun times in independent software development.

Also, I really like Fog Creek's new office.

I'm going to write a rather long winded entry about the Microsoft Texas Hold'Em Game that I worked on several years ago, as it's come to my attention that there's some confusion over whether or not the game is "rigged" in some way to allow certain players an advantage or disadvantage.  While, for obvious reasons, I'm not able to post the actual source code that we use, I will try to be as technically specific as possible (within reason), and explain the methodologies and rationale that goes into a computer game with a random chance factor.  If you're looking for the short and simple, I'm going to explain how we use fair and random algorithms to ensure good unpredictable shuffles of cards, that we don't cheat or give players an advantage because it would be extra work and would ruin our business relationships as well as our player perception, and finally to reinforce point two, if we were to put cheating into our games, how we would have to do it and all the problems it would cause, technically, financially, and for our business.

Part 1: The Technology of a Fair Shuffle

Shuffling a virtual deck of cards by computer is a process that is meant to simulate the more-or-less random act of shuffling actual cards by hand.  The intent is that a person will have a deck of cards in an order that cannot be discerned by any player, and thus puts everyone on equal footing.  In the real world, this is fairly easy.  You pick up some cards, spread them around on the table and push them back together, riffle them, cut them, riffle them again a few times, and you're good.  Maybe when you riffle the cards, one flies out, and so you shove it back in.  That's some good randomness.  The cards also don't alternate perfectly.  More randomness.  There are lots of little "mistakes" that help ensure that the cards wind up in a reasonably unknown order before the first card is dealt.  In the computer world, however, it's a little more difficult.

Part of the problem is that computers are deterministic.  They follow precise steps in a precise order, which is what keeps software running in a predictable manner, and ensures that every time you press the "okay" button, for example, a dialog will close, or whatever is supposed to happen, happens.  This makes randomness difficult.

One way to get randomness into a computer is to use an external true random source.  One could hook up a Geiger Counter to a radioactive source, and count the time between emissions from decaying atoms.  Or a webcam could be pointed at a lava lamp, and the image analyzed to produce random numbers.  Some high end CPUs and motherboards have special analog diodes on them that vary in a highly random manner, and these can be used to generate random numbers.  All these methods, however, are expensive, impractical, and in some cases, dangerous.  Thus, we tend to use what are called Pseudo-Random Number Generators, or PRNGs.

What is a PRNG?  It is an algorithm, or computational process, that produces numbers that look random, and have reasonable values for tests of randomness, but are not truly random.  I'll give an example of a poor PRNG, which is defined by this formula:

NextValue = (PreviousValue + 7) Modulo 11

This Very Bad PRNG produces "random" values between 0 and 10 inclusive.  At each step, we take the previous output from the PRNG, and we add 7 to it, then we modulo the result by 11.  It's interesting to note that both 7 and 11 are Prime Numbers.  Here is some sample output of the Very Bad PRNG:

0, 7, 3, 10, 6, 2, 9, 5, 1, 8, 4, 0, 7, 3, 10...

These numbers start out looking pretty random, except that once you get a few numbers in you notice that the pattern repeats once we get back to 0, after eleven numbers.  That means this algorithm has a period of 11.  You also notice that individual numbers never repeat before the whole pattern repeats.  Finally, if you know the formula, you can figure out what the next number will be if you know the current number.  This is not a very good PRNG at all.

Texas Hold'Em uses a very good PRNG called the Mersenne Twister algorithm.  I won't describe the algorithm in detail here, although there is code available online.  Mersenne Twister has much better properties than my Very Bad PRNG above.  First of all, Mersenne Twister has a period of 2¹⁹⁹³⁷ − 1 (approximately 4.315425 × 10⁶⁰⁰¹ , that is 4 with over six thousand zeroes after it).  The pattern won't repeat until it's gone through this many output numbers.  Next, unlike my poor example above, you can't predict the next number by looking at the current one.  Mersenne Twister requires that you look at over 600 consecutive outputs in order to be able to accurately predict the next.  Finally, since it outputs 32-bit numbers, that is numbers equal to 2³² − 1 or less (0 through 4,294,267,295), you can bet it repeats the same numbers several times before it runs through it's period.

Mersenne Twister is a very good PRNG for free online gaming.  It's stable, it's well understood, and it produces numbers that are highly random.  (It's bad for Cryptography, but that's okay, we're not using it for that, and the reasons why are too complex for this article.)

It also is easy to configure with a good seed value, which is the initial value to configure the PRNG.  In the Very Bad PRNG above, we used 0.  Obviously, if we always used the same start value, the series of output values that followed would always be the same, and that would be bad.  Thus, we use a super-precise clock value, combined with another secret value, to seed our PRNG at the start of every game.  This means that every single game of Texas Hold'Em starts with a different initial value, so that the card shuffles will be unpredictable.  It also means that no one can start up their own PRNG to try to simulate ours, because their clocks will almost certainly be out of sync to the required degree of precision, and they don't know the secret number nor how we combine it with the clock to start up our PRNG.  (We actually use a combination of date and time, so every moment of every day produces a different seed.)

But what about those cards, and the way they're shuffled?  The deck starts out as a sorted pile of 52 cards, with the Ace of Spades on the top and the 2 of Clubs on the bottom.  We use a substitution shuffle, which steps through every card in the deck and swaps it's position with another card in the deck whose position is determined by the Mersenne Twister PRNG.  Computationally, this is very efficient, because it means we only have to do 52 swaps to ensure that every card is in a different position.  These swaps are done out of sight of the players, each swap consumes another value from the PRNG.  Since the players will, at most, only see 21 cards face up on the board (if everyone turns their cards over and plays to the river), the players are not exposed to 52 consecutive output values from the PRNG, thus preventing them from gathering the required 600+ values to predict the next shuffle.

When the next shuffle comes around, we don't just reshuffle the whole deck from the previous order.  Cards are actually pulled off the deck when they are dealt to players, and muck cards and burn cards are kept in a separate internal muck pile.  At the end of the round, this muck pile is added back to the original deck, just like in a real poker game, and this sets up a new initial deck order before the next shuffle is performed.  Thus, the actions of the players, what order they fold, and how far the round goes, actually adds even more randomness into each shuffle.

Finally, the PRNG is used outside of the deck shuffling, by the AI algorithm to add some randomness to their decision making, and to how much they will bet, as well as for the initial placement of the button at the start of the game.  This results in each shuffle of the deck being very very random, and thus not biased in any way.

Closing out on the technological side, I want to explain that while the shuffles are random and fair, as I've hopefully explained, they are also compartmentalized from other parts of the software.  Texas Hold'Em uses a methodology called Object Oriented Programming.  This is a way of writing code so that different components of the game know how to do different things that make sense for that component, and not much else.  For example, the deck of cards can be shuffled, a card can be drawn from the top, and a card can be placed on the top.  That's pretty much it.  Players can accept a card given to them (they do this twice at the beginning of the round), fold a card they have, and bet an amount of money (which can be zero so they can check).  And that's pretty much it for players.  The hand evaluator can look at a list of cards and tell what the best hand those cards make is, but that's all it can do.

You'll notice that nowhere in these different components is there code to reorder the deck in a specific fashion, or to change the value of a card.  Players can't request specific cards, they can only accept a card handed to them, and that card has to come from the top of the deck.  From a coding and testing standpoint, this is very good because it means the code is easier to read, write, and test.  From a fairness standpoint, it means that there's no way a certain player could be given specific cards, or that the software could dole out cards in a specific order to the advantage or disadvantage of any player.  All it can do is shuffle and deal, evaluate, collect, reshuffle, and deal again.  And that's why a serious analysis of Texas Hold'Em will show a random distribution of cards from random shuffles, and no advantage or "rigging" for any players.

Part 2: Why Don't We Cheat?

The short of it is that cheating or providing an unfair advantage would be terrible for our business.  Our players expect a fair, even game when they come to the MSN Games website, whether that game is Texas Hold'Em or Backgammon or Dominos.  If our games were unfair in any way, we'd lose business, we'd lose players who felt slighted, and our reputation would be tarnished.  If we lose business, we lose sponsors and advertisers, and that means we lose money.  It is in our best interest to present games that are fair and even handed for everyone, especially when these games are tried and true titles like Poker, where people have an expectation of fairness and of non-rigged gaming.

If we did cheat, it would be obvious very quickly.  A bad random number generator would display terrible patterns in the cards that were dealt, and a solid statistical analysis would reveal these patterns.  Players who were wise to this would skew their scores toward the high end, and we would see a terrible distribution of scores.  Players who did poorly would leave for other gaming sites, and we would lose the ability to create new games and titles because every future release would be suspect.

We also don't cheat because to cheat would be an incredible amount of work.  Getting these games running to the quality bar that is expected by our players is a true trial of solid engineering.  Texas Hold'Em alone took about a year to develop and test, and a large portion of that was spent ensuring that the game played Poker properly.  After spending all that time getting a solid experience, to then go and add code that would give certain players an advantage or disadvantage would be more time spent that could not be spent on other projects, not to mention extensive testing to ensure that these changes didn't break the "right way of playing" in the game.  It's simply not worth it to make games that are unfair.  It's a waste of time and manpower, and it gains us nothing with the potential to cost us everything.

Finally, what about a "malicious agent" who goes and changes the game after it's released?  First of all, Texas Hold'Em is actually a pretty big game.  Only two developers and two testers (of the original team of nine) are still with the company, and only one of those people is still on the Casual Games team.  Of those four people with familiarity of the software, only that one person still has access to the underlying code to the game, and he has been too busy with other projects to spend time playing around with it.  Finally, no one person can alter a game and release it to the world.  We have a complex process of review, testing, and release management that requires that several people view and sign off on any changes to any game that is released.  This is as much to ensure high quality, stable games as it is to prevent exactly this kind of messing with the fairness of any game.  It would take a concerted conspiracy of people to perpetrate this kind of fraud, and I assure you, we all have better things to work on, and a bigger vision to accomplish: Making great games that people love to play!

Thus, it is in no one's interest to produce a game that is rigged or unfair in any way.

Part 3: What Exactly Would It Take?

Okay, let's say that someone did want to make Texas Hold'Em a "rigged" game?  What would that take?

That depends on what how they'd want to rig it.  We could make a game that was biased towards particular usernames.  However, we couldn't put those names right in the game code itself.  What if we wanted to change who got favor?   To change it, we'd have to change the code and go through the whole release process every time.  That's complicated, and requires the review and release process listed above.  No, a better way would be to have an external list that was read every time the game started up, a list outside the code in a separate file.  But this introduces complexity.  What if the file is missing?  We'd have to test that the game ran normally if it couldn't find the list.  What if usernames were misspelled?  We'd have to test for that.  What if a user didn't exist or was deleted?  We'd have to test for that.  What if anyone could access this file?  That's a security risk, and we could have malicious people changing this list for their own ends.  Then what?  This whole scenario becomes a giant nightmare of more test cases and insecure software.  It's completely unacceptable.

Let's say instead we wanted to bias by people's scores.  Higher scores go higher, and lower scores go lower.  That's fine, but where do these scores come from?  We don't pass score information into the game, so we'd have to add in more code to accept and process these scores.  Then how do we decide what constitutes high and low?  We'd need an average, a midpoint from which to base that bias, and that requires processing the entire list of scores on a regular basis to recalculate the average.  How often do we do that?  Do we do it on the servers?  We'd have to.  Doesn't that take up processing power that could be used for other things?  Yes.  Isn't that wasteful?  You bet.  The end result here would be polarization of scores, with no normal distribution, a waste of server processing, more bugs, more testing, it would be obvious, and again, unacceptable.

What about the actual cheating code?  We'd need to know who to give good cards to and who to give bad cards to.  This means our card deck would need more than shuffle, give card, and take card.  We'd want to order the deck in a specific manner, ideally to give everyone pretty good hands, but the one person we want to favor the best hand of all.  This means that the hand evaluator has to talk to the player list, and figure out what order they get cards in, then sort the deck specially so that players A and B get Full Houses, but player C gets a Straight Flush.  The code path to do this would be glaringly obvious to anyone who worked on the game, and this too would introduce a slew of potential bugs.  How could we test that it didn't give the wrong player the best hand?  What conspiracy of collaboration would be required to get this through the entire release process?  How would Object Oriented Programming be broken by all this interrelated collaboratively cheating code?  It would be a mess, and it would take months to code correctly, test, and release properly.  Months that could be spent making another fair game that would be played and enjoyed by thousands, and which wouldn't jeopardize our good name.  And for what?  So a small group could claim they had a higher bragging score than another, larger group?  In short, it would be a complete waste of time and would benefit no one.

Conclusion

Professional Software Development is actually a very rigorous, difficult task.  Generating code that is fair, functions correctly, and produces a game that is enjoyable is actually a difficult enough task.  It consumes time and resources, and the eventual intended payoff is a population that enjoys the game and business relationships that generate revenue.  Every moment not focused on that goal is time wasted, and a potential negative reaction from the players and partners we should be making happy.

I know there are some people who will always think that the system is rigged.  However, I have never once participated in creating software that intentionally slighted any player, nor have I ever seen a coworker do the same.  In the end, writing fun, fair games is what I enjoy, and doing so consumes the majority of my work time.  (The rest is spent in meetings.)  I stake my integrity and reputation on my serious and disciplined focus towards producing quality software.

I hope that people enjoy the games we write, and I hope that this has provided some insight into the complexity behind the games you play, and demonstrated why the games I've made at Microsoft are always fair and even handed, and hopefully fun for many many people.

I'm using the term "year" loosely, since I'd like to go back to October of 2007 here, but the past twelve months have displayed a resurgence in high quality, lower production budget games that are build by small teams (or individual developers), and are playable in a matter of hours rather than weeks.

Portal: The highest profile small game of the last twelve months, this student project from Digipen was reimagined by the very same students under the watchful tutelage of Valve Software.  What emerged is a unique, fun, polished work of first-person puzzle gaming, with an unforgettable antagonist and a catchy theme song.  While benefiting from the team at Valve, the initial shell for the game started small, and the final experience is tight, polished, and an unforgettable title from the last year.

Braid: One developer, one artist, licensed music, a profoundly deep story, time-puzzle based gameplay, and perhaps the most uniquely satisfying game available this year on XBox Live Arcade.  Braid is refreshingly unlike any other title on the market, and the underlying story subtly changes your perception without relying on a Fight Club style plot twist.  This is a must have for any gamer, and I find myself still puzzling over the true meaning of the plot, which nicely references Infocom's Trinity, itself more artistic literature than game.

Multiwinia: The lads at Introversion have put out another blast of a title, this time a multiplayer take on their stylized lo-rez masterpiece Darwinia.  With five new game modes and the same weirdly beautiful art style as it's kin, this game is deceptively difficult despite it's simplicity.  A nice way to kill five minutes or two hours, thanks to four guys from England.

Fable Pub Games:  I feel compelled to place this title here since my former small team at Microsoft Casual Games created it.  While, like all successful casinos, it's a money losing racket in the long term, the level of polish and the tie-in with Fable II makes this a neat way to immerse yourself in the game world whenever you have time to kill while waiting for the full title to come out.  It also captures the casino feel better and in a more seamless way than any other console game I've seen in a while.

Anchorhead: I would feel remiss if I didn't mention at least one Interactive Fiction title on this list.  I honestly haven't played Anchorhead yet, but all the reviews have placed it near the top of the all-time greats, so I'll have to get to it very soon.  It's great to hear that the IF community is still producing quality work, even if, as a genre, it continues to slip beneath the radar of the gaming community at large.

The keys to these games, of course, are that I would rather play any of these over and over than most new "blockbuster" titles that are being released.  I haven't picked up Spore, for example, although the word on the street is that it both succeeds and fails in exactly the ways I had predicted it to.  I honestly can't name another high visibility title I'm looking forward to this year.  And perhaps that's part of the charm of the small game.  By arriving almost unannounced, held up like a craftsman work of art rather than a mass-produced dish that's been stewed and seasoned and refined over time to achieve maximum bland appeal to the greatest possible audience (the very reason I don't eat at The Cheesecake Factory), these games stand out like Italian mopeds at a Harley convention.  They're great in their own fashion, beautiful to behold, and yes, they're small, but they're just a blast to take out for a spin.

Some thoughts on Interactive Fiction and game authoring:

• Story is important.  Like really really important.  I couldn't tell you the story, in detail, of Doom 3, or countless other games I've played.  Nor can I think of any interesting stores that I've "made up" while playing sandbox games like SimCity.  However, I can recite in a second a bunch of mostly inferred backstory and the main plots of Portal, Half Life 2, Braid, the entire Homeworld series, and almost any Interactive Fiction game I've played.  These things stick with a player.  They become part of our subconscious, and every location, every twist and turn of plot from a really great story is burned into our memories, guiding our future actions.  We come back to them from time to time, and that is a display of the power of a truly great author, that they can continue to shape our lives long after we have stepped away from the tale they wove.
• If I ever start my own IF company, I'm going to make sure to hire people who are authors first, and coders second.  Clearly, coding ability is important, but it becomes more and more obvious that writing code (especially Inform) is a skill that can be quickly learned, and mastery of coding is not as important as the ability to craft the written word into a gripping and immersive experience.  I find this with my day job, that the people I enjoyed working with the most were passionate about the games and the play, even if they were imperfect at the execution.  They learned and improved on the rote skills, but the passion for the creative (as long as it was grounded in sanity) was something that couldn't be taught.  Those who viewed every challenge as a technical one, to be tackled via brute force and algorithms, they will almost certainly have no place among the writers of IF.  That's fine.  There are databases and engines aplenty for them to tinker with.
• The talking is not as important as the doing.  I find there is a lot of discussion, but even among those who are vocal (and those who are nearly silent), it is those who produce actual games that are the most revered.  Creation of content is everything, and we must focus our efforts on continually producing, with just enough promoting and networking to expand our markets and expose ourselves to potential players.  Even so, every word, post, and action will reflect upon us.  Let us be professional, yet engaging, in our appearance, and let that appearance be scarce because we spend lots of time creating!
• There's no way I'm going to finish Suspension in time for this year's IF Comp.  Just no way.  It's too big and there's too much left to do.  I should already be in the playtesting phase, and I'm not even complete with 20% of the gameplay.  Perhaps next year.

That's all for now.  Off to write code!

I just finished reading Chris Crawford's "on Interactive Storytelling", which was more of an interesting insight into his thoughts on the game industry than an eye-opening exploration of bold new ground for me.

Interactive Storytelling is one of several books I picked up to familiarize myself with the current state of thinking on fiction and story in computer games, and the first of those I decided to read.  Right off the bat, it mixes interesting insights (stories are, at their core, about people, not things) with derisive comments about game developers and artists.  Crawford demolishes a series of established methods for leading players down a path as too limiting and as ultimately scripted or linear storytelling, and then later in the book reestablishes similar methods for keeping players on track, hand waving away the fact that he dismissed the very same methods chapters before.  This was disturbing, but not as disturbing as the glaringly inaccurate technical statements about how many possible states there are in Pac Man, or calculating the ratio of an icons physical dimensions to the number of possible meanings that icon can represent (one cannot eat "every other dot" in Pac Man, nor does every possible combination of pixels in an icon represent a meaningful pictograph to a human being).

For those uninitiated with games development, however, it does provide an interesting overview of the technology required to represent interpersonal communication and interaction with simulated personalities.  There are some good discussions of grammar, representing moods and desires, tracking states and action histories, and overarching daemons that nudge and guide the story in certain directions.  The notions of abstraction were useful, and Crawford's comments on letting players make the "wrong choice" and then representing the results of that choice, rather than shooing the player away from "bad choices", are important lessons to learn (or relearn, as Nelson states essentially the same thing in the Craft of Adventure).  Finally, Crawford is absolutely right to state that more ambitious, story-driven interactive content has little hope of spreading via typical video-game storefronts and point-of-sale outlets, and that new avenues of mass-market exposure must be explored.

However, what Crawford aims for, although he doesn't explicitly state it, is to have an experience with all the interactive freedom of real life while providing an unscripted narrative and emergent story arc as deep and compelling as Romeo & Juliet.  I don't believe this is possible, because real life is not as deep and meaningful as the Bard's tales in any reasonably short time span.  Reality TV, a misnamed genre if ever there was one, claims to present as much drama with the freedom of the participants as the compelling factor, yet the open secret is that these events are heavily scripted, the contestants cajoled and nudged in the "right" direction, and the outcome edited into a compelling format.  Providing an entertaining (or at an extreme end, emotionally moving) experience is the result of careful crafting and guiding of the audience down a path over which the journey is the tale, and the ending or endings are designed to inspire a sense of achievement, introspection, or closure.

However, in many ways, we've already reached the goals of interactive entertainment that are emotionally moving, or that inspire a sense of awe on par with that of great theatre, novels, or fine movies.  It's just that these examples are few and far between.  The game Ico for the Playstation 2, for example, ties the players success to the Princess Yorda, driving a deep sense of loyalty, companionship, sadness, and accomplishment over the course of the game.  Relic's original Homeworld not only tugs at the heartstrings when the eponymous planet is razed, but explores the fanaticism of exiles lost mid-way, and empires bent on absolute control.  Within the genre of Interactive Fiction, of course we have Planetfall and Floyd (which Crawford derides as too scripted, ignoring his own suggestions pages before as to how to develop characters that push the players towards certain goals and emotions), as well as recent achievements such as Emily Short's Galatea, and the world of Slouching Towards Bedlam.  So what if the Interactive Fiction games are not vast open worlds where every character has nearly infinite emotional range?  So what if these titles intersperse storytelling moments with resource management or puzzle solving?  The emotional reaction in the player is the goal that counts, and their altered outlook on the real world is the lasting result of that experience.

It is true that the vast majority of electronic entertainment produced today is derivative and overly similar, with little to no compelling story or drama.  Yet, it is these existing shining gems that we should hold up as examples to admire and learn from as we move forward.  These titles expose us to deeper truths while providing an entertaining escape, and their limits are part of their freedom, guiding us in a safe manner down interesting paths away from the vast uncertain chaos of real life and towards a sense of accomplishment and joy.