Python으로 ○× 게임 AI를 밑바닥부터 만들기 그 233: 플레이아웃(Playout) 처리의 고속화

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

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

지난 기사에서는 아래의 원시 몬테카를로 방법 (Primitive Monte Carlo Method) 알고리즘에 필요한 플레이아웃 (Playout) 구현을 진행했습니다.

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

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

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

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

지난 기사에서 실제로 확인했듯이, 원시 몬테카를로 방법은 대수의 법칙 (Law of large numbers)에 따라 플레이아웃을 수행한 횟수가 많을수록 정밀도가 높아집니다. 따라서 플레이아웃 처리 속도가 빠른 것이 매우 중요합니다. 이전 기사에서 여러 편에 걸쳐 Marubatsu 클래스의 다양한 처리 과정을 고속화한 이유 중 하나가 바로 이것입니다. 다른 이유로는 향후 기사에서 소개할 다양한 다른 머신러닝 (Machine Learning) 기법에서도 처리의 고속화가 매우 중요하기 때문입니다.

지난 기사에서 구현한 여러 번의 플레이아웃 결과를 집계하는 playout은 제한 시간을 설정할 수 있으므로, 현재의 playout이 1초 동안 몇 번의 플레이아웃을 수행할 수 있는지 측정해 보기로 하겠습니다. 또한, 그 과정에서 지금까지 작성한 다양한 게임판을 나타내는 클래스별로 측정을 진행하겠습니다.

참고로 지금까지 작성한 게임판을 나타내는 클래스를 아래 표에 정리합니다. 클래스명 링크는 해당 클래스를 정의한 기사로 연결되는 링크입니다.

게임판 클래스	게임판 데이터 타입	칸 데이터 타입
ListBoard	2차원 list	str
...
아래는 해당 처리를 수행하는 프로그램입니다.

4 ~ 7행: 각각의 게임판을 나타내는 클래스에 대해 count_linemark가 True인 경우와 False인 경우의 반복 처리를 수행한다. 또한, BitBoard3x3과 TwoBitBoard3x3 클래스는 마크의 수를 세는 처리를 수행하지 않으므로 키워드 인자(Keyword argument) count_linemark를 기술해도 수행되는 처리는 변하지 않는다. 따라서 이 두 클래스는 count_linemark가 False인 경우에만 처리를 수행하도록 하였다 -
8행: 이용할 게임판 클래스의 이름과 count_linemark의 값을 표시한다 -
9 ~ 10행: boardclass에 대입된 게임판을 나타내는 클래스와 count_linemark를 실인자(Actual argument)로 기술하여 Marubatsu 클래스의 인스턴스를 생성하고, 제한 시간을 1초로 설정하여 playout을 호출한다. 또한 플레이아웃 횟수를 나타내는 pnum에는 1초 동안 절대로 처리가 끝나지 않는 1억 회를 설정하였다 -
11행: playout의 반환값 중에서 실제로 플레이아웃이 수행된 횟수를 표시한다

1 from marubatsu import Marubatsu, ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3
2 from util import playout
3
...

행 번호가 없는 프로그램

행 번호가 없는 프로그램

from marubatsu import Marubatsu, ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3
from util import playout
for boardclass in [ListBoard, List1dBoard, ArrayBoard, NpBoard, NpIntBoard, NpBoolBoard, BitBoard, BitBoard3x3, TwoBitBoard3x3]:
...

실행 결과

boardclass = ListBoard count_linemark = False
playout count = 16625
boardclass = ListBoard count_linemark = True
...

아래는 위 실행 결과를 정리한 표입니다. 표에서 BitBoard3x3가 플레이아웃 처리 속도가 가장 빠르다는 것을 확인할 수 있었습니다. 또한, 많은 경우에 count_linemark가 True인 경우가 처리 속도가 느려지는 것이 확인되었습니다.

게임판 클래스	count_linemark	플레이아웃 횟수
ListBoard	False	16625
ListBoard	True	13843
List1dBoard	False	22207
List1dBoard	True	15236
ArrayBoard	False	21743
ArrayBoard	True	15985
NpBoard	False	10221
NpBoard	True	10634
NpIntBoard	False	12227
NpIntBoard	True	12647
NpBoolBoard	False	12390
NpBoolBoard	True	10252
BitBoard	False	13613
BitBoard	True	10664
BitBoard3x3		24684
TwoBitBoard3x3		23125

플레이아웃을 할 때 처리되는 과정에서는 count_markpats나 calc_same_hashables 메서드는 호출되지 않기 때문에, 해당 메서드를 이용하는 AI 함수의 처리 속도를 비교하면 위의 표와는 다른 결과가 나옵니다. 그 메서드들을 이용했을 경우의 처리 속도 검증에 대해서는 과거 글을 참고해 주십시오.

이후 playout을 개선할 예정인데, 그때 개선된 playout 처리가 올바른지 확인할 수 있도록 난수 시드를 0으로 설정하여 게임 시작 시 국면에서 1만 번의 플레이아웃을 수행하고, 플레이아웃에서 처음 (0, 0)에 착수한 경우의 결과를 표시할 예정입니다. 난수 시드를 특정 값으로 설정하면 같은 패턴의 난수가 발생합니다. 따라서 이후 개선된 playout이 올바르게 구현되어 있다면, 아래와 동일한 처리를 했을 때 같은 결과가 나오므로, 이를 확인함으로써 올바른 처리가 이루어졌는지 확인할 수 있습니다.

참고로, 모든 결과를 표시하여 확인해도 무방하지만, 확인 작업이 힘들기 때문에 (0, 0)에 착수한 경우의 결과만 확인하기로 했습니다. 궁금한 분은 playout의 반환값이 모두 같은지 확인해 보셔도 됩니다.

3행째: random.seed(0)으로 난수 시드를 0으로 설정함 -
5 ~ 8행째: 플레이아웃을 1만 번 수행하고, 처음 (0, 0)에 착수한 경우의 결과를 표시함

1 import random
2
3 random.seed(0)
...

행 번호가 없는 프로그램

import random
random.seed(0)
mb = Marubatsu()
...

실행 결과

(0, 0) o 710 x 298 draw 156

playout

playout의 처리에는 이전 기사에서 설명한, 처리 효율을 악화시키는 원인이 되는 병목 현상 (bottleneck)이 있습니다. 병목 현상이 무엇인지에 대해 잠시 생각해 보세요.

playout

의 병목 현상은 이전 기사에서 병목 현상이라는 용어를 설명했을 때의 예와 마찬가지로, 플레이아웃 (playout)을 할 때마다 deepcopy로 Marubatsu 클래스의 인스턴스를 깊은 복사 (deep copy)하고 있다는 점입니다.

아래는 playout에서 100회의 플레이아웃을 수행했을 때의 처리 시간과, 100회의 Marubatsu 클래스 인스턴스 깊은 복사를 수행했을 때의 처리 시간을 측정하는 프로그램입니다. 또한, 실제 인수를 기술하지 않고 Marubatsu 클래스의 인스턴스를 생성했으므로 이용하는 게임판을 나타내는 클래스는 BitBoard3x3이 됩니다.

from copy import deepcopy
mb = Marubatsu()
%timeit playout(mb, 100)

실행 결과

3.85 ms ± 11.8 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit
for _ in range(100):
deepcopy(mb)

실행 결과

2.12 ms ± 11.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

실행 결과로부터 playout의 3.85 ms의 약 절반인 2.12 ms가 deepcopy의 처리 시간임을 확인할 수 있었습니다. deepcopy 처리를 다른 처리로 대체함으로써 고속화할 수 있다면, playout의 처리 속도를 약 2배로 빠르게 만들 수 있습니다. 그 고속화 방법에 대해 잠시 생각해 보세요.

먼저, 이전 기사에서 수행했던 deepcopy 대체 처리를 통한 ai_abs_dls라는 AI 함수의 처리 고속화에 대해 복습하고, playout의 경우에는 동일한 방법을 사용할 수 없음을 설명하겠습니다.

수정 전의 ai_abs_dls가 deepcopy로 깊은 복사를 수행했던 이유는 다음과 같습니다.

ai_abs_dls에서는 현재 국면에 대해 각각의 합법수 (legal move)를 두었을 때의 국면 평가치를 계산할 필요가 있음 - 합법수를 두었을 때의 국면을 계산할 때는 매번 현재 국면에 대해 합법수를 두어야 하는데, 현재 국면을 나타내는 데이터에 직접 합법수를 두어 버리면 국면이 변해 버리는 문제가 있음

현재 국면을 나타내는 Marubatsu 클래스의 인스턴스에 대해 deepcopy로 깊은 복사를 수행하고, 복사한 국면에 합법수를 둠으로써 그 문제를 해결함

이전 기사에서는 착수를 취소하는 unmove라는 메서드를 구현하여, 깊은 복사를 수행하는 대신 합법수를 두고 평가치를 계산한 후 unmove 메서드를 한 번만 호출하여 현재 국면으로 되돌리는 대처를 했습니다.

반면, 플레이아웃에서는 게임의 결판이 날 때까지 착수를 계속하기 때문에, unmove를 이용하여 원래 국면으로 되돌리려면 게임의 결판이 날 때까지 수행한 착수 횟수만큼 unmove 메서드를 호출해야 합니다. 따라서 안타깝게도 플레이아웃의 경우에는 unmove로 원래 국면으로 되돌리는 방법은 효율이 나쁘며 유효한 방법이 아닙니다. 그러므로 다른 deepcopy 대체 방법을 생각해야 합니다.

playout에서 필요한 처리는 플레이아웃을 수행한 후의 mb를 플레이아웃을 수행하기 전의 국면으로 되돌리는 처리입니다. 그러한 처리는 플레이아웃을 수행한 후의 mb 속성 값을 플레이아웃을 수행하기 전의 값으로 되돌림으로써 실현할 수 있습니다. 구체적으로는 플레이아웃에 의해 값이 변화하는 mb의 속성에 대해 다음과 같은 처리를 수행합니다.

• 플레이아웃을 수행하기 전에, mb의 속성 값을 다른 변수에 복사하여 기록해 둠 - 플레이아웃을 수행한 후에, mb의 속성 값을 기록해 두었던 변수를 복사하여 복원함

deepcopy는 mb의 모든 속성을 복사하여 복원하지만, 위의 처리에서는 플레이아웃에서 변화하는 속성만을 복사하여 복원한다는 점에서 효율이 좋아집니다.

위의 처리를 수행하기 위해, 플레이아웃에 의해 변화하는 mb

의 속성을 검증해 보기로 하겠습니다. 아래는 지난 기사에서 정의한 playout 함수 내부에서 플레이아웃을 반복하는 처리 중 mb에 관한 처리만을 발췌한 프로그램입니다.

def playout(mborig, pnum, timelimit=None):
略
for _ in range(pnum):
...

위의 내용을 통해 playout 함수 내부의 플레이아웃을 수행하는 처리에서는 mb의 calc_legal_moves와 move 메서드만이 호출되고 있음을 알 수 있습니다.

calc_legal_moves 메서드는 합법수(legal moves) 목록을 계산하는 메서드이므로 국면의 상황은 변화하지 않습니다. 따라서 이 메서드를 호출해도 mb의 속성 값은 변하지 않습니다. 궁금하신 분은 calc_legal_moves 메서드의 프로그램을 보고 직접 확인해 보시기 바랍니다.

아래는 Marubatsu 클래스의 move 메서드 정의입니다.

1 def move(self, move, placedFalse):
2 if not placed:
3 self.board.setmark_by_move(move, self.turn)
...

위의 내용을 통해 아래의 속성들이 변화함을 알 수 있습니다.

• 3행: self.board.setmark_by_move에 의해 게임판에 합법수를 착수하며, board 속성이 변화함
• 5행: last_turn 속성이 변화함
• 6행: turn 속성이 변화함
• 7행: move_count 속성이 변화함
• 8행: last_move 속성이 변화함
• 9행: self.board.judge를 호출하여 승패 판정을 수행하며, status 속성이 변화함
• 10~14행: records 속성이 변화함

9행에서 호출되는 judge 메서드는 승패 판정을 계산하여 반환값으로 돌려주는 처리를 수행하는 메서드로, 해당 처리를 수행할 때 mb의 속성 값은 변화하지 않습니다. 궁금하신 분은 judge 메서드의 프로그램을 보고 확인해 보시기 바랍니다.

10~14행에서 변화하는 records 속성은 승부가 결정될 때까지 진행된 기보(착수 목록)를 기록(record)하는 속성입니다. 기보 정보는 unmove 메서드로 착수를 취소하는 처리나, 이전 기사에서 구현한 GUI를 통해 ○× 게임 대국을 진행하는 Marubatsu_GUI 클래스 내에서 대국을 나중에 되돌아볼 수 있는 리플레이 기능 처리 시 필요합니다. 하지만 플레이아웃에서 필요한 것은 대국의 승패 결과뿐이므로 기보를 기록할 필요가 없습니다. 따라서 플레이아웃 처리에서는 records 속성을 업데이트하는 처리를 생략할 수 있으며, 이를 생략함으로써 처리 속도를 개선할 수 있습니다.

결과적으로, records 속성의 업데이트 처리를 수행하지 않고 플레이아웃을 진행할 경우 기록해야 할 속성은 board, last_turn, turn, move_count, last_move, status임을 알 수 있었습니다.

플레이아웃 처리에서 Marubatsu 클래스의 move 메서드를 이용하면, 위에서 설명한 플레이아웃 처리 중 업데이트할 필요가 없는 records 속성까지 업데이트해 버리는 문제가 발생하므로 move 메서드를 그대로 사용할 수는 없습니다. 또한, Marubatsu 클래스의 속성 정보를 기록했다가 나중에 되돌리는 처리는 playout과 같은 함수가 아니라 Marubatsu 클래스의 메서드로 구현하는 것이 좋습니다. 이에 따라 Marubatsu 클래스에 해당 처리를 수행하는 playout 메서드를 정의하기로 합니다.

플레이아웃 처리에서 업데이트되는 board 속성의 값은 게임판을 나타내는 클래스의 인스턴스이므로, 이전 기사에서 설명한 바와 같이 변수에 대입하는 처리로는 데이터가 복사되지 않고 공유되어 버립니다. 따라서 처음에는 board 속성만을 deepcopy를 통해 깊은 복사(deep copy)하여 변수에 기록하는 방식으로 구현하겠습니다. 깊은 복사는 처리 속도가 느리다는 문제가 있으므로, 나중에 깊은 복사를 사용하지 않는 효율적인 처리 방식으로 수정할 예정입니다.

그 외의 플레이아웃(Playout)에서 값이 변화하는 속성(Attribute)의 값은 모두 int 형이나 str 형과 같은 불변(Immutable) 데이터이므로, 변수에 대입하는 처리만으로 데이터를 실질적으로 복사(Copy)할 수 있습니다.

앞선 설명에서는 플레이아웃 전에 mb의 속성 값을 변수에 대입하여 기록하고, 플레이아웃 후에 복원한다고 설명했지만, 아래의 알고리즘으로 처리하면 mb의 속성 값을 변경하지 않고도 플레이아웃 처리를 수행할 수 있습니다. 단, board 속성은 제외합니다. 이 방식이 mb의 속성을 복원하는 처리를 작성하지 않아도 되는 만큼 프로그램을 조금 더 간결하게 작성할 수 있으므로, 본 기사에서는 아래의 알고리즘으로 구현하기로 합니다.

• 플레이아웃 처리를 수행하기 전에, 플레이아웃 처리에 필요한 mb의 속성 값을 로컬 변수에 대입한다.
• 플레이아웃 처리에서는 mb의 속성을 이용하지 않고, 플레이아웃 처리에 필요한 mb의 속성 값을 대입한 로컬 변수를 사용하여 처리하도록 한다.

아래는 그와 같이 Marubatsu 클래스의 playout 메서드를 정의한 프로그램입니다. 설명과 수정 사항은 지난 기사에서 정의한 playout 함수로부터의 수정 사항입니다.

• 4, 9 ~ 14행: mborig를 self로 수정한다.
• 16행: 게임판을 나타내는 board 속성 값을 deepcopy로 깊은 복사하여 로컬 변수 board에 기록한다.
• 20 ~ 22행: turn, move_count, status 속성 값을 로컬 변수에 대입한다.
• 24, 25행: mb를 self로 수정한다.
• 28 ~ 32행: Marubatsu 클래스의 move 메서드와 동일한 처리를 로컬 변수만을 이용하여 수행하도록 수정한다.
• 29행: 원래 프로그램에서 last_turn 속성에 대입하던 값을 로컬 변수에 대입한다.
• 32행: 원래의 move 메서드에서는 31행 이후에 move를 last_move 속성에 대입했지만, 그 값은 다음 32행에서 그대로 이용할 뿐이므로, last_move에 move를 대입하는 처리는 하지 않고 32행에서 로컬 변수 move를 그대로 기술하기로 했다.
• 33행: 플레이아웃 처리가 끝났으므로, 로컬 변수 board에 기록해 두었던 원래 국면을 나타내는 데이터의 깊은 복사를 수행하여 board 속성에 대입해 복원한다.
• 34행: mb.status를 status로 수정한다.

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

행 번호가 없는 프로그램

from time import perf_counter
from copy import deepcopy
def playout(self, pnum, timelimit=None):
...

수정 사항

from time import perf_counter
from copy import deepcopy
-def playout(mborig, pnum, timelimit=None):
...

아래는 위에서 정의한 playout 메서드로 난수 시드(Seed)를 0으로 설정하여 1만 번의 플레이아웃을 수행하는 프로그램입니다. 앞서와 동일한 결과가 표시되는 것을 통해 올바른 처리가 이루어짐을 확인할 수 있었습니다.

random.seed(0)
retval = mb.playout(10000)
move = mb.board.xy_to_move(0, 0)
...

실행 결과

(0, 0) o 710 x 298 draw 156

아래의 앞선 예제와 유사한 프로그램으로 위에서 정의한 playout 메서드의 처리 속도를 확인해 보겠습니다. 앞선 프로그램과의 차이점은 playout(mb, pnum=100000000, timelimit=1)을 mb.playout(pnum=100000000, timelimit=1)로 수정한 점입니다.

위의 수정 사항에서는 게임판을 나타내는 board 속성에 대해 deepcopy를 사용하여 깊은 복사(deep copy)를 수행하는 부분이 비효율적이라는 점에 초점을 맞추었습니다. 따라서 다음으로 이 문제를 해결할 것입니다.

deepcopy의 대안 방법 구상은 이전과 동일하게, 플레이아웃을 수행하기 전에 게임판을 나타내는 mb.board 내에서 플레이아웃에 의해 변화하는 속성 값들을 기록해 두고, 플레이아웃 후에 원래 상태로 되돌리는 방식입니다. 다만, 이전에는 mb의 속성을 직접 변경하지 않는 알고리즘으로 프로그램을 작성할 수 있었지만, 이번에는 mb.board의 속성을 변경하지 않도록 프로그램을 작성하기가 어려우므로 이 방법은 채택하지 않습니다.

또한, Marubatsu 클래스의 메서드 내에서 게임판을 나타내는 클래스 속성을 직접 변경하는 것은 바람직하지 않으므로, 게임판을 나타내는 클래스에 아래의 두 가지 메서드를 추가하기로 결정했습니다. 수행할 처리는 게임 데이터 저장(save) 및 불러오기(load)와 유사하므로 각각 save와 load라는 이름을 붙였습니다.

게임판 클래스	count_linemark	플레이아웃 횟수	수정 후 횟수
ListBoard	False	16625	28327
ListBoard	True	13843	20445
List1dBoard	False	22207	39620
List1dBoard	True	15236	23251
ArrayBoard	False	21743	41177
ArrayBoard	True	15985	23935
NpBoard	False	10221	14189
NpBoard	True	10634	14417
NpIntBoard	False	12227	18041
NpIntBoard	True	12647	18303
NpBoolBoard	False	12390	18656
NpBoolBoard	True	10252	13625
BitBoard	False	13613	19077
BitBoard	True	10664	13415
BitBoard3x3		24684	51124
TwoBitBoard3x3		23125	45061

메서드	처리
save
게임판 클래스의 속성 중, 값이 변화하는 속성을 복사한 데이터를 반환값으로 반환한다
load
save 메서드의 반환값을 대입하는 가변 인자 data를 가지며, 게임판의 상태를 save를 실행한 시점의 상태로 복원한다

또한, 게임판을 나타내는 클래스마다 해당 속성의 데이터 구조가 다르므로, 각각의 클래스마다 이 두 가지 메서드를 구현해야 합니다.

save와 load 메서드는 모든 게임판을 나타내는 클래스에 구현해야 하므로, 아래 프로그램과 같이 게임판을 나타내는 클래스의 기저 클래스(Base Class)인 Board 클래스의 추상 메서드(Abstract Method)로 정의하기로 합니다.

from marubatsu import Board
from abc import ABCMeta, abstractmethod
@abstractmethod
...

게임판을 나타내는 클래스의 속성에는 게임판의 크기를 나타내는 BOARD_SIZE 속성 등, __init__ 메서드에서 초기화한 후 값이 변화하지 않는 속성과, 게임판을 나타내는 board 속성처럼 착수를 수행하면 변화하는 속성이 있습니다. 변화하지 않는 속성은 복사나 복원을 수행할 필요가 없습니다.

아래는 값이 변화하는 속성의 목록이며, 이 속성들의 값에 대한 복사 및 복원 처리를 수행해야 합니다. 그 방법에 대해 잠시 생각해 보세요.

속성	의미
board
게임판을 나타내는 데이터. 데이터 구조는 게임판 클래스에 따라 다르다
rowcount
각 행의 마크 수를 나타내는 데이터
colcount
각 열의 마크 수를 나타내는 데이터
diacount
각 대각선의 마크 수를 나타내는 데이터
cross_turn
×의 차례인지 여부를 나타내는 int형 데이터. TwoBitBoard3x3 클래스에만 존재한다

아래는 board 속성의 데이터 구조를 나타내는 표입니다.