Take It or Leave It: A Game Show for Computers

Question

Context:

A reclusive billionaire has created a game show to attract the world's best and brightest programmers. On Mondays at the stroke of midnight, he chooses one person from a pool of applicants to be the contestant of the week, and provides them with a game. You are this week's lucky contestant!

This week's game:

The host provides you with API access to a stack of 10,000 digital envelopes. These envelopes are randomly sorted, and contain within them a dollar value, between $1 and $10,000 (no two envelopes contain the same dollar value).

You have 3 commands at your disposal:

1. Read(): Read the dollar figure in the envelope at the top of the stack.

2. Take(): Add the dollar figure in the envelope to your game show wallet, and pop the envelope off the stack.

3. Pass(): Pop off the envelope on the top of the stack.

The Rules:

1. If you use Pass() on an envelope, the money within is lost forever.

2. If you use Take() on an envelope containing $X, from that point forward, you may never use Take() on an envelope containing < $X. Take() on one of these envelopes will add $0 to your wallet.

Write an algorithm that finishes the game with the maximal amount of money.

If you're writing a solution in Python, feel free to use this controller to test out algorithms, courtesy of @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

If you use the controller, you cannot access globals, you can only use the 3 provided API commands, and local scoped variables. (@Beta Decay)

Notes: "Maximal" in this case means the median value in your wallet after N > 50 runs. I expect, though I would love to be proven wrong, that the median value for a given algorithm will converge as N increases to infinity. Feel free to try to maximize the mean instead, but I have a feeling that the mean is more likely to be thrown off by a small N than the median is.

Edit: changed the number of envelopes to 10k for easier processing, and made Take() more explicit.

Edit 2: The prize condition has been removed, in light of this post on meta.

Current high scores:

PhiNotPi - $805,479

Reto Koradi - $803,960

Dennis - $770,272 (Revised)

Alex L. - $714,962 (Revised)

Answer 1

CJam, $87,143 $700,424 $720,327 $727,580 $770,272

{0:T:M;1e4:E,:)mr{RM>{RR(*MM)*-E0.032*220+R*<{ERM--:E;R:MT+:T;}{E(:E;}?}&}fRT}
[easi*]$easi2/=N

This program simulates the entire game multiple times and calculates the median.

How to run

I've scored my submission by doing 100,001 test runs:

$ time java -jar cjam-0.6.5.jar take-it-or-leave-it.cjam 100001
770272

real    5m7.721s
user    5m15.334s
sys     0m0.570s

Approach

For each envelope, we do the following:

• Estimate the amount of money that will inevitably be lost by taking the envelope.

  If R is the content and M is the maximum that has been taken, the amount can be estimated as R(R-1)/2 - M(M+1)/2, which gives the money all envelopes with contents X in the interval (M,R) contain.

  If no envelopes had been passed yet, the estimation would be perfect.

• Calculate the amount of money that will inevitably be lost by passing the envelope.

  This is simply the money the envelope contains.

• Check if the quotient of both is less than 110 + 0.016E, where E is the number of remaining envelopes (not counting envelopes that cannot be taken anymore).

  If so, take. Otherwise, pass.

Answer 2

Python, $680,646 $714,962

f = (float(len(stack)) / 10000)
step = 160
if f<0.5: step = 125
if f>0.9: step = 190
if read() < max_taken + step:
    take()
else:
    passe()

Takes larger and larger amounts in steps of size between $125 and $190. Ran with N=10,000 and got a median of $714962. These step sizes came from trial and error and are certainly not optimal.

The full code, including a modified version of @Maltysen's controller which prints a bar chart while it runs:

import random
N = 10000


def init_game():
    global stack, wallet, max_taken
    stack = list(range(1, 10001))
    random.shuffle(stack)
    wallet = max_taken = 0

def read():
    return stack[0]

def take():
    global wallet, max_taken
    amount = stack.pop(0)
    if amount > max_taken:
        wallet += amount
        max_taken = amount

def passe():
    stack.pop(0)

def test(algo):
    results = []
    for _ in range(N):
        init_game()
        for i in range(10000):
            algo()
        results += [wallet]
        output(wallet)
    import numpy
    print 'max: '
    output(max(results))
    print 'median: '
    output(numpy.median(results))
    print 'min: '
    output(min(results))

def output(n):
    print n
    result = ''
    for _ in range(int(n/20000)):
        result += '-'
    print result+'|'

def alg():
    f = (float(len(stack)) / 10000)
    step = 160
    if f<0.5: step = 125
    if f>0.9: step = 190
    if read() < max_taken + step:
        #if read()>max_taken: print read(), step, f
        take()
    else:
        passe()

test(alg)

BitCoin address: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Wow OP delivered! Thanks @LivingInformation!

Answer 3

C++, $803,960

for (int iVal = 0; iVal < 10000; ++iVal)
{
    int val = game.read();
    if (val > maxVal &&
        val < 466.7f + 0.9352f * maxVal + 0.0275f * iVal)
    {
        maxVal = val;
        game.take();
    }
    else
    {
        game.pass();
    }
}

Reported result is the median from 10,001 games.

Answer 4

Java, $806,899

This is from a trial of 2501 rounds. I am still working on optimizing it. I wrote two classes, a wrapper and a player. The wrapper instantiates the player with the number of envelopes (always 10000 for the real thing), and then calls the method takeQ with the top envelope's value. The player then returns true if they take it, false if they pass it.

Player

import java.lang.Math;

public class Player {
  public int[] V;

  public Player(int s) {
    V = new int[s];
    for (int i = 0; i < V.length; i++) {
      V[i] = i + 1;
    }
    // System.out.println();
  }

  public boolean takeQ(int x) {

    // System.out.println("look " + x);

    // http://www.programmingsimplified.com/java/source-code/java-program-for-binary-search
    int first = 0;
    int last = V.length - 1;
    int middle = (first + last) / 2;
    int search = x;

    while (first <= last) {
      if (V[middle] < search)
        first = middle + 1;
      else if (V[middle] == search)
        break;
      else
        last = middle - 1;

      middle = (first + last) / 2;
    }

    int i = middle;

    if (first > last) {
      // System.out.println(" PASS");
      return false; // value not found, so the envelope must not be in the list
                    // of acceptable ones
    }

    int[] newVp = new int[V.length - 1];
    for (int j = 0; j < i; j++) {
      newVp[j] = V[j];
    }
    for (int j = i + 1; j < V.length; j++) {
      newVp[j - 1] = V[j];
    }
    double pass = calcVal(newVp);
    int[] newVt = new int[V.length - i - 1];
    for (int j = i + 1; j < V.length; j++) {
      newVt[j - i - 1] = V[j];
    }
    double take = V[i] + calcVal(newVt);
    // System.out.println(" take " + take);
    // System.out.println(" pass " + pass);

    if (take > pass) {
      V = newVt;
      // System.out.println(" TAKE");
      return true;
    } else {
      V = newVp;
      // System.out.println(" PASS");
      return false;
    }
  }

  public double calcVal(int[] list) {
    double total = 0;
    for (int i : list) {
      total += i;
    }
    double ent = 0;
    for (int i : list) {
      if (i > 0) {
        ent -= i / total * Math.log(i / total);
      }
    }
    // System.out.println(" total " + total);
    // System.out.println(" entro " + Math.exp(ent));
    // System.out.println(" count " + list.length);
    return total * (Math.pow(Math.exp(ent), -0.5) * 4.0 / 3);
  }
}

Wrapper

import java.lang.Math;
import java.util.Random;
import java.util.ArrayList;
import java.util.Collections;

public class Controller {
  public static void main(String[] args) {
    int size = 10000;
    int rounds = 2501;
    ArrayList<Integer> results = new ArrayList<Integer>();
    int[] envelopes = new int[size];
    for (int i = 0; i < envelopes.length; i++) {
      envelopes[i] = i + 1;
    }
    for (int round = 0; round < rounds; round++) {
      shuffleArray(envelopes);

      Player p = new Player(size);
      int cutoff = 0;
      int winnings = 0;
      for (int i = 0; i < envelopes.length; i++) {
        boolean take = p.takeQ(envelopes[i]);
        if (take && envelopes[i] >= cutoff) {
          winnings += envelopes[i];
          cutoff = envelopes[i];
        }
      }
      results.add(winnings);
    }
    Collections.sort(results);
    System.out.println(
        rounds + " rounds, median is " + results.get(results.size() / 2));
  }

  // stol... I mean borrowed from
  // http://stackoverflow.com/questions/1519736/random-shuffling-of-an-array
  static Random rnd = new Random();

  static void shuffleArray(int[] ar) {
    for (int i = ar.length - 1; i > 0; i--) {
      int index = rnd.nextInt(i + 1);
      // Simple swap
      int a = ar[index];
      ar[index] = ar[i];
      ar[i] = a;
    }
  }
}

A more detailed explanation is coming soon, after I finish optimizations.

The core idea is to be able to estimate the reward from playing a game from a given set of envelopes. If the current set of envelopes is {2,4,5,7,8,9}, and the top envelope is the 5, then there are two possibilities:

• Take the 5 and play a game with {7,8,9}
• Pass the 5 and play a game of {2,4,7,8,9}

If we calculate the expected reward of {7,8,9} and compare it to the expected reward of {2,4,7,8,9}, we will be able to tell if taking the 5 is worth it.

Now the question is, given a set of envelopes like {2,4,7,8,9} what is the expected value? I found the the expected value seems to be proportional to the total amount of money in the set, but inversely proportional to the square root of the number of envelopes that the money is divided into. This came from "perfectly" playing several small games in which all of the envelopes have almost identical value.

The next problem is how to determine the "effective number of envelopes." In all cases, the number of envelopes is known exactly by keeping track of what you've seen and done. Something like {234,235,236} is definitely three envelopes, {231,232,233,234,235} is definitely 5, but {1,2,234,235,236} should really count as 3 and not 5 envelopes because the 1 and 2 are nearly worthless, and you would never PASS on a 234 so you could later pick up a 1 or 2. I had the idea of using Shannon entropy to determine the effective number of envelopes.

I targeted my calculations to situations where the envelope's values are uniformly distributed over some interval, which is what happens during the game. If I take {2,4,7,8,9} and treat that as a probability distribution, its entropy is 1.50242. Then I do exp() to get 4.49254 as the effective number of envelopes.

The estimated reward from {2,4,7,8,9} is 30 * 4.4925^-0.5 * 4/3 = 18.87

The exact number is 18.1167.

This isn't an exact estimate, but I am actually really proud of how well this fits the data when the envelopes are uniformly distributed over an interval. I'm not sure of the correct multiplier (I am using 4/3 for now) but here is a data table excluding the multiplier.

Set of Envelopes                    Total * (e^entropy)^-0.5      Actual Score

{1,2,3,4,5,6,7,8,9,10}              18.759                        25.473
{2,3,4,5,6,7,8,9,10,11}             21.657                        29.279
{3,4,5,6,7,8,9,10,11,12}            24.648                        33.125
{4,5,6,7,8,9,10,11,12,13}           27.687                        37.002
{5,6,7,8,9,10,11,12,13,14}          30.757                        40.945
{6,7,8,9,10,11,12,13,14,15}         33.846                        44.900
{7,8,9,10,11,12,13,14,15,16}        36.949                        48.871
{8,9,10,11,12,13,14,15,16,17}       40.062                        52.857
{9,10,11,12,13,14,15,16,17,18}      43.183                        56.848
{10,11,12,13,14,15,16,17,18,19}     46.311                        60.857

Linear regression between expected and actual gives an R^2 value of 0.999994.

My next step to improve this answer is to improve estimation when the number of envelopes starts to get small, which is when the envelopes are not approximately uniformly distributed and when the problem starts to get granular.

---

Edit: If this is deemed worthy of bitcoins, I just got an address at 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. Thanks! (This was here from when the challenge author was handing out prizes.)

Answer 5

C++, ~$815,000

Based on Reto Koradi's solution, but switches to a more sophisticated algorithm once there's 100 (valid) envelopes left, shuffling random permutations and computing the heaviest increasing subsequence of them. It will compare the results of taking and not taking the envelope, and will greedily select the best choice.

#include <algorithm>
#include <iostream>
#include <vector>
#include <set>


void setmax(std::vector<int>& h, int i, int v) {
    while (i < h.size()) { h[i] = std::max(v, h[i]); i |= i + 1; }
}

int getmax(std::vector<int>& h, int n) {
    int m = 0;
    while (n > 0) { m = std::max(m, h[n-1]); n &= n - 1; }
    return m;
}

int his(const std::vector<int>& l, const std::vector<int>& rank) {
    std::vector<int> h(l.size());
    for (int i = 0; i < l.size(); ++i) {
        int r = rank[i];
        setmax(h, r, l[i] + getmax(h, r));
    }

    return getmax(h, l.size());
}

template<class RNG>
void shuffle(std::vector<int>& l, std::vector<int>& rank, RNG& rng) {
    for (int i = l.size() - 1; i > 0; --i) {
        int j = std::uniform_int_distribution<int>(0, i)(rng);
        std::swap(l[i], l[j]);
        std::swap(rank[i], rank[j]);
    }
}

std::random_device rnd;
std::mt19937_64 rng(rnd());

struct Algo {
    Algo(int N) {
        for (int i = 1; i < N + 1; ++i) left.insert(i);
        ival = maxval = 0;
    }

    static double get_p(int n) { return 1.2 / std::sqrt(8 + n) + 0.71; }

    bool should_take(int val) {
        ival++;
        auto it = left.find(val);
        if (it == left.end()) return false;

        if (left.size() > 100) {
            if (val > maxval && val < 466.7f + 0.9352f * maxval + 0.0275f * (ival - 1)) {
                maxval = val;
                left.erase(left.begin(), std::next(it));
                return true;
            }

            left.erase(it);
            return false;
        }

        take.assign(std::next(it), left.end());
        no_take.assign(left.begin(), it);
        no_take.insert(no_take.end(), std::next(it), left.end());
        take_rank.resize(take.size());
        no_take_rank.resize(no_take.size());
        for (int i = 0; i < take.size(); ++i) take_rank[i] = i;
        for (int i = 0; i < no_take.size(); ++i) no_take_rank[i] = i;

        double take_score, no_take_score;
        take_score = no_take_score = 0;
        for (int i = 0; i < 1000; ++i) {
            shuffle(take, take_rank, rng);
            shuffle(no_take, no_take_rank, rng);
            take_score += val + his(take, take_rank) * get_p(take.size());
            no_take_score += his(no_take, no_take_rank) * get_p(no_take.size());
        }

        if (take_score > no_take_score) {
            left.erase(left.begin(), std::next(it));
            return true;
        }

        left.erase(it);
        return false;
    }

    std::set<int> left;
    int ival, maxval;
    std::vector<int> take, no_take, take_rank, no_take_rank;
};


struct Game {
    Game(int N) : score_(0), max_taken(0) {
        for (int i = 1; i < N + 1; ++i) envelopes.push_back(i);
        std::shuffle(envelopes.begin(), envelopes.end(), rng);
    }

    int read() { return envelopes.back(); }
    bool done() { return envelopes.empty(); }
    int score() { return score_; }
    void pass() { envelopes.pop_back(); }

    void take() {
        if (read() > max_taken) {
            score_ += read();
            max_taken = read();
        }
        envelopes.pop_back();
    }

    int score_;
    int max_taken;
    std::vector<int> envelopes;
};


int main(int argc, char** argv) {
    std::vector<int> results;
    std::vector<int> max_results;
    int N = 10000;
    for (int i = 0; i < 1000; ++i) {
        std::cout << "Simulating game " << (i+1) << ".\n";
        Game game(N);
        Algo algo(N);

        while (!game.done()) {
            if (algo.should_take(game.read())) game.take();
            else game.pass();
        }
        results.push_back(game.score());
    }

    std::sort(results.begin(), results.end());
    std::cout << results[results.size()/2] << "\n";

    return 0;
}