ค่าคาดหวังเชิงบวกของเกมที่ไม่ขึ้นกับกลยุทธ์ของ Ballmer

 (gukov.dev)
1 คะแนน โดย GN⁺ 2024-09-08 | 1 ความคิดเห็น | แชร์ทาง WhatsApp

Steve Ballmer คิดผิด

ไม่กี่วันก่อน John Graham-Cumming ได้โพสต์บทความเกี่ยวกับ "คำถามสัมภาษณ์เรื่องการค้นหาแบบไบนารีที่ผิดพลาดของ Steve Ballmer" ซึ่งได้รับความสนใจอย่างมากบน HackerNews ปริศนาลับสมองข้อโปรดของ Ballmer มีดังนี้:

ฉันกำลังนึกถึงตัวเลขหนึ่งตัวระหว่าง 1 ถึง 100 คุณสามารถเดาได้ และหลังจากแต่ละครั้งที่เดา ฉันจะบอกว่าสูงไปหรือต่ำไป ถ้าคุณเดาถูกตั้งแต่ครั้งแรก ฉันจะให้คุณ 5 ดอลลาร์ จากนั้น 4 ดอลลาร์ 3 ดอลลาร์ 2 ดอลลาร์ 1 ดอลลาร์ 0 ดอลลาร์ แล้วคุณจะต้องจ่ายฉัน 1 ดอลลาร์ 2 ดอลลาร์ 3 ดอลลาร์

คุณจะเล่นเกมนี้ไหม?

Steve Ballmer ให้เหตุผลสองข้อในบทสัมภาษณ์ YouTube นี้ว่าทำไมคุณไม่ควรเล่นเกมนี้:

  1. มีตัวเลขจำนวนมากระหว่าง 1 ถึง 100 ที่ทำให้ขาดทุน ดังนั้นแม้จะเลือกตัวเลขแบบสุ่ม ค่าคาดหวังก็ติดลบ
  2. เขาสามารถเลือกตัวเลขแบบมีกลยุทธ์ให้ใช้เวลาค้นหานานที่สุดได้ โดยอาศัยการค้นหาแบบไบนารี

อย่างไรก็ตาม John ได้หักล้างข้อแรกด้วยการแสดงให้เห็นว่า หาก Ballmer เลือกตัวเลขแบบสุ่ม ค่าคาดหวังของเกมจริง ๆ แล้วเป็นบวกที่ $0.20

ผมจะหักล้างข้อที่สอง และพิสูจน์ว่าค่าคาดหวังของเกมเป็นบวกไม่ว่ากลยุทธ์ของ Ballmer จะเป็นอย่างไร

Ballmer จะเลือกตัวเลขแบบเป็นปฏิปักษ์ได้อย่างไร

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

แล้วจะรับมืออย่างไร?

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

ในทฤษฎีเกม สิ่งนี้เรียกว่า mixed strategy ซึ่งสร้างจาก strategy set ของหลาย ๆ pure strategy

เพราะตัวเลขเดียวกันอาจเป็น "ฝั่งชนะ" ในรูปแบบการค้นหาแบบหนึ่ง แต่เป็น "ฝั่งแพ้" ในอีกแบบหนึ่ง mixed strategy แบบนี้จึงสามารถ "ปรับให้เรียบ" ผลตอบแทนคาดหวังของแต่ละตัวเลขได้ และอาจทำให้ทุกตัวเลขกลายเป็น "ฝั่งชนะ" ได้ กล่าวคือมีผลตอบแทนคาดหวังเป็นบวกสำหรับทุกตัวเลข ซึ่งนั่นคือสิ่งที่เรากำลังมองหา

จะหากลยุทธ์ผสมที่ชนะได้อย่างไร

หมายเหตุ: เราต้องการหากลยุทธ์ สักแบบ ที่ชนะทุกตัวเลข ไม่ได้ต้องการหา กลยุทธ์ที่ดีที่สุด ที่ยังชนะได้และให้ค่าคาดหวังสูงสุดในกรณีเลวร้ายที่สุด (Nash equilibrium)

ถ้าสนใจ Nash equilibrium, Arthur O’Dwyer ได้สำรวจคำตอบแบบ closed-form สำหรับเกมที่มีตัวเลขไม่เกิน 5 ตัว และ Bo Waggoner ได้ประมาณค่า equilibrium ของเกม 100 ตัวเลขด้วยการใช้ no-regret online learning

การหากลยุทธ์ผสมที่ชนะทุกตัวเลขสามารถมองเป็นปัญหาการหาค่าเหมาะที่สุดทางคณิตศาสตร์ได้ แต่ละกลยุทธ์อธิบายได้ด้วยเวกเตอร์ "ผลชนะ" V=(v1,..,v100) โดยที่ vk คือผลชนะคาดหวังเมื่อ Ballmer เลือกตัวเลข k ตัวอย่างเช่น การค้นหาแบบไบนารีอาจสอดคล้องกับเวกเตอร์ที่มีค่า v50=5, v25=4, v0=−1

สมมติว่าเรามีกลยุทธ์บริสุทธิ์ V1, V2, ..., Vn และกลยุทธ์ผสมเลือกกลยุทธ์ Vk ด้วยความน่าจะเป็น pk เวกเตอร์ "ผลชนะ" ของกลยุทธ์ผสมนั้นก็เป็นเพียงการรวมเชิงเส้น: Vmixed=∑i=1npiVi

ในการตีความนี้ การหากลยุทธ์ที่ชนะก็คือการหาการรวมเชิงเส้นที่มีข้อจำกัดสองอย่าง:

  • ทุกองค์ประกอบของการรวมเชิงเส้นนี้ต้องเป็นบวก (หมายถึงสามารถทำเงินได้โดยเฉลี่ยสำหรับทุกตัวเลข)
  • สัมประสิทธิ์ของการรวมเชิงเส้นนี้ต้องไม่ติดลบ (เพราะแทนความน่าจะเป็น)

นี่คือปัญหา linear programming แบบคลาสสิก และใน scipy ก็มีตัวแก้ปัญหาที่มีประสิทธิภาพสำหรับเรื่องนี้ ผมได้ลองคิดกลยุทธ์บริสุทธิ์หลายแบบขึ้นมา (การค้นหาแบบไบนารีหลายรูปแบบ) แล้วป้อนเข้า scipy.linprog() และ voilà — คำตอบก็ให้กลยุทธ์ที่ชนะออกมา!

ตัวอย่างกลยุทธ์ที่ชนะ

โค้ดทั้งหมดอยู่ที่ 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 ในแต่ละขั้นให้เดาองค์ประกอบขวาสุดของช่วงที่ไม่ทำให้ความซับซ้อนในกรณีเลวร้ายที่สุดเพิ่มขึ้น
  • ความน่าจะเป็น 1.1608%: การค้นหาแบบไบนารี เดาครั้งแรกเป็น 44 ในแต่ละขั้นให้เดาองค์ประกอบซ้ายสุดของช่วงที่ไม่ทำให้ความซับซ้อนในกรณีเลวร้ายที่สุดเพิ่มขึ้น
  • ความน่าจะเป็น 2.1310%: การค้นหาแบบไบนารี เดาครั้งแรกเป็น 42 ในแต่ละขั้นให้เดาองค์ประกอบปลายสุดของช่วงที่ไม่ทำให้ความซับซ้อนในกรณีเลวร้ายที่สุดเพิ่มขึ้น

...

กลยุทธ์เต็มมี 74 บรรทัด จึงละไว้เพื่อความกระชับ หากสนใจสามารถดูได้บน GitHub

สรุป

ถ้าคุณทำเงินได้เฉลี่ย 14 เซนต์ต่อเกม ครั้งหน้าเมื่อ Steve Ballmer เสนอเกมนี้ คุณควรเข้าร่วมอย่างแน่นอน

สรุปโดย GN⁺

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

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

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

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

  • ข้อโต้แย้งของ Ballmer ว่าด้วย tail risk

    • หากให้ความสำคัญกับการอยู่รอด ค่าคาดหวังไม่ใช่วิธีเดิมพันที่ดี
    • เหมือนกับเหตุผลที่เราไม่ all-in ทุกครั้งในโป๊กเกอร์แม้ว่าค่าคาดหวังจะสูง
    • โดยเฉลี่ยอาจมีโอกาสชนะสูงกว่า แต่คุณได้ผลลัพธ์เพียงครั้งเดียว
    • หากเป้าหมายคือการชนะ ก็ควรหลีกเลี่ยงการติดหนี้ Ballmer
    • น่าจะน่าสนใจกว่าถ้าใช้การจำลองแบบมอนติคาร์โลเพื่อดูการกระจายตัวของผลแพ้ชนะของกลยุทธ์นี้

  • เมื่อ Ballmer บอกว่าเขาเป็น "ฝ่ายตรงข้าม" เขาหมายความว่าเขาไม่จำเป็นต้องเลือกตัวเลขตายตัว

    • สำหรับการเดาแต่ละครั้ง เขาสามารถตอบในแบบที่คงจำนวนตัวเลขที่เป็นไปได้ให้มากที่สุด และรับประกันความพ่ายแพ้ได้ไม่ว่ากลยุทธ์จะเป็นอย่างไร

  • มีการเสนออัลกอริทึมชื่อ "random offset binary search"

    • เลือกตัวเลขสุ่มระหว่าง 0-100 และเรียกมันว่า "offset"
    • ใช้อัลกอริทึม binary search แต่ในแต่ละขั้นให้นำค่าไปบวกกับ "offset" แล้วทำ modulo 100
    • ต่อให้ Ballmer รู้กลยุทธ์นี้ เขาก็ไม่สามารถเลือกตัวเลขเฉพาะเพื่อทำให้ประสิทธิภาพแย่ลงได้
    • ดังนั้นผลลัพธ์คาดหวังจึงยังคงเป็น $0.20 ต่อเกม

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

  • แนะนำหนังสือ "Little Mathematics Library – Elements of Game Theory"

    • เป็นหนังสือที่ดีเกี่ยวกับ mixed strategies ในทฤษฎีเกม
    • หนังสือใช้เกมไพ่สองใบเป็นตัวอย่างเพื่อสร้างแรงจูงใจ
      • ถ้าผู้เล่น A จั่วได้เอซ จะเรียกเงิน 1 ดอลลาร์จากคู่แข่ง
      • ถ้าจั่วได้ไพ่ 2 จะเลือกได้ว่าจะเรียกเงิน 1 ดอลลาร์จากคู่แข่ง หรือจ่าย 1 ดอลลาร์
      • คู่แข่งสามารถเลือกที่จะรับ 1 ดอลลาร์ไปเลย หรือขอพิสูจน์ว่าเป็นเอซจริงหรือไม่
      • ถ้าเป็นเอซจริงจะต้องจ่าย 2 ดอลลาร์ และถ้าเป็นการ bluff จะได้รับ 2 ดอลลาร์
      • จากนั้นวิเคราะห์เกมและหากลยุทธ์ที่เหมาะสมที่สุดกับผลตอบแทนคาดหวังของผู้เล่นแต่ละฝ่าย

  • มีการแชร์ลิงก์ที่ให้การวิเคราะห์ Nash equilibrium ในวงกว้างขึ้น และคำตอบเชิงตัวเลขสำหรับทั้งเกม

  • กระบวนการสัมภาษณ์งานสายเทคยุคใหม่เป็นตัวอย่างของความบ้าคลั่งล้วน ๆ

  • กำลังมองหาคอมเมนต์ที่บอกว่า "น่าจะถูกต้องนะ ทำได้ดี!" แต่ไม่เจอ เลยเขียนเอง

    • น่าจะถูกต้องนะ ทำได้ดี

  • Steve Ballmer มีทรัพย์สินสุทธิ 1.2 แสนล้านดอลลาร์

    • ถ้าสมมติว่าแต่ละเกมใช้เวลา 30 วินาที จะต้องใช้เวลา 1.6 ล้านปีถึงจะชนะเงินทั้งหมดของเขาได้