Ambil atau Tinggalkan: Pertunjukan Game untuk Komputer

28

Konteks:

Seorang miliarder yang tertutup telah menciptakan acara permainan untuk menarik para programmer terbaik dan terpandai di dunia. Pada hari Senin di tengah malam, ia memilih satu orang dari kumpulan pelamar untuk menjadi kontestan minggu ini, dan memberi mereka permainan. Anda adalah kontestan yang beruntung minggu ini!

Game minggu ini:

Tuan rumah memberi Anda akses API ke tumpukan 10.000 amplop digital. Amplop ini diurutkan secara acak, dan di dalamnya berisi nilai dolar, antara $ 1 dan $ 10.000 (tidak ada dua amplop yang berisi nilai dolar yang sama).

Anda memiliki 3 perintah yang Anda inginkan:

  1. Baca (): Baca angka dolar dalam amplop di bagian atas tumpukan.

  2. Take (): Tambahkan angka dolar dalam amplop ke dompet permainan Anda, dan keluarkan amplop dari tumpukan.

  3. Pass (): Lepaskan amplop di bagian atas tumpukan.

Aturan:

  1. Jika Anda menggunakan Pass () pada amplop, uang di dalamnya hilang selamanya.

  2. Jika Anda menggunakan Take () pada amplop yang berisi $ X, sejak saat itu, Anda tidak boleh menggunakan Take () pada amplop yang berisi <$ X. Ambil () pada salah satu amplop ini akan menambah $ 0 ke dompet Anda.

Tulis algoritma yang menyelesaikan permainan dengan jumlah uang maksimal.

Jika Anda menulis solusi dengan Python, jangan ragu untuk menggunakan pengontrol ini untuk menguji algoritma, milik @Maltysen: https://gist.github.com/Maltysen/5a4a33691cd603e9aeca

Jika Anda menggunakan pengontrol, Anda tidak dapat mengakses global, Anda hanya dapat menggunakan 3 perintah API yang disediakan, dan variabel cakupan lokal. (@Beta Decay)

Catatan: "Maksimal" dalam hal ini berarti nilai median di dompet Anda setelah N> 50 berjalan. Saya berharap, meskipun saya ingin terbukti salah, bahwa nilai median untuk algoritma yang diberikan akan konvergen ketika N meningkat hingga tak terbatas. Jangan ragu untuk mencoba memaksimalkan mean, tetapi saya merasa bahwa mean lebih mungkin terlempar oleh N kecil daripada mediannya.

Sunting: mengubah jumlah amplop menjadi 10k untuk memudahkan pemrosesan, dan menjadikan Take () lebih eksplisit.

Sunting 2: Kondisi hadiah telah dihapus, mengingat pos ini menggunakan meta.

Skor tinggi saat ini:

PhiNotPi - $ 805.479

Reto Koradi - $ 803.960

Dennis - $ 770.272 (Revisi)

Alex L. - $ 714.962 (Revisi)

Informasi hidup
sumber
Saya menerapkan dengan cara yang mengembalikan False. Karena Anda dapat membacanya, tidak ada gunanya gagal seluruh permainan dengan pengambilan yang gagal ()
OganM
4
Jika ada yang ingin menggunakannya, berikut ini adalah pengontrol yang telah saya gunakan untuk menguji algoritme saya: gist.github.com/Maltysen/5a4a33691cd603e9aeca
Maltysen
8
PS Pertanyaan yang bagus dan selamat datang di Programming Puzzles and Code Golf :)
trichoplax
3
@Maltysen Saya menempatkan controller Anda ke OP, terima kasih atas kontribusinya!
LivingInformation
1
Saya tidak bisa menemukan aturan eksplisit tentang hadiah bitcoin, tetapi ada beberapa diskusi meta tentang hadiah dunia nyata yang dapat dikontribusikan orang.
trichoplax

Jawaban:

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

Program ini mensimulasikan seluruh permainan beberapa kali dan menghitung median.

Bagaimana cara menjalankannya

Saya telah mencetak kiriman saya dengan melakukan 100.00 tes berjalan:

$ 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

Pendekatan

Untuk setiap amplop, kami melakukan hal berikut:

  • Perkirakan jumlah uang yang pasti akan hilang dengan mengambil amplop.

    Jika R adalah konten dan M adalah maksimum yang telah diambil, jumlahnya dapat diperkirakan sebagai R (R-1) / 2 - M (M + 1) / 2 , yang memberikan uang semua amplop dengan konten X dalam interval (M, R) mengandung.

    Jika belum ada amplop yang dilewati, estimasi akan sempurna.

  • Hitung jumlah uang yang pasti akan hilang dengan menyerahkan amplop.

    Ini hanyalah uang yang berisi amplop.

  • Periksa apakah hasil bagi dari keduanya kurang dari 110 + 0,016E , di mana E adalah jumlah amplop yang tersisa (tidak termasuk amplop yang tidak dapat diambil lagi).

    Jika demikian, ambil. Kalau tidak, lulus.

Dennis
sumber
5
Karena menggunakan bahasa golf membantu dengan cara apa pun. ; P +1 untuk algo.
Maltysen
2
Saya tidak dapat mereplikasi hasil Anda menggunakan klon Python: gist.github.com/orlp/f9b949d60c766430fe9c . Skor Anda sekitar $ 50.000. Itu urutan besarnya.
orlp
1
@LivingInformation Trial and error. Saat ini saya sedang mencari menggunakan jumlah yang tepat, bukan estimasi, tetapi kode yang dihasilkan sangat lambat.
Dennis
2
Jawaban ini membutuhkan lebih banyak upvote daripada milik saya! Lebih pintar, skor lebih tinggi, dan bahkan golf!
Alex L
1
@LivingInformation Ini adalah alamat saya: 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()

Mengambil jumlah yang lebih besar dan lebih besar dalam langkah ukuran antara $ 125 dan $ 190. Berlari dengan N = 10.000 dan dapatkan median $ 714962. Ukuran langkah ini berasal dari coba-coba dan tentu saja tidak optimal.

Kode lengkap, termasuk versi modifikasi dari pengontrol @ Maltysen yang mencetak bagan batang saat dijalankan:

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)

Alamat BitCoin: 1CBzYPCFFBW1FX9sBTmNYUJyMxMcmL4BZ7

Wow OP terkirim! Terima kasih @LivingInformation!

Alex L
sumber
1
Pengontrolnya adalah Maltysen, bukan milikku.
orlp
2
Dikonfirmasi Saya baru saja membuat controller, dan mendapatkan nomor yang sangat mirip untuk solusi Anda. Sebenarnya, saya pikir Anda harus mempertahankan nilai max_takendalam kode Anda sendiri, karena itu bukan bagian dari API game resmi. Tapi itu sepele untuk dilakukan.
Reto Koradi
1
Ya, max_taken ada di pengontrol @ Maltysen. Jika berguna saya dapat memposting seluruh solusi (pengontrol + algoritma) dalam satu blok.
Alex L
Ini benar-benar bukan masalah besar. Tapi saya pikir pendekatan paling bersih adalah dengan hanya menggunakan read(), take()dan pass()metode dalam kode yang diposting, karena itu adalah "3 perintah yang Anda inginkan" berdasarkan definisi dalam pertanyaan.
Reto Koradi
@Reto Saya bersedia merevisi pertanyaan untuk perintah apa pun yang paling masuk akal. Baca, Ambil, dan Lulus semuanya 4 karakter, dan terasa pas, tetapi saya terbuka untuk saran (misalnya, saya telah mempertimbangkan untuk mengubah "lewati" menjadi "pergi", karena saya memberi judul pada pos "ambil atau tinggalkan itu ").
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();
    }
}

Hasil yang dilaporkan adalah median dari 10.001 pertandingan.

Reto Koradi
sumber
Tebak dan periksa, saya ambil? Atau apakah Anda menggunakan semacam fuzzer input untuk konstanta?
LivingInformation
Saya menjalankan algoritma optimasi untuk menentukan konstanta.
Reto Koradi
Apakah Anda berpikir bahwa perhitungan dinamis pada setiap titik akan lebih efektif, atau apakah Anda pikir ini mendekati nilai maksimum yang dapat Anda terima?
LivingInformation
Saya tidak punya alasan untuk percaya bahwa itu adalah strategi yang ideal. Saya harap ini maksimum untuk fungsi linier dengan parameter ini. Saya sudah mencoba untuk mengizinkan berbagai macam istilah non-linear, tetapi sejauh ini belum menemukan sesuatu yang secara signifikan lebih baik.
Reto Koradi
1
Saya dapat mengkonfirmasi bahwa simulasi ini memberikan skor yang dilaporkan sedikit lebih dari $ 800.000.
orlp
3

C ++, ~ $ 815.000

Berdasarkan solusi Reto Koradi, tetapi beralih ke algoritma yang lebih canggih begitu ada 100 (valid) amplop yang tersisa, mengacak permutasi acak dan menghitung kenaikan berikutnya yang paling berat. Ini akan membandingkan hasil pengambilan dan tidak mengambil amplop, dan rakus akan memilih pilihan terbaik.

#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
sumber
Menarik. Terlintas dalam benak saya bahwa mungkin untuk meningkatkan dengan melihat nilai-nilai yang tersisa untuk beberapa amplop terakhir. Saya kira Anda bermain dengan titik cutoff di mana Anda berganti strategi? Apakah terlalu lambat jika Anda beralih lebih awal? Atau hasilnya benar-benar semakin buruk?
Reto Koradi
@RetoKoradi saya memang bermain dengan titik cutoff, dan cutoff sebelumnya keduanya terlalu lambat dan lebih buruk. Tidak terlalu mengejutkan jujur, pada 100 amplop kita sudah sampel hanya 1.000 permutasi dari kemungkinan 93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000.
orlp
3

Java, $ 806.899

Ini dari uji coba 2501 putaran. Saya masih berusaha mengoptimalkannya. Saya menulis dua kelas, pembungkus dan pemain. Pembungkus instantiate pemain dengan jumlah amplop (selalu 10.000 untuk hal yang nyata), dan kemudian memanggil metode takeQdengan nilai amplop atas. Pemain kemudian kembali truejika mereka mengambilnya, falsejika mereka melewatinya.

Pemain

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

Pembungkus

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

Penjelasan lebih rinci akan segera hadir, setelah saya menyelesaikan optimasi.

Gagasan intinya adalah untuk dapat memperkirakan hadiah dari bermain game dari set amplop tertentu. Jika set amplop saat ini adalah {2,4,5,7,8,9}, dan amplop atas adalah 5, maka ada dua kemungkinan:

  • Ambil 5 dan mainkan game dengan {7,8,9}
  • Lewati 5 dan mainkan permainan {2,4,7,8,9}

Jika kita menghitung hadiah yang diharapkan dari {7,8,9} dan membandingkannya dengan hadiah yang diharapkan dari {2,4,7,8,9}, kita akan dapat mengetahui apakah mengambil 5 itu sepadan.

Sekarang pertanyaannya adalah, diberikan satu set amplop seperti {2,4,7,8,9} berapa nilai yang diharapkan? Saya menemukan nilai yang diharapkan tampaknya proporsional dengan jumlah total uang di set, tetapi berbanding terbalik dengan akar kuadrat dari jumlah amplop yang dibagi menjadi uang. Ini datang dari "sempurna" memainkan beberapa permainan kecil di mana semua amplop memiliki nilai yang hampir sama.

Masalah selanjutnya adalah bagaimana menentukan " jumlah efektif amplop." Dalam semua kasus, jumlah amplop diketahui persis dengan melacak apa yang telah Anda lihat dan lakukan. Sesuatu seperti {234.235.236} pasti tiga amplop, {231.232.233.234.235} pasti 5, tetapi {1,2.234.235.236} harus benar-benar dihitung sebagai 3 dan bukan 5 amplop karena 1 dan 2 hampir tidak berharga, dan Anda tidak akan pernah LULUS pada 234 jadi Anda kemudian dapat mengambil 1 atau 2. Saya punya ide untuk menggunakan entropi Shannon untuk menentukan jumlah efektif amplop.

Saya menargetkan perhitungan saya ke situasi di mana nilai-nilai amplop didistribusikan secara seragam selama beberapa interval, yang merupakan apa yang terjadi selama pertandingan. Jika saya mengambil {2,4,7,8,9} dan memperlakukannya sebagai distribusi probabilitas, entropinya adalah 1,50242. Kemudian saya lakukan exp()untuk mendapatkan 4.49254 sebagai jumlah efektif amplop.

Taksiran hadiah dari {2,4,7,8,9} adalah 30 * 4.4925^-0.5 * 4/3 = 18.87

Jumlah pastinya 18.1167.

Ini bukan perkiraan yang tepat, tapi saya benar-benar bangga dengan seberapa baik ini cocok dengan data ketika amplop didistribusikan secara seragam dalam suatu interval. Saya tidak yakin dengan pengali yang benar (saya menggunakan 4/3 untuk saat ini) tetapi di sini adalah tabel data tidak termasuk pengali.

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

Regresi linier antara yang diharapkan dan aktual memberikan nilai R ^ 2 sebesar 0,999994 .

Langkah saya berikutnya untuk meningkatkan jawaban ini adalah meningkatkan estimasi ketika jumlah amplop mulai menjadi kecil, yaitu ketika amplop tidak kira-kira didistribusikan secara seragam dan ketika masalahnya mulai menjadi butiran.


Sunting: Jika ini dianggap layak bitcoin, saya baru saja mendapat alamat di 1PZ65cXxUEEcGwd7E8i7g6qmvLDGqZ5JWg. Terima kasih! (Ini di sini sejak penulis tantangan membagikan hadiah.)

PhiNotPi
sumber
Secara tidak sengaja mengirimi Anda 20k satoshi lebih dari 805.479. Sebagai referensi, jumlah itu seharusnya menjadi skor Anda. Selamat menikmati kesalahanku :)
LivingInformation
Apakah Anda akan menjalankan angka dengan putaran lebih banyak? Berdasarkan apa yang saya lihat, ada sedikit variasi, dan 500 tidak cukup untuk mendapatkan median yang stabil. Skor saya sangat dekat dengan Anda jika saya hanya menjalankan 500 putaran, tetapi semuanya tergantung pada bagaimana angka acak jatuh. Jika saya menggunakan seed variabel, dan melakukan 500 run beberapa kali, saya mungkin bisa mendapatkan skor yang lebih tinggi.
Reto Koradi
@RetoKoradi saya pasti akan melakukan lebih banyak putaran.
PhiNotPi