[Pt-BR]
Continuando nosso humilde artigo. Leia a primeira parte aqui: http://essaysonlogic.blogspot.com/2011/07/ensaio-sobre-heuristicas-em-engines-de.html
RESUMO (clique para lê-lo)
2. ESTRUTURAÇÃO DE DADOS
Para se começar a fazer o computador entender o jogo, é necessário virtualizá-lo. Xadrez e Damas utilizam um tabuleiro de oito linhas por oito colunas. Intuitivamente, é possível representá-lo computacionalmente com um array de 64 posições[1]. Cada posição pode conter um identificador para sinalizar se a posição está desocupada ou qual peça contém. No xadrez, normalmente utiliza-se números de -6 a 6 para se representar as peças, sendo negativos para as peças pretas, positivos para as brancas e zero para sinalizar um espaço vazio no tabuleiro. Em Go e Jogo da Velha, o mesmo é válido, porém com números variando de -1 a 1 e Damas de -2 a 2. Entretanto, o Jogo da Velha teria um array de apenas nove espaços, equanto Go pode ter tabuleiros de tamanhos variados, chegando até a dezenove por dezenove.
Uma representação alternativa do tabuleiro é na forma de string. Existem várias notações oficiais que podem ser utilizadas para descrever a posição de cada peça no Xadrez. É possível fazer codificações semelhantes para os outros jogos. Esta forma de armazenamento ocupa menos espaço em memória, mas é mais difícil e menos intuitiva de se trabalhar.
A máquina representa o desenrolar do jogo na forma de uma árvore n-ária[2]. Cada nó possui um estado possível do tabuleiro, sendo a raiz a organização inicial das peças. Os "n" filhos são dados pelas possíveis jogadas, ou seja, cada sucessor será a nova organização das peças no tabuleiro caso um determinado movimento seja escolhido. O nível da árvore equivale ao número do turno.
A Figura 4 ilustra o começo de um Jovo da Velha. Na raiz, o estado inicial, em branco. Depois há um turno do X e outro do O. Teoricamente, nem todos as possíveis jogadas estão presentes. Entretanto, é necessário notar que, neste jogo, o "ponto de vista" é indiferente, portanto, girando as imagens, tem-se as posições que faltam.
--
Continuando nosso humilde artigo. Leia a primeira parte aqui: http://essaysonlogic.blogspot.com/2011/07/ensaio-sobre-heuristicas-em-engines-de.html
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.
2. ESTRUTURAÇÃO DE DADOS
Para se começar a fazer o computador entender o jogo, é necessário virtualizá-lo. Xadrez e Damas utilizam um tabuleiro de oito linhas por oito colunas. Intuitivamente, é possível representá-lo computacionalmente com um array de 64 posições[1]. Cada posição pode conter um identificador para sinalizar se a posição está desocupada ou qual peça contém. No xadrez, normalmente utiliza-se números de -6 a 6 para se representar as peças, sendo negativos para as peças pretas, positivos para as brancas e zero para sinalizar um espaço vazio no tabuleiro. Em Go e Jogo da Velha, o mesmo é válido, porém com números variando de -1 a 1 e Damas de -2 a 2. Entretanto, o Jogo da Velha teria um array de apenas nove espaços, equanto Go pode ter tabuleiros de tamanhos variados, chegando até a dezenove por dezenove.
 |
| Figura 1: exemplo de tabuleiro |
 |
| Figura 2: representação com inteiros |
 |
| Figura 3: representação com caracteres |
Uma representação alternativa do tabuleiro é na forma de string. Existem várias notações oficiais que podem ser utilizadas para descrever a posição de cada peça no Xadrez. É possível fazer codificações semelhantes para os outros jogos. Esta forma de armazenamento ocupa menos espaço em memória, mas é mais difícil e menos intuitiva de se trabalhar.
A máquina representa o desenrolar do jogo na forma de uma árvore n-ária[2]. Cada nó possui um estado possível do tabuleiro, sendo a raiz a organização inicial das peças. Os "n" filhos são dados pelas possíveis jogadas, ou seja, cada sucessor será a nova organização das peças no tabuleiro caso um determinado movimento seja escolhido. O nível da árvore equivale ao número do turno.
A Figura 4 ilustra o começo de um Jovo da Velha. Na raiz, o estado inicial, em branco. Depois há um turno do X e outro do O. Teoricamente, nem todos as possíveis jogadas estão presentes. Entretanto, é necessário notar que, neste jogo, o "ponto de vista" é indiferente, portanto, girando as imagens, tem-se as posições que faltam.
 |
| Figura 4: Dois primeiros turnos em um Jogo da Velha |
--
- Claude E. Shannon, "Programming a computer for playing chess", Philosophical Magazine, Vol. 41, No. 314, March 1950. Available: http://archive.computerhistory.org/...computer_for_playing_chess.shannon.062303002.pdf
- AI Horizon, (2011, April). Available: http://www.aihorizon.com/essays/
2 admirable thoughts:
Tabuleiro pra mim é só Dama. D:
Tive que fazer um trabalho de programação envolvendo xadrez, quero isso longe de mim por um tempo.
Post a Comment