Algoritmo AI de Damas

7

Estou fazendo uma IA para o meu jogo de damas e estou tentando dificultar o máximo possível. Aqui estão os critérios atuais para uma mudança na dificuldade mais difícil:

1: Procure um bloco: é quando uma peça está sendo ameaçada e outra peça pode ser movida por trás dela para protegê-la. Aqui está um exemplo:

Black Moves
|W| |W| |W| |W| |
| |W| |W| |W| |W|
|W| | | |W| |W| |
| | | |W| | | | |
| | | | |B| | | |
| |B| | | |B| |B|
|B| |B| |B| |B| |
| |B| |B| |B| |B|

Blocos Brancos
|W| |W| |W| |W| |
| |W| | | |W| |W|
|W| |W| |W| |W| |
| | | |W| | | | |
| | | | |B| | | |
| |B| | | |B| |B|
|B| |B| |B| |B| |
| |B| |B| |B| |B|

2: Mover peças para fora de perigo: se alguma peça estiver sendo ameaçada e uma peça não puder ser bloqueada para ela, ela tentará se afastar. Se a peça não puder sair do caminho sem ainda estar em perigo, o computador a ignora.

3: Se o jogador do computador possuir quaisquer reis, ele tentará 'caçar' as peças inimigas no tabuleiro, se nenhum movimento puder ser feito que não ponha em perigo o rei ou outras peças, o computador ignora esta regra.

4: Qualquer peça pertencente ao computador que está na coluna 1 ou 6 tentará ir para o lado. Quando uma peça está na coluna 0 ou 7, está em uma posição muito estratégica porque não pode ser capturada enquanto estiver em uma dessas colunas

5: Faz um movimento aleatório educado, o movimento não comprometerá a peça que está se movendo ou qualquer peça que esteja no quadro.

6: Se nenhuma das opções acima for possível, ela fará um movimento aleatório.


Esta pergunta não é realmente específica para nenhuma linguagem, mas se todos os exemplos pudessem estar em Java, seria ótimo, considerando que este aplicativo está escrito no Android. Alguém vê algum espaço para melhorias neste algoritmo? Algo que tornaria melhor jogar damas?

John
fonte
(Em uma nota específica do Damas, o IIRC estar no limite não é necessariamente a vantagem que você faz parecer; essas peças não têm mobilidade, pois só têm um movimento disponível e são mais fáceis de capturar e capturar.)
Steven Stadnicki
2
Apenas no caso de você não estar ciente de damas, é um jogo resolvido e, se jogado perfeitamente, o resultado é sempre um empate. chessbase.com/newsdetail.asp?newsid=3997
Adam

Respostas:

15

Se você está tentando criar uma boa IA para o seu programa de damas, o primeiro lugar para procurar é o que é conhecido como pesquisa em árvore de jogos Alpha-Beta . A versão curta é que qualquer IA que leve em conta apenas os recursos estáticos da posição atual terá problemas, principalmente no início e no meio do jogo, porque simplesmente não consegue entender o que está acontecendo atualmente no jogo e o que as ameaças são. Em vez disso, o que você deseja fazer é escrever um algoritmo que procure todos os movimentos-e-respostas possíveis em busca de algum número de movimentos à frente (5 a 10 seria típico), avalie a posição no final de cada ramo desse movimento-e -reply tree (em termos de 'quantas peças à frente ou atrás eu estou?), e então faz o movimento que lhe dá a melhor chance - em outras palavras, o movimento que maximizaseu valor possível, onde o valor possível é calculado como o valor mínimo possível em todas as respostas do seu oponente (supondo, em outras palavras, que ele fará a melhor jogada para ele) etc. - é por isso que esse algoritmo é freqüentemente chamado de algoritmo Minimax .

O que você encontrará é que muitos dos elementos dos quais você está falando - mover peças para o lado, mover peças fora de perigo etc. - se tornarão elementos da função de avaliação posicional da pesquisa na árvore de jogos. Essencialmente, em vez de fazer a pergunta simples 'quantas peças à frente há um lado ou o outro?', Você dirá 'qual é o valor dessa posição?' e, em seguida, forneça valores de pontos para vários recursos do tabuleiro (por exemplo, se uma peça está do lado, vulnerável etc.) em termos de peças parciais - por exemplo, você pode decidir que a diferença entre uma aresta e um centro peça vale possivelmente 0,1 peça, portanto, em uma posição em que você é um homem por trás, mas possui uma peça extra de borda, o valor total para você será -0,9.

Uma noção avançada crítica para IA de damas especificamente é o conceito de busca por Quiescência : imagine que você desce seis movimentos em sua árvore e, no final, seu oponente acabou de capturar onde sua resposta (forçada) é uma recaptura imediata. Infelizmente, a função de avaliação posicional não pode ver a recaptura, por isso avalia a posição como uma peça para o seu oponente, mesmo que você esteja prestes a recuperar a paridade. A busca por quiescência é uma tentativa de resolver esse problema, forçando o avaliador a descer para um ramo até que todas as capturas forçadas possíveis tenham sido feitas e somente então avaliar a posição.

Tudo isso pode parecer bastante complicado, mas acho que você achará mais direto do que parece - depois de escrever sua função de avaliador, a pesquisa em árvore é relativamente fácil; existem muitos conceitos inteligentes (como tabelas de transposição ) que você pode aplicar a ele, mas deve ser fácil fazer algo funcionar e continuar melhorando. Para obter mais detalhes, sugiro pesquisar em praticamente qualquer um dos termos principais (pesquisa alfa-beta, minimax, pesquisa de quiescência, árvore de jogos etc.); há muitas informações boas sobre todos esses conceitos na web.

Steven Stadnicki
fonte
Obrigado pela sua resposta, já pensei em fazer isso antes, mas sempre achei que meu caminho era mais eficaz, mas a maneira como você o descreve parece que seria mais eficaz, mas com muito mais trabalho. Em breve, vou criar uma IA para um jogo de xadrez e acho que seria menos trabalhoso e mais eficaz fazê-lo do seu jeito. Se o computador tem várias opções diferentes para escolher e as reduz a um casal com resultados bons, como pode perder? Obrigado pela resposta detalhada!
John
Eu ainda recomendaria que você tentasse o método de Steven, pois seria significativamente mais fácil implementar o minimax em damas do que o xadrez e, de fato, seria significativamente mais fácil implementar o minimax em damas do que você imagina. Eu escrevi um algoritmo minimax (não podado) para o Connect Four em algumas centenas de linhas. Tudo é bastante direto se você estiver disposto a dedicar tempo e energia para melhorar suas habilidades.
precisa
11
Gostaria de ressaltar que, desde a resposta de Steven, o MTCS se tornou imensamente popular como uma alternativa ao Alpha / Beta. Também vale a pena analisar, especialmente porque o MTCS é um algoritmo a qualquer momento .
Tobia Tesan
@TobiaTesan Presumo que você queira dizer MCTS (Monte Carlo Tree Search)? É verdade, mas o MCTS é substancialmente mais difícil de implementar do que um algoritmo alfa-beta básico e eu definitivamente incentivaria a implementação da AB primeiro, principalmente porque é uma boa base para implementar o MCTS.
Steven Stadnicki
11
@StevenStadnicki Veja bem, eu não estava tentando criticar de nenhuma maneira sua excelente resposta (que eu votei). Concordo que métodos clássicos como A / B sempre valem a pena ser aprendidos primeiro, principalmente porque o Minimax é um poderoso quadro teórico; no entanto, o MTCS realmente não me pareceu tão difícil de implementar; a parte complicada do IMHO é que algumas versões de pseudocódigo existem um pouco no lado de baixo nível, em particular (por exemplo, Gelly 2011), elas gostam de expressar o algoritmo através de efeitos colaterais em um estado global [board] que são revertidos como chamadas recursivas são acionadas.
Tobia Tesan