mcts
1.0.0
이 튜토리얼에서는 몬테카를로 트리 검색 알고리즘과 코드의 각 부분을 설명합니다. 최근에는 MCTS를 적용하여 게임을 개발했습니다.
코드는 일반적이며 기본 Python에 익숙하다고 가정합니다. 우리는 우리 게임과 관련하여 그것을 설명했습니다. 프로젝트나 게임에 사용하려면 아래에 언급한 기능을 약간 수정해야 합니다.
게임 플레이스토어 링크는 다음과 같습니다: Sudo Tic Tac Toe.
우리 게임(모드 1)의 규칙은 다음과 같습니다.
보시다시피 이 게임은 분기 요소가 매우 높습니다. 첫 번째 이동의 경우 전체 보드가 비어 있습니다. 따라서 81개의 빈 자리가 있습니다. 첫 번째 턴에는 81개의 가능한 이동이 있습니다. 두 번째 턴에는 규칙 4를 적용하여 8개 또는 9개의 가능한 이동이 있습니다.
처음 2개 이동의 경우 81*9 = 729개의 가능한 조합이 생성됩니다. 따라서 게임이 진행됨에 따라 가능한 조합의 수가 증가하여 분기 요인이 높아집니다. 우리 게임의 두 모드 모두에서 분기 계수가 매우 높습니다. 이러한 높은 분기 요소를 가진 게임의 경우 minimax 알고리즘을 적용하는 것이 불가능합니다. MCTS 알고리즘은 이러한 종류의 게임에 작동합니다.
또한 게임을 플레이하면서 알 수 있듯이 AI가 움직이는 데 걸리는 시간은 약 1초에 불과합니다. 따라서 MCTS는 빠르게 실행됩니다. MCTS는 게임의 두 모드 모두에 적용되었습니다.
아래에서는 Python의 MCTS 코드를 보여줍니다. 먼저 numpy와 defaultdict를 가져와야 합니다.
import numpy as np
from collections import defaultdict아래와 같이 MCTS 클래스를 정의합니다.
class MonteCarloTreeSearchNode ():
def __init__ ( self , state , parent = None , parent_action = None ):
self . state = state
self . parent = parent
self . parent_action = parent_action
self . children = []
self . _number_of_visits = 0
self . _results = defaultdict ( int )
self . _results [ 1 ] = 0
self . _results [ - 1 ] = 0
self . _untried_actions = None
self . _untried_actions = self . untried_actions ()
return클래스는 다음과 같은 멤버 함수로 구성됩니다. 아래의 모든 함수는 main() 함수를 제외한 멤버 함수입니다.
def untried_actions ( self ):
self . _untried_actions = self . state . get_legal_actions ()
return self . _untried_actions특정 상태에서 시도되지 않은 작업 목록을 반환합니다. 게임의 첫 번째 턴에는 81가지 가능한 행동이 있습니다. 두 번째 턴의 경우 8 또는 9입니다. 이는 게임에 따라 다릅니다.
def q ( self ):
wins = self . _results [ 1 ]
loses = self . _results [ - 1 ]
return wins - loses승리 - 패배의 차이를 반환합니다.
def n ( self ):
return self . _number_of_visits각 노드를 방문한 횟수를 반환합니다.
def expand ( self ):
action = self . _untried_actions . pop ()
next_state = self . state . move ( action )
child_node = MonteCarloTreeSearchNode (
next_state , parent = self , parent_action = action )
self . children . append ( child_node )
return child_node 현재 상태에서 수행되는 작업에 따라 다음 상태가 생성됩니다. 이 단계에서는 가능한 모든 상태가 하위 배열에 추가되고 child_node가 반환됩니다. 현재 상태에서 가능한 상태는 모두 children 배열에 추가되고 이 상태에 해당하는 child_node가 반환됩니다.
def is_terminal_node ( self ):
return self . state . is_game_over ()현재 노드가 터미널인지 여부를 확인하는 데 사용됩니다. 게임이 끝나면 터미널 노드에 도달합니다.
def rollout ( self ):
current_rollout_state = self . state
while not current_rollout_state . is_game_over ():
possible_moves = current_rollout_state . get_legal_actions ()
action = self . rollout_policy ( possible_moves )
current_rollout_state = current_rollout_state . move ( action )
return current_rollout_state . game_result ()현재 상태에서 게임 결과가 나올 때까지 전체 게임을 시뮬레이션합니다. 이 게임 결과가 반환됩니다. 예를 들어 승리하면 결과는 1입니다. 그렇지 않으면 패배하면 -1입니다. 그리고 동점이면 0이 됩니다. 전체 게임이 무작위로 시뮬레이션되는 경우, 즉 각 턴에서 가능한 이동 세트 중에서 이동이 무작위로 선택되는 경우 이를 라이트 플레이아웃이라고 합니다.
def backpropagate ( self , result ):
self . _number_of_visits += 1.
self . _results [ result ] += 1.
if self . parent :
self . parent . backpropagate ( result )이 단계에서는 노드에 대한 모든 통계가 업데이트됩니다. 상위 노드에 도달할 때까지 각 노드의 방문 횟수는 1씩 증가합니다. 결과가 1이면 승리이며, 승리는 1씩 증가합니다. 그렇지 않은 경우 결과가 패배이면 손실입니다. 1씩 증가합니다.
def is_fully_expanded ( self ):
return len ( self . _untried_actions ) == 0모든 작업은 _untried_actions에서 하나씩 팝됩니다. 비어 있게 되면, 즉 크기가 0이 되면 완전히 확장됩니다.
def best_child ( self , c_param = 0.1 ):
choices_weights = [( c . q () / c . n ()) + c_param * np . sqrt (( 2 * np . log ( self . n ()) / c . n ())) for c in self . children ]
return self . children [ np . argmax ( choices_weights )]완전히 확장되면 이 함수는 하위 배열 중에서 가장 좋은 하위 항목을 선택합니다. 공식의 첫 번째 항은 착취에 해당하고 두 번째 항은 탐색에 해당합니다.
def rollout_policy ( self , possible_moves ):
return possible_moves [ np . random . randint ( len ( possible_moves ))]가능한 이동 중에서 무작위로 이동을 선택합니다. 이것은 무작위 재생의 예입니다.
def _tree_policy ( self ):
current_node = self
while not current_node . is_terminal_node ():
if not current_node . is_fully_expanded ():
return current_node . expand ()
else :
current_node = current_node . best_child ()
return current_node롤아웃을 실행할 노드를 선택합니다.
def best_action ( self ):
simulation_no = 100
for i in range ( simulation_no ):
v = self . _tree_policy ()
reward = v . rollout ()
v . backpropagate ( reward )
return self . best_child ( c_param = 0. )이것은 가능한 최선의 움직임에 해당하는 노드를 반환하는 최선의 행동 함수입니다. 확장, 시뮬레이션 및 역전파 단계는 위의 코드에 의해 수행됩니다.
def get_legal_actions ( self ):
'''
Modify according to your game or
needs. Constructs a list of all
possible states from current state.
Returns a list.
''' def is_game_over ( self ):
'''
Modify according to your game or
needs. It is the game over condition
and depends on your game. Returns
true or false
''' def game_result ( self ):
'''
Modify according to your game or
needs. Returns 1 or 0 or -1 depending
on your state corresponding to win,
tie or a loss.
''' def move ( self , action ):
'''
Modify according to your game or
needs. Changes the state of your
board with a new value. For a normal
Tic Tac Toe game, it can be a 3 by 3
array with all the elements of array
being 0 initially. 0 means the board
position is empty. If you place x in
row 2 column 3, then it would be some
thing like board[2][3] = 1, where 1
represents that x is placed. Returns
the new state after making a move.
''' def main ():
root = MonteCarloTreeSearchNode ( state , None , action )
selected_node = root . best_action ()
return 이것이 main() 함수입니다. 루트 노드를 초기화하고 best_action 함수를 호출하여 최상의 노드를 얻습니다. 이것은 클래스의 멤버 함수가 아닙니다. 다른 모든 함수는 클래스의 멤버 함수입니다.
MCTS는 4단계로 구성됩니다.
아이디어는 트리의 리프 노드에 도달할 때까지 가장 좋은 자식 노드를 계속 선택하는 것입니다. 이러한 하위 노드를 선택하는 좋은 방법은 UCT(트리에 적용되는 신뢰 상한) 공식을 사용하는 것입니다.
wi/ni + c*sqrt(t)/ni
wi = i번째 이동 후 승리 횟수
ni = i번째 이동 후의 시뮬레이션 수
c = 탐사 매개변수(이론적으로 √2와 동일)
t = 상위 노드에 대한 총 시뮬레이션 수
후속 노드를 찾기 위해 더 이상 UCT를 적용할 수 없으면 리프 노드에서 가능한 모든 상태를 추가하여 게임 트리를 확장합니다.
확장 후 알고리즘은 임의로 하위 노드를 선택하고 게임의 결과 상태에 도달할 때까지 선택한 노드에서 전체 게임을 시뮬레이션합니다. 플레이 아웃 중에 노드가 무작위로 선택되는 경우 이를 라이트 플레이 아웃이라고 합니다. 품질 경험적 방법이나 평가 기능을 작성하여 대규모 플레이를 선택할 수도 있습니다.
알고리즘은 게임이 끝나면 상태를 평가하여 어떤 플레이어가 승리했는지 파악합니다. 이는 루트까지 위쪽으로 이동하고 방문한 모든 노드에 대한 방문 점수를 증가시킵니다. 또한 해당 포지션의 플레이어가 플레이아웃에서 승리한 경우 각 노드의 승리 점수를 업데이트합니다.
자신만의 게임을 만들 계획이라면 다음 질문에 대해 생각해 봐야 합니다.
스도 틱택토
질문이나 제안 사항이 있으시면 언제든지 [email protected]으로 문의해 주세요.
