Como implementar a IA para damas / rascunhos?

Eu vi esse jogo de damas e me perguntei como a IA foi implementada.

Como devo implementar uma IA para damas (rascunhos, dama, dama)? Existem algoritmos conhecidos?

Muito thnaks cheio para todos. Estou muito maravilha de ver este post no blog tutorial do jogo Tic Tac Toe .

Então, eu quero o código-fonte aberto do algoritmo de jogo dama e a postagem no blog .. Existe algum link útil ou qualquer arquivo doc ..? Por favor deixe-me saber..

Oh, eu amo esses jogos!

Então, para começar, primeiro, para que um computador jogue, ele precisa:

1. uma estrutura para trabalhar com
2. regras para jogar por
3. uma condição de vitória para trabalhar no sentido de

Vamos abordar esta peça de cada vez.

Estrutura

Como a placa é uma grade 8x8 (mas pode ser facilmente dimensionada) e cada espaço da grade pode existir em apenas um dos cinco estados, vamos definir esses estados:

[EMPTY, WHITE_PIECE, BLACK_PIECE, WHITE_PIECE_PROMOTED, BLACK_PIECE_PROMOTED]

Respectivamente, ENUM'd para:

[0, 1, 2, 3, 4]

Agora que sabemos o que cada espaço pode ser, precisamos de uma maneira de representar todos os espaços, ou o quadro, se desejar. Quase todas as linguagens fortes suportam uma matriz multidimensional (uma matriz em que cada elemento é uma matriz contendo dados). Portanto, use o seguinte código para definir nossa matriz:

BOARD_ARRAY = array(8, 8)

Isso nos dará uma matriz 8 x 8 na qual podemos armazenar números inteiros (nossas enumerações anteriores):

(
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
)

Agora você já pode ver como isso está começando a parecer um quadro! Eu nunca reproduzi a variante mencionada no vídeo do youtube, mas parece começar com 2 linhas de peças brancas uma linha da parte inferior e 2 linhas de peças pretas uma linha do topo. O que significa que, quando começamos um jogo, nossa matriz deve ficar assim:

(
[0, 0, 0, 0, 0, 0, 0, 0],
[2, 2, 2, 2, 2, 2, 2, 2],
[2, 2, 2, 2, 2, 2, 2, 2],
[0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0],
[1, 1, 1, 1, 1, 1, 1, 1],
[1, 1, 1, 1, 1, 1, 1, 1],
[0, 0, 0, 0, 0, 0, 0, 0],
)

(Lembre-se de que 2 representa 'BLACK_PIECE' e 1 representa 'WHITE_PIECE')

Então agora o computador tem uma estrutura para trabalhar. Etapa 1 concluída!

Regras

Vamos imaginar que você tinha um tabuleiro real à sua frente, jogando contra um jogador mestre. Se você tentasse mover uma de suas peças, levaria um tapa na mão. Se você tentasse mover uma peça de uma maneira que não conseguiria, levaria um tapa na mão. Se você tentou trapacear bem ... você entendeu. Mas o problema é que os computadores não. Portanto, é nosso trabalho fornecer regras estritas para serem cumpridas.

Precisamos criar uma maneira de verificar se algum movimento é 'legal'. O que significa que primeiro precisamos de uma maneira de representar um 'movimento'. Uma maneira seria usar posições de array; Por exemplo, para mover uma peça de [0, 0] para [0, 1], poderíamos criar uma função que atualizará o tabuleiro, dado esse movimento. Então, de volta à folga:

MY_MOVE = array( [0, 0], [0, 1] )

O item acima representa uma peça, movendo um espaço para baixo do canto superior do tabuleiro (assumindo que 0, 0 é o canto superior esquerdo). Você também pode perceber que eu escolhi usar uma matriz multidimensional para a mudança. Isso ocorre porque as peças podem teoricamente se mover um grande número de vezes em um turno (para 'pular' outras peças). Então, vamos fingir que em 0, 1 havia uma peça do oponente, o que significa que aterrissaríamos em 0, 2:

MY_MOVE = array( [0, 0], [0, 2] )

Muito simples eh. O programa deve entender que, se pularmos um espaço, estamos pulando outra peça (ou é uma jogada ilegal e deve gerar um erro). Agora vamos pular duas peças:

MY_MOVE = array ( [0, 0], [0, 2], [0, 4] )

Isso nos fornece uma maneira de descrever qualquer movimento no quadro. Yay! Agora, como eu não entendo completamente as regras do jogo exato em questão (embora tenha jogado um pouco de damas canadenses nos meus dias), a legalidade exata da jogada precisará ser definida por você. Um bom fluxo até este ponto seria semelhante a:

FUNCTION_FIND_ALL_LEGAL_MOVES( MY_BOARD ) Returns: array ALL_LEGAL_MOVES
FUNCTION_FIND_BEST_MOVE( MY_BOARD, ALL_LEGAL_MOVES ) Returns: array MY_MOVE
FUNCTION_DO_MOVE( MY_BOARD, MY_MOVE ) Throws: error ILLEGAL_MOVE Updates: MY_BOARD
repeat from start for each turn

O que precede pressupõe que você pode percorrer cada peça para encontrar todas as suas jogadas legais e, em seguida, receber uma coleção de todas as jogadas legais de alguma forma escolher a melhor (estratégia aqui). A jogada é aplicada ao tabuleiro ou gera um erro. Em seguida, o próximo jogador faz a sua vez. Portanto, temos uma IA que sabe jogar! Alegria! Se movendo.

Ganhando

Jogos simples são maravilhosos, porque vencer é definido por um estado muito simples. Não há peças brancas no quadro? Bem, eu acho que você ganhou! Isso é implementado na etapa 2 quando escolhemos a melhor jogada para nos aproximar da condição vencedora.

Para criar uma IA muito inteligente, você pode manter um banco de dados que armazene todos os quadros possíveis como um estado, com todos os movimentos possíveis de todos os estados possíveis, para encontrar cadeias para ganhar.

Você também pode criar estratégias, como: se houver uma peça que SERÁ pulada, salve a peça ou se uma peça puder saltar mais de uma peça, faça esse salto.

Isso deve lhe dar um bom ponto de partida, é apenas um método de possibilidades literalmente ilimitadas. Teoricamente, você poderia construir um robô gigante para desenhar com giz de cera e realizar análises espectrais no desenho para escolher movimentos ... mas não funcionaria muito bem ou rápido. Desta forma, funcionou no passado e funcionou bem (: Espero que ajude!

Algumas palavras sobre implementação

Damas é o que é referido como um jogo 'resolvido', na medida em que podemos calcular todos os movimentos sem incógnitas. Mas isso é um monte de movimentos! Portanto, não há como fazer tudo manualmente ... se ao menos houvesse ... ah, certo, somos programadores. bomba de punho

O SQL é uma ferramenta maravilhosa para armazenar todos esses movimentos aparentemente intermináveis. Para quem não tem experiência com SQL, o mySQL é um servidor SQL gratuito (bastante fácil de usar) e de código aberto. O SQL é usado para gerenciar bancos de dados, como uma planilha com esteróides. Também é capaz de armazenar grandes quantidades de dados e trabalhar com eles muito rapidamente.

Então, como podemos usar isso? Como sabemos que, se o tabuleiro estiver em um estado exato (cada peça em uma determinada posição), podemos calcular todos os movimentos disponíveis e salvá-los. Por exemplo:

+Board State+          +All Possible Moves+               +Best Move+
([0,0,1,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([7,6],[7,7])
([0,0,2,2,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([5,5],[5,4])
([0,0,1,3,3],[3..)     ([0,1],[0,2]), ([7,6],[7,7],[5..)  ([4,4],[4,3])
etc...

Portanto, quando o computador precisa fazer uma mudança, ele simplesmente procura o estado da placa (armazenada como chave primária) no banco de dados e pode escolher a melhor jogada (deve ser imbatível) ou uma das outras jogadas para tornar mais amigável AI.

Ótimo agora vamos construir esse banco de dados. Primeiro, precisamos calcular todos os estados do fórum. O que pode ser feito com um grande loop desagradável, se alguém quiser gastar algum tempo e resolver isso, seria incrível. Olhe para a matriz como um número grande e conte para cima, exceto na base 5 (0, 1, 2, 3, 4), e condicione que cada jogador tenha apenas 16 peças.

Nesse ponto, devemos ter todos os estados da placa armazenados e podemos calcular todos os movimentos possíveis.

Uma vez calculados todos os movimentos possíveis, vem a parte divertida de encontrar os melhores movimentos possíveis. É aqui que meu conhecimento começa a falhar e coisas como Minimax ou A * começam a entrar em jogo. Desculpe, não posso ajudar mais nisso: /

Em qualquer ponto do jogo, a quantidade de movimentos possíveis para um jogador é bastante baixa * (cerca de 5), significa que é possível pensar alguns movimentos à frente, avaliar todos os movimentos possíveis e selecionar a melhor jogada.

Essa abordagem é chamada minimax (wikipedia) .

Para implementar o minimax, você precisará de uma função de avaliação que retorne uma pontuação para um determinado layout e jogador do tabuleiro. Para rascunhos, uma implementação ingênua seria uma função que retorna um ponto para cada peça que o jogador tiver vivo.

Uma visualização de uma árvore de decisão minimax (do artigo da wikipedia). Abaixo do lado esquerdo está o número da curva. Os nós das folhas têm uma pontuação avaliada, que é alimentada de volta à árvore para tomar uma decisão.

*no entanto, rascunhos é o jogo com o maior fator de ramificação que foi completamente resolvido .

A poda alfa-beta é um algoritmo de pesquisa que busca diminuir o número de nós que são avaliados pelo algoritmo minimax em sua árvore de pesquisa. É um algoritmo de busca antagônico usado comumente para jogar à máquina em jogos para dois jogadores (jogo da velha, xadrez, ir etc.). Ele para de avaliar completamente uma jogada quando pelo menos uma possibilidade foi encontrada que prova que a jogada é pior do que uma jogada examinada anteriormente. Tais movimentos não precisam ser avaliados mais. Quando aplicado a uma árvore minimax padrão, ele retorna o mesmo movimento que o minimax faria, mas remove galhos que possivelmente não podem influenciar a decisão final.