Poda alfa-beta com movimentos simultâneos?

7

Tenho um jogo que estou construindo ai ai pois tem 2 jogadores fazendo movimentos simultâneos. Neste jogo, há exatamente um movimento em que, se os dois fazem ao mesmo tempo, o resultado é diferente do que se tivessem feito separadamente (todos os outros movimentos são bem independentes).

Enfim, estou tentando encontrar um bom algoritmo para jogar nele. O Minimax com poda alfa-beta parece ser um bom candidato se os jogadores estiverem fazendo movimentos alternados, mas não para os simultâneos. Encontrei um artigo (pdf) sobre o assunto, mas está um pouco demais - estou tendo problemas para ler o pseduocódigo.

Então, alguém pode ajudar a esclarecer essa abordagem, sugerir outra maneira de realizar a poda alfa-beta em um jogo assim ou sugerir um algoritmo melhor inteiramente?

Fishtoaster
fonte

Respostas:

9

O fato é que, com movimentos simultâneos, a estratégia ideal é mais difícil de adivinhar, porque você precisa calcular algo que nem sempre está obviamente vencendo.

Dê uma olhada no equilíbrio de Nash e no dilema do prisioneiro, se você ainda não os conhece. Esse é o tipo de raciocínio necessário sempre que você considerar dois movimentos simultâneos, em vez de simplesmente escolher um movimento que entre em uma configuração vencedora em jogos com movimentos não simultâneos. O conceito de dominância substitui o conceito de vencer .

O algoritmo em sua referência faz isso quando se refere às figuras 4 e 5, mas primeiro tente descobrir o que essas figuras devem fazer antes de entender como elas o fazem.

jmad
fonte