Turing Machine

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.

Como sabem os nossos leitores mais atentos, andámos aqui uns tempos às voltas com os robots que jogam futebol (séries RoboCup 2004 e Robótica Portuguesa). O que nos interessa é a problemática da inteligência artificial nas suas várias vertentes. Agora vamos virar-nos para outro aspecto desse mundo: o xadrez dos computadores. Para começar damos um conselho, que se insere na nossa militância por não deixar cair no esquecimento as pérolas da blogosfera. O conselho é: comecem por ler entradas de outros blogues que, apesar de serem mais antigas, interessam muito a este tema. Depois trataremos aqui de alargar o nosso contributo para a problematização do tema. Assim sendo, sugiro para começar:

No Abrupto:
Máquina/Homem (17-11-03);
Máquina/Homem 2 (18-11-03);
Máquina/Homem 3 (18-11-03);
Máquina/Homem 4 (19-11-03).
Como de costume no Abrupto, grande parte da animação resulta de leitores que colaboram (alguns com informações interessantes, outros na busca da glória efémera de serem citados pelo político-literato). Neste caso há sugestões interessantes (e ligações para outros blogues) com pertinência para esta questão.

No Em Expansão Vertiginosa (que, embora desactivado, deve continuar a ser consultado):
Homem vs. Máquina no Xadrez (18-11-03)

No cyberiade: histórias cibernéticas, uma série que vai muito para além desta questão concreta, mas que pode despertar alguns para a questão mais geral da inteligência das máquinas.
Ciência... Finalmente: Máquinas inteligentes?
Máquinas inteligentes II (Redes Neuronais)
Máquinas inteligentes III (Computação Evolutiva)
Máquinas inteligentes IV (O Cérebro)
Máquinas inteligentes V (O significado)
Máquinas inteligentes VI (Uma máquina inteligente tem de ser sub-simbólica)
Máquinas inteligentes VII (Princípios para construir uma máquina inteligente)

Embora em língua inglesa, valeria a pena seguir uma sugestão do A aba de Heisenberg, lendo um artigo em cinco partes, assim:
I - Have chess computers surpassed the strongest grandmasters?
II - Are chess computers improving faster than grandmasters?
III - What does the future hold for grandmasters against computers?
IV - How (not) to play chess against computers…
V - Are you a betting man (or machine)?

Bom, com todo este material estão em condições de discutir o que eu aqui direi nos próximos dias...

No número 4 da série HIPERTEXTO (que publico simultaneamente na Turing Machine e na Abébia Vadia), que versava Blogues de Ciência e Filosofia, prometi: Um dia destes continuarei esta leitura chamando a atenção para alguns posts que apareceram nestes blogues e que considero serem bons exemplos de reflexão sobre a ciência. Aqui estou a dar seguimento a essa ideia. E assim começo outra série: Filosofia e Ciência na Blogosfera. Começo por dar um esquelético roteiro para um debate que envolveu recentemente três colegas da blogosfera portuguesa: A aba de Heisenberg, Meia Livraria e No Mundo.

A 10/04/04, A aba de Heisenberg publicou uma entrada intitulada A codificação do gosto humano e a criação musical automática. Nesse texto, fazia a seguinte afirmação: Os computadores ultrapassaram os humanos em tarefas mentais como jogar xadrez.

A 16/04/04, o Meia Livraria, um tanto escandalizado com essa afirmação, ripostou no texto Pobre Heisenberg! , no qual afirma, nomeadamente: Existem certos programas de computador que ganham certas partidas a certos homens, tal como existem certos homens que ganham partidas a certos programas de computador. (...) Ou seja, nada de conclusivo. E ainda que estivesse (repito: não está) decidida a supremacia desportiva da máquina, existe no Xadrez um conjunto de valores que nunca se poderão reduzir ao aspecto desportivo, ao resultado da partida. (...) São coisas de homens, caro Nuno, não de algoritmos.

A 17/04/04, A aba de Heisenberg volta ao debate com "As coisas dos homens". Entretanto, no mesmo dia, já No Mundo publicara, sobre o mesmo tema, o texto A Mente Algorítmica. Aí se retoma um questionamento científico-filosófico do tema. O Meia Livraria não perde tempo e, ainda no mesmo dia, responde aqui.

Digo-vos eu: debate muito interessante. Além do mais, há lá comentários que vale a pena seguir e ligações para outros textos que aprofundam certos aspectos desta reflexão. Talvez ainda um dia eu me meta à estrada para dar a minha achega...
Aliás, vou meter-me já por uma encruzilhada dessa estrada: começarei aqui, muito proximamente, uma reflexão sobre o xadrez dos computadores como vertente da questão da inteligência das máquinas.

Entretanto, UM PEDIDO DE COLABORAÇÃO: por favor, sugiram-me outros "diálogos" de ciência e filosofia na blogosfera, indicando onde eles andaram, que blogues participaram, em que datas (pelo menos aproximadas) as coisas aconteceram. É claro que se indicarem os links, ainda melhor! Pois, é pedir de mais. Dirão: porque fazer isto para ele? Nesse caso publicamos nós! De acordo, então publiquem. O meu único objectivo é juntar essas peças de debate num sítio onde seja mais fácil consultá-las, mas isso não tem de ser feito só aqui. Poderia haver outras portas para esse trabalho noutros blogues, sem dúvida. Contudo, se preferirem dar-me as "dicas" e deixar que eu faça a sistematização, eu farei a minha parte. Obrigado!

É só para dizer que voltei! E que agora recomeçamos o nosso trabalho aqui na máquina. Como presente envenenado deixo-vos um olhar angustiado, que dizem ter mesmo perturbado o computador HAL de "2001 Odisseia no Espaço".