เกมที่มีค่าคาดหมายเป็นบวกแม้ Ballmer จะเลือกเชิงกลยุทธ์

 (gukov.dev)
1 คะแนน โดย GN⁺ 2024-09-08 | 1 ความคิดเห็น | แชร์ทาง WhatsApp
  • ปริศนาทายตัวเลขของ Steve Ballmer เป็นเกมหาตัวเลขระหว่าง 1~100 ซึ่งการค้นหาแบบทวิภาคคงที่สามารถถูกแก้ทางได้ แต่ถ้าใช้ กลยุทธ์ผสม ก็สามารถสร้างค่าคาดหมายเป็นบวกได้ไม่ว่าคู่แข่งจะเลือกอย่างไร
  • Ballmer มองว่าแม้จะสุ่มเลือกตัวเลข ค่าคาดหมายก็ยังติดลบ และเขายังสามารถเลือกตัวเลขที่ทำให้ตนเองใช้เวลานานที่สุดได้ด้วย แต่ John Graham-Cumming โต้แย้งว่าเมื่อสุ่มเลือก ค่าคาดหมายคือ $0.20
  • ในรูปแบบการค้นหาแบบคงที่ จะมีอย่างน้อย 37 ตัวเลขจากทั้งหมด 100 ตัวที่ต้องใช้คำถาม 6 ครั้ง จึงทำให้เกิดการขาดทุน ดังนั้นถ้าคู่แข่งรู้กลยุทธ์ ก็สามารถทำให้ผู้เล่นแพ้ได้ทุกครั้ง
  • ทางแก้คือใช้ กลยุทธ์ผสม ตามทฤษฎีเกม โดยสุ่มเลือกหนึ่งในหลายกลยุทธ์การค้นหาแบบบริสุทธิ์ เพื่อเฉลี่ยผลแพ้ชนะของแต่ละตัวเลขและกำจัดตัวเลขที่เสียเปรียบ
  • ตัวอย่างกลยุทธ์ที่หาได้จากการแก้ปัญหาเชิงเส้นด้วย scipy.linprog() ให้ผลว่าถ้า Ballmer สุ่มเลือกจะมีกำไรเฉลี่ย $0.16 และแม้เลือกแบบเป็นปฏิปักษ์ก็ยังมีกำไรคาดหมายกรณีแย่ที่สุด $0.14

ปริศนาทายตัวเลขและข้อโต้แย้งเดิม

  • ปริศนาที่ Ballmer ชอบคือเกมที่อีกฝ่ายนึกตัวเลขระหว่าง 1~100 แล้วทุกครั้งที่ผู้เล่นทาย จะบอกว่าสูงไปหรือต่ำไป
  • รางวัลคือถ้าทายถูกครั้งแรกได้ $5 จากนั้นเป็น $4, $3, $2, $1, $0 และหลังจากนั้นผู้เล่นต้องจ่าย $1, $2, $3 ตามลำดับ
  • Ballmer มองว่าไม่ควรเล่นเกมนี้ด้วยเหตุผล 2 ข้อ
    • ต่อให้สุ่มเลือกตัวเลข ก็มีตัวเลขที่ขาดทุนจำนวนมากจนทำให้ค่าคาดหมายติดลบ
    • เขาสามารถเลือกตัวเลขที่ทำให้การค้นหาแบบทวิภาคใช้เวลานานที่สุดได้อย่างมีกลยุทธ์
  • John Graham-Cumming โต้แย้งใน “Steve Ballmer’s incorrect binary search interview question” ว่าถ้า Ballmer สุ่มเลือกตัวเลข ค่าคาดหมายจะเป็นบวกที่ $0.20
  • และไปไกลกว่านั้น ยังสามารถหากลยุทธ์ที่ให้ค่าคาดหมายเป็นบวกได้แม้ Ballmer จะเลือกตัวเลขอย่างมีกลยุทธ์

จุดอ่อนของการค้นหาแบบทวิภาคคงที่

  • หากผู้เล่นใช้ กลยุทธ์การค้นหาแบบทวิภาค เดิมทุกครั้ง ในบรรดา 100 ตัวเลขจะมี 37 ตัวที่ต้องใช้คำถามถึง 6 ครั้งกว่าจะตอบถูก
  • หาก Ballmer รู้กลยุทธ์คงที่นั้น เขาก็สามารถเลือกหนึ่งใน 37 ตัวเลขที่ “แพ้” เหล่านี้เพื่อบังคับให้ผู้เล่นขาดทุนได้
  • จุดอ่อนนี้ไม่ได้จำกัดอยู่แค่รูปแบบการค้นหาแบบทวิภาคแบบใดแบบหนึ่ง
    • ไม่ว่าจะเป็นรูปแบบการค้นหาแบบคงที่ใด ก็จะมีอย่างน้อย 37 ตัวเลขที่ทำให้ขาดทุน
    • หากคู่แข่งเลือกตัวเลขเหล่านั้น ผู้เล่นก็จะขาดทุนทุกครั้ง

รับมือด้วยกลยุทธ์ผสม

  • แทนที่จะยึดรูปแบบการค้นหาแบบเดียว ให้เตรียมรูปแบบการค้นหาหลายแบบไว้ แล้วเมื่อเริ่มเกมจึงสุ่มเลือกหนึ่งแบบตามความน่าจะเป็นและใช้แบบนั้นจนจบ
  • ในทฤษฎีเกม สิ่งนี้เรียกว่า กลยุทธ์ผสม ที่อิงจากหลาย กลยุทธ์บริสุทธิ์
  • แม้จะเป็นตัวเลขเดียวกัน แต่ในบางรูปแบบการค้นหาอาจเป็นตัวเลขที่ชนะ ขณะที่ในอีกรูปแบบอาจเป็นตัวเลขที่แพ้
  • เป้าหมายของกลยุทธ์ผสมคือเฉลี่ยผลตอบแทนคาดหมายของแต่ละตัวเลข เพื่อให้ทุกตัวเลขมีค่าคาดหมายเป็นบวก

ค้นหากลยุทธ์ด้วยการโปรแกรมเชิงเส้น

  • เป้าหมายไม่ใช่การหากลยุทธ์เหมาะที่สุดที่ทำให้ค่าคาดหมายกรณีแย่ที่สุดสูงสุด หรือ Nash equilibrium แต่เป็นการหากลยุทธ์ใดก็ได้ที่ชนะทุกตัวเลข
  • แต่ละกลยุทธ์บริสุทธิ์สามารถแทนได้ด้วย เวกเตอร์ชัยชนะ ความยาว 100 ตัว V = (v_1, .., v_100)
    • v_k คือผลตอบแทนคาดหมายเมื่อ Ballmer เลือกตัวเลข k
    • ตัวอย่างเช่น การค้นหาแบบทวิภาคอาจมีค่าอย่าง v_50 = 5, v_25 = 4, v_0 = -1
  • หากกลยุทธ์ผสมเลือกกลยุทธ์บริสุทธิ์ V_k ด้วยความน่าจะเป็น p_k เวกเตอร์ชัยชนะรวมจะเป็น V_mixed = Σ p_i V_i
  • หากต้องการหากลยุทธ์ที่ชนะ จำเป็นต้องมีการรวมเชิงเส้นที่ตรงตามเงื่อนไขต่อไปนี้
    • ทุกองค์ประกอบต้องเป็นบวก
    • สัมประสิทธิ์ต้องไม่ติดลบ เพราะเป็นความน่าจะเป็น
  • นี่เป็นปัญหา การโปรแกรมเชิงเส้น แบบคลาสสิก และสามารถแก้ได้ด้วย scipy.optimize.linprog ของ SciPy
  • เมื่อสร้างชุดกลยุทธ์บริสุทธิ์จากรูปแบบการค้นหาแบบทวิภาคหลายแบบ แล้วใส่ลงในโค้ดที่ใช้ scipy.linprog() ก็จะได้กลยุทธ์ผสมที่ชนะ

กลยุทธ์ตัวอย่างและผลลัพธ์

  • โค้ดทั้งหมดอยู่ที่ gukoff/ballmer_puzzle
  • ผลลัพธ์แรกเริ่มอยู่ที่ $0.07 ต่อเกม และ Arthur O’Dwyer ได้เพิ่มกลยุทธ์บริสุทธิ์ใหม่เพื่อปรับปรุงผลลัพธ์
  • ประสิทธิภาพของกลยุทธ์ผสมที่ปรับปรุงแล้วเป็นดังนี้
    • กำไรเฉลี่ยเมื่อ Ballmer สุ่มเลือก: $0.16
    • กำไรกรณีแย่ที่สุดเมื่อ Ballmer เลือกแบบเป็นปฏิปักษ์: $0.14
  • กลยุทธ์ผสมตัวอย่างจะผสมรูปแบบการค้นหาแบบทวิภาคหลายแบบด้วยความน่าจะเป็นเล็กน้อย
    • ความน่าจะเป็น 0.4714%: ทายครั้งแรกเป็น 29 จากนั้นทายค่ากลางของช่วง และถ้าเสมอกันให้เลือกฝั่งซ้าย
    • ความน่าจะเป็น 0.1691%: ทายครั้งแรกเป็น 33 จากนั้นทายค่ากลาง และถ้าเสมอกันให้เลือกฝั่งซ้าย
    • ความน่าจะเป็น 0.1299%: ทายครั้งแรกเป็น 36 จากนั้นทายค่ากลาง และถ้าเสมอกันให้เลือกฝั่งขวา
    • ความน่าจะเป็น 3.3341%: ทายครั้งแรกเป็น 37 จากนั้นทายค่ากลาง และถ้าเสมอกันให้เลือกฝั่งขวา
    • ความน่าจะเป็น 1.7818%: ทายครั้งแรกเป็น 43 จากนั้นเลือกสมาชิกที่อยู่ขวาสุดในช่วง โดยไม่เพิ่ม worst-case complexity
    • ความน่าจะเป็น 1.1608%: ทายครั้งแรกเป็น 44 จากนั้นเลือกสมาชิกที่อยู่ซ้ายสุดในช่วง โดยไม่เพิ่ม worst-case complexity
    • ความน่าจะเป็น 2.1310%: ทายครั้งแรกเป็น 42 จากนั้นเลือกสมาชิกที่ปลายช่วง โดยไม่เพิ่ม worst-case complexity
  • กลยุทธ์ฉบับสมบูรณ์มี 74 บรรทัด และรายการเต็มที่ละไว้สามารถดูได้ที่ winning strategy บน GitHub
  • หากกำไรเฉลี่ย 14 เซนต์ต่อเกมคุ้มกับเวลาที่ใช้ เกมนี้ก็น่าเล่นแม้ Ballmer จะเป็นฝ่ายเสนอมาก็ตาม

บทความที่เกี่ยวข้อง

1 ความคิดเห็น

 
GN⁺ 2024-09-08
ความคิดเห็นบน Hacker News

  • บทความที่เกี่ยวข้องล่าสุด: คำถามสัมภาษณ์เรื่องการค้นหาแบบไบนารี ที่ผิดพลาดของ Steve Ballmer - https://news.ycombinator.com/item?id=41434637 - กันยายน 2024, 240 ความคิดเห็น

  • ผมคิดว่าการประยุกต์ในบทความนี้เจ๋งดี แต่ดูเหมือนจะพลาดประเด็นหลักไป
    ข้อโต้แย้งของ Ballmer โดยเนื้อแท้แล้วเกี่ยวกับ tail risk ถ้าให้ความสำคัญกับการอยู่รอด expected value ก็ไม่ใช่เกณฑ์ที่ดีเลยสำหรับการเดิมพัน เพราะคุณมีโอกาสแค่ครั้งเดียว เหตุผลเดียวกับที่ในโป๊กเกอร์ การเอาทรัพย์สินทั้งหมดไปลงทุกครั้งที่ได้ไพ่ซึ่ง “ตาม expected value” แล้วน่าจะชนะนั้นไม่สมเหตุสมผล และภายในไม่กี่ตาคุณก็แทบจะแน่นอนว่าจะล้มละลาย
    ไม่ว่าค่าเฉลี่ยจะเป็น +$0.07 หรืออะไรก็ตาม ช่วงการกระจายของผลลัพธ์ย่อมลงไปต่ำกว่า 0 ได้ชัดเจน โดยเฉลี่ยแล้วโอกาสชนะอาจสูงกว่าโอกาสแพ้เล็กน้อย แต่ในความเป็นจริงคุณจะได้รับผลลัพธ์เพียงครั้งเดียว ถ้าเป้าหมายคือชนะหรือจบเห่ และถ้าคุณไม่ได้อยากเป็นหนี้ Ballmer ก็ไม่เล่นน่าจะดีกว่า
    สิ่งที่น่าสนใจกว่าคือการทำ Monte Carlo simulation กับกลยุทธ์นี้เพื่อดูการกระจายของชนะ/แพ้ แบบนั้นทางเลือกอาจไม่ได้ชัดเจนขนาดนั้นก็ได้
    ถ้าคุณเล่นเกมนี้ได้สักหลายล้านล้านครั้ง แน่นอนว่าก็กวาดให้เกลี้ยงได้เลย :P

    • ผมไม่รู้ว่า “ข้อโต้แย้งของ Ballmer โดยเนื้อแท้แล้วคือ tail risk” มาจากไหน ดูไม่เหมือนว่าเขาอ้างแบบนั้นในการสัมภาษณ์ คำอธิบายโจทย์และคำตอบถูกนำเสนอเฉพาะในมุมมอง expected value ของการเล่นเกมหนึ่งครั้งเท่านั้น และจุดพลิกคือการเลือกตัวเลขแบบมีปฏิปักษ์ ไม่ใช่ความเสี่ยงล้มละลาย
      แม้ใช้เป็นตัวอย่าง tail risk ก็ไม่ค่อยดี ในกลยุทธ์ที่เห็นได้ชัด tail นั้นหนามากแบบสุดโต่ง
    • ใช่แล้ว St. Petersburg paradox แสดงให้เห็นว่าเรารู้เรื่องนั้นโดยสัญชาตญาณ เหตุผลที่ผมใส่คำว่า “paradox” ในเครื่องหมายคำพูด คือผมมองว่านี่ไม่ใช่ paradox แต่เป็นปฏิกิริยาปกติ
      Sam Bankman-Fried ชอบ expected value มาก และเป็นที่รู้จักจากการบอกว่าเขาจะยอมโยนเหรียญที่ถ้าออกหัวจะเพิ่ม “มูลค่า” ของโลกเป็นสองเท่า แต่ถ้าออกก้อยจะทำลายโลก
      สรุปแล้ว St. Petersburg paradox เป็นแบบนี้: โยนเหรียญที่ยุติธรรมจนกว่าจะออกหัว และผู้เล่นจะได้รับ $2^n เมื่อ n คือจำนวนครั้งที่โยนเหรียญ ถ้าออกหัวครั้งแรกได้ $2 ครั้งที่สองได้ $4 ครั้งที่สามได้ $8 ครั้งที่สิบได้ $1024(2^10) อะไรทำนองนั้น เห็นได้ง่ายว่า expected value ของเกมนี้มุ่งไปหาอนันต์
      ดังนั้นคนที่มีเหตุผลอย่างสมบูรณ์ควรเต็มใจจ่ายแทบทุกจำนวนเงินเพื่อเล่นเกมนี้ เพราะเงินจำนวนจำกัดใด ๆ ก็ยังน้อยกว่าอนันต์ ทำให้ expected gain เป็นบวกเสมอ
      แต่คงแทบไม่มีใครยอมจ่ายหลายล้านดอลลาร์เพื่อเล่นเกมนั้น SBF อาจเป็นข้อยกเว้นก็ได้
      มันจะเป็น paradox ก็ต่อเมื่อคุณคิดว่านี่แสดงว่าผู้คนไม่ “มีเหตุผล” ในความเป็นจริงมันน่าจะหมายความว่า expected value ไม่ใช่มาตรวัดความเสี่ยงที่ดี และทุกคนก็รู้เรื่องนั้นอยู่แล้ว
      บทความที่ครบถ้วนและน่าสนใจมากเกี่ยวกับ St. Petersburg paradox: https://plato.stanford.edu/entries/paradox-stpetersburg/
    • ไม่เห็นด้วย ผมว่า Ballmer ก็แค่ผิด
      ต่างจากคนส่วนใหญ่ที่นี่ ผมคิดว่าคำถามแบบนี้เป็นวิธีที่ค่อนข้างดีในการดูว่าคนคิดอย่างไร ถ้ามีพื้นฐานคณิตศาสตร์/สถิติ/วิทยาการคอมพิวเตอร์ อย่างน้อยก็ควรเริ่มสนทนาเกี่ยวกับโจทย์นี้ได้
      แต่ถ้าซ่อนสมมติฐานหรือเพิ่มข้อจำกัดที่ไร้สาระตามใจตัวเองเพื่อทำให้เป็นกับดัก ผมก็เริ่มไม่รับแล้ว
      ถ้าคำถามคือ “จะเล่นเกมนี้ไหม” การแปลเป็นคณิตศาสตร์อย่างสมเหตุสมผลคือ “จงตัดสินว่า expected value มากกว่า 0 หรือไม่” ถ้าจะพูดถึง tail risk ก็ต้องระบุ utility function และมันอาจไม่สมมาตรสำหรับผู้เล่นสองฝ่ายด้วย และต้องบอกให้ชัดว่านั่นคือเจตนา
    • ผมว่าอันนี้ไม่ถูก คนส่วนใหญ่ไม่ได้ล้มละลายเพราะเสีย 1 ดอลลาร์ ถ้าบริบทเป็นแบบนั้น Steve ก็ล้มเหลวอย่างหนักในการสื่อบริบทนั้น
      พูดตรง ๆ ผมว่า Steve ไม่ได้เข้าใจ ความลึกทางคณิตศาสตร์ ของโจทย์นี้อย่างแท้จริง
    • Kelly criterion
      ถ้าเดิมพันมากกว่า Kelly fraction ความเสี่ยงล้มละลายจะเพิ่มขึ้น โดยเฉพาะในระยะยาว
      https://en.m.wikipedia.org/wiki/Kelly_criterion
      ไม่ได้บอกว่ามันใช้กับสถานการณ์ในบทความต้นฉบับนะ แค่เกี่ยวข้องกับคอมเมนต์แม่ และมีประโยชน์มากในหลายสถานการณ์ เช่น การลงทุน

  • ตอนที่ Ballmer พูดว่า “เป็นปฏิปักษ์” ผมนึกถึงกลยุทธ์แบบนี้ ที่จริงเขาไม่จำเป็นต้องเลือกตัวเลขคงที่ตั้งแต่แรกเลย แค่ตอบแต่ละครั้งด้วยคำตอบที่ทำให้เหลือตัวเลขที่เป็นไปได้มากที่สุดก็พอ และแบบนั้นไม่ว่ากลยุทธ์ไหนก็สามารถ รับประกันความพ่ายแพ้ ได้

    • ใช่เลย ไม่รู้ว่านั่นเป็นเจตนาจริง ๆ หรือเปล่า แต่ถ้าใช่ก็น่าขำตรงที่มันทำให้การวิเคราะห์ทางคณิตศาสตร์ทั้งหมดนี้ไร้ความหมายไปเลย
      บทความต้นฉบับเสนอกลยุทธ์สุ่มที่ซับซ้อน ซึ่งรับประกันค่าเฉลี่ยขั้นต่ำ $0.07 ต่อคู่ต่อสู้แบบปฏิปักษ์ทุกแบบได้ ในขณะที่ Ballmer แค่ผัดผ่อน “การเลือก” แล้วลากเกมไปเรื่อย ๆ ก็ทำให้ต้องทายเจ็ดครั้งทุกตาและจ่าย 1 ดอลลาร์ได้
      ถ้าคาดว่าจะทำเงินได้เฉลี่ย $0.07 คุณจะเล่นไปกี่ตาก่อนจะรู้ตัวว่ากำลังโดนหลอก?
    • คอมเมนต์นี้ควรอยู่สูงกว่านี้
      บทความต้นฉบับน่าสนใจ แต่สมมติ “ความเป็นปฏิปักษ์” ในความหมายที่อ่อนมาก คือมองว่า Ballmer ยัง commit กับตัวเลือกเริ่มต้นบางอย่างอยู่
      ที่น่าสนใจคือ ถ้า Ballmer ใช้ commitment scheme ผู้เล่นก็ตรวจสอบข้อเท็จจริงนี้ได้ [1] เช่น ตอนเริ่มเกม Ballmer สร้างบิตสุ่ม 500 บิต แล้วต่อท้ายด้วยตัวเลขที่เลือกในช่วง 1~100 จากนั้นแฮชผลลัพธ์แล้วส่งค่าแฮชนั้นให้ พอเกมจบ เขาส่งบิตสุ่ม 500 บิตมาให้ และผู้เล่นก็เอาตัวเลขที่เปิดเผยแล้วมาต่อกับบิตเหล่านั้นแล้วแฮช เพื่อตรวจสอบว่าได้ค่าแฮชที่ส่งมาตอนแรกหรือไม่ ถ้า Ballmer โกหกแล้วเปลี่ยนตัวเลข เขาต้องหาบิต 500 บิตที่เมื่อต่อกับตัวเลขอื่นแล้วได้ค่าแฮชเดิม ซึ่งทำได้ยาก
      [1]: https://en.wikipedia.org/wiki/Commitment_scheme
    • ผมก็คิดแบบนั้นเหมือนกัน ให้ความรู้สึกเหมือน Absurdle ซึ่งเป็นเวอร์ชันแบบปฏิปักษ์ของ Wordle: https://qntm.org/files/absurdle/absurdle.html
      ทำโดยผู้สร้าง HATERIS ซึ่งเป็นเวอร์ชันของ Tetris ที่ให้บล็อกแย่ที่สุดเสมอ
    • จากถ้อยคำของกฎ ดูเหมือนว่าเขาหมายถึงการเลือกตัวเลขหนึ่งตัวแล้วคงไว้ เพราะบอกว่า “มีตัวเลขอยู่ในหัว” แน่นอนว่าผู้สัมภาษณ์บางคนชอบบิดกฎเหมือนเล่นเกมชิงไหวชิงพริบเพื่อให้ตัวเองดูฉลาด แต่กรณีนี้ไม่น่าจะเป็นเจตนาแบบนั้น
    • ในการวิเคราะห์ competitive ratio ของอัลกอริทึมออนไลน์ เขาทำกันแบบนี้ คู่ต่อสู้สามารถเปลี่ยนใจได้ตามต้องการ และต้อง commit แค่กับการตัดสินใจที่ได้ทำไปแล้วในอดีตเท่านั้น

  • แก้ไข: อ้อ ไม่ใช่สิ คอมเมนต์นี้ผิด ขอบคุณ fgna ที่ชี้ให้เห็น
    ดูเหมือนจะมีการพิสูจน์ที่ง่ายกว่าว่าสามารถชนะ Ballmer แบบปฏิปักษ์ได้ ผลลัพธ์คาดหมายออกมาเท่ากับการค้นหาแบบทวิภาคเมื่อเจอกับ Ballmer แบบสุ่มพอดี
    อัลกอริทึมของผมชื่อ “การค้นหาแบบทวิภาคพร้อมออฟเซ็ตสุ่ม” วิธีคือ

    1. เลือกตัวเลขสุ่มระหว่าง 0~100 แล้วเรียกว่า offset
    2. ทำ อัลกอริทึมค้นหาแบบทวิภาค แต่ในแต่ละขั้นให้บวกค่า offset เข้าไปในค่า แล้วใช้เศษจากการหารด้วย 100
      จบ แค่นี้ต่อให้ Ballmer รู้กลยุทธ์นี้ ก็ไม่สามารถเลือกตัวเลขเฉพาะเพื่อทำให้ประสิทธิภาพแย่ลงได้ ดังนั้นผลลัพธ์คาดหมายยังคงเป็น $0.20 ต่อเกม และดีกว่ากลยุทธ์ที่บทความเสนอ
    • น่าเสียดายที่ตัวเลขไม่ได้เป็นวงกลม :( ถ้าใส่ออฟเซ็ตให้ตัวเลขเริ่มต้น การค้นหาแบบทวิภาค จะทำงานแบบเหมาะที่สุดไม่ได้ไม่ใช่เหรอ? ลองคิดว่าตัวเลขน้อยกว่า 50 แต่เริ่มทายที่ 60 ตอนนี้ต้องค้นหา 30 ตัว ไม่ใช่ 25 ตัว จึงไม่เหมาะที่สุด
    • เจ๋งดี ลองจินตนาการว่าตัวเลข 1~100 ถูกวางรอบหน้าปัดนาฬิกา จะเข้าใจง่ายขึ้น เหมือนสุ่มหมุนนาฬิกาก่อนเริ่มการค้นหาแบบทวิภาคจากด้านบนตามปกติ

  • ในบรรดาหลาย ๆ เรื่องที่ Ballmer เคยผิด เรื่องนี้ก็น่าจะเป็นหนึ่งในนั้น

    • Ballmer เดิมพันกับ Microsoft ถูกอยู่นะ
    • ถ้าผิดแบบ Ballmer ได้ก็คงดี มูลค่าสุทธิจากการตัดสินใจของเขาอยู่ระดับหลายหมื่นล้านดอลลาร์
    • คุณต้องเอาเรื่องที่คุณเคยผิดมาให้ดูด้วย เพื่อให้เราตัดสินได้
    • อันที่ผมชอบเป็นการส่วนตัวที่สุด: https://www.youtube.com/shorts/rCszxibClKE

  • นี่แหละเพื่อน ๆ ตัวอย่างสมบูรณ์แบบที่แสดงให้เห็นว่าทำไม กระบวนการสัมภาษณ์สายเทคโนโลยี สมัยใหม่ถึงเป็นความบ้าคลั่งล้วน ๆ

    • นี่เป็นตัวอย่างสมบูรณ์แบบของการสัมภาษณ์สายเทคโนโลยีสมัยใหม่ที่พังจริงหรือ?
      คำถามของ Ballmer ดูยุติธรรมดีเมื่อคิดถึงระดับความซับซ้อนของคำตอบที่เขาคาดหวัง
      ผู้ถูกสัมภาษณ์น่าจะให้คำตอบที่ผิดในเชิงคณิตศาสตร์ แต่ในกระบวนการนั้นก็ได้แสดงวิธีคิด และสาธิตหลักการวิทยาการคอมพิวเตอร์บางส่วน
      ต้องคำนึงด้วยว่า Ballmer มีอาชีพการงานมายาวนาน ถ้าเขาเคยถามคำถามนี้จริง ก็น่าจะเป็นยุค 80 และตอนนั้นคงไม่มีใครคาดหวังให้ตอบวิธีแก้ซับซ้อนแบบที่บทความอธิบาย
      ถ้าให้คำตอบที่ถูกต้องได้ก็คงยอดเยี่ยมและควรรับเข้าทำงานทันที แต่คำถามนี้ไม่ได้ดูพังโดยพื้นฐาน เพราะไม่ว่าจะเดิมพันหรือไม่เดิมพัน คำตอบไหนก็ต้องให้เหตุผลสนับสนุนอย่างดี
    • พูดอย่างเป็นธรรม Steve Ballmer เป็นผู้นำที่แย่มาก และถ้าเขาต้องเข้าสัมภาษณ์สายเทคโนโลยี เขาคงไม่ผ่าน Microsoft คงไม่หยุดนิ่งไป 10 ปี ก่อนที่ Satya Nadella จะรับช่วงต่อและกอบกู้บริษัทขึ้นมาใหม่
    • จริงเหรอ? ในฐานะผู้สัมภาษณ์ ถ้าจำเป็นต้องถามคำถามนี้ แล้วผู้สมัครพูดว่า “จริง ๆ แล้วผิดครับ เหตุผลคือแบบนี้” นั่นเป็นสัญญาณที่ดีมากไม่ใช่หรือ โดยทั่วไปคนเขาไม่ทำแบบนี้กันเหรอ?
      โดยปกติจะมีการพูดคุยกับผู้สัมภาษณ์ทุกคน และไม่ได้ดูแค่ว่า “ผู้สมัครตอบโจทย์ถูกไหม” เป็นการส่วนตัวผมคิดว่าคำถามสัมภาษณ์ของบิ๊กเทคจำนวนมากโง่ แต่จากที่เจอมาทั้งสองฝั่ง ผมมองว่ากระบวนการไม่ได้พังเท่าที่คิด
    • ผมไม่ได้ทำงานในอุตสาหกรรมเทคโนโลยี แต่ผมคิดมาตลอดว่าคำถามแบบนี้ถูกออกแบบมาเพื่อให้แสดง ความสามารถในการแก้ปัญหา ไม่ว่าคำตอบจะถูกหรือผิด
      ในกรณีนี้ก็แค่แสดงให้เห็นว่าสามารถให้เหตุผลเกี่ยวกับการค้นหาแบบทวิภาค และแสดงได้ว่ากำไรเฉลี่ยคือ 0.20 ดอลลาร์
    • ถ้าใช้เพื่อดูว่าทั้งสองฝ่ายจะทำงานร่วมกันอย่างสนุกไหม ผมว่าก็โอเค แต่บ่อยขึ้นเรื่อย ๆ ที่มันกลายเป็นแบบทดสอบปริศนา หรือแย่กว่านั้น
      อย่างน้อยก็ทำให้เราได้ฟิกชันคุณภาพอย่าง https://aphyr.com/posts/340-reversing-the-technical-intervie... และภาคต่อของมัน

  • บทความที่วิเคราะห์ สมดุลของแนช อย่างกว้างขึ้น รวมถึงคำตอบเชิงตัวเลขของเกมทั้งหมด อยู่ที่ https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...

  • มูลค่าสุทธิของ Steve Ballmer อยู่ที่ 120,000 ล้านดอลลาร์ ดังนั้นถ้าสมมติว่าเกมหนึ่งตาใช้เวลา 30 วินาที การจะชนะเอาเงินทั้งหมดต้องใช้เวลา 1.6 ล้านปี

    • ก็ให้คอมพิวเตอร์เล่นกันเองได้ ให้ AI ในคอมพิวเตอร์ของผมเจอกับ AI ของ Ballmer โดยรันเกมคอมพิวเตอร์ 1,683,036,051,984 ครั้งภายใน 30 วินาที

  • Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
    เป็นหนังสือที่ดีมากซึ่งว่าด้วย กลยุทธ์ผสม ในทฤษฎีเกม
    ตัวอย่างสร้างแรงจูงใจในหนังสือก็ยอดเยี่ยมเช่นกัน
    “มีไพ่สองใบ คือเอซกับ 2 ผู้เล่น A สุ่มหยิบไพ่ใบหนึ่งจากสองใบนี้ และ B มองไม่เห็นว่าไพ่ใบไหนถูกหยิบไป ถ้า A หยิบได้เอซ เขาจะพูดว่า ‘ฉันมีเอซ’ และเรียกเงิน 1 ดอลลาร์จากอีกฝ่าย ถ้า A หยิบได้ 2 เขาสามารถ (A1) พูดว่า ‘ฉันมีเอซ’ แล้วเรียกเงิน 1 ดอลลาร์จากอีกฝ่าย หรือ (A2) สารภาพว่ามีไพ่ 2 และจ่ายเงิน 1 ดอลลาร์ให้อีกฝ่าย
    หากอีกฝ่ายได้รับเงิน 1 ดอลลาร์โดยสมัครใจ ก็ไม่มีทางเลือกนอกจากต้องรับไว้ แต่ถ้าถูกเรียกเงิน 1 ดอลลาร์ เขาสามารถ (B1) เชื่อว่า A มีเอซและจ่ายเงิน 1 ดอลลาร์ หรือ (B2) ขอเปิดดูเพื่อตรวจว่าคำพูดของ A เป็นจริงหรือไม่ หาก A มีเอซจริง B ต้องจ่ายให้ A 2 ดอลลาร์ ในทางกลับกัน หาก A บลัฟและมีไพ่ 2 อยู่ A ต้องจ่ายให้ B 2 ดอลลาร์
    จงวิเคราะห์เกมนี้ และหากลยุทธ์ที่เหมาะที่สุดกับผลตอบแทนคาดหวังของผู้เล่นแต่ละคน”