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

이번 기사에서는 이전 기사에서 설명한 강화학습 (RL) 용어를 사용하여 원시 몬테카를로법 (Primitive Monte Carlo Method)에 대해 설명합니다. 그 후, 일부 프로그램을 수정하겠습니다.

먼저 일반적인 〇× 게임의 강화학습에서 이전 기사에서 설명한 강화학습 용어가 어떻게 대응하는지에 대해, 지금까지 구현한 프로그램을 예로 들며 구체적으로 설명하고, 그 후 원시 몬테카를로법에 의한 〇× 게임 강화학습의 경우에 대해 설명합니다.

아래는 원시 몬테카를로법에 국한되지 않는, 일반적인 〇× 게임의 강화학습과 강화학습 용어의 관계에 대한 설명입니다.

이전 기사에서 설명한 것처럼, 강화학습에서는 학습을 수행하는 프로그램을 에이전트 (agent), 에이전트가 다양한 행동을 시행착오하며 경험을 얻는 대상을 환경 (environment)이라고 부릅니다. 지금까지 구현한 프로그램의 경우 ai_pmc와 ai_pmc2가 에이전트이며, 〇× 게임 처리를 수행하는 Marubatsu 클래스의 인스턴스가 환경입니다. 또한, 이후의 설명에서는 환경을 나타내는 Marubatsu 클래스의 인스턴스를 mb라고 표기하겠습니다.

이전 기사에서 설명한 것처럼, 에이전트가 환경에 대해 행하는 거동을 행동 (action)이라고 부릅니다. 〇× 게임에서의 행동이란 국면의 합법수 중에서 하나를 선택하여 착수하는 것에 해당합니다. 구체적으로는 에이전트가 환경인 mb의 move 메서드를 호출하여 착수하는 것이 행동이 됩니다.

이전 기사에서 설명한 것처럼, 강화학습에서는 에이전트가 현재 환경의 상태에서 행동을 선택할 때 지침으로 삼는 '어떤 행동을 취해야 하는가'에 대한 방침을 방책 (policy)이라고 부르며, 에이전트는 방책에 따라 행동을 선택합니다. 일반적으로 방책은 학습 대상이 되는 환경의 '각 상태'에서 취할 수 있는 '각 행동을 선택할 확률'로 표현합니다. 원시 몬테카를로법의 경우의 방책은 모든 상태(국면)에서 합법수를 선택할 확률을 균등하게 배분합니다.

이전 기사에서 설명한 것처럼, 에이전트가 목적을 달성하기 위해 수행한 일련의 행동의 모임을 에피소드 (episode)라고 부르며, 에피소드 내의 하나하나의 행동을 스텝 (step)이라고 부릅니다. 〇× 게임에서의 일련의 행동이란 현재 국면에서 게임의 결판이 날 때까지 합법수를 계속해서 착수한다는 것을 의미하므로, 〇× 게임 강화학습에서의 에피소드와 스텝은 다음과 같습니다.

• 에피소드: 현재 국면에서 결판이 날 때까지 방책에 따라 합법수를 선택하고, move 메서드로 계속 착수하는 일련의 흐름
• 스텝: 에피소드 내에서 이루어지는 하나하나의 행동 (착수)

이전 기사에서 설명한 것처럼, 환경 내에서 에이전트가 현재 놓여 있는 상황을 상태 (state)라고 부르며, 〇× 게임의 경우 국면을 나타내는 '차례', '게임판', '게임 상황 (플레이 중 또는 결과)', '합법수 목록' 등이 상태입니다.

에이전트가 환경으로부터 현재 상태의 정보를 얻는 것을 관측 (observation)이라고 부르며, 〇× 게임의 경우 에이전트가 환경인 mb의 아래 속성과 메서드를 이용하는 것이 관측에 해당합니다.

이전 기사에서 설명한 것처럼, 보상 (reward)은 에이전트의 행동 결과, 목표에 대해 어느 정도의 성과를 얻었는지를 나타내는 수치로, 일반적으로 클수록 얻은 성과가 높음을 나타냅니다. 이전 기사에서 설명한 것처럼, 보상에는 스텝마다 얻는 '즉시 보상'과 에피소드 전체에서 얻는 '누적 보상' (수익)이 있습니다.

〇× 게임의 경우의 즉시 보상은 일반적으로 아래 표와 같이, 게임의 결판이 나지 않은 국면의 경우에는 0을, 결판이 난 국면의 경우에는 승패에 따른 값을 설정하며, 무승부의 경우에는 0.5 (0.5승)로 카운트합니다.

위의 즉시 보상은 〇의 차례를 기준으로 하고 있기 때문에 〇에게 유리할수록 큰 값이 됩니다. 반대로 ×의 차례인 경우에는 ×에게 유리할수록 작은 값이 되므로, 실제 강화학습 (RL)에서는 ×의 차례일 경우 위의 보상에 -1을 곱하여 부호를 반전시키는 기법이 자주 사용됩니다.

오셀로, 쇼기, 바둑과 같은 게임의 경우도 마찬가지로, 게임의 결판이 나지 않은 경우의 보상을 0으로 하고, 결판이 났을 때 승패 결과에 따른 보상을 설정합니다.

한편, 점수가 있는 액션 게임과 같은 경우에는 게임 도중에 적을 쓰러뜨리는 등의 행동을 통해 얻는 점수를 즉시 보상으로 합니다.

게임의 결판이 나지 않은 경우의 즉시 보상이 0이기 때문에, 현재 국면에서 결판이 날 때까지의 일련의 행동 (1개의 에피소드 (Episode))을 통해 얻은 즉시 보상의 합계는, 아래의 표와 같이 게임의 결판이 났을 때 얻은 즉시 보상, 즉 게임의 승패 결과를 나타내는 수치 그 자체가 됩니다.

일반적인 강화학습에서는 누적 보상 (Cumulative Reward) 또는 수익 (Return)을 즉시 보상의 합계와는 조금 다른 방법으로 계산하지만, 〇× 게임처럼 도중의 행동으로는 보상을 얻지 못하고 마지막 행동에서만 보상을 얻는 경우 등에서는 즉시 보상의 합계 그 자체를 누적 보상으로 하는 경우가 있습니다. 실제로 원시 몬테카를로법 (Vanilla Monte Carlo Method)에서의 누적 보상은 즉시 보상의 합계로 계산합니다.

원시 몬테카를로법의 누적 보상을 즉시 보상의 합계와는 다른 방법으로 계산할 수도 있습니다. 일반적인 강화학습에서 사용되는 누적 보상의 계산 방법과, 그것을 원시 몬테카를로법에 적용했을 때의 특징에 대해서는 향후 기사에서 설명할 예정입니다.

이후의 설명에서 필요하게 될 강화학습의 「탐색 (Exploration)」과 「활용 (Exploitation)」이라는 용어에 대해 설명하겠습니다.

아래는 이전 기사에서 설명한 강화학습의 목적입니다.

에이전트 (Agent)와 환경 (Environment)이 「방책 (Policy)에 따르는 행동」과 「그 결과 변화한 상태와 얻은 보상의 보고」라는 상호작용을 반복하여 얻은 경험을 바탕으로 방책을 개선함으로써, 누적 보상의 기대치를 최대화하는 방책을 학습하는 구조이다.

현실 세계에서 무언가를 자신의 힘만으로 배울 때는 다음과 같은 수법을 취하는 것이 일반적입니다.

• 미지의 행동을 수행함으로써 새로운 정보를 모은다 (경험을 얻는다)
• 지금까지 얻은 경험을 바탕으로 최적이라고 생각되는 행동을 취한다 (경험을 활용한다)

강화학습에서는 전자의 행동을 「탐색 (Exploration)」, 후자의 행동을 「활용 (Exploitation)」이라고 부릅니다. 또한, 방금 설명한 「에피소드 (Episode)」가 1회의 탐색 작업에 해당합니다.

이전 기사에서 소개한 「A 지점에서 B 지점까지의 최단 경로를 찾는」 「최단 경로 학습」을 구체적인 예로 들어 설명하겠습니다.

탐색 수법의 한 예로, 취할 수 있는 행동 중에서 랜덤하게 행동을 선택하는 것이 있습니다. 최단 경로 학습의 경우에는 교차로에 도착할 때마다 랜덤하게 길을 선택하는 것에 해당하며, 그러한 탐색을 몇 번이고 반복함으로써 A 지점에서 B 지점까지의 다양한 경로의 소요 시간 경험을 얻을 수 있습니다.

활용의 한 예로는, 지금까지 경험한 최선의 행동을 선택하는 방법이 있습니다. 최단 경로 학습의 경우에는 지금까지 지나온 (경험한) 경로 중에서 소요 시간이 가장 짧았던 경로를 선택하는 것이 활용에 해당합니다.

강화학습 수법의 큰 차이점 중 하나는 「탐색과 활용을 어떻게 수행할 것인가」라는 접근 방식의 차이입니다.

이후에 설명하듯이, 원시 몬테카를로법에서는 플레이아웃 (Playout)이라는 랜덤한 행동을 계속해서 선택하는 탐색을 수없이 수행하고, 탐색을 통해 얻은 경험으로부터 행동을 선택하는 활용을 수행합니다. 이 수법은 탐색을 완료한 뒤에 활용을 수행하는, 즉 「탐색과 활용을 완전히 독립적으로 수행한다」는 특징이 있습니다. 이 수법은 매우 폭넓은 경험을 얻을 수 있지만, 한편으로는 랜덤한 행동을 통해 얻는 경험은 게임의 본질적인 공략에는 별로 도움이 되지 않는 경우가 많기 때문에 효율이 나쁘다는 문제가 있습니다. 이는 서로가 거의 랜덤하게 두는 초보자끼리의 대국을 아무리 지켜봐도, 상급자끼리의 높은 수준의 대국에서 통용될 만한 좋은 경험을 거의 얻을 수 없는 점과 매우 닮아 있습니다.

이 문제를 해결하는 수법으로서, 지금까지 얻은 경험을 활용하면서 동시에 새로운 탐색을 섞어서 수행하는, 즉 「탐색과 활용을 병행하는」 수법이 있습니다. 이 수법의 한 예를 「최단 경로 학습」으로 설명하면, 교차로에서 다음과 같은 행동을 선택하는 탐색을 수행하는 것에 해당합니다.

• 기본적으로 (예를 들어 90%의 확률로) 지금까지 얻은 경험을 바탕으로 B 지점에 빠르게 도달할 수 있다고 생각되는 길을 선택한다 (활용 (Exploitation))
• 가끔 (예를 들어 10%의 확률로) 무작위로 길을 선택한다 (탐색 (Exploration))

위의 「가끔 무작위로 길을 선택하는 것」을 현실 세계에 비유하면, 가끔 변덕을 부려 평소에는 다니지 않는 길을 선택하는 것에 해당합니다. 그 결과, 운이 좋으면 지름길을 찾아 더 짧은 경로를 발견할 수 있을지도 모르지만, 운이 나쁘면 멀리 돌아가게 될 수도 있습니다. 또한, 멀리 돌아가게 된 경우라도 「그 길은 멀리 돌아가는 길이다」라는 경험을 얻을 수 있기 때문에 그 탐색이 완전히 헛수고가 되는 것은 아닙니다. 인간과 마찬가지로 강화학습 (RL)에서도 「실패로부터 배우는 것」은 매우 중요합니다.

이처럼 탐색과 활용을 균형 있게 병용하며 경험을 쌓음으로써, 탐색과 활용을 독립적으로 수행할 때보다 효율적으로 학습을 진행할 수 있게 되지만, 균형이 맞지 않으면 역효과가 나는 문제가 있습니다. 예를 들어 위의 무작위 길을 선택하는 확률을 99%와 같이 매우 크게 설정하면, 무작위 선택만을 수행하는 경우와 거의 다를 바 없게 됩니다. 반대로 0.01%와 같이 매우 작은 값으로 설정하면, 대부분의 탐색에서 그때까지의 경험 중 최단 루트를 선택하게 되므로, 탐색을 통해 새로운 경험을 거의 얻을 수 없게 됩니다.

탐색과 활용을 어떻게 수행할지는 강화학습의 매우 중요한 테마이며, 질 좋은 경험을 효율적으로 얻기 위한 다양한 수법들이 고안되어 있습니다. 그러한 수법 중 일부에 대해서는 향후 기사에서 소개할 예정입니다.

아래는 〇× 게임에서의 위 용어들에 대한 구체적인 예시를 정리한 표입니다. 탐색과 활용에 대해서는 강화학습 수법에 따라 크게 다르기 때문에 생략했습니다.

위의 설명으로부터, 지금까지의 기사에서 구현한 미니맥스법 (Minimax)이나 αβ 탐색법 (Alpha-Beta Pruning)을 이용한 AI 함수도 위의 표에 나온 용어로 설명한 것과 유사한 처리를 하고 있으므로 강화학습의 일종이 아닌가 생각한 분도 계시겠지만, 일반적으로 미니맥스법이나 αβ 탐색법은 강화학습으로 간주되지 않습니다. 그 이유에 대해 설명하겠습니다.

강화학습의 「방책 (Policy)」이 「각 행동을 선택할 확률」로 표현되는 것에서 알 수 있듯이, 강화학습은 확률을 이용한 계산을 수행하는 알고리즘입니다. 또한 강화학습에서는 환경의 내부 구조를 모두 파악하여 책상 위에서 분석하는 것이 아니라, 환경에 대해 실제로 행동을 일으킨 결과로 얻어진 상태나 보상을 관측하여 학습함으로써 최적해에 가까운 근사해를 계산하는, 이전 기사에서 설명한 휴리스틱 (Heuristic)한 알고리즘입니다.

그에 반해 미니맥스법이나 αβ 탐색법은 확률을 사용하지 않으며, 계산을 수행할 수 있다면 확률에 의존하지 않는 확정적인 최적해를 반드시 도출할 수 있는, 이전 기사에서 설명한 연역법에 의한 알고리즘입니다.

위의 차이를 「A 지점에서 B 지점까지의 최단 경로를 찾는」 문제로 설명하면 다음과 같습니다.

• 강화학습 (Reinforcement Learning) 기법: 지도를 보지 않고 A 지점에서 B 지점까지 다양한 경로로 걷는 경험을 쌓음으로써 최단 경로로 보이는 경로를 찾는 접근 방식에 해당한다. 경험을 쌓으면 쌓을수록 소요 시간이 짧은 경로를 찾을 수 있지만, 그 경로가 정말 최단 경로라는 보장은 없다.
• 미니맥스 (Minimax) 법 기법: 수중에 있는 지도를 보고 A 지점에서 B 지점까지의 모든 경로의 소요 시간을 책상 위에서 계산함으로써 최단 경로를 찾는 접근 방식에 해당한다. 모든 경로의 소요 시간을 계산할 수 있다면 반드시 최단 경로를 찾을 수 있지만, 경로의 수가 방대해지면 계산에 시간이 너무 많이 걸려 현실적인 시간 내에 답을 찾지 못하는 경우가 있다.

다음으로, 원시 몬테카를로 (Primitive Monte Carlo) 법에 의한 〇× 게임의 강화학습과 강화학습 용어의 관계에 대해 설명하겠습니다.

원시 몬테카를로 법에 의한 강화학습은 일반적인 강화학습과 비교했을 때 다양한 조건이 한정되어 있습니다. 그렇기 때문에 일반적인 강화학습에서 필요로 하는 고도의 수학적 지식을 필요로 하지 않는다는 특징이 있으며, 그 성질 덕분에 강화학습을 배울 때 첫 번째 소재로 자주 다루어집니다.

에이전트 (Agent), 환경 (Environment), 행동 (Action), 보상 (Reward)에 관해서는 앞서 설명한 것과 동일합니다.

아래의 원시 몬테카를로 법 알고리즘은, 절차 1이 랜덤한 행동을 계속 선택함으로써 경험을 얻는 「탐색 (Exploration)」에 해당하며, 절차 2가 얻은 경험으로부터 행동을 선택하는 「활용 (Exploitation)」에 해당합니다. 또한, 절차 1-1에서 수행하는 한 번의 플레이아웃 (Playout) 작업이 강화학습에서의 1회 「에피소드 (Episode)」에 해당합니다.

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

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

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

• 가장 높은 플레이아웃 평가치가 계산된 국면이 되는 합법수를 최선수로 한다.

참고로, 위의 「플레이아웃의 평가치」는 지난 기사에서 설명한 것처럼 무승부를 0.5승으로 계산했을 경우의 승률을 나타냅니다.

위의 절차 1에서 알 수 있듯이, 원시 몬테카를로 법에서는 플레이아웃이라는 탐색을 몇 번이고 수행하지만, 탐색을 수행할 때 그 이전에 수행했던 탐색의 지식을 이용(활용)하지는 않습니다. 절차 2의 「활용」은 절차 1의 「탐색」 작업이 완전히 완료된 후에 이루어지기 때문에, 원시 몬테카를로 법에는 「탐색과 활용을 독립적으로 수행한다」는 강한 특징이 있습니다.

「현재 국면에서 합법수를 두었을 때의 모든 국면」이라는 표기는 길기 때문에, 이번 기사에서는 이후 이 국면들을 「다음 국면」이라고 표기하겠습니다.

원시 몬테카를로 법에서는 다음 국면에 대해 미리 정해둔 횟수 또는 제한 시간이 올 때까지 랜덤한 착수를 계속하는 플레이아웃을 수행합니다. 따라서 원시 몬테카를로 법에서 국면을 나타내는 「상태 (State)」와 행동의 방침을 나타내는 「방책 (Policy)」의 관계는 아래의 표와 같으며, 이 방책에 따라 「탐색」이 이루어집니다.

원시 몬테카를로 법은 탐색과 활용이 독립되어 있기 때문에, 「모든 탐색에서 항상 위의 동일한 방책이 계속 사용된다」는 특징이 있습니다.

강화학습에서의 활용은 탐색을 통해 얻은 경험으로부터 누적 보상의 기대치를 최대화하는 방책을 구하는 것이며, 원시 몬테카를로 법에서의 활용은 다음과 같습니다.

「다음 국면의 플레이아웃 평가치가 가장 높아지는 합법수를 선택한다」

위의 내용을 강화학습 용어로 바꾸면 다음과 같습니다.

현재 국면에서의 방책을 다음과 같이 개선한다.

• 다음 국면의 플레이아웃 평가치가 가장 높아지는 합법수를 선택할 확률을 1 (100 %)로 한다. 그러한 합법수가 복수 존재할 경우에는 그 합법수들을 선택할 확률을 균등하게 배분한다.
• 그 외의 합법수를 선택할 확률을 0 (0 %)로 한다.

항상 같은 행동을 선택하는 방책을 결정론적 방책 (Deterministic policy), 확률에 따라 행동을 선택하는 방책을 확률론적 방책 (Stochastic policy)이라고 부릅니다.

참고로, 특정 행동을 선택할 확률을 100 %로 설정함으로써 확률론적 방책을 사용하여 결정론적 방책을 표현할 수 있으므로, 강화학습에서의 방책은 확률론적 방책으로 표현하는 것이 일반적이며, 본 기사의 방책 또한 확률론적 방책을 사용합니다.

위의 방책을 통해 누적 보상의 기대치(Expected Value)가 최대화됨을 설명하겠습니다.

앞서 설명한 바와 같이, 현재 국면에서 결판이 날 때까지의 일련의 행동(하나의 에피소드 (Episode))을 통해 얻은 누적 보상(즉시 보상의 합계)은 아래 표와 같이 무승부를 0.5승으로 가정했을 때의 〇의 승패 결과에 따른 보상으로 설정합니다. 이는 현재 국면에 국한되지 않고 임의의 국면에서 플레이아웃 (Playout)을 수행했을 때 얻을 수 있는 누적 보상에서도 마찬가지입니다.

원시 몬테카를로법 (Vanilla Monte Carlo Method)에서는 다음 국면에 대해 여러 번의 플레이아웃을 수행한 결과로 얻은 플레이아웃 평가치를 활용하지만, 이전 기사에서 설명했듯이 그 플레이아웃 평가치를 계산하는 식은 「누적 보상의 평균값」을 계산하는 식 그 자체입니다. 따라서 원시 몬테카를로법에서의 활용은, 다음 국면 중에서 탐색 (Search, 플레이아웃)을 통해 가장 높은 누적 보상의 평균값이 얻어진 합법수를 선택하는 처리를 수행합니다.

플레이아웃에서는 무작위로 합법수를 선택하므로, 플레이아웃을 통해 얻어지는 누적 보상을 확률 변수 $X$로 나타내면, 누적 보상의 기대치는 아래 식과 같이 표현됩니다.

$E[X] = 0 × P(X=0) + 0.5 × P(X=0.5) + 1 × P(X=1)$

단, $P(X=x)$는 플레이아웃을 통해 누적 보상 $x$가 얻어질 확률을 나타냅니다. 확률에 대해 잊으셨다면 이전 기사를 복습해 주세요.

$P(X=x)$는 확률을 나타내므로 0 이상 1 이하의 값이며, 따라서 누적 보상의 기대치는 반드시 유한한 값이 됩니다. 또한, 원시 몬테카를로법에서는 모든 탐색 (플레이아웃)이 매번 동일한 방책으로 완전히 독립적으로 수행되기 때문에, 누적 보상은 「어떤 확률 분포로부터 무작위 복원 추출된 데이터」로 간주할 수 있습니다. 이 성질 덕분에 이전 기사에서 설명한 대수의 법칙 (Law of Large Numbers)을 적용할 수 있으며, 플레이아웃을 여러 번 수행했을 때 얻어지는 누적 보상의 평균값은 플레이아웃 횟수를 늘리면 늘릴수록 이론적인 값인 누적 보상의 기대치에 가까워지게 됩니다.

위의 내용으로부터, 플레이아웃 횟수를 늘리면 늘릴수록 다음 국면의 플레이아웃 평가치가 가장 높아지는 합법수를 선택한다는 방책이, 누적 보상의 기대치를 최대화하는 최선의 방책과 일치할 확률이 매우 높아진다는 것이 증명되었습니다.

이와 같이 원시 몬테카를로법에서의 활용의 타당성은 대수의 법칙만으로 심플하게 설명할 수 있습니다. 이는 탐색과 활용을 독립적으로 수행하기 때문에 성립하는 큰 장점입니다. 반면, 탐색과 활용을 병행하는 일반적인 강화학습 (Reinforcement Learning)의 경우에는 더 복잡한 수학적 개념을 사용할 필요가 있습니다. 이러한 고도의 기법들에 대해서는 향후 기사에서 설명할 예정입니다.

원시 몬테카를로법을 직관적인 말로 요약하면 다음과 같습니다.

• 어떤 합법수가 좋은지 전혀 감이 잡히지 않으므로, 무작위로 착수하는 플레이아웃을 반복함으로써 경험을 쌓는다 (탐색)
• 이때 〇의 승리를 1, 무승부를 0.5, ×의 승리를 0으로 보상을 설정하여, 얻어진 경험의 좋고 나쁨을 수치화한다
• 최종적으로 다음 국면의 누적 보상 평균 (플레이아웃 평가치)이 가장 높아지는 합법수를 가장 이기기 쉬운 합법수로 간주하고 선택한다 (활용)

원시 몬테카를로법의 큰 문제 중 하나는 탐색에서 이용하는 방책이 항상 동일하기 때문에, 탐색에서 얻은 경험을 탐색이 모두 종료될 때까지 활용할 수 없다는 점입니다. 인간이 학습을 수행할 때는 얻은 경험을 즉시 다음 탐색에 활용하는 것이 일반적이지 않나요? 예를 들어 큰 실수를 했을 경우, 다음 행동에서는 즉시 그 실수를 반복하지 않는 행동을 선택하는 것이 일반적이지만, 원시 몬테카를로법에서는 항상 동일한 방책으로 탐색을 수행하기 때문에 몇 번이고 큰 실수를 반복하는 탐색을 수행할 가능성이 높습니다.

또 다른 큰 문제로는 원시 몬테카를로법이 현재 국면에 대한 방책만을 계산한다는 점입니다. AI의 목적은 강한 상대에 대해 승리할 수 있는 합법수를 선택하는 것이지만, 플레이아웃을 통해 얻어지는 경험은 무작위 착수를 수행한 대국이기 때문에 얻어진 경험의 대부분은 약한 상대와의 대전 결과가 됩니다. 이 문제를 해결하기 위해서는 현재 국면 이외의 국면 방책을 얻어진 경험을 통해 갱신함으로써, 다음 탐색을 수행할 때 최선의 수에 가까운 합법수를 선택할 확률을 높일 필요가 있습니다.

이러한 문제점들을 해결하기 위해서는 현재의 국면뿐만 아니라 플레이아웃 (Playout) 도중에 통과한 다양한 국면의 방책도 동시에 기록·갱신해 나가는 메커니즘이 필요합니다. 탐색을 통해 얻은 경험을 다음 탐색에 즉시 피드백할 수 있다면, 탐색을 진행함으로써 더욱 최선의 수에 가까운 정밀도 높은 합법수를 선택할 수 있게 됩니다. 그러한 더욱 효율적이고 고도화된 강화학습 (Reinforcement Learning) 기법에 대해서는 다음 회차 이후의 기사에서 소개하겠습니다.

원시 몬테카를로법 (Raw Monte Carlo Method)으로 〇× 게임의 착수를 선택하는 현재의 ai_pmc와 ai_pmc2가 수행하는 처리에 몇 가지 문제점이 있다는 것을 깨달았으므로 수정하기로 합니다.

현재 처리의 문제점에 대해 설명하겠습니다.

아래는 원시 몬테카를로법 알고리즘의 재게시입니다.

• 현재의 국면에서 합법수를 착수한 모든 국면에 대하여 아래의 계산을 수행한다

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

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

• 가장 높은 플레이아웃 평가치가 계산된 국면이 되는 합법수를 최선의 수로 한다

위의 절차 1은 다음 국면(현재의 국면에서 합법수를 착수한 모든 국면)에 대하여 특정 횟수 또는 제한 시간까지 플레이아웃을 수행한다는 것이지만, 현재의 ai_pmc와 ai_pmc2는 이전 기사에서 설명한 제한 시간에 관한 처리 문제로 인해, 위와는 약간 다른 아래의 알고리즘으로 플레이아웃을 수행하고 있습니다.

현재의 국면으로부터 「특정 횟수」 또는 「특정 시간이 경과할 때까지」 플레이아웃을 수행하고, 처음 착수를 수행한 합법수마다 플레이아웃 결과의 집계를 수행한다.

위의 알고리즘은 플레이아웃 횟수가 많아지면 많아질수록 대수의 법칙 (Law of Large Numbers)에 의해 첫 번째 착수가 합법수 중에서 균등하게 선택되게 되므로, 플레이아웃 횟수가 많은 경우에는 원래의 원시 몬테카를로법 알고리즘과 거의 동일한 처리가 수행됩니다. 반대로 말하면, 플레이아웃 횟수가 적은 경우에는 첫 번째 착수에서 각각의 합법수가 선택되는 비율에 편차가 생기는 문제가 있습니다. 나아가 이전 기사에서 설명한 것처럼, 플레이아웃 횟수를 줄이면 특정 합법수가 선택되지 않는 경우가 발생하는 문제도 있습니다.

원시 몬테카를로법에서 플레이아웃을 수행하는 대상은 현재의 국면이 아니라 다음 국면(현재의 국면에서 합법수를 착수한 모든 국면)입니다.

그에 반해 현재의 ai_pmc와 ai_pmc2에서는 현재의 국면으로부터 몇 번이고 플레이아웃을 수행하고, 그 결과를 처음 착수를 수행한 합법수로 분류하여 집계하는 처리를 수행하고 있기 때문에, 원시 몬테카를로법이 「플레이아웃을 현재의 국면으로부터 수행한다」는 알고리즘처럼 보여버리는 문제가 있습니다.

Marubatsu 클래스의 playout 메서드는 여러 번의 플레이아웃 처리와 다음 국면별 플레이아웃 결과의 집계 처리를 수행하지만, 이는 메서드의 이름인 「플레이아웃」 처리라기보다는 원시 몬테카를로법 그 자체의 처리이기 때문에, 메서드의 이름과 처리 내용이 일치하지 않는다는 문제가 있습니다.

또한, 현재의 playout 메서드는 원시 몬테카를로법의 처리를 수행하도록 구현되어 있기 때문에, 플레이아웃 처리를 필요로 하는 다른 강화학습 알고리즘에서 playout 메서드를 이용할 수 없다는 문제가 있습니다. 예를 들어 향후 기사에서 소개할 몬테카를로 트리 탐색 (Monte Carlo Tree Search) 처리에서는 원시 몬테카를로법과 다른 상황에서 플레이아웃을 수행하기 때문에, 현재의 playout 메서드를 그대로 이용할 수 없습니다.

위와 같은 이유로, 다음과 같은 수정을 진행하기로 합니다.

• Marubatsu 클래스의 playout 메서드가 1회의 플레이아웃 처리만을 수행하도록 한다
• 제한 시간 처리는 playout에서 수행하지 않는다
• ai_pmc와 ai_pmc2가 본래의 원시 몬테카를로법 알고리즘으로 처리를 수행한다
• Marubatsu 클래스의 playout 메서드에서 수행하던 제한 시간 처리나 플레이아웃 결과의 집계 처리를 ai_pmc와 ai_pmc2에서 수행한다

원시 몬테카를로법에서는 현재의 국면으로부터 특정 합법수를 착수한 국면에 대하여 플레이아웃을 수행합니다. 따라서 Marubatsu 클래스의 playout 메서드에 현재의 국면에 대하여 착수할 합법수를 대입하는 가인수 (Formal Argument)를 추가하기로 하고, 다음과 같이 수정하겠습니다.

• 가인수 move

현재 국면에 대해 수행할 착수를 대입한다 - 플레이아웃 (Playout) 처리는 한 번만 수행하고, 승패 결과를 나타내는 값을 반환값으로 반환하도록 한다

• 현재의 playout 메서드와 마찬가지로, playout 메서드의 처리에 의해 국면의 상황이 변화하지 않도록 한다. 구체적인 방법에 대해 잊어버린 분은 이전 기사를 복습할 것

아래는 그와 같이 playout 메서드를 수정한 프로그램입니다. 또한, 대폭적인 수정을 수행하므로 수정 사항은 생략합니다.

• 4행: 가인수 (Formal Argument)를 첫 번째 착수를 대입하는 move로만 한다. 또한, 향후 기사에서 소개할 몬테카를로 트리 탐색 (Monte Carlo Tree Search)에서는 현재 국면에서 플레이아웃을 수행하는 경우가 있으므로, 기본값을 None으로 한 기본 인자 (Default Argument)로 설정하여, None인 경우에는 현재 국면에서 플레이아웃을 수행하는 것으로 한다.
• 5행 앞에 있었던 result의 초기화나 제한 시간에 관한 처리를 삭제한다. 또한, 5행의 현재 게임판 정보를 저장하는 처리는 기존과 동일하다.
• 6~8행: 현재 차례, 수(手), 상태를 로컬 변수에 대입한다.
• 9~17행: 승부가 날 때까지 반복 처리를 수행한다.
• 10, 11행: move가 None인 경우에 다음 착수가 무작위로 선택되도록 함으로써, 가인수 move에 처음에 착수할 합법수가 대입되어 있었을 경우에는 처음에 그 합법수가 착수되도록 한다.
• 13~16행: move의 착수를 수행하고 게임의 상태를 계산한다. 이 부분은 기존 playout의 처리와 동일하다.
• 17행: 다음 착수가 무작위로 선택되도록 하기 위해 move에 None을 대입한다.
• 18행: 게임판을 플레이아웃을 수행하기 전의 상태로 되돌린다.
• 19행: 게임의 결과를 반환값으로 반환한다

1 from marubatsu import Marubatsu
2 import random
3
...

행 번호가 없는 프로그램