베이즈 추론 Part 2: 패스 한 번의 무게
이 글은 Claude Opus 5.5 을 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.
「대부호 CPU 플레이어 만들기」 Part 3 은 상대의 패스를 장부에 적기만 하고 확률에는 섞지 않았습니다. 이유를 설명한 끝에 이렇게 썼습니다. “그 가중치를 얼마로 둘지는 실험으로 정해야 합니다. 1차에서는 기록만 남기고 쓰지 않았습니다.”
Part 1 의 말로 바꾸면 그 가중치는 우도입니다. 이 상대가 이런 손패를 쥐었다면 여기서 패스했을 확률. 여섯 주 동안 봇은 패스 기록을 탐색에 한 번 써 보려다 접었지만, 봇 저장소의 평가 문서에 패스 하나의 우도를 숫자로 잰 기록은 없습니다. 그 숫자를 재고, 그 숫자로 고친 믿음이 실제 손패를 얼마나 더 맞히는지 봤습니다.
장부는 이미 베이즈였습니다#
장부는 덱을 넷으로 나눕니다. 내 손패, 이번 판에 나온 카드, 위치를 아는 카드(내가 조공으로 준 카드), 그리고 위치를 모르는 미확인 카드. 미확인 카드는 상대 자리, 블라인드, 나락한 자리의 숨은 칸 어딘가에 있습니다. 여기에 제약이 붙습니다. 블라인드에는 조커가 가지 않고, 나에게 가장 센 카드를 조공으로 바친 자리는 그보다 센 카드를 들 수 없습니다. 운영 봇이 손패 다섯 장 이하에서 탐색할 때는 이 제약을 지키는 배분을 무작위로 뽑습니다.
이것을 Part 1 의 표에 옮기면 장부가 베이즈 갱신이라는 것이 보입니다. 사전 분포는 “카드는 고르게 섞여 나뉘었다” 이고, 제약을 어기는 배분은 우도 0, 지키는 배분은 우도 1 입니다. 사전에 우도를 곱해 정규화하면 제약을 지키는 배분 위의 균등 분포가 남는데, 장부가 뽑으려는 것이 바로 그것입니다. Part 1 의 예제에서 패스하지 않은 세계를 버리던 방법과 같은 일을 하고 있었던 셈입니다.
패스는 이 틀에 들어가지 않았습니다. 패스는 배분을 불가능하게 만들지 않고 덜 그럴듯하게 만들 뿐이라, 0 과 1 사이의 우도가 필요합니다. 장부의 주석은 지금도 이렇게 적혀 있습니다. “확률에 섞지 않는다 — 약한 증거의 무게는 정책·튜닝의 몫이다.”
받을 수 있는데 패스하는 비율#
대부호에서 필드를 받을 수 없는 자리는 패스할 수밖에 없습니다. 받을 수 있는 자리는 받아도 되고 패스해도 됩니다. 그러니 우도는 둘로 나뉩니다. 손패로 그 필드를 받을 수 없다면 패스의 우도는 1 입니다. 받을 수 있다면 θ 이고, 이것은 상대가 얼마나 자주 카드를 아끼는지에 달려 있습니다.
시뮬레이터에서는 모든 손패가 보이므로 θ 를 셀 수 있습니다. 운영 hard 봇 넷이 4인 매치 200개(seed 9,300,001–9,300,200, 매치당 4판)를 두는 동안 필드를 마주한 결정을 모두 모았습니다. “받을 수 있다” 는 반칙 끝내기가 아닌 수로 그 필드를 이길 수 있다는 뜻입니다.
받을 수 있던 결정은 18,021개였고 그 가운데 4,545개가 패스였습니다. θ = 0.252, 네 번에 한 번꼴입니다. 받을 수 없던 결정 14,834개는 하나도 빠짐없이 패스였습니다. 규칙이 그렇습니다. Part 1 예제의 θ = 0.25 는 이 값을 반올림한 것이고, 튜링의 단위로 옮기면 패스 한 번이 “이 자리는 그 필드를 받을 수 있었다” 는 가설에 −6.0 데시반입니다.
상황에 따라 θ 는 꽤 달랐습니다. 결정하는 자리의 손패가 여섯 장 이상일 때 싱글 필드에서는 0.234(9,174번 중 2,146번), 두 장 이상의 묶음에서는 0.335(5,663번 중 1,898번)였습니다. 손패가 다섯 장 이하로 줄면 아낄 카드가 적어져 싱글 0.152(2,625번 중 400번), 묶음 0.181(559번 중 101번)로 내려갑니다. 아래 실험은 이것을 θ 하나로 뭉뚱그려 씁니다.
세 믿음#
이 우도로 믿음을 고쳐 보고, 이미 있던 두 믿음과 견줬습니다.
- U, 장부 균등. 지금 운영 봇이 탐색에 쓰는 표본입니다. 패스를 쓰지 않습니다.
- S, 공개 이력으로 고르기. 11월 5일의 PR290 이 시험한 방식입니다. 균등 표본 256개를 뽑아, 이번 판 이력과 “어긋남” 이 적은 12개를 고릅니다. 어긋남은 상대가 패스한 필드를 표본 손패로는 받을 수 있었던 경우의 수입니다.
- B(θ), 우도 가중. 같은 균등 표본에 어긋남 k 개마다 θ 를 곱한 무게 θ^k 를 줍니다. Part 1 의 두 번째 방법이고, 패스들이 서로 독립이라고 가정합니다.
다른 seed 200개(9,400,001–9,400,200)로 같은 매치를 다시 돌리면서, 1번 참가자(첫 판에 1번 자리에 앉은 봇)가 결정할 때마다 세 믿음을 냈습니다. 활성 상대마다, 미확인 카드마다 “이 자리가 이 카드를 쥐고 있을 확률” 을 내고 실제 손패와 맞춰 봤습니다. 결정 10,986개, 칸으로는 693,481개입니다. U 와 B 는 결정마다 2,000개 표본으로 냈고, S 는 고르기를 20번 되풀이한 240개로 그 믿음이 뜻하는 확률을 냈습니다.
점수는 브라이어 점수입니다. 예측 확률 p 와 실제(있으면 1, 없으면 0)의 차이를 제곱해 평균낸 것이고, 낮을수록 좋습니다. 1950년 확률로 낸 일기예보를 채점하려고 제안된 방법입니다. 오차 범위는 매치 200개를 단위로 낸 95% 구간입니다.
| 믿음 | 전체 브라이어 | U 대비 | 손패 5장 이하 U 대비 | 로그 손실 U 대비 |
|---|---|---|---|---|
| U 장부 균등 | 0.2071 | |||
| B, θ = 0.01 | 0.2189 | +5.7% | +9.6% | +9.8% |
| B, θ = 0.1 | 0.2081 | +0.5% | +0.9% | +0.9% |
| B, θ = 0.25 (잰 값) | 0.2059 | −0.6% | −1.2% | −0.4% |
| B, θ = 0.5 | 0.2057 | −0.7% | −1.4% | −0.6% |
| S 고르기 | 0.2087 | +0.8% | +0.5% | +2.9% |
잰 θ 로 가중한 믿음은 균등보다 나았습니다. 전체 차이는 −0.00124 ± 0.00042, 운영 봇이 탐색하는 손패 다섯 장 이하에서는 −0.00238 ± 0.00117 로 우연의 범위 밖입니다. 다만 크기가 1% 안팎입니다. 이득은 패스를 많이 한 자리에 몰려 있었습니다. 이번 판에 패스 기록이 없는 자리의 칸에서는 −0.07%, 세 번 이상 패스한 자리의 칸에서는 −1.4% 였습니다.
θ = 0.01 은 “패스했으면 받을 카드가 없다” 고 읽는 믿음입니다. 패스를 아예 안 쓰는 것보다 5.7% 나빴고, 탐색 구간에서는 9.6% 나빴습니다. Part 1 의 표에서 θ = 0 이 사후 확률을 0 으로 만들던 장면이 실제 판에서 그대로 나왔습니다.
S 는 전체 브라이어로 균등보다 0.8% 나빴습니다(+0.00163 ± 0.00070). 탐색 구간에서는 브라이어 차이가 우연과 구별되지 않았지만, 확신한 예측이 틀릴 때 크게 깎는 로그 손실로는 4.3% 나빴습니다. 어디서 틀리는지는 보정표에 보입니다. 믿음이 말한 확률을 구간으로 묶고, 그 구간의 칸에서 카드가 실제로 그 자리에 있던 비율을 셌습니다.
| 믿음이 말한 확률 | U: 평균 예측 → 실제 (칸) | B(0.25) | S |
|---|---|---|---|
| 0.1 미만 | 0.049 → 0.050 (18,480) | 0.049 → 0.060 (24,766) | 0.036 → 0.116 (37,791) |
| 0.3 이상 0.4 미만 | 0.340 → 0.339 (329,028) | 0.340 → 0.340 (307,984) | 0.343 → 0.336 (266,293) |
| 0.8 이상 0.9 미만 | 0.828 → 0.842 (785) | 0.838 → 0.775 (1,907) | 0.839 → 0.698 (3,276) |
| 0.9 이상 | 0.986 → 1.000 (25) | 0.941 → 0.767 (446) | 0.973 → 0.617 (2,496) |
장부 균등은 모든 구간에서 말한 만큼 맞았습니다. 정직하지만, 0.9 를 넘게 확신하는 일이 거의 없습니다. S 는 “거의 확실하다” 고 한 칸이 2,496개였는데 실제로 맞은 것은 62% 였고, “거의 없다” 고 한 칸에서 카드가 나온 비율은 12% 였습니다. 256개에서 어긋남이 가장 적은 12개만 남기는 것은 패스를 매우 강한 증거로 다루는 것과 같아, θ = 0.01 쪽으로 기웁니다. B 는 끝 구간에서 조금 자신만만했지만 S 보다 훨씬 덜했습니다.
일본 UEC 컴퓨터 대빈민 대회에서 2016년 우승한 Glicine 의 제작자 오오토 가쓰미도 자기 손패 추정을 두고 같은 약점을 적었습니다. 만드는 손패 배치 수가 고정되어 있고, 사후 확률을 따르는 배치 묶음을 만드는 것을 목표로 하지 못했으며, 그것이 프로그램의 약점으로 보인다는 것입니다.
독립이 아니었습니다#
표에는 이상한 점이 하나 있습니다. 데이터에서 잰 θ = 0.25 보다 θ = 0.5 가 조금 더 나았습니다. 우도를 제대로 쟀다면 그 값이 가장 좋아야 합니다.
B 는 패스를 서로 독립인 증거로 곱합니다. Part 1 에서 데시반을 더할 때 붙인 조건입니다. 그래서 같은 판에서 같은 자리가 앞서 “받을 수 있는데 패스” 한 횟수별로 θ 를 다시 셌습니다. 그런 패스가 아직 없던 결정 9,616개에서는 0.191, 한 번 있던 3,926개에서는 0.297, 두 번 이상 있던 4,479개에서는 0.345 였습니다.
한 번 아낀 자리는 다음에도 아낄 가능성이 큽니다. 아끼고 싶은 카드가 판 내내 그 손에 있기 때문일 것입니다. 그러면 두 번째 패스는 첫 번째 패스가 이미 한 말을 상당 부분 되풀이하는데, B 는 그것을 새 증거로 보고 −6 데시반을 또 뺍니다. 증거를 겹쳐 세는 것입니다. θ 를 0.5(패스당 −3 데시반)로 올려 증거를 약하게 세면 겹쳐 센 몫이 대략 상쇄되는 것으로 보입니다. 몬테카를로 Part 2 에서 장부의 위험 점수가 자리끼리를 독립처럼 합쳐 위험을 낮게 봤던 것과 같은 종류의 오차가, 이번에는 증거를 부풀리는 쪽으로 나왔습니다.
강한 우도에는 다른 비용도 있습니다. 무게가 몇몇 표본에 쏠리면 평균은 사실상 그 몇 개로 냅니다. 무게의 고르기를 재는 유효 표본 크기 (Σw)² / Σw² 로 보면, θ = 0.25 에서 결정 하나의 유효 표본은 중앙값이 2,000개의 51% 였습니다. θ = 0.01 에서는 중앙값이 12%, 하위 10% 결정은 0.5%, 그러니까 열 개 남짓입니다. 틀린 모형 위에 표본 흔들림까지 얹힙니다.
봇은 왜 거의 그대로였나#
이 결과는 11월 초의 실험들과 맞아떨어집니다. PR290 은 롤아웃 속 상대를 hard-3 로 두고 탐색 표본을 S 방식으로 고른 후보를 시뮬레이터에서 운영 봇과 맞붙였는데, 4인 판의 평균 순위가 −0.008~−0.021 등 나아지는 데 그쳐 신뢰구간이 모두 0 을 덮었고, 승격하지 않았습니다. 같은 256개에서 실제 손패와 가장 가까운 12개를 골라 주는 “완벽한 고르기” 도 −0.055 였습니다. 그 바로 전 PR289 에서는 상대 손패를 정확히 알려 주고 롤아웃 속 상대를 hard-3 로 두면 탐색 구간에서 −0.115 가 나왔지만, 롤아웃 속 상대가 easy 이면 같은 정확한 손패로도 −0.044 였습니다. 시뮬레이터의 상대가 롤아웃 모형과 거의 같은 봇이라 부풀려진 숫자이긴 하지만, 정보의 값은 그 정보를 쓰는 상대 모형에 달려 있다는 것이 그때의 결론이었습니다.
이번 측정은 정보 쪽을 채웁니다. 패스로 고칠 수 있는 믿음은 잘 고쳐도 1% 남짓입니다. 탐색 구간에서 −1.2% 로 손패 여섯 장 이상일 때(−0.45%)보다 컸지만 그래도 그 정도입니다. 패스 하나가 말해 주는 것은 “그 필드를 받을 수 있었는가” 하는 한 비트이고, 어느 카드인지는 말해 주지 않습니다.
UEC 대회의 강한 프로그램들은 같은 문제를 다르게 풀었습니다. 오오토의 2015년 wisteria 는 손패 조합을 일정 개수 만들고, 각 조합에서 이번 시합의 진행이 나올 우도를 방책 함수로 계산해 우도가 가장 큰 조합을 썼습니다. 패스만이 아니라 상대가 둔 모든 수가 증거가 됩니다. 시뮬레이션에서 수를 고르는 확률적 방책과 추정에 쓰는 방책이 같은 틀이라 추정기를 따로 만들 필요가 없었고, 시합마다 상대의 실제 수로 방책을 다시 학습해 추정이 상대의 습관을 따라가게 했습니다. 상대 모형이 각 행동을 고를 확률을 곱해 딜마다 무게를 주는 방식은 트릭테이킹 카드 게임에서도 쓰입니다. 앨버타 대학의 레브스톡 등은 2019년 스카트에서 사람 기보로 학습한 방책으로 이것을 했습니다.
효과도 보고되어 있습니다. 고치공과대학의 2024년도 석사 논문 초록 하나는 오오토의 프로그램 Blauweregen 을 바탕으로 손패 추정 방법을 여럿 두고, 시합마다 밴딧으로 골라 쓰게 했습니다. 상대 손패를 알려 주지 않은 실험에서, 우도가 가장 큰 배치를 고르는 방법이 쓰인 시합의 평균 득점은 3.66~3.69점으로 무작위 배분의 3.46~3.56점보다 0.14~0.20점 높았습니다. 상대 손패를 그대로 알려 준 실험에서 그 방법이 쓰인 시합은 4.13~4.34점이었습니다. 밴딧이 고른 시합끼리의 평균이라 통제된 비교는 아닙니다.
우리 대부호 봇이 이 길을 그대로 따라가기는 어렵습니다. 시뮬레이터의 상대인 hard 봇은 결정적이라, 같은 시야에서 늘 같은 수를 둡니다. 결정적 방책으로 계산한 우도는 수마다 0 아니면 1 이고, 그 0 과 1 은 장부의 제약처럼 단단하지만 틀리면 진짜 손패를 지워 버립니다. 이번에 잰 θ = 0.25 도 hard 봇의 습관입니다. 사람이 받을 수 있는데도 패스하는 비율은 재지 않았고, 사람마다 다를 것입니다. 봇에게서 잰 숫자를 사람에게 그대로 쓰면, 신호기가 작동한다고 보고 잡은 우도로 잔해가 있던 구역을 옅게 칠한 AF447 수색의 실수를 작게 되풀이하게 됩니다.
10월에 장부가 패스를 기록만 하고 쓰지 않은 것은 결과적으로 안전한 선택이었습니다. 표에서 보듯 정직하지만 아무것도 쓰지 않는 믿음은, 확신에 차서 틀리는 믿음보다 낫습니다. 패스는 쓸 수 있고, 잰 우도로 쓰면 믿음이 조금 나아집니다. 그 우도를 어디서 재느냐는 결국 맞은편에 누가 앉았느냐의 문제입니다.
자료에 대해#
실험은 모두 시뮬레이터에서 4인 판으로만 했고, 네 자리 모두 운영 hard(hard-6)입니다. 봇 저장소 사본(커밋 86ff00d9)에 실험용 파일 두 개만 붙여 돌렸고 원본은 건드리지 않았습니다. 브라이어 점수와 보정은 카드 한 장 한 장의 주변 확률로 쟀습니다. 상대 손패 전체가 맞는지는 재지 않았습니다. S 의 확률은 고르기를 20번 되풀이해 낸 것이고, 실제 탐색은 결정마다 한 번 고른 12개를 씁니다. 받을 수 있는지는 반칙 끝내기만 빼고 판정했으며, 8 자르기나 혁명처럼 hard 봇이 따로 아끼는 수의 사정은 θ 하나에 뭉뚱그렸습니다. PR289·PR290 의 수치는 공개되지 않은 봇 저장소의 평가 문서에서 옮겼습니다. 고치공과대학 논문은 초록만 읽었습니다.
| 편 | 제목 |
|---|---|
| Part 1 | 우도가 뭐냐는 질문 |
| Part 2 | 패스 한 번의 무게 (지금 글) |
References#
최신 (2024~2026)#
- 中山友里歌, 「相手手札推定を動的に切り替える大貧民プレイヤの研究」, 高知工科大学大学院 修士学位論文梗概 (2024), 표 2·3: https://www.kochi-tech.ac.jp/library/ron/pdf/2024/03/20/a1275108.pdf
배경 (2023년까지)#
- 大渡勝己, 「コンピュータ大貧民クライアント「wisteria」の製作」 (2015), 3절: https://www.tanaka.ecc.u-tokyo.ac.jp/wp/wp-content/blogs.dir/5/files/2017/02/wisteria2015.pdf
- 大渡勝己, 「コンピュータ大貧民クライアント「Glicine」の紹介」 (2016), 5절: https://www.tanaka.ecc.u-tokyo.ac.jp/wp/wp-content/blogs.dir/5/files/2017/02/Glicine2016.pdf
- Douglas Rebstock, Christopher Solinas, Michael Buro, Nathan R. Sturtevant, “Policy Based Inference in Trick-Taking Card Games”, IEEE CoG (2019), 식 (1): https://arxiv.org/abs/1905.10911
- Glenn W. Brier, “Verification of Forecasts Expressed in Terms of Probability”, Monthly Weather Review 78(1): 1–3 (1950): https://doi.org/10.1175/1520-0493(1950)078%3C0001:VOFEIT%3E2.0.CO;2
- Art B. Owen, Monte Carlo theory, methods and examples, 9장 9.3절 식 (9.13) (유효 표본 크기): https://artowen.su.domains/mc/