컴퓨터는 어떻게 다음 수를 고를까? 게임 컴퓨터의 단계가 갈리는 원리

컴퓨터는 무엇을 '생각'할까

컴퓨터와 장기를 두다 보면 신기한 순간이 있어요. 내가 몰래 준비한 포 장군을 미리 알고 막아 버리거나, 별것 아닌 것처럼 보이던 수가 세 수 뒤에 외통으로 이어지는 순간이요. 컴퓨터는 어떻게 이런 수를 찾을까요?

컴퓨터는 사람처럼 '느낌'으로 두지 않아요. 대신 둘 수 있는 수를 하나하나 실제로 둬 보고, 그 뒤에 상대가 둘 수를 또 둬 보고, 그렇게 몇 수 앞까지 펼쳐 본 다음 가장 좋은 길을 고르는 방식으로 둬요. 이 글에서는 이 원리를 쉬운 말로 풀어 보고, 이 사이트의 미니게임 컴퓨터가 1단계부터 10단계까지 무엇이 다른지, 실제로 이웃한 단계끼리 두면 결과가 어떻게 나오는지 정리했어요.

몇 수 앞을 펼쳐 보는 '게임 나무'

지금 판에서 내가 둘 수 있는 수가 30가지라고 해 볼게요. 30가지 수 하나하나에 대해 상대도 또 30가지쯤 응수할 수 있어요. 이걸 그림으로 그리면 줄기에서 가지가 갈라지고, 그 가지에서 또 가지가 갈라지는 나무 모양이 돼요. 그래서 이것을 게임 나무라고 불러요.

이 글에서 '몇 수 앞'은 나와 상대가 번갈아 한 번씩 두는 것을 각각 한 수로 센 거예요. 내가 두고 상대가 받으면 두 수예요. 한 수에 30가지씩이라면 두 수 앞은 900가지, 네 수 앞은 81만 가지, 여섯 수 앞은 7억 가지가 넘어요. 나무가 이렇게 금방 커지니 컴퓨터도 판이 끝날 때까지 모두 펼쳐 보지는 못하고, 정해진 깊이까지만 내다봐요. 체스·장기·돌 뒤집기에서는 이 깊이가 단계를 가르는 중요한 기준 중 하나예요.

판을 점수로 바꾸는 '평가 함수'

정해진 깊이까지 내다본 뒤에는 그 끝의 판이 나에게 얼마나 좋은지를 숫자 하나로 매겨야 해요. 이 일을 하는 계산을 평가 함수라고 해요. 이 사이트의 컴퓨터는 이런 것들을 점수로 셈해요.

• 체스: 말의 가치(폰 100, 나이트 320, 비숍 330, 룩 500, 퀸 900)와 말마다 좋은 자리 표. 같은 나이트라도 판 가운데에 있으면 점수가 높아요.
• 장기: 전통 점수와 같은 비율의 말 가치(차 1300, 포 700, 마 500, 상·사 300, 졸 200)와 자리 점수.
• 돌 뒤집기: 칸마다 정해 둔 가치와 둘 수 있는 곳의 수, 끝판에는 돌 수. 자세한 내용은 돌 뒤집기(리버시) 잘 두는 법에 정리했어요.
• 오목: 줄의 모양. 다섯이 되는 자리, 4, 열린 3 같은 모양에 큰 점수를 주고 상대의 모양을 막는 수에도 점수를 줘요.

평가 함수가 판을 얼마나 잘 읽느냐가 컴퓨터의 '감각'이고, 몇 수 앞까지 펼쳐 보느냐가 '수읽기'라고 할 수 있어요.

상대도 최선을 다한다고 가정해요

나무 끝의 점수를 모았으면 거꾸로 올라오며 수를 골라요. 이때 중요한 약속이 있어요. 내 차례에는 나에게 가장 좋은 수를, 상대 차례에는 상대에게 가장 좋은(나에게 가장 나쁜) 수를 둔다고 가정하는 거예요. 이 방식을 '최소최대(미니맥스)'라고 불러요. 상대가 실수해 주길 바라는 수가 아니라, 상대가 최선으로 막아도 괜찮은 수를 고르는 셈이에요.

여기에 계산을 크게 줄이는 요령이 붙어요. 어떤 수를 살펴보다가 "이 길은 이미 앞에서 찾은 수보다 나빠질 게 확실하다"는 게 드러나면, 그 가지의 나머지는 더 볼 필요가 없어요. 이렇게 가지를 쳐 내는 방법을 알파베타 가지치기라고 해요. 좋은 수부터 먼저 살펴보면 쳐 낼 수 있는 가지가 많아져서, 같은 시간에 훨씬 깊이 볼 수 있어요. 이 사이트의 체스·장기·돌 뒤집기 컴퓨터가 모두 이 방식을 써요.

체스와 장기 컴퓨터는 몇 가지를 더 해요. 정해진 깊이에서 딱 멈추면 "내가 말을 잡았는데 바로 다음 수에 다시 잡히는" 장면을 놓칠 수 있어요. 그래서 3단계부터는 깊이 끝에서도 잡고 잡히는 수가 잠잠해질 때까지 조금 더 따라가 봐요. 체스 컴퓨터는 체크를 받은 장면에서는 한 수를 더 내다보고요.

오목 컴퓨터는 방식이 조금 달라요. 오목은 둘 수 있는 칸이 아주 많아서 모든 수를 펼치기보다는, 줄의 모양으로 좋은 후보를 고른 다음 4를 연달아 만들어 이기는 수순이 있는지를 깊이 찾아봐요. 4단계는 이 수순을 4수까지, 10단계는 14수까지 찾고, 8단계부터는 3과 4를 섞어 이기는 수순도 찾아봐요. 그래서 오목은 깊이보다 이런 수순을 얼마나 길게 찾느냐와 상대 모양을 얼마나 잘 알아채느냐로 단계가 갈려요.

일부러 약하게 만드는 법

컴퓨터를 강하게 만드는 것보다 '알맞게 약하게' 만드는 게 더 어려울 때가 있어요. 너무 엉뚱하게 두면 재미가 없고, 너무 정확하면 이길 수가 없으니까요. 이 사이트는 이런 방법을 섞어서 단계를 나눴어요.

• 덜 내다보기: 체스 1~3단계는 한 수 앞만 보고, 4·5단계는 두 수, 6·7단계는 세 수, 8·9단계는 네 수, 10단계는 다섯 수가 기본이에요. 높은 단계는 시간이 남으면 더 깊이(체스 10단계는 여덟 수까지) 봐요. 장기도 비슷하게 나뉘어 있어요.
• 점수 흔들기: 수마다 점수에 무작위 값을 더해요. 흔들림이 크면 최선이 아닌 수를 자주 골라요. 체스 1단계는 폰 네 개 값만큼(400점) 흔들고, 단계가 오를수록 줄여서 체스·장기·돌 뒤집기 모두 9·10단계에서는 흔들지 않아요. 오목은 좋은 후보 몇 개 중에서 고르는 폭을 단계마다 좁혀요.
• 가끔 아무 수나: 체스와 장기 1단계는 45%, 2단계는 25% 확률로 아무 수나 둬요. 처음 배우는 사람이 이길 수 있도록요. 돌 뒤집기 1단계는 늘 둘 수 있는 곳 중 아무 데나 둬요.
• 알아채지 못하기: 오목 1단계는 바로 다섯을 만들 수 있는 자리도 30% 확률로 놓치고, 상대의 4를 알아챌 확률도 55%뿐이에요. 3단계부터는 다섯과 4를 놓치지 않아요.
• 생각 시간: 높은 단계는 한 수에 쓸 시간을 정해 두고(체스 10단계 2.8초, 장기 10단계 3초, 오목 10단계 2.5초 등), 그 안에서 더 깊이 볼 수 있으면 더 봐요.

이웃한 단계끼리 둬 보니

정말 단계가 오를수록 강해질까요? 이 사이트의 컴퓨터끼리 바로 이웃한 단계(1단계와 2단계, 2단계와 3단계 …)로 여러 판을 두게 해 봤어요. 먼저 두기와 나중 두기는 번갈아 바꿨어요. 아래는 사람의 대국이 아니라 사이트 컴퓨터끼리 둔 결과이고, 판 수가 많지 않아 대략적인 경향으로 봐 주세요.

오목은 40판씩, 나머지 게임은 20판씩 둬서 위 단계가 몇 판을 이겼는지 셌어요.

• 오목(40판씩): 1·2단계 판부터 위 단계가 29승, 34승, 28승, 27승, 22승, 22승, 22승, 20승, 14승을 거뒀어요(맨 끝이 9·10단계). 6·7단계 판부터는 225칸이 다 차도록 승부가 안 나는 무승부가 8~13판씩 나왔어요.
• 돌 뒤집기(20판씩): 위 단계가 18승, 13승, 16승, 14승, 13승, 14승, 17승, 8승, 11승이에요. 8·9단계 판에서는 9단계가 8승 12패로 오히려 밀렸어요.
• 체스(20판씩): 위 단계가 15승, 20승, 20승, 19승, 20승, 18승까지 거의 다 이기다가, 7·8단계 판부터 무승부가 늘어 6승 4패 10무, 9승 2패 9무, 10승 0패 10무가 됐어요.
• 장기(20판씩): 위 단계가 16승, 20승, 17승, 15승, 18승을 거두다가 6·7단계 판은 10승 10패였고, 이어서 18승, 18승, 9·10단계 판은 9승 11패였어요.

대부분의 판에서 위 단계가 더 많이 이겼어요. 특히 체스·장기의 낮은 단계는 아무 수나 두는 확률과 점수 흔들림이 단계마다 크게 줄어서, 위 단계가 20판 중 15판 이상을 가져갔어요. 오목과 돌 뒤집기는 낮은 단계에서도 아래 단계가 꽤 이겼고, 단계가 높아진다고 차이가 고르게 줄어들지도 않았어요. 어느 단계 사이가 크게 벌어지는지는 그 두 단계의 설정이 얼마나 다른지에 달려 있어요. 장기 6단계와 7단계는 똑같이 세 수 앞을 보고 흔들림만 조금 달라서 10승 10패가 나왔고, 체스는 7·8단계 판부터 서로 실수가 적어져 비기는 판이 절반 가까이 됐어요. 돌 뒤집기 8·9단계, 장기 9·10단계처럼 위 단계가 밀린 판도 있어요. 여기에는 판 수가 적다는 것 말고도 이유가 하나 더 있어요. 9·10단계는 점수 흔들림이 없어서, 같은 쪽을 잡고 두면 거의 같은 수순이 되풀이되기 쉬워요. 체스 9·10단계 판이 정확히 10승 10무로 갈린 것도 몇 가지 판이 반복된 결과에 가까워요. 실제로 오목 10단계끼리 둔 판을 살펴보니 백의 첫 수 여덟 가지에 따라 정해진 여덟 가지 판뿐이었어요. 그래서 높은 단계의 숫자는 판 수만큼 믿기 어렵고, "9단계가 8단계보다 약하다"는 뜻으로 보면 안 돼요.

생각 시간도 단계에 따라 크게 달랐어요. 이 계산을 돌린 컴퓨터에서 낮은 단계는 한 수에 1,000분의 몇 초면 충분했지만, 10단계는 한 수에 평균 체스 약 2.3초, 장기 약 2.4초, 돌 뒤집기 약 1.9초를 썼어요. 오목 10단계는 평균 0.15초 정도였지만, 어려운 자리에서는 1.5초까지 생각했어요. 같은 시간이라도 내다볼 수 있는 깊이는 기기마다 달라요.

계산은 내 기기 안에서 해요

이 사이트의 컴퓨터는 서버가 아니라 내 휴대폰이나 컴퓨터의 브라우저 안에서 계산해요. 화면이 멈추지 않도록 계산을 따로 맡는 '웹 워커'라는 기능을 써요. 수를 고를 때 서버에 물어보지 않고, 깬 단계 같은 진행 기록도 지금 쓰는 브라우저에만 저장돼요.

대신 기기의 성능이 영향을 줘요. 높은 단계는 정해진 생각 시간 안에서 계산하기 때문에, 느린 기기에서는 같은 시간에 조금 덜 깊이 봐요. 그래서 오래된 휴대폰에서는 높은 단계가 아주 조금 약하게 느껴질 수도 있어요.

1997년 체스 컴퓨터 딥블루가 세계 챔피언 카스파로프를 이기고, 2016년 알파고가 이세돌 9단을 4대 1로 이긴 뒤로 게임 컴퓨터는 사람보다 훨씬 강해졌어요. 이 사이트의 컴퓨터는 그런 최강의 컴퓨터가 아니라, 사람이 한 단계씩 이겨 가며 실력이 느는 것을 목표로 만든 상대예요. 미니게임에서 1단계부터 도전해 보고, 무르기 없이 이겨 ★을 모아 보세요. 오목에서 먼저 두는 쪽이 얼마나 유리한지는 오목은 왜 흑이 유리할까?에서 컴퓨터끼리 둔 결과로 따로 살펴봤어요.