Monthly Archives: December 2015

Is Your Server A Survivor?

Posted on by

Heavy ice storms have knocked out power throughout most of Oklahoma and left me thinking about emergency preparedness. Not for humans, mind you, but for machines. After all, in the web business uptime is everything and a customer living in California isn’t going to care or even realize that the reason your online store is down is because of heavy flooding in a data center halfway across the country.

So… Quiz Time! How many natural disasters could your server survive before your customers could no longer access your website and/or services?

Most professional hosting services have backup generators and battery arrays that keep things humming along without so much as a hiccup during even the worst of blackouts. And in 99% of the case that’s all you need.

But what about the other 1% of the time?

For instance, generators need fuel. What happens if that fuel runs out and deep snows or heavy flooding prevents you from bringing in more fuel to start them back up? How many hours or days could you server go without supplies before finally falling silent? Do you even know? (I don’t. Such shame.)

And what about your server’s physical safety? A backup generator won’t do you any good if an earthquake drops a steel girder right on top of your hardware or if a tornado blows your whole data center off to Oz.

Now obviously there comes a point where it’s no longer worth spending a bunch of money just to make your server 0.0001% more robust. There’s nothing wrong with shrugging your shoulders and saying, “If a meteor crashes into my server I’ll build a new one from backup and my customers will just have to deal with the downtime. If anybody complains I’ll send them a picture of the crater.”

And that’s perfectly fine. Nobody has ever died because they had to wait an extra day to order a funny t-shirt they found online.

Of course… people HAVE died because they had to wait an extra day for military communication. And a thirty second outage of financial data can make all sorts of people wish they were dead. So there are some industries where downtime is never OK.

Which means there are people working in those industries who get paid to sit around talking about how they plan to recover from simultaneous lightning strikes in five different states during a zombie apocalypse.

I’m… feeling a little career envy here.

Let’s Program A Prisoner’s Dilemma Part 2: Crime And Punishment

Posted on by

Last time we learned about a game theory thought experiment called the “Iterated Group Prisoner’s Dilemma”. Basically players get randomly paired up and have to decide to either cooperate by accepting a small penalty for themselves or defect by shoving a big penalty onto the other player. The players then get shuffled around and repeat the game with a new partner. After a few hundred rounds (or more) the game comes to a stop and the winner is whoever has lost the fewest points.

This time we’re going to start programing a simulator for that game so we can watch how different strategies play out.

I will be writing this project in Ruby. It’s not really “better” for this program than any of the various other high level languages we could choose from, but I’ve been using it a lot as part of my game programming hobby and figured I might as well stick with it while it was in my head.

So if you want to follow along with my exact code open up a file named prisonerdilemma.rb in your favorite text editor and get ready for some Ruby. Of course, rewriting the project in your favorite language is always an option.

Introducing Prisoner 24601

The most important part of the prisoner’s dilemma is the prisoners. So let’s make a list of what our little digital prisoners need to be able to do in order for this simulation to work.

1) They need to have a unique ID so that other prisoners (and us humans) can recognize them.

2) They need to be able to decide whether to cooperate or defect with other prisoners based on ID.

3) They need to be able to see whether their opponent decided to cooperate or defect.

4) They need to be able to report what strategy they are using so we can keep track of how different strategies perform.

5) They need to be able to keep track of their score so we can calculate who is winning and losing.

Based on all this I’ve thrown together a very simple prisoner class for us to start working with. It can’t really do much except book keeping though. It has variables to keep track of it’s own ID, score and strategy and even exposes the score to outside code so we can update it during the game. It also has a convenient “report” function that will print out all that information in human friendly format.

As for actual game playing code… it does technically have a “cooperate?” function for deciding how to play the game along with a “learnResults” function for keeping track of its opponents. But at the moment both of these functions are empty because this is just skeleton code; it isn’t meant to actually do anything. In fact, if you try to call the “cooperate?” function it will throw an error!

class Prisoner
   attr_reader :id, :strategy, :score
   attr_writer :score

   def initialize(id)
      @id = id;
      @score = 0;
      @strategy = "Prisoner Parent Class"
   end

   def cooperate?(opponentID)
      throw "Prisoner child class must implement a cooperate? method"
   end

   def learnResults(opponentID,oponentCooperated)
   end

   def report
      puts "ID: #{@id} Score: #{@score} Strategy: #{@strategy}"
   end
end

Still, even with two incomplete functions we can still give this a test run. If you were to add some code like this to your project:

testprisoner = Prisoner.new(6)
testprisoner.score = -10
testprisoner.report

You would get some output like this:

ID: 6 Score: -10 Strategy: Prisoner Parent Class

Ye Not Guilty – The “Saint” Strategy

Now that we’ve got a nice generic class up and running we can move on to writing a prisoner with actual dilemma solving code!

For our first attempt we’re going to be writing the simplest possible of all prisoner algorithms: A player who always always chooses to cooperate. We’ll be calling this the “Saint” strategy.

Now the actual code for this will be virtually identical to the generic prisoner. It will just have a different name inside of the “strategy” variable and its “cooperate” function will return true instead of throwing an error.

But we all know that copy pasting code is horrible and hard to maintain, so we’ll be using the miracle of inheritance to avoid any copy pasting.

class Saint < Prisoner
   def initialize(id)
      super(id)
      @strategy = "Saint"
   end

   def cooperate?(opponentID)
      return true
   end
end

That “Saint < Prisoner” tells the compiler that Saint is a type of Prisoner and should get a free copy of all of its code. Then instead of writing an entire new class from scratch we only have to write the few bits that are different.

First up we write a new initialize function so we can set the strategy variable to “Saint” instead of the default from the Prisoner class. But we still want the Prisoner class to handle things like setting our ID and initializing our score so we start out by calling the generic Prisoner initialize function with a call to “super”.

The super call checks whether the parent has a function with the same name as the current function and then calls it. It’s really useful for when you want a child function to do everything the parent did and then a little extra. Just start with super to get the parent’s behavior and then add in the unique child logic afterwards.

Next we write a new cooperate? function, which for our super trusting saint just involves returning “true”. In this case we want to completely override the parent’s version of the function so we leave out the call to super and just write new code.

Father of Lies

That was pretty easy, so let’s keep going by programming a second type of prisoner that perfectly mirrors our first. This time we’ll create a player that always always chooses to defect. Let’s call this the “Devil” strategy.

class Devil < Prisoner
   def initialize(id)
      super(id)
      @strategy = "Devil"
   end

   def cooperate?(opponentID)
      return false
   end
end

Just like with the “Saint” we use inheritance to grab our basic Prionser code and then just add in our new strategy name and cooperate? Algorithm. Couldn’t be easier.

A Not So Epic Clash Between Good And Evil

And now here’s a little code snippet you can use for testing that both of our new classes work:

testSaint = Saint.new(1)
testSaint.report
testDevil = Devil.new(2)
testDevil.report
puts "Saint Cooperates?"
puts testSaint.cooperate?(testDevil.id)
puts "Devil Cooperates?"
puts testDevil.cooperate?(testSaint.id)

Which results in this output:

ID: 1 Score: 0 Strategy: Saint

ID: 2 Score: 0 Strategy: Devil

Saint Cooperates?

true

Devil Cooperates?

False

Let’s Get Ready To Rumble

Now that we have some players assembled our next task will be setting up an actual game for them to play in. But that will have to wait until the next post.

Could Your Web App Survive A Transplant?

Posted on by

Sometimes you need to move your code off of the computer you wrote it for and onto some other machine. A buddy wants a copy of your random D&D dungeon generator. A co-worker needs a copy of the billing software you’ve been working on. A client wants you to move their inventory software to a new system.

And when you get a job like this it quickly becomes apparent that some programs are easier to move than others. A simple Java application can be tossed onto just about any machine and stand a good chance of automagically working while a complex piece of legacy code might be almost impossible to move due to dependency on obsolete libraries or bizarre hardware requirements*.

Now unfortunately for us web developers, online applications tend to be some of the harder pieces of software to move from one computer to another. In general it’s not enough to just have a copy of the code moved to the new machine; you also need a copy of the right database and server along with the proper database table definitions and server config instructions.

And that’s just the starting point. The older and more complex your web app is the higher the odds are that it has developed dependencies of certain URLs, IP addresses, third party data feeds, server libraries and so on. At that point you’re no longer trying to move an application, you’re trying to relocate an entire digital ecosystem.

But I’m Never Ever Going To Move My Web App To A Different Computer

Now at this point you might be thinking to yourself “But Scott, web apps don’t need to move. You just install them on your server and let other people visit them through the Internet. That’s the whole point.”

And for the most part that’s true. If your web app runs properly on its current server it doesn’t really matter how hard or easy it would be to get a second copy of your web app running on a different server with a different URL.

Until one day you find out your website is so popular that it’s starting to slow down and you need to create a second copy and load balance between the two.

Or maybe someone offers to pay you a bunch of money to build a copy of your web app for their business.

Or maybe you find out you need a bunch of risky new features and you want to create a test server to run your changes on before you update the main server.

Or maybe you finally get enough funding to hire a second developer and now he needs to know how to set up a local copy of your online web app so he can start experimenting without taking down half your live database.

Take your pick. There are plenty of reasons that a complex website that you thought would always run on just one machine with just one URL might suddenly need to be split across multiple computers with various different access methods.

Oh No! How Do I Prevent This From Ruining My Web App?

Fortunately, there are ways to make your online applications easier to move and copy.

Probably the most important tip is: Avoid hard coding resource locations.

Hard coding the IP address of your database straight into your code will result in all sorts of headaches when some new developer comes along and wants to connect to localhost or a test database instead. Similarly hard coding the location of libraries (ex: /home/bob/businessapp/library/coolstuff.php) can lead to extreme frustration if your app ever ends up installed in a different location or even on a different operating system. You’ll wind up being forced to hunt down and replace dozens or hundreds of file references with new locations that match the new machine.

The fix for this is to store environment specific data like code paths and database connection credentials in some sort of variable instead.

//BAD! This will make it really hard to run this code on a different machine or OS
include('/home/bob/businessapp/library/coolstuff.php');
include('/home/bob/businessapp/library/importantstuff.php');

//BETTER! Now we can adapt this code to new machines by changing just one variable
$libraryPath = '/home/bob/businessapp/library/';
include($libraryPath.'coolstuff.php');
include($libraryPath.'importantstuff.php');

But where should you declare these environment specific variables?

Your first instinct might be to just store them in the same file where they are used. Put the database variables at the top of your database connection script or your library path at the top of the file that loads up all the support code for your framework.

But mixing up environment variables and code can be dangerous.

For instance, imagine you send your buddy a copy of your web app and teach him how to customize the connection information in the database file “database.php”. Then a few months later you find a bug in that code and have to send him an updated copy. He deletes his broken “database.php”, loads the new one and suddenly nothing works because deleting the old “database.php” file also deleted the customi connection information that pointed to his database.

But what if you instead had two files: a “database_connect.php” file that has the actual database logic and a “database_config.php” file that just holds a few variables for database location and authentication. You give your friend a copy of both and show him how to update “database_config.php”. A few months later you find an error in the logic of “database_connect.php” and send him an update. This time everything works perfectly because replacing the broken “database_connect.php” file had no impact on the customized variables your friend had entered into “database_config.php”.

This is the basic idea behind config files. Sometimes they’re text files holding values for the code to read. Other times they are actual code files filled with static variables. But no matter how they are written the goal is the same: to create a file that will never be overwritten by bug fixes or feature updates; a safe place for keeping track of machine and user specific information.

Keep that in mind when designing your next major web app and you should hopefully find yourself in a situation where copying or duplicating your program is as easy as copying some code and updating a few config files. And doesn’t that sound like a lot more fun than trying to manually find and replace dozens of hard coded references that keep trying to overwrite each other every time you install an update?

 

*  Example: Sometimes software, especially in embedded systems, keeps track of time by counting processor cycles. As you can imagine a program that thinks one second is equal to one million processor cycles will start acting really weird if you give it a processor that runs several times faster than that.

Let’s Program A Prisoner’s Dilemma Part 1: Game Theory Is Less Fun Than It Sounds

Posted on by

A Different Kind Of Gaming

Game Theory, despite the name, is unfortunately not “The study of videogames”. Instead it is the science of mathematically analyzing how decisions are made.

The reason it’s called game theory is because one popular way to analyze real world decision making is to come up with a simplistic “game” that mimics the core dynamic of the real world problem. The game can then be mathematically analyzed and the results applied back to the more complex real world situation.

For instance, a game theorist studying crime might come up with a “game” where people who follow the law get 1 point and people who break the law have a chance of gaining two points but also a chance of losing three points. He can then mathematically analyze how different risk levels influence whether or not crime is a winning strategy.

The Prisoner’s Dilemma

The most famous example of a game theory game is the “Prisoner’s Dilemma”. Two criminal are caught red-handed committing a small crime that will land them in jail for one year. The police also suspect the two criminals are guilty of a larger crime worth two years of jail time, but they don’t have enough evidence to prove it.

The police eventually come up with a plan to interview each criminal separately and offer them this deal: Testify about the other guy’s involvement in the larger crime and we’ll drop the current small charge against you.

And now here’s the “game”: As one of the prisoners do you protect your buddy and keep quiet even though it means going to jail for a year? Or do you tattle in hopes of going free? And how do you know whether or not you can trust the other guy? If he confesses you go to jail for an extra two years.

Other Guy Keeps Quiet Other Guy Confesses
You Keep Quiet You both go to jail for one year You go to jail for three years

Other guy goes free
You Confess You go free

Other guy goes to jail for three years

 You both go to jail for two years

Now as mathematicians we want to be able to analyze this choice with actual numbers, so let’s do a little game theorizing. Instead of two prisoners let’s imagine a two player game where each player is allowed to choose to either play nice and cooperate or to betray their partner and defect. If you cooperate you lose 1 point. If you defect the OTHER player loses 2 points.

Player B Cooperates Player B Defects
Player A Cooperates Player A: -1 point

Player B: -1 point

 Player A: -3 points

Player B: -0 points
Player A Defects Player A: -0 points

Player B: -3 points

 Player A: -2 points

Player B: -2 points

What makes this such an interesting game to study is the fact that the best group strategy and the best individual strategy are complete opposites.

As a group the obvious solution is for both players to cooperate so that between them they only lose 2 points. If one player defects the total loss jumps up to 3 points and if both players defect the total loss is 4 points, as bad as it gets.

But as an individual the equally obvious solution is to defect. After all, if you cooperate you are guaranteed to lose 1 point and might even lose 3 points if the other player defects. But if you yourself defect you might not lose any points and even if the other player defects you only lose 2. There is just no good reason to purposely give up one point.

So the smartest thing to do as an individual is to defect but the smartest thing to do as a group is to cooperate and there doesn’t seem to be any logical way to bridge the gap between these two strategies. Or is there?

Iterated Prisoner’s Dilemma

The core problem in the prisoners dilemma is the fact that it’s a one-time choice. You either cooperate or defect and a few seconds later you find out who won and who lost, end of story. This is why there is no logical reason not to betray the other player. If you defect you’re guaranteed to at least tie so why risk anything else?

But what if you had to play the game multiple times?

This could change things up. Now your decision to cooperate or defect might impact how future games are played. There is now a possibility to build or lose trust.

But sadly you can show that even with multiple games the best logical strategy is still to always defect. The logic goes like this:

1) During the last round you might as well defect since there are no more future rounds in which the other player could punish you.

2) Since a logical opponent will defect during the last round you might as well defect during the second to last round. It’s not like your opponent was going to cooperate in that last round anyways.

3) Since a logical opponent will defect during the second to last round you might as well defect during the third to last round…

4) Continue the pattern and you can see that always defecting is the best strategy.

There are only two ways to break out of this cycle.:

One is to have an infinite number of rounds so that players are always at risk of being punished in the future for bad behavior in the present. We’re not going to do that though for the simple reason that there is no way to run an infinite number of Prisoner’s Dilemmas on a finite computer.

The other way to break the cycle is to introduce more players.

Iterated Group Prisoner’s Dilemma

The iterated group prisoners dilemma works the same as the normal iterated prisoner dilemma except that you have several different players who get randomly paired up before every round.

This drastically changes the dynamics of the game.

In a two-player prisoner’s dilemma double defection is a “stable” strategy because it means neither player will get ahead of the other. You might be losing two points every round but the other guy is too so you aren’t actually losing.

But when there’s a group? Now a players who is constantly losing two points from double defection can end up falling behind other pairs of players who cooperate and thus only lose one point per round. Suddenly it’s not enough to try and figure out whether your current partner is going to cooperate or defect; you also have to worry about whether other players in other matches are cooperating or defecting.

Interesting… But Is It Useful?

The Iterated Group Prisoners Dilemma is not only mathematically interesting, it is highly relevant to real life. Ever day people are faced with scenarios where they can choose to either work together or try to cheat each other. In the long run it’s best for society when people work together but on an individual level exploiting others can provide huge short term benefits.

So by analyzing the prisoners dilemma we can get some interesting insights into why different societies work the way they do along with some ideas on what sort of ethical systems are and aren’t stable.

Of course, real life has all sorts of issues that aren’t fully reflected in a simple tool like the prisoners dilemma so don’t think it somehow has all the answers to all our problems. But it’s still better than nothing and at the very least provides a nice topic for small talk with other math geeks.

What Does Any Of This Have To Do With Programming?

As AI enthusiasts we are obviously very interested in writing programs that can make logical decisions, and the prisoners dilemma provides a great sandbox for practicing that skill. It’s simple enough of a scenario to be implemented in less than a page of code while still being complex enough to produce interesting results.

So here’s the plan for this Let’s Program: We’re going to write a Prisoner’s Dilemma simulation along with a few different types of players each with their own strategy for deciding when to cooperate and when to defect. We’ll then run a bunch of simulations and see if we can find any interesting trends.

Like usual this isn’t exactly an original idea. Game theorists have been writing and testing prisoners dilemma programs for years and if you’re familiar with their research you probably already know everything we’re going to cover in this Let’s Program.

But who cares? The goal here is to practice our programming, not push the cutting edge of computer science. And there’s bound to be at least one reader in my audience who isn’t already a game theory expert.

Actually, quick show of hands: Is there anyone here who has never studied game theory before reading this blog?

There, see? That guy over there is the reason we’re doing this. He’s about to learn something cool.

Open Worlds With Closed Plots

Posted on by

Open world games have become an incredibly popular genre and the industry has settled on a predictable formula for building them. You start by creating a decent sized world for the player to explore, usually a big city or a small country. You then fill that world with secrets to find, activities to do and optional mission to complete. You then finish up by introducing a series of connected, mandatory missions that work together to tell some sort of story.

Unfortunately, half the time the main story is the least entertaining part of the game.

Part of this is because open world games are hard to write for. Writers are used to linear stories where they can control what happens and when. Need tension? Put a bunch of tough challenges one right after another. Need urgency? Introduce a time limit. Want some relief? Tone down the enemies for a level or two.

But in an open world game? The pacing is all in the hands of the player. He might decide to follow along and do your “urgent” mission right away, or he might decide to spend five hours fishing and blow away whatever sense of dramatic tension you were trying to build. And while it is possible to write a story that makes sense regardless of whether it is done quickly or at a leisurely pace the truth is that most writers have yet to master the knack of producing such a flexible script.

But it’s not just story. There’s a real gameplay conflict between the freedom of the open world genre and the limits of mandatory plot missions. This leads to frustrated players who have gotten used to being able to pick and choose what they want to do and why only to suddenly find themselves forced into a specific type of gameplay or given a specific motivation they may or may not actually care about.

For instance, I spent most of my time in Watchdogs playing as the world’s sneakiest pacifist hacker and was rather annoyed when the game suddenly mandated that I murder several dozen mobsters in a literally explosive action scene. Sure, it was cool but that wasn’t how I wanted to play the game.

All of which makes me wonder… what if we built an open world game with no main plot? Just drop the player into the world, teach him what a sidequest marker looks like and then leave it completely up to him to pick and choose how to play the game. Don’t force a specific high-level goal on him or try to tell him what his character’s ultimate motivation is. Instead let every player blaze their own narrative into the world.

The Elder Scroll series and their Fallout cousins are actually pretty close to doing this. The main quest is already mechanically treated just like an extra big side quest and the manual is often eager to reassure you that nothing bad will happen if you decide to ignore the whole thing and go off and do your own thing instead. So why not go just one step further and drop that main quest entirely? Take the development time that would have gone into it to instead spice up as many of the side quests as possible.

Personally I think it’d be a blast.