O melhor algoritmo que aprimora o alfa-beta?

8

Eu estou estudando IA. Meu professor nos deu o código-fonte de um jogo semelhante ao xadrez e nos pediu para aprimorá-lo. Meu exercício é melhorar o algoritmo alfa / beta implementado nesse jogo. O programador já usa tabelas de transposição, MTD (f) com memória alfa / beta + (MTD (f) é o melhor algoritmo que conheço de longe). Existe algum algoritmo melhor para aprimorar a pesquisa alfa-beta ou uma boa maneira de implementar o MTD (f) na codificação de um jogo?

Risa
fonte

Respostas:

6

Responderei geralmente mais especificamente. Primeiro, na minha experiência, quando um professor pergunta, existe uma maneira melhor ... Eu imediatamente vou ao livro e procuro por coisas que o autor observou como falhas no algoritmo em questão. Segundo, vejo otimizações que me ajudaram no passado.

Para um algoritmo de pesquisa em árvore como o alfa-beta, eu adicionaria uma heurística que reduz o número de pesquisas ou faz com que ele procure primeiro em locais mais prováveis.

Eu atribuiria pesos a caminhos que podem ser tomados na árvore com base nos resultados anteriores. Se um caminho resultou em uma pontuação mais alta no passado, provavelmente é um bom caminho a seguir novamente. Para encurtar a história, adicione heurísticas aos caminhos e escolha ir com eles para que o algoritmo possa terminar mais cedo.

Note que eu realmente não me lembro muito sobre o algoritmo específico, apenas que é uma árvore e a abordagem ingênua a ele não envolve essa heurística.

brandon
fonte
Eu acho que você está falando en.wikipedia.org/wiki/Killer_heuristic
Adam
Parece que sim. Tentei dar uma resposta menos específica para ajudar com problemas futuros, pois a abordagem é a mesma. O verdadeiro problema não era que a risa não conhece a otimização alfa-beta, é que eles precisam ver a abordagem comum das otimizações, especialmente na IA, pois esse é um campo muito relacionado à pesquisa.
Brandon
4

Você não mencionou a remoção de movimentação nula ou reduções de movimentação tardia. Eles são bastante fáceis de implementar e são ainda mais eficazes na redução do tamanho da pesquisa do que na poda alfa-beta. As extensões de pesquisa também são importantes para atenuar o efeito do horizonte; a busca por quiescência, em particular, é um componente muito importante para uma IA de xadrez.

Kira Chow
fonte
1

Analise a ordem de movimentação e a pesquisa de variações de princípio

Druzil
fonte