Aplicações do MCTS / UCT

O MCTS / UCT é um método de pesquisa em árvore de jogo que usa um algoritmo de bandido para selecionar nós promissores a serem explorados. Os jogos são concluídos aleatoriamente e os nós que levam a mais vitórias são explorados com mais intensidade. O algoritmo bandido mantém um equilíbrio entre explorar nós com altas taxas de vitória e explorar nós desconhecidos (e em sua forma pura não necessariamente usa uma função de avaliação heurística). Os programas baseados nessa técnica geral obtiveram resultados surpreendentes no computador Go .

As pesquisas monte-carlo dirigidas por bandidos foram aplicadas a outros problemas de pesquisa? Por exemplo, seria uma abordagem útil na aproximação de soluções para MAX-SAT, BKP ou outros problemas de otimização combinatória? Existem características particulares de um problema (estrutural / estatístico / etc.) Que sugiram se uma abordagem no estilo bandido seria ou não eficaz?

Existem problemas determinísticos conhecidos que seriam totalmente resistentes aos métodos de bandidos, devido à natureza do espaço da solução?

Esta não é uma resposta completa, mas algumas observações básicas sobre como aplicar isso ao MAX-SAT.

$7/8$$x=0$$x=1$$x=0$$x=1$$7/8$$7/8$

$7/8$$NP$$7/8$heurística que você usa, mesmo que adivinhe perfeitamente, ainda existem fórmulas insatisfatórias para as quais o retorno apenas concluirá que são insatisfatórias após várias etapas exponenciais. Limites inferiores nos comprimentos das provas de resolução produzem esses resultados. Uma referência é:

Pavel Pudlák, Russell Impagliazzo: Um limite inferior para algoritmos DLL para k-SAT (versão preliminar). SODA 2000: 128-136

Quanto à questão de quais características tornam um problema passível de abordagem baseada em bandidos, este artigo descreve o comportamento da UCT em vários espaços de pesquisa:

http://www.cs.cornell.edu/~raghu/Raghuram_Ramanujan_files/mcts11.pdf

Atenciosamente, Cameron

Este artigo de pesquisa recente lista a aplicação do MCTS a vários problemas de pesquisa e otimização que não sejam jogos, na Seção 7.8:

http://pubs.doc.ic.ac.uk/survey-mcts-methods/survey-mcts-methods.pdf

http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=6145622

Quanto aos domínios que são totalmente resistentes aos métodos baseados em bandidos, não conheço nenhuma mão imediata. O xadrez é uma omissão flagrante da literatura do MCTS, possivelmente devido a "estados de armadilha" que prejudicaram a pesquisa, mas também possivelmente devido ao fato de que os jogadores de xadrez de computador são tão otimizados e bons nos dias de hoje que é improvável que qualquer nova abordagem faça um dente neles.

Atenciosamente, Cameron