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

이번 기사에서는 원시 몬테카를로법(Primitive Monte Carlo Method)이 어떤 강화학습 (RL)을 수행하고 있는지에 대해 설명할 예정이었으나, 지금까지 설명한 것과 다른 알고리즘으로 승률을 계산하는 원시 몬테카를로법이 있으며, 그 알고리즘이 더 일반적이라는 것을 깨달았습니다. 그래서 이번 기사에서는 그 알고리즘의 구현과 그 성질의 검증을 진행하기로 하겠습니다.

아래는 이전 기사에서 설명한 원시 몬테카를로법의 알고리즘 재게입니다.

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

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

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

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

또한, 이후의 설명에서는 표기를 짧게 하기 위해 「승률」, 「무승부율」, 「패배율」을 해당 국면에서 여러 번의 플레이아웃을 수행했을 때의 결과를 나타내는 것으로 하겠습니다.

위의 절차 2에서는 「가장 높은 승률」이라고 표기하고 있지만, 〇× 게임처럼 무승부가 존재하는 게임의 경우, 단순히 가장 높은 승률만을 사용하여 최선수를 계산하면 무승부가 고려되지 않는 문제가 발생합니다. 예를 들어, 모든 합법수를 두었을 때의 국면 승률이 0인 경우에는 무승부율의 크기와 상관없이 모든 합법수가 최선수로 계산되어 버립니다. 그래서 이전 기사에서 설명한 것처럼, 원시 몬테카를로법으로 최선수를 계산하는 AI인 ai_pmc에서는 위의 절차 2의 처리를 아래의 알고리즘으로 계산하기로 했습니다.

• 최고 승률이 계산된 국면이 되는 합법수를 최선수로 한다. 단, 최고 승률이 같은 경우에는 무승부율이 가장 높은 합법수를 최선수로 한다
• 최선수가 여러 개 계산된 경우에는 그중에서 랜덤하게 선택한 합법수를 최선수로 한다

이 알고리즘은 최고 승률이 같을 때 무승부율을 사용하여 최선수를 계산해야 하기 때문에, 승률과 무승부율이라는 두 가지 수치를 이용한 2단계 절차로 최선수를 계산한다는 점이 복잡하다는 문제가 있습니다.

다른 알고리즘으로서 무승부를 0.5승으로 고려하는 방법이 있으므로, 그 알고리즘에 대해 설명하겠습니다.

이하의 설명에서는 표기를 간결하게 하기 위해 아래의 기호를 사용하기로 합니다. 또한, 「플레이아웃의 평가치」의 의미에 대해서는 바로 다음에 설명하겠습니다.

$wr + dr × 0.5$

가장 높은 값을 취하는 합법수를 최선수로 계산한다는 점에서, 이 값은 이전 기사에서 설명한 「평가치 (Evaluation value)」라고 생각할 수 있으므로, 본 기사에서는 이 값을 「플레이아웃의 〇의 평가치」라고 부르며 $ps_〇$라고 표기하겠습니다. 따라서, $ps_〇$는 아래의 식으로 계산됩니다.

$ps_〇 = wr + dr × 0.5$

마찬가지로, ×의 차례인 경우 합법수를 두었을 때의 국면 중에서 아래의 식에 의해 계산되는 「무승부를 0.5승으로 계산한 ×의 승률」이 가장 높은 합법수를 최선수로 계산합니다. 본 기사에서는 이 값을 「×의 플레이아웃의 평가치」라고 부르며 $ps_×$라고 표기하겠습니다.

$ps_× = lr + dr × 0.5$

따라서, 최선수는 아래의 알고리즘으로 계산됩니다.

• 〇의 차례에서는 합법수를 두었을 때의 국면 중에서 $ps_〇$가 최대가 되는 합법수를 최선수로 한다
• ×의 차례에서는 합법수를 두었을 때의 국면 중에서 $ps_×$가 최대가 되는 합법수를 최선수로 한다

단, $ps_〇$와 $ps_×$는 아래의 식으로 계산하는 것으로 한다.

$ps_〇 = wr + dr × 0.5$

$ps_× = lr + dr × 0.5$

다음 설명에서는 $ps_〇$와 $ps_×$를 하나로 묶은 것을 「플레이아웃 (Playout)의 평가치」라고 표현하겠습니다.

$ps_〇$와 $ps_×$에는 다음과 같은 성질이 있습니다.

• $0 ≦ ps_〇 ≦ 1$
• $0 ≦ ps_× ≦ 1$
• $ps_〇 + ps_× = 1$

각각에 대해 증명하겠습니다.

$0 ≦ ps_〇 ≦ 1$은 아래의 이유로 항상 성립합니다. $0 ≦ ps_× ≦ 1$도 마찬가지입니다. 이 성질로부터 $ps_〇$와 $ps_×$는 확률의 일종이라고 생각할 수 있습니다.

• $wr$, $dr$, $lr$은 확률이므로 각각 0 이상 1 이하의 값이 되기 때문에 $0 ≦ ps_〇$가 성립한다
• 〇의 승률과 무승부율과 ×의 승률의 합은 1이 되므로 아래의 식이 성립한다

$wr + dr + lr = 1$ - $0 ≦ dr$, $0 ≦ lr$로부터 아래의 식이 성립한다

$ps_〇 = wr + dr × 0.5 ≦ wr + dr + lr = 1$

$ps_〇$와 $ps_×$의 계산식을 $ps_〇 + ps_×$에 대입하면 아래와 같이 1이 됩니다.

$ps_〇 + ps_× = wr + dr × 0.5 + lr + dr × 0.5$

$= wr + dr + lr = 1$

이로부터 $ps_× = 1 - ps_〇$가 성립하므로, $ps_×$는 $ps_〇$가 클수록 작은 값이 됩니다. 따라서 아래와 같이 최선의 수를 $ps_〇$만으로 구할 수도 있습니다.

• 〇의 차례에서는, 합법수를 두었을 때의 국면 중에서 $ps_〇$가 최대가 되는 합법수를 최선의 수로 한다
• ×의 차례에서는, 합법수를 두었을 때의 국면 중에서 $ps_〇$가 최소가 되는 합법수를 최선의 수로 한다

이 알고리즘은 $ps_〇$의 값만을 기준으로 최선의 수를 계산할 수 있으므로, 승률과 무승부율을 별도로 다루는 알고리즘보다 계산 방법이 심플해진다는 장점이 있습니다. 또한, 플레이아웃의 평가치 안에 무승부율이 포함되어 있으므로, 모든 합법수를 두었을 때의 국면의 승률이 0%인 경우라도 무승부율을 고려한 최선의 수를 계산할 수 있습니다.

아래 Wikipedia의 기사에 기재되어 있는 것처럼, 몬테카를로법 (Monte Carlo method)을 이용한 알고리즘에서는 무승부를 0.5승으로 취급하는 것이 일반적인 듯합니다.

계산의 복잡성을 제외하면, 어느 쪽이 더 좋은 알고리즘인지 단언할 수는 없습니다.

예를 들어 아래와 같이 5개의 합법수가 존재하는 〇의 차례인 국면의 경우를 생각해 보겠습니다.

• 수를 두면 그 후에 서로 어떤 수를 두더라도 〇가 100% 승리하는 합법수가 1개 존재한다
• 수를 두면 그 후에 서로 어떤 수를 두더라도 100% 무승부가 되는 합법수가 3개 존재한다
• 수를 두면 그 후에 서로 어떤 수를 두더라도 〇가 100% 패배하는 합법수가 1개 존재한다

위의 경우 각각의 알고리즘으로 계산되는 값은 아래와 같이 크게 다릅니다.

• 승률을 사용하는 알고리즘의 경우 1 ÷ 5 = 0.2가 된다
• 무승부를 고려한 $ps_〇$를 사용하는 알고리즘의 경우 (1 + 3 * 0.5) ÷ 5 = 0.5가 된다

승률을 사용하는 알고리즘은 승리 이외를 무시하기 때문에 「승리만을 중시하는」 합법수가, 무승부를 고려하는 $ps_〇$를 사용하는 알고리즘은 무승부를 승리의 절반으로 계산하기 때문에 「승리와 무승부를 중시」, 즉 「패배를 피하는」 합법수가 선택되기 쉬워집니다.

이처럼 두 알고리즘은 중시하는 바가 다르기 때문에, 어느 알고리즘을 선택할지는 무엇을 중시하느냐에 따라 선택해야 합니다. 예를 들어, 다음 대전은 무승부라도 괜찮은 경우에는 무승부를 고려한 $ps_〇$를 이용한 알고리즘을 선택하는 것이 좋을 것입니다.

미리 상정하는 대전 상대(또는 대전 상대와 거의 동등한 능력을 가진 상대)와 몇 번이고 대전을 할 수 있는 경우에는, 양쪽 알고리즘으로 대전을 진행하여 대전 성적이 더 좋은 쪽을 선택하는 방법도 있습니다.

$ps_〇$나 $ps_×$를 계산할 때, 무승부율인 $dr$에 곱하는 값을 0 ~ 1의 범위로 설정함으로써 무승부를 어느 정도로 고려할지 조정할 수 있습니다. 구체적으로는 $ps_〇$와 $ps_×$를 아래의 식으로 계산합니다.

$ps_〇 = wr + dr × α$ (단, $0 ≦ α ≦ 1$로 한다)

$ps_× = lr + dr × α$ (단, $0 ≦ α ≦ 1$로 한다)

이 식의 $α$는 무승부를 몇 승으로 계산할지를 나타내는 값으로, 예를 들어 $α = 0.2$로 했을 경우의 $ps_〇$는 아래와 같이 무승부를 0.2승으로 계산합니다.

$ps_〇 = wr + dr × 0.2$

또한, $α = 0$인 경우에는 승률이, $α = 1$인 경우에는 패배하지 않을 확률이 계산됩니다.

참고로 $α ≠ 0.5$인 경우에는 아래와 같이 $ps_〇 + ps_×$가 항상 1이 되지 않을 수 있다는 점에 주의가 필요합니다.

$ps_〇 + ps_× = wr + dr × α + lr + dr × α$

$= wr + 2α × dr + lr$

$= wr + dr + lr + (2α - 1) × dr$

$= 1 + (2α - 1) × dr$

알고리즘의 차이가 합법수(legal move)의 선택이나 특정 AI와의 대전 결과에 어떤 영향을 미치는지 검증하기 위해, 이번 기사에서는 무승부를 0.5승으로 하여 $ps_〇$와 $ps_×$를 계산하는 원시 몬테카를로법(Primitive Monte Carlo) AI인 ai_pmc2를 구현하고, ai_pmc와의 차이를 검증하도록 하겠습니다.

ai_pmc2를 구현하기 전에, 나중에 시각적인 검증을 수행할 수 있도록 각 국면에서 무한히 플레이아웃(playout)을 수행했을 경우의 $ps_〇$ 기대값 1을 Mbtree 클래스에서 계산하여 파일로 저장하고, 게임 트리의 시각화를 수행하는 Marubatsu_GUI 클래스에서 표시할 수 있도록 하겠습니다. 또한, $ps_×$는 앞서 설명한 것처럼 $1 - ps_〇$라는 식으로 계산할 수 있으므로, 파일에는 $ps_〇$의 기대값만을 저장하기로 합니다.

각 국면에서 무한히 플레이아웃을 수행했을 경우의 〇 승률($wr$), 무승부율($dr$), × 승률($lr$)의 기대값 계산은 이전 기사에서 구현한 Mbtree 클래스의 calc_playout_prob_by_df 메서드로 수행하며, 국면을 나타내는 Node 클래스 인스턴스의 playout_prob라는 속성에 대입했습니다.

마찬가지로, $ps_〇$의 기대값 계산과 Node 클래스의 속성 대입 처리도 이 메서드에서 수행하도록 하겠습니다. 이때 $ps_〇$의 기대값은 playout_score라는 속성에 대입합니다.

아래는 그와 같이 calc_playout_prob_by_df 메서드를 수정한 프로그램입니다.

12, 13행: 게임의 승부가 결정된 국면인 경우, playout_score 속성에 〇가 승리한 경우 1을, 무승부인 경우 0.5를 대입한다. 참고로 비교 연산자의 계산 결과인 true와 false에 대해 연산을 수행하면, true는 1, false는 0으로 계산되므로 if 문을 사용하지 않은 12, 13행의 식으로 그러한 계산을 수행할 수 있다.
20, 21행: 게임의 승부가 결정되지 않은 국면인 경우에는 playout_prob 속성에 대입된 〇 승률($wr$)의 기대값에 무승부율($dr$)의 기대값 절반을 가산한 값을 $ps_〇$의 기대값으로 계산하여 playout_score 속성에 대입한다.

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):
...

수정 부분

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

위의 수정 후에 아래 프로그램으로 Mbtree 클래스의 인스턴스를 생성하고, 게임 시작 시의 국면을 나타내는 루트 노드의 playout_score 속성을 표시하면, 실행 결과의 마지막 줄과 같이 $ps_〇$의 기대값으로서 약 0.648이 계산되어 있음을 확인할 수 있습니다.

mbtree = Mbtree()
print(mbtree.root.playout_score)

실행 결과

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

계산한 $ps_〇$의 기댓값을 Mbtree_GUI 클래스에서 표시하기 위해서는 계산한 데이터를 파일에 저장해야 하므로, 해당 처리를 수행하는 calc_and_save_bestmoves_and_score_by_board 메서드를 아래 프로그램과 같이 수정합니다.

17행: 파일에 저장할 데이터 중 각 국면을 나타내는 dict의 playout_score 키 값에 $ps_〇$의 기댓값을 대입한다.

1 from tqdm import tqdm
2 import gzip, pickle
3
...

행 번호가 없는 프로그램

from tqdm import tqdm
import gzip, pickle
def calc_and_save_bestmoves_and_score_by_board(self, path):
...

수정 부분

from tqdm import tqdm
import gzip, pickle
def calc_and_save_bestmoves_and_score_by_board(self, path):
...

위의 정의 후에, 아래 프로그램으로 Mbtree_GUI 클래스에서 이용할 3개의 파일을 $ps_〇$의 기댓값이 기록된 데이터로 업데이트합니다. 또한, 실행 결과는 특별히 중요한 정보가 표시되지 않으므로 생략합니다.

mbtree = Mbtree()
mbtree.calc_and_save_bestmoves_and_score_by_board("../data/bestmoves_and_score_by_board.dat")
mbtree2 = Mbtree(shortest_victory=True)
...

다음으로 $ps_〇$와 $ps_×$의 기댓값을 Mbtree_GUI 클래스에서 표시할 수 있도록 합니다. 구체적으로는 Dropdown에 $ps_〇$와 $ps_×$의 기댓값을 표시하는 항목을 추가하고, 해당 항목을 선택했을 때 국면 상단에 대응하는 기댓값을 표시하도록 수정합니다. 수정 방법은 이전 기사에서 수행했던 것과 유사하므로 그쪽도 참조해 주세요.

먼저 Dropdown을 생성하는 Mbtree_GUI 클래스의 create_widets 메서드를 아래 프로그램과 같이 수정합니다. 항목 이름은 "플레이아웃의 〇 평가치", "플레이아웃의 × 평가치"로 하고, 해당 항목들을 선택했을 때의 Dropdown value 속성 값을 "playout_score_o"와 "playout_score_x"로 설정했습니다.

13, 14행: Dropdown에 위에서 설명한 항목을 추가했다.

1 from tree import Mbtree_GUI
2 import matplotlib.pyplot as plt
3 import ipywidgets as widgets
...

행 번호가 없는 프로그램

from tree import Mbtree_GUI
import matplotlib.pyplot as plt
import ipywidgets as widgets
...

수정 부분

from tree import Mbtree_GUI
import matplotlib.pyplot as plt
import ipywidgets as widgets
...

$ps_〇$와 $ps_×$의 기댓값을 국면 상단에 표시하기 위해 Node 클래스의 __init__ 메서드와 draw_node 메서드를 아래 프로그램과 같이 수정합니다.

10행: __init__ 메서드 내에서 $ps_〇$의 기댓값이 대입된 데이터를 playout_score 속성에 대입한다.
19 ~ 23행: draw_node 메서드 내에서 Dropdown의 선택 항목을 나타내는 가매개변수(仮引数) show_score의 값에 따라 국면 상단에 $ps_〇$ 또는 $ps_×$의 기댓값을 표시하는 처리를 추가한다.

행 번호가 없는 프로그램

from tree import Node, Rect
from marubatsu import Marubatsu_GUI
def __init__(self, mb, parent=None, depth=0, bestmoves_and_score_by_board=None):
...

수정 사항

from tree import Node, Rect
from marubatsu import Marubatsu_GUI
def __init__(self, mb, parent=None, depth=0, bestmoves_and_score_by_board=None):
...

위의 수정 후에 아래 프로그램을 실행하여, Dropdown에서 「플레이아웃의 〇 평가치」를 선택하면 실행 결과와 같이 국면 상단에 $ps_〇$의 기댓값이 표시됩니다. 이미지는 생략하지만 「플레이아웃의 × 평가치」를 선택했을 때 $ps_× = 1 - ps_〇$가 되는 $ps_×$의 기댓값이 표시되는 것을 확인해 주십시오.

Mbtree_GUI()

실행 결과

또한, Dropdown에서 「플레이아웃에서의 〇 승률」을 선택했을 때의 아래 그림과 비교하여, 무승부를 0.5승으로 고려한 만큼 국면 상단에 표시되는 수치가 커져 있는 것을 확인할 수 있습니다.

다음으로 $ps_〇$와 $ps_×$를 사용하여 원시 몬테카를로법 (Primitive Monte Carlo method)으로 최선수를 계산하는 ai_pmc2를 아래 프로그램과 같이 정의합니다. 아래의 설명과 수정 사항에는 ai_pmc와의 차이점을 나타냅니다. 또한, 아래의 설명에서는 〇의 차례인 경우를 기준으로 설명하고 있으나, ×의 차례인 경우 $ps_〇$가 $ps_×$가 된다는 점 외에는 동일하므로 그 설명은 생략합니다.

7행: best_ratio를 삭제하고, $ps_〇$의 최댓값을 기록하는 best_score를 -1로 초기화한다. $ps_〇$의 값의 범위는 0 ~ 1이므로 초기화하는 값은 0 미만의 값이라면 무엇이든 좋다.
9행: ratio_by_move를 삭제하고, 대신 각각의 합법수에 대한 $ps_〇$의 값을 기록하는 score_by_move를 빈 dict로 초기화한다.
12행: winratio와 drawratio를 삭제하고, 〇의 차례인 경우에는 $ps_〇 = wr + dr imes 0.5$를, ×의 차례인 경우에는 $ps_× = lr + dr imes 0.5$를 계산하여 score에 대입한다.
16, 17, 23, 24행: ratio와 best_ratio의 디버그 표시를 score와 best_score의 표시로 수정했다.
18 ~ 24행: score가 bestscore보다 큰 경우에 최선수를 갱신하는 처리로 수정했다.
25 ~ 29행: score와 bestscore가 같은 경우에 최선수를 추가하는 처리로 수정했다.
31행: score_by_move의 move 키 값에 $ps_〇$를 나타내는 score를 기록하도록 수정했다. ratio_by_move의 경우와 달리 movexy가 아니라 move 키 값에 대입해야 한다는 점에 주의할 것. 또한, 그때 이전 기사의 ai_pmc와 마찬가지로 gui_play에서 평가치를 표시하는 경우를 고려하여 소수점 넷째 자리에서 반올림한 값을 대입했다.
34행의 다음 줄에 있던 ratio_by_move를 반환값의 일부로 반환하는 처리를 삭제했다.

1 from ai import dprint
2 from random import choice
3
...

행 번호가 없는 프로그램

행 번호가 없는 프로그램

from ai import dprint
from random import choice
def ai_pmc2(mb, pnum, timelimit=None, debug=False, analyze=False, *args, **kwargs):
...

수정 사항

from ai import dprint
from random import choice
def ai_pmc2(mb, pnum, timelimit=None, debug=False, analyze=False, *args, **kwargs):
...

위의 ai_pmc2 정의 후에 아래의 프로그램으로, 게임 시작 시의 국면에 대해 키워드 인자(keyword argument)로서 pnum=10000, debug=True, analyze=True를 기술하여 ai_pmc2로 최선의 수를 계산하면, 실행 결과와 같이 각 합법수의 무승부율을 고려한 $ps_〇$가 계산되어, 최댓값이 계산된 (1, 1)이 최선의 수로 계산된 것을 확인할 수 있습니다.

mb = Marubatsu()
ai_pmc2(mb, pnum=10000, debug=True, analyze=True)

실행 결과

==================================================
move (0, 0)
score : 0.665
...

아래는 실행 결과의 $ps_〇$와 앞서 Marubatsu_GUI()에서 표시한 $ps_〇$의 기대치를 정리한 표로, 10,000회의 플레이아웃 (playout)을 통해 이론값에 가까운 $ps_〇$가 계산된 것을 확인할 수 있습니다.

ai_pmc2의 실력을 측정하기 위해, 이전 기사에서 ai_pmc에 대해 수행했던 것과 마찬가지로, 아래의 조건에서 랜덤하게 착수하는 ai2s와 약해결 (weak solution) AI인 ai14s와의 대전을 진행합니다.

• 처리에 시간이 걸리므로 대전 횟수는 1,000회로 한다
• 플레이아웃 (playout) 횟수를 5, 10, 50, 100, 1000, 10000회로 하여 대전을 진행한다
• 플레이아웃 (playout) 횟수를 1억 회, 제한 시간을 0.0001, 0.0005, 0.001, 0.01, 0.1초로 하여 대전을 진행한다

아래는 해당 대전을 수행하는 프로그램과 실행 결과입니다.

from ai import ai_match, ai2s, ai14s
for pnum in [5, 10, 50, 100, 1000, 10000]:
print(f"pnum {pnum}")
...

실행 결과

pnum 5
ai_pmc2 VS ai2s
100%|██████████| 1000/1000 [00:00<00:00, 1673.41it/s]
...

아래는 위의 ai2s와의 대전 실행 결과와, 이전 기사의 ai_pmc VS ai2s 대전 결과를 정리한 표입니다. 왼쪽부터 ai2s에 대한 승률, 패율, 무승부율의 %를 나타내며, 상단이 ai_pmc VS ai2s, 하단이 ai_pmc2 VS ai2s의 대전 결과입니다.