귀퉁이를 일부러 미루는 AI — 용코바코 리버시가 원조 규칙을 옮기고 뒤집기를 맞춰 본 방법

용코바코 리버시는 「용코바코 전통 전략 시리즈」의 다섯째 게임입니다. 가로세로 8칸 판에서 상대 돌을 내 돌로 앞뒤에서 막아 내 색으로 바꾸는 놀이인데, 요즘 흔히 아는 오셀로가 아니라 그보다 먼저 나온 원조 리버시 규칙을 골랐습니다. 아래는 그 규칙을 코드로 옮기면서 정한 것, 뒤집기 셈이 맞는지 확인한 방법, 그 위에서 AI가 수를 고르는 방식에 대한 메모입니다. 모드마다의 안내는 용코바코 리버시 게임 소개에 있습니다.

갈리는 곳은 첫 네 수입니다

오셀로는 한가운데 네 칸에 흑 둘과 백 둘을 엇갈려 깔아 둔 채로 시작합니다. 원조 리버시는 판을 비워 두고, 두 사람이 그 네 칸(d4 · e4 · d5 · e5)을 흑 · 백 · 흑 · 백 차례로 하나씩 채웁니다. 이 네 수 동안에는 사이에 낄 돌이 생길 수 없으므로 아무것도 뒤집히지 않습니다. 다섯째 수부터가 우리가 아는 리버시입니다.

네 칸을 채우는 차례는 4 × 3 × 2 × 1 = 24가지입니다. 그 가운데 흑 두 개가 대각으로 마주 보는, 그러니까 오셀로의 출발 모양으로 끝나는 차례는 8가지뿐이고, 나머지 16가지는 흑 두 개가 가로나 세로로 맞닿습니다. 무작위로 둔 4,000판에서도 대각 1,334판 · 맞닿음 2,666판으로 거의 정확히 1 대 2가 나왔습니다. 오셀로식 출발을 고르는 설정은 두지 않았습니다. 네 칸을 어느 쪽으로 끌고 갈지부터가 이 규칙에서 처음 부딪히는 자리라고 봤기 때문입니다.

옛 규칙에는 손에 쥐는 돌 이야기도 있습니다. 각자 32개를 들고 두다가 다 떨어지면 상대 것을 빌려 씁니다. 따져 보면 결국 판 위 64칸이 다 찰 때까지 둔다는 말과 같아서, 따로 세지 않고 판에 놓인 돌만 셉니다. 32 대 32로 끝나면 비김입니다.

둘 곳이 없을 때의 넘김은 규칙 파일이 스스로 처리합니다. 한 수를 놓은 뒤 상대에게 놓을 칸이 하나도 없으면 차례를 그대로 돌려주고 그 수에 «넘어감» 표시를 남기며, 두 사람 다 막혔으면 그 자리에서 판을 닫습니다. 무작위 4,000판, 255,627수 가운데 넘어간 수는 1,731번이었고, 판이 다 차기 전에 둘 다 막혀 끝난 판은 45판이었습니다.

한 칸에 놓으면 여덟 줄을 따라갑니다

놓을 수 있는지와 무엇이 뒤집히는지는 같은 셈에서 나옵니다. 빈칸에서 여덟 방향으로 한 칸씩 나아가며 상대 돌이 이어지는 동안 계속 가다가, 처음 만난 상대 돌이 아닌 칸이 내 돌이면 그 사이가 모두 뒤집힙니다. 빈칸이나 판 끝을 만나면 그 방향은 아무것도 아닙니다. 여덟 방향 어디서도 뒤집을 돌이 없으면 그 칸에는 둘 수 없습니다.

규칙은 파일 한 벌뿐이고, 화면 · AI · 서버가 모두 그것을 가져다 씁니다. AI는 판을 그리는 쪽이 멈추지 않도록 화면과 따로 도는 Web Worker 안에서 셈하고, 1:1 대결의 수는 서버의 대국방이 같은 파일로 한 번 더 따져 본 뒤에 판에 올립니다. 화면은 같은 셈을 방향마다 묶어 받아, 한 수에 여러 줄이 넘어갈 때 줄마다 차례로 돌아가는 모습을 그립니다.

못 두는 칸을 누르면 화면이 까닭을 한 줄로 댑니다. 상대 돌이 가장 길게 이어진 방향 하나를 골라, 그 줄 끝이 비어 있는지 판 밖으로 나가는지를 말하는 식입니다. 「c5가 비어 있어요」처럼 칸 이름 뒤에 조사가 붙는데, 칸 이름이 숫자로 끝나므로 그 숫자를 우리말로 읽었을 때의 받침으로 «이»와 «가»를 고릅니다. 1 · 3 · 6 · 7 · 8은 받침이 있고 2 · 4 · 5는 없습니다.

정규식으로 짠 느린 셈과 대 봤습니다

시험에서 답을 대 볼 바깥 판정기가 없어서, 시험 쪽에 생김새가 딴판인 셈을 하나 더 두었습니다. 이쪽은 칸을 하나씩 세지 않습니다. 놓으려는 칸에서 한 방향으로 늘어선 칸들을 «빈칸 · 상대 · 나»를 뜻하는 글자로 이어 적은 다음, 그 글자열이 «상대가 한 번 이상 나온 뒤 내 돌»로 시작하는지를 정규식 하나로 봅니다. 하나는 칸을 세고 하나는 글자를 맞춰 보니, 둘이 똑같이 틀리기는 어렵습니다.

• 무작위 4,000판 — 판마다 끝까지 무작위로 두면서, 매 수마다 «둘 수 있는 칸 목록»과 «칸마다 뒤집히는 돌»을 두 셈에 똑같이 물었습니다. 255,627수 동안 한 곳도 어긋나지 않았습니다.
• 함께 본 것 — 한 수를 두면 내 돌은 «놓은 하나 + 뒤집은 수»만큼 늘고 상대 돌은 뒤집은 수만큼 줍니다. 수의 8%쯤은 무른 뒤 다시 둬서 판이 그대로 돌아오는지 봤고, 끝난 판마다 수 목록을 처음부터 다시 둬서 같은 판과 같은 결과가 나오는지도 봤습니다. 1:1 서버와 이어하기 저장이 «수 목록만 있으면 판을 다시 세울 수 있다»에 기대고 있어서입니다.
• 판이 끝난 모습 — 판이 다 차서 끝난 판 3,955 · 둘 다 막혀 끝난 판 45. 한 수에 가장 많이 뒤집힌 돌은 16개였습니다.

AI는 속도 때문에 둘 곳을 셈하는 부분을 따로 하나 더 가지고 있습니다. 둘레 여덟 칸에 상대 돌이 없는 칸은 여덟 방향을 훑기 전에 미리 걸러 내는 식입니다. 이 셈도 무작위 판 7,679개에서 흑과 백 양쪽으로 15,358번 규칙 파일과 맞춰 보는데, 역시 어긋난 적이 없습니다.

AI는 돌 수보다 «둘 곳 수»를 먼저 봅니다

리버시 엔진으로 이름난 것들은 웹에서 돌리려면 내려받을 것이 크거나, 따로 받아야 하는 평가 파일이 있거나, 여러 줄로 돌면서 사이트 전체에 특별한 보안 머리글을 요구했습니다. 그 머리글은 광고와 허브 안의 게임 화면을 막을 수 있어서, 오목 · 장기와 마찬가지로 작게 직접 짰습니다.

판을 점수로 바꿀 때 보는 것은 다섯 가지입니다.

• 칸마다의 값 — 귀퉁이 120, 귀퉁이와 대각으로 붙은 칸(b2 꼴) −40, 귀퉁이 바로 옆 가장자리(b1 꼴) −20. 귀퉁이를 이미 가졌으면 700을 따로 더하고, 귀퉁이가 빈 채 b2 꼴에 놓인 돌은 180, b1 꼴은 90을 뺍니다.
• 둘 곳 수의 차이 — 내가 놓을 수 있는 칸이 많고 상대가 적을수록 좋습니다. 빈칸이 40개를 넘을 때 가장 무겁고(칸 하나 차이에 78), 빈칸이 16개 이하로 줄면 22까지 가벼워집니다.
• 굳은 돌 — 가진 귀퉁이에서 가장자리를 따라 끊김 없이 이어진 돌은 다시는 뒤집히지 않습니다. 하나에 60.
• 앞줄 돌 — 빈칸에 닿아 있는 내 돌은 상대에게 뒤집을 거리를 줍니다. 하나에 −12.
• 돌 수 — 빈칸이 40개를 넘는 동안은 아예 보지 않다가, 끝으로 갈수록 6, 26으로 무게가 붙습니다.

이 점수로 몇 수 앞까지 갈래를 따라가며(알파베타 탐색) 한 번 본 판은 표에 적어 두고 다시 셈하지 않습니다. 따라갈 수의 차례는 귀퉁이를 먼저, 그다음은 적게 뒤집는 수를 먼저 봅니다. 많이 뒤집는 수가 대개 상대에게 둘 곳을 더 열어 주기 때문입니다.

빈칸이 몇 개 안 남으면 점수 매기기를 그만두고 판 끝까지 모든 갈래를 정확히 풀어 돌 차이가 가장 좋은 수를 고릅니다. 이 끝내기가 정말 최선을 두는지는 빈칸 8개짜리 판 22개를 느리지만 빠짐없이 뒤지는 셈으로 따로 풀어 맞춰 봤고, 22판 모두 최선과 같은 결과를 냈습니다.

단계마다 바뀌는 것

입문과 초급에는 세 가지 버릇을 일부러 붙였습니다. 점수를 무작위로 흔들고, 가끔은 둘 수 있는 칸 아무 데나 두며(입문 22% · 초급 6%), 한 번에 돌을 가장 많이 넘기는 칸이 보이면 앞뒤 따지지 않고 그리로 갑니다(입문 50% · 초급 16%). 리버시를 막 시작했을 때 거의 누구나 거치는 버릇입니다. 무작위 판 40개에서 «가장 많이 뒤집는 수»를 고른 비율을 재 보면 입문 53% · 초급 18% · 중급 10% · 상급 3% · 최상급 10%입니다.

리버시는 한 수에 돌이 여럿 바뀌어서, 답이 너무 빨리 나오면 내 돌이 어디서 넘어갔는지 놓치기 쉽습니다. 그래서 낮은 단계일수록 조금 더 기다렸다가 둡니다 — 상급이 0.25초를 채운 뒤에 놓고, 한 단계 내려갈 때마다 0.1초씩 늘어 입문은 0.55초를 기다립니다. 최상급만 기다림이 없습니다. 개발 컴퓨터에서 다섯 단계로 끝까지 둬 보면 한 수 평균은 0.03~0.05초, 가장 오래 걸린 수도 1초를 넘지 않았습니다.

연습에서 「힌트」를 누르면 AI가 최상급의 설정(8수 · 빈칸 13칸부터 끝내기)으로 1.5초 동안 따져 본 칸 하나에 원을 둘러 줍니다.

맨 위 단계가 귀퉁이를 덜 잡는 까닭

귀퉁이를 둘 수 있는 무작위 판 30개를 모아 단계마다 귀퉁이를 실제로 잡는지 세어 봤습니다. 따로, 귀퉁이가 빈 채 그 대각 옆에 둘 수 있는(그리고 다른 둘 곳도 있는) 판 30개에서는 그 위험한 칸을 피하는지를 셌습니다. 끝내기 풀이가 끼어들지 않도록 둘 다 빈칸이 24개 넘게 남은 판만 썼습니다.

최상급의 53%는 언뜻 고장처럼 보이는 숫자입니다. 하지만 최상급은 귀퉁이에 큰 점수를 주는 같은 판 매기기를 쓰면서 여덟 수 앞까지 따라갑니다. 그 끝에서 «지금 귀퉁이를 잡으면 몇 수 뒤가 더 나빠진다»는 갈래가 보이면, 귀퉁이를 그 자리에서 잡는 대신 더 나은 점수가 나온 다른 수를 고릅니다. 귀퉁이를 잡느냐는 최상급에게 목표가 아니라 판 점수의 일부일 뿐입니다. 그래서 시험에서 최상급의 기준선은 «절반 넘게 잡기»로 낮게 두고, 정말 센지는 아래처럼 직접 맞붙여서 봅니다.

다섯 단계를 서로 붙여 보니

다섯 단계에서 나올 수 있는 열 짝을 모두, 흑과 백을 한 번씩 바꿔 두 판씩 돌려 짝마다 네 판을 두게 했습니다. 한 칸 위아래로 붙은 짝은 이렇습니다.

두 칸 이상 벌어진 여섯 짝에서는 아래 단계가 한 판도 가져가지 못했습니다. 귀퉁이를 덜 잡던 최상급도 상급에게 네 판을 다 이겼으니, 적어도 이 네 판에서는 귀퉁이를 미룬 판단이 손해로 돌아오지 않았습니다. 아래 단계가 이긴 유일한 판은 입문과 초급 사이에서 나왔습니다. 둘 다 일부러 흔들리게 만든 단계라 돌릴 때마다 조금씩 다르게 나옵니다. 사람에게는 단계 사이 간격이 어떻게 느껴질지는 아직 모릅니다 — 그건 실제로 둔 판이 모여야 보입니다.

같은 시리즈의 체스 · 9줄 바둑 · 장기 · 오목도 깔지 않고 브라우저에서 바로 둡니다.