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

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

+3 votos
144 visitas
perguntada Abr 24, 2019 em Programação Computacional por Stuart Mill (1,434 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
comentou Mar 2 por Raíssa (851 pontos)  
Achei muito interessante esse exercício. Você tem outra referência a ele além do site da Wikipédia?
comentou Mar 3 por Stuart Mill (1,434 pontos)  
Raíssa, nesse livro The Unexpected Hanging and Other Mathematical Diversions você consegue encontrar uma explicação mais detalhada, e pra ver o funcionamento do algoritmo, tem esse vídeo (https://www.youtube.com/watch?v=sw7UAZNgGg8) explicando e exemplificando.

Entre ou cadastre-se para responder esta pergunta.

...