Ballmer 전략과 무관한 게임의 긍정적 기대값

• Steve Ballmer의 숫자 맞히기 퍼즐은 1~100 사이 수를 찾는 게임으로, 고정된 이진 탐색은 공략당할 수 있지만 혼합 전략을 쓰면 상대 선택과 무관하게 양의 기대값을 만들 수 있음
• Ballmer는 무작위 선택에서도 기대값이 음수이고 자신이 오래 걸리는 숫자를 고를 수 있다고 봤지만, John Graham-Cumming은 무작위 선택 시 기대값이 $0.20이라고 반박함
• 고정 탐색 패턴에서는 100개 숫자 중 최소 37개가 6번 질문을 요구해 손실을 만들 수 있어, 상대가 전략을 알면 매번 플레이어를 지게 만들 수 있음
• 해결책은 여러 순수 탐색 전략 중 하나를 확률적으로 고르는 게임 이론의 혼합 전략이며, 숫자별 승패 차이를 평균화해 불리한 숫자를 없애는 방식임
• scipy.linprog()로 선형계획 문제를 풀어 찾은 예시 전략은 Ballmer가 무작위로 고르면 평균 $0.16, 적대적으로 골라도 최악의 경우 $0.14의 기대 이익을 냄

---

숫자 맞히기 퍼즐과 기존 반박

• Ballmer가 좋아했다는 퍼즐은 상대가 1~100 사이의 숫자를 생각하고, 플레이어가 추측할 때마다 높거나 낮다고 알려주는 게임임
• 보상은 첫 추측에 맞히면 $5, 이후 $4, $3, $2, $1, $0, 그다음부터는 플레이어가 $1, $2, $3을 내는 방식임
• Ballmer는 두 가지 이유로 이 게임을 하지 말아야 한다고 봄
  • 무작위로 숫자를 골라도 손실이 나는 숫자가 많아 기대값이 음수라고 판단함
  • 자신이 이진 탐색으로 가장 오래 걸리는 숫자를 전략적으로 고를 수 있다고 봄
• John Graham-Cumming은 “Steve Ballmer’s incorrect binary search interview question”에서 Ballmer가 무작위로 숫자를 고르면 기대값이 $0.20으로 양수라고 반박함
• 여기서 더 나아가, Ballmer가 전략적으로 숫자를 고르는 경우에도 기대값이 양수인 전략을 찾을 수 있음

고정 이진 탐색의 약점

• 플레이어가 항상 같은 이진 탐색 전략을 쓴다면, 100개 숫자 중 37개는 답을 맞히기까지 6번 질문이 필요함
• Ballmer가 그 고정 전략을 알고 있으면 이 37개의 “지는” 숫자 중 하나를 골라 플레이어에게 손실을 강제할 수 있음
• 이런 취약점은 특정 이진 탐색 하나에만 국한되지 않음
  • 어떤 고정 탐색 패턴에서도 최소 37개 숫자는 손실을 만듦
  • 상대가 그 숫자를 고르면 플레이어는 매번 손실을 봄

혼합 전략으로 대응

• 한 가지 탐색 패턴을 고정하지 않고, 여러 탐색 패턴을 준비한 뒤 게임 시작 시 그중 하나를 확률적으로 뽑아 끝까지 유지함
• 게임 이론에서는 이를 여러 순수 전략에 기반한 혼합 전략이라고 부름
• 같은 숫자라도 어떤 탐색 패턴에서는 이기는 숫자이고, 다른 탐색 패턴에서는 지는 숫자일 수 있음
• 혼합 전략의 목표는 각 숫자별 기대 수익을 평균화해, 모든 숫자에서 기대값이 양수가 되게 만드는 것임

선형계획으로 전략 찾기

• 목표는 최악의 경우 기대값을 최대화하는 최적 전략, 즉 Nash 균형을 구하는 것이 아니라 모든 숫자에서 이기는 임의의 전략을 찾는 것임
• 각 순수 전략은 길이 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의 scipy.optimize.linprog로 풀 수 있음
• 여러 이진 탐색 변형을 순수 전략 집합으로 만들고 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, 이후 최악 복잡도를 늘리지 않는 구간 내 가장 오른쪽 원소 선택
  • 확률 1.1608%: 첫 추측 44, 이후 최악 복잡도를 늘리지 않는 구간 내 가장 왼쪽 원소 선택
  • 확률 2.1310%: 첫 추측 42, 이후 최악 복잡도를 늘리지 않는 구간 끝쪽 원소 선택
• 완전한 전략은 74줄이며, 생략된 전체 목록은 GitHub의 winning strategy에서 볼 수 있음
• 게임당 평균 14센트의 이익이 들이는 시간에 맞는다면, Ballmer가 이 게임을 제안해도 플레이할 만함

[GN⁺]

Hacker News 의견들

• 최근 관련 글: Steve Ballmer의 잘못된 이진 탐색 면접 질문 - https://news.ycombinator.com/item?id=41434637 - 2024년 9월, 댓글 240개

• 이 글은 응용은 멋지지만 핵심을 놓친 듯함
  Ballmer의 논지는 본질적으로 꼬리 위험에 관한 것임. 생존을 중시한다면 기대값은 베팅 기준으로 전혀 좋지 않다. 기회가 한 번뿐이기 때문임. 포커에서 “기대상” 이길 패가 나올 때마다 전 재산을 거는 게 말이 안 되는 것과 같은 이유이고, 몇 판 안에 거의 확실히 파산하게 됨
  평균이 +$0.07이든 뭐든 분포 폭은 분명 0 아래로도 내려갈 수 있음. 평균적으로는 이길 확률이 질 확률보다 조금 높을지 몰라도 실제로는 결과를 하나만 받게 됨. 목표가 이기거나 끝장이거나라면, Ballmer에게 돈을 빚지고 싶은 게 아니라면 안 하는 편이 낫다
  더 흥미로운 건 이 전략을 몬테카를로 시뮬레이션해서 승패 분포를 보는 것임. 그러면 선택이 그렇게 명확하지 않을 수도 있음
  몇 조 번쯤 게임을 할 수 있다면 당연히 탈탈 털어도 됨 :P

  • “Ballmer의 논지는 본질적으로 꼬리 위험”이라는 건 어디서 나온 건지 모르겠음. 인터뷰에서 그런 주장을 했다고 보이지 않음. 문제와 답 설명은 게임 1회 시행의 기대값 관점으로만 제시되어 있고, 반전은 수의 적대적 선택이지 파산 위험이 아님
    꼬리 위험 예시로도 별로임. 뻔한 전략에서는 꼬리가 극단적으로 두꺼움
  • 맞음. 상트페테르부르크 역설은 우리가 직관적으로 그걸 알고 있음을 보여줌. “역설”이라고 따옴표를 붙이는 이유는, 이게 역설이라기보다 정상적인 반응이라고 보기 때문임
    Sam Bankman-Fried는 기대값을 아주 좋아했고, 앞면이면 세계의 “가치”를 두 배로 만들지만 뒷면이면 세계를 파괴하는 동전 던지기를 하겠다고 한 것으로 유명함
    요약하면 상트페테르부르크 역설은 이렇다. 공정한 동전을 앞면이 나올 때까지 던지고, 플레이어는 동전을 던진 횟수를 n이라 할 때 $2^n을 받음. 첫 번째에 앞면이면 $2, 두 번째면 $4, 세 번째면 $8, 열 번째면 $1024(2^10)를 받는 식임. 이 게임의 기대값이 무한대에 접근한다는 건 쉽게 보일 수 있음
    따라서 완전히 합리적인 사람이라면 이 게임을 하기 위해 사실상 어떤 금액이든 낼 의향이 있어야 함. 어떤 유한한 돈도 무한대보다 작으니 기대 이득은 항상 양수이기 때문임
    하지만 그 게임을 하려고 수백만 달러를 내겠다는 사람은 아마 거의 없을 것임. SBF는 예외일지도 모름
    이것이 사람들이 “합리적”이지 않음을 보여준다고 생각할 때만 역설임. 실제로는 기대값이 위험 측정에 좋은 척도가 아니고, 모두가 그걸 알고 있다는 뜻으로 보임
    상트페테르부르크 역설에 대한 아주 완전하고 흥미로운 글: https://plato.stanford.edu/entries/paradox-stpetersburg/
  • 동의하지 않음. Ballmer는 그냥 틀렸다고 봄
    여기 대부분과 달리 이런 질문이 사람이 어떻게 생각하는지 보는 데 꽤 괜찮은 방식이라고 생각함. 수학/통계/컴퓨터 과학 배경이 있다면 적어도 이 문제에 대한 대화를 시작할 수 있어야 한다고 기대함
    다만 가정을 숨기거나 자기 멋대로 헛된 제약을 추가해서 함정으로 만들면 거기서부터 납득이 안 됨
    질문이 “이 게임을 하겠는가”라면 합리적인 수학적 번역은 “기대값이 0보다 큰지 판단하라”임. 꼬리 위험을 이야기하려면 효용 함수를 명시해야 하고, 두 플레이어에게 비대칭일 수도 있음. 그리고 그게 의도라고 분명히 말해야 함
  • 이건 맞지 않다고 봄. 대부분의 사람은 1달러를 잃는다고 파산하지 않음. 그런 맥락이었다면 Steve가 그 맥락 전달에 크게 실패한 것임
    솔직히 Steve가 이 문제의 수학적 깊이를 제대로 파악하지 못한 것 같음
  • 켈리 기준
    켈리 비율보다 많이 베팅하면 특히 장기적으로 파산 위험이 커짐
    https://en.m.wikipedia.org/wiki/Kelly_criterion
    원 글 상황에 적용된다는 말은 아님. 다만 부모 댓글에는 관련 있고, 투자 같은 여러 상황에서 매우 유용함

• Ballmer가 “적대적”이라고 했을 때 이런 전략을 떠올렸음. 사실 그는 처음에 고정된 숫자를 고를 필요가 전혀 없음. 각 추측마다 가능한 숫자가 가장 많이 남는 답을 주면 되고, 그러면 어떤 전략이든 패배를 보장할 수 있음

  • 맞음. 그게 실제로 의도였는지는 모르겠지만, 맞다면 이 모든 수학적 분석을 완전히 무의미하게 만든다는 점이 웃김
    원 글은 어떤 적대자에게도 평균 최소 $0.07을 보장하는 복잡한 무작위 전략을 제시함. 반면 Ballmer는 “선택”을 미루고 질질 끌기만 해도 매번 일곱 번 추측하게 만들어 1달러를 내게 함
    평균 $0.07을 벌 거라고 기대했다면, 사기당하고 있다는 걸 깨닫기 전까지 몇 판이나 할까?
  • 이 댓글이 더 위에 있어야 함
    원 글은 흥미롭지만, Ballmer가 여전히 어떤 초기 선택에 커밋한다고 보는 아주 약한 의미의 “적대적”을 가정함
    흥미롭게도 Ballmer가 커밋먼트 스킴을 쓰면 플레이어가 이 사실을 확인할 수 있음 [1]. 예를 들어 게임 시작 시 Ballmer가 무작위 비트 500개를 만들고, 거기에 1~100 범위에서 고른 숫자를 붙인 뒤 결과를 해시해서 그 해시를 보내는 식임. 게임이 끝나면 그는 500개의 무작위 비트를 보내고, 플레이어는 이제 공개된 선택 숫자와 그 비트를 이어 붙여 해시했을 때 처음 보낸 해시가 나오는지 확인할 수 있음. Ballmer가 거짓말을 해서 숫자를 바꾸려면, 다른 숫자와 이어 붙였을 때도 원래 해시가 나오게 하는 500비트를 찾아야 하는데 이건 어렵다
    [1]: https://en.wikipedia.org/wiki/Commitment_scheme
  • 나도 그렇게 생각했음. Wordle의 적대적 변형인 Absurdle 같은 느낌임: https://qntm.org/files/absurdle/absurdle.html
    항상 최악의 블록을 주는 Tetris 변형인 HATERIS의 제작자가 만든 것임
  • 규칙의 표현상 그는 숫자를 하나 고르고 유지한다는 뜻으로 보임. “머릿속에 숫자가 있다”고 했으니까. 물론 어떤 면접관은 머리싸움처럼 규칙을 꼬아서 스스로 똑똑해 보이려 하지만, 여기서는 그런 의도는 아닌 것 같음
  • 온라인 알고리즘의 경쟁 비율 분석에서는 이렇게 함. 적대자는 마음을 마음대로 바꿀 수 있고, 과거에 이미 내린 결정에만 커밋하면 됨

• 수정: 아, 아님. 이 댓글은 틀렸음. 지적해 준 fgna에게 고마움
  적대적 Ballmer를 이길 수 있다는 더 단순한 증명이 있는 것 같음. 무작위 Ballmer를 상대로 한 이진 탐색과 정확히 같은 양의 기대 결과가 나옴
  내 알고리즘 이름은 “무작위 오프셋 이진 탐색”임. 방식은 이렇다

  1. 0~100 사이의 무작위 숫자를 고르고 이를 offset이라고 부름
  2. 이진 탐색 알고리즘을 수행하되, 각 단계에서 값에 offset을 더하고 100으로 나눈 나머지를 사용함
     끝임. 이제 Ballmer가 이 전략을 안다고 해도 특정 숫자를 골라 성능을 더 나쁘게 만들 수 없음. 따라서 기대 결과는 여전히 게임당 $0.20이고, 글에서 제안한 전략보다 낫다
  • 안타깝게도 숫자는 원형이 아님 :( 초기 숫자에 오프셋을 주면 이진 탐색이 최적으로 작동하지 않지 않나? 숫자가 50보다 작은데 60부터 추측한다고 생각해보면, 이제 25개가 아니라 30개를 찾아야 하므로 최적이 아님
  • 멋짐. 1~100의 숫자가 시계판 둘레에 배치되어 있다고 상상하면 이해하기 좋음. 기존 이진 탐색을 위쪽부터 시작하기 전에 시계를 무작위로 돌리는 셈임

• Ballmer가 틀렸던 많은 것들 중에서도, 이것도 그중 하나인 듯함

  • Ballmer는 Microsoft에 베팅한 건 맞았음
  • Ballmer처럼 틀릴 수 있다면 좋겠음. 그의 의사결정 순잔고는 수십억 달러였음
  • 우리가 판단할 수 있도록 당신이 틀렸던 것도 보여줘야 함
  • 개인적으로 제일 좋아하는 것: https://www.youtube.com/shorts/rCszxibClKE

• 이게 바로 친구들이여, 현대 기술 면접 절차가 순수한 광기인 이유를 보여주는 완벽한 예시임

  • 이게 망가진 현대 기술 면접의 완벽한 예시일까?
    Ballmer의 질문은 그가 기대한 답의 복잡도를 생각하면 공정해 보임
    면접자는 아마 수학적으로는 틀린 답을 내겠지만, 그 과정에서 사고 과정을 보여주고 컴퓨터 과학 원리도 조금 시연하게 됨
    Ballmer의 경력이 길었다는 점을 생각해야 함. 그가 이 질문을 실제로 했다면 아마 80년대였을 테고, 그때는 글에서 설명한 복잡한 해법을 내놓으리라고 아무도 기대하지 않았을 것임
    올바른 답을 제시했다면 대단한 일이고 즉시 채용감이었을 것임. 하지만 이 질문은 근본적으로 망가진 것 같지는 않음. 베팅을 하든 안 하든, 어느 답이든 잘 정당화해야 하기 때문임
  • 공정하게 말하면 Steve Ballmer는 형편없는 리더였고, 그가 기술 면접을 봐야 했다면 통과하지 못했을 것임. Satya Nadella가 이어받아 회사를 다시 일으켜 세우기 전까지 Microsoft가 10년간 정체하지도 않았을 것임
  • 정말 그런가? 면접관으로서 이 질문을 어쩔 수 없이 해야 하는데 후보자가 “사실 틀렸습니다. 이유는 이렇습니다”라고 말한다면 아주 좋은 신호임. 보통 사람들이 이렇게 하지 않나?
    일반적으로 모든 면접관과 토론이 있고, 단순히 “후보자가 문제를 맞혔는가”만 보지는 않음. 개인적으로 많은 빅테크 면접 문제가 멍청하다고 생각하지만, 양쪽에서 겪어 보니 프로세스가 생각만큼 망가진 건 아니라고 봄
  • 기술 업계에서 일하지는 않지만, 이런 질문은 정답 여부와 무관하게 문제 해결 능력을 보여주도록 설계된 것이라고 늘 생각했음
    이 경우라면 이진 탐색에 대해 추론할 수 있고, 평균 이익이 0.20달러임을 보일 수 있다는 걸 보여주는 정도임
  • 양쪽이 함께 일하면 즐거울지 알아보는 데 쓰는 한 괜찮다고 봄. 하지만 점점 더 자주 이게 퀴즈나 그보다 나쁜 것으로 변함
    그래도 덕분에 https://aphyr.com/posts/340-reversing-the-technical-intervie...와 그 후속편 같은 양질의 픽션은 얻음

• 전체 게임의 수치해를 포함해 내시 균형을 더 폭넓게 분석한 글은 https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...에 있음

• Steve Ballmer의 순자산은 1,200억 달러라서, 게임 한 판에 30초가 걸린다고 하면 전부 따는 데 160만 년이 걸림

  • 컴퓨터끼리 플레이시키면 됨. 내 컴퓨터의 AI 대 Ballmer의 AI. 30초 안에 1조 6830억 3605만 1984번의 컴퓨터 게임을 돌리는 것임

• 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달러를 낸다
  이 게임을 분석하고 각 플레이어의 최적 전략과 기대 보수를 구하라”