Work the Shell

I admit it, my kids and I often find ourselves at the local arcade playing video games. There seems to be two basic types of arcades nowadays: those where you play to earn free games and get the high score, and those that are ticket-based where doing well on a game produces tickets that you cash in for cheesy tchotchkes or incredibly cheap stuffed animals.

We tend to go to the latter, and one of the games that's caught my attention is a video version of the popular TV show Deal or No Deal. It got me thinking about odds and probability and how these games actually work.

The game is incredibly simple: you're told that there is a range of prizes hidden in briefcases, and you choose which to eliminate and win what's left in the last briefcase. It's not too exciting, except as you go along, you're offered the opportunity to take a specific cash prize instead of continuing the game.

On the TV show, there are 26 cases, and the prizes range from $0.01 to $1,000,000.00 in uneven jumps. Attractive models hold each case, and the game typically proceeds where the player guesses a bunch of cases to eliminate, in clusters. If the eliminated cases have low-value prizes, that's good—there is, therefore, a better chance of winning big bucks. If they have high-value prizes inside, well, that's not good.

After each set of cases is eliminated, the house offers the player a “deal” to stop playing the game—a payoff that's worth more than the lowest unidentified prize but obviously lower than the highest unidentified prize.

The prizes are 0.01, 1, 5, 10, 25, 50, 75, 100, 200, 300, 400, 500 and 750, and then the big values: 1,000, 5,000, 10,000, 25,000, 50,000, 75,000, 100,000, 200,000, 300,000, 400,000, 500,000, 750,000 and 1,000,000.

Calculating the average payout, assuming you have an equal chance of picking each of the cases at the beginning of the game, is easy: add them up and divide by 26. The result is 131,477.54. If they offered me $130k instead of playing the game? Even though it's a bit lower than the average expected payout, I'd take it. Deal!

Let's say we're most of the way through the game though, and 20 of the possible prizes are knocked out. What's left are 0.01, 50, 300, 1,000 and 250,000. Your chance of picking the 250,000 prize case? One in five.

The expected payout is $50,270, and if that's what you're offered, it's significantly better than four of the five possible outcomes you face. My advice? Deal!

It turns out that there's some sort of random factor that's thrown in to the “deal”, so in the game itself, they vary up or down a percentile value.

To experiment with this as a shell script (yeah, it only took me half the column to get to my first line of code), we need to work with arrays—something that's frankly a bit confusing. Here's how we could define the 26 briefcases:

declare -a cases=(0.01 1 5 10 25 50 75 100 200 300 400 500 750
1000 5000 10000 25000 50000 75000 100000 200000 300000 400000
500000 750000 1000000)

This might be the first time you've seen the declare statement in the shell. In this case, the -a flag declares the variable as being an array. Its usage, however, is not mandatory—arrays can be implicitly declared simply by using the array assignment syntax (a list of values inside parentheses).

You reference individual array elements with $var[index], but there's a twist because of how the shell parses content. What you need to do is actually wrap it with curly braces: ${var[index]}. Add a #, and you get the number of elements in the array, like this:

echo Total number of array elements is ${#cases[*]}

The value that'll be printed is 26, just what we want for Deal or No Deal. To see value #11, you could use ${cases[11]}, but that's wrong. Why? Because shell arrays are indexed starting at zero, so case #11 is actually ${cases[10]}, which, yeah, is pretty confusing.

Let's start by writing the snippet that can calculate expected payout before you have picked a single briefcase out of the collection:

for (( val=0 ; $val < ${#cases[*]} ; val+=1 )) ; do

    sum=$(( $sum+${cases[$val]} ))

done

echo sum = $sum, payout = $(( $sum / ${#cases[*]} ))

The bad news? It turns out that the 0.01 value really messes things up, as we can't do integer math with a non-integer value. So, because the 0.01 value actually proves not to influence things much, I'm going to replace it with the value 0. Here's the output:

sum = 3418416, payout = 131477

That's reasonably accurate. Our earlier calculation was 131,477.54. Close enough for gaming work!

Now, let's randomly pick out 22 of the cases, calculate the expected payout and offer a “deal” versus the values still remaining.

First, pick out some cases:

for (( picked=1 ; $picked <= 22 ; )) ; do

  pick=$(( RANDOM % 26 ))

  if [ ${cases[$pick]} -ne -1 ] ; then

    cases[$pick]=-1

    picked=$(( $picked + 1 ))

  fi

done

That gets all but four cases out of the game by setting their value to -1 (remembering that we're using 0 to represent $0.01). To see what's left in the game and calculate the expected payout of only the remaining values, do this:

for (( val=0 ; $val < ${#cases[*]} ; val+=1 )) ; do

  if [ ${cases[$val]} -ne -1 ] ; then

    echo \(Still in the game: a prize \

      worth \$${cases[$val]}\)

    sum=$(( $sum+${cases[$val]} ))

    cnt=$(( $cnt+1 ))

  fi

done

echo Win \$$(( $sum / $cnt )) if you stop. \

     Deal, or no deal\?

exit 0

Run the code, and here's a sample output:

(Still in the game: a prize worth $50)

(Still in the game: a prize worth $1000)

(Still in the game: a prize worth $5000)

(Still in the game: a prize worth $400000)

Win $101512 if you stop. Deal, or no deal?

Would you take the deal, or try for the $400,000 case?