Ballmer Stratejisinden Bağımsız Pozitif Beklenen Değerli Oyun

 (gukov.dev)
1 puan yazan GN⁺ 2024-09-08 | 1 yorum | WhatsApp'ta paylaş
  • Steve Ballmer’ın sayı tahmin etme bulmacası, 1 ile 100 arasındaki bir sayıyı bulma oyunu; sabit bir ikili arama alt edilebilir, ancak karma strateji kullanıldığında karşı tarafın seçimine bakılmaksızın pozitif beklenen değer elde edilebilir
  • Ballmer, rastgele seçimde bile beklenen değerin negatif olduğunu ve kendisinin uzun sürecek sayıları seçebileceğini düşünüyordu; ancak John Graham-Cumming, rastgele seçimde beklenen değerin $0.20 olduğunu söyleyerek buna karşı çıktı
  • Sabit arama desenlerinde 100 sayıdan en az 37’si 6 soru gerektirerek kayıp yaratabilir; bu yüzden karşı taraf stratejiyi bilirse oyuncuyu her seferinde kaybettirebilir
  • Çözüm, birden fazla saf arama stratejisinden birini olasılıksal olarak seçen oyun teorisindeki karma stratejidir; bu yöntem, sayı bazındaki kazanç/kayıp farklarını ortalayarak dezavantajlı sayıları ortadan kaldırır
  • scipy.linprog() ile doğrusal programlama problemi çözülerek bulunan örnek strateji, Ballmer rastgele seçerse ortalama $0.16, düşmanca seçse bile en kötü durumda $0.14 beklenen kâr sağlar

Sayı tahmin etme bulmacası ve önceki karşı argüman

  • Ballmer’ın sevdiği söylenen bulmaca, karşı tarafın 1 ile 100 arasında bir sayı tuttuğu ve oyuncu her tahminde bulunduğunda sayının daha yüksek mi daha düşük mü olduğunun söylendiği bir oyundur
  • Ödül, ilk tahminde bilinirse $5; sonrasında $4, $3, $2, $1, $0; daha sonraki denemelerden itibaren ise oyuncunun $1, $2, $3 ödemesi şeklindedir
  • Ballmer iki nedenle bu oyunun oynanmaması gerektiğini düşünüyordu
    • Rastgele sayı seçilse bile kayıp yaratan çok sayıda sayı olduğu için beklenen değerin negatif olduğuna karar vermişti
    • İkili aramada en uzun sürecek sayıları stratejik olarak seçebileceğini düşünüyordu
  • John Graham-Cumming, “Steve Ballmer’s incorrect binary search interview question” yazısında, Ballmer rastgele sayı seçerse beklenen değerin $0.20 ile pozitif olduğunu söyleyerek buna karşı çıktı
  • Bunun da ötesinde, Ballmer’ın sayıyı stratejik olarak seçtiği durumda bile beklenen değeri pozitif olan bir strateji bulunabilir

Sabit ikili aramanın zayıflığı

  • Oyuncu her zaman aynı ikili arama stratejisini kullanırsa, 100 sayıdan 37’si doğru cevabı bulmak için 6 soru gerektirir
  • Ballmer bu sabit stratejiyi biliyorsa bu 37 “kaybettiren” sayıdan birini seçerek oyuncuya kaybı dayatabilir
  • Bu zayıflık yalnızca belirli bir ikili aramayla sınırlı değildir
    • Herhangi bir sabit arama deseninde en az 37 sayı kayıp yaratır
    • Karşı taraf bu sayıları seçerse oyuncu her seferinde zarar eder

Karma stratejiyle karşılık vermek

  • Tek bir arama desenini sabitlemek yerine, birden çok arama deseni hazırlanır ve oyun başlarken bunlardan biri olasılıksal olarak seçilip sonuna kadar korunur
  • Oyun teorisinde buna birden çok saf stratejiye dayalı karma strateji denir
  • Aynı sayı, bir arama deseninde kazandıran sayı iken başka bir arama deseninde kaybettiren sayı olabilir
  • Karma stratejinin amacı, her sayı için beklenen getiriyi ortalayarak tüm sayılarda beklenen değeri pozitif hale getirmektir

Doğrusal programlamayla strateji bulmak

  • Amaç, en kötü durum beklenen değerini maksimize eden optimal stratejiyi, yani Nash dengesini bulmak değil; tüm sayılarda kazandıran herhangi bir strateji bulmaktır
  • Her saf strateji, uzunluğu 100 olan bir kazanç vektörü V = (v_1, .., v_100) ile ifade edilebilir
    • v_k, Ballmer k sayısını seçtiğinde beklenen getiridir
    • Örneğin ikili arama v_50 = 5, v_25 = 4, v_0 = -1 gibi değerlere sahip olabilir
  • Karma strateji saf strateji V_k’yi p_k olasılığıyla seçerse toplam kazanç vektörü V_mixed = Σ p_i V_i olur
  • Kazandıran bir strateji bulmak için şu koşulları sağlayan bir doğrusal kombinasyon gerekir
    • Her eleman pozitif olmalıdır
    • Katsayılar olasılık olduğu için negatif olmamalıdır
  • Bu tipik bir doğrusal programlama problemidir ve SciPy’nin scipy.optimize.linprog aracıyla çözülebilir
  • Birden fazla ikili arama varyasyonu saf strateji kümesi olarak oluşturulup scipy.linprog()’a verilen kodda kazandıran bir karma strateji elde edilir

Örnek strateji ve sonuçlar

  • Tüm kod gukoff/ballmer_puzzle deposunda yer alıyor
  • İlk sonuç oyun başına $0.07 idi; Arthur O’Dwyer yeni saf stratejiler ekleyerek performansı iyileştirdi
  • İyileştirilmiş karma stratejinin performansı şöyle
    • Ballmer rastgele seçtiğinde ortalama kâr: $0.16
    • Ballmer düşmanca seçtiğinde en kötü durum kârı: $0.14
  • Örnek karma strateji, birden çok ikili arama varyasyonunu küçük olasılıklarla karıştırır
    • Olasılık 0.4714%: ilk tahmin 29; ardından aralığın ortasını tahmin et, eşitlik olursa solu seç
    • Olasılık 0.1691%: ilk tahmin 33; ardından ortayı tahmin et, eşitlik olursa solu seç
    • Olasılık 0.1299%: ilk tahmin 36; ardından ortayı tahmin et, eşitlik olursa sağı seç
    • Olasılık 3.3341%: ilk tahmin 37; ardından ortayı tahmin et, eşitlik olursa sağı seç
    • Olasılık 1.7818%: ilk tahmin 43; ardından en kötü durum karmaşıklığını artırmayan aralıktaki en sağdaki öğeyi seç
    • Olasılık 1.1608%: ilk tahmin 44; ardından en kötü durum karmaşıklığını artırmayan aralıktaki en soldaki öğeyi seç
    • Olasılık 2.1310%: ilk tahmin 42; ardından en kötü durum karmaşıklığını artırmayan aralığın uç tarafındaki öğeyi seç
  • Tam strateji 74 satır uzunluğunda; atlanan listenin tamamı GitHub’daki winning strategy bölümünde görülebilir
  • Oyun başına ortalama 14 sent kâr harcanan zamana değiyorsa, Ballmer bu oyunu önerse bile oynamaya değer

İlgili okumalar

1 yorum

 
GN⁺ 2024-09-08
Hacker News yorumları

  • Yakın zamanda ilgili yazı: Steve Ballmer'ın hatalı ikili arama mülakat sorusu - https://news.ycombinator.com/item?id=41434637 - Eylül 2024, 240 yorum

  • Bu yazıda uygulama hoş ama asıl nokta kaçırılmış gibi
    Ballmer'ın argümanı özünde kuyruk riski ile ilgili. Hayatta kalmayı önemsiyorsanız beklenen değer, bahis ölçütü olarak hiç iyi değildir. Çünkü yalnızca tek bir fırsatınız var. Pokerde “beklenen olarak” kazanacak el her geldiğinde tüm servetinizi ortaya koymanın mantıksız olmasıyla aynı neden; birkaç el içinde neredeyse kesin olarak batarsınız
    Ortalama +$0.07 olsa da ne olursa olsun dağılımın genişliği açıkça 0'ın altına da inebilir. Ortalama olarak kazanma olasılığı kaybetme olasılığından biraz yüksek olabilir, ama gerçekte yalnızca tek bir sonuç alırsınız. Hedef ya kazanmak ya da mahvolmaksa, Ballmer'a borçlanmak istemiyorsanız oynamamak daha iyidir
    Daha ilginç olan, bu stratejiyi Monte Carlo simülasyonu ile çalıştırıp galibiyet/mağlubiyet dağılımını görmek. O zaman seçim o kadar da bariz olmayabilir
    Oyunu birkaç trilyon kez falan oynayabiliyorsanız elbette sonuna kadar sömürün :P

    • “Ballmer'ın argümanı özünde kuyruk riski” ifadesinin nereden çıktığını bilmiyorum. Röportajda böyle bir iddiada bulunmuş gibi görünmüyor. Sorun ve cevap açıklaması yalnızca oyunun tek bir denemesinin beklenen değeri açısından sunuluyor; ters köşe, sayının hasmane seçimi, iflas riski değil
      Kuyruk riski örneği olarak da pek iyi değil. Bariz stratejide kuyruk aşırı derecede kalın
    • Doğru. St. Petersburg paradoksu, bunu sezgisel olarak bildiğimizi gösteriyor. “Paradoks” sözcüğünü tırnak içine almamın nedeni, bunun paradokstan çok normal bir tepki olduğunu düşünmem
      Sam Bankman-Fried beklenen değeri çok severdi ve yazı gelirse dünyanın “değerini” ikiye katlayacak, tura gelirse dünyayı yok edecek bir yazı-tura atacağını söylemesiyle ünlü
      Özetle St. Petersburg paradoksu şöyle. Adil bir para, yazı gelene kadar atılır ve oyuncu, para atma sayısı n ise $2^n alır. İlk atışta yazı gelirse $2, ikincide gelirse $4, üçüncüde $8, onuncuda $1024(2^10) alır. Bu oyunun beklenen değerinin sonsuza yaklaştığını göstermek kolaydır
      Dolayısıyla tamamen rasyonel bir kişi, bu oyunu oynamak için fiilen herhangi bir tutarı ödemeye istekli olmalıdır. Her sonlu para miktarı sonsuzdan küçük olduğundan, beklenen kazanç her zaman pozitiftir
      Ama bu oyunu oynamak için milyonlarca dolar ödemek isteyecek kişi muhtemelen neredeyse yoktur. SBF belki istisna olabilir
      Bu, ancak insanların “rasyonel” olmadığını gösterdiğini düşündüğünüzde paradokstur. Gerçekte ise beklenen değerin risk ölçmek için iyi bir ölçüt olmadığı ve herkesin bunu bildiği anlamına geliyor gibi görünüyor
      St. Petersburg paradoksu hakkında çok kapsamlı ve ilginç bir yazı: https://plato.stanford.edu/entries/paradox-stpetersburg/
    • Katılmıyorum. Bence Ballmer sadece yanılmış
      Buradaki çoğu kişiden farklı olarak, bu tür soruların bir insanın nasıl düşündüğünü görmek için epey iyi bir yöntem olduğunu düşünüyorum. Matematik/istatistik/bilgisayar bilimi geçmişiniz varsa, en azından bu problem hakkında bir sohbet başlatabilmeniz beklenir
      Ancak varsayımları saklayıp ya da kafanıza göre anlamsız kısıtlar ekleyerek bunu tuzağa dönüştürürseniz, işte oradan itibaren ikna edici olmuyor
      Soru “bu oyunu oynar mısın” ise bunun rasyonel matematiksel çevirisi “beklenen değerin 0'dan büyük olup olmadığına karar ver”dir. Kuyruk riskinden söz etmek istiyorsanız fayda fonksiyonunu açıkça belirtmeniz gerekir; bu iki oyuncu için asimetrik de olabilir. Ayrıca niyetin bu olduğunu açıkça söylemeniz gerekir
    • Bence bu doğru değil. Çoğu insan 1 dolar kaybetti diye iflas etmez. Bağlam buysa, Steve o bağlamı aktarmakta ciddi biçimde başarısız olmuş demektir
      Açıkçası Steve'in bu problemin matematiksel derinliğini tam kavrayamadığını düşünüyorum
    • Kelly kriteri
      Kelly oranından fazla bahis yaparsanız, özellikle uzun vadede iflas riskiniz artar
      https://en.m.wikipedia.org/wiki/Kelly_criterion
      Orijinal yazıdaki duruma uygulanır demiyorum. Ama üst yorumla ilgili ve yatırım gibi birçok durumda çok yararlı

  • Ballmer “hasmane” dediğinde aklıma böyle bir strateji gelmişti. Aslında başlangıçta sabit bir sayı seçmesine hiç gerek yok. Her tahminde, olası sayıların en fazlasını geride bırakan yanıtı vermesi yeterli; böylece hangi strateji olursa olsun yenilgiyi garanti edebilir

    • Doğru. Gerçekten amaçlanan bu muydu bilmiyorum ama öyleyse, tüm bu matematiksel analizi tamamen anlamsız kılması komik
      Asıl yazı, herhangi bir hasma karşı ortalama en az $0.07 garanti eden karmaşık bir rastgele strateji sunuyor. Oysa Ballmer “seçimi” erteleyip işi uzatmakla her seferinde yedi tahmin yaptırıp 1 dolar ödetebilir
      Ortalama $0.07 kazanmayı bekliyorsanız, dolandırıldığınızı fark edene kadar kaç el oynarsınız?
    • Bu yorum daha yukarıda olmalı
      Asıl yazı ilginç ama Ballmer’ın hâlâ bir başlangıç seçimine bağlandığını varsayan, çok zayıf anlamda bir “hasmane” durum kabul ediyor
      İlginç biçimde, Ballmer bir commitment scheme kullanırsa oyuncu bunu doğrulayabilir [1]. Örneğin oyunun başında Ballmer 500 rastgele bit üretir, buna 1–100 aralığında seçtiği sayıyı ekler ve sonucu hash’leyip bu hash’i gönderir. Oyun bitince 500 rastgele biti gönderir; oyuncu da artık açıklanan seçilmiş sayıyı bu bitlerle birleştirip hash’lediğinde başta gönderilen hash’in çıkıp çıkmadığını kontrol edebilir. Ballmer yalan söyleyip sayıyı değiştirmek isterse, başka bir sayıyla birleştirildiğinde de aynı hash’i verecek 500 bit bulması gerekir; bu da zordur
      [1]: https://en.wikipedia.org/wiki/Commitment_scheme
    • Ben de öyle düşünmüştüm. Wordle’ın hasmane bir varyantı olan Absurdle gibi: https://qntm.org/files/absurdle/absurdle.html
      Her zaman en kötü bloğu veren Tetris varyantı HATERIS’in yaratıcısı tarafından yapılmış
    • Kuralların ifade edilişine göre onun bir sayı seçip buna bağlı kaldığı anlamı çıkıyor. “Aklında bir sayı var” dendiğine göre. Elbette bazı mülakatçılar, kendilerini zeki göstermek için kuralları bir akıl oyununa çevirir; ama burada niyet bu değil gibi
    • Çevrimiçi algoritmaların rekabet oranı analizinde böyle yapılır. Hasım fikrini istediği gibi değiştirebilir; yalnızca geçmişte zaten verdiği kararlara bağlı kalması gerekir

  • Düzenleme: Ah, hayır. Bu yorum yanlış. Bunu işaret eden fgna’ya teşekkürler
    Hasmane Ballmer’ı yenebileceğinize dair daha basit bir kanıt var gibi. Rastgele Ballmer’a karşı ikili aramayla tam olarak aynı beklenen sonuç elde ediliyor
    Algoritmamın adı “rastgele ofsetli ikili arama”. Şöyle çalışıyor

    1. 0–100 arasında rastgele bir sayı seçin ve buna offset deyin
    2. İkili arama algoritmasını çalıştırın; ancak her adımda değere offset ekleyip 100’e göre kalanını kullanın
      Hepsi bu. Artık Ballmer bu stratejiyi bilse bile belirli bir sayı seçip performansı daha kötü hâle getiremez. Dolayısıyla beklenen sonuç hâlâ oyun başına $0.20 ve yazıda önerilen stratejiden daha iyi
    • Ne yazık ki sayılar dairesel değil :( Başlangıç sayısına ofset verirseniz ikili arama optimum çalışmaz, değil mi? Sayının 50’den küçük olduğunu ama 60’tan tahmin etmeye başladığınızı düşünün; artık 25 değil 30 sayı aramanız gerekir, bu yüzden optimum değil
    • Harika. 1–100 arasındaki sayıların bir saat kadranının çevresine yerleştirildiğini hayal etmek anlamayı kolaylaştırıyor. Mevcut ikili aramayı en üstten başlatmadan önce saati rastgele döndürmek gibi

  • Ballmer’ın yanıldığı birçok şey arasında, bu da onlardan biri gibi görünüyor

    • Ballmer’ın Microsoft’a bahis oynadığı doğruydu
    • Ballmer gibi yanılabilmeyi isterdim. Kararlarının net bakiyesi milyarlarca dolardı
    • Yargılayabilmemiz için senin yanıldığın şeyleri de göstermelisin
    • Kişisel favorim: https://www.youtube.com/shorts/rCszxibClKE

  • İşte dostlar, modern teknik mülakat sürecinin neden saf delilik olduğunu gösteren kusursuz örnek bu

    • Bu, bozuk modern teknik mülakatın kusursuz bir örneği mi?
      Ballmer’ın sorusu, beklediği yanıtın karmaşıklığı düşünüldüğünde adil görünüyor
      Aday muhtemelen matematiksel olarak yanlış bir yanıt verecektir; ama bu süreçte düşünme biçimini gösterir ve biraz bilgisayar bilimi ilkesini de sergiler
      Ballmer’ın kariyerinin uzun olduğunu düşünmek gerek. Bu soruyu gerçekten sorduysa muhtemelen 80’lerdeydi ve o dönemde kimse yazıda anlatılan karmaşık çözümün verilmesini beklemezdi
      Doğru yanıtı sunsaydı bu harika bir şey olurdu ve hemen işe alınacak biri sayılırdı. Ama bu soru temelden bozuk gibi gelmiyor. Bahse girsin ya da girmesin, hangi yanıt olursa olsun iyi gerekçelendirmesi gerektiği için
    • Adil olmak gerekirse Steve Ballmer berbat bir liderdi ve teknik mülakata girmesi gerekseydi geçemezdi. Satya Nadella devralıp şirketi yeniden ayağa kaldırana kadar Microsoft 10 yıl boyunca yerinde saymış da olmazdı
    • Gerçekten öyle mi? Bir mülakatçı olarak bu soruyu sormak zorunda kalsam ve aday “Aslında bu yanlış. Nedeni şu” dese, bu çok iyi bir işaret olurdu. İnsanlar genelde böyle yapmıyor mu?
      Genellikle tüm mülakatçılarla bir tartışma olur ve yalnızca “aday problemi çözdü mü”ye bakılmaz. Kişisel olarak birçok büyük teknoloji şirketi mülakat sorusunu aptalca buluyorum; ama iki tarafta da deneyimleyince sürecin düşündüğüm kadar bozuk olmadığı kanısındayım
    • Teknoloji sektöründe çalışmıyorum ama böyle soruların, doğru yanıttan bağımsız olarak problem çözme becerisini göstermek için tasarlandığını hep düşünmüştüm
      Bu durumda da ikili arama hakkında akıl yürütebildiğinizi ve ortalama kârın 0.20 dolar olduğunu gösterebildiğinizi ortaya koymak gibi
    • İki tarafın birlikte çalışmaktan keyif alıp almayacağını anlamak için kullanıldığı sürece bence sorun yok. Ama giderek daha sık bunun bir bilgi yarışmasına, hatta daha kötüsüne dönüştüğünü görüyoruz
      Yine de bu sayede https://aphyr.com/posts/340-reversing-the-technical-intervie... ve devamı gibi kaliteli kurmacalar elde ediyoruz

  • Oyunun tamamının sayısal çözümünü de içerecek şekilde Nash dengesini daha geniş analiz eden yazı https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s... adresinde

  • Steve Ballmer’ın net serveti 120 milyar dolar; bir oyunun 30 saniye sürdüğü varsayılırsa hepsini kazanmak 1,6 milyon yıl alır

    • Bilgisayarları birbirine oynatırsın. Benim bilgisayarımdaki yapay zeka Ballmer’ın yapay zekasına karşı. 30 saniye içinde 1 trilyon 683 milyar 360 milyon 51 bin 984 bilgisayar oyunu çalıştırmak yani

  • Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
    Oyun teorisindeki karma stratejiyi ele alan çok iyi bir kitap
    Kitaptaki motive edici örnek de harika
    “İki kart var: bir as ve bir 2. Oyuncu A bunlardan birini rastgele çeker; B hangi kartın çekildiğini göremez. A ası çektiyse ‘Elimde as var’ der ve rakibinden 1 dolar ister. A 2’yi çektiyse (A1) ‘Elimde as var’ deyip rakibinden 1 dolar isteyebilir ya da (A2) elinde 2 olduğunu itiraf edip rakibine 1 dolar verebilir
    Rakip gönüllü olarak 1 dolar alırsa bunu kabul etmek zorundadır. Ama kendisinden 1 dolar istenirse (B1) A’nın elinde as olduğuna inanıp 1 dolar verebilir ya da (B2) kontrol isteyip A’nın söylediğinin doğru olup olmadığını görebilir. A’nın elinde gerçekten as varsa B, A’ya 2 dolar ödemek zorundadır. Buna karşılık A blöf yapmışsa ve elinde 2 varsa A, B’ye 2 dolar öder
    Bu oyunu analiz edin ve her oyuncunun optimal stratejisini ve beklenen getirisini bulun”