Como escolho o melhor algoritmo para um jogo de tabuleiro como damas?
Até agora, considerei apenas três algoritmos, a saber, minimax, poda alfa-beta e pesquisa em árvore Monte Carlo (MCTS). Aparentemente, a poda alfa-beta e o MCTS são extensões do algoritmo básico minimax.
tl; dr:
Nenhum desses algoritmos é prático para o trabalho moderno, mas são bons lugares para começar pedagogicamente.
Você sempre deve preferir usar a poda Alpha-Beta em vez da pesquisa minimax simples.
Você deve preferir usar alguma forma de pesquisa guiada heurística, se conseguir criar uma heurística útil. Criar uma heurística útil geralmente requer muito conhecimento de domínio.
Você deve preferir usar a pesquisa da Árvore de Monte Carlo quando não tiver uma boa heurística, quando os recursos computacionais forem limitados e quando os erros não terão grandes consequências no mundo real.
Mais detalhes:
Na pesquisa minimax, não tentamos ser muito inteligentes. Nós apenas usamos uma abordagem de programação dinâmica padrão. É fácil descobrir o valor dos movimentos de diferença se estivermos perto do final do jogo (já que o jogo terminará na próxima jogada, não precisamos olhar muito à frente). Da mesma forma, se soubermos o que o nosso oponente fará no último lance do jogo, é fácil descobrir o que devemos fazer no segundo lance. Efetivamente, podemos tratar o segundo último lance como o último lance de um jogo mais curto. Podemos então repetir esse processo. O uso dessa abordagem certamente descobrirá as melhores estratégias em um jogo de formato extensivo padrão, mas exigirá que consideremos todos os movimentos possíveis, o que é inviável para todos, exceto os jogos mais simples.
A poda alfa-beta é uma melhoria estrita na pesquisa Minimax. Faz uso do fato de que alguns movimentos são obviamente piores que outros. Por exemplo, no xadrez, não preciso considerar nenhuma jogada que lhe daria a oportunidade de me colocar em xeque-mate, mesmo que você pudesse fazer outras coisas nessa posição. Quando vejo que um movimento pode levar a uma perda, não vou me preocupar em pensar no que mais pode acontecer a partir desse ponto. Vou procurar outras coisas. Também é certo que esse algoritmo produz o resultado correto e é mais rápido, mas ainda deve considerar a maioria dos movimentos na prática.
Existem duas maneiras comuns de contornar o custo computacional extremo de resolver exatamente esses tipos de jogos:
Use uma heurística (a pesquisa A * é o algoritmo usual para fins pedagógicos, mas a pesquisa por quiescência é uma ideia semelhante em jogos para 2 jogadores). Esta é apenas uma função que fornece uma estimativa do valor de um estado do jogo. Em vez de considerar todos os movimentos de um jogo, você pode considerar movimentos a uma distância finita à frente e, em seguida, usar o valor da heurística para julgar o valor dos estados atingidos. Se sua heurística é consistente (essencialmente: se sempre superestima a qualidade dos estados), isso ainda produzirá a resposta correta, mas com enormes acelerações na prática.
Use implementações (como a Pesquisa de árvore de Monte Carlo). Basicamente, em vez de considerar todos os movimentos, execute alguns milhares de jogos simulados entre jogadores agindo aleatoriamente (isso é mais rápido do que considerar todos os movimentos possíveis). Atribua um valor aos estados igual à taxa média de vitórias dos jogos a partir dele. Isso pode não resultar na resposta correta, mas em alguns tipos de jogos, ele é executado de maneira confiável. É frequentemente usado como uma extensão de técnicas mais exatas, em vez de ser usado por si só.
Dado este contexto, eu recomendaria começar com o Minimax . Dos três algoritmos, o Minimax é o mais fácil de entender.
O Alpha-Beta , como outros já mencionaram em outras respostas, é uma melhoria estrita em relação ao Minimax. O Minimax é basicamente uma parte da implementação do Alpha-Beta, e um bom entendimento do Alpha-Beta exige que você comece com um bom entendimento do Minimax. Se você tiver tempo sobrando depois de entender e implementar o Minimax, eu recomendaria seguir para o Alpha-Beta posteriormente e construí-lo em cima do Minimax. Começar com o Alpha-Beta se você ainda não entende o Minimax não faz muito sentido.
A Pesquisa de árvores de Monte-Carlo é provavelmente um pouco mais avançada e mais complicada para entender realmente. Nos últimos dez anos, o MCTS realmente tem se tornado muito mais popular que os outros dois, portanto, desse ponto de vista, entender o MCTS pode ser mais "útil".
A conexão entre o Minimax e o MCTS é menos direta / óbvia do que a conexão entre o Minimax e o Alpha-Beta, mas ainda existe uma conexão pelo menos em um nível conceitual. Eu diria que ter um bom entendimento do Minimax ainda é benéfico antes de mergulhar no MCTS ; em particular, entender o Minimax e suas falhas / pontos fracos pode fornecer um contexto útil / ajudá-lo a entender por que o MCTS se tornou "necessário" / popular.
Para concluir, na minha opinião:
fonte
Se você precisar escolher entre as podas Minimax e Alpha-Beta, escolha Alpha-beta. É mais eficiente e rápido porque pode podar uma parte substancial da sua árvore de exploração. Mas você precisa ordenar as ações da melhor para a pior, dependendo do ponto de vista máximo ou mínimo, para que o algoritmo possa perceber rapidamente se a exploração é necessária.
fonte