Giá trị kỳ vọng dương của trò chơi không phụ thuộc vào chiến lược của Ballmer

 (gukov.dev)
1 điểm bởi GN⁺ 2024-09-08 | 1 bình luận | Chia sẻ qua WhatsApp
  • Câu đố đoán số của Steve Ballmer là trò chơi tìm một số từ 1 đến 100; tìm kiếm nhị phân cố định có thể bị khai thác, nhưng dùng chiến lược hỗn hợp thì có thể tạo ra giá trị kỳ vọng dương bất kể đối thủ chọn thế nào
  • Ballmer cho rằng ngay cả khi chọn ngẫu nhiên thì giá trị kỳ vọng vẫn âm và ông có thể chọn những con số khiến người chơi mất nhiều thời gian hơn, nhưng John Graham-Cumming đã phản bác rằng nếu chọn ngẫu nhiên thì giá trị kỳ vọng là $0.20
  • Với mẫu tìm kiếm cố định, trong 100 số sẽ có ít nhất 37 số cần 6 câu hỏi mới tìm ra, đủ để tạo ra thua lỗ; vì vậy nếu đối thủ biết chiến lược thì họ có thể khiến người chơi thua ở mọi ván
  • Lời giải là dùng chiến lược hỗn hợp của lý thuyết trò chơi, tức chọn ngẫu nhiên một trong nhiều chiến lược tìm kiếm thuần túy, để trung bình hóa chênh lệch thắng thua theo từng con số và loại bỏ các số bất lợi
  • Một chiến lược ví dụ tìm được bằng cách giải bài toán quy hoạch tuyến tính với scipy.linprog() cho lợi nhuận kỳ vọng trung bình $0.16 nếu Ballmer chọn ngẫu nhiên, và lợi nhuận kỳ vọng tệ nhất vẫn là $0.14 ngay cả khi ông chọn theo hướng đối kháng

Câu đố đoán số và phản biện trước đây

  • Câu đố mà Ballmer được cho là thích là trò chơi trong đó đối thủ nghĩ ra một số từ 1 đến 100, và mỗi lần người chơi đoán thì sẽ được báo là cao hơn hay thấp hơn
  • Phần thưởng là nếu đoán đúng ngay lần đầu thì được $5, sau đó lần lượt là $4, $3, $2, $1, $0, rồi từ đó trở đi người chơi phải trả $1, $2, $3
  • Ballmer cho rằng không nên chơi trò này vì hai lý do
    • Ngay cả khi số được chọn ngẫu nhiên, có quá nhiều số gây thua lỗ nên ông kết luận giá trị kỳ vọng là âm
    • Ông cho rằng mình có thể chiến lược hóa việc chọn những số khiến tìm kiếm nhị phân mất nhiều bước nhất
  • John Graham-Cumming trong bài “Steve Ballmer’s incorrect binary search interview question” đã phản bác rằng nếu Ballmer chọn số ngẫu nhiên thì giá trị kỳ vọng là $0.20, tức dương
  • Tiến thêm một bước, ta còn có thể tìm được chiến lược cho giá trị kỳ vọng dương ngay cả khi Ballmer chọn số một cách chiến lược

Điểm yếu của tìm kiếm nhị phân cố định

  • Nếu người chơi luôn dùng cùng một chiến lược tìm kiếm nhị phân cố định, thì trong 100 số sẽ có 37 số cần đến 6 câu hỏi mới đoán đúng
  • Nếu Ballmer biết chiến lược cố định đó, ông có thể chọn một trong 37 số “thua” này để buộc người chơi chịu lỗ
  • Điểm yếu này không chỉ giới hạn ở một kiểu tìm kiếm nhị phân cụ thể
    • Với bất kỳ mẫu tìm kiếm cố định nào, luôn có ít nhất 37 số gây thua lỗ
    • Nếu đối thủ chọn các số đó, người chơi sẽ thua ở mọi ván

Đối phó bằng chiến lược hỗn hợp

  • Thay vì cố định một mẫu tìm kiếm, ta chuẩn bị nhiều mẫu tìm kiếm rồi khi bắt đầu ván sẽ chọn ngẫu nhiên một mẫu theo xác suất định trước và giữ nguyên nó đến hết ván
  • Trong lý thuyết trò chơi, đây được gọi là chiến lược hỗn hợp dựa trên nhiều chiến lược thuần túy
  • Cùng một con số có thể là số thắng trong mẫu tìm kiếm này nhưng lại là số thua trong mẫu khác
  • Mục tiêu của chiến lược hỗn hợp là trung bình hóa lợi nhuận kỳ vọng theo từng con số để mọi con số đều cho giá trị kỳ vọng dương

Tìm chiến lược bằng quy hoạch tuyến tính

  • Mục tiêu không phải là tìm chiến lược tối ưu theo nghĩa tối đa hóa giá trị kỳ vọng trong trường hợp xấu nhất, tức cân bằng Nash, mà chỉ là tìm một chiến lược bất kỳ thắng với mọi con số
  • Mỗi chiến lược thuần túy có thể biểu diễn bằng một vector chiến thắng độ dài 100 là V = (v_1, .., v_100)
    • v_k là lợi nhuận kỳ vọng khi Ballmer chọn số k
    • Ví dụ, tìm kiếm nhị phân có thể có các giá trị như v_50 = 5, v_25 = 4, v_0 = -1
  • Nếu chiến lược hỗn hợp chọn chiến lược thuần túy V_k với xác suất p_k, thì vector chiến thắng tổng thể sẽ là V_mixed = Σ p_i V_i
  • Để tìm một chiến lược thắng, cần một tổ hợp tuyến tính thỏa các điều kiện sau
    • Mỗi phần tử đều phải dương
    • Các hệ số không được âm vì chúng là xác suất
  • Đây là một bài toán quy hoạch tuyến tính điển hình và có thể giải bằng scipy.optimize.linprog của SciPy
  • Khi tạo tập các chiến lược thuần túy từ nhiều biến thể tìm kiếm nhị phân và đưa vào đoạn mã dùng scipy.linprog(), ta thu được một chiến lược hỗn hợp chiến thắng

Chiến lược ví dụ và kết quả

  • Toàn bộ mã có tại gukoff/ballmer_puzzle
  • Kết quả ban đầu là $0.07 mỗi ván, sau đó Arthur O’Dwyer bổ sung các chiến lược thuần túy mới để cải thiện kết quả
  • Hiệu quả của chiến lược hỗn hợp đã cải tiến như sau
    • Lợi nhuận trung bình khi Ballmer chọn ngẫu nhiên: $0.16
    • Lợi nhuận tệ nhất khi Ballmer chọn theo hướng đối kháng: $0.14
  • Chiến lược hỗn hợp ví dụ trộn nhiều biến thể tìm kiếm nhị phân với các xác suất nhỏ
    • Xác suất 0.4714%: đoán đầu tiên là 29, sau đó đoán điểm giữa của khoảng và nếu hòa thì chọn bên trái
    • Xác suất 0.1691%: đoán đầu tiên là 33, sau đó đoán điểm giữa và nếu hòa thì chọn bên trái
    • Xác suất 0.1299%: đoán đầu tiên là 36, sau đó đoán điểm giữa và nếu hòa thì chọn bên phải
    • Xác suất 3.3341%: đoán đầu tiên là 37, sau đó đoán điểm giữa và nếu hòa thì chọn bên phải
    • Xác suất 1.7818%: đoán đầu tiên là 43, sau đó chọn phần tử ngoài cùng bên phải trong khoảng miễn là không làm tăng độ phức tạp trường hợp xấu nhất
    • Xác suất 1.1608%: đoán đầu tiên là 44, sau đó chọn phần tử ngoài cùng bên trái trong khoảng miễn là không làm tăng độ phức tạp trường hợp xấu nhất
    • Xác suất 2.1310%: đoán đầu tiên là 42, sau đó chọn phần tử ở mép khoảng miễn là không làm tăng độ phức tạp trường hợp xấu nhất
  • Chiến lược đầy đủ dài 74 dòng; danh sách đầy đủ đã được lược bỏ có thể xem tại winning strategy trên GitHub
  • Nếu mức lợi nhuận trung bình 14 xu mỗi ván xứng đáng với thời gian bỏ ra, thì vẫn đáng chơi ngay cả khi Ballmer đề xuất trò này

Bài viết liên quan

1 bình luận

 
GN⁺ 2024-09-08
Các ý kiến trên Hacker News

  • Bài viết liên quan gần đây: Câu hỏi phỏng vấn tìm kiếm nhị phân sai lầm của Steve Ballmer - https://news.ycombinator.com/item?id=41434637 - tháng 9 năm 2024, 240 bình luận

  • Bài này ứng dụng thì hay, nhưng có vẻ đã bỏ lỡ trọng tâm
    Luận điểm của Ballmer về bản chất là về rủi ro đuôi. Nếu coi trọng việc sống sót, giá trị kỳ vọng hoàn toàn không phải là tiêu chí tốt để đặt cược. Vì bạn chỉ có một cơ hội. Cũng giống như trong poker, việc đặt toàn bộ tài sản mỗi khi có một ván bài “kỳ vọng” sẽ thắng là vô lý; gần như chắc chắn bạn sẽ phá sản chỉ sau vài ván
    Dù trung bình là +$0.07 hay gì đi nữa, độ rộng của phân phối rõ ràng vẫn có thể đi xuống dưới 0. Trung bình thì xác suất thắng có thể nhỉnh hơn xác suất thua một chút, nhưng trên thực tế bạn chỉ nhận một kết quả duy nhất. Nếu mục tiêu là thắng hoặc mất sạch, thì trừ khi bạn muốn nợ tiền Ballmer, tốt hơn là không chơi
    Điều thú vị hơn là mô phỏng Monte Carlo chiến lược này để xem phân phối thắng/thua. Khi đó lựa chọn có thể không rõ ràng đến vậy
    Nếu có thể chơi trò này vài nghìn tỷ lần thì tất nhiên cứ vắt kiệt thôi :P

    • Tôi không biết câu “luận điểm của Ballmer về bản chất là rủi ro đuôi” đến từ đâu. Trong cuộc phỏng vấn không thấy ông ấy lập luận như vậy. Phần nêu vấn đề và giải thích đáp án chỉ được trình bày từ góc nhìn giá trị kỳ vọng của một lần chơi, và điểm ngoặt là việc chọn số theo kiểu đối kháng, chứ không phải rủi ro phá sản
      Là ví dụ về rủi ro đuôi thì cũng không hay. Với chiến lược hiển nhiên, phần đuôi cực kỳ dày
    • Đúng vậy. Nghịch lý St. Petersburg cho thấy chúng ta trực giác đã biết điều đó. Tôi đặt “nghịch lý” trong ngoặc kép vì tôi cho rằng đây không hẳn là nghịch lý mà là một phản ứng bình thường
      Sam Bankman-Fried rất thích giá trị kỳ vọng, và nổi tiếng vì từng nói rằng anh ta sẽ tung một đồng xu mà nếu ra mặt ngửa thì nhân đôi “giá trị” của thế giới, còn nếu ra mặt sấp thì phá hủy thế giới
      Tóm lại, nghịch lý St. Petersburg là như sau. Tung một đồng xu công bằng cho đến khi ra mặt ngửa; người chơi nhận $2^n, trong đó n là số lần tung. Nếu ra ngửa ngay lần đầu thì nhận $2, lần thứ hai thì $4, lần thứ ba thì $8, lần thứ mười thì $1024(2^10), v.v. Có thể dễ dàng thấy giá trị kỳ vọng của trò chơi này tiến tới vô hạn
      Vì vậy, một người hoàn toàn lý trí đáng lẽ phải sẵn sàng trả gần như bất kỳ số tiền nào để chơi trò này. Vì mọi số tiền hữu hạn đều nhỏ hơn vô hạn, nên lợi ích kỳ vọng luôn dương
      Nhưng có lẽ gần như không ai chịu trả hàng triệu đô la để chơi trò đó. SBF có thể là ngoại lệ
      Nó chỉ là nghịch lý nếu bạn nghĩ điều này cho thấy con người không “lý trí”. Trên thực tế, có vẻ nó có nghĩa là giá trị kỳ vọng không phải là thước đo tốt cho rủi ro, và ai cũng biết điều đó
      Một bài viết rất đầy đủ và thú vị về nghịch lý St. Petersburg: https://plato.stanford.edu/entries/paradox-stpetersburg/
    • Tôi không đồng ý. Tôi nghĩ Ballmer đơn giản là sai
      Khác với phần lớn mọi người ở đây, tôi nghĩ những câu hỏi kiểu này là một cách khá tốt để xem một người suy nghĩ ra sao. Nếu có nền tảng toán/thống kê/khoa học máy tính, tôi kỳ vọng ít nhất họ phải có thể bắt đầu một cuộc trao đổi về vấn đề này
      Tuy nhiên, nếu giấu các giả định hoặc tự ý thêm những ràng buộc vô nghĩa để biến nó thành bẫy, thì từ đó trở đi tôi không thấy thuyết phục nữa
      Nếu câu hỏi là “bạn có chơi trò này không”, thì cách diễn giải toán học hợp lý là “hãy xác định giá trị kỳ vọng có lớn hơn 0 hay không”. Nếu muốn nói về rủi ro đuôi thì phải nêu rõ hàm tiện ích, và nó cũng có thể bất đối xứng giữa hai người chơi. Và phải nói rõ đó là ý định
    • Tôi không nghĩ điều này đúng. Đa số mọi người sẽ không phá sản vì mất 1 đô la. Nếu đó là bối cảnh, thì Steve đã thất bại nặng nề trong việc truyền đạt bối cảnh đó
      Thành thật mà nói, có vẻ Steve chưa nắm được đúng độ sâu toán học của bài toán này
    • Tiêu chuẩn Kelly
      Nếu đặt cược nhiều hơn tỷ lệ Kelly, rủi ro phá sản sẽ tăng lên, đặc biệt là về dài hạn
      https://en.m.wikipedia.org/wiki/Kelly_criterion
      Không có ý nói nó áp dụng cho tình huống trong bài gốc. Chỉ là có liên quan đến bình luận cha, và rất hữu ích trong nhiều tình huống như đầu tư

  • Khi Ballmer nói “đối kháng”, tôi đã nghĩ đến kiểu chiến lược này. Thật ra ban đầu ông ấy hoàn toàn không cần chọn một con số cố định. Ở mỗi lần đoán, chỉ cần đưa ra câu trả lời khiến số lượng khả năng còn lại là nhiều nhất; như vậy dù dùng chiến lược nào cũng có thể bảo đảm thua

    • Đúng. Tôi không biết đó có thực sự là ý định hay không, nhưng nếu đúng thì buồn cười ở chỗ nó khiến toàn bộ phân tích toán học này trở nên hoàn toàn vô nghĩa
      Bài gốc đưa ra một chiến lược ngẫu nhiên phức tạp bảo đảm trung bình tối thiểu $0.07 trước mọi đối thủ. Trong khi đó Ballmer chỉ cần trì hoãn “lựa chọn” và câu giờ là có thể buộc người chơi lần nào cũng phải đoán bảy lần và trả 1 đô la
      Nếu bạn kỳ vọng kiếm trung bình $0.07, bạn sẽ chơi bao nhiêu ván trước khi nhận ra mình đang bị lừa?
    • Bình luận này nên được đưa lên cao hơn
      Bài gốc thú vị, nhưng nó giả định một nghĩa “đối kháng” rất yếu, trong đó Ballmer vẫn cam kết với một lựa chọn ban đầu nào đó
      Thú vị là nếu Ballmer dùng commitment scheme thì người chơi có thể kiểm chứng điều này [1]. Ví dụ, khi bắt đầu trò chơi, Ballmer tạo 500 bit ngẫu nhiên, ghép thêm con số đã chọn trong phạm vi 1~100, rồi băm kết quả và gửi giá trị băm đó. Khi trò chơi kết thúc, ông ấy gửi 500 bit ngẫu nhiên, và người chơi có thể ghép con số đã được công bố với các bit đó rồi băm để kiểm tra xem có ra đúng giá trị băm ban đầu hay không. Nếu Ballmer nói dối và đổi số, ông ấy phải tìm 500 bit sao cho khi ghép với một số khác vẫn cho ra giá trị băm ban đầu, mà việc này là khó
      [1]: https://en.wikipedia.org/wiki/Commitment_scheme
    • Tôi cũng nghĩ vậy. Cảm giác giống Absurdle, một biến thể đối kháng của Wordle: https://qntm.org/files/absurdle/absurdle.html
      Nó được làm bởi tác giả của HATERIS, biến thể Tetris luôn đưa cho bạn khối tệ nhất
    • Cách diễn đạt luật chơi có vẻ ngụ ý rằng ông ấy chọn một con số và giữ nguyên. Vì có nói là “có một con số trong đầu”. Tất nhiên có những người phỏng vấn thích bẻ cong luật như trò đấu trí để tỏ ra thông minh, nhưng ở đây có vẻ không phải ý đó
    • Trong phân tích tỷ lệ cạnh tranh của thuật toán online thì người ta làm như vậy. Đối thủ có thể đổi ý tùy ý, và chỉ cần cam kết với những quyết định đã đưa ra trong quá khứ

  • Sửa: À, không phải. Bình luận này sai. Cảm ơn fgna đã chỉ ra
    Có vẻ có một chứng minh đơn giản hơn rằng ta có thể thắng Ballmer đối kháng. Kỳ vọng thu được đúng bằng tìm kiếm nhị phân khi đối đầu Ballmer ngẫu nhiên
    Tên thuật toán của tôi là “tìm kiếm nhị phân với offset ngẫu nhiên”. Cách làm như sau

    1. Chọn một số ngẫu nhiên từ 0~100 và gọi nó là offset
    2. Thực hiện thuật toán tìm kiếm nhị phân, nhưng ở mỗi bước cộng offset vào giá trị rồi lấy phần dư khi chia cho 100
      Hết. Giờ dù Ballmer biết chiến lược này, ông ấy cũng không thể chọn một số cụ thể để làm hiệu năng tệ hơn. Vì vậy kỳ vọng vẫn là $0.20 mỗi ván, tốt hơn chiến lược được đề xuất trong bài
    • Tiếc là các con số không nằm trên một vòng tròn :( Nếu thêm offset vào số ban đầu thì tìm kiếm nhị phân sẽ không còn hoạt động tối ưu nữa, phải không? Thử nghĩ số nhỏ hơn 50 nhưng lại bắt đầu đoán từ 60; lúc này phải tìm trong 30 số chứ không phải 25 số, nên không tối ưu
    • Hay đấy. Dễ hiểu hơn nếu tưởng tượng các số 1~100 được đặt quanh mặt đồng hồ. Tức là xoay đồng hồ một cách ngẫu nhiên trước khi bắt đầu tìm kiếm nhị phân thông thường từ phía trên

  • Trong số rất nhiều điều Ballmer đã sai, có vẻ đây cũng là một điều

    • Ballmer đã đúng khi đặt cược vào Microsoft
    • Ước gì tôi có thể sai như Ballmer. Số dư ròng từ các quyết định của ông ấy là hàng chục tỷ đô la
    • Bạn cũng nên cho thấy những điều bạn đã sai để chúng tôi phán xét
    • Mục tôi thích nhất: https://www.youtube.com/shorts/rCszxibClKE

  • Đây chính là, thưa các bạn, một ví dụ hoàn hảo cho thấy vì sao quy trình phỏng vấn kỹ thuật hiện đại là sự điên rồ thuần túy

    • Đây có phải là ví dụ hoàn hảo về phỏng vấn kỹ thuật hiện đại bị hỏng không?
      Câu hỏi của Ballmer có vẻ công bằng nếu xét đến độ phức tạp của đáp án mà ông ấy kỳ vọng
      Ứng viên có lẽ sẽ đưa ra một câu trả lời sai về mặt toán học, nhưng trong quá trình đó sẽ thể hiện được cách suy nghĩ và trình diễn một chút nguyên lý khoa học máy tính
      Cần nhớ là sự nghiệp của Ballmer rất dài. Nếu ông ấy thực sự hỏi câu này thì có lẽ là vào thập niên 80, khi chẳng ai kỳ vọng ứng viên đưa ra lời giải phức tạp như bài viết mô tả
      Nếu đưa ra được đáp án đúng thì đó là điều rất ấn tượng và đáng tuyển ngay. Nhưng câu hỏi này về cơ bản có vẻ không hỏng. Vì dù có cược hay không, câu trả lời nào cũng cần được biện minh tốt
    • Nói công bằng thì Steve Ballmer là một lãnh đạo tệ, và nếu ông ấy phải tham gia phỏng vấn kỹ thuật thì có lẽ đã không qua được. Microsoft đã trì trệ suốt 10 năm cho đến khi Satya Nadella tiếp quản và vực dậy công ty
    • Thật vậy sao? Với tư cách người phỏng vấn, nếu tôi buộc phải hỏi câu này mà ứng viên nói “Thực ra câu này sai. Lý do là thế này” thì đó là một tín hiệu rất tốt. Chẳng phải người ta thường làm vậy sao?
      Thông thường sẽ có thảo luận với mọi người phỏng vấn, chứ không chỉ nhìn vào việc “ứng viên có giải đúng bài hay không”. Cá nhân tôi nghĩ nhiều câu hỏi phỏng vấn Big Tech rất ngớ ngẩn, nhưng sau khi trải nghiệm từ cả hai phía, tôi thấy quy trình không hỏng như người ta tưởng
    • Tôi không làm trong ngành công nghệ, nhưng tôi luôn nghĩ những câu hỏi như thế này được thiết kế để thể hiện năng lực giải quyết vấn đề, bất kể có đúng đáp án hay không
      Trong trường hợp này, chỉ cần cho thấy bạn có thể suy luận về tìm kiếm nhị phân và chứng minh lợi nhuận trung bình là 0.20 đô la
    • Tôi thấy ổn nếu dùng nó để xem hai bên làm việc cùng nhau có vui không. Nhưng càng ngày nó càng thường biến thành câu đố mẹo, hoặc tệ hơn
      Dù vậy, nhờ đó ta cũng có được những tác phẩm hư cấu chất lượng như https://aphyr.com/posts/340-reversing-the-technical-intervie... và các phần tiếp theo

  • Bài viết phân tích rộng hơn về cân bằng Nash, bao gồm cả nghiệm số của toàn bộ trò chơi, nằm tại https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...

  • Tài sản ròng của Steve Ballmer là 120 tỷ USD, nên nếu mỗi ván mất 30 giây thì sẽ mất 1,6 triệu năm để thắng hết

    • Cứ cho máy tính chơi với nhau là được. AI trên máy tôi đấu với AI của Ballmer. Tức là chạy 1.683.036.051.984 ván máy tính trong vòng 30 giây

  • Little Mathematics Library – Elements of Game Theory: https://mirtitles.org/2012/09/06/little-mathematics-library-...
    Đây là một cuốn sách rất hay về chiến lược hỗn hợp trong lý thuyết trò chơi
    Các ví dụ tạo động lực trong sách cũng rất xuất sắc
    “Có hai lá bài: một quân Át và một quân 2. Người chơi A rút ngẫu nhiên một trong hai lá, còn B không nhìn thấy lá nào đã được rút. Nếu A rút quân Át, A sẽ nói ‘tôi có quân Át’ và yêu cầu đối phương trả 1 USD. Nếu A rút quân 2, A có thể (A1) nói ‘tôi có quân Át’ và yêu cầu đối phương trả 1 USD, hoặc (A2) thú nhận rằng mình có quân 2 và đưa cho đối phương 1 USD
    Nếu đối phương tự nguyện nhận 1 USD thì buộc phải chấp nhận. Nhưng nếu bị yêu cầu trả 1 USD, B có thể (B1) tin rằng A có quân Át và đưa 1 USD, hoặc (B2) yêu cầu kiểm tra để xem lời A nói có đúng không. Nếu A thật sự có quân Át, B phải trả cho A 2 USD. Ngược lại, nếu A đã bluff và có quân 2, A phải trả cho B 2 USD
    Hãy phân tích trò chơi này và tìm chiến lược tối ưu cùng kỳ vọng tiền thưởng của mỗi người chơi”