ARTIGO 349 (ANO I, Nº 34. DE 23 A 30 DE SETEMBRO DE 2010) - Como funcionam os computadores de xadrez: O diagrama da árvore de três níveis.

PESQUISADO E POSTADO, PELO PROF. FÁBIO MOTTA (ÁRBITRO DE XADREZ).

REFERÊNCIA:
http://informatica.hsw.uol.com.br/computadores-de-xadrez2.htm

O diagrama da árvore de três níveis

O diagrama a seguir mostra uma árvore de 3 níveis que parece apresentar movimentos planejados e avalia o valor da posição final do tabuleiro:

O computador está representado como o jogador branco. O jogador preto se movimentou e deixou a posição no tabuleiro no topo da árvore. Nessa árvore, o branco pode fazer 3 movimentos possíveis. De cada um desses 3 movimentos possíveis, o preto pode fazer também 3 movimentos possíveis. De cada uma dessas 9 posições possíveis, o branco pode fazer 2 movimentos possíveis, na realidade, o número total de movimentos de qualquer posição é 20 ou mais, mas seria difícil desenhar.

Para decidir o que fazer, o computador olha para esta árvore e trabalha de baixo para cima. Seus cálculos são preparados e, portanto, descobre as melhores posições do tabuleiro de cada uma das posições possíveis que o preto irá tomar (máximo):

Um nível acima significa que o preto vai escolher a pior posição possível para o branco (mínimo):

Finalmente, leva o máximo do topo dos 3 números: 7. Esse é o movimento que o computador vai fazer. Uma vez que o preto se movimenta, o computador caminha por todo o processo outra vez, formando uma nova árvore e avaliando todas as posições do tabuleiro para descobrir qual é o próximo movimento.

Esse aproximação é chamada de algoritmo minimax porque alterna entre o máximo e o mínimo à medida que se move para cima da árvore. Aplicando uma técnica chamada poda alfa-beta, o algoritmo pode se movimentar duas vezes mais rápido e consome muito menos memória. Como você pode ver, esse processo é completamente mecânico e não envolve raciocínio. É simplesmente o cálculo da força bruta que aplica uma função de avaliação de todas as posições do tabuleiro possíveis numa árvore com um certo conhecimento.

O que é interessante é que esse tipo de técnica funciona muito bem. Num computador rápido o suficiente, o algoritmo pode ver longe o suficiente para jogar uma partida muito boa. Se você adicionar técnicas de aprendizado que modificam a função de avaliação baseada em jogos passados, a máquina pode melhorar cada vez mais.

A chave é saber, entretanto, que nada se compara ao raciocínio humano. Quando aprendermos como o raciocínio humano funciona e criarmos um computador que usa essas técnicas para jogar xadrez, então será incrível.