mcts
1.0.0
В этом уроке мы объясним алгоритм поиска по дереву Монте-Карло и каждую часть кода. Недавно мы применили MCTS для разработки нашей игры.
Код является общим и предполагает только базовое знание Python. Мы объяснили это применительно к нашей игре. Если вы хотите использовать его для своего проекта или игры, вам придется немного изменить функции, которые я упомянул ниже.
Вот ссылка на игру в магазине: Sudo Tic Tac Toe.
Правила нашей игры (режим 1) следующие:
Как вы могли заметить, в этой игре очень высокий коэффициент ветвления. При первом ходе вся доска пуста. Итак, осталось 81 пустое место. Для первого хода у него есть 81 возможный ход. На второй ход, применяя правило 4, имеется 8 или 9 возможных ходов.
Для первых двух ходов получается 81*9 = 729 возможных комбинаций. Таким образом, количество возможных комбинаций увеличивается по ходу игры, что приводит к высокому коэффициенту ветвления. Для обоих режимов нашей игры коэффициент ветвления очень высок. Для игр с таким высоким коэффициентом ветвления невозможно применить минимаксный алгоритм. Алгоритм MCTS работает для таких игр.
Кроме того, как вы могли заметить, играя в игру, время, необходимое искусственному интеллекту для того, чтобы сделать ход, составляет всего около секунды. Таким образом, MCTS работает быстро. MCTS применен к обоим режимам игры.
Ниже мы демонстрируем код MCTS на Python. Сначала нам нужно импортировать 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 Из текущего состояния генерируется следующее состояние в зависимости от выполняемого действия. На этом этапе все возможные состояния добавляются к массиву 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 одно за другим. Когда он становится пустым, то есть когда размер равен нулю, он полностью расширяется.
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].
