Turing Machine

Ali na Fundação dedicada a ela e ao marido, ao Jardim das Amoreiras, uma magnífica exposição de Vieira da Silva, com obras que nem sempre estão à mão de ver. Esta que aqui se ilustra (jogo de xadrez) é uma das que lá moram por agora. Eu prefiro qualquer uma das "bibliotecas" (das que lá estão, a que está "em fogo"), mas não encontrei imagem a condizer. É de ir. Pode-se aproveitar para namorar nos bancos do jardim, antes ou depois: é sempre uma mais-valia. (Ontem, chovia: não deu muito jeito para isso).
Incidentalmente: a história dela e do marido (judeu, húngaro) mostra bem que país era este sob o governo de Salazar.

O El País é, como se sabe, um reaccionaríssimo diário do país vizinho. Passo a resumir um texto do seu editorialista Hermann Tertsch, publicado há alguns dias.

Desde há pelo menos 20 anos que países como a Alemanha ou a Holanda tudo faziam para que os imigrantes muçulmanos não renunciassem à sua cultura. Tudo o que não fosse nesse sentido era considerado racista e xenófobo. Nessa linha, racistas eram os que pugnavam por um esforço de integração por parte dos imigrantes. Os partidos democráticos desinteressaram-se do problema. As elites pregavam a tolerância, mesmo com os intolerantes.

Foi preciso o assassínio de Theo van Ghog para que se afundasse a grande mentira. Na Holanda contam-se já vinte atentados anti-muçulmanos desde aquela morte. Em França, os jovens muçulmanos são a ponta de lança do anti-semitismo europeu. Há pouco tempo o Der Spiegel publicava um dossier acabrunhante sobre os maus-tratos, as torturas e os sequestros que sofrem milhares de mulheres no seio das suas famílias na Alemanha. Em certos países europeus há bairros onde já não se aplica a Constituição, mas a sharia. Tal como em muitos lares.

Seria cruel dizer que merecemos as consequências do nosso relativismo. Mas temos uma responsabilidade evidente: o nosso erro não foi o de exercer os nossos direitos, mas sim o de não os fazer respeitar. Tanto repetimos ao longo dos anos que todas as ideias são boas, que acabámos por convencer disso aqueles que matam e morrem por valores diametralmente opostos aos nossos.
Convém sempre lembrar que a imensa maioria dos imigrados muçulmanos na Europa são gente de bem. E que há muitos indesejáveis “cristãos”. Mas a polícia holandesa calcula que 5% dos imigrantes muçulmanos nesse país são fanáticos preparados para a violência. Isto é: 50.000.

E que tal um combinação inteligente de firmeza e tolerância, a par com a consciência dos perigos que realmente corremos?

Madrid, princípios de 1987. Visita ao Casón del Buen Retiro, dependência do Museu do Prado. Vamos ver "Guernica", de P.R. Picasso. (Não se trata aqui, pois, da visita a Guernica, que acontecerá anos depois.) É um óleo sobre tela. Medindo 350x780 cm, é um verdadeiro mural.
De uma textura aparentemente simplista, esta obra não utiliza a cor, mas somente o preto, o branco e o cinzento que resulta da sua combinação. A pintura é plana: os olhos de animais e pessoas aparecem de frente em rostos de perfil, mostram-se visíveis elementos corporais que deveriam estar encobertos devido à posição do corpo. Formalmente, a composição carece de perspectiva, cabendo ao espectador a tarefa de lha dar.
Várias propostas existem para a leitura formal desta obra. De entre as possíveis, uma primeira leitura organiza-a em três grandes fragmentos verticais. O primeiro é o da criança morta nos braços da mãe, deixando cair a cabeça para a mão da estátua de guerreiro derrubado. O segundo fragmento é o central: é dominado pelo cavalo relinchante e por duas fontes de luz muito distintas, apresentando-se uma como uma brecha/explosão agressiva e a outra serenamente na mão de uma mulher. O terceiro fragmento é o das mulheres olhando para "o que se não vê mas também já não importa ver" - mulheres talvez periféricas ao centro da composição.
Uma segunda leitura assenta na percepção de um complexo de espaços triangulares, uns sobrepondo-se por serem muito visíveis e marcados, outros mais discretos e mais reflexivos.
Uma terceira leitura de entre as possíveis é a que organiza toda a composição como girando em torno do cavalo relinchante, que seria o centro da obra.
No mesmo local onde está exposta a "Guernica" podemos observar também dezenas de trabalhos preparatórios (alguns deles coloridos, ao contrário do produto final). Desses trabalhos preparatórios ressaltam como tendo sido mais problemáticos na composição os elementos "cavalo" e "cabeça de mulher".
Este vasto conjunto de estudos que prepararam a "Guernica", expostos ali no mesmo local que a própria obra, abrem uma interessante possibilidade de exploração das intenções do próprio Picasso aquando da composição, nomeadamente das vias que abriu e depois fechou no trabalho final, bem como também do que surgiu no produto final tendo estado arredado dos estudos preparatórios. Ou não?

Uma parte das razões que me levaram a andar desaparecido daqui estão relacionadas com o facto de ter andado "aparecido" por outros lados. Relatório e contas podem encontrar-se no seguinte atalho: Na Terra do Grão Mogol.

Guernica, pequena cidade da Biscaia espanhola, é considerada a pátria das liberdades vascas: era diante do seu famoso carvalho que os monarcas espanhóis ou os seus representantes costumavam fazer jurar respeitar os direitos vascos.
A 26 de Abril de 1937, segunda-feira, dia de feira, a cidade a 30 Km da frente da guerra civil espanhola, dezasseis horas e quarenta e três minutos. Inicia-se um bombardeamento aéreo pelos partidários de Franco, que terminou às dezanove horas e quarenta e cinco minutos. Tinham então morrido mais de milhar e meio de pessoas e muitas outras ficado feridas. O Parlamento Vasco e o famoso carvalho ficaram intactos.
Os bombardeiros eram da Alemanha então dirigida por Hitler e o próprio bombardeamento veio a ser considerado uma experiência a pensar na Guerra Mundial que se lhe seguiu.
Os "nacionalistas" espalharam inicialmente o boato de que tinham sido os próprios vascos a incendiar a cidade. Dois dias depois os franquistas ocuparam a cidade.
Picasso, que no princípio desse ano tinha recebido do governo da República Esponhola o encargo de pintar um mural para o pavilhão espanhol da Exposition Internationale des Arts et Techniques dans la Vie Moderne (Paris 1937) e que se encontrava indeciso quanto ao motivo a escolher, decidiu consagrar tal mural à destruição de Guernica, como representação dos horrores da guerra. O quadro "Guernica", que daí resultou, é por muitos considerado como a obra prima de Picasso.

Exactamente de hoje a um mês, dia por dia, faz um ano que este blogue começou. "Este blogue" como realidade editorial, que não como realidade técnica. Como realidade técnica, o Turing Machine vive ao mesmo tempo no servidor Blogspot e no servidor do Paulo Querido. E não nasceu no mesmo dia nos dois espaços. Mas nasceu como ideia exposta ao olhar público a 24 de Outubro de 2003.
Vou comemorar (que pretensão) essa passagem de um ano. Do seguinte modo. Eu tenho uma ideia de qual o "post" que, individualmente considerado, considero o melhor deste blogue. Quererão os leitores dizer-me qual dos posts deste blogue consideram o melhor? Aquele leitor que, até 24 de Outubro me indicar (nos comentários a esta entrada) qual o post que considera o melhor e coincidir com a minha opinião nesse ponto, receberá uma lembrança enviada por mim. Não há júri, têm de confiar em mim. Não digo qual é o prémio (mais uma vez, têm de confiar em mim).
Se nenhum leitor coincidir com a minha secreta opinião, escolherei de entre todas as respostas aquela que, não sendo a minha, mais se aproximaria de ser a minha.
Para participar é favor deixar, nos comentários a esta entrada, a data e o título do post que consideram. Deixem qualquer forma de serem referenciados, embora eu tencione acertar os pormenores da entrega por e-mail restrito com o "vencedor".
Vá lá, participem da minha festinha...

(Este post foi escrito a 24 de Setembro de 2004, mas vai datado de 24 de Outubro para ficar "à tona" durante o período deste passatempo.)

Antes eram as ilusões dos filósofos. Hoje, os cientistas arrogantes acreditam que as ilusões só acontecem aos outros. Que só os outros vêem no mundo o que só existe na sua mente. E, na verdade, se a história ensina alguma coisa, vêem claramente visto o que amanhã outros verão como claramente não visto. Enfim.

Em 1950, Alan Turing propôs o "jogo da imitação": seria um computador capaz de imitar um humano na capacidade de dar respostas a um questionário escrito, de tal modo que outro humano não distinguisse a máquina do homem? Turing "apostou" que, em 2000, um interrogador humano médio não teria mais do que 70% de hipóteses de fazer uma identificação correcta após 5 minutos de interrogatório.

No futebol robótico há uma aposta parecida, formulada pelos investigadores japoneses Asada e Kitano em 1999: "Até meados do século XXI, uma equipa de robots humanóides baterá a equipa humana campeã do mundo de futebol, segundo os regulamentos oficiais da FIFA."

A pergunta que deixamos, a concluir, é: quererá o futebol robótico, na procura de ganhar a sua aposta para 2050, usar o mesmo tipo de "truque" que está na base do xadrez computacional? O futebol robótico considerará que ganhou a sua aposta se, obtendo vantagem sobre os humanos, ela resultar de uma combinação de "doping tecnológico" (máquinas com desempenho físico desproporcionado face aos humanos, o tipo de vantagem que os atletas podem obter ingerindo substâncias químicas) com transferência directa de conhecimento humano para a máquina por via dos seus programadores? Ou, pelo contrário, o futebol robótico aceita o desafio específico de exigir dos robots o desenvolvimento autónomo de comportamentos colectivos, de equipa, como chave do eventual sucesso da sua aposta? Neste sentido, trata-se de saber se a robótica colectiva é apenas "mais do mesmo" ou se efectivamente aceita o desafio de pensar o social como factor de inteligência.

Temos vindo a mostrar que os recursos do computador e do humano, no jogo do xadrez, são muito diferentes. Esse facto é especialmente relevante se o conjugarmos com a compreensão de que há diferenças notáveis entre a forma como os humanos e os computadores "jogam xadrez".

A força dos computadores é uma função da capacidade para não cometer erros, enquanto a força dos seus oponentes humanos consiste em propor problemas que não estejam previstos pela função de avaliação. Os humanos não avaliam posições por busca exaustiva, mas com base em padrões visuais e conceitos abstractos retirados da experiência. Além disso, os grandes jogadores não se limitam a reconhecer padrões, também revelam padrões nunca antes observados.

Ainda mais: os humanos, especialmente nos finais de partida, usam uma abordagem teleológica: visualizam o tipo de posição que querem atingir e é nessa base que definem a táctica pela qual orientam os lances (não começam por analisar jogada a jogada). O humano "imagina" uma posição a atingir, enquanto o computador só identifica como desejável uma dada posição em resultado do cálculo de variantes. A situação é muito diferente do lado da máquina que é posta a jogar xadrez. Como sintetiza Amorim: "A rigor, os programas de xadrez não planejam. Ao invés disso, eles procuram por soluções contingentes, como se cada posição que ocorre durante uma partida fosse um novo problema a ser resolvido" (Amorim 2002:71. Para o conjunto do argumento, ver também pp. 69-81).

Um dos nomes importantes da IA, John McCarthy, assinala, a este propósito: "o facto de que este nível de jogo requeira milhões de vezes mais cálculos do que os realizados por um jogador humano é uma medida do nosso entendimento limitado dos princípios da inteligência artificial." Parece, pois, natural que acrescente: "os torneios deveriam admitir apenas programas com limites rigorosos em termos de capacidade computacional. Isso faria com que a atenção [dos investigadores] se concentrasse nos avanços científicos".

Isto suscita a questão: poderá o futebol robótico, na procura de ganhar a aposta para 2050, usar o mesmo tipo de "truque" que está na base do xadrez computacional?

(continua)

A forma de projectar as heurísticas (de que falámos na entrada anterior) mostra claramente que elas contêm uma grande quantidade de conhecimento humano embutido. Os programas de xadrez incorporam normalmente módulos (para além do "motor") que constituem claramente formas de conhecimento embutido. Muito conhecimento acumulado historicamente pelos humanos é introduzido nos programas de xadrez sob várias formas: bibliotecas de aberturas, bibliotecas de finais, livros de partidas.
As "bibliotecas de aberturas" são vastas colecções de caminhos de jogo entre o início da partida e, digamos, o vigésimo lance, permitindo que nessa fase o programa, em vez de analisar as posições, as recupere directamente da memória, onde já se encontram avaliadas.
As "bibliotecas de finais" são similares (embora muitas vezes assentes em análise inversa, assim: toma-se uma posição de xeque-mate e elaboram-se múltiplas linhas de jogo daí para trás; no decorrer de uma partida, alinha-se o jogo em curso com um dos desenvolvimentos previamente estudados).
Os "livros de partidas" são registos de partidas históricas. O livro de partidas do Deep Blue continha 700.000 partidas de grandes mestres registadas lance a lance.
Um "livro de partida alargado" contém um resumo de informação sobre as jogadas dessas partidas, de tal modo que, se certa jogada possível na posição actual da partida em curso já ocorreu numa partida registada, o programa vai indicar a sua "qualidade" segundo uma série de parâmetros históricos, entre os quais: se participou numa vitória ou numa derrota, se o recurso a essa jogada é recente ou antigo (um uso recente indicia conformidade com os avanços teóricos), a frequência com que essa jogada foi usada e qual a categoria do jogador que a utilizou (em princípio um jogador de mais alto nível comete menos erros). Ponderados todos esses factores, essa jogada pode ser aplicada naquele caso, a menos que o programa descubra naquele momento uma alternativa melhor.
Vemos, então, que a força competitiva dos programas de xadrez resulta de uma combinação de força bruta com heurísticas e grandes bases de dados. Em situações em que é difícil aplicar heurísticas relevantes (por exemplo, com poucas peças em jogo), recorre-se a grandes bases de dados associadas à força bruta. Em longas sequências de variantes forçadas ("sequências de variantes forçadas" são situações em que uma determinada linha de jogo, face a toda a teoria xadrezística aplicável àquele posicionamento das peças, é claramente muito mais razoável e compensadora do que qualquer outra alternativa) - dizia, em longas sequências de variantes forçadas o que domina é a força bruta; em situações mais fluidas prevalecem as heurísticas.
Dada a quantidade de conhecimento humano embutido numa máquina de jogar xadrez, torna-se fácil de compreender que a equipa do Deep Thought (um antecessor do Deep Blue) tenha afirmado, acerca das expectativas para o confronto com um campeão humano, que "o resultado não vai revelar se a máquina pensa, mas se um esforço humano colectivo pode suplantar os maiores feitos dos seres humanos mais capazes". Murray Campbell, uma das inteligências humanas na base do Deep Blue, escreve que "os jogos da base de dados representam um consenso aproximado, desenvolvido ao longo de décadas de jogo" - isto é, mais uma vez, saber humano acumulado.

Dadas as limitações da "força bruta", de que falámos no ponto anterior, o xadrez computacional tem de recorrer a heurísticas. As heurísticas são critérios gerais de análise que indicam onde será provável encontrar os factores críticos na dinâmica do jogo, para que esses possam ser explorados aprofundadamente sem perder tempo a analisar todas as combinações legalmente possíveis. A implementação das heurísticas começa pela definição dos aspectos a serem avaliados com base em padrões de posicionamento das peças; continua com a criação de algoritmos para reconhecer tais padrões; passa para a definição do peso que cada factor terá na avaliação global. A função de avaliação posicional materializa todo o processo, definindo como será atribuído um único valor numérico a cada posição com base em todos os elementos considerados. O Deep Blue II usava uma "função de avaliação rápida" (para os aspectos mais relevantes e mais fáceis de identificar) e uma "função de avaliação lenta" (para os aspectos mais subtis): se a primeira desse um resultado muito claro, a segunda era dispensada.

Tudo o que possa ser importante e não esteja previsto ou esteja subvalorizado na função de avaliação torna-se "invisível" para o computador de xadrez. As situações de maior risco são as posições instáveis, aquelas em que o balanço material ou posicional pode ser alterado abruptamente: um rei está em xeque, uma peça foi tomada, há peões avançados na sexta ou sétima linha (um peão que atinja a oitava linha pode ser "promovido" a uma peça à escolha do jogador, constituindo assim uma forte ameaça).

O que acontece é que a distinção entre posições mais ou menos desejáveis é em geral pouco clara. Por exemplo, os peões dobrados. "Peões dobrados" são peões da mesma cor que ocupam uma mesma vertical do tabuleiro, tendo assim pouca mobilidade e sendo facilmente atacados e bloqueados. São, em geral, um ponto fraco. Mas podem, em certos casos, ajudar a controlar o centro do tabuleiro.

Amorim (2002:70-72) identifica vários tipos de posições que enganam sistematicamente os programas de xadrez. Um caso é a incapacidade do programa para distinguir entre uma troca de peças desfavorável e um "sacrifício". (Chama-se "sacrifício" à entrega deliberada de uma peça em troca de uma vantagem posicional, relevante mas por vezes subtil e cujo valor só se revelará mais tarde e em função da situação concreta do jogo.)

Outro caso é o de uma peça "encravada". "Encravada" está uma peça que não pode deixar a casa onde se encontra, porque se o fizer expõe uma peça de valor superior - que está a proteger por interposição - a captura. Se a peça exposta a ameaça é o rei, retirar a peça "encravada" é ilegal. Noutros casos, a peça encravada pode sair, mas com perda grave de material. Assim, uma peça encravada está na prática reduzida à condição de "muro" contra uma ameaça do adversário, mas um programa de xadrez normalmente considera-a em termos formais como se ela continuasse a poder agir sobre várias casas do tabuleiro.

Outra situação ambígua para um programa de computador é a de uma cadeia de peões fechada. Uma "cadeia de peões fechada" é uma estrutura de peões que se protegem mutuamente e que têm um efeito de barreira, dividindo o tabuleiro em dois campos (todas as peças do adversário estão do outro lado da barreira e não podem furá-la), de tal modo que o rei da mesma cor fica inacessível às peças de que dispõe o adversário. Ora, perante uma cadeia de peões fechada acontece que as jogadas de preparação para uma ruptura vantajosa parecem inofensivas ao computador, porque os seus efeitos estão para lá do seu horizonte de análise.

É para incorporar conhecimento deste tipo numa heurística que se recorre à experiência e sensibilidade de mestres xadrezistas humanos que identifiquem indicadores de desequilíbrio.

Um papel que me caiu nas mãos conduziu-me à inevitabilidade de tratar aqui um assunto menos "científico" e mais "social" (ou será "político"?).

O Professor João Caupers, Director da Faculdade de Direito da Universidade Nova de Lisboa, distribuiu aos seus alunos de Direito Administrativo I neste ano lectivo de 2004/2005 uma nota introdutória que merece aqui um destaque.

O Prof. Caupers sublinha o "nível de exigência muito elevado" que se pratica na disciplina. Isso é bom. E avança a prova desse traço: "os elevados níveis de reprovação (entre 33 e 44%) aí estão como testemunho de tal nível de exigência". Lindo! Em qualquer escola decente, esses níveis de reprovação obrigariam o professor a explicar o que é que funcionou mal, exigiriam uma análise à qualidade pedagógica da actividade docente - até se concluir de que lado estaria o defeito. Neste caso, o Prof. Caupers, não contente com gabar-se desses níveis de reprovação, considera que isso é um indicador da exigência da disciplina. Isso quer dizer que as outras disciplinas da mesma faculdade têm um nível de exigência insuficiente, só porque não chumbam tanto? Aliás, o Prof. Caupers tem uma forma fácil de melhorar a avaliação da sua disciplina: reprova mais alunos e está feito. Nem precisa de fazer nenhum esforço para ser melhor professor. Basta reprovar mais alunos. E chega.

Depois, o Prof. Caupers escreve que "estudar é uma actividade penosa, que exige esforço, trabalho e espírito de sacrifício". Eu concordo que estudar exige esforço e trabalho - e até espírito de sacrifício. Mas "estudar é uma actividade penosa"? Eu, por mim, sempre gostei de estudar - e continuo a gostar. Por isso não compreendo que um professor universitário diga aos seus alunos que estudar é uma actividade penosa. Contudo, se para o Prof. Caupers estudar é uma actividade penosa, compreendo o motivo de tanto fel na sua escrita: depois de tantos anos a exercer uma actividade tão penosa, ficou definitivamente marcado pelo ferrete de tanto sofrimento e agora descarrega sobre os seus alunos. Que pena que se diga aos estudantes que estudar é uma actividade penosa...

Mas o Prof. Caupers ainda oferece outra pérola. Escreve, no capítulo da "Boa educação": "Os estudantes tratarão as estudantes com a gentileza adequada: a igualdade entre mulheres e homens não justifica o tratamento das primeiras sem a devida deferência". Dizem-me que o Prof. Caupers, em certas situações, obriga os alunos a deixar as alunas entrarem primeiro na sala de aula. Deve ser dentro do mesmo princípio, que ele inclui na "boa educação", e que não passa de machismo mal encapotado. Não terão as estudantes a mesma obrigação de respeitar os estudantes?

Caramba. Isto passa-se na Faculdade de Direito de UNL, que é provavelmente o que entre nós há de melhor no ramo. Se calhar sou eu que estou fora de moda, mas, para o meu critério, um professor que só é capaz de disciplinar a sua disciplina com estes meios, está fortemente necessitado de ser submetido a provas de aptidão pedagógica. Com urgência.

Escrevemos antes que a Inteligência Artificial entende um jogo de xadrez como um problema de busca ou exploração do espaço de estados. Vejamos algo mais concreto sobre a implementação desse entendimento.
O elemento básico de um típico programa de xadrez para computador é o "motor", constituído por três módulos: um gerador de jogadas (especifica todos os lances legais a partir de uma dada posição), um calculador de variantes (especifica os caminhos que o jogo pode tomar - sucessões de lances e contra-lances - contando com as respostas do adversário), um avaliador de posições (distingue posições mais e menos promissoras e perigos associados).
A via que muitos autores consideram privilegiada para o xadrez computacional é a "força bruta", isto é, o recurso intensivo à capacidade de processamento da máquina para realizar cálculos exaustivos. Em termos puramente lógicos, a abordagem por busca exaustiva é simples: para cada posição são determinadas todas as sequências de jogadas legais que podem seguir-se, contando passo a passo com todas as respostas possíveis do adversário, e escolhe-se a linha de jogo que leva mais seguramente ao estado final desejado (vitória) ou a uma posição intercalar favorável, assumindo que o adversário fará em cada momento o melhor lance à sua disposição. Por isso, o factor Nps ("nós por segundo", nodes per second, número de posições diferentes analisadas por segundo) é muitas vezes considerado a principal medida da força de um computador de xadrez. Essa força, para um mesmo programa, varia com o poder de cálculo da máquina. O problema é que, havendo no xadrez um número astronómico de posições legais e respectivas combinações em jogos válidos, a busca exaustiva torna-se impraticável. Calculou-se que uma análise exaustiva que antecipe uns meros cinco lances requer a análise de 600. 000.000.000.000 posições. O Deep Blue II levaria cerca de 820 horas a fazer essa análise.
Temos, portanto, sérias limitações ao mero uso da força bruta. Então, que fazer? No próximo capítulo falaremos das heurísticas.

Do lado das máquinas, o herói desta história é o Deep Blue. Que objecto era esse?

O Deep Blue, o "computador xadrezista", era (hardware e software) concebido especificamente para derrotar um humano num jogo de xadrez - recorrendo para isso a meios extraordinários. O Deep Blue II (usado no segundo encontro com Kasparov) tinha 30 GB de memória RAM, 120 GB em unidades de disco, 30 microprocessadores de uso geral e 480 processadores específicos para optimizar as buscas no jogo de xadrez, trabalhando em paralelo. Com este poder, analisava em média 200 milhões de posições por segundo. Enquanto os xadrezistas humanos de topo analisam, em cada jogada, no máximo cem ou duzentas posições, o Deep Blue podia analisar muitos biliões.

Depois de termos andado nos robots que jogam futebol, recuamos no tempo e passamos para os computadores que jogam xadrez.
O ano de 1997 é, simultaneamente: o ano em que pela primeira vez um computador (Deep Blue II) vence um campeão mundial de xadrez em título (Kasparov) num encontro (série de partidas) em condições tradicionais de torneio; o ano em que tem lugar a primeira edição do RoboCup (campeonato mundial de futebol robótico). Note-se, de passagem, que o Deep Blue I já tinha ganho a Kasparov uma partida num encontro que tinham disputado no ano anterior. Vamos então começar por uma rápida comparação entre futebol e xadrez do ponto de vista do nosso interesse pelas relações entre o homem e a máquina - e a inteligência.
Há diferenças muito significativas entre os desafios que o xadrez e o futebol colocam à Iinteligência Artificial. O futebol depende essencialmente das leis físicas que regem o mundo material: factores como o peso e o tamanho da bola, o tamanho do campo, o piso de jogo ou as dimensões da baliza influenciam decisivamente as características do jogo. Esses jogos dependem de certos movimentos característicos dos atletas. O xadrez, pelo contrário, não depende em nada essencial do suporte físico: há até quem jogue xadrez "às cegas" (sem tabuleiro e sem qualquer auxiliar, retendo na memória toda a história da partida e comunicando apenas a notação formal das jogadas). Nesses jogos "formais" todas as jogadas podem ser descritas de forma abstracta e inequívoca, numa notação exaustiva relativamente ao conteúdo do jogo. A única ponte entre o xadrez e as condicionantes físicas resulta do facto de uma partida, quando jogada em condições regulamentares de torneio, estar sujeita a condicionantes de tempo (um tempo máximo para um determinado número de jogadas).
Um jogo como o xadrez pode ser descrito por um conjunto de estados iniciais (arranjo das peças no início do jogo, que no xadrez é sempre o mesmo), um conjunto de estados finais (arranjos das peças que determinam o fim do jogo e o seu resultado) e um conjunto de regras que definem as jogadas legais pelas quais se passa sucessivamente de um estado para outro. O "espaço de estados" de um jogo como o xadrez é o conjunto de todos os arranjos de peças que se podem obter por uma sucessão de jogadas legais a partir do estado inicial. O xadrez é um jogo de informação perfeita (o que não acontece, por exemplo, naqueles jogos de cartas em que um jogador não conhece o jogo dos outros) e não probabilístico (sem a intervenção da sorte que interfere, por exemplo, no gamão, onde o lançamento dos dados determina uma parte da evolução). A Inteligência Artificial entende um jogo do tipo do xadrez como um problema de busca ou exploração do espaço de estados. Discutimos nos próximos capítulos alguns aspectos da implementação desse entendimento.