대부호 CPU 플레이어 만들기 Part 3: 본 것을 잊지 않는 장부

이 글은 Claude Fable 5.1 을 이용해 초안이 작성되었으며, 이후 퇴고를 거쳤습니다.

Part 2 의 easy 봇은 자기 손패와 지금 필드¹만 봅니다. 이번 편부터 hard 입니다. hard 가 easy 보다 더 많이 보는 것은 아닙니다. 같은 것을 보고 잊지 않을 뿐입니다. 이 편은 그 “잊지 않는 장치” 인 장부와, 장부로 계산하는 위험 점수의 이야기입니다.

세 시리즈에서 이미 쓴 원칙을 다시 적습니다. 봇이 강해지는 이유는 더 많이 보기 때문이 아니라, 같은 것을 보고 더 잘 세기 때문이어야 합니다.

1. 시야에 더한 것 — 사람 화면에 있는 것만#

Part 1 의 View 에서 아래 절반이 이번 편의 재료입니다. 더한 것은 전부 그 자리의 사람이 화면에서 볼 수 있는 것 입니다.

하나씩 넘어갈 것 같지만 둘은 조심해야 했습니다.

이번 판의 것만. 서버에는 매치 전체의 이벤트 이력이 있습니다. 그것을 그대로 넘기면 봇은 지난 판에 나온 카드까지 “나왔다” 고 셉니다. 대부호는 네 판마다 자리를 다시 섞으니 엉뚱한 자리의 카드로 세기도 합니다. 그래서 봇에게는 이번 판의 수에서 나온 이벤트만 잘라 넘깁니다.

실제로 낸 종류. 카드 석 장이 “♥5 조커 조커” 였다면 이것은 5 석 장일 수도, ♥3-4-5 계단일 수도, ♥5-6-7 계단일 수도 있습니다. 카드만 보고는 알 수 없습니다. 그런데 종류에 따라 깔맞춤⁶이 걸리는지, 다음 사람이 무엇으로 받아야 하는지가 다릅니다. 처음 구현은 이벤트에 카드만 적고 종류를 적지 않았습니다. hard 를 만들면서 낸 수의 종류를 이벤트에 함께 적기 시작했고, 그 전에 쌓인 옛 기록은 종류를 비워 두었습니다. 짐작으로 채우지 않습니다. 모르는 것은 모르는 것으로 두는 편이, 틀린 것을 아는 것처럼 두는 것보다 낫습니다.

그리고 하나 더. 내가 받은 조공 카드는 돌려주기를 마친 뒤부터 시야에 들어옵니다. 사람 화면이 그렇습니다. 이 경계는 테스트가 지킵니다. 돌려주기 전에는 시야에 없고, 뒤에는 있습니다.

2. 장부 — 54장을 네 칸에#

시야가 들어오면 봇은 결정마다 장부 를 새로 만듭니다. 메모리에 들고 다니지 않습니다. 서버가 재시작하면 기억이 사라지는 봇은 재시작 전후로 다른 봇이 되기 때문입니다. 세 시리즈에서 세운 그대로입니다.

장부의 뼈대는 보존식 하나입니다. 덱 54장은 겹치지 않게 네 칸으로 나뉩니다.

flowchart LR
    D["덱 54장"] --> M["내 손패"]
    D --> P["이번 판에<br/>나온 카드"]
    D --> K["위치를 아는<br/>안 나온 카드<br/><small>내가 조공으로 준 카드</small>"]
    D --> U["위치도 모르는<br/>미확인 카드"]
    U --> S["상대들의<br/>손패 자리"]
    U --> B["블라인드<br/><small>조커는 없다</small>"]
    U --> X["나락한 사람의<br/>남은 카드<br/><small>조커가 있을 수 있다</small>"]
    style D fill:#FFD700,color:#000000
    style M fill:#87CEEB,color:#000000
    style P fill:#87CEEB,color:#000000
    style K fill:#90EE90,color:#000000
    style U fill:#D3D3D3,color:#000000
    style S fill:#D3D3D3,color:#000000
    style B fill:#D3D3D3,color:#000000
    style X fill:#D3D3D3,color:#000000

// Ledger 는 이번 판의 카드 장부입니다. 54장이 아래 넷으로 겹치지 않게 나뉩니다.
//
//	Mine ⊎ Public ⊎ (Known 의 카드) ⊎ Unknown = 54장
//	len(Unknown) = Σ Slots + BlindSlots + Σ DroppedSlots
type Ledger struct {
    Mine    []model.Card          // 내 손패
    Public  []model.Card          // 이번 판에 나온 카드
    Known   map[int][]model.Card  // 자리 → 거기 있다고 아는 안 나온 카드 (내가 조공으로 준 것)
    Unknown []model.Card          // 위치도 모르는 카드

    Slots        map[int]int      // 활성 상대마다 미확인 칸 수 = 남은 장수 − known
    BlindSlots   int              // 블라인드 장수 (4인 2, 5인 4, 6인 0)
    DroppedSlots map[int]int      // 나락한 자리마다 숨은 칸 수
    Bound        map[int]int      // 조공 상한: 이 자리의 미확인 칸에 있을 수 있는 가장 센 카드
    Passes       map[int][]PassedField // 자리마다 패스했을 때의 필드 — 기록만 한다
}

세 줄에 설명을 더합니다.

초록 칸, “위치를 아는 안 나온 카드”. 내가 대빈민이어서 대부호에게 ♥2 와 조커를 조공으로 줬다면, 그 두 장은 나오지 않았어도 대부호의 손에 있다는 것을 압니다. 이것을 미확인에 넣으면 큰 실수가 됩니다. 내가 A 를 내려는데 “2 가 어디 있는지 모르니 아무도 못 받을 수도 있다” 고 셈하게 됩니다. 2 가 어디 있는지 압니다. 대부호 손입니다. 그래서 장부는 이 칸을 따로 둡니다. 그 카드가 나중에 실제로 나오면 “나온 카드” 칸으로 옮기고, 두 번 빼지 않습니다.

조공 상한. 반대로 내가 대부호여서 대빈민에게서 가장 강한 두 장을 받았다면, 대빈민의 남은 손패에는 그보다 센 카드가 없습니다. 규칙이 가장 강한 카드를 주라고 하니까요. 받은 두 장 중 약한 쪽이 그 자리의 상한이 됩니다. 단, 내가 돌려준 카드는 예외라서 상한보다 셀 수 있습니다. 그것도 내가 준 것이니 알고 있습니다.

패스는 기록만. 어떤 자리가 ♠J 한 장에 패스했다는 것은 그 자리에 J 보다 센 싱글이 없다는 약한 증거 입니다. 달무티 hard 는 이것을 확률에 섞었습니다. 대부호에서는 섞지 않았습니다. 이유는 다음 절에 있습니다.

보존식이 맞지 않으면 장부는 오류를 돌려줍니다. 미확인 카드 수와 칸 수가 다르면 시야 어딘가가 어긋난 것이므로, 틀린 장부로 두는 대신 Part 1 의 fallback⁷ 을 타서 easy 가 대신 둡니다. 시뮬레이션 수백만 결정에서 이 오류는 한 번도 나지 않았습니다. 그래도 길은 두어야 합니다.

3. 자격과 추론을 나눈다#

대부호가 달무티와 가장 다른 점이 여기서 장부에 들어옵니다.

달무티에서는 패스한 사람도 차례가 돌아오면 다시 낼 수 있습니다. 그래서 달무티 hard 는 “이 자리가 패스했으니 지금은 못 받겠지만, 혹시 받을 카드를 들고 아끼는 것 아닐까” 를 확률로 깎아 셌습니다. 대부호에서는 패스하면 그 필드가 끝날 때까지 못 냅니다. 패스한 자리의 “지금 이 필드를 받을 위험” 은 짐작이 아니라 정확히 0 입니다. 카드를 무엇을 들었든 상관없습니다.

그래서 장부는 두 질문을 갈라 둡니다.

// Responders 는 field 에 응수할 «자격» 이 있는 상대 자리입니다 —
// 활성이고, 이번 필드에서 패스하지 않았고, 필드 제출자가 아니고, 남은 장수 ≥ 필드 장수.
// 자격이 없는 자리의 지금 응수 위험은 정확히 0 입니다.
func Responders(seats []SeatState, me, fieldSeatNo int, field *model.Field) []int

위험 점수는 자격이 있는 자리에 대해서만 계산합니다. 자격이 없는 자리는 계산에 들어가지도 않습니다. 이 한 줄 덕에 대부호 봇의 위험 계산은 달무티보다 오히려 단순해졌습니다. “패스한 자리가 다시 받을 위험” 이라는 흐릿한 항이 없어졌기 때문입니다.

패스 기록을 확률에 섞지 않은 이유도 같습니다. 패스 뒤에 그 필드에서는 어차피 못 내므로 “지금 위험” 에는 쓸 곳이 없고, 다음 필드 에서 그 자리가 무엇을 들었는지 짐작하는 데는 쓸 수 있지만 그 가중치를 얼마로 둘지는 실험으로 정해야 합니다. 1차에서는 기록만 남기고 쓰지 않았습니다.

4. 위험 점수 — 이 수를 내면 누가 받을 수 있는가#

hard 가 수를 고를 때 가장 많이 묻는 질문입니다. “이 수가 필드가 되면, 자격 있는 상대 가운데 누군가 가 받을 수 있는가.” 답은 0 과 1 사이의 숫자입니다. 0 이면 아무도 못 받고, 그 수는 리드를 지킵니다.

4.1 계산의 뼈대 — 항아리에서 뽑기#

미확인 카드가 어디 있는지 모르지만, 어디에 있을 수 있는지 는 압니다. 상대들의 손패 자리, 블라인드⁸, 나락한 사람의 남은 카드입니다. 장부는 미확인 카드가 그 자리들에 제약을 지키는 모든 배분이 똑같이 그럴듯하다 고 봅니다. 제약은 둘입니다. 블라인드에는 조커가 없고, 조공 상한이 있는 자리에는 상한 아래 카드만 있습니다.

가장 단순한 경우를 손으로 계산해 봅니다. 내가 싱글을 내려 하고, 미확인 카드가 10장, 그 가운데 내 싱글을 이기는 카드가 2장, 자격 있는 상대가 한 자리에 미확인 칸 3개라고 합시다. 그 자리가 이기는 카드를 하나도 안 들었을 경우의 수는 10장 중 이기지 못하는 8장에서 3장을 뽑는 C(8,3) = 56 이고, 전체는 C(10,3) = 120 입니다. 그러니 그 자리가 받을 수 있을 위험은

1 − 56 / 120 ≈ 0.53

입니다. 이것이 초기하 분포⁹이고, 장부가 하는 계산의 전부가 이것의 변주입니다. 싱글은 이 계산이 정확 합니다. 응수자가 여럿이어도 손패를 합쳐서 세면 “누군가” 가 받을 위험까지 정확합니다.

4.2 어려운 곳 — 같은 숫자와 계단, 그리고 조커#

같은 숫자 묶음은 “이기는 숫자 r 의 카드를 한 장 이상 들고, 거기에 조커를 보태 장수를 채울 수 있는가” 라서 숫자마다·조커 수마다 경우가 갈립니다. 이것은 동적 계획¹⁰으로 자리 하나에 대해 정확히 셉니다. 계단은 무늬와 창(시작 숫자)마다 채워질 확률을 각각 정확히 세고, 창끼리는 “하나라도” 로 합칩니다. 이 합치기는 근사 입니다. 같은 카드가 두 창에 겹쳐 들어가는 것을 독립처럼 다루기 때문입니다.

여러 자리를 합칠 때 가장 큰 함정이 조커 였습니다. 조커는 두 장뿐이고, 한 장을 두 사람이 나눠 가질 수 없습니다. 자리마다 “받을 위험” 을 따로 구해 “하나라도” 로 합치면, 두 자리가 같은 조커 를 들었다는 불가능한 경우까지 세게 됩니다. 처음 구현이 그랬고, 정답과 견주니 안전한 쪽으로 0.28 까지 틀렸습니다. 아무도 못 받을 자리를 “28% 는 받힌다” 고 본 것이 아니라, 받힐 자리를 “안전하다” 고 본 쪽이라 더 나쁜 오차였습니다.

고친 방법은 조커가 누구에게 몇 장 있는지를 먼저 나누는 것 입니다. “A 가 조커 1, B 가 조커 0” 같은 경우마다 조건부로 위험을 구하고, 각 경우의 확률(이것은 정확한 다변량 초기하 분포입니다)로 평균합니다. 오차가 0.09 로 줄었습니다.

렉시오 시리즈에서 비슷한 사고가 있었습니다. 유일한 응수 카드가 반드시 상대 중 하나에게 있는데 받힐 확률을 0.68 로 세던 버그였습니다. 그때 배운 것은 무엇을 사건으로 세는지 를 먼저 정해야 한다는 것이었습니다. 한 장의 카드가 어느 자리에 있는지는 서로 배타이고, 서로 다른 응수 조합이 있는지는 겹칠 수 있습니다. 이번에는 그것을 처음부터 적어 두고 시작했지만, 조커의 배타는 그래도 한 번 놓쳤습니다.

4.3 정답과 견주기#

근사라고 적었으니 얼마나 근사인지를 재야 합니다. 미확인 카드 6~8장짜리 작은 상태를 종류마다 150개 만들고, 미확인 카드를 칸에 나누는 모든 경우 를 하나씩 세어 정답을 구한 뒤 장부의 값과 견줬습니다. 정답은 엔진의 “받을 수 있는가” 판정을 그대로 쓴 것이고, 장부의 근사식을 다시 쓴 것이 아닙니다.

마지막 열이 중요합니다. 셋째 열 “누군가” 의 오차 0.098 은 대부분 위험한 쪽으로 틀린 것입니다. 봇이 조금 더 조심하는 쪽이지요. 안전한 쪽으로 틀린 것은 같은 숫자에서 최대 0.089 였고, 그것도 응수자들이 미확인 카드의 대부분을 나눠 갖는 작은 상태에서 가장 컸습니다. 큰 상태에서는 작아질 것으로 보지만 검증하지 않았습니다.

그래서 이 숫자를 “확률” 이라 부르지 않고 “근사 위험 점수” 라 부릅니다. 봇도 그렇게 씁니다. 절대값으로 “30% 미만이면 안전” 같은 문턱을 긋지 않고, 후보들 사이의 순서 와, 다음에 적을 “확정 안전” 만 믿습니다.

4.4 확정 안전 — 오차를 허용하지 않는 한 줄#

450개 상태 모두에서 정답이 0 이면 장부도 0, 장부가 0 이면 정답도 0 이었습니다. 테스트가 이것을 단언합니다.

“아무도 못 받는다” 는 판단은 봇의 결정에서 가장 센 카드입니다. Part 4 의 확정 종료 줄¹¹이 이 판단 위에 서고, 그 줄이 있으면 봇은 점수 계산을 건너뛰고 그대로 냅니다. 여기서 틀리면 봇은 “확실히 이긴다” 고 믿고 낸 수를 받힙니다. 그래서 확정 안전에는 근사 오차를 허용하지 않습니다. 카드 구성과 장수로 증명 될 때만 0 입니다.

// Holds 는 내가 낸 수가 놓인 field 를, 받을 자격이 있는 상대 누구도 받을 수 없다는 것이
// 증명되는지입니다(확정 안전). 받기 중이면 이미 패스한 자리는 뺍니다.
func (l Ledger) Holds(field model.Field, revolution bool, responding bool) bool

5. 비용#

결정 하나에 이 계산을 후보마다 합니다. 4인 판 초반, 미확인 카드 38장, 응수자 셋, 조공 상한이 있는 상태에서 위험 점수 하나의 비용은 싱글 0.03ms, 같은 숫자 0.13ms, 계단 0.43ms 였습니다. 후보가 수십 개여도 Part 1 에서 정한 한 수 100ms 예산 안입니다.

다만 벤치마크는 최악의 손패 로 잽니다. 렉시오 때 평균 손패로 재서 놓친 조합이 125ms 까지 간 적이 있습니다. 같은 무늬가 11장이고 조커가 둘인 손패처럼, 계단 창이 가장 많이 생기는 손패를 따로 두고 잽니다.

정리#

hard 가 보는 것은 easy 와 같습니다. 그 자리의 사람이 화면에서 보는 것, 그리고 이번 판에 나온 카드입니다. 다른 것은 잊지 않는다 는 점과, 그것으로 54장을 네 칸에 나눈 장부 를 결정마다 새로 만든다는 점입니다.

장부는 두 가지를 돌려줍니다. 하나는 “이 자리가 지금 낼 자격이 있는가” 라는 확정 답이고, 대부호에서는 패스한 자리의 자격이 0 이라 달무티보다 단순합니다. 다른 하나는 “자격 있는 누군가가 이 수를 받을 수 있는가” 라는 근사 위험 점수 이고, 확률이라 부르지 않습니다. 단, “아무도 못 받는다” 는 확정 판단만은 오차 없이 증명될 때만 내립니다.

Part 4 는 장부 반대편의 질문입니다. 상대가 아니라 내 손패 를 봅니다. 남은 카드를 몇 수에, 혁명¹²이 일어나면 어떻게, 그리고 반칙 없이 끝낼 수 있는가입니다.

시리즈 목록#

• 대부호 CPU 플레이어 만들기 Part 1: 달무티 봇을 그대로 못 쓰는 이유
• 대부호 CPU 플레이어 만들기 Part 2: 규칙 네 줄짜리 easy 봇
• 대부호 CPU 플레이어 만들기 Part 3: 본 것을 잊지 않는 장부 (이 글)
• 대부호 CPU 플레이어 만들기 Part 4: 혁명을 따라가는 손패 계획
• 대부호 CPU 플레이어 만들기 Part 5: easy 와 hard 는 어디서 갈라지는가
• 대부호 CPU 플레이어 만들기 Part 6: 항목을 하나씩 꺼 보니
• 대부호 CPU 플레이어 만들기 Part 7: 처음 보는 판에서 재다