Ensaio sobre Heurísticas em Engines de Jogos de Lógica I

[Pt-BR]

RESUMO (clique para lê-lo) 

Este artigo foi, em suma, inspirado na ideia de fazer a máquina vencer um humano em seu próprio jogo. Esta ideia serve para jogos que se enquadram na definição de atividade intelectual. São exemplificadas as formas de representação virtual do tabuleiro com arrays e do jogo em si com árvores. Cada nó contém um estado possível do jogo; cada turno leva a um novo nó. As folhas são os diversos fins de jogo.

O computador analisa cada posição do array, vê quais os possíveis movimentos e qual tem maior prioridade. Os algoritmos de busca mais básicos comparam os nós-folha para decidir o melhor caminho. Entretanto a árvore pode facilmente crescer além do suportável pela memória do computador. Alguns aprimoramentos em heurísca são apresentados. E mesmo com a atual tecnologia, ainda surgem problemas computacionais.

1. INTRODUÇÃO

Jogos que requerem um processamento lógico são, não só saudáveis à mente humana, mas como um bom campo para se desenvolver e testar técnicas que simulam o pensamento humano ou que até tentam superá-lo. Go, Damas, Sudoku, Jogo da Velha e em especial o Xadrez, são desafios com regras próprias, um espaço finito e objetivos definidos. Apesar de alguns apresentarem-se mais dinâmicos que outros, todos requerem um mínimo de raciocínio para se atingir o objetivo[1].

A implementação de Inteligência Artificial nesta área procura simular em uma máquina os métodos de resolução já conhecidos por seres humanos, otimizá-los e possivelmente desenvolver outros para então fazer a máquina superar seu criador em seu próprio jogo.


1.1. Atividade Intelectual

Quanto maior a complexidade do jogo, computadores tendem a jogá-lo de uma forma mais divergente da que os humanos costumam usar. Os primeiros programas desenvolvidos, por exemplo, faziam uso apenas da força bruta. Até hoje, os computadores só se baseiam nas regras que lhe são dadas, no atual estado do tabuleiro e nas possíveis jogadas. O que falta no computador em relação a um humano é a capacidade intuitiva. A grande maioria de derrotas por parte das máquinas quando jogando contra uma pessoa se deve ao fato de não ser possível sintetizar a forma de raciocínio de enxadristas.

Memorável partida de duas grandes mentes

"Uma atividade intelectual onde procedimentos de heurística e processo de aprendizagem possuem papéis importantes" é definida, segundo Samuel[2], por cinco características básicas:

• Deve haver um objetivo definido.
• A atividade não pode ser determinística, ou seja, não pode ter uma única solução a ser aplicada. As regras de interação devem ser claras e conhecidas.
• É necessário um conhecimento prévio, com o qual se comparará o progresso na atividade.
• Ela deve ser familiar a uma quantidade significativa de pessoas. 

Xadrez, Damas, Go e até o Jogo da Velha se encaixam na descrição acima. Sudoku, por sua vez, serve de contra-exemplo para o segundo tópico. Apesar de satisfazer as outras características, Sudoku possui apenas uma solução. Dado um desafio, o resultado do final do "tabuleiro" será sempre o mesmo. Por outro lado, os outros jogos permitem jogadas variadas e diversos resultados. Isto ocorre com mais intensidade no Xadrez, dada a a variedade de peças, suas respectivas regras de movimento e jogadas especiais.

--

1. David Gleich, "Machine Learning in Computer Chess: Genetic Programming and KRK", Harvey Mudd College, May 13 2003. Available: http://www.stanford.edu/~dgleich/publications/MachineLearningCompChess.pdf
2. Ben P. Walls, Beautiful Mates: Applying Principles of Beauty to Computer Chess Heuristics, 1997, ISBN 1-58112-009-5