Tómalo o déjalo: un programa de juegos para computadoras

28

Contexto:

Un multimillonario solitario ha creado un programa de juegos para atraer a los mejores y más brillantes programadores del mundo. Los lunes a la medianoche, elige a una persona de un grupo de solicitantes para ser el concursante de la semana, y les proporciona un juego. ¡Eres el concursante afortunado de esta semana!

El juego de esta semana:

El host le proporciona acceso API a una pila de 10,000 sobres digitales. Estos sobres se ordenan aleatoriamente y contienen dentro de ellos un valor en dólares, entre $ 1 y $ 10,000 (no hay dos sobres que contengan el mismo valor en dólares).

Tienes 3 comandos a tu disposición:

  1. Leer (): lee la cifra en dólares en el sobre en la parte superior de la pila.

  2. Take (): Agregue la figura del dólar en el sobre a la billetera de su programa de juegos y saque el sobre de la pila.

  3. Pase (): salta el sobre en la parte superior de la pila.

Las normas:

  1. Si usa Pass () en un sobre, el dinero dentro se pierde para siempre.

  2. Si usa Take () en un sobre que contiene $ X, a partir de ese momento, nunca podrá usar Take () en un sobre que contenga <$ X. Tomar () en uno de estos sobres agregará $ 0 a su billetera.

Escribe un algoritmo que termine el juego con la cantidad máxima de dinero.

Si está escribiendo una solución en Python, siéntase libre de usar este controlador para probar algoritmos, cortesía de @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

Si usa el controlador, no puede acceder a los globales, solo puede usar los 3 comandos API proporcionados y las variables de ámbito local. (@Beta Decay)

Notas: "Máximo" en este caso significa el valor medio en su billetera después de N> 50 carreras. Espero, aunque me encantaría que me demuestren lo contrario, que el valor medio para un algoritmo dado convergerá a medida que N aumente hasta el infinito. En su lugar, siéntase libre de intentar maximizar la media, pero tengo la sensación de que es más probable que la media sea arrojada por una pequeña N que la mediana.

Editar: cambió el número de sobres a 10k para un procesamiento más fácil e hizo Take () más explícito.

Edición 2: La condición del premio se ha eliminado, a la luz de esta publicación en meta.

Puntajes altos actuales:

PhiNotPi - $ 805,479

Reto Koradi - $ 803,960

Dennis - $ 770,272 (revisado)

Alex L. - $ 714,962 (Revisado)

LivingInformation
fuente
Lo implementé de una manera que solo devuelve False. Como puedes leerlo, no tiene sentido fallar todo el juego en una toma fallida ()
OganM
44
En caso de que alguien quiera usarlo, aquí está el controlador que he estado usando para probar mis algoritmos: gist.github.com/Maltysen/5a4a33691cd603e9aeca
Maltysen
8
PD Bonita pregunta y bienvenido a Programming Puzzles y Code Golf :)
trichoplax
3
@Maltysen Puse su controlador en el OP, ¡gracias por la contribución!
LivingInformation
1
No pude encontrar una regla explícita sobre los premios de bitcoin, pero hay una meta discusión sobre los premios del mundo real a la que las personas pueden contribuir.
trichoplax

Respuestas:

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

Este programa simula todo el juego varias veces y calcula la mediana.

Como correr

He puntuado mi presentación haciendo 100.001 pruebas:

$ 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

Enfoque

Para cada sobre, hacemos lo siguiente:

  • Calcule la cantidad de dinero que inevitablemente se perderá al tomar el sobre.

    Si R es el contenido y M es el máximo que se ha tomado, la cantidad puede estimarse como R (R-1) / 2 - M (M + 1) / 2 , lo que le da al dinero todos los sobres con contenido X en el intervalo (M, R) contiene.

    Si todavía no se hubieran pasado sobres, la estimación sería perfecta.

  • Calcule la cantidad de dinero que inevitablemente se perderá al pasar el sobre.

    Esto es simplemente el dinero que contiene el sobre.

  • Compruebe si el cociente de ambos es inferior a 110 + 0.016E , donde E es el número de sobres restantes (sin contar los sobres que ya no se pueden tomar).

    Si es así, tómalo. De lo contrario, pase.

Dennis
fuente
55
Porque usar un lenguaje de golf ayuda de cualquier forma. ; P +1 para el algo.
Maltysen
2
No puedo replicar sus resultados usando un clon de Python: gist.github.com/orlp/f9b949d60c766430fe9c . Obtienes alrededor de $ 50,000. Eso es un orden de magnitud.
orlp
1
@LivingInformation Prueba y error. Actualmente estoy buscando usar la cantidad exacta en lugar de las estimaciones, pero el código resultante es muy lento.
Dennis
2
¡Esta respuesta necesita más votos a favor que la mía! ¡Es más inteligente, puntúa más alto e incluso se juega al golf!
Alex L
1
@LivingInformation Esta es mi dirección: 17uLHRfdD5JZ2QjSqPGQ1B12LoX4CgLGuV
Dennis
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()

Toma cantidades cada vez más grandes en pasos de tamaño entre $ 125 y $ 190. Funcionó con N = 10,000 y obtuvo una mediana de $ 714962. Estos tamaños de paso provienen de prueba y error y ciertamente no son óptimos.

El código completo, incluida una versión modificada del controlador de @ Maltysen que imprime un gráfico de barras mientras se ejecuta:

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)

Dirección de BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Wow OP entregado! Gracias @LivingInformation!

Alex L
fuente
1
El controlador es de Maltysen, no mío.
orlp
2
Confirmado. Acababa de configurar un controlador y obtengo números muy similares para su solución. Estrictamente hablando, creo que debes mantener el valor de max_takentu propio código, ya que no es parte de la API oficial del juego. Pero eso es trivial de hacer.
Reto Koradi
1
Sí, max_taken está en el controlador de @ Maltysen. Si es útil, puedo publicar la solución completa (controlador + algoritmo) en un bloque.
Alex L
Realmente no es gran cosa. Pero creo que el enfoque más limpio sería utilizar sólo el read(), take()y pass()métodos en el código publicado, ya que esos son los "3 comandos a su disposición", basada en la definición de la cuestión.
Reto Koradi
@Reto Estoy dispuesto a revisar la pregunta a los comandos que tengan más sentido. Read, Take y Pass fueron los 4 caracteres, y me sentí apropiado, pero estoy abierto a sugerencias (por ejemplo, he considerado cambiar "pasar" a "salir", porque titulé la publicación "tómalo o déjalo" ").
LivingInformation
5

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

El resultado reportado es la mediana de 10,001 juegos.

Reto Koradi
fuente
Adivina y comprueba, ¿lo tomo? ¿O usaste algún tipo de fuzzer de entrada para las constantes?
LivingInformation
Ejecuté un algoritmo de optimización para determinar las constantes.
Reto Koradi
¿Crees que un cálculo dinámico en cada punto sería más efectivo o crees que se está acercando al valor máximo que puedes recibir?
LivingInformation
No tengo motivos para creer que sea la estrategia ideal. Espero que sea el máximo para una función lineal con estos parámetros. He estado tratando de permitir varios tipos de términos no lineales, pero hasta ahora no he encontrado nada significativamente mejor.
Reto Koradi
1
Puedo confirmar que simular esto da un puntaje reportado de poco más de $ 800,000.
orlp
3

C ++, ~ $ 815,000

Basado en la solución de Reto Koradi, pero cambia a un algoritmo más sofisticado una vez que quedan 100 sobres (válidos), barajando permutaciones aleatorias y calculando la subsecuencia cada vez mayor. Comparará los resultados de tomar y no tomar el sobre, y seleccionará con avidez la mejor opción.

#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
fuente
Interesante. Se me pasó por la cabeza que debería ser posible mejorar mirando los valores que quedan para los últimos sobres. Me imagino que jugaste con el punto de corte donde cambias de estrategia. ¿Se está volviendo demasiado lento si cambia antes? ¿O los resultados realmente están empeorando?
Reto Koradi
@RetoKoradi Jugué con el punto de corte, y los cortes anteriores se volvieron demasiado lentos y peores. No es demasiado sorprendente, honestamente, a 100 sobres ya estamos muestreando un mero 1000 permutaciones de un máximo de 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.
orlp
3

Java, $ 806,899

Esto es de una prueba de 2501 rondas. Todavía estoy trabajando en optimizarlo. Escribí dos clases, una envoltura y un jugador. El contenedor crea una instancia del jugador con el número de sobres (siempre 10000 para el objeto real) y luego llama al método takeQcon el valor del sobre superior. El jugador luego regresa truesi lo toman, falsesi lo pasan.

Jugador

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

Envoltura

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

Pronto habrá una explicación más detallada, después de que termine las optimizaciones.

La idea central es poder estimar la recompensa de jugar un juego a partir de un conjunto dado de sobres. Si el conjunto actual de sobres es {2,4,5,7,8,9}, y el sobre superior es el 5, entonces hay dos posibilidades:

  • Toma el 5 y juega con {7,8,9}
  • Pase el 5 y juegue un juego de {2,4,7,8,9}

Si calculamos la recompensa esperada de {7,8,9} y la comparamos con la recompensa esperada de {2,4,7,8,9}, podremos saber si vale la pena tomar el 5.

Ahora la pregunta es, dado un conjunto de sobres como {2,4,7,8,9} ¿cuál es el valor esperado? Descubrí que el valor esperado parece ser proporcional a la cantidad total de dinero en el conjunto, pero inversamente proporcional a la raíz cuadrada del número de sobres en los que se divide el dinero. Esto vino de jugar "perfectamente" varios juegos pequeños en los que todos los sobres tienen un valor casi idéntico.

El siguiente problema es cómo determinar el " número efectivo de sobres". En todos los casos, la cantidad de sobres se conoce exactamente al realizar un seguimiento de lo que ha visto y hecho. Algo así como {234,235,236} es definitivamente tres sobres, {231,232,233,234,235} es definitivamente 5, pero {1,2,234,235,236} realmente debería contar como 3 y no 5 sobres porque el 1 y 2 son casi inútiles, y nunca pasarías un 234 así más tarde podría recoger un 1 o 2. Tuve la idea de usar la entropía de Shannon para determinar el número efectivo de sobres.

Dirigí mis cálculos a situaciones en las que los valores de la envolvente se distribuyen uniformemente en algún intervalo, que es lo que sucede durante el juego. Si tomo {2,4,7,8,9} y trato eso como una distribución de probabilidad, su entropía es 1.50242. Luego hago exp()para obtener 4.49254 como el número efectivo de sobres.

La recompensa estimada de {2,4,7,8,9} es 30 * 4.4925^-0.5 * 4/3 = 18.87

El número exacto es 18.1167.

Esta no es una estimación exacta, pero estoy realmente orgulloso de cuán bien se ajusta a los datos cuando los sobres se distribuyen uniformemente en un intervalo. No estoy seguro del multiplicador correcto (estoy usando 4/3 por ahora) pero aquí hay una tabla de datos que excluye el multiplicador.

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

La regresión lineal entre lo esperado y lo real da un valor R ^ 2 de 0.999994 .

Mi próximo paso para mejorar esta respuesta es mejorar la estimación cuando el número de sobres comienza a ser pequeño, que es cuando los sobres no están distribuidos de manera aproximadamente uniforme y cuando el problema comienza a ser granular.


Editar: si esto se considera digno de bitcoins, acabo de recibir una dirección en 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. ¡Gracias! (Esto fue aquí cuando el autor del desafío estaba repartiendo premios).

PhiNotPi
fuente
Accidentalmente te envié 20k satoshi sobre 805,479. Como referencia, se suponía que la cantidad era su puntaje. Disfruta mi error :)
LivingInformation
¿Correrás números con más rondas? Según lo que estoy viendo, hay bastante variación, y 500 no es suficiente para obtener una mediana estable. Mi puntaje es muy cercano al tuyo si corro solo 500 rondas, pero todo depende de cómo caigan los números aleatorios. Si usé una semilla variable, e hice 500 corridas varias veces, probablemente podría obtener una puntuación más alta.
Reto Koradi
@RetoKoradi Definitivamente voy a hacer más rondas.
PhiNotPi