Primeira vez aqui? Seja bem vindo e cheque o FAQ!
x

Como usar backtracking para implementar o algoritmo do Hexapawn Educable Robot (HER)?

+2 votos
53 visitas
perguntada Abr 24 em Programação Computacional por Stuart Mill (1,099 pontos)  

Considere a seguinte modificação do xadrez, em que o tabuleiro é 3x3, com 3 peões na linha de cima e de baixo conforme a imagem abaixo. Considere que o jogador humano sempre começa com as peças brancas. A movimentação do peão é a mesma do xadrez (não existe en passant nem promoção de peão).

A imagem será apresentada aqui.

  • Vitória no jogo: A vitória no jogo se dá por:

    1. Avançar um peão até a terceira linha.
    2. Capturando todos os peões inimigos
    3. Alcançando uma posição tal que o adversário não possa mais se mover.

O aprendizado do HER foi proposto inicialmente com caixas de fósforo e pedrinhas coloridas. A cada uma das possíveis configurações do jogo corresponde uma caixa de fósforo. A cada caixa de fósforo correspondem as ações legais que a HER pode tomar nesse cenário. A figura abaixo apresenta as caixas, com o número associado da rodada em que o cenário ocorre (a rodada um é a primeira jogada do humano, a 2 é a primeira jogada da HER, etc.). Cada setinha indica uma das possíveis ações legais da HER. Note que a situação em que o humano faz a abertura à direita é simétrico ao caso da abertura da esquerda, e portanto é ocultado.

A imagem será apresentada aqui.

Para decidir a jogada da HER, toma-se uma pedrinha aleatória (uma ação) para cada cenário possível em que a máquina seja chamada a jogar.

  • Aprendizado: O aprendizado da HER se dá da seguinte forma:
    a. HER vence -> Recolha todas as pedrinhas de volta à caixa de onde vieram.
    b. HER perde -> Remova a pedrinha da ÚLTIMA JOGADA DE HER (a ação imediatamente anterior a sua derrota).

  • Sugestão de problema: Implemente o jogo de Hexapawn com o HER. Monitore o desempenho de HER em termos de vitórias após alguns jogos.

Fontes:
https://en.wikipedia.org/wiki/Hexapawn
The Unexpected Hanging and Other Mathematical Diversions, by Martin Gardner (capítulo 8)

Compartilhe

Entre ou cadastre-se para responder esta pergunta.

...