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


11월 초 부호공주 봇의 다음 개선 후보를 정리한 문서에는 하지 않을 일의 목록도 있었습니다. 그중 한 줄이 탐색의 뿌리에서 표본을 나누는 방식을 밴딧 알고리즘으로 바꾸는 것이었습니다. 이유는 짧았습니다. UEC 컴퓨터 대빈민 대회에서도 효과가 잡음 수준이었고, 후보가 둘에서 넷뿐인 지금 탐색에서는 더 작으리라는 것이었습니다.

Part 1 을 쓰고 나니 이 한 줄을 그냥 넘기기 어려웠습니다. 뿌리의 롤아웃은 마지막에 수 하나를 고르기 위한 예산이고, 그런 문제에 맞는 알고리즘이 따로 있다는 것을 막 정리한 참이었기 때문입니다. 그래서 이번에는 그 한 줄을 숫자로 확인해 보기로 했습니다.

봇의 뿌리에 놓인 슬롯머신#

hard 봇이 수를 고르는 과정의 마지막 단계는 탐색입니다. 점수 층이 고른 수, Easy 봇이라면 둘 수, 받는 차례라면 패스, 그리고 점수 상위 두 수를 후보로 모읍니다. 겹치는 것을 빼면 후보는 둘에서 넷입니다. 장부와 맞는 상대 손패 표본을 16개 뽑고, 후보마다 그 16개 판을 끝까지 굴려 평균 순위가 가장 좋은 수를 둡니다. 롤아웃 안에서 봇 자신은 탐색 없는 hard 로, 상대들은 Easy 로 둡니다.

Part 1 의 말로 옮기면 후보 하나가 슬롯머신 한 대이고, 롤아웃 한 번이 레버 한 번이며, 그 판의 순위가 상금입니다. 머신마다 16번씩 똑같이 당기는 것이니 균등 배분입니다. 그리고 굴려 본 판은 아무 점수도 남기지 않고 마지막에 고른 수만 남으므로, 이 문제는 버는 문제가 아니라 고르는 문제입니다.

탐색은 손패가 다섯 장 이하일 때만 돕니다. 결정 하나에 쓸 수 있는 시간이 로컬 기준 p99 20ms 로 정해져 있고, 손패가 많을수록 롤아웃이 비싸기 때문입니다. 10월 실험에서 표본 수는 강함을 크게 좌우했습니다. 표본을 4개, 8개, 16개로 늘리자 탐색 없는 봇과의 평균 순위 차이가 −0.030, −0.054, −0.064 로 벌어졌습니다(음수가 좋은 쪽입니다). 그 뒤 4인 판에서 탐색 범위를 손패 여섯에서 여덟 장으로 넓히려 했을 때는 시간 한도를 지키려고 표본을 6~12개로 줄여야 했고, 다섯 설정이 모두 운영 봇과 구별되지 않았습니다. 그때 남긴 결론은 범위를 넓힌 이득을 표본이 줄어든 잡음이 지운다는 것이었습니다.

같은 예산을 더 잘 나누는 것이 밴딧이 약속하는 일입니다. 범위를 넓히는 데 막힌 자리가 바로 그 자리였습니다.

대회 봇들이 해 본 것#

UEC 컴퓨터 대빈민 대회에서 2018년 이후 우승한 프로그램 상당수는 오오토 가쓰키의 Blauweregen 을 고친 것이었습니다. 오오토가 공개한 소스에서 뿌리의 배분은 이렇습니다. 후보가 둘이면 양쪽에 똑같이 나눕니다. 셋 이상이면 네 번씩 굴려 본 뒤, 평균에 0.7·√(√N / nᵢ) 를 더한 값이 가장 큰 후보를 다음에 굴립니다. N 은 전체 롤아웃 수, nᵢ 는 그 후보의 롤아웃 수입니다. Part 1 에서 본 톨핀과 시모니가 뿌리용으로 제안한 UCB√ 규칙이고, 학습한 정책의 점수를 미리 몇 번 굴린 것처럼 얹어 시작합니다.

그 뒤 대회 참가자들은 이 자리를 여러 번 바꿔 보았습니다.

  • 2018년 tommy 는 UCB 를 Thompson 샘플링으로 바꿨습니다. 슬라이드에는 몬테카를로 탐색의 목적이 최선의 수를 찾는 것이라 보상을 최대로 하는 밴딧과는 어긋난다는 설명과 함께, 바꿨더니 조금 강해진 것 같다는 물음표 달린 평가가 있습니다.
  • 2019년 grease 는 최선의 팔을 가려내는 문제의 풀이인 연속 제거 방식을 썼습니다. 1만 시합씩 수십 번 붙여 본 결과는 Blauweregen 과 grease, tommy, 그리고 같은 계열의 lilovyy 가 거의 같은 강함이었습니다.
  • CloneArgo 는 UCB1 으로 바꿔 2019년 발표에서 승률이 조금 좋았다고 했지만, 시합 수가 적어 통계적으로 확실하지 않다고 스스로 적었습니다.

오오토의 2016년 논문에는 교사로 쓴 프로그램 15개의 기보에서 잰 평균 후보 수가 있는데, 5.6~6.8개였습니다. 같은 예산으로 균등 배분과 UCB 를 정면으로 견준 자료는 찾지 못했습니다.

재는 방법#

봇 저장소의 사본에서 운영 hard 봇 넷이 4인 매치 240개(매치당 4판)를 두게 하고, 1번 자리가 점수 단계까지 간 결정 7,122개를 모았습니다. 바로 나갈 수 있는 수, 확정 종료 줄, 위협 차단처럼 탐색 전에 결정이 끝나는 경우는 뺐습니다. 이 결정들의 합법 후보는 평균 8.4개, 중앙값 5개, 많게는 84개였습니다.

결정마다 후보 집합을 둘 만들었습니다. 하나는 지금 탐색이 보는 후보 그대로이고(평균 2.67개), 다른 하나는 여기에 점수 순으로 후보를 더해 12개까지 넓힌 것입니다(평균 6.30개). 그리고 장부에서 표본 768개를 뽑아 넓힌 후보 모두를 768판씩 끝까지 굴렸습니다. 앞의 512판으로 낸 평균 순위를 그 결정의 기준으로 삼고, 뒤의 256판을 순서를 바꿔 가며 50번 꺼내 쓰면서 배분 방법들을 재생했습니다. 같은 판을 쓰므로 방법끼리의 차이는 운이 아니라 배분에서 나옵니다.

잰 것은 기준으로 가장 좋은 후보를 골랐는지와, 못 골랐다면 기준 평균 순위로 얼마를 놓쳤는지입니다. 기준이라고 했지만 이것은 롤아웃 모형이 보는 정답입니다. 롤아웃 속 상대가 Easy 이므로 실제 판의 정답과는 다를 수 있고, 이 문제는 글 끝에서 다시 다룹니다.

후보가 둘이면 할 일이 없습니다#

아래 표는 넓힌 후보 집합을 후보 수로 나누어, 결정마다 롤아웃 64번을 쓸 때 기준의 최선을 고른 비율입니다. 맨 아래 줄의 독립 표본은 균등 배분이되 후보마다 다른 판을 굴린 경우입니다.

방법후보 2후보 3~4후보 5~8후보 9~12
결정 수1,5931,6121,6252,292
균등82.8%66.4%51.5%34.0%
UCB182.7%65.9%51.5%34.4%
Thompson80.1%60.9%45.1%30.6%
Sequential Halving82.8%67.3%54.0%38.1%
균등, 독립 표본79.3%59.7%45.2%31.4%

후보가 둘일 때 Sequential Halving 은 균등 배분과 똑같은 계산입니다. 라운드가 하나뿐이라 둘에게 예산을 반씩 주고 끝나기 때문입니다. 오오토의 코드가 후보 둘에서 똑같이 나누는 것도 같은 이유일 것입니다. UCB1 도 차이가 0.1%p 였습니다. 후보가 셋에서 넷일 때 Sequential Halving 이 0.9%p 앞섰고, 놓친 값으로는 평균 순위 0.0016 이었습니다. 지금 탐색이 보는 후보 집합 전체로 보면 Sequential Halving 이 균등 배분보다 아끼는 몫은 평균 순위 0.0007 이었습니다. 11월의 문서가 옳았습니다.

같은 판을 굴리는 쪽이 더 컸습니다#

표에서 가장 큰 차이는 밴딧끼리가 아니라 맨 아래 줄에 있습니다. 같은 균등 배분이라도 후보마다 다른 판을 굴리면 최선을 고르는 비율이 후보 수와 관계없이 2.6~6.7%p 떨어졌습니다. 지금 후보 집합에서 놓친 값은 평균 순위 0.0041 늘었는데, Sequential Halving 이 아끼는 몫의 여섯 배에 가깝습니다.

이유는 대부호의 판이 손패 배분에 크게 좌우된다는 데 있습니다. 상대에게 2와 조커가 몰린 판이면 어떤 수를 두든 순위가 나쁘고, 반대면 어떤 수든 좋습니다. 두 후보를 같은 판에서 견주면 그 몫이 양쪽에서 함께 빠지고 수의 차이만 남습니다. 봇 코드의 주석은 이것을 공통 난수라고 부릅니다. 밴딧이 후보마다 굴리는 횟수를 다르게 하는 순간 이 짝은 조금씩 어긋납니다. Thompson 이 균등 배분보다도 못한 데에는 그 몫도 있을 것이고, Part 1 의 ε-greedy 처럼 앞선 후보에 몰아 굴리느라 덜 굴린 후보의 평균이 흔들리는 탓도 있을 것입니다.

후보가 열 개면 달라집니다#

표의 오른쪽 끝에서는 이야기가 바뀝니다. 후보가 9~12개면 64번을 똑같이 나눠도 한 후보에 대여섯 번밖에 돌아가지 않습니다. 균등 배분은 34.0% 만 최선을 골랐고, Sequential Halving 은 38.1% 를 골랐습니다. 놓친 값은 0.0815 에서 0.0628 로 줄었습니다. 예산을 256번으로 늘려도 순서는 같아서, 48.1% 대 42.3% 였습니다.

그렇다면 탐색이 보는 후보를 넓히고 Sequential Halving 으로 나누면 되지 않겠습니까? 이것을 재려면 질문을 바꿔야 합니다. 최선을 얼마나 자주 고르느냐가 아니라, 탐색하지 않고 점수 층의 수를 그냥 둘 때보다 평균 순위가 얼마나 좋아지느냐입니다. 결정당 롤아웃이 64번일 때 그 값은 지금 후보에 균등 배분이 +0.025, 넓힌 후보에 균등 배분이 +0.014, 넓힌 후보에 Sequential Halving 이 +0.022 였습니다. 256번으로 늘리면 같은 순서로 +0.037, +0.036, +0.041 이었습니다.

64번에서는 넓히는 것이 손해였습니다. 기준으로 따지면 넓힌 집합 안에 점수 층의 수보다 나은 수가 더 있습니다. 집합 안의 최선이 점수 층의 수보다 나은 몫이 지금 후보에서는 평균 순위 0.041, 넓힌 후보에서는 0.053 이었습니다. 그런데 후보가 늘어난 만큼 한 후보에 돌아가는 판이 줄고, 그 잡음이 더 찾은 몫을 먹어 버립니다. 10월의 범위 넓히기가 막힌 것과 같은 모양입니다. Sequential Halving 은 그 손해를 대부분 되찾았지만 지금 후보를 그대로 두는 것을 넘지는 못했습니다. 256번이 되어서야 넓힌 후보와 Sequential Halving 의 조합이 가장 좋아졌습니다.

점수 층이 고른 상위 두세 수는 오오토의 프로그램이 정책 점수로 얹는 사전 분포와 같은 일을 하고 있었던 셈입니다. 예산이 적을 때는 그럴듯한 후보만 굴리는 것 자체가 가장 강한 가지치기입니다.

대국에서는#

모형 안의 이득이 실제 판으로 옮겨 가는지는 대국으로 재야 합니다. 시뮬레이터에서 운영 봇과 탐색만 다른 봇을 4인 판에 앉혔습니다. 후보 봇 하나와 운영 봇 셋, 거꾸로 운영 봇 하나와 후보 봇 셋을 자리를 돌려 가며 두고, 4판·8판·12판 매치를 seed 128개씩 돌렸습니다. 후보 봇은 탐색 범위 안의 결정마다 롤아웃 64번을 씁니다. 운영 봇은 손패 다섯 장 이하에서만 후보마다 16번씩, 결정당 32~64번을 씁니다. Δ 는 후보 봇의 판당 평균 순위가 운영 봇과 얼마나 다른지이고, 음수가 후보가 나은 쪽입니다.

탐색 범위후보배분Δ [95% 신뢰구간]결정 p99
손패 5장 이하지금균등+0.014 [+0.001, +0.027]18.6ms
손패 5장 이하넓힘균등+0.013 [−0.004, +0.029]18.2ms
손패 5장 이하넓힘Sequential Halving+0.010 [−0.007, +0.027]18.5ms
손패 8장 이하지금균등−0.016 [−0.036, +0.004]40.9ms
손패 8장 이하넓힘균등+0.010 [−0.012, +0.032]39.4ms
손패 8장 이하넓힘Sequential Halving−0.002 [−0.025, +0.021]39.9ms

어느 것도 운영 봇과 구별되지 않았습니다. 첫 줄은 신뢰구간이 겨우 0 을 비켜 갔지만, 여섯 번을 재면 이 정도 하나는 우연으로도 자주 나옵니다. 저는 잡음으로 봅니다.

여덟 장까지 넓힌 세 줄의 순서는 앞에서 롤아웃 모형이 매긴 순서와 같습니다. 지금 후보에 예산을 몰아준 쪽이 가장 좋았고, 넓힌 후보에서는 Sequential Halving 이 균등 배분보다 나았습니다. 두 배분을 같은 seed 끼리 짝지어 보면 차이는 −0.012 [−0.037, +0.013] 이었습니다. 모형에서 기대한 크기와 어긋나지 않지만, seed 128개로 가려낼 수 있는 크기는 아닙니다. 게다가 여덟 장까지 탐색하는 봇은 결정 p99 가 40ms 안팎이라 운영 봇이 지키는 20ms 를 두 배 넘깁니다.

롤아웃이 보는 정답#

재생 실험의 숫자는 모두 롤아웃 모형이 매긴 정답을 기준으로 했습니다. 모형은 상대를 Easy 로 둡니다. 10월에 롤아웃 속 모든 자리를 Easy 로 두고 판의 모든 국면에서 탐색했더니, 탐색하지 않는 봇보다 평균 순위가 0.306 나빠진 적이 있습니다. 모형이 고른 최선이 실제 최선이 아닐 수 있다는 뜻입니다. 11월 초에는 롤아웃 속 상대를 hard 로 바꾸면 정확한 상대 손패의 값이 두 배 반으로 커진다는 것도 쟀습니다.

대국에서 모형의 순서가 그대로 나온 것은 반가웠지만, 그 순서를 믿을 만큼 차이가 크지는 않았습니다. 밴딧은 정해진 예산으로 모형의 정답에 더 빨리 다가가게 해 줍니다. 후보가 열 개쯤이면 그 차이가 분명하고, 둘이면 할 일이 없습니다. 그 정답이 맞는지는 밴딧이 알려 주지 않습니다. 베이즈 편의 끝에서 우도를 어디서 재느냐가 맞은편에 누가 앉았느냐의 문제라고 썼는데, 롤아웃을 어디에 쓰느냐도 결국 롤아웃 안에 누구를 앉히느냐로 돌아옵니다.

자료에 대해#

UEC 대회 쪽은 참가자들이 발표한 슬라이드와 오오토가 공개한 소스가 자료입니다. 슬라이드는 숫자 없이 인상만 적은 것이 많고, 소스는 2025년의 개발판이라 2017년 대회판과 세부가 다를 수 있습니다. 대빈민의 여러 몬테카를로 기법을 견준 것으로 보이는 2021년 정보처리학회 발표는 학회 저장소가 점검 중이라 읽지 못했습니다. 실험은 봇 저장소의 사본에서 했고, 운영 코드와 저장소는 건드리지 않았습니다. 대국은 4인 판만 쟀고, seed 128개로는 평균 순위 0.02 안팎의 차이를 가려내지 못합니다. 기준 평균은 표본 512개로 낸 값이라 그 자체에도 잡음이 있지만, 모든 방법에 똑같이 걸리므로 방법끼리의 비교는 흔들지 않습니다.


편제목
Part 1벌 것인가, 고를 것인가
Part 2열여섯 번을 어디에 쓸까 (지금 글)

References#

UEC 컴퓨터 대빈민 대회#

이 블로그의 관련 글#