Ekspektasi positif dari permainan yang tidak bergantung pada strategi Ballmer

 (gukov.dev)
1 poin oleh GN⁺ 2024-09-08 | 1 komentar | Bagikan ke WhatsApp
  • Teka-teki tebak angka Steve Ballmer adalah permainan mencari angka antara 1 hingga 100; pencarian biner tetap bisa dieksploitasi, tetapi dengan strategi campuran pemain dapat menciptakan nilai harapan positif terlepas dari pilihan lawan
  • Ballmer beranggapan bahwa bahkan dengan pilihan acak nilai harapannya negatif dan ia bisa memilih angka yang paling lama ditebak, tetapi John Graham-Cumming membantah bahwa untuk pilihan acak nilai harapannya adalah $0.20
  • Dalam pola pencarian tetap, setidaknya 37 angka dari 100 membutuhkan 6 pertanyaan sehingga bisa menimbulkan kerugian; jika lawan mengetahui strateginya, ia bisa memaksa pemain kalah setiap kali
  • Solusinya adalah strategi campuran dalam teori permainan, yaitu memilih secara probabilistik salah satu dari beberapa strategi pencarian murni, lalu merata-ratakan selisih menang-kalah per angka agar tidak ada angka yang merugikan
  • Contoh strategi yang ditemukan dengan menyelesaikan masalah program linear memakai scipy.linprog() menghasilkan laba harapan rata-rata $0.16 jika Ballmer memilih acak, dan laba harapan terburuk $0.14 bahkan jika ia memilih secara adversarial

Teka-teki tebak angka dan bantahan sebelumnya

  • Teka-teki yang konon disukai Ballmer adalah permainan di mana lawan memikirkan sebuah angka antara 1 hingga 100, dan setiap kali pemain menebak, lawan memberi tahu apakah angkanya lebih tinggi atau lebih rendah
  • Imbalannya adalah $5 jika benar pada tebakan pertama, lalu $4, $3, $2, $1, $0, dan setelah itu pemain membayar $1, $2, $3
  • Ballmer menganggap permainan ini tidak layak dimainkan karena dua alasan
    • Bahkan jika angka dipilih secara acak, ada banyak angka yang menghasilkan kerugian sehingga ia menilai nilai harapannya negatif
    • Ia menganggap dirinya bisa memilih secara strategis angka yang paling lama ditemukan oleh pencarian biner
  • John Graham-Cumming dalam “Steve Ballmer’s incorrect binary search interview question” membantah bahwa jika Ballmer memilih angka secara acak, nilai harapannya justru positif, yaitu $0.20
  • Lebih jauh lagi, bahkan ketika Ballmer memilih angka secara strategis, kita tetap bisa menemukan strategi dengan nilai harapan positif

Kelemahan pencarian biner tetap

  • Jika pemain selalu memakai strategi pencarian biner yang sama, maka 37 dari 100 angka membutuhkan 6 pertanyaan untuk menemukan jawabannya
  • Jika Ballmer mengetahui strategi tetap itu, ia bisa memilih salah satu dari 37 angka “kalah” tersebut dan memaksa pemain merugi
  • Kerentanan ini tidak terbatas pada satu bentuk pencarian biner tertentu
    • Dalam pola pencarian tetap apa pun, setidaknya 37 angka akan menghasilkan kerugian
    • Jika lawan memilih angka-angka itu, pemain akan merugi setiap saat

Menghadapi dengan strategi campuran

  • Alih-alih menetapkan satu pola pencarian, siapkan beberapa pola pencarian lalu pada awal permainan pilih salah satunya secara probabilistik dan gunakan sampai akhir
  • Dalam teori permainan, ini disebut strategi campuran yang dibangun dari beberapa strategi murni
  • Untuk angka yang sama, suatu pola pencarian bisa membuatnya menjadi angka menang, sementara pola lain bisa membuatnya menjadi angka kalah
  • Tujuan strategi campuran adalah merata-ratakan keuntungan harapan untuk tiap angka agar semua angka memiliki nilai harapan positif

Mencari strategi dengan program linear

  • Tujuannya bukan mencari strategi optimal yang memaksimalkan nilai harapan pada kasus terburuk, yaitu keseimbangan Nash, melainkan menemukan sembarang strategi yang menang untuk semua angka
  • Setiap strategi murni dapat dinyatakan sebagai vektor kemenangan panjang 100 V = (v_1, .., v_100)
    • v_k adalah keuntungan harapan ketika Ballmer memilih angka k
    • Misalnya, pencarian biner bisa memiliki nilai seperti v_50 = 5, v_25 = 4, v_0 = -1
  • Jika strategi campuran memilih strategi murni V_k dengan probabilitas p_k, maka vektor kemenangan totalnya menjadi V_mixed = Σ p_i V_i
  • Untuk menemukan strategi yang menang, diperlukan kombinasi linear yang memenuhi syarat berikut
    • Setiap elemennya harus positif
    • Karena koefisiennya adalah probabilitas, nilainya tidak boleh negatif
  • Ini adalah masalah program linear yang khas, dan dapat diselesaikan dengan scipy.optimize.linprog dari SciPy
  • Dengan menjadikan beberapa variasi pencarian biner sebagai himpunan strategi murni dan memasukkannya ke dalam kode yang memakai scipy.linprog(), diperoleh strategi campuran yang menang

Strategi contoh dan hasil

  • Kode lengkap tersedia di gukoff/ballmer_puzzle
  • Hasil awalnya adalah $0.07 per permainan, lalu Arthur O’Dwyer menambahkan strategi murni baru untuk meningkatkan hasilnya
  • Kinerja strategi campuran yang telah ditingkatkan adalah sebagai berikut
    • Rata-rata laba jika Ballmer memilih secara acak: $0.16
    • Laba terburuk jika Ballmer memilih secara adversarial: $0.14
  • Strategi campuran contoh menggabungkan beberapa variasi pencarian biner dengan probabilitas kecil
    • Probabilitas 0.4714%: tebakan pertama 29, lalu tebak titik tengah interval, dan jika seri pilih sisi kiri
    • Probabilitas 0.1691%: tebakan pertama 33, lalu tebak titik tengah, dan jika seri pilih sisi kiri
    • Probabilitas 0.1299%: tebakan pertama 36, lalu tebak titik tengah, dan jika seri pilih sisi kanan
    • Probabilitas 3.3341%: tebakan pertama 37, lalu tebak titik tengah, dan jika seri pilih sisi kanan
    • Probabilitas 1.7818%: tebakan pertama 43, lalu pilih elemen paling kanan dalam interval yang tidak menambah kompleksitas kasus terburuk
    • Probabilitas 1.1608%: tebakan pertama 44, lalu pilih elemen paling kiri dalam interval yang tidak menambah kompleksitas kasus terburuk
    • Probabilitas 2.1310%: tebakan pertama 42, lalu pilih elemen di ujung interval yang tidak menambah kompleksitas kasus terburuk
  • Strategi lengkapnya terdiri dari 74 baris, dan daftar penuh yang dihilangkan bisa dilihat di winning strategy di GitHub
  • Jika laba rata-rata 14 sen per permainan sebanding dengan waktu yang dikeluarkan, maka permainan ini tetap layak dimainkan meski Ballmer yang mengusulkannya

Bacaan terkait

1 komentar

 
GN⁺ 2024-09-08
Opini Hacker News

  • Tulisan terkait terbaru: Pertanyaan wawancara binary search yang keliru dari Steve Ballmer - https://news.ycombinator.com/item?id=41434637 - September 2024, 240 komentar

  • Tulisan ini penerapannya keren, tetapi sepertinya melewatkan inti persoalan
    Argumen Ballmer pada dasarnya soal tail risk. Jika yang diutamakan adalah bertahan hidup, nilai harapan sama sekali bukan patokan yang baik untuk bertaruh. Karena kesempatan hanya ada satu kali. Ini sama alasannya dengan tidak masuk akalnya mempertaruhkan seluruh harta setiap kali di poker muncul kartu yang “secara ekspektasi” akan menang; dalam beberapa putaran saja hampir pasti bangkrut
    Entah rata-ratanya +$0.07 atau apa pun, lebar distribusinya jelas bisa turun ke bawah 0. Secara rata-rata, peluang menang mungkin sedikit lebih tinggi daripada peluang kalah, tetapi dalam kenyataan Anda hanya menerima satu hasil. Kalau tujuannya adalah menang atau tamat, lebih baik tidak melakukannya, kecuali Anda memang ingin berutang kepada Ballmer
    Yang lebih menarik adalah melakukan simulasi Monte Carlo terhadap strategi ini dan melihat distribusi menang-kalahnya. Dengan begitu pilihannya mungkin tidak sejelas itu
    Kalau bisa memainkan gim ini beberapa triliun kali, tentu saja boleh dikuras habis :P

    • Saya tidak tahu dari mana munculnya klaim bahwa “argumen Ballmer pada dasarnya soal tail risk”. Dalam wawancara, saya tidak melihat ia membuat klaim seperti itu. Penjelasan soal dan jawabannya disajikan hanya dari sudut pandang nilai harapan untuk satu kali permainan, dan twist-nya adalah pemilihan angka secara adversarial, bukan risiko bangkrut
      Sebagai contoh tail risk pun kurang bagus. Dalam strategi yang jelas, ekornya luar biasa tebal
    • Benar. Paradoks Sankt-Peterburg menunjukkan bahwa secara intuitif kita mengetahui hal itu. Saya memberi tanda kutip pada “paradoks” karena menurut saya ini lebih merupakan reaksi yang normal daripada sebuah paradoks
      Sam Bankman-Fried sangat menyukai nilai harapan, dan terkenal pernah mengatakan bahwa ia akan melakukan lempar koin yang jika sisi depan keluar akan menggandakan “nilai” dunia, tetapi jika sisi belakang keluar akan menghancurkan dunia
      Ringkasnya, Paradoks Sankt-Peterburg adalah sebagai berikut. Koin adil dilempar sampai sisi depan muncul, dan pemain menerima $2^n jika n adalah jumlah lemparan koin. Jika sisi depan muncul pada lemparan pertama, ia mendapat $2; pada lemparan kedua $4; pada lemparan ketiga $8; pada lemparan kesepuluh $1024 (2^10), dan seterusnya. Mudah ditunjukkan bahwa nilai harapan gim ini mendekati tak terhingga
      Jadi orang yang sepenuhnya rasional seharusnya bersedia membayar praktis berapa pun untuk memainkan gim ini. Karena uang berhingga berapa pun lebih kecil daripada tak terhingga, keuntungan yang diharapkan selalu positif
      Namun mungkin hampir tidak ada orang yang mau membayar jutaan dolar untuk memainkan gim itu. SBF mungkin pengecualian
      Ini hanya menjadi paradoks jika Anda menganggapnya menunjukkan bahwa orang tidak “rasional”. Dalam kenyataannya, ini tampak berarti bahwa nilai harapan bukan ukuran risiko yang baik, dan semua orang tahu itu
      Tulisan yang sangat lengkap dan menarik tentang Paradoks Sankt-Peterburg: https://plato.stanford.edu/entries/paradox-stpetersburg/
    • Saya tidak setuju. Menurut saya Ballmer memang keliru
      Berbeda dari kebanyakan orang di sini, saya pikir pertanyaan semacam ini cukup baik untuk melihat bagaimana seseorang berpikir. Jika punya latar belakang matematika/statistik/ilmu komputer, setidaknya orang itu seharusnya bisa memulai percakapan tentang masalah ini
      Namun jika asumsi disembunyikan atau batasan tak berdasar ditambahkan sesuka hati sehingga menjadi jebakan, dari situ saya tidak bisa menerimanya
      Jika pertanyaannya “apakah Anda akan memainkan gim ini”, terjemahan matematis yang rasional adalah “tentukan apakah nilai harapannya lebih besar dari 0”. Jika ingin membahas tail risk, fungsi utilitas harus dinyatakan, dan bisa saja asimetris bagi kedua pemain. Dan harus jelas dikatakan bahwa itu memang maksudnya
    • Saya rasa ini tidak tepat. Kebanyakan orang tidak akan bangkrut karena kehilangan 1 dolar. Jika itu konteksnya, berarti Steve sangat gagal menyampaikan konteks tersebut
      Jujur saja, sepertinya Steve tidak benar-benar memahami kedalaman matematis dari masalah ini
    • Kriteria Kelly
      Jika bertaruh lebih besar daripada rasio Kelly, risiko bangkrut meningkat, terutama dalam jangka panjang
      https://en.m.wikipedia.org/wiki/Kelly_criterion
      Saya tidak mengatakan ini berlaku pada situasi di tulisan asli. Namun ini relevan dengan komentar induk, dan sangat berguna dalam banyak situasi seperti investasi

  • Saat Ballmer mengatakan “adversarial”, saya membayangkan strategi seperti ini. Sebenarnya ia sama sekali tidak perlu memilih angka tetap di awal. Pada setiap tebakan, ia cukup memberikan jawaban yang menyisakan jumlah kemungkinan angka terbanyak, dan dengan begitu strategi apa pun bisa dijamin kalah

    • Benar. Saya tidak tahu apakah itu memang maksud sebenarnya, tetapi kalau iya, lucu karena itu membuat seluruh analisis matematis ini sepenuhnya tidak berarti
      Tulisan aslinya menyajikan strategi acak yang rumit yang menjamin rata-rata minimal $0.07 terhadap adversary mana pun. Sebaliknya, Ballmer cukup menunda “pilihan” dan mengulur-ulur saja untuk membuat Anda menebak tujuh kali setiap kali, sehingga harus membayar 1 dolar
      Kalau Anda berharap mendapat rata-rata $0.07, berapa ronde yang akan Anda mainkan sebelum sadar bahwa Anda sedang ditipu?
    • Komentar ini seharusnya berada lebih atas
      Tulisan aslinya menarik, tetapi mengasumsikan “adversarial” dalam arti yang sangat lemah, yaitu Ballmer tetap berkomitmen pada suatu pilihan awal
      Menariknya, jika Ballmer memakai commitment scheme, pemain bisa memverifikasi hal ini [1]. Misalnya, saat permainan dimulai Ballmer membuat 500 bit acak, menambahkan angka yang dipilihnya dari rentang 1–100, lalu meng-hash hasilnya dan mengirim hash itu. Setelah permainan selesai, ia mengirim 500 bit acak tersebut, dan pemain dapat menggabungkan angka pilihan yang kini diungkap dengan bit-bit itu lalu meng-hash-nya untuk memeriksa apakah hasilnya sama dengan hash yang dikirim di awal. Jika Ballmer berbohong dan ingin mengubah angkanya, ia harus menemukan 500 bit yang, saat digabungkan dengan angka lain, tetap menghasilkan hash semula, dan itu sulit
      [1]: https://en.wikipedia.org/wiki/Commitment_scheme
    • Saya juga berpikir begitu. Rasanya seperti Absurdle, varian adversarial dari Wordle: https://qntm.org/files/absurdle/absurdle.html
      Itu dibuat oleh pembuat HATERIS, varian Tetris yang selalu memberi blok terburuk
    • Dari cara aturannya ditulis, tampaknya maksudnya ia memilih satu angka dan mempertahankannya. Karena disebut “ada angka di kepalanya”. Tentu saja ada pewawancara yang memelintir aturan seperti adu kecerdikan agar terlihat pintar, tetapi sepertinya bukan itu maksudnya di sini
    • Dalam analisis competitive ratio untuk algoritme online, memang seperti ini. Adversary boleh berubah pikiran sesuka hati, dan hanya perlu berkomitmen pada keputusan yang sudah dibuat di masa lalu

  • Edit: Ah, bukan. Komentar ini salah. Terima kasih kepada fgna yang sudah menunjukkan kekeliruannya
    Sepertinya ada pembuktian yang lebih sederhana bahwa Ballmer adversarial bisa dikalahkan. Hasil ekspektasinya persis sama besarnya dengan binary search melawan Ballmer acak
    Nama algoritme saya adalah “binary search dengan offset acak”. Caranya begini

    1. Pilih angka acak antara 0 dan 100, lalu sebut itu offset
    2. Jalankan algoritme binary search, tetapi pada setiap langkah tambahkan offset ke nilainya dan gunakan sisa pembagian dengan 100
      Selesai. Sekarang, meskipun Ballmer mengetahui strategi ini, ia tidak bisa memilih angka tertentu untuk membuat performanya lebih buruk. Jadi hasil ekspektasinya tetap $0.20 per permainan, dan lebih baik daripada strategi yang diusulkan di tulisan
    • Sayangnya angka-angkanya bukan melingkar :( Kalau memberi offset pada angka awal, bukankah binary search tidak bekerja optimal? Bayangkan angkanya kurang dari 50 tetapi mulai menebak dari 60; sekarang yang harus dicari bukan 25 angka, melainkan 30 angka, jadi tidak optimal
    • Keren. Lebih mudah dipahami jika membayangkan angka 1–100 ditempatkan di sekeliling permukaan jam. Ini seperti memutar jam secara acak sebelum memulai binary search biasa dari atas

  • Di antara banyak hal yang Ballmer salah, tampaknya ini juga salah satunya

    • Ballmer memang benar saat bertaruh pada Microsoft
    • Saya ingin bisa salah seperti Ballmer. Saldo bersih dari keputusan-keputusannya bernilai puluhan miliar dolar
    • Anda juga harus menunjukkan hal-hal yang pernah Anda salah agar kami bisa menilai
    • Favorit pribadi saya: https://www.youtube.com/shorts/rCszxibClKE

  • Ini, teman-teman, adalah contoh sempurna mengapa proses wawancara teknis modern benar-benar gila

    • Apakah ini benar-benar contoh sempurna wawancara teknis modern yang rusak?
      Pertanyaan Ballmer tampak adil jika melihat kompleksitas jawaban yang ia harapkan
      Kandidat mungkin akan memberikan jawaban yang secara matematis salah, tetapi dalam prosesnya ia menunjukkan cara berpikir dan sedikit mendemonstrasikan prinsip ilmu komputer
      Perlu diingat karier Ballmer panjang. Jika ia benar-benar mengajukan pertanyaan ini, kemungkinan itu terjadi pada era 80-an, dan saat itu tidak ada yang mengharapkan orang memberi solusi rumit seperti yang dijelaskan dalam tulisan
      Kalau seseorang memberi jawaban yang benar, itu luar biasa dan layak langsung direkrut. Tetapi menurut saya pertanyaan ini tidak rusak secara mendasar. Karena baik memilih bertaruh maupun tidak, jawaban apa pun harus dibenarkan dengan baik
    • Agar adil, Steve Ballmer adalah pemimpin yang buruk, dan kalau ia harus menjalani wawancara teknis, ia mungkin tidak akan lolos. Microsoft tidak akan stagnan selama 10 tahun sebelum Satya Nadella mengambil alih dan membangkitkan kembali perusahaan
    • Benarkah begitu? Sebagai pewawancara, kalau saya terpaksa mengajukan pertanyaan ini dan kandidat berkata “sebenarnya ini salah. Alasannya begini”, itu sinyal yang sangat baik. Bukankah biasanya orang memang melakukan itu?
      Umumnya selalu ada diskusi dengan semua pewawancara, dan tidak sekadar melihat “apakah kandidat menjawab soal dengan benar”. Secara pribadi saya menganggap banyak soal wawancara Big Tech itu bodoh, tetapi setelah mengalaminya dari kedua sisi, menurut saya prosesnya tidak serusak yang dibayangkan
    • Saya tidak bekerja di industri teknologi, tetapi saya selalu mengira pertanyaan seperti ini dirancang untuk menunjukkan kemampuan memecahkan masalah, terlepas dari benar atau tidaknya jawaban
      Dalam kasus ini, kira-kira menunjukkan bahwa seseorang bisa bernalar tentang binary search dan menunjukkan bahwa keuntungan rata-ratanya adalah 0,20 dolar
    • Menurut saya tidak apa-apa selama dipakai untuk mengetahui apakah kedua pihak akan senang bekerja bersama. Namun makin sering ini berubah menjadi kuis, atau sesuatu yang lebih buruk
      Meski begitu, setidaknya berkat itu kita mendapat fiksi berkualitas seperti https://aphyr.com/posts/340-reversing-the-technical-intervie... dan sekuelnya

  • Artikel yang menganalisis keseimbangan Nash secara lebih luas, termasuk solusi numerik untuk keseluruhan gim, ada di https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...

  • Kekayaan bersih Steve Ballmer adalah 120 miliar dolar AS, jadi jika satu putaran gim memakan waktu 30 detik, diperlukan 1,6 juta tahun untuk memenangkan semuanya

    • Tinggal biarkan komputer bermain. AI di komputer saya melawan AI Ballmer. Artinya menjalankan 1 triliun 683 miliar 605 juta 1984 gim komputer dalam 30 detik

  • Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
    Ini buku yang sangat bagus yang membahas strategi campuran dalam teori permainan
    Contoh motivasi yang ada di buku itu juga sangat bagus
    “Ada dua kartu, As dan 2. Pemain A mengambil salah satu secara acak, dan B tidak melihat kartu mana yang diambil. Jika A mengambil As, ia mengatakan ‘saya punya As’ dan meminta 1 dolar kepada lawan. Jika A mengambil 2, ia bisa (A1) mengatakan ‘saya punya As’ dan meminta 1 dolar kepada lawan, atau (A2) mengaku bahwa ia punya 2 dan memberi lawan 1 dolar
    Jika lawan secara sukarela menerima 1 dolar, ia tidak punya pilihan selain menerimanya. Namun jika diminta 1 dolar, ia bisa (B1) percaya bahwa A punya As dan memberi 1 dolar, atau (B2) meminta verifikasi untuk melihat apakah ucapan A benar. Jika A benar-benar punya As, B harus membayar 2 dolar kepada A. Sebaliknya, jika A melakukan bluffing dan punya 2, A membayar 2 dolar kepada B
    Analisis gim ini dan tentukan strategi optimal serta payoff harapan masing-masing pemain”