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

Part 3 의 장부1는 상대를 보는 눈이었습니다. 이번 편은 내 손패 를 보는 눈입니다. Part 2 끝에서 easy 가 ♠K · ♥2 · 조커 를 들고 반칙패2로 끝나는 장면을 봤습니다. 사람은 2 와 조커를 쌍으로 먼저 내고 K 로 끝냅니다. 그 차이는 한 수 앞을 보느냐, 손패 전체를 보느냐 입니다.

손패 전체를 보는 장치를 이 시리즈에서는 손패 계획 이라 부릅니다. 렉시오와 달무티에도 있었습니다. 대부호에서 새로 생긴 어려움은 하나, 혁명3 입니다.

1. 두 질문#

손패 계획이 답하는 질문은 둘입니다.

질문이름
남은 손패를 최소 몇 수 에 낼 수 있는가RawMinPlays — 날값
남은 손패를 마지막 수가 합법인 채로 최소 몇 수에 낼 수 있는가MinPlays — 정상 종료4를 만족하는 최소 수

달무티에는 첫 질문만 있었습니다. 어떤 카드로 끝내도 반칙이 아니니까요. 대부호에서는 둘이 갈립니다. ♠K · ♥2 · 조커 는 날값으로는 두 수(K 싱글 + 2·조커 쌍)이고, 정상 종료로도 두 수(2·조커 쌍 → K)입니다. 같은 두 수지만 순서가 다릅니다. 쌍을 먼저 내야 합니다. ♥A · ♥2 · 조커 라면 날값은 한 수 (♥A-2-조커 를 조커로 채운 최강 계단)지만, 조커가 든 수로 끝내는 것은 반칙이므로 정상 종료는 두 수(2·조커 쌍 → A)입니다.

봇은 둘 다 씁니다. 날값은 “이 수를 내면 손패가 얼마나 줄어드는가” 를 재는 자로, 정상 종료 수는 “이 길로 가면 끝낼 수 있는가” 를 묻는 데 씁니다. 정상 종료가 아예 불가능한 손패(조커 한 장만 남은 경우)에서는 날값으로 물러섭니다.

2. 묶음 목록#

계획은 손패를 묶음 으로 나누는 데서 시작합니다. 묶음은 한 수에 낼 수 있는 카드 집합입니다. 싱글, 같은 숫자 여러 장, 같은 무늬 연속 3장 이상의 계단5, 그리고 거기에 조커를 끼운 것들입니다.

대부호의 묶음 목록에는 달무티에 없던 조심할 점이 둘 있습니다.

같은 카드가 두 종류로 읽힙니다. ♥5 와 조커 둘은 “5 석 장” 으로도 “♥3-4-5 계단” 으로도 낼 수 있습니다. 카드 집합은 같지만 종류가 다르면 다른 묶음 입니다. 종류에 따라 받는 쪽의 조건이 다르고 깔맞춤6도 다르게 걸립니다. 그래서 묶음은 (카드 집합, 종류) 쌍입니다.

조커 두 장은 각각 따로 넣습니다. 엔진의 합법 수 목록은 “조커 한 장을 쓰는 수” 를 첫 번째 조커로만 적습니다. 어느 조커를 쓰든 같은 수니까요. 그런데 계획은 남은 손패 를 다시 봅니다. 첫 번째 조커를 쓴 뒤 남은 손패에는 두 번째 조커가 있고, 그 조커로 만들 수 있는 묶음을 목록에서 찾아야 합니다. 첫 번째 조커로만 적어 두면 그 묶음이 없는 것으로 나옵니다. 실제로 사람 화면 쪽에서 같은 원인의 버그가 먼저 났고, 계획기는 그것을 알고 시작했습니다.

// planGroup 은 묶음 하나입니다 — 카드 집합(비트마스크)과 종류.
type planGroup struct {
    mask  uint32           // 손패 안에서 어느 카드들인지
    cards []model.Card
    kind  model.PlayKind   // 같은 숫자 / 계단 — 같은 카드라도 종류가 다르면 다른 묶음
    flips bool             // 같은 숫자 4장 이상 — 이 묶음을 내면 혁명
}

마지막 줄 flips 가 이 편의 주인공입니다.

3. 혁명을 홀짝 하나로#

3.1 왜 어려운가#

혁명은 같은 숫자 4장 이상을 내면 일어나고, 조커를 뺀 서열이 통째로 뒤집힙니다. 다시 4장을 내면 돌아옵니다. 손패 계획에 이것이 왜 문제인지는 두 손패를 견주면 보입니다. 혁명이 없는 상태에서 시작합니다.

손패생각 없이 세면실제로는
3 넉 장 + ♥23 넉 장 → 2 한 장. 그런데 2 로 끝내면 반칙이니 3수?3 넉 장을 내면 혁명. 혁명 중에는 2 가 가장 약한 카드라 2 로 끝내도 정상. 2수
2 넉 장 + ♥32 넉 장 → 3 한 장. 3 은 끝내기 카드니 2수?2 넉 장을 내면 혁명. 혁명 중에는 3 이 반칙 카드. 2 를 석 장 + 한 장으로 쪼개 혁명을 피하고 3 으로 끝내야 함. 3수

같은 모양의 손패인데 답이 2수와 3수로 갈립니다. 반칙 여부가 카드에 붙은 꼬리표가 아니라, 마지막 수를 낼 때의 혁명 상태 로 정해지기 때문입니다. 그러니 계획은 “어떤 순서로 내면 마지막 수를 낼 때 혁명 상태가 어떻게 되어 있는가” 를 알아야 합니다.

3.2 순서를 다 보지 않아도 되는 이유#

손패 13장을 묶음으로 나누는 모든 방법에 순서까지 붙이면 경우의 수가 폭발합니다. 그런데 반칙 규칙을 다시 읽으면 빠져나갈 길이 있습니다.

반칙은 마지막 수 와 그때의 혁명 상태 로만 정해진다.

마지막 수 전까지의 순서는 상관없습니다. 중간에 혁명이 몇 번 일어났든, 마지막 수를 낼 때의 혁명 상태는 그 전까지 낸 혁명 묶음의 개수가 홀수인가 짝수인가 로 정해집니다. 그러니 “어떤 부분집합7을 몇 수에 낼 수 있는가” 를 셀 때, 그 안에 혁명 묶음이 홀수 개인가 짝수 개인가 만 함께 들고 다니면 됩니다.

// best[mask][p] 는 mask 를 묶음으로 나누는 최소 수입니다.
// p 는 그 안의 혁명 묶음 수의 홀짝(0 짝수, 1 홀수)입니다.
best [][2]int8

손패 n 장의 모든 부분집합 2^n 개(13장이면 8,192개)마다 이 값을 채웁니다. 작은 부분집합부터, “가장 낮은 비트의 카드를 덮는 묶음 하나를 고르고 나머지는 이미 계산된 값” 으로 채우는 전형적인 분할 동적 계획8입니다.

flowchart LR
    H["손패<br/>최대 13장"] --> G["묶음 목록<br/>(카드 집합, 종류)<br/>혁명 묶음 표시"]
    G --> T["부분집합 표<br/>2^13 칸<br/>칸마다 (최소 수, 혁명 홀짝)"]
    T --> R["RawMinPlays<br/>날값"]
    T --> M["MinPlays<br/>마지막 수가 그때의<br/>혁명 상태에서 정상인 최소 수"]
    T --> P["Partition<br/>그 순서"]
    style H fill:#FFD700,color:#000000
    style G fill:#D3D3D3,color:#000000
    style T fill:#90EE90,color:#000000
    style R fill:#87CEEB,color:#000000
    style M fill:#87CEEB,color:#000000
    style P fill:#87CEEB,color:#000000

정상 종료 최소 수는 표에서 이렇게 읽습니다. 마지막 묶음 후보 하나를 고르고, 그 묶음을 뺀 나머지의 최소 수와 혁명 홀짝을 표에서 읽습니다. 지금 혁명 상태에 그 홀짝을 더하면 마지막 수를 낼 때의 혁명 상태가 나오고, 그 상태에서 마지막 묶음이 반칙인지를 엔진의 IsForbiddenFinish 로 봅니다. 반칙이 아닌 후보 가운데 가장 짧은 것이 답입니다.

// MinPlays 는 mask 를 내는 최소 제출 수입니다 — 단 마지막 수가 그때의 혁명 상태에서 정상 종료여야 합니다.
// 반칙은 마지막 수와 그때의 혁명 상태로만 정해지므로, 나머지는 순서 없이 혁명 묶음 수의 홀짝만 봅니다.
func (p *Planner) MinPlays(mask uint32, revolution bool) int

3.1 의 두 손패를 이 표로 다시 풀면, 3 넉 장 + ♥2 는 마지막 묶음 ♥2 의 나머지(3 넉 장)가 1수·홀수이고 혁명 중의 2 는 정상이라 2수, 2 넉 장 + ♥3 은 마지막 묶음 ♥3 의 나머지가 “2 넉 장(1수·홀수, 혁명 중 3 은 반칙)” 과 “2 석 장 + 2 한 장(2수·짝수, 평소 3 은 정상)” 두 길이 있어 3수 가 됩니다. 사람이 머리로 하는 것과 같은 계산입니다.

3.3 완전탐색과 견주기#

이 표가 맞는지는 다른 방법으로 구한 정답 과 견줘야 압니다. 손패 7장 이하의 손패 400개를 만들고, 엔진의 합법 수 목록으로 남은 손패를 실제로 다시 펼치면서 혁명 전이를 따라가는 완전탐색9 으로 정답을 구했습니다. 전체 손패와 모든 부분 손패, 혁명 있음·없음 둘에서 날값과 정상 종료 수가 모두 일치했습니다.

7장까지만 비교한 것은 완전탐색이 그 이상에서 느려지기 때문입니다. 표는 13장까지 쓰이지만, 계산의 뼈대가 장수에 따라 바뀌지 않으니 7장에서 맞으면 13장에서도 맞을 것으로 봅니다. 이것은 추론 이고, 그래서 Part 7 의 수동 재생에서 긴 손패의 결정을 다시 눈으로 읽었습니다.

4. 확정 종료 줄#

최소 수는 “내 손패만 보면” 의 이야기입니다. 상대가 받아 버리면 그 수는 통하지 않습니다. 그래서 계획의 두 번째 산출물은 Part 3 의 장부와 손을 잡습니다.

확정 종료 줄 은 이런 순서입니다.

  1. 지금 차례에 첫 수를 낼 수 있습니다(받기라면 필드10를 이깁니다).
  2. 마지막 전까지 매 수가 필드를 그 자리에서 정리하거나(8컷11, ♠3극상12), 아무도 못 받는다고 장부가 증명합니다.
  3. 마지막 수가 그때의 혁명 상태 에서 정상 종료입니다.

이 세 조건을 다 만족하는 순서가 있으면, 그 줄의 첫 수를 내는 순간 판은 끝난 것 입니다. 상대가 무엇을 들었든 끼어들 수 없습니다. 모두 패스하면 리드는 마지막에 낸 사람, 즉 나에게 돌아오고, 나는 다음 수를 내고, 또 아무도 못 받습니다.

// FinishLine 은 확정 종료 줄입니다 — 지금 차례에 첫 수를 낼 수 있고, 마지막 전까지 매 수가 필드를 정리하거나
// 아무도 못 받는다고 holds 가 증명하며, 마지막 수가 그때의 혁명 상태에서 정상 종료인 순서. 가장 짧은 줄입니다.
//
// 줄 안에서는 상대가 카드를 내지 않으므로 장부의 미확인이 줄 끝까지 그대로입니다 — 지금 증명된 것은
// 나중에도 참입니다. 혁명이 바뀌면 그 상태로 다시 증명합니다.
func (p *Planner) FinishLine(field *model.Field, revolution bool, holds Holds) []model.Play

주석의 둘째 단락이 이 장치가 성립하는 이유입니다. 줄 안에서는 상대가 카드를 내지 않습니다. 그러니 장부의 미확인 카드는 줄 끝까지 변하지 않고, 첫 수를 낼 때 증명된 “아무도 못 받는다” 는 마지막까지 참입니다. 단 하나, 혁명이 일어나면 서열이 바뀌니 그 뒤의 수는 혁명 상태로 다시 증명합니다. 2 석 장은 평소에는 거의 무적13이지만 혁명 중에는 가장 약한 석 장입니다.

증명은 장부의 Holds 가 맡습니다. Part 3 에서 오차를 허용하지 않는다 고 적은 바로 그 판단입니다. 위험 점수가 0.02 인 수는 “거의 안전” 이지만 줄에는 들어가지 않습니다. 확률로 깎은 안전은 확정이 아닙니다. 조커 한 장도 ♠3 이 어디 있는지 모르는 한 줄에 들어가지 않습니다.

이 줄이 있으면 hard 는 다른 계산을 하지 않습니다. Part 5 에서 보겠지만, 결정 순서에서 “즉시 끝내기” 바로 다음이 이 줄입니다. 점수보다 앞입니다.

Part 7 의 수동 재생에서 실제로 본 줄은 이런 모양이었습니다. 8 두 장으로 8컷을 걸어 리드를 되찾고, 아무도 못 받는다고 증명된 9 석 장을 내고, 마지막에 K 로 끝냅니다. 그 봇은 2 석 장을 끝까지 아끼다가 이 줄에서 썼습니다.

5. 검증과 비용#

검증표본결과
묶음 목록 = 엔진의 합법 수 목록 + 두 번째 조커 변형무작위 손패 300(같은 무늬가 긴 손패 30 포함)같은 집합
날값·정상 종료 최소 수 = 완전탐색손패 ≤ 7장 400개 × 모든 부분 손패 × 혁명 둘모두 일치
확정 종료 줄의 존재와 길이 = 완전탐색600 상태(받기 절반, 깔맞춤·혁명 포함), 줄이 있는 상태 136모두 일치
엔진으로 실제 재생 — 상대가 증명에 쓴 카드를 쥐고 받으려 함줄이 있는 상태 전부매 수 뒤 리드가 돌아오고, 마지막 수가 정상 종료

마지막 줄은 조금 다른 종류의 검증입니다. 계획기가 “아무도 못 받는다” 고 한 줄을, 실제 엔진에서 상대들이 받을 수 있는 카드를 최대한 들고 받으려 해 보게 한 것입니다. 받지 못했습니다. 계획기와 장부가 서로 맞는지를 둘 밖에서 확인한 셈입니다.

비용은 최악의 손패로 잽니다. 같은 무늬 11장 + 조커 둘은 묶음이 1,093개 생기는 손패입니다. 처음 구현은 이 손패의 표를 만드는 데 13ms 가 걸렸습니다. 계단 창마다 쥔 카드의 모든 부분집합을 돌았기 때문입니다. “빼는 카드만 고르기” 로 바꾸고, 안쪽 루프의 할당을 평평한 배열로 바꿔 3.4ms 가 됐습니다. 그 뒤 후보 13개마다 “이 수를 낸 뒤의 최소 수” 를 읽는 것은 0.06ms 입니다. 표를 한 번 만들어 두면 후보 비교는 거의 공짜입니다.

정리#

손패 계획은 두 질문에 답합니다. 최소 몇 수인가(날값), 그리고 마지막 수가 합법인 채로 최소 몇 수인가(정상 종료). 대부호에서는 혁명 때문에 둘이 갈리고, 반칙이 “마지막 수와 그때의 혁명 상태” 로만 정해진다는 규칙 덕에 혁명 묶음 수의 홀짝 하나만 들고 다니면 순서를 다 보지 않아도 됩니다.

그 위에 장부의 확정 안전을 이어 붙이면 확정 종료 줄 이 나옵니다. 첫 수를 내는 순간 판이 끝난 것이 증명되는 순서입니다.

이제 재료가 다 모였습니다. 장부(상대), 계획(내 손패), 그리고 easy 의 수(기준). Part 5 에서 이것들을 어떤 순서로 쓰는지, 그리고 그 결과 easy 와 hard 가 같은 자리에서 어디서 갈라지는지를 그림 하나로 봅니다.

시리즈 목록#

  1. 장부: 이번 판에 나온 카드를 기억해 «아직 안 나온 카드가 어디 있을 수 있는가» 를 정리한 것입니다. Part 3 에서 설명합니다. ↩︎

  2. 반칙패: 조커·2(혁명 중에는 3)·8 만으로 된 수·♠3 한 장으로 손패를 비우면 그 판 꼴찌가 되는 규칙입니다. ↩︎

  3. 혁명: 같은 숫자 4장 이상을 한 번에 내면 조커를 뺀 카드 서열이 통째로 뒤집히는 규칙입니다. 다시 4장을 내면 돌아오고, 판이 끝나면 풀립니다. ↩︎

  4. 정상 종료: 반칙패가 되는 카드로 끝내지 않고 손패를 비우는 것입니다. ↩︎

  5. 계단: 같은 무늬의 연속한 숫자 3장 이상(예: ♠5 ♠6 ♠7)을 한 수로 내는 조합입니다. 조커가 빈 자리를 채울 수 있습니다. ↩︎

  6. 깔맞춤: 같은 무늬의 수가 두 번 이어지면 그 필드에서는 그 무늬로만 받을 수 있게 되는 규칙입니다. ↩︎

  7. 부분집합: 손패 n 장 가운데 «어느 카드들을 골랐는가» 의 한 경우입니다. 모든 경우는 2^n 가지이고, 13장이면 8,192가지입니다. ↩︎

  8. 동적 계획(dynamic programming): 큰 문제를 작은 문제로 쪼개고, 작은 문제의 답을 표에 적어 두었다가 다시 써서 큰 문제를 푸는 방법입니다. 여기서는 «손패의 일부를 몇 수에 낼 수 있는가» 를 작은 부분부터 채워 올라갑니다. ↩︎

  9. 완전탐색: 가능한 경우를 하나도 빼지 않고 전부 세어 정답을 구하는 방법입니다. 느리지만 틀릴 수 없어서, 빠른 근사 계산이 맞는지 확인하는 «정답지» 로 씁니다. ↩︎

  10. 리드 / 받기 / 필드: 필드는 테이블에 놓여 있는 지금의 카드(들)입니다. 필드가 비어 있을 때 첫 수를 내는 것이 «리드», 놓인 필드보다 센 수로 이어 내는 것이 «받기» 입니다. 모두가 패스하면 필드가 정리되고 마지막에 낸 사람이 다시 리드합니다. ↩︎

  11. 8컷: 8 이 든 싱글이나 같은 숫자 묶음을 내면 즉시 필드가 정리되고 낸 사람이 다시 리드하는 규칙입니다(계단 속 8 은 예외). ↩︎

  12. ♠3극상: 조커 한 장은 최강의 싱글이지만 오직 ♠3 한 장으로만 받을 수 있고, 받으면 필드가 정리되는 규칙입니다. ↩︎

  13. 무적: 덱 구성상 어떤 카드로도 받을 수 없는 수입니다. 예를 들어 2 석 장은 2 보다 센 숫자가 없고 조커는 두 장뿐이라 받을 수 없습니다. ↩︎