monte carlo tree search em jogo da velha

introdução

Monte Carlo Tree Search, ou MCTS, é um algoritmo (ou família de algoritmos) utilizado para fazer busca em árvores que são particularmente grandes. Ao empregar a “aleatoriedade direcionada” comum aos métodos de Monte Carlo, o algoritmo resolve diversas dificuldades inerentes ao percurso de árvores gigantescas.

Em que situações um algoritmo como o MCTS é bem-vindo? Uma das aplicações mais famosas é na área de agentes inteligentes que jogam jogos. Usualmente nessas situações, modela-se as possíveis jogadas como uma árvore denominada árvore de jogo (ou game tree), de modo que a tarefa de “encontrar a melhor jogada” acaba se reduzindo a uma busca em árvore. Um exemplo:

Para decidir em que posição jogar, o jogador X deve considerar qual posição irá aumentar suas chances de vencer. Nós sabemos que as posições “4” e “8” são as melhores (são as únicas que lhe dão chance de ganhar), mas como o agente descobriria isso? Ele teria de expandir a árvore e observar que quando ele põe nessas posições, há mais possibilidades de vitória. Porém, é perceptível que essa árvore é grande - como percorrer isso tudo de forma eficiente? Felizmente, o que o MCTS nos permite fazer é justamente obter uma boa decisão sem ter que expandir a árvore inteira.

funcionamento

De forma bem informal, o que o algoritmo faz é muito parecido com o que muitos de nós fazemos enquanto estamos pensando na próxima jogada: analisar aos poucos a árvore de jogo procurando as decisões mais promissoras. É como se ele estivesse falando: “eu posso botar um X aqui, mas aí ele vai marcar um O aqui, e aí eu vou perder… então é melhor eu não botar o X aqui… onde eu boto então? vamos supôr que eu bote aqui…” e assim por diante. Basicamente, ele vai continuar fazendo isso até atingir algum gatilho que nós escolhemos - como um tempo máximo de execução.

O mais importante de entender de cara é que o objetivo do algoritmo é construir uma árvore de jogo. A cada iteração ele vai botar um nó novo na árvore, referente a uma decisão que pode ser tomada em algum momento do jogo (p.ex.: “jogador 1 bota X na posição 7”). O segredo é que o MCTS vai focar a construção nos caminhos que contém as decisões mais promissoras.

Mas o que significa uma decisão ser promissora? Significa duas coisas diferentes:

tomar essa decisão agora levará a mais vitórias no futuro (ela é uma boa decisão);
não analisamos muito a fundo as consequências dessa decisão (ela tem potencial).

Esses serão os dois fatores analisados na hora de escolher qual decisão será expandida (há uma forte similaridade com a noção de exploration vs. exploitation discutida em outros contextos).

Mais especificamente, cada nó de decisão possui dois atributos:

valor: um número que representa o quão atrativa é aquela dceisão. Um valor alto significa que a decisão é boa.
- no exemplo do jogo da velha, podemos modelar isso como “o quão próximo essa decisão me deixa de uma vitória”.
visitas: um número que representa quantas vezes aquela decisão já foi analisada. Se um nó tiver um número de visitas baixo (quando comparado ao resto da árvore, claro), significa que não demos muita atenção àquela decisão: isto é, ela tem potencial.

Uma coisa importante de notar nessa nossa modelagem do jogo da velha é que o atributo de valor tem de obrigatoriamente ser relativo a um jogador. Afinal, pra dizermos se uma decisão é boa, precisamos saber: boa pra quem? Uma decisão que é boa pra mim não é boa pra você, meu adversário. Portanto, nesta modelagem, cada nó de decisão deve ter atrelado a si mesmo um jogador. Observe a seguinte situação: vamos supôr que eu (jogador X) estou jogando contra você (jogador O), e você está usando o algoritmo do MCTS pra decidir como atuar. Digamos que você está prestes a ganhar o jogo:

Existem várias decisões que eu posso tomar a partir desse momento. Qual delas é a melhor? Pra mim, é bloquear a sua vitória! Portanto, o nó de valor mais alto é justamente o nó em que eu faço isso - apesar de ser você que está rodando o algoritmo.

Mas pra quê isso? Quando olharmos o algoritmo em si isso vai ficar mais claro, mas podemos fazer um argumento intuitivo: se o o algoritmo sempre atribuísse o valor do nó referente ao jogador inicial, ele estaria implicitamente dizendo que as partes da árvore em que o jogador adversário deixa ele ganhar são mais promissoras. E isso não é muito útil na realidade, porque faria o algoritmo ser muito otimista! É como se ele estivesse pensando: “eu vou botar um X aqui e aí só falta mais um pra eu ganhar! bom, ele pode me bloquear botando um O aqui, é claro. mas ele provavelmente não vai fazer isso! então vou botar um X aqui mesmo”. É fofo, mas irreal. O mundo é cruel, algoritmo…

A única coisa que faz sentido é esperar que os seus adversário joguem contra você, e portanto explorar a árvore levando isso em consideração. Não só no jogo da velha, mas em qualquer jogo com dois ou mais jogadores.

Voltando. A essa altura do campeonato é importante deixar claro que existem diversas variações pro método MCTS, e a que vamos abordar é uma das mais “padrão”. Nessa nossa abordagem, uma decisão é determinada promissora de acordo com a seguinte fórmula, denominada UCT (Upper Confidence Bound for Trees):

\[UCT = \underbrace{\frac{Q(i)}{N(i)}}_{\text{boa decisão}} + \underbrace{\sqrt{\frac{2 \ln N(j)}{N(i)}}}_{\text{decisão com potencial}}\]

tal que:

$j$ é o pai do nó $i$;
$Q(i)$ é o valor do nó $i$;
$N(i)$ é a quantidade de visitas do nó $i$.

Analisando com mais carinho, observamos que:

o primeiro termo, $\frac{Q(i)}{N(i)}$, calcula o “valor médio” do nó $i$, dividindo seu valor pela quantidade de visitas - se ele teve muitas visitas com valor alto, esse valor médio também será alto. Portanto, ele está relacionado com a nossa noção de boa decisão.
o segundo termo, $\sqrt{\frac{2 \ln N(j)}{N(i)}}$, utiliza as visitas do nó $i$ em relação às visitas de seu pai, para retornar um valor alto quando a quantidade de visitas do nó $i$ for baixa em relação às do seu pai (p. ex.: seu pai foi visitado 100 vezes mas o nó $i$ foi visitado apenas 2. isso retornaria um valor mais alto do que o dos irmãos de $i$).

Estudar a razão particular pra fórmula ser desse jeito foge do escopo desse texto, mas ela pode ser conferida aqui (!TODO! botar). Ter uma noção das suas componentes e do que elas medem já é suficiente pra entender o funcionamento do algoritmo. Vamos logo falar de como ele funciona.

O algoritmo pode ser dividido em 4 etapas:

seleção
expansão
simulação
atualização

etapas

1. seleção

“Qual a decisão mais promissora a ser analisada?”

Na etapa de seleção, partimos da raiz e percorremos a árvore descendo pelos nós de maior UCT, até chegar em uma de duas situações:

o nó ainda pode ser expandido, ou
o nó é um estado terminal.

Bom, pra entender o motivo disso primeiro precisamos entender o que significa “poder ser expandido”. É bem simples na verdade: um nó pode ser expandido quando existem jogadas imediatas a partir dele que ainda não foram incluídas na árvore. Em outras palavras: ainda existem filhos possíveis que ele não tem. Observe na árvore abaixo:

O nó $A$ ainda pode ser expandido (a jogada “X3” ainda é possível), mas o nó $B$ não (todas as jogadas imediatamente a partir dali já estão incluídas na árvore).

Agora que tiramos isso do caminho, qual o intuito da etapa de seleção? Bom, a resposta pra isso é simples, se você lembrar que estamos tentando contruir uma árvore! A etapa de seleção simplesmente escolhe um dos nós que ainda não foram construídos, para que possamos construir ele nas etapas seguintes. E qual o critério de seleção que estamos usando? Os nós que estão em ramos mais promissores - por isso estamos percorrendo a árvore escolhendo os nós de maior UCT. Uma imagem para ilustrar o que está acontecendo:

Por isso estamos de olho em nós que ainda podem ser expandidos - por definição, eles são partes ainda não construídas da nossa árvore.

Mas por que precisamos ficar atento também a nós de estado terminal? Isso é simplesmente porque pode ser que aconteça a seguinte situação:

Nesse caso, não tem muito o que expandir, afinal o jogo já acabou! Portanto, simplesmente retornamos o nó $C$ mesmo e é isso aí.

2. expansão

“Adicione um novo nó na árvore”

Na etapa de seleção, selecionamos o nó mais promissor que ainda pode ser expandido. Na etapa de expansão, iremos adicionar seus nós filhos à árvore.

Existem diversas formas de fazer isso, e essa é uma decisão de design do algoritmo. Um método possível é escolher aleatoriamente um dos filhos possíveis e adicioná-lo à árvore. Outro é adicionar todos os filhos possíveis simultaneamente. Uma figura pra ilustrar as diferenças:

Independente de qual for o método de expansão escolhido, no fim ele fará sempre a mesma coisa: adicionar nós à árvore.

3. simulação

“Qual o valor desse nó expandido?”

Agora que adicionamos um nó à árvore, precisamos preencher seus atributos. O atributo visitas é fácil - inicializamos ele com $1$, que é a visita atual. Mas e o atributo valor? Qual é o valor desse novo nó, ou seja, o quão próximo ele deixa o jogador atual da vitória?

Evidentemente, a resposta exata só pode ser obtida vendo todas as ramificações possíveis da decisão do nó, mas isso é justamente o que não queremos fazer, já que iria requisitar que construíssemos a árvore inteira. Então, ao invés de buscarmos a resposta exata, vamos buscar uma aproximação, que será obtida com base numa simulação.

A ideia é: se todos os jogadores agissem de forma aleatória daqui em diante, qual seria um possível resultado do jogo? Esta será a origem do valor da nossa decisão.

Mas afinal, o que garante que isso é uma aproximação decente pra resposta real? Em resumo, a mesma coisa que faz os métodos de Monte Carlo funcionarem: a lei dos grandes números. Apesar de uma simulação com jogadas aleatórias não ser uma aproximação legal, milhares (ou milhões!) delas certamente garantirão uma resposta mais precisa.

Existem formas, é claro, de deixar nossas simulações mais próximas da realidade - podemos fazer os jogadores simulados atuarem não de forma aleatória, mas de acordo com alguma heurística (p. ex.: aleatório, mas nunca fazendo uma jogada que lhe faria perder).

Mas isso são aprimoramentos. O ponto importante de se destacar é que o algoritmo em tese funciona sem isso - ou seja, o agente MCTS consegue descobrir uma boa resposta sem nenhum modelo mental de como o outro jogador se comporta! Com um número grande o suficiente de simulações, suas aproximações irão convergir pro valor real, e ele irá descobrir com uma alta precisão quais as melhores decisões - sem necessariamente ver a árvore toda.

Usualmente, a simulação na árvore é representada por uma linha ondulada:

4. atualização

“O que o valor desse nó expandido significa pro resto da árvore?”

Ao obtermos o valor de um nó recém-expandido, implicitamente também obtemos algumas informações sobre o resto da árvore. Afinal, se uma simulação resulta em uma derrota para o jogador X, certamente não foi só a última decisão que levou a essa derrota - mas todas as decisões tomadas anteriormente!

Isso significa iterar por todos os nós descendentes do nó recém-expandido, e fazer duas atualizações:

o atributo visitas deve ser incrementado em $1$;
o atributo valor deve ser incrementado de acordo com o resultado da simulação.

Evidentemente, há muitas formas de fazer essa segunda atualização. Um modelo que podemos utilizar para o jogo da velha é o seguinte:

\[valor = \begin{cases} +1 & \text{ se vitória} \\ +0 & \text{ se empate} \\ -1 & \text{ se derrota} \\ \end{cases}\]

É importante destacar dois detalhes.

O primeiro: lembre-se da nossa discussão anterior sobre a modelagem com dois jogadores. Se a simulação terminou em vitória para o jogador X, os antepassados relativos ao jogador X aumentarão o seu valor, enquanto os relativos ao jogador O irão diminuir o seu valor (já que o jogador O perde com aquele resultado).

O segundo: se na etapa de seleção chegamos em um nó terminal que não podia ser expandido, ainda assim ele é simulado e seu valor é propagado para o resto da árvore. Isso é importante, porque se aquele nó foi selecionado como sendo “o mais promissor até agora”, ele precisa ser re-simulado e ter seus valores atualizados. Se não fizermos isso, ele será potencialmente escolhido a toda iteração do algoritmo, já que nada vai mudar!

Seguindo o exemplo anterior:

exemplo in natura

E é isso! Pra recapitular, essas são basicamente as quatro etapas do algoritmo:

seleção - percorrer a árvore buscando os nós de maior UCT, até chegar em um nó da árvore ainda não-expandido (ou um nó terminal).
expansão - se chegarmos em um nó que ainda pode ser expandido, adicionamos as possíveis expansões à árvore (talvez uma de cada vez, talvez todas ao mesmo tempo).
simulação - simulamos um jogo a partir daquele ponto até obtermos um resultado. Assim preenchemos o valor do nó selecionado.
atualização - atualizamos os antepassados do nó simulado de acordo com o resultado da simulação.

Abaixo tem um painel pra você desafiar um algoritmo MCTS no jogo da velha. Clique em “visualizar” pra ver ele realizando as etapas iterativamente!

em construção

bibliografia

Browne, Cameron B., et al. “A survey of monte carlo tree search methods.” IEEE Transactions on Computational Intelligence and AI in games 4.1 (2012): 1-43.