Programação dinâmica e jogos de tabuleiro

Programação dinâmica e jogos de tabuleiro: Um estudo Prof. Dr. Sérgio Crespo
Alexandre Nunes Barbosa
Daniel de Souza Martins [e-mail]/ [e-mail]

Dynamic programming and board games: A survey
David K. Smith

Roteiro

Introdução
Muitos artigos falam sobre a possibilidade do uso de PD (programação dinâmica), e outras técnicas, para otimização de jogos como o xadrez.
A literatura fala de técnicas de otimização utilizando matemática pura, lógica e informática.
O trabalho aborda apenas o uso da PD e a contribuição dela na investigação de habilidades lógicas necessárias para a resolução de enigmas ou para derrotar um inimigo em um jogo de tabuleiro. Estrutura













O estudo é aplicado a jogos de tabuleiro, que não exigem esforço físico, exigindo apenas esforço mental(inteligência, agilidade mental e lógica);
No decorrer do artigo são utilizados termos técnicos relacionados a PD, como: estágio, estado, decisão, política, fórmula de recorrência, dimensão, etc.
Informalmente nos jogos de tabuleiro o estágio refere-se a quantidade de possíveis jogadas, porém em alguns jogos essa quantidade é potencialmente infinita, nesses casos, o retorno da PD independe do estágio. O estado refere-se a posição em que as peças (peças, cartas ou similar) se encontram.
A decisão refere-se ao próximo movimento.
A política e a fórmula de recorrência implicam em um valor que pode ser associado ao estado e ao estágio.
A dimensão depende do jogo, e sobre a forma como se escolhe para descrever o estado.

Jogos determinísticos de um jogador - Conceito

Jogos determinísticos de um jogador – Jogos abordados

Jogos determinísticos de um jogador - Exemplo

Jogos determinísticos de um jogador - Conclusão

Jogos estocásticos de um jogador - Conceito

Jogos estocásticos de um jogador – Jogos abordados

Jogos estocásticos de um jogador - Exemplo

Jogos estocásticos de um jogador - Conclusão

Jogos determinísticos de dois jogadores - Conceito
São jogos onde