Ballmer की रणनीति से स्वतंत्र इस गेम का सकारात्मक expected value

 (gukov.dev)
1 पॉइंट द्वारा GN⁺ 2024-09-08 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • Steve Ballmer का number-guessing puzzle 1~100 के बीच का नंबर खोजने वाला गेम है। इसमें fixed binary search का counter किया जा सकता है, लेकिन mixed strategy का उपयोग करने पर प्रतिद्वंद्वी की पसंद से स्वतंत्र रूप से positive expected value बनाया जा सकता है
  • Ballmer का मानना था कि random choice में भी expected value negative है और वह ऐसा नंबर चुन सकता है जिसे खोजने में सबसे ज़्यादा समय लगे, लेकिन John Graham-Cumming ने तर्क दिया कि random choice पर expected value $0.20 है
  • Fixed search pattern में 100 नंबरों में से कम-से-कम 37 नंबर ऐसे होते हैं जिनके लिए 6 सवाल पूछने पड़ते हैं, जिससे नुकसान हो सकता है; इसलिए अगर प्रतिद्वंद्वी रणनीति जानता हो तो वह हर बार खिलाड़ी को हरा सकता है
  • समाधान है कई pure search strategies में से किसी एक को probability के साथ चुनने वाली game theory की mixed strategy, जो नंबर-दर-नंबर जीत-हार के अंतर को average करके प्रतिकूल नंबरों को खत्म करती है
  • scipy.linprog() से linear programming problem हल करके मिली एक उदाहरण रणनीति में, अगर Ballmer random चुने तो औसतन $0.16, और adversarial तरीके से चुने तो worst case में $0.14 का expected profit मिलता है

नंबर-गेसिंग पहेली और पहले का प्रतिवाद

  • Ballmer को पसंद आने वाली यह पहेली ऐसी है कि प्रतिद्वंद्वी 1~100 के बीच एक नंबर सोचता है, और खिलाड़ी हर guess पर यह जानता है कि जवाब उससे बड़ा है या छोटा
  • इनाम की संरचना यह है: पहली guess में सही होने पर $5, उसके बाद $4, $3, $2, $1, $0, और फिर उसके बाद खिलाड़ी को $1, $2, $3 देना पड़ता है
  • Ballmer का मानना था कि यह गेम नहीं खेलना चाहिए, दो कारणों से
    • random तरीके से नंबर चुनने पर भी expected value negative है क्योंकि नुकसान देने वाले नंबर ज़्यादा हैं
    • वह रणनीतिक रूप से ऐसा नंबर चुन सकता है जिसे binary search से खोजने में सबसे ज़्यादा समय लगे
  • John Graham-Cumming ने “Steve Ballmer’s incorrect binary search interview question” में इसका प्रतिवाद किया और कहा कि अगर Ballmer random तरीके से नंबर चुने तो expected value $0.20 positive होती है
  • इससे आगे बढ़कर, Ballmer अगर रणनीतिक रूप से नंबर चुने तब भी positive expected value देने वाली रणनीति खोजी जा सकती है

Fixed binary search की कमजोरी

  • अगर खिलाड़ी हमेशा एक ही binary search strategy का उपयोग करे, तो 100 नंबरों में से 37 नंबर ऐसे होंगे जिन्हें सही जवाब तक पहुँचने के लिए 6 सवाल चाहिए
  • अगर Ballmer उस fixed strategy को जानता हो, तो वह इन 37 “हारने वाले” नंबरों में से कोई एक चुनकर खिलाड़ी पर नुकसान थोप सकता है
  • यह कमजोरी केवल किसी एक खास binary search तक सीमित नहीं है
    • किसी भी fixed search pattern में कम-से-कम 37 नंबर नुकसान कराते हैं
    • अगर प्रतिद्वंद्वी उन नंबरों को चुने, तो खिलाड़ी हर बार नुकसान उठाएगा

Mixed strategy से जवाब

  • एक ही search pattern को fix करने के बजाय, कई search patterns तैयार किए जाते हैं और गेम शुरू होने पर उनमें से एक को probability के साथ चुना जाता है, जिसे अंत तक बनाए रखा जाता है
  • game theory में इसे कई pure strategies पर आधारित mixed strategy कहा जाता है
  • एक ही नंबर किसी एक search pattern में जीतने वाला नंबर हो सकता है और किसी दूसरे pattern में हारने वाला
  • mixed strategy का लक्ष्य हर नंबर के expected payoff को average करके ऐसा बनाना है कि सभी नंबरों पर expected value positive रहे

Linear programming से रणनीति खोजना

  • लक्ष्य worst case expected value को maximize करने वाली optimal strategy, यानी Nash equilibrium, खोजना नहीं है; बल्कि ऐसी कोई भी strategy खोजना है जो सभी नंबरों पर जीत दे
  • हर pure strategy को लंबाई 100 के win vector V = (v_1, .., v_100) के रूप में लिखा जा सकता है
    • v_k वह expected payoff है जब Ballmer नंबर k चुनता है
    • उदाहरण के लिए, binary search में v_50 = 5, v_25 = 4, v_0 = -1 जैसे मान हो सकते हैं
  • अगर mixed strategy pure strategy V_k को probability p_k से चुनती है, तो कुल win vector V_mixed = Σ p_i V_i होगा
  • जीतने वाली strategy पाने के लिए ऐसा linear combination चाहिए जो इन शर्तों को पूरा करे
    • हर तत्व positive होना चाहिए
    • coefficients probability हैं, इसलिए वे negative नहीं हो सकते
  • यह एक सामान्य linear programming समस्या है, और इसे SciPy के scipy.optimize.linprog से हल किया जा सकता है
  • अलग-अलग binary search variants को pure strategy set बनाकर scipy.linprog() में डाले गए code से winning mixed strategy मिलती है

उदाहरण रणनीति और परिणाम

  • पूरा code gukoff/ballmer_puzzle में उपलब्ध है
  • शुरुआती परिणाम प्रति गेम $0.07 था, और Arthur O’Dwyer ने नई pure strategies जोड़कर प्रदर्शन बेहतर किया
  • बेहतर mixed strategy का प्रदर्शन इस प्रकार है
    • Ballmer के random चुनने पर औसत profit: $0.16
    • Ballmer के adversarial चुनने पर worst-case profit: $0.14
  • उदाहरण mixed strategy कई binary search variants को छोटी probabilities के साथ मिलाती है
    • probability 0.4714%: पहली guess 29, उसके बाद interval के बीच का मान guess करना, और tie होने पर बाईं ओर चुनना
    • probability 0.1691%: पहली guess 33, उसके बाद बीच का मान guess करना, और tie होने पर बाईं ओर चुनना
    • probability 0.1299%: पहली guess 36, उसके बाद बीच का मान guess करना, और tie होने पर दाईं ओर चुनना
    • probability 3.3341%: पहली guess 37, उसके बाद बीच का मान guess करना, और tie होने पर दाईं ओर चुनना
    • probability 1.7818%: पहली guess 43, उसके बाद interval के भीतर सबसे दायाँ तत्व चुनना जो worst-case complexity न बढ़ाए
    • probability 1.1608%: पहली guess 44, उसके बाद interval के भीतर सबसे बायाँ तत्व चुनना जो worst-case complexity न बढ़ाए
    • probability 2.1310%: पहली guess 42, उसके बाद interval के किनारे वाला तत्व चुनना जो worst-case complexity न बढ़ाए
  • पूरी strategy 74 lines लंबी है, और छोड़ी गई पूरी सूची GitHub की winning strategy में देखी जा सकती है
  • अगर प्रति गेम औसतन 14 सेंट का मुनाफ़ा लगाए गए समय के हिसाब से ठीक लगे, तो Ballmer यह गेम प्रस्तावित करे तब भी इसे खेलना उचित हो सकता है

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-09-08
Hacker News की राय

  • हाल की संबंधित पोस्ट: Steve Ballmer का गलत binary search interview question - https://news.ycombinator.com/item?id=41434637 - सितंबर 2024, 240 comments

  • इस लेख में application तो शानदार है, लेकिन लगता है कि core point छूट गया है
    Ballmer की दलील मूल रूप से tail risk के बारे में है। अगर survival को अहमियत देते हैं, तो expected value betting criterion के तौर पर बिल्कुल अच्छा नहीं है। क्योंकि मौका सिर्फ एक बार मिलता है। यह उसी वजह जैसा है कि poker में हर बार “expected” winning hand आने पर अपनी पूरी net worth दांव पर लगाना समझदारी नहीं है; कुछ ही hands में आपका दिवालिया होना लगभग तय हो जाएगा
    average +$0.07 हो या कुछ भी, distribution की चौड़ाई साफ तौर पर 0 से नीचे भी जा सकती है। औसतन जीतने की संभावना हारने की संभावना से थोड़ी ज्यादा हो सकती है, लेकिन असल में आपको सिर्फ एक outcome मिलता है। अगर goal जीतना या पूरी तरह खत्म हो जाना है, और आप Ballmer के कर्जदार नहीं बनना चाहते, तो बेहतर है न खेलें
    ज्यादा दिलचस्प यह होगा कि इस strategy की Monte Carlo simulation करके जीत-हार का distribution देखा जाए। तब choice शायद इतनी साफ न लगे
    अगर आप यह game कुछ trillion बार खेल सकते हैं, तो जाहिर है जमकर लूट लेना चाहिए :P

    • “Ballmer की दलील मूल रूप से tail risk है” यह कहां से आया, समझ नहीं आता। interview में ऐसा दावा करते नहीं दिखते। problem और answer explanation सिर्फ game के एक trial के expected value के नजरिए से रखे गए हैं, और twist numbers की adversarial choice है, ruin risk नहीं
      tail risk example के तौर पर भी यह खास नहीं है। obvious strategy में tail बेहद fat है
    • सही। St. Petersburg paradox दिखाता है कि intuitively हमें यह बात पता है। “paradox” को quotes में रखने की वजह यह है कि मेरे हिसाब से यह paradox से ज्यादा normal reaction है
      Sam Bankman-Fried expected value को बहुत पसंद करते थे, और famously कहा था कि वे ऐसा coin toss करेंगे जिसमें heads आने पर दुनिया की “value” दोगुनी हो जाए, लेकिन tails आने पर दुनिया नष्ट हो जाए
      संक्षेप में St. Petersburg paradox यह है। एक fair coin तब तक उछाला जाता है जब तक heads न आ जाए, और player को coin उछालों की संख्या n होने पर $2^n मिलते हैं। पहले toss पर heads आए तो $2, दूसरे पर $4, तीसरे पर $8, दसवें पर $1024(2^10), इसी तरह। यह आसानी से दिखाया जा सकता है कि इस game की expected value infinity की ओर जाती है
      इसलिए पूरी तरह rational व्यक्ति को इस game को खेलने के लिए practically कोई भी रकम देने को तैयार होना चाहिए। क्योंकि कोई भी finite पैसा infinity से कम है, इसलिए expected gain हमेशा positive है
      लेकिन शायद ही कोई इस game को खेलने के लिए millions of dollars देने को तैयार होगा। SBF शायद exception हों
      यह तभी paradox है जब आपको लगे कि यह दिखाता है कि लोग “rational” नहीं हैं। असल में यह लगता है कि expected value risk को measure करने का अच्छा पैमाना नहीं है, और सबको यह पता है
      St. Petersburg paradox पर बहुत comprehensive और दिलचस्प लेख: https://plato.stanford.edu/entries/paradox-stpetersburg/
    • सहमत नहीं। मेरे हिसाब से Ballmer बस गलत थे
      यहां ज्यादातर लोगों के उलट, मुझे लगता है कि इस तरह के questions यह देखने का काफी अच्छा तरीका हैं कि कोई व्यक्ति कैसे सोचता है। अगर math/statistics/computer science background है, तो कम से कम इस problem पर conversation शुरू कर पाने की उम्मीद करनी चाहिए
      लेकिन अगर assumptions छिपाई जाएं या अपनी मर्जी से बेकार constraints जोड़कर इसे trap बना दिया जाए, तो वहीं से यह स्वीकार्य नहीं लगता
      अगर question “क्या आप यह game खेलेंगे” है, तो उसका rational mathematical translation है “तय करें कि expected value 0 से ज्यादा है या नहीं।” tail risk की बात करनी हो तो utility function specify करना होगा, और वह दोनों players के लिए asymmetric भी हो सकता है। और यह साफ कहना होगा कि यही intent है
    • मुझे यह सही नहीं लगता। ज्यादातर लोग 1 dollar खोने से दिवालिया नहीं होते। अगर context यही था, तो Steve उस context को convey करने में बुरी तरह fail हुए
      सच कहूं तो लगता है Steve ने इस problem की mathematical depth ठीक से नहीं समझी
    • Kelly criterion
      Kelly fraction से ज्यादा bet करने पर, खासकर long term में, ruin risk बढ़ जाता है
      https://en.m.wikipedia.org/wiki/Kelly_criterion
      यह नहीं कह रहा कि यह original post की situation पर लागू होता है। बस parent comment से relevant है, और investing जैसी कई situations में बहुत useful है

  • जब Ballmer ने “adversarial” कहा, तो मेरे दिमाग में यही strategy आई थी। असल में उसे शुरुआत में कोई fixed number चुनने की बिल्कुल जरूरत नहीं है। हर guess पर वह ऐसा जवाब दे सकता है जिससे संभव numbers सबसे ज्यादा बचे रहें, और तब किसी भी strategy के खिलाफ वह हार सुनिश्चित कर सकता है

    • सही। पता नहीं उसका असली इरादा यही था या नहीं, लेकिन अगर था, तो मजेदार बात यह है कि इससे यह सारी mathematical analysis पूरी तरह बेकार हो जाती है
      मूल लेख किसी भी adversary के खिलाफ औसतन कम से कम $0.07 की guarantee देने वाली एक जटिल randomized strategy देता है। दूसरी तरफ Ballmer सिर्फ “चुनाव” टालकर और खींचते रहकर हर बार सात guesses करवाकर 1 dollar दिलवा सकता है
      अगर आपको उम्मीद हो कि आप औसतन $0.07 कमाएंगे, तो ठगे जाने का एहसास होने से पहले आप कितने games खेलेंगे?
    • यह comment और ऊपर होना चाहिए
      मूल लेख दिलचस्प है, लेकिन वह “adversarial” को बहुत कमजोर अर्थ में मानता है, जहां Ballmer फिर भी किसी initial choice पर commit करता है
      दिलचस्प बात यह है कि अगर Ballmer commitment scheme इस्तेमाल करे, तो player यह verify कर सकता है [1]। उदाहरण के लिए game शुरू होने पर Ballmer 500 random bits बनाए, उसमें 1~100 range में चुना हुआ number जोड़े, फिर result को hash करके वह hash भेज दे। game खत्म होने पर वह 500 random bits भेजे, और player अब publicly revealed चुने हुए number और उन bits को concatenate करके hash करे और देखे कि शुरुआत में भेजा hash वही आता है या नहीं। अगर Ballmer झूठ बोलकर number बदलना चाहे, तो उसे किसी दूसरे number के साथ concatenate करने पर भी वही original hash देने वाले 500 bits ढूंढने होंगे, जो मुश्किल है
      [1]: https://en.wikipedia.org/wiki/Commitment_scheme
    • मैंने भी यही सोचा था। यह Wordle के adversarial variant Absurdle जैसा लगता है: https://qntm.org/files/absurdle/absurdle.html
      इसे HATERIS के creator ने बनाया है, जो Tetris का ऐसा variant है जो हमेशा सबसे खराब block देता है
    • नियमों की wording से लगता है कि वह एक number चुनता है और उसी पर बना रहता है। उसने कहा था कि “उसके दिमाग में एक number है”। बेशक कुछ interviewers नियमों को दिमागी चाल की तरह मोड़कर खुद को smart दिखाने की कोशिश करते हैं, लेकिन यहां ऐसा इरादा नहीं लगता
    • online algorithms के competitive ratio analysis में ऐसा ही किया जाता है। adversary अपना मन मनमर्जी से बदल सकता है, और उसे सिर्फ उन decisions पर commit होना होता है जो वह past में already ले चुका है

  • Edit: आह, नहीं। यह comment गलत है। ध्यान दिलाने के लिए fgna का धन्यवाद
    मुझे लगता है adversarial Ballmer को हराने का एक और simple proof है। random Ballmer के खिलाफ binary search जितना ही expected result मिलता है
    मेरे algorithm का नाम “random offset binary search” है। तरीका यह है

    1. 0~100 के बीच एक random number चुनें और उसे offset कहें
    2. binary search algorithm चलाएं, लेकिन हर step पर value में offset जोड़ें और 100 से divide करने पर remainder इस्तेमाल करें
      बस। अब Ballmer को यह strategy पता हो तब भी वह कोई खास number चुनकर performance को और खराब नहीं कर सकता। इसलिए expected result अभी भी प्रति game $0.20 है, और लेख में सुझाई गई strategy से बेहतर है
    • अफसोस, numbers circular नहीं हैं :( initial number में offset देने पर binary search optimally काम नहीं करती, है न? सोचिए number 50 से छोटा है लेकिन आप 60 से guess करना शुरू करते हैं; अब 25 नहीं, 30 numbers search करने पड़ेंगे, इसलिए यह optimal नहीं है
    • बढ़िया। इसे समझने का अच्छा तरीका है कि 1~100 के numbers घड़ी के डायल की परिधि पर रखे हैं। यह conventional binary search को ऊपर से शुरू करने से पहले घड़ी को random तरीके से घुमाने जैसा है

  • Ballmer जिन बहुत सी बातों में गलत था, यह भी शायद उन्हीं में से एक है

    • Ballmer ने Microsoft पर bet तो सही लगाया था
    • काश मैं Ballmer की तरह गलत हो पाता। उसके decisions का net balance अरबों dollars में था
    • ताकि हम judge कर सकें, आपको वे चीजें भी दिखानी चाहिए जिनमें आप गलत थे
    • मेरा personal favorite: https://www.youtube.com/shorts/rCszxibClKE

  • दोस्तों, यही वह perfect example है जो दिखाता है कि modern technical interview process pure madness क्यों है

    • क्या यह broken modern technical interviews का perfect example है?
      Ballmer का सवाल, जिस answer complexity की उसने उम्मीद की होगी उसे देखते हुए, fair लगता है
      candidate शायद mathematically गलत answer देगा, लेकिन process में अपनी thinking दिखाएगा और computer science principles भी थोड़ा demonstrate करेगा
      Ballmer का career लंबा रहा है, यह ध्यान रखना चाहिए। अगर उसने यह सवाल सच में पूछा था, तो शायद 80s में पूछा होगा, और उस समय कोई भी लेख में बताए गए complex solution की उम्मीद नहीं करता
      सही answer देना बड़ी बात होती और तुरंत hire करने लायक signal होता। लेकिन यह सवाल fundamentally broken नहीं लगता। bet करना हो या न करना हो, किसी भी answer को अच्छे से justify करना पड़ेगा
    • fairness में कहें तो Steve Ballmer एक खराब leader था, और अगर उसे technical interview देना पड़ता तो वह pass नहीं होता। Satya Nadella के संभालने और company को फिर उठाने से पहले Microsoft 10 साल तक ठहरी भी नहीं रहती
    • सच में? अगर interviewer के तौर पर मुझे यह सवाल पूछना ही पड़े और candidate कहे “असल में यह गलत है। वजह यह है”, तो यह बहुत अच्छा signal है। आमतौर पर लोग ऐसा नहीं करते क्या?
      सामान्य तौर पर हर interviewer के साथ discussion होता है, और सिर्फ “candidate ने problem solve की या नहीं” नहीं देखा जाता। personally मुझे कई Big Tech interview problems बेवकूफी भरी लगती हैं, लेकिन दोनों sides से experience के बाद मुझे process उतना broken नहीं लगता जितना लोग सोचते हैं
    • मैं tech industry में काम नहीं करता, लेकिन मैंने हमेशा सोचा है कि ऐसे सवाल सही answer से independent होकर problem-solving ability दिखाने के लिए design किए जाते हैं
      इस case में बस यह दिखाना है कि आप binary search के बारे में reason कर सकते हैं, और average profit $0.20 है यह दिखा सकते हैं
    • जब तक इसका उपयोग यह जानने के लिए हो कि दोनों साथ काम करके enjoy करेंगे या नहीं, तब तक ठीक है। लेकिन increasingly यह quiz या उससे भी खराब चीज में बदल जाता है
      फिर भी इसकी बदौलत https://aphyr.com/posts/340-reversing-the-technical-intervie... और उसके sequels जैसी अच्छी fiction मिलती है

  • पूरे गेम के numerical solution सहित Nash equilibrium का अधिक व्यापक विश्लेषण https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s... पर है

  • Steve Ballmer की net worth 120 अरब डॉलर है, इसलिए अगर एक गेम में 30 सेकंड लगते हैं, तो सब कुछ जीतने में 16 लाख साल लगेंगे

    • कंप्यूटरों को आपस में खेलने दे सकते हैं। मेरे कंप्यूटर का AI बनाम Ballmer का AI। 30 सेकंड के भीतर 1 खरब 6830 अरब 3605 करोड़ 1984 कंप्यूटर गेम चलाने होंगे

  • Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
    गेम थ्योरी की mixed strategies पर यह बहुत अच्छी किताब है
    किताब में दिए गए motivating examples भी बेहतरीन हैं
    “दो कार्ड हैं: एक Ace और एक 2। खिलाड़ी A इनमें से एक को random तरीके से निकालता है, और B यह नहीं देख पाता कि कौन-सा कार्ड निकला। अगर A ने Ace निकाला है, तो वह कहता है ‘मेरे पास Ace है’ और सामने वाले से 1 डॉलर मांगता है। अगर A ने 2 निकाला है, तो वह या तो (A1) ‘मेरे पास Ace है’ कहकर सामने वाले से 1 डॉलर मांग सकता है, या (A2) मान सकता है कि उसके पास 2 है और सामने वाले को 1 डॉलर दे सकता है
    अगर सामने वाला स्वेच्छा से 1 डॉलर पाता है, तो उसे स्वीकार करना ही होगा। लेकिन अगर उससे 1 डॉलर मांगा जाता है, तो वह या तो (B1) मान ले कि A के पास Ace है और 1 डॉलर दे, या (B2) जांच की मांग करे और देखे कि A की बात सच है या नहीं। अगर A के पास सचमुच Ace है, तो B को A को 2 डॉलर देने होंगे। इसके उलट, अगर A bluff कर रहा था और उसके पास 2 था, तो A, B को 2 डॉलर देगा
    इस गेम का विश्लेषण करें और हर खिलाड़ी की optimal strategy और expected payoff निकालें”