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

링크	설명
marubatsu.py	Marubatsu, Marubatsu_GUI 클래스 정의
...
AI 목록과 지금까지 작성한 데이터 파일에 대해서는 아래 기사를 참조해 주세요.

지난 기사에서는 원시 몬테카를로법 (Primitive Monte Carlo Method)에 의한 〇× 게임의 AI인 ai_pmc를 정의하고, 랜덤하게 수를 두는 AI인 ai2s와 대전함으로써, ai_pmc가 최선의 수를 선택하지 않는 국면이 존재함을 확인했습니다.

이번 기사에서는 우선 원시 몬테카를로법이 최선의 수를 선택하지 않는 국면에서 어떤 합법수 (Legal Move)를 선택하는지 조사함으로써, 원시 몬테카를로법의 성질 검증을 시작합니다. 또한, 그 과정에서 Mbtree 클래스에 버그가 있음이 판명되어 해당 버그를 수정합니다.

참고로, 원시 몬테카를로법에서는 플레이아웃 (Playout) 횟수가 늘어나면 늘어날수록 대수의 법칙 (Law of Large Numbers)에 의해 플레이아웃 결과의 비율이 이론적인 확률에 가까워집니다. 따라서 원시 몬테카를로법의 검증은 플레이아웃 횟수를 무한히 수행했을 경우의 이론적 확률을 바탕으로 수를 선택한다는 전제하에 검증을 진행합니다.

또한, "무한 횟수의 플레이아웃을 수행했을 경우의 원시 몬테카를로법"이라는 표기는 번거로우므로, 이번 기사에서는 이를 "무한 횟수의 원시 몬테카를로법"이라고 표기하겠습니다.

무한 횟수의 원시 몬테카를로법이 최선의 수를 선택하지 않는 국면을 검증하기 위해서는, 그러한 국면의 목록을 계산해야 합니다. 그 방법에 대해 잠시 생각해 보세요.

아래는 그 계산을 수행하는 알고리즘입니다.

• 이전 기사에서 계산하여 파일로 저장한, 각 국면에서의 플레이아웃 결과의 이론적 확률을 기록한 Mbtree 데이터를 파일에서 읽어온다.
• 읽어온 게임 트리 (Game Tree)의 각 노드 (Node)에 대해, 무한 횟수의 원시 몬테카를로법에 의해 선택되는 합법수 목록이 최선의 수 목록에 포함되지 않는 국면을 계산하여 열거한다.

게임 트리 노드의 목록은 이전 기사에서 설명한 바와 같이 Mbtree 클래스의 nodelist 속성에 할당되어 있으므로, 이를 이용하여 모든 노드를 조사할 수 있습니다.

단계 2에서 열거하는 국면의 조건은, 무한 횟수의 원시 몬테카를로법에 의해 선택되는 합법수의 집합을 A, 해당 국면의 최선의 수 집합을 B라고 할 때, 집합 A의 모든 요소가 집합 B에 포함된다는 포함 관계 $A \subseteq B$가 만족되지 않는 경우를 나타냅니다. Python의 집합을 나타내는 set은 <= 연산자로 포함 관계가 있는지 판정할 수 있으므로, 포함 관계가 만족되지 않는 것은 not (A <= B)라는 식으로 판정할 수 있습니다. set에 대해 잊어버리신 분은 이전 기사를 복습해 주세요.

A와 B가 실수인 경우에는 A ≦ B가 만족되지 않는 것과 A > B가 만족되는 것이 같은 의미를 갖지만, A와 B가 집합인 경우에는 $A \subseteq B$가 만족되지 않는 것과 $A \supset B$가 만족되는 것이 서로 다른 의미를 갖기 때문에, A > B라는 식으로 판정을 수행할 수는 없다는 점에 주의하십시오. 예를 들어 A = {1, 2}, B = {3, 4, 5}인 경우에는 $A \subseteq B$와 $A \supset B$가 모두 만족되지 않습니다.

아래는 그러한 처리를 수행하는 프로그램입니다. 참고로 최선의 수 목록은 게임 트리 각 노드의 bestmoves 속성에 이미 기록되어 있습니다. 잊어버리신 분은 이전 기사를 복습해 주세요.

3행: 파일에서 플레이아웃의 이론적 결과가 계산된 Mbtree 클래스의 인스턴스를 읽어온다 -
5행: 조건을 만족하는 국면의 노드 목록을 기록할 nodelist를 빈 list로 초기화한다. 이때, nodelist에는 (노드, 무한 횟수의 원시 몬테카를로법이 선택하는 합법수의 집합, 최선의 수 집합)이라는 tuple을 기록하기로 한다 -
6~16행: 이전 기사에서 정의한 ai_pmc와 동일한 알고리즘으로 무한 횟수의 원시 몬테카를로법에 의해 계산되는 합법수 목록을 계산하여 bestmoves에 대입한다 -
17, 18행: bestmoves의 집합이 국면의 진짜 최선의 수 목록을 나타내는 node.bestmoves의 집합에 포함되어 있지 않은 경우 nodelist

의 요소에 해당 노드의 정보를 추가한다 -
20행: nodelist

의 요소 수와 게임 트리 (game tree) 노드의 수를 계산하여 표시한다.

1 from tree import Mbtree
2
3 mbtree = Mbtree.load("../data/playout")
...

행 번호가 없는 프로그램

from tree import Mbtree
mbtree = Mbtree.load("../data/playout")
nodelist = []
...

실행 결과

1614 549946

실행 결과로부터 게임 트리의 549,946개 노드 중 1,614개의 노드에서 무한 횟수의 원시 몬테카를로법 (Vanilla Monte Carlo)이 최선의 수를 선택하지 않음을 확인할 수 있었습니다.

아래는 위 프로그램으로 계산한, 무한 횟수의 원시 몬테카를로법이 최선의 수를 선택하지 않는 처음 5개 노드의 「국면 (board state)」, 「선택하는 합법수 목록」, 「최선의 수 목록」을 표시하는 프로그램입니다. 계산된 좌표는 (x, y) 좌표가 아니므로 move_to_xy 메서드로 (x, y) 좌표로 변환한 뒤 표시를 수행했습니다.

for node, pmcmoves, bestmoves in nodelist[:5]:
pmcmoves = [node.mb.board.move_to_xy(move) for move in pmcmoves]
bestmoves = [node.mb.board.move_to_xy(move) for move in bestmoves]
...

실행 결과

pmcmoves [(1, 1)]
bestmoves [(1, 0), (2, 2), (2, 0)]
Turn o
...

실행 결과로부터 다음 사항을 확인할 수 있습니다.

• 어떤 국면에서도 선택되는 합법수가 최선의 수 목록에 포함되지 않음
• 1, 2, 5번째 국면이나, 3, 4번째 국면처럼 동일한 국면이 계산되고 있음

동일 국면을 통합함으로써 검증할 국면을 대폭 줄일 수 있으므로, 동일 국면을 계산하지 않도록 위 프로그램을 개량하기로 합니다. 그 방법에 대해 잠시 생각해 보세요.

아래는 동일 국면을 계산하지 않도록 하는 알고리즘입니다.

• 계산된 국면의 집합을 나타내는 변수 checkedmb를 빈 set으로 초기화한다.
• 노드의 계산을 수행할 때, 해당 노드의 국면을 나타내는 해시 가능한 (hashable) 값을 board_to_hashable 메서드로 계산하고, 그 값이 checkedmb에 포함되어 있다면 해당 국면은 확인된 것이므로 처리를 건너뛴다.
• 동일 국면을 나타내는 해시 가능한 값의 목록을 calc_same_hashables로 계산하여 checkedmb에 추가함으로써 동일 국면을 계산 완료 상태로 만든다.

아래는 위 알고리즘으로 수정한 프로그램입니다.

• 1행: 위 절차 1을 수행
• 4, 5행: 위 절차 2를 수행
• 6행: 위 절차 3을 수행

1 checkedmb = set()
2 nodelist = []
3 for node in mbtree.nodelist:
...

행 번호가 없는 프로그램

checkedmb = set()
nodelist = []
for node in mbtree.nodelist:
...

수정 사항

+checkedmb = set()
nodelist = []
for node in mbtree.nodelist:
...

실행 결과

30 549946

실행 결과로부터 동일 국면을 제외함으로써 무한 횟수의 원시 몬테카를로법이 최선의 수를 선택하지 않는 국면이 30종류로 대폭 줄어든 것을 확인할 수 있었습니다.

아래는 해당 국면의 목록을 표시하는 프로그램입니다.

for node, pmcmoves, bestmoves in nodelist:
pmcmoves = [node.mb.board.move_to_xy(move) for move in pmcmoves]
bestmoves = [node.mb.board.move_to_xy(move) for move in bestmoves]
...

실행 결과

pmcmoves [(1, 1)]
bestmoves [(1, 0), (2, 2), (2, 0)]
Turn o
...

실행 결과로부터 어떤 국면에서도 무한 횟수의 원시 몬테카를로법 (Primitive Monte Carlo Method)이 선택하는 합법수가 최선수 목록에 포함되지 않음을 확인할 수 있었습니다. 30종류의 모든 국면을 검증하는 것은 매우 힘든 일이므로, 위 국면들 중 몇 가지에 대해서만 검증을 수행하기로 합니다.

위의 실행 결과에서는 표시되는 모든 국면에서 "무한 횟수의 원시 몬테카를로법이 선택하는 모든 합법수"가 최선수에 포함되지 않지만, 무한 횟수의 원시 몬테카를로법이 선택하는 합법수 중에서 단 하나라도 최선수에 포함되지 않는 합법수가 존재한다면, 그 국면에서 최선수가 아닌 착수가 이루어질 가능성이 생깁니다.

실행 결과와 같이 문자로 표기된 내용을 사용하여 국면을 검증하는 것은 이해하기 어려우므로, 이전 기사에서 정의한 게임 트리 (Game Tree)를 이미지로 시각화하는 Mbtree_GUI 클래스를 이용한 검증을 수행하기로 합니다. 다만, 아래의 프로그램을 실행하면 실행 결과와 같은 에러가 발생하는 것으로 판명되었기에, 이번 기사에서는 이 에러를 수정하도록 하겠습니다.

from tree import Mbtree_GUI
Mbtree_GUI()

실행 결과 (이미지는 생략했습니다)

---------------------------------------------------------------------------
TypeError Traceback (most recent call last)
Cell In[5], line 3
...

에러 메시지를 통해 self.board[mark] |= move라는 처리에서 int 형과 tuple을 |= 연산자로 계산하려고 시도한 것이 원인이 되어 에러가 발생했음을 알 수 있으므로, self.board[mark]와 move의 값이 실제로 무엇인지 확인하여 에러의 원인을 검증하기로 합니다.

in BitBoard3x3.setmark_by_move(self, move, mark)라는 메시지를 통해 다음 사항을 알 수 있습니다.

• 이 처리는 BitBoard3x3 클래스의 setmark_by_move 메서드에서 이루어지고 있다.
• 따라서 self는 BitBoard3x3 클래스의 인스턴스이다.
• 따라서 self.board[mark]는 mark 차례의 비트보드 (Bitboard)를 나타내는 int 형 데이터이다.

에러 메시지를 거슬러 올라가면 in Mbtree.create_subtree(self)와 move = bestmoves_and_score_by_board[board_str]["bestmoves"][0]라는 메시지를 통해, move에는 Mbtree 클래스의 create_subtree 내에서 bestmoves_and_score_by_board[board_str]["bestmoves"][0]가 대입되어 있음을 확인할 수 있습니다. Mbtree 클래스의 정의는 상당히 이전 기사에서 다루었기 때문에, 필자를 포함하여 아마 대부분의 분은 그 상세 내용을 기억하지 못하고 계실 것이라 생각합니다. 그래서 이 값에 대해 Mbtree 클래스의 프로그램을 살펴보며 확인해 보기로 합니다.

bestmoves_and_score_by_board에는 아래의 프로그램과 같이 Mbtree 클래스의 create_subtree 내에서 self.subtree["bestmoves_and_score_by_board"]가 대입됩니다.

def create_subtree(self):
    bestmoves_and_score_by_board = self.subtree["bestmoves_and_score_by_board"]
    (중략)

또한, self.subtree에는 아래의 프로그램과 같이 Mbtree 클래스의 __init__ 메서드 내에서, 가매개변수 (Dummy argument) subtree의 값이 None이 아닌 경우 가매개변수 subtree의 값이 대입됩니다.

def __init__(self, algo="bf", shortest_victory=False,
             recalculate_draw_score=False, subtree=None):
    if subtree is not None:
        ...

Mbtree 클래스의 인스턴스를 생성하는 처리는 아래의 프로그램과 같이 Mbtree_GUI 클래스의 update_gui

메서드 내에서 키워드 인자 (keyword argument) subtree에 아래의 프로그램과 같은 dict를 대입하여 호출됩니다. 따라서, self.subtree["bestmoves_and_score_by_board"]에는 self.bestmoves_and_score_by_board의 값이 대입되는 것을 확인할 수 있었습니다.

def update_gui(self):
略
self.mbtree = Mbtree(
...

self.bestmoves_and_score_by_board에는 아래의 프로그램과 같이 Mbtree_GUI 클래스의 create_widgets 메서드 내에서 self.dropdown.value의 값이 대입됩니다. self.dropdown에는 이전 기사에서 설명한 Dropdown 위젯이 대입되며, self.dropdown.value에는 Dropdown 위젯에서 선택된 항목에 대응하는 self.scoretable_dict에 대입된 dict의 키(key) 값이 대입됩니다.

def create_widgets(self):
略
self.dropdown = widgets.Dropdown(
...

앞서의 프로그램에서는 Mbtree_GUI를 실인자 (actual argument)를 기술하지 않고 호출하고 있기 때문에, 아래 Mbtree_GUI 클래스의 __init__ 메서드의 가인자 (formal argument) scoretable_dict에는 기본값인 None이 대입됩니다. 그 때문에 self.scoretable_dict에는 util.py에서 정의된, 최선의 수 등의 데이터를 파일로부터 읽어오는 load_bestmoves를 통해 파일에서 읽어온 3개의 요소를 가진 dict가 대입됩니다.

def __init__(self, scoretable_dict=None, show_score=True, size=0.15):
if scoretable_dict is None:
from util import load_bestmoves
...

self.dropdown.value는 그중 하나를 나타내므로, 아래의 프로그램과 같이 scoretable_dict의 첫 번째 키 값을 프로그램으로 표시해 보겠습니다. 또한, bestmoves_and_score_by_board.dat에 기록된 데이터는 이전 기사에서 설명한 바와 같이 「국면과 최선의 수·평가값의 대응표」를 나타냅니다. 잊으신 분은 복습해 주세요.

from util import load_bestmoves
from pprint import pprint
bestmoves = load_bestmoves("../data/bestmoves_and_score_by_board.dat")
...

실행 결과

{'.........': {'bestmoves': [(0, 0),
(1, 0),
(2, 0),
...

실행 결과로부터 load_bestmoves로 읽어온 「국면과 최선의 수·평가값의 대응표」를 나타내는 데이터에는 국면을 나타내는 문자열을 키(key)로 하고, 키의 값에 아래와 같은 dict가 대입되는 것을 확인할 수 있었습니다.

키	키의 값
bestmoves	국면의 최선의 수 목록을 (x, y) 형식으로 기록한 list
score	해당 국면의 평가값

move = bestmoves_and_score_by_board[board_str]["bestmoves"][0]라는 식의 board_str에는 게임판을 나타내는 문자열이 대입되어 있으므로, 위의 데이터 구조로부터 move에는 해당 국면의 최선의 수 목록을 나타내는 list의 첫 번째 요소가 대입됩니다. 또한, 위의 실행 결과로부터 해당 요소는 최선의 수 좌표를 나타내는 (x, y)라는 튜플 (tuple)임을 확인할 수 있었습니다.

이상의 검증을 통해, self.board[mark] |= move라는 식에서 실제로 int 형과 tuple을 |= 연산자로 연산했기 때문에 에러가 발생했음을 확인할 수 있었습니다.

이러한 에러가 발생한 원인은 이전 기사에서 Marubatsu 클래스가 이용하는 게임판을 나타내는 기본 클래스가 ListBoard에서 BitBoard3x3으로 변경되었기 때문입니다. ListBoard 클래스의 게임판 좌표는 (x, y)라는 tuple이며, 방금 전 에러가 발생했던 setmark_by_move 메서드가 ListBoard 클래스의 메서드인 경우에는 move의 값이 (x, y)라는 tuple인 것이 맞으므로 에러가 발생하지 않습니다. 반면, 변경 후의 BitBoard3x3 클래스의 경우에는 setmark_by_move 메서드의 move는 int 형의 비트보드 (BitBoard) 데이터여야 하므로 에러가 발생하게 됩니다.

이 에러를 수정하는 방법으로는, bestmoves_and_score_by_board.dat 내의 좌표 데이터를 (x, y) 좌표에서 Marubatsu 클래스가 실제로 이용하고 있는 게임판 클래스의 좌표 데이터로 변경하는 방법과, self.board[mark] |= move 처리를 수행하기 전에 move를 Marubatsu 클래스가 실제로 이용하고 있는 게임판 클래스의 좌표 데이터로 xy_to_move 메서드를 이용하여 변환하는 방법을 생각할 수 있습니다.

전자의 방법은 bestmoves_and_score_by_board.dat의 데이터를 다시 만들어야 한다는 점과, 향후 기사에서 Marubatsu 클래스가 이용하는 기본 게임판 클래스가 변경될 경우(1)에 또다시 같은 종류의 수정을 해야 한다는 문제가 있습니다. 후자의 방법의 경우에는 그러한 문제가 발생하지 않으므로, 본 기사에서는 후자의 방법으로 수정하기로 합니다.

아래는 그와 같이 Mbtree 클래스의 create_subtree 메서드를 수정한 프로그램입니다.

9, 10행: bestmoves_and_score_by_board에서 계산한 (x, y) 좌표를 게임판을 나타내는 childmb.board의 xy_to_move 메서드로 게임판 좌표로 변환한다.

1 from marubatsu import Marubatsu
2 from tree import Node
3 from copy import deepcopy
...

행 번호가 없는 프로그램

from marubatsu import Marubatsu
from tree import Node
from copy import deepcopy
...

수정 부분

from marubatsu import Marubatsu
from tree import Node
from copy import deepcopy
...

위의 수정 후에 아래 프로그램을 실행하면, 실행 결과와 같이 다른 에러가 발생합니다. 또한, 두 가지 에러가 표시되지만, 아래에서는 첫 번째 에러만을 표기합니다. 그 이유는 첫 번째 에러의 원인을 수정함으로써 두 번째 에러도 수정되기 때문입니다. 이 에러의 원인에 대해 잠시 생각해 보시기 바랍니다.

Mbtree_GUI()

실행 결과 (표시되는 이미지는 생략합니다)

---------------------------------------------------------------------------
KeyError Traceback (most recent call last)
Cell In[8], line 1
...

에러 메시지를 통해 Mbtree 클래스의 draw_subtree 메서드 내의 bestnode.children_by_move[bestmove] 처리를 수행할 때, bestmove에 (1, 1)이라는 tuple이 대입되어 있으며, bestnode.children_by_move에 대입된 dict에 (1, 1)이라는 키가 존재하지 않는 것이 원인임을 알 수 있습니다.

또한, 직전 행의 bestmove = bestnode.bestmoves[0]으로부터 bestmove에는 bestnode.bestmoves[0]이 대입되어 있음을 알 수 있습니다.

bestnode

에는 게임 트리의 노드를 나타내는 Node 클래스의 인스턴스가 할당되어 있으며, 그 bestmoves 속성 값은 아래 프로그램의 Node 클래스의 __init__ 메서드에서 기본 인자 bestmoves_and_score_by_board의 "bestmoves" 키 값으로 대입됩니다.

def __init__(self, mb:Marubatsu, parent=None, depth=0, bestmoves_and_score_by_board=None):
# 생략
if bestmoves_and_score_by_board is not None:
...

이 기본 인자 bestmoves_and_score_by_board에는 이름에서 알 수 있듯이 앞서 설명한 Mbtree_GUI 클래스 내에서 파일로부터 읽어온 "상황(局面)과 최선수・평가값의 대응표" 데이터가 대입됩니다. 이는 이전에와 동일한 검증을 수행함으로써 확인할 수 있지만, 설명이 길어지므로 생략합니다. 흥미가 있는 분은 실제로 확인해 보세요.

따라서, bestmove = bestnode.bestmoves[0]에 의해 bestmove에는 (x, y)라는 tuple이 대입됩니다. 한편, 게임 트리의 노드 children_by_move 속성에는 아래 프로그램의 실행 결과에서 알 수 있듯이 BitBoard3x3의 좌표인 int 타입을 키로 하는 dict가 대입되어 있습니다. 이 때문에, dict의 키에 (1, 1)와 같은 tuple을 지정하여 키 값을 참조하면 앞서 발생했던 KeyError라는 에러가 발생합니다.

pprint(mbtree.root.children_by_move)

실행 결과

{1: <tree.Node object at 0x00000288C8B539D0>,
2: <tree.Node object at 0x000002888460CC00>,
4: <tree.Node object at 0x000002888FD9F330>,
...

이 에러 역시 앞서와 마찬가지로 bestmove를 게임판의 좌표로 변환함으로써 수정할 수 있습니다. 아래는 그렇게 draw_subtree 메서드를 수정한 프로그램입니다.

8, 9행目: (x, y) 좌표를 게임판을 나타내는 bestnode.mb.board의 xy_to_move 메서드로 게임판의 좌표로 변환합니다.

1 import matplotlib.patches as patches
2
3 def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
...

행 번호가 없는 프로그램

import matplotlib.patches as patches
def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
...

수정된 부분

import matplotlib.patches as patches
def draw_subtree(self, centernode=None, selectednode=None, ax=None, anim_frame=None,
isscore=False, show_bestmove=False, show_score=True, size=0.25, lw=0.8, maxdepth=2):
...

위의 수정 후 아래 프로그램을 실행하면, 실행 결과처럼 에러가 발생하지 않게 되었음이 확인됩니다. 또한, 다양한 조작을 해도 에러가 발생하지 않는 것을 확인해 보세요.

Mbtree_GUI()

실행 결과

이상으로 Mbtree_GUI 클래스의 처리에 관한 버그 수정이 완료되었습니다. 이 버그는 게임판을 나타내는 Marubatsu 클래스의 사양을 수정한 것으로 인해 발생한 것이지만, 이처럼 특정 클래스의 사양을 변경함으로써 다른 클래스의 처리에서 버그가 발생하는 것은 주의를 기울이더라도 매우 자주 일어나는 일입니다. 실제로 Marubatsu 클래스의 사양을 수정할 때 이러한 버그가 발생하지 않도록 주의를 기울였으나, 안타깝게도 실제로 버그가 발생하고 말았습니다.

GUI에서 게임을 플레이하는 gui_play

하지만 Mbtree_GUI 클래스를 이용하고 있기 때문에, 위의 수정을 수행하기 전에 gui_play()를 실행하면 동일한 버그가 발생합니다. 어쩌면 gui_play의 처리 과정에서 다른 버그가 발생하고 있을 가능성도 있으므로, 위의 버그를 수정한 후 아래의 프로그램을 실행해 본 결과, 실행 결과와 같은 에러가 발생하는 것을 확인할 수 있었습니다.

from util import gui_play
gui_play()

실행 결과 (표시되는 이미지는 생략합니다)