Tema


Anatomia do motor de xadrez


Motivação

O xadrez por computador é um problema de computação antigo e interessante. O estudo deste jogo começou antes da invenção do computador e foi desenvolvendo junto com o avanço da tecnologia. Mas, mesmo com a capacidade de processamento dos computadores atuais, ainda não é possível calcular toda as jogadas do xadrez em tempo limitado. Logo, devemos ter um bom algoritmo para ter um jogador forte. Neste trabalho pretendo apresentar as principais técnicas usadas nos algoritmos deste jogo.


Problema a ser estudado

Atualmente, um jogo de xadrez por computador pode ser dividido em duas partes:

  1. Busca em banco de dados.
    No início do jogo, o programa de xadrez faz uma busca no banco de dados para escolher uma jogada considerada boa por jogos anteriores. No final do jogo, existe um banco de dados que contem a jogada vencedora quando resta 5 ou menos peças. Nesta parte, não há muito que analisar.

  2. Busca na árvore.
    Depois da parte inicial, pode não existir uma jogada considerada boa no banco de dados. Então, o programa inicia uma busca na árvore. O programa escolhe a melhor folha usando alguma função de avaliação e técnicas como min-max, corte alfa-beta, algumas heurísticas e tabelas de hash. O estudo desta parte é o que deve ser feito.

Objetivos

Inicialmente, estudar as técnicas básicas para busca em árvore, heurística e função de avaliação e analisar técnicas mais sofisticadas. Depois, estudar como estas técnicas são usadas e implementadas em alguns programas de xadrez de código aberto. Finalmente, criar um texto que apresenta as principais técnicas usadas nos algoritmos para xadrez por computador e como estas algoritimos são implementadas nos programas existentes.

Principais atividades previstas e cronograma

  • Maio: Estudo da estrutura de dados.
  • Maio-Junho: Estudo das técnicas básicas. (busca em árvore, heurística, função de avaliação, tabelas)
  • Junho-Julho: Estudo das técnicas mais sofisticadas.
  • Julho-Setembro: Analisar as implementações. (GNU Chess(Fruit), Stock Fish, Pulse)
  • Agosto-Dezembro: Monografia.
  • Novembro: Pôster.
  • Novembro: Apresentação.