mcts
1.0.0
Neste tutorial iremos explicar o algoritmo Monte Carlo Tree Search e cada parte do código. Recentemente aplicamos o MCTS para desenvolver nosso jogo.
O código é geral e pressupõe apenas familiaridade com Python básico. Nós explicamos isso em relação ao nosso jogo. Se quiser utilizá-lo em seu projeto ou jogo, você terá que modificar ligeiramente as funções que mencionei abaixo.
Aqui está o link da playstore para o jogo: Sudo Tic Tac Toe.
As regras do nosso jogo (modo 1) são as seguintes:
Como você deve ter visto, este jogo tem um fator de ramificação muito alto. No primeiro movimento, todo o tabuleiro está vazio. Portanto, existem 81 espaços vazios. Para o primeiro turno tem 81 movimentos possíveis. Para o segundo turno aplicando a regra 4 tem 8 ou 9 movimentos possíveis.
Para os primeiros 2 movimentos isto resulta em 81*9 = 729 combinações possíveis. Assim, o número de combinações possíveis aumenta à medida que o jogo avança, resultando num elevado factor de ramificação. Para ambos os modos do nosso jogo o fator de ramificação é muito alto. Para jogos com fator de ramificação tão alto não é possível aplicar o algoritmo minimax. O algoritmo MCTS funciona para esse tipo de jogo.
Além disso, como você deve ter visto ao jogar, o tempo que a IA leva para fazer um movimento é de apenas um segundo. Assim, o MCTS funciona rápido. MCTS foi aplicado a ambos os modos de jogo.
Abaixo demonstramos o código MCTS em Python. Primeiro precisamos importar numpy e defaultdict.
import numpy as np
from collections import defaultdictDefina a classe MCTS conforme mostrado abaixo.
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 ()
returnA classe consiste nas seguintes funções de membro. Todas as funções abaixo são funções membro, exceto a função main().
def untried_actions ( self ):
self . _untried_actions = self . state . get_legal_actions ()
return self . _untried_actionsRetorna a lista de ações não tentadas de um determinado estado. Para o primeiro turno do nosso jogo existem 81 ações possíveis. Para o segundo turno é 8 ou 9. Isso varia em nosso jogo.
def q ( self ):
wins = self . _results [ 1 ]
loses = self . _results [ - 1 ]
return wins - losesRetorna a diferença entre vitórias e derrotas
def n ( self ):
return self . _number_of_visitsRetorna o número de vezes que cada nó é visitado.
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 A partir do estado atual, o próximo estado é gerado dependendo da ação executada. Nesta etapa, todos os estados possíveis são anexados ao array children e o child_node é retornado. Os estados que são possíveis a partir do estado atual são todos anexados ao array children e o child_node correspondente a este estado é retornado.
def is_terminal_node ( self ):
return self . state . is_game_over ()Isto é usado para verificar se o nó atual é terminal ou não. O nó terminal é alcançado quando o jogo termina.
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 ()A partir do estado atual, todo o jogo é simulado até que haja um resultado para o jogo. Este resultado do jogo é retornado. Por exemplo, se resultar numa vitória, o resultado será 1. Caso contrário, será -1 se resultar numa derrota. E é 0 se houver empate. Se todo o jogo for simulado aleatoriamente, ou seja, a cada turno o movimento é selecionado aleatoriamente entre um conjunto de movimentos possíveis, é chamado de playout leve.
def backpropagate ( self , result ):
self . _number_of_visits += 1.
self . _results [ result ] += 1.
if self . parent :
self . parent . backpropagate ( result )Nesta etapa todas as estatísticas dos nós são atualizadas. Até que o nó pai seja alcançado, o número de visitas para cada nó é incrementado em 1. Se o resultado for 1, ou seja, resultou em uma vitória, então a vitória é incrementada em 1. Caso contrário, se o resultado for uma perda, então a perda é incrementado em 1.
def is_fully_expanded ( self ):
return len ( self . _untried_actions ) == 0Todas as ações são exibidas em _untried_actions, uma por uma. Quando fica vazio, ou seja, quando o tamanho é zero, ele está totalmente expandido.
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 )]Depois de totalmente expandida, esta função seleciona o melhor filho do array filhos. O primeiro termo da fórmula corresponde à exploração e o segundo termo corresponde à exploração.
def rollout_policy ( self , possible_moves ):
return possible_moves [ np . random . randint ( len ( possible_moves ))]Seleciona aleatoriamente um movimento entre movimentos possíveis. Este é um exemplo de reprodução aleatória.
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_nodeSeleciona o nó para executar a implementação.
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. )Esta é a melhor função de ação que retorna o nó correspondente ao melhor movimento possível. A etapa de expansão, simulação e retropropagação são realizadas pelo código acima.
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 Esta é a função main(). Inicialize o nó raiz e chame a função best_action para obter o melhor nó. Esta não é uma função membro da classe. Todas as outras funções são funções membro da classe.
O MCTS consiste em 4 etapas:
A ideia é continuar selecionando os melhores nós filhos até chegarmos ao nó folha da árvore. Uma boa maneira de selecionar esse nó filho é usar a fórmula UCT (Upper Confidence Bound aplicado às árvores):
wi/ni + c*sqrt(t)/ni
wi = número de vitórias após o i-ésimo movimento
ni = número de simulações após o i-ésimo movimento
c = parâmetro de exploração (teoricamente igual a √2)
t = número total de simulações para o nó pai
Quando não é mais possível aplicar UCT para encontrar o nó sucessor, ele expande a árvore do jogo anexando todos os estados possíveis do nó folha.
Após a expansão, o algoritmo escolhe um nó filho arbitrariamente e simula o jogo inteiro a partir do nó selecionado até atingir o estado resultante do jogo. Se os nós forem escolhidos aleatoriamente durante o jogo, isso é chamado de jogo leve. Você também pode optar por um jogo pesado escrevendo heurísticas de qualidade ou funções de avaliação.
Quando o algoritmo chega ao final do jogo, ele avalia o estado para descobrir qual jogador ganhou. Ele percorre para cima até a raiz e aumenta a pontuação de visita para todos os nós visitados. Ele também atualiza a pontuação de vitórias para cada nó se o jogador daquela posição tiver vencido o playout.
Se você planeja fazer seu próprio jogo, terá que pensar nas seguintes questões.
Sudo Tic Tac Toe
Se você tiver alguma dúvida ou sugestão, não hesite em nos contatar em [email protected]
