poda alfa beta distribuída

19

Estou procurando um algoritmo eficiente que me permita processar a árvore de pesquisa minimax para xadrez com poda alfa-beta em uma arquitetura distribuída. Os algoritmos que encontrei (PVS, YBWC, DTS, veja abaixo) são todos bastante antigos (1990 é o mais recente). Suponho que houve muitos avanços substanciais desde então. Qual é o padrão atual nesse campo?

Além disso, por favor, aponte-me para a explicação de DTS feita por um idiota, pois não consigo entendê-la nos trabalhos de pesquisa que li.

Os algoritmos mencionados acima:

  • PVS: Divisão de variação de princípio
  • YBWC: Jovens irmãos esperam conceito
  • DTS: Divisão Dinâmica de Árvores

são todos discutidos aqui .

algorithms distributed-systems board-games wirate
fonte
Talvez esta seja uma leitura interessante: chessbase.com/newsdetail.asp?newsid=8047
Alex ten Brink
2
Bem, este é um problema (paralelizando a pesquisa minimax ou qualquer uma de suas variantes) particularmente difícil. Em um artigo publicado este ano por Richard Korf, intitulado "Desafios de pesquisa em pesquisa combinatória", pode-se ler o seguinte: "[...] a pesquisa minimax com poda de alfa-beta foi notoriamente difícil de paralelizar" Duvido sinceramente existe um algoritmo que torná-lo sempre de forma eficiente ...
Carlos Linares López
Então, considerando que sou apenas um estudante de ciências da computação do 4º semestre muito humilde, devo optar por um algoritmo serializado ou tentar esperar alguma aceleração sub-linear aceitável?
Wirate
Desculpe pelo atraso na minha resposta, isso passou completamente despercebido na minha Caixa de entrada. De fato, eu esperaria que a economia final dependa completamente da distribuição das pontuações atribuídas por sua função de avaliação às folhas da árvore de pesquisa. Em geral, não há garantias de que um algoritmo de pesquisa distribuído tenha um desempenho significativamente melhor que um algoritmo de pesquisa alfa-beta serializado. Assim, eu definitivamente ir para uma versão serializada do que tentar como muitas melhorias como viável (movimentos de ordenação, quadros de transposição, etc.)
Carlos Linares López
Eu tive algum sucesso com o alfa-beta paralelo (basicamente como descrito na página wiki à qual você vinculou).
list.

Respostas:

3

Sim, a teoria avançou significativamente e de certa forma devido à literatura de análise de xadrez e às técnicas gerais de programação paralela. aqui estão algumas referências mais recentes sobre a poda alfa (xadrez) sobre clusters / paralelismo distribuído. também algumas das primeiras literaturas de xadrez de computação distribuída são anteriores a muitos padrões básicos de design paralelo e podem ser conceituadas nessa estrutura.

a idéia básica por trás do DTS é que as árvores de pesquisa são distribuídas entre os nós computacionais com base na complexidade do movimento / layout. processadores não utilizados que "terminam cedo" podem fazer um trabalho adicional além de uma alocação inicial, que pode ser distribuída o mais uniformemente possível inicialmente, mas acabará sendo desigual. portanto, é basicamente um tipo de fila de "balanceamento de carga" e "produtor / consumidor" , ou também semelhante à programação de tarefas.

Este processador ocioso transmite (usando memória compartilhada) que está ocioso e está disponível para "ajudar" qualquer outro processador a pesquisar sua árvore. Os processadores ocupados coletam os dados do "estado da árvore" e os armazenam na memória compartilhada para o processador inativo examinar. Esse processador inativo analisa esses dados e decide qual (se houver) dos processadores ocupados parece ter uma árvore que é complicada o suficiente para ser eficiente para ajudar na pesquisa. Se essa posição for encontrada, o processador inativo informa o processador que possui esse nó e eles "unem" forças.

vzn
fonte