규칙만 알려주고, 삼인 장기 AI를 키웠습니다 (AlphaZero 방식・RTX 3080 한 장으로)

세 사람이 하나의 판을 둘러가는 '삼인 장기'를 만들고, 그 AI를 규칙과 승패 정보만을 가지고 자체 대국 학습시켰습니다. AlphaZero / KataGo와 동일한 방식을 사용했습니다.

완성된 AI는 브라우저만으로 구동됩니다. 친구와 방을 만들어 세 명이 둘 수도 있으며, 자리가 비면 이 AI가 그 자리를 채웁니다.

• 즐기기: https://mataasobo.com/shogi3/
• 친구와 두기: https://mataasobo.com/shogi3/room.html
• 코드 및 학습 기록: https://github.com/sphosino/shogi3

이 글에서는 학습 과정에서 막혔던 부분과, AI가 발견한 '사람의 감각과는 다른 삼인 장기 플레이 방식'에 대해 작성합니다.

삼인 장기의 규칙

• 9×9 판에 파랑(아래에서 위로)・빨강(위에서 아래로)・초록(오른쪽에서 왼쪽으로) 세 사람이 참여합니다.
• 한 사람의 말은 기물(玉, 金2, 銀2, 飛, 角, 歩5), 가지고 온 말로는 향과 계가 있습니다.
• 玉을 잡힌 사람은 탈락하며, 마지막에 남은 1명이 승리합니다. 또 다른 규칙으로, 玉이 적진의 1단목에 들어가면 그 자리에서 바로 승리(입옥)합니다.
• 잡은 말을 어떻게 할지는 세 가지 규칙 중 하나를 선택합니다 (자신의 가지고 온 말로 사용하기 / 남아있는 다른 사람에게 넘겨주기 / 조건을 만족하지 못하면 사라지게 하기).

직접 만든 AI를 포기한 이유

처음에는 기물의 가치 등을 수동으로 작성한 평가 함수와 α-β 탐색을 이용해 만들었습니다. 하지만 세 명이 참여하는 경우, 탐색 방식에 좋은 선택지가 없습니다.

• 편집증적 탐색 (Paranoid Search): '상대 2명이 연합하여 나를 노린다'고 가정하고, 2인용 탐색으로 만듭니다. 가지치기는 효과가 있지만, 실제로는 상대방도 서로 다투기 때문에 판단이 흐트러집니다.
• max^N: 세 사람 각각이 자신의 점수를 최대화한다고 생각합니다. 이것이 올바르지만, 가지치기가 거의 효과를 발휘하지 못합니다.

읽는 깊이를 1단계 늘려도 승률은 33%에서 41% 정도밖에 오르지 않았습니다. 평가 함수의 계수 조정에도 건당 약 75분이 걸립니다. 그래서 자체 대국 학습 방식으로 전환했습니다.

만든 것들

3인용 MCTS

AlphaZero의 탐색(PUCT)을, 가치를 '세 사람 각각의 승률'이라는 세 가지 조합으로 확장했습니다.

• 네트워크는 국면으로부터 '다음 수의 확률'과 '파랑・빨강・초록 각각이 1등이 될 확률'을 출력합니다.
• 탐색의 각 노드에서는, 차례가 된 사람이 자신의 승률이 높은 수를 선택합니다.
• 리프 가치의 세 가지 조합은 그대로 루트까지 더해집니다. 2인 게임처럼 부호를 반전시키지 않습니다.

2인 게임의 '상대방의 점수는 나의 손해'라는 원리가 성립하지 않기 때문에, 이렇게 해야 합니다. '두 사람에게 협공된다'고 가정하지 않으므로, 편집증적 오류도 없습니다.

판을 회전시키지 않는다

2인 장기의 경우, 차례가 된 사람이 보는 방향으로 판을 돌려 맞출 수 있습니다. 하지만 세 명의 경우, 차례가 된 사람을 맞춰도 나머지 2명의 방향이 자리마다 달라집니다. 초기 배치 역시 세 명이 대칭적이지 않습니다. 그래서 판은 회전시키지 않고 그대로의 좌표로 넣고, '지금 누가 차례인지'를 입력으로 알려주었습니다. 대칭성을 이용한 데이터 증강도 불가능합니다.

막혔던 부분

1. 강화학습만으로는 기물의 가치만으로는 승리할 수 없었다

네트워크가 없는 초기 세대는, 기물의 가치만으로 평가하는 간단한 탐색(발판)으로 대국을 만들고, 거기서부터 강화학습을 돌렸습니다. 하지만 수천 판에 걸쳐 네트워크가 발판을 따라잡지 못합니다 (발판 대비 0~8%).

먼저 발판의 대국을 3만 판 만들어 그것을 모방하게 하는 것(증류)으로, 발판에 75% 승리하는 곳에서 시작할 수 있었습니다.

2. 삼인 장기에서는 가치가 승패를 암기한다

삼인 장기는 초반의 승패에 우연이 크게 작용하여, 학습 데이터의 승패를 그대로 외워버렸습니다. 학습에 사용된 대국에서는 초반에도 승패를 74~81% 맞히지만, 아직 보지 못한 대국에서는 전혀 맞히지 못합니다.

가치 교사(Teacher)를 '실제 승자'와 '탐색의 루트 가치'의 절반씩으로 하니 해결되었습니다. 큰 네트워크로 옮길 때도, 교사를 '실제 승패'가 아니라 '교사 네트워크의 출력'으로 하면 같은 국면에서 항상 같은 답이 나오므로 암기가 일어나지 않습니다. 증류한 네트워크가 선생님을 능가했습니다 (선생님 대비 55%).

3. 학습률을 갑자기 올리면 배운 것이 무너진다

증류의 마지막 학습률(0.002)에서, 강화학습을 갑자기 0.02로 시작하니 무너졌습니다. 증류 직후 몇 세대만 낮은 값으로 유지하도록 하고 있습니다.

4. '누구를 노릴지' 유행이 순환한다

세 사람의 경우, 세대별로 '누구의 말을 노릴지' 하는 유행이 바뀌어 강함이 일직선으로 나열되지 않는 경우가 있었습니다(A는 B에게 이기고, B는 C에게 이김, C는 A에게 이김). 자기 대국 중 25%에 과거 세대를 섞자, 과거의 유행에 대한 약점이 사라졌습니다.

5. 사람이 큰 차이를 만들면 AI가 이상해진다

AI 간의 대국에서는 20개 이상의 말 차이가 거의 나지 않습니다(2만 국 중 2국). 그런데 사람이 AI와 두면서 큰 차이를 만들자, AI에게는 본 적 없는 국면이 되었고 판단이 어색해졌습니다. 실제로 큰 차이가 난 국면이나 무작위한 국면부터 다시 두는 대국을 조금 섞어보니, 또 강해졌습니다.

강함의 증가

말의 가치만으로 한 기반을 0으로 하고, 직접 대전 승률에서 쌓아 올린 추정치로 마지막 네트워크는 약 2,310입니다. 12 블록 × 160 채널에서는 정체되었기 때문에 거기서 멈췄습니다(v1.1).

AI가 발견한, 사람의 감각과 다른 싸우는 방식

여기서 가장 재미있었습니다(숫자는 '잡은 말은 자신의 말' 규칙의 자기 대국에서).

공짜로 잡히는 버림말을 자주 둔다

AI는 초반부터 상대방 진영 근처에 큰 말이나 향로를 두어, 그냥 잡힐 것 같은 수(手)를 자주 둡니다.

세대 182의 자기 대국 46수. 파랑이 빨강 진영 근처(9-2, 빨간 원)에 기마를 두고, 다음 수에 빨강이 은으로 그냥 잡았습니다. 그럼에도 불구하고 파랑의 승률 예상은 36.1% → 36.7%로 거의 변하지 않았습니다.

세어보니 다음과 같았습니다.

• 잡히기만 해도, 둔 사람의 승률 예상은 평균 1.5 포인트(기마도 2.2 포인트)밖에 떨어지지 않습니다.
• 노려진 사람을 또 다른 사람이 공격하러 오는 비율이 50~57%입니다(같은 진영 근처에 두는 수). 회의가 없는 '공동 작전'처럼 보입니다.
• 한 국에서 이런 수를 5회 이상 둔 사람의 승률은 약 43%, 0회인 사람은 약 2%였습니다. 다만, 강한 국면이라 공격받을 수 있다는 역방향 효과도 섞여 있습니다.

특히 의문인 것은, 다음으로 두는 사람에게 그냥 잡히는 장소 (둔 사람의 말도, 세 번째 사람의 말도 이득이 없는 칸)에도 두어버린다는 것입니다. 둘인 장기라면 그저 손해입니다.

그래서 AI의 기보에서 이런 '다음 사람에게 그냥 버리는 수'를 60곳 가져와서, 현재 학습 AI에게 국면별로 물어봤습니다(1국면 3200회 읽음).

강한 세대(182 이후)의 대국에서. 비율은 AI가 읽은 후보수 중 '공격 수'(상대방 말을 잡거나, 또는 상대방 진영의 2칸 이내에 두는 수)를 사용한 읽기 비율입니다.

• 그냥 버리는 수가 나오는 경우는,
  버리지 않는 수를 두면 다음 사람에게 공격받기 쉬운 국면에서, 게다가 세 번째 사람은 둔 사람을 노리지 않은 국면이었습니다. - 그리고 AI의 평가에서는, 그냥 버리는 수와 버리지 않는 수는 거의 같았습니다(현재 AI도 그냥 버리는 수를 제일 많이 읽는 국면에서는 차이가 0.1 포인트).

여기서 추측합니다. 세 사람의 경우, 다음 사람에게 자유로운 한 수를 넘기면 자신이 공격받을 수도 있습니다. 말을 한 개 그냥 잡히게 하면, 그 한 수는 '잡는 데' 쓰이고, 차례는 자신을 노리지 않은 세 번째 사람에게 돌아갑니다. AI에게는 말 1개의 손해와, 다음 사람의 1수를 없애는 이득이 거의 균형을 이루는 것처럼 보입니다.

다만, 개수는 60곳으로 적고, '공격 수'를 정하는 방식도 대략적입니다. 정말 그렇게 읽고 있는지는 아직 확실히 할 수 없습니다.

말의 개수로 크게 앞서도 이길 수 없다

최고가 2등에게 12개 이상의 차이를 둔 국면에서도, 그 사람의 승률은 30%로 평균인 33%와 변함이 없었습니다. 가지고 있는 말이 8개 이상 독점해도 26%입니다. 처음에 탈락하는 사람은 대부분 앞서가던 사람이었습니다. 앞서간 사람은 남은 2명으로부터 차례대로 공격받을 수 있습니다.

자리에 따라 유리/불리가 있다

학습이 진행됨에 따라, 파랑의 승률이 낮아졌습니다(세대 213에서 파랑 38%・빨강 42%・초록 20%). 원인은, 파랑과 빨강이 초반에 초록 진영의 줄(1줄)로 향로를 두어 상하로 협박했기 때문입니다. 처음 20수 동안 파랑과 빨강 모두 1줄에 향로를 두는 대국이 62~75% 있습니다. 차례 순서를 바꿔도 고쳐지지 않으므로, 초기 배치 문제입니다.

세대 182의 자기 대국 10수. 빨강이 1-3, 파랑이 1-9에 향로(빨간 원). 초록 진영(점선)은 이것을 싫어하여, 3수째에는 이미 1-5에서 2-5로 도망치고 있다

체스나 바둑에서도 강한 사람끼리 대국할수록 선수의 우위가 명확해졌습니다. 삼인 장기에서도 AI가 강해지면서 녹(緑)의 불리함이 보이기 시작했다고 생각합니다.

브라우저에서 구동하기

학습된 네트워크를 ONNX로 만들어, 브라우저의 ONNX Runtime Web (WebGPU)으로 추론하고 탐색은 Rust를 WebAssembly로 구동하고 있습니다. 서버에서 추론하지 않기 때문에, 플레이어가 늘어나도 비용이 증가하지 않습니다. GPU가 없는 기기에서는 CPU로 조금 얕게 읽습니다.

친구와 두는 방은 Cloudflare Workers와 Durable Objects로 만들었습니다. 서버는 수순이 규칙에 맞는지 확인하고 배분만 하며, 비어 있는 자리의 CPU 수는 방에 있는 사람들의 브라우저가 학습 AI로 생각하여 보냅니다.

맺음말

삼인 장기는 '2인용 상식'으로는 통하지 않는 부분이 많았고, 학습 과정에서 막히는 부분이나 AI의 싸움 방식 모두 2인 장기와는 달랐습니다.

AI와 두는 것도, 친구와 세 명이 두는 것도 브라우저에서 지금 바로 할 수 있습니다. 감상평이나, AI에게 이긴 기보를 보내주시면 감사하겠습니다.

토론