MCTS: Busca em Árvore Monte Carlo

Rode o MCTS no jogo da velha e veja a árvore crescer torta: visitas e taxa de vitória por jogada, o caminho de seleção de cada iteração e o efeito da constante C.

MCTS: a árvore que cresce torta

0 iterações1 nós · profundidade 0

anel cheio: mais visitada, a jogada que o MCTS devolveria

anel tracejado: maior UCB1, a próxima a ser explorada

A árvore está vazia. Cada iteração faz seleção, expansão, simulação e retropropagação.

C = 1.40

A largura de cada nó é o número de visitas. Rode cem iterações e repare que a árvore não é simétrica: o ramo promissor recebe quase toda a busca e desce fundo, enquanto os ruins viram tiras finas. Arraste o C para zero e o desenho vira um corredor estreito, porque a seleção passa a ignorar o que ainda não conhece. Suba o C para dois e ele alarga, com todas as jogadas visitadas quase o mesmo tanto e nenhuma estudada a fundo. Nenhum dos dois extremos joga bem.