Quero começar com um cenário que me fez pensar sobre o desempenho do MCTS: Vamos supor que exista uma ação que ainda não foi adicionada à árvore de pesquisa. São algumas camadas / movimentos muito profundos. Mas se jogarmos esse lance, o jogo será basicamente ganho. No entanto, vamos supor também que todas as jogadas que poderiam ser feitas no estado do jogo são muito ruins. Por uma questão de argumento, digamos que existem 1000 movimentos possíveis e apenas um deles é bom (mas muito bom) e o resto é muito ruim. O MCTS não deixaria de reconhecer isso e nãoaumentar a árvore de pesquisa em direção a esse movimento e também avaliar muito mal essa subárvore? Eu sei que o MCTS eventualmente converge para o minimax (e eventualmente ele construirá a árvore inteira se houver memória suficiente). Então, ele deve saber que a mudança é boa, embora haja muitas possibilidades ruins. Mas acho que na prática isso não é algo em que se possa confiar. Talvez alguém possa me dizer se esta é uma avaliação correta da minha parte.
Além deste cenário especial, eu também gostaria de saber se existem outros cenários em que o MCTS terá um desempenho ruim (ou extraordinário).
Respostas:
Se a movimentação é encontrada e a rapidez com que ela é encontrada depende de algumas coisas. Se bem entendi, há uma sequência de muitas jogadas "ruins" que levam à jogada de "grande vitória", e você tem medo de que o algoritmo MCTS não chegue à jogada de "grande vitória" porque selecionará mais promissoras move-se ainda mais para a árvore. Algumas coisas em que pensar (leia também o artigo da Wikipedia sobre MCTS ):
ao fazer playouts, você pode jogar seu jogo apenas por mais alguns movimentos ou até o final do jogo. Jogar apenas alguns movimentos adiante é obviamente mais rápido, mas no caso extremo que você descreveu, não seria a melhor escolha. Se você souber da existência de tais cenários, lance o jogo até o fim nos playouts.
ao fazer playouts, você pode escolher seus movimentos / ações aleatoriamente ou com base em algumas heurísticas simples e gananciosas (rápidas) adaptadas ao seu problema. Talvez haja heurísticas gananciosas projetadas para encontrar ou levar em consideração esses cenários para o seu jogo / problema? Se sim, implemente-os. É então chamado de "playout pesado". Compare os resultados com os playouts usando movimentos aleatórios.
Se você escolher as ações usando UCT (limite superior de confiança aplicado a árvores), a primeira parte da expressão será responsável pela exploração. Movimentos com alta taxa de vitória média são os preferidos. A segunda parte corresponde à exploração. Se o parâmetro de exploração estiver alto o suficiente (teste empiricamente para o seu problema), serão preferidos movimentos com poucas simulações. A alta exploração seria outra maneira de encontrar sua jogada de ouro, em detrimento da exploração (leia sobre o dilema de exploração / exploração).
Se você descrever um cenário realista de jogo ou problema, poderemos ajudá-lo a apresentar uma estratégia adequada.
fonte