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
254 visitas
perguntada Abr 24, 2019 em Programação Computacional por Stuart Mill (1,419 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, 2020 por anônimo  
Achei muito interessante esse exercício. Você tem outra referência a ele além do site da Wikipédia?
comentou Mar 3, 2020 por Stuart Mill (1,419 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.

...