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

지난 기사에서는 아래의 원시 몬테카를로 (pure monte carlo) 법 알고리즘에 필요로 하는 플레이아웃 (playout) 처리의 고속화를 수행했습니다.

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

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

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

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

이번 기사에서는 위의 알고리즘으로 최선수를 계산하는 AI 함수를 정의합니다.

또한, 「여러 번의 플레이아웃을 수행했을 경우의 승률」이라는 표기는 중복되므로, 이후에는 국면의 승률과 무승부율이라는 용어를 해당 국면에서 여러 번의 플레이아웃을 수행했을 경우의 승률과 무승부율이라는 의미로 사용하기로 합니다. 또한, 승률은 해당 국면 차례인 플레이어의 승률을 나타내기로 합니다.

AI 함수의 이름은 원시 몬테카를로 (pure monte carlo) 법을 사용하므로 ai_pmc라고 명명하기로 합니다.

아래는 ai_pmc의 가변 인자 목록으로, 최선수를 계산할 국면을 대입하는 mb, playout 메서드를 호출할 때 사용하는 플레이아웃 설정을 대입하는 pnum, timelimit, 지금까지 작성한 AI 함수로 구현한 디버그 표시 및 분석용 결과를 반환할지 여부를 나타내는 가변 인자 debug와 analyze를 정의하기로 했습니다. 또한, mb 이외의 가변 인자에는 아래 표와 같은 기본값을 설정하기로 했습니다. 그 외에 아래 이외의 가변 인자에 대응하는 실인자가 기술되었을 경우 에러가 발생하지 않도록 하기 위해 *args와 **kwargs를 정의했습니다.

또한, analyze가 True인 경우에는 분석용 데이터로서 아래의 dict를 반환값으로 반환하기로 합니다.

다음으로, 위의 사양에 따라 ai_pmc를 정의하는데, 그때 방금 전의 원시 몬테카를로 법에 문제가 있다는 것을 깨달았으므로 그 수정을 진행하기로 합니다. 어떤 문제가 있는지 잠시 생각해 보세요.

방금 설명한 원시 몬테카를로 법 알고리즘의 절차 2는 「가장 높은 승률이 계산된 국면이 되는 합법수를 최선수로 한다」라고 되어 있습니다. 대전 결과가 승리와 패배밖에 없는 경우에는 이것으로 문제가 없지만, 〇× 게임의 경우에는 무승부라는 결과가 있기 때문에 무승부율에 대해서도 고려할 필요가 있습니다. 그래서 최고 승률이 같을 경우에는 무승부율이 더 높은 국면이 되는 합법수를 최선수로 하기로 합니다.

상정되는 구체적인 예로는, 어떤 합법수를 두어도 무승부 이상밖에 되지 않는 국면이 있습니다. 그 경우에는 어떤 합법수를 두었을 때의 국면의 승률도 모두 0%가 되기 때문에, 무승부율이 가장 높아지는 합법수를 최선수로 합니다.

또한, 동률인 최선수가 여러 개 존재할 경우에 대한 언급이 없으므로, 그러한 경우에는 그중에서 랜덤하게 선택하기로 합니다.

아래는 그렇게 수정한 원시 몬테카를로 법의 절차 2입니다.

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

아래는 ai_pmc를 정의하는 프로그램입니다. 또한, 최선수 목록을 계산하는 알고리즘은 이전 기사에서 설명한, 합법수를 착수했을 때의 국면 중 가장 높은 평가치를 계산하는 알고리즘과 동일합니다. 다만, 이번에는 「최고 승률」과 「그때의 무승부율」을 기록할 필요가 있으므로, best_ratio라는 변수에 「최고 승률」과 「그때의 무승부율」을 요소로 하는 tuple을 기록하기로 했습니다.

디버그 표시(debug display)에 관해서는 이전 기사에서 정의한, 가장 평가치가 높은 합법수를 최선수로 계산하는 AI 함수의 데코레이터(decorator)로 사용되는 ai_by_score의 처리를 유용했습니다.

4행: 위에서 설명한 매개변수를 가진 함수로서 ai_pmc를 정의한다 -
5행: playout 메서드에서 매개변수 pnum과 timelimit에 대입된 횟수와 제한 시간으로 플레이아웃(playout)을 수행하고, 그 결과를 retval에 대입한다. playout의 반환값 데이터 구조를 잊어버린 분은 이전 기사를 복습할 것 -
6행: 최선수 목록을 기록하는 best_moves를 빈 list로 초기화한다 -
7행: best_ratio를 (-1, 0)이라는 tuple로 초기화한다. 승률의 최솟값은 0이므로, 최고 승률을 나타내는 tuple의 요소를 그보다 작은 -1로 설정함으로써, 반드시 best_ratio가 첫 번째 합법수를 착수했을 때의 국면의 승률과 무승부율로 업데이트되도록 한다 -
8, 9행: analyze가 True인 경우 반환값으로 돌려줄 dict의 ratio_by_move 키 값을 계산할 변수를 빈 dict로 초기화한다 -
10 ~ 29행: 플레이아웃의 집계 결과를 나타내는 retval["result"]로부터 각각의 합법수를 착수했을 때의 국면의 승률과 무승부율을 계산하고, 최고 승률이었을 경우 best_moves와 best_ratio를 업데이트한다. 반복문(loop)에서는 move에는 합법수가, count에는 해당 합법수를 착수했을 때의 국면으로부터 플레이아웃을 수행했을 경우의 집계 결과를 기록한 dict가 대입된다 -
11행: 처음에 move를 착수했을 때의 플레이아웃 횟수를 내장 함수 sum으로 계산한다 -
12, 13행: move를 착수했을 때의 국면의 승률과 무승부율을 계산한다. 승률은 현재 국면 차례 플레이어의 승수를 나타내는 count[mb.turn]을 사용하여 계산한다 -
14 ~ 17행: move, move를 착수했을 때의 국면의 승률과 무승부율, 지금까지 계산한 최선수의 승률과 무승부율을 디버그 표시한다 -
18 ~ 23행: 「승률이 최고 승률보다 큰」 경우 또는 「승률과 최고 승률이 같고, 무승부율이 최고 승률일 때의 무승부율보다 큰」 경우에, 최선수와 최고 승률의 업데이트 및 디버그 표시를 수행한다 -
24 ~ 27행: 위의 조건을 만족하지 않는 경우, 「승률과 최고 승률」 및 「무승부율과 최고 승률일 때의 무승부율」이 같은 경우에, 최선수 목록에 move를 추가하고 디버그 표시를 수행한다 -
28, 29행: analyze가 True인 경우 ratio_by_move에 move의 승률과 무승부율을 기록한다 -
30 ~ 37행: analyze의 값에 따른 반환값을 돌려준다

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

행 번호가 없는 프로그램

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

아래는 게임 시작 시의 국면에 대해 위에서 정의한 ai_pmc로 최선수를 계산하는 프로그램입니다. 실행 결과로부터 가운데 칸인 (1, 1)이 계산된 것을 확인할 수 있습니다.

from marubatsu import Marubatsu
mb = Marubatsu()
print(mb.board.move_to_xy(ai_pmc(mb)))

실행 결과

(1, 1)

아래는 debug=True와 analyze=True를 실제 인자(actual argument)로 기술했을 경우의 프로그램입니다. 반환값인 dict의 표시를 알기 쉽게 하기 위해 pprint를 이용했습니다. 실행 결과에 표시되는 합법수(legal move)의 좌표가 정수로 표현되는 BitBoard3x3의 좌표라는 점이 알아보기 어렵다는 문제가 있으므로, 그 수정을 거친 후 실행 결과에 대해 고찰해 보기로 합니다.

from pprint import pprint
pprint(ai_pmc(mb, debug=True, analyze=True))

실행 결과

====================
move 1
ratio win: 0.610 draw 0.134
...

아래는 board_to_xy 메서드를 이용하여 합법수를 (x, y) 좌표로 표시하도록 ai_pmc를 수정한 프로그램입니다. 또한, analyze가 False인 경우 반환값으로 계산하는 최선수는 게임판의 좌표로 계산할 필요가 있습니다. 따라서 best_moves의 계산 처리는 변경하지 않고, 분석용으로서 (x, y) 좌표로 최선수 목록을 나타내는 best_movesxy를 별도로 계산하도록 했습니다. 또한 best_movesxy에 관한 처리를 추가한 만큼 ai_pmc의 처리 속도는 느려지지만, 플레이아웃 (playout) 횟수가 어느 정도 이상 많다면 플레이아웃 처리 시간과 비교했을 때 무시할 수 있을 정도로 짧은 처리이므로 그 점을 신경 쓸 필요는 없을 것입니다.

4행: (x, y) 좌표로 최선수 목록을 기록하는 best_movesxy를 빈 리스트(list)로 초기화한다 -
12행: move를 (x, y) 좌표로 변환하여 movexy에 대입한다 -
20, 26행: best_movesxy에 (x, y) 좌표를 기록하는 처리를 추가한다 -
14, 23, 28, 30행: 디버그 표시와 ratio_by_move에 관한 move를 (x, y) 좌표로 나타내는 movexy로 수정한다 -
33행: best_moves를 best_movesxy로 수정한다

1 def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
2 retval = mb.playout(pnum, timelimit)
3 best_moves = []
...

행 번호가 없는 프로그램

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
retval = mb.playout(pnum, timelimit)
best_moves = []
...

수정 부분

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
retval = mb.playout(pnum, timelimit)
best_moves = []
...

처리 속도가 아주 조금 느려지기 때문에 본 기사에서는 수행하지 않겠지만, ai.py의 ai_by_score나 ai_by_mmscore에도 동일한 성질이 있으므로, 그 점이 신경 쓰이는 분은 위와 같이 (x, y) 좌표가 표시되도록 수정해 보시기 바랍니다.

몇 가지 조건에서 debug=True, analyze=True로 설정하여 ai_pmc의 동작을 확인함으로써, ai_pmc가 이론적인 플레이아웃 결과에 가까운 값을 계산하는 것과 원시 몬테카를로 법 (Primitive Monte Carlo method) 알고리즘대로 계산하는 것을 확인하도록 하겠습니다.

먼저 〇의 차례인 국면에서의 확인을 진행하겠습니다. 아래는 방금 전과 동일한 게임 시작 시의 〇 차례 국면에 대해 ai_pmc

로 최선의 수를 계산하는 프로그램입니다. 실행 결과로부터 위의 수정을 통해 합법수(legal move)의 좌표가 (x, y) 좌표로 표시되게 된 것을 확인할 수 있습니다. 또한, 디버그 표시를 통해 최선의 수 목록 데이터가 원시 몬테카를로 법 (Primitive Monte Carlo Method) 알고리즘에 따라 올바르게 업데이트되어 가는 모습을 확인할 수 있습니다.

pprint(ai_pmc(mb, debug=True, analyze=True))

실행 결과

==================================================
move (0, 0)
ratio win: 0.613 draw 0.112
...

아래는 이전 기사에서 계산한, 게임 시작 후 1회의 착수를 수행한 국면에서 플레이아웃 (playout)을 수행했을 경우의 이론적인 확률을 나타내는 표입니다. 위의 실행 결과와 비교하여 〇의 승률과 무승부율이 상당히 가깝게 계산되고 있음을 확인해 주십시오. 또한, 그중에서도 〇의 승률이 가장 높은 (1, 1)만이 최선의 수 후보(candidate)로서 계산되고 있음을 확인할 수 있습니다.

다음으로 아래의 프로그램에서 게임 시작 후 중앙인 (1, 1)에 착수를 수행한 ×의 차례 국면에 대해 ai_pmc로 최선의 수를 계산하도록 하겠습니다. 이 국면은 ×의 차례인 국면이므로, 승률이 ×의 승률을 나타낸다는 점에 주의해 주십시오.

mb = Marubatsu()
mb.cmove(1, 1)
print(mb)
...

실행 결과

Turn x
...
.O.
...

실행 결과의 ratio_by_move로부터 아래 사항을 확인할 수 있습니다.

• 동일한 국면이 되는 4개 모서리 합법수의 승률은 거의 같다.
• 동일한 국면이 되는 4개 변 합법수의 승률은 거의 같다.
• 4개 모서리 합법수의 승률이 4개 변 합법수보다 높으며, 4개 모서리 중 가장 승률이 높은 (0, 0)이 최선의 수로서 계산되었다.

다음으로, 위의 결과가 이론적인 확률에 가까운 값이 되는지 확인하도록 하겠습니다.

아래는 이전 기사에서 계산하여 파일로 저장한, 각 국면에서의 플레이아웃 결과의 이론적인 확률을 기록한 Mbtree 데이터를 파일로부터 읽어와, 위의 프로그램에서 합법수를 착수했을 때의 각각의 국면에서의 플레이아웃 결과의 이론적인 확률을 표시하는 프로그램입니다.

• 3행: Mbtree의 load 메서드로 파일에 저장된 Mbtree 데이터를 읽어온다.
• 4행: 처리 과정에서 게임판 클래스의 xy_to_move와 move_to_xy 메서드를 이용할 필요가 있으므로, 게임판을 나타내는 클래스의 인스턴스를 게임 시작 시의 국면을 나타내는 게임 트리의 루트 노드인 mbtree.root로부터 추출하여 board에 대입한다.
• 5행: (1, 1) 합법수의 게임판 좌표를 계산한다.
• 6행: 게임 시작 시의 국면을 나타내는 mbtree.root에 대하여 (1, 1)을 착수했을 때의 국면을 나타내는 자식 노드를, 「합법수를 키(key)로, 키의 값을 해당 합법수를 착수했을 때의 국면을 나타내는 자식 노드로」 하는 dict가 대입된 children_by_move 속성을 이용하여 계산하여 node에 대입한다.
• 7~11행: node의 children_by_move 속성에 대한 반복 처리를 수행함으로써, node의 각각의 자식 노드에 대한 처리를 수행한다.
• 8행: node에 대해 수행된 착수를 나타내는 move를 (x, y) 좌표로 변환한다.
• 9, 10행: node의 국면으로부터의 플레이아웃 결과의 이론적인 확률은 playout_prob 속성에 대입되어 있으므로, 거기서 ×의 차례를 나타내는 node.turn

의 승률과 무승부율을 참조합니다 -
11행: 수행된 착수, ×의 승률, 무승부율을 표시한다

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

행 번호가 없는 프로그램

from tree import Mbtree
mbtree = Mbtree.load("../data/playout")
board = mbtree.root.mb.board
...

실행 결과

(0, 0) x win prob 0.229 draw prob 0.114
(0, 1) x win prob 0.157 draw prob 0.114
(0, 2) x win prob 0.229 draw prob 0.114
...

아래는 각각의 합법수(legal move)에 대한 방금 전 ai_pmc의 실행 결과와 위의 이론적인 확률을 정리한 표입니다. 상단이 ×의 승률, 하단이 무승부율을 나타냅니다. 표에서 약간의 편차는 있지만, ai_pmc가 이론적인 확률에 가까운 값을 계산하고 있음을 확인할 수 있었습니다.

다음으로, 아래의 프로그램으로 〇가 절대로 승리할 수 없는 국면에 대해 ai_pmc가 의도한 대로 계산을 수행하는지 확인합니다.

mb = Marubatsu()
mb.cmove(0, 0)
mb.cmove(1, 0)
...

실행 결과

Turn o
ox.
ox.
...

이 국면에서는 〇가 (2, 0)에 착수할 경우에는 반드시 무승부가 되며, 그 외의 곳에 착수할 경우에는 ×가 (2, 0)에 착수하면 ×의 승리, (2, 0)에 착수하지 않으면 무승부가 됩니다. 따라서 각각의 합법수를 착수했을 때의 국면 승률과 무승부율의 이론값은 아래 표와 같으며, 실행 결과의 ratio_by_move를 통해 ai_pmc가 이론적인 확률에 매우 가까운 값을 계산하고 있음을 확인할 수 있었습니다.

또한, 모든 합법수를 착수했을 때의 국면 승률이 0 %이므로, 원시 몬테카를로 법 (Primitive Monte Carlo Method) 알고리즘에 따라 무승부율이 가장 높았던 합법수인 (2, 0)이 최선수로 올바르게 계산되었음을 확인할 수 있습니다.

지금까지의 프로그램에서는 플레이아웃 (playout) 횟수를 ai_pmc의 가변 인자(optional argument)인 pnum의 기본값인 10,000회로 하여 계산을 진행해 왔으므로, 이와는 다른 횟수의 플레이아웃으로 ai_pmc 계산을 수행해 보겠습니다.

아래는 게임 시작 시의 국면에 대해 플레이아웃 횟수를 10에서 100만까지 10배씩 늘려가며 ai_pmc 계산을 수행하는 프로그램입니다. 계산 과정의 확인은 이제 충분하다고 생각되어, 아래 프로그램에서는 analyze만 True로 설정했습니다.

이 프로그램을 실행하면 실행 결과와 같은 에러가 발생했습니다. 이 에러의 원인에 대해 잠시 생각해 보세요.

mb = Marubatsu()
for pnum in [10, 100, 1000, 10000, 100000, 1000000]:
    print(f"pnum {pnum}")
    ...

실행 결과

pnum 10
---------------------------------------------------------------------------
ZeroDivisionError Traceback (most recent call last)
...

pnum 10

의 표시 이후에 에러가 발생하고 있으므로, pnum의 값이 10일 때 에러가 발생한다는 것을 알 수 있습니다. 또한, 에러 메시지를 통해 winratio 계산 시 0으로 나누기 (division by zero), 즉 계산할 수 없는 연산이 수행된 것이 원인임을 알 수 있습니다. 또한, 그로부터 totalcount의 값이 0이라는 것을 알 수 있습니다.

totalcount는 pnum 회의 플레이아웃 (playout) 중에서, 처음에 move의 합법수 (legal move)가 착수된 횟수를 나타내지만, pnum이 10과 같이 작은 수치인 경우에는 플레이아웃에서 단 한 번도 처음에 move의 합법수가 착수되지 않는 경우가 높은 확률로 발생하며, 그 결과 totalcount가 0이 되어 0으로 나누기 에러가 발생합니다.

예를 들어, 플레이아웃 횟수가 9이고 합법수의 수가 9인 경우에는, 9회의 플레이아웃에서 처음에 착수된 합법수가 모두 다른 경우를 제외하면, 어떤 합법수가 착수된 횟수가 0회가 됩니다. 그 구체적인 확률은, 9회의 플레이아웃에서 모든 첫 착수가 다른 조합이 $9!$이고, 9회의 플레이아웃에서의 첫 착수 조합이 $9^9$이므로 $1 - \frac{9!}{9^9} \approx 0.999 \approx 99.9%$가 됩니다. 다른 예로, 플레이아웃 횟수가 합법수의 수보다 적은 경우에는 어떤 합법수도 절대 처음에 착수되지 않기 때문에 반드시 이 에러가 발생하게 됩니다.

반면, 플레이아웃 횟수를 늘림으로써 이 에러가 발생할 확률은 0에 매우 가까워집니다. 예를 들어 플레이아웃 횟수가 10000회이고 합법수의 수가 6인 경우에는, 주사위를 10000번 던져서 단 한 번도 특정 눈이 나오지 않을 경우와 마찬가지로, 극히 작은 확률(약 $10^{-800}$)로 이 에러가 발생합니다. 다만, 아무리 플레이아웃 횟수를 늘려도 안타깝게도 그 확률을 0으로 만들 수는 없으므로, 설령 플레이아웃 횟수가 일정 이상 큰 경우에만 계산을 수행한다는 것을 알고 있더라도 이 에러가 발생하지 않도록 해야 합니다.

이 에러가 발생하지 않도록 하기 위해서는, 플레이아웃에서 단 한 번도 착수가 이루어지지 않은 합법수에 대해 어떤 처리를 할지 결정해야 합니다. 본 기사에서는 승률이나 무승부율을 계산할 수 없는 합법수를 최선의 수로 선택하지 않도록 프로그램을 수정하겠습니다.

그러한 수정을 수행하는 방법 중 하나로, 최댓값을 계산하는 내장 함수 max를 이용한 totalcount = max(1, sum(count.values()))를 통해 totalcount의 최솟값을 1로 설정하여 승률과 무승부율을 계산하는 방법이 있으며, 그 경우에는 다음과 같은 계산이 이루어집니다.

• 원래의 totalcount 값이 1 이상인 경우에는 totalcount 값이 변하지 않으므로 계산 결과는 변하지 않는다.
• 원래의 totalcount 값이 0인 경우에는 totalcount를 1로 하여 계산한다. 원래의 totalcount는 승리 횟수와 무승부 횟수의 합계이므로, 이 경우에는 승리 횟수와 무승부 횟수가 반드시 0이 되어, 승률과 무승부율은 모두 0 $\div$ 1 = 0으로 계산된다. 그 결과, 해당 합법수는 다른 모든 합법수의 승률과 무승부율이 0이 아닌 한 선택되지 않게 된다.

다른 방법으로는 if 문을 이용하여 totalcount가 0인 경우 continue 문으로 처리를 건너뛰는 방법이 있습니다. if 문을 작성할 필요가 없는 만큼 프로그램을 간결하게 작성할 수 있다는 장점이 있으므로, 본 기사에서는 위의 방법을 채택하기로 합니다.

아래는 그와 같이 ai_pmc를 수정한 프로그램입니다.

• 3행: 내장 함수 max를 이용하여 totalcount의 최솟값이 1이 되도록 수정함

1 def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
2 for move, count in retval["result"].items():
...

행 번호가 없는 프로그램

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
retval = mb.playout(pnum, timelimit)
best_moves = []
...

수정된 부분

def ai_pmc(mb, pnum=10000, timelimit=None, debug=False, analyze=False, *args, **kwargs):
元と同じなので省略
for move, count in retval["result"].items():
...

이러한 0으로 나누기(Zero Division)에 의한 버그는 매우 흔하게 발생하는 버그 중 하나입니다. 나눗셈을 수행할 때는 0으로 나누기가 발생하지 않도록 주의해야 합니다.

위와 같이 수정된 후 아래 프로그램을 실행하면, 실행 결과처럼 오류가 더 이상 발생하지 않는 것을 확인할 수 있습니다.

for pnum in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"pnum {pnum}")
pprint(ai_pmc(mb, pnum=pnum, analyze=True))
...

실행 결과