본 기사의 프로그램은 Python 버전 3.13에서 실행하고 있습니다. 또한, numpy 버전은 2.3.5입니다.

이전 기사에서 대수의 법칙 (Law of Large Numbers)에 대한 설명이 끝났으므로, 이번 기사부터 이전 기사에서 설명한 원시 몬테카를로 법 (Primitive Monte Carlo Method)에 의한 〇× 게임 AI 구현을 시작합니다.

• 현재 국면에서 합법수 (Legal Move)를 두는 모든 국면에 대해 아래의 계산을 수행한다

• 게임이 결판이 날 때까지 난수를 이용하여 랜덤한 착수를 계속하며, 그 결과를 기록한다. 이 작업을 플레이아웃 (Playout)이라고 부른다

• 미리 정해둔 횟수 또는 미리 정해둔 시간이 될 때까지 플레이아웃을 반복하여, 그 승률을 계산한다

• 가장 높은 승률이 계산된 국면이 되는 합법수를 최선수 (Best Move)로 한다

위의 알고리즘으로 수행하는 플레이아웃에서는 랜덤한 착수를 계속하기 때문에, 그 결과인 「〇의 승리」, 「×의 승리」, 「무승부」가 발생하는 확률은 특정 확률 분포로 나타낼 수 있다고 간주할 수 있습니다. 또한, 플레이아웃은 몇 번이든 동일한 조건으로 수행할 수 있으며, 각각의 플레이아웃 결과는 독립적입니다. 따라서 여러 번의 플레이아웃 결과는 특정 모집단으로부터의 무작위 복원 추출로 간주할 수 있으므로 대수의 법칙을 적용할 수 있으며, 위의 알고리즘에 의해 「〇의 승률」, 「×의 승률」, 「무승부율」의 근사치를 계산할 수 있습니다. 또한, 대수의 법칙에 따라 플레이아웃 횟수가 많아질수록 이러한 근사치의 정밀도가 높아집니다.

이번 기사에서는 플레이아웃을 수행하는 프로그램을 구현하고, 실제로 플레이아웃 횟수가 많아질수록 대수의 법칙에 의해 근사치의 정밀도가 높아진다는 것을 보여줍니다.

참고로, 원시 몬테카를로 법에 의한 AI 구현과 그 강도 검증 및 알고리즘 개선 방법에 대해서는 향후 기사에서 설명할 예정입니다.

먼저 〇× 게임의 임의의 국면에 대해 플레이아웃을 수행했을(결판이 날 때까지 랜덤한 착수를 계속했을) 경우의 「〇의 승리」, 「×의 승리」, 「무승부」 각각의 발생 확률 계산 방법에 대해 설명하고, 실제로 그 계산을 수행하도록 하겠습니다.

〇× 게임의 국면 (state)을 $S$라고 표기하면, $S$에 대해 플레이아웃을 수행했을 경우의 결과는 「〇의 승리」, 「×의 승리」, 「무승부」 중 하나가 되며, 각각의 발생 확률의 합계는 1이 됩니다. 또한, $S$는 결판이 난 국면도 포함하며, 그 경우에는 당연하게도 랜덤한 착수는 이루어지지 않고 해당 국면의 결과 확률이 1, 그 외의 확률은 0이 됩니다.

국면 $S$에 대한 플레이아웃 결과를 나타내는 확률 변수 $X_S$라고 표기하면, 각각의 결과가 발생하는 확률은 확률 질량 함수 (Probability Mass Function) $P$를 사용하여 아래 표와 같이 표기할 수 있습니다. 단, 표기를 간결하게 하기 위해 확률 변수 $X_S$의 값은 「〇의 승리」인 경우 「〇」, 「×의 승리」인 경우 「×」, 「무승부」인 경우 「△」로 하였습니다.

| 의미 |
|---|---|
| $P(X_S=〇)$ | 〇의 승률 |
| ... |
이번 기사에서는 이 값들을 계산하여, 플레이아웃 횟수를 늘리면 각각의 비율이 이러한 이론값에 가까워진다는 것을 보여줍니다.

$P(X_S=〇)$, $P(X_S=×)$, $P(X_S=△)$의 구체적인 계산 방법에 대해 설명합니다.

국면 $S$가 결판이 난 국면인 경우는 아래 표와 같습니다.

$P(X_S=〇) = \sum_{i=1}^{n}\frac{1}{n}P(X_{S_i}=〇)= \frac{1}{n}\sum_{i=1}^{n}P(X_{S_i}=〇)$

동일한 이유로 $P(X_S=×)$와 $P(X_S=△)$도 아래의 식으로 계산할 수 있습니다.

$P(X_S=×) = \frac{1}{n}\sum_{i=1}^{n}P(X_{S_i}=×)$

$P(X_S=△) = \frac{1}{n}\sum_{i=1}^{n}P(X_{S_i}=△)$

게임의 승패가 결정된 국면은 이전 기사에서 설명한 〇× 게임의 게임 트리 (game tree) 리프 노드 (leaf node)에 해당하며, $X_{S_i}$의 국면은 $X_{S}$ 국면의 자식 노드 (child node)에 해당합니다. 따라서 위의 식은 아래의 계산을 수행함을 나타냅니다.

• 리프 노드의 확률을 계산한다
• 자식 노드의 확률로부터 부모 노드의 확률을 계산한다

이 성질은 이전 기사에서 설명한, 게임 트리 각 노드의 평가값을 계산하는 미니맥스법 (minimax method)과 동일하기 때문에, 미니맥스법과 유사한 알고리즘으로 계산을 수행할 수 있습니다.

이전 기사에서는 너비 우선 탐색 (BFS) 알고리즘과 깊이 우선 탐색 (DFS) 알고리즘 두 종류의 알고리즘으로 미니맥스법을 구현하는 방법을 소개했지만, 어떤 방법으로 구현해도 결과는 같으므로 이번 기사에서는 더 간단하게 구현할 수 있는 깊이 우선 (depth first) 알고리즘으로 구현하기로 하겠습니다. 관심이 있는 분은 너비 우선 알고리즘으로 구현해 보시기 바랍니다.

미니맥스법을 깊이 우선 알고리즘으로 수행하는 처리는 게임 트리를 나타내는 Mbtree 클래스의 calc_score_by_df 메서드로 구현했습니다. 마찬가지로 깊이 우선 알고리즘으로 플레이아웃 (playout)을 수행했을 경우 각 노드의 각각의 결과 확률 (probability) 계산을 Mbtree 클래스의 calc_playout_prob_by_df 메서드로 정의하겠습니다.

플레이아웃을 수행했을 경우의 각각의 비율은 게임의 상태를 나타내는 Marubatsu 클래스의 status 속성 값을 키 (key)로 한 아래 표의 딕셔너리 (dict)로 표현하며, 게임 트리 노드를 나타내는 Node 클래스 인스턴스의 playout_prob 속성에 대입하기로 합니다. 또한, mb는 노드의 국면을 나타내는 Marubatsu 클래스의 인스턴스입니다.

아래는 Mbtree 클래스의 calc_playout_prob_by_df 메서드의 정의입니다.

• 4행: calc_playout_prob_by_df 메서드를 계산 대상이 되는 국면을 나타내는 게임 트리 노드를 대입하는 매개변수 node를 가진 메서드로 정의한다.
• 5~9행: 국면으로부터 랜덤한 착수를 계속했을 경우의 〇의 승률, ×의 승률, 무승부 확률을 나타내는 playout_prob 속성을 각각의 확률을 0으로 한 딕셔너리로 초기화한다.
• 10, 11행: node의 국면이 결판이 난 경우 playout_prob 속성에 대입된 딕셔너리의 해당 키 값을 1로 설정하여 그 확률을 100%로 설정한다.
• 12~17행: 결판이 나지 않은 경우의 처리를 수행한다.
• 13행: 자식 노드 (합법수)의 수를 계산하여 childnum에 대입한다.
• 14행: 각각의 자식 노드 (합법수를 착수한 국면)에 대해 반복 처리를 수행한다.
• 15행: 자식 노드에 대해 calc_playout_prob_by_df를 재귀 호출함으로써, 깊이 우선 알고리즘으로 자식 노드의 각각의 확률을 계산한다.
• 16, 17행: 15행의 재귀 호출에 의해 자식 노드의 각각의 확률이 playout_prob 속성에 계산되므로, 각각의 확률을 childnum으로 나눈 값을 playout_prob 속성의 해당 확률에 가산함으로써 평균값을 계산한다.

1 from tree import Mbtree
2 from marubatsu import Marubatsu
3
...

행 번호가 없는 프로그램

from tree import Mbtree
from marubatsu import Marubatsu
def calc_playout_prob_by_df(self, node):
...

다음으로, Mbtree 클래스의 __init__

다음으로, Mbtree 클래스의 __init__

메서드의 16행에 아래 프로그램과 같이 calc_playout_prob_by_df의 실인수(actual argument)에 게임 트리의 루트 노드(root node)를 기술하여 호출함으로써, 모든 국면에 대한 플레이아웃 (Playout) 결과의 확률을 계산하는 처리를 추가합니다.

1 from tree import Node
2
3 def __init__(self, algo="bf", shortest_victory=False,
...

행 번호가 없는 프로그램

from tree import Node
def __init__(self, algo="bf", shortest_victory=False,
recalculate_draw_score=False, subtree=None):
...

수정 사항

from tree import Node
def __init__(self, algo="bf", shortest_victory=False,
recalculate_draw_score=False, subtree=None):
...

5 ~ 16행의 조건 분기에서는 algo 속성값에 따라 너비 우선 (breadth first)과 깊이 우선 (depth first) 중 어떤 알고리즘으로 계산을 수행할지 변경하고 있습니다. 하지만 이번 기사에서는 너비 우선 (breadth first) 알고리즘으로 처리하는 calc_playout_prob_by_bf 메서드를 구현하지 않았으므로, 해당 조건 분기 이후에 반드시 깊이 우선 알고리즘에 의한 calc_playout_prob_by_df를 실행하도록 했습니다.

어떤 알고리즘으로 계산하더라도 결과는 변하지 않으므로 이대로도 문제는 없지만, 여유가 있는 분들은 너비 우선 알고리즘으로 계산을 수행하는 calc_playout_prob_by_bf 메서드를 구현하여 algo 속성값에 따라 호출하는 메서드를 변경하는 프로그램을 구현해 보시기 바랍니다.

위의 수정 후에 아래 프로그램을 실행하여 새로운 Mbtree 클래스의 인스턴스를 생성하고, 게임 시작 시의 국면과 그 국면에 합법수 (legal move)를 둔 국면에 대한 플레이아웃 결과의 각각의 확률을 표시합니다.

1행: 새로운 Mbtree 클래스의 인스턴스를 생성한다 -
2행: 게임 시작 시의 국면을 나타내는 mbtree.root를 요소로 하는 리스트 (list)와, 그 자식 노드(child node)의 목록을 나타내는 리스트를 + 연산자로 결합한 리스트에 대해 반복 처리를 수행함으로써, 게임 시작 시의 노드와 그 자식 노드에 대해 반복 처리를 수행한다 -
3 ~ 7행: node의 국면과 플레이아웃 결과의 각각의 확률을 표시한다

1 mbtree = Mbtree()
2 for node in [mbtree.root] + mbtree.root.children:
3 print(node.mb)
...

행 번호가 없는 프로그램

mbtree = Mbtree()
for node in [mbtree.root] + mbtree.root.children:
print(node.mb)
...

실행 결과

9 depth 1 node created
72 depth 2 node created
504 depth 3 node created
...

아래는 위의 실행 결과를 정리한 표입니다. 각각의 확률을 % 표기로 바꾸고, 소수점 둘째 자리에서 반올림했습니다.

위의 표를 통해 다음을 알 수 있습니다.

• 변(side)과 모서리(corner)에 착수했을 경우의 각각의 확률은 동일하다
• 중앙 > 모서리 > 변 순으로 〇의 승률이 높아진다
• 어떤 국면에서도 〇의 승률이 50%를 넘는다

위의 첫 번째 내용인, 모서리에 착수했을 경우와 변에 착수했을 경우의 국면은 동일한 국면이므로 확률이 같아지는 것은 당연하다고 할 수 있습니다.

두 번째 결과는 이전 기사에서 고찰한 바와 같이, 〇의 승리로 이어지는 「자1적0공2(자신1 적0 공백2)」가 되는 직선이 많은 순서대로 〇가 유리해지기 때문에 승률이 높아짐을 나타냅니다. 따라서, 원시 몬테카를로 (Monte Carlo) 방법의 AI는 게임 시작 시의 국면에서 중앙의 합법수(legal move)를 선택합니다.

세 번째 내용을 통해 이 게임은 무작위로 착수를 계속하는 경우에는 〇가 유리한 게임임을 알 수 있습니다.

단, 위의 두 번째와 세 번째는 무작위로 착수를 계속했을 경우의 성질입니다. 〇× 게임은 무승부(draw)가 발생하는 게임이므로, 서로가 최선의 수(best move)를 계속 착수한다면 게임 시작 시점에 어떤 착수를 하더라도 무승부가 됩니다.

Mbtree 인스턴스의 계산은 시간이 걸리기 때문에, 계산한 게임 트리(game tree) 데이터를 아래의 프로그램에서 Mbtree의 save 메서드를 이용하여 playout.mbtree라는 이름의 데이터를 저장하는 폴더에 해당 파일을 저장하기로 합니다.

mbtree.save(".../data/playout")

아래는 위에서 저장한 파일을 load 메서드로 불러와 mbtree2라는 변수에 대입하고, 게임 시작 시의 국면을 나타내는 루트 노드(root node)의 playout_prob 속성을 표시하는 프로그램입니다. 실행 결과로부터 방금 전 표의 게임 시작 시 국면의 확률이 표시되는 것을 확인할 수 있습니다.

mbtree2 = Mbtree.load(".../data/playout")
print(mbtree2.root.playout_prob)

실행 결과

{0: 0.5849206349206348, 1: 0.2880952380952381, 'draw': 0.126984126984127}

다음으로, 임의의 국면에 대하여 플레이아웃 (Playout)을 「지정한 횟수」 또는 「지정한 시간이 경과할 때까지」 수행하고, 각각의 합법수를 착수했을 때의 국면에 대한 「〇의 승리」, 「×의 승리」, 「무승부」의 횟수를 계산하는 playout 함수를 구현합니다. 대수의 법칙 (Law of Large Numbers)을 따르는지 확인하기 위해서는 실제로 몇 번의 플레이아웃이 실행되었는지에 대한 정보가 필요하므로, playout은 비율이 아닌 횟수를 계산하여 반환하도록 했습니다.

처음에 설명한 원시 몬테카를로 방법의 알고리즘에서는, 현재 국면의 각각의 합법수를 착수했을 때의 국면에 대하여 「특정 횟수」 또는 「특정 시간이 경과할 때까지」 플레이아웃을 수행한다고 설명했지만, 국면에 따라 게임이 결판이 나기까지의 평균 수(move)가 다르기 때문에, 1회 플레이아웃 처리 시간의 평균은 국면에 따라 다릅니다. 따라서 합법수를 착수했을 때의 각각의 국면에 대해 동일한 제한 시간을 둔 플레이아웃을 수행하면, 국면마다 플레이아웃 횟수가 달라지기 때문에 플레이아웃 집계 결과의 정밀도가 국면마다 달라지는 문제가 발생합니다.

그래서 playout 구현에서는 합법수를 착수했을 때의 국면이 아니라, 현재 국면으로부터 「특정 횟수」 또는 「특정 시간이 경과할 때까지」 플레이아웃을 수행하고, 처음 착수를 수행한 합법수별로 플레이아웃 결과의 집계를 수행하기로 합니다. 이 방법에서는 각각의 합법수가 선택되는 횟수는 동일하지 않지만, 대수의 법칙에 따라 플레이아웃 횟수가 늘어날수록 각각의 합법수가 선택되는 비율이 균등에 가까워지기 때문에 위의 문제를 잘 해결할 수 있습니다.

아래는 playout의 매개변수(argument) 목록입니다.

playout의 반환값은 아래와 같은 dict를 중첩(nested)한 데이터 구조로 합니다.

아래는 playout을 정의하는 프로그램입니다. 또한, 시간 측정은 이전 기사에서 설명한 perf_counter라는 time 모듈에서 정의된 함수를 이용하고 있습니다. 잊어버린 분은 복습해 주세요.

5행: 위의 표의 가변 인수를 갖도록 playout을 정의한다 -
6~8행: timelimit이 None이 아닌 경우에는 perf_counter()로 현재 시간을 측정하고, 거기에 timelimit을 가산함으로써 제한 시간에서의 perf_counter() 값을 계산하여 timelimit_pc에 대입한다 -
9~15행: 플레이아웃의 집계 결과를 기록하는 result에 빈 dict를 대입하고, 각각의 합법수(legal move)를 키로 하여, 그 키의 값에 〇의 승리, ×의 승리, 무승부 횟수가 각각 0임을 나타내는 dict를 대입한다 -
16행: 플레이아웃을 수행한 횟수를 기록하는 변수를 0으로 초기화한다 -
17행: 반복 처리를 통해 pnum 회의 플레이아웃을 수행한다 -
18, 19행: timelimit이 None이 아닌 경우에는 perf_counter()로 시간을 측정하고, timelimit_pc를 초과했다면 제한 시간을 초과한 것이므로 break로 반복 처리를 중단한다 -
20행: 플레이아웃은 매번 mborig의 국면에서 수행해야 하므로, deepcopy로 mborig의 깊은 복사(deep copy)를 수행한 mb에 대해 플레이아웃 처리를 수행하도록 한다 -
21행: 첫 번째 착수를 기록하는 변수를 None으로 초기화한다 -
22~26행: 반복 처리를 통해 승부가 날 때까지 랜덤한 착수를 수행한다 -
23행: random.choice를 이용하여 합법수 중에서 랜덤한 합법수를 선택한다 -
24, 25행: firstmove가 None인 경우에 합법수를 firstmove에 대입함으로써 처음 수행한 착수를 기록한다 -
26행: 랜덤하게 선택한 합법수를 착수한다 -
27, 28행: result의 firstmove 키에 대입된 dict의 mb.status 키 값을 1 증가시켜 집계를 수행하고, 플레이아웃을 수행한 횟수를 나타내는 count에 1을 가산한다 -
29~32행: 방금 설명한 데이터 구조의 반환값을 반환한다

1 from time import perf_counter
2 from copy import deepcopy
3 import random
...

행 번호가 없는 프로그램

from time import perf_counter
from copy import deepcopy
import random
...

아래는 게임 시작 시의 국면에 대해 제한 시간을 두지 않고 플레이아웃을 10000회 수행하여 그 결과를 표시하는 프로그램입니다.

1, 2행: 게임 시작 시의 국면을 나타내는 데이터를 mb에 대입하여 게임판을 표시한다 -
3행: 제한 시간을 두지 않고 playout으로 10000회의 플레이아웃을 수행하여 결과를 retval에 대입한다 -
4행: 플레이아웃이 실제로 수행된 횟수를 표시한다 -
5행: retval['result']의 각 키(첫 번째 착수)와 키의 값(해당 착수에 대한 각 결과의 횟수)에 대해 반복 처리를 수행한다 -
6~8행: 직전의 착수에 대한 표시와 구별하기 쉽도록 빈 줄과 가로줄을 표시한다 -
9행: move

move에는 플레이아웃(Playout)에서 처음으로 착수한 합법수를 나타내는 데이터가 대입되어 있지만, 그 데이터 구조가 (x, y)와 같은 tuple 형태라고 단정할 수 없으므로 mb.board.move_to_xy를 사용하여 (x, y) 좌표로 변환하여 표시한다 -
10 ~ 12행: move 착수를 수행하여 해당 국면을 표시하고, 다음 반복 처리에서 mb를 원래 국면으로 되돌릴 필요가 있으므로 unmove를 호출한다 -
13행: 각각의 결과 비율을 계산하기 위해 counts의 키(key) 값의 합계를 계산한다 -
14행: counts의 각 키(결과)와 키의 값(개수)에 대해 반복 처리를 수행한다 -
15행: 결과, 개수, 그리고 그 비율을 계산하여 표시한다. 또한, 결과를 나타내는 데이터는 게임판을 나타내는 클래스에 따라 다르므로, 이전 기사에서 도입한 게임판 클래스의 board.MARK_TABLE 속성을 이용하여 승패 결과를 나타내는 문자열로 변환해야 한다

1 mb = Marubatsu()
2 print(mb)
3 retval = playout(mb, 10000)
...

행 번호가 없는 프로그램

mb = Marubatsu()
print(mb)
retval = playout(mb, 10000)
...

실행 결과

Turn o
...
...
...

실행 결과로부터 제한 시간을 설정하지 않았기 때문에 10,000회의 플레이아웃이 수행되었음을 확인할 수 있습니다. 집계 결과에 대해서는 나중에 정리하겠습니다.

다음으로 제한 시간을 설정했을 경우의 처리를 확인합니다. 위의 10,000회 플레이아웃은 필자의 컴퓨터에서 약 0.4초 만에 실행되었습니다. 따라서 아래 프로그램과 같이 제한 시간을 1초, 플레이아웃 횟수를 100만 회로 설정하고 플레이아웃이 실제로 수행된 횟수만큼만 표시하면, 실행 결과와 같이 1초 후에 반복 처리 도중에 중단되어 약 25,000회의 플레이아웃이 실행되었음을 확인할 수 있습니다.

retval = playout(mb, 1000000, timelimit=1)
print(f"playout count = {retval['count']}")

실행 결과

playout count = 25758

위의 결과가 대수의 법칙 (Law of Large Numbers)을 따르고 있는지 확인할 수 있도록, 방금 계산한 각 국면의 이론적 확률과의 차이(difference) 및 해당 국면에서의 차이의 평균을 계산하여 비교할 수 있도록 합니다. 또한, 그때 프로그램을 재사용할 수 있도록 analyze_playout이라는 함수를 아래 프로그램과 같이 정의하기로 했습니다.

1행: 분석할 playout의 반환값을 대입하는 가매개변수(formal parameter) retval과, 각 국면에서 플레이아웃을 수행했을 경우의 각각의 확률이 대입된 Mbtree 클래스의 인스턴스를 대입하는 가매개변수 mbtree를 가진 함수로서 analyze_playout을 정의한다 -
3, 4행: 각 국면의 차이 합계와 차이의 개수를 계산할 변수를 0으로 초기화한다 -
9행: mb의 국면에 대응하는 게임 트리(Game Tree)의 노드는 mbtree의 nodelist_by_mb 속성에 대입된 dict의 tuple(mb.records) 키 값에 대입되어 있으므로, 그것을 node에 대입한다. 잊어버린 분은 이전 기사를 복습할 것 -
12행: 결과 목록의 헤더를 표시한다. prob는 mbtree에 기록된 이론적 확률을, diff는 플레이아웃으로 계산된 비율과 이론적 확률의 차이(difference)를 나타낸다 -
14 ~ 17행: 20행의 기술을 짧게 만들기 위해, 20행에서 표시할 내용을 계산하여 변수에 대입한다 -
16행: node.playout_prob로부터 대응하는 이론적 확률(단위는 %)을 계산한다 -
17행: 플레이아웃으로 계산된 비율과 이론적 확률의 차이(절대값)를 계산한다 -
18, 19행: 차이의 합계와 차이를 계산한 횟수를 계산한다 -
20행: 결과를 나열하여 표시한다. 또한, 플레이아웃 횟수를 늘렸을 때 정밀도가 높아지는 것을 고려하여 소수점 아래 둘째 자리까지 표시하도록 수정하였다 -
24행: 차이의 평균을 계산하여 표시한다

1 def analyze_playout(mb, retval, mbtree):
2 print(f"playout count = {retval['count']}")
3 diffsum = 0
...

행 번호가 없는 프로그램

def analyze_playout(mb, retval, mbtree):
print(f"playout count = {retval['count']}")
diffsum = 0
...

아래는 플레이아웃 (Playout) 횟수를 100, 1000, 1만, 10만, 100만 회로 설정했을 때의 결과를 analyze_playout으로 표시하는 프로그램입니다. 실행 결과가 길기 때문에 접어두었습니다.

for pnum in [100, 1000, 10000, 100000, 1000000]:
retval = playout(mb, pnum=pnum)
analyze_playout(mb, retval, mbtree)

실행 결과

playout count = 100
move (0, 0)
Turn x
...

아래는 위의 실행 결과에서 차분(Difference)만을 추출한 표이며, 각 열은 플레이아웃 (Playout)에서 처음으로 착수한 합법수 (Legal move)의 좌표를 나타냅니다. 또한, 표의 셀 수치는 위에서부터 순서대로 「〇의 승리」, 「×의 승리」, 「무승부」를 나타내며 단위는 %입니다.