Возьми или оставь: игровое шоу для компьютеров

28

Контекст:

Миллиардер-затворник создал игровое шоу для привлечения лучших и самых ярких программистов мира. По понедельникам в полночь он выбирает одного человека из числа претендентов на участие в неделе и предоставляет им игру. Вы счастливчик на этой неделе!

Игра на этой неделе:

Хост предоставляет API-доступ к стопке из 10 000 цифровых конвертов. Эти конверты сортируются случайным образом и содержат внутри себя долларовую стоимость от 1 до 10000 долларов (никакие два конверта не содержат одинаковую долларовую стоимость).

В вашем распоряжении 3 команды:

  1. Чтение (): чтение цифры доллара в конверте в верхней части стопки.

  2. Возьмите (): добавьте долларовую цифру в конверте в свой кошелек для игрового шоу и вытяните конверт из стопки.

  3. Pass (): выскочить из конверта на вершине стека.

Правила:

  1. Если вы используете Pass () на конверте, деньги внутри будут потеряны навсегда.

  2. Если вы используете Take () на конверте, содержащем $ X, с этого момента вы никогда не сможете использовать Take () на конверте, содержащем <$ X. Take () на одном из этих конвертов добавит $ 0 к вашему кошельку.

Напишите алгоритм, который заканчивает игру с максимальной суммой денег.

Если вы пишете решение на Python, не стесняйтесь использовать этот контроллер для проверки алгоритмов, предоставлено @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

Если вы используете контроллер, вы не сможете получить доступ к глобальным переменным, вы можете использовать только 3 предоставленные команды API и локальные переменные области действия. (@Beta Decay)

Примечания: «Максимальный» в этом случае означает медиану в вашем кошельке после N> 50 пробежек. Я ожидаю, хотя я бы хотел оказаться ошибочным, что медианное значение для данного алгоритма будет сходиться при увеличении N до бесконечности. Не стесняйтесь пытаться максимизировать среднее значение вместо этого, но у меня есть ощущение, что среднее значение, скорее всего, будет отброшено небольшим N, чем медиана.

Изменить: изменил количество конвертов до 10 КБ для упрощения обработки и сделал Take () более явным.

Изменить 2: условие приза было удалено, в свете этого поста на мета.

Текущие рекорды:

PhiNotPi - $ 805 479

Рето Коради - $ 803 960

Деннис - 770 272 долл. США (пересмотрено)

Алекс Л. - 714 962 $ (пересмотренный)

LivingInformation
источник
Я реализовал таким образом, что он просто возвращает False. Так как вы можете прочитать его, нет смысла проваливать всю игру на неудачном
дубле
4
На случай, если кто-то захочет его использовать, вот контроллер, который я использовал для проверки своих алгоритмов: gist.github.com/Maltysen/5a4a33691cd603e9aeca
Maltysen
8
PS Хороший вопрос и добро пожаловать в программирование головоломок и Code Golf :)
trichoplax
3
@ Maltysen Я поместил ваш контроллер в ОП, спасибо за вклад!
LivingInformation
1
Я не смог найти четкого правила для призов в биткойнах, но есть мета-обсуждение реальных призов, в которые люди могут внести свой вклад.
Трихоплакс

Ответы:

9

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

Эта программа имитирует всю игру несколько раз и вычисляет медиану.

Как бегать

Я набрал 100001 тестов:

$ 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

Подходить

Для каждого конверта мы делаем следующее:

  • Оцените сумму денег, которая неизбежно будет потеряна, взяв конверт.

    Если R - это содержание, а M - это максимум, который был взят, сумма может быть оценена как R (R-1) / 2 - M (M + 1) / 2 , что дает деньги всем конвертам с содержанием X в интервал (M, R) содержит.

    Если конверты еще не были переданы, оценка будет идеальной.

  • Рассчитайте сумму денег, которая неизбежно будет потеряна, передавая конверт.

    Это просто деньги, которые содержит конверт.

  • Проверьте, не является ли отношение обоих менее 110 + 0,016E , где E - количество оставшихся конвертов (не считая конверты, которые больше не могут быть взяты).

    Если так, бери. В противном случае, пройти.

Деннис
источник
5
Потому что использование языка игры в гольф помогает в любом случае. ; P +1 для алгоритма.
Maltysen
2
Я не могу воспроизвести ваши результаты, используя клон Python: gist.github.com/orlp/f9b949d60c766430fe9c . Вы набрали около 50 000 долларов. Это на порядок ниже.
orlp
1
@LivingInformation Проб и ошибок. В настоящее время я смотрю на использование точного количества вместо оценок, но полученный код очень медленный.
Деннис
2
Этот ответ требует больше голосов, чем мой! Это умнее, баллы выше, и даже в гольф!
Алекс Л
1
@LivingInformation Это мой адрес: 17uLHRfdD5JZ2QjSqPGQ1B12LoX4CgLGuV
Деннис
7

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()

Принимает все большие и большие суммы в размере от 125 до 190 долларов. Побежал с N = 10000 и получил медиану $ 714962. Эти размеры шагов получены методом проб и ошибок и, конечно, не являются оптимальными.

Полный код, включая модифицированную версию контроллера @ Maltysen, которая печатает гистограмму во время работы:

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: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Ух ОП доставлено! Спасибо @LivingInformation!

Алекс Л
источник
1
Контроллер принадлежит Малтисену, а не моему.
orlp
2
Подтверждено. Я только что установил контроллер и получил очень похожие цифры для вашего решения. Строго говоря, я думаю, что вы должны поддерживать значение max_takenв своем собственном коде, поскольку он не является частью официального API игры. Но это тривиально.
Рето Коради
1
Да, max_taken находится в контроллере @ Maltysen. Если это полезно, я могу разместить все решение (контроллер + алгоритм) в одном блоке.
Алекс Л
Это действительно ничего страшного. Но я думаю , что самый чистый подход будет использовать только read(), take()и pass()методы Опубликованная кода, поскольку те являются «3 команды в вашем распоряжении» , основанный на определении вопроса.
Рето Коради
@ Reto Я хочу пересмотреть вопрос, чтобы какие-либо команды имели больше смысла. «Чтение», «Возьми» и «Проход» были все 4 символа, и я чувствовал, что это уместно, но я открыт для предложений (например, я подумал изменить «пройти» на «уйти», потому что я назвал пост «возьми его или оставь» «).
LivingInformation
5

С ++, 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();
    }
}

Отмеченный результат - медиана из 10 001 игр.

Рето Коради
источник
Угадай и проверь, я так понимаю? Или вы использовали какой-то входной фаззер для констант?
LivingInformation
Я запустил алгоритм оптимизации для определения констант.
Рето Коради
Считаете ли вы, что динамический расчет в каждой точке будет более эффективным, или вы думаете, что он приближается к максимальному значению, которое вы можете получить?
LivingInformation
У меня нет оснований полагать, что это идеальная стратегия. Я надеюсь, что это максимум для линейной функции с этими параметрами. Я пытался разрешить различные виды нелинейных терминов, но до сих пор не нашел ничего значительно лучше.
Рето Коради
1
Я могу подтвердить, что моделирование этого дает отчетный счет чуть более 800 000 долларов.
Orlp
3

C ++, ~ 815 000 долларов

Основывается на решении Рето Коради, но переключается на более сложный алгоритм, когда остается 100 (действительных) конвертов, перемешивая случайные перестановки и вычисляя наиболее тяжелую возрастающую их подпоследовательность. Он будет сравнивать результаты взятия и не взятия конверта и жадно выберет лучший выбор.

#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;
}
orlp
источник
Интересный. Мне пришло в голову, что можно улучшить, посмотрев на значения, оставшиеся для последних нескольких конвертов. Я полагаю, вы играли с точкой отсечки, где вы меняете стратегии? Это просто становится слишком медленным, если вы переключаетесь раньше? Или результаты на самом деле ухудшаются?
Рето Коради
@RetoKoradi Я играл с точкой среза, и более ранние срезы становились слишком медленными и хуже. Не слишком удивительно , если честно, на 100 конвертах мы уже выборок Простых 1000 перестановок из возможного 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.
orlp
3

Ява, $ 806 899

Это из испытания 2501 раундов. Я все еще работаю над оптимизацией. Я написал два класса, обертку и плеер. Оболочка создает экземпляр игрока с количеством конвертов (для реальных вещей всегда 10000), а затем вызывает метод takeQсо значением верхнего конверта. Игрок затем возвращается, trueесли они его принимают, falseесли они его пропускают.

игрок

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);
  }
}

обертка

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;
    }
  }
}

Более подробное объяснение скоро появится, когда я закончу оптимизацию.

Основная идея заключается в том, чтобы иметь возможность оценить вознаграждение за игру в заданном наборе конвертов. Если текущий набор конвертов {2,4,5,7,8,9}, а верхний конверт - 5, то есть две возможности:

  • Возьми 5 и играй в игру с {7,8,9}
  • Пройдите 5 и играйте в игру {2,4,7,8,9}

Если мы вычислим ожидаемое вознаграждение {7,8,9} и сравним его с ожидаемым вознаграждением {2,4,7,8,9}, мы сможем определить, стоит ли брать 5.

Теперь вопрос, учитывая набор конвертов типа {2,4,7,8,9}, какова ожидаемая стоимость? Я обнаружил, что ожидаемое значение кажется пропорциональным общей сумме денег в наборе, но обратно пропорционально квадратному корню из числа конвертов, на которые делятся деньги. Это произошло из-за «идеальной» игры в несколько небольших игр, в которых все конверты имеют почти одинаковую ценность.

Следующая проблема заключается в том, как определить « эффективное количество конвертов». Во всех случаях количество конвертов точно известно, отслеживая то, что вы видели и делали. Что-то вроде {234,235,236} определенно состоит из трех конвертов, {231,232,233,234,235} определенно равно 5, но {1,2,234,235,236} должно действительно считаться как 3, а не 5 конвертов, потому что 1 и 2 почти бесполезны, и вы никогда не пропустите на 234, поэтому позже вы могли бы взять 1 или 2. У меня была идея использовать энтропию Шеннона для определения эффективного числа конвертов.

Я нацелил свои расчеты на ситуации, когда значения конверта равномерно распределены по некоторому интервалу, что и происходит во время игры. Если я беру {2,4,7,8,9} и рассматриваю это как распределение вероятностей, его энтропия равна 1,50242. Затем я exp()получаю 4.49254 как эффективное количество конвертов.

Расчетное вознаграждение от {2,4,7,8,9} составляет 30 * 4.4925^-0.5 * 4/3 = 18.87

Точное число есть 18.1167.

Это не точная оценка, но я действительно горжусь тем, насколько хорошо это подходит для данных, когда конверты равномерно распределены по интервалу. Я не уверен в правильном множителе (сейчас я использую 4/3), но вот таблица данных, исключая множитель.

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

Линейная регрессия между ожидаемым и фактическим дает значение R ^ 2 0,999994 .

Мой следующий шаг по улучшению этого ответа - улучшить оценку, когда количество конвертов начинает уменьшаться, то есть когда конверты распределены примерно неравномерно и когда проблема начинает становиться гранулированной.


Изменить: Если это считается достойным биткойнов, я только что получил адрес по адресу 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. Благодарность! (Это было здесь с того момента, когда автор конкурса раздавал призы.)

PhiNotPi
источник
Случайно отправил тебе 20к сатоши за 805,479. Для справки, сумма должна была быть вашей оценкой. Наслаждайся моей ошибкой :)
LivingInformation
Будете ли вы набирать номера с большим количеством раундов? Исходя из того, что я вижу, вариаций немного, и 500 недостаточно, чтобы получить стабильную медиану. Мой счет очень близок к вашему, если я пробежу только 500 раундов, но все зависит от того, как случайные числа упали. Если бы я использовал переменное начальное число и несколько раз выполнял 500 прогонов, я мог бы получить более высокий балл.
Рето Коради
@RetoKoradi Я определенно собираюсь сделать больше раундов.
PhiNotPi