Diário das pequenas descobertas da vida.
Quarta-feira, 23 de Abril de 2008
O Rei vai manco

Corre o ano de 1996. Dois adversários confrontam-se num jogo usualmente sinónimo de raciocínio, imaginação, destreza mental e capacidade intelectual. Um é um relativo desconhecido, o outro é o campeão mundial. O primeiro é limitado intelectualmente, o segundo é dono de uma inteligência e cultura exemplares. No primeiro recontro, disputam seis partidas, sendo a primeira ganha pelo relativo desconhecido, enquanto outras três são ganhas pelo campeão mundial e registam-se dois empates. A vitória é do campeão mundial. Em Maio de 1997, voltam-se a encontrar o aspirante e o mestre. Desta vez, para surpresa e preocupação do mundo inteiro, o aspirante derrotou o mestre no conjunto das 6 partidas disputadas. O mestre: o campeão mundial de Xadrez Gari Kasparov. O aspirante: o ducentésimo quinquagésimo nono super-computador mais potente do mundo Deep Blue.

Tabuleiro de XadrezMas como pôde um computador ganhar a um ser humano numa actividade tão associada à inteligência e aptidão mental humanas? Terão os computadores finalmente chegado ao limiar da inteligência artificial? Estará a espécie humana prestes a ser derrubada pelas suas próprias criações? Já há muito as histórias (pois é, não me habituo/aprecio a usar o termo «estória») de Ficção Científica abordam essa possibilidade.
Ver os artigos
~
Ó AI meu bem para uma análise do filme «IA - Inteligência Artificial»;
~
Kubernates sobre a origem da palavra «ciberbética»;

Mas o que há de concreto na suposta inteligência de Deep blue, esse gigante com 1,4 toneladas curtas, as usadas nos EUA, o que equivale às nossas 1,25 ton? Será que, na verdade, o xadrez não é o jogo de inteligência e astúcia que geralmente se pensa? Ou será que esta victória é a primeira indicação da revolução prestes a acontecer? Para responder a esta questão, talvez valha a pena analisar primeiro o que é, ao certo, o xadrez.

Peças de XadrezO Xadrez é um jogo de tabuleiro, que simula um cenário de disputa militar, em que se confrontam dois adversários. É jogado num tabuleiro com 64 (8x8) quadrados claros e escuros (geralmente, mas não sempre, brancos e pretos). No início do jogo, cada adversário tem, à sua disposição e nas duas filas mais próximas de si, 16 peças jogáveis: 8 «Peões», 2 «Torres», 2 «Cavalos», 2 «Bispos», 1 «Rainha» (ou «Dama») e 1 «Rei». Por convenção, o primeiro a jogar é quem tem as peças brancas. É também um jogo em que a peça mais poderosa e influente é feminina. Tendo em conta a ancestralidade do jogo, isto é digno de nota!

As peças só podem ser movimentadas de acordo com as suas regras próprias:

~ o Peão só pode ser movido para a frente na vertical, desde que a casa esteja livre, um quadrado e, na primeira vez que é movido, pode (mas não é obrigatório) andar duas casas (ou quadrados) para a frente. Não se pode deslocar para uma casa já ocupada por outra peça excepto quando «come» a peça, o que só pode ocorrer na diagonal para a frente. Cada jogador tem oito Peões no início da partida;

~ a Torre só se pode mover na vertical ou na horizontal, quantas casas livres estiverem ao longo desse trajecto. Se houver uma peça do adversário a meio do trajecto que efectua, substitui («come») a peça adversária e fica no seu lugar. Se for uma peça da sua cor, pára na casa imediatamente anterior. Cada jogador tem duas Torres no início da partida;

~ o Cavalo move-se em «L»: 3 casas na vertical e 1 na horizontal ou 3 casas na horizontal e 1 na vertical (podendo começar por andar 1 casa numa direcção e depois 3 na direcção perpendicular a essa primeira). «Salta» por cima de quaisquer peças que estejam a meio do «L» que efectua, não as «come» mas ignora-as. Se, na casa onde termina o «L», estiver uma peça da outra cor, o cavalo «come» a peça, substituindo-a. Se estiver uma peça da mesma cor, o Cavalo não pode fazer o «L» para aí. Cada jogador tem, no início da partida, 2 Cavalos;

~ o Bispo só se pode mover obliquamente, quantas casas estiverem livres ao longo desse trajecto. Se houver uma peça do adversário a meio do trajecto que efectua, substitui («come») a peça adversária e fica no seu lugar. Se for uma peça da sua cor, pára na casa imediatamente anterior. Devido à forma peculiar como se move, um Bispo deslocar-se-á, até ao fim da partida, sempre por quadrados da mesma cor que a sua casa inicial. Para cada adversário, um dos Bispos começa (e desloca-se) em casas «brancas» e o outro em casas «pretas». Cada jogador tem dois Bispos no início da partida;

~ a raínha pode-se mover como uma torre (na vertical ou na horizontal) ou como um bispo (obliquamente), quantas casas livres estiverem ao longo desse trajecto. Se houver uma peça do adversário a meio do trajecto que efectua, substitui («come») a peça adversária e fica no seu lugar. Se for uma peça da sua cor, pára na casa imediatamente anterior. Cada jogador tem apenas um raínha no início da partida e é a peça mais poderosa do jogador;

~ o rei é a peça mais importante do jogo, uma vez que a sua perda (o substantivo, que se lê «pêr+da») implica que se perca (do verbo «perder», que se lê «pér+ca») o jogo. Pode-se mover como uma torre (na vertical ou na horizontal) ou como um bispo (obliquamente), mas apenas uma casa de cada vez. Se houver uma peça do adversário no quadrado para onde se desloca, substitui («come») a peça adversária e fica no seu lugar. Se for uma peça da sua cor, não se pode deslocar nesse sentido. Cada jogador tem apenas um rei no início da partida.

Há ainda, além destas regras de movimento, outras que alteram a movimentação das peças: Roque (quando Rei e Torre trocam), Captura en passant (quando um peão chega à 3.ª linha do adversário) ou a Promoção (quando um peão chega à 1.ª linha do adversário e pode ser subtituído por qualquer peça que o jogador queira).

É um jogo estimulante e interessante e muito tem-se já escrito sobre este jogo de origens antiquíssimas (veja-se, por exemplo, o artigo, sobre o Xadrez na Wikipédia em Português, Xadrez). As suas regras são simples, a estratégia é que demora a ser dominada e implementada. E, seguramente, saber como as diferentes peças se movem no tabuleiro não é o mesmo que saber jogar Xadrez. Quando um ser humano aprende a jogar, começa por interiorizar os movimentos das peças. Mas, quando joga com um jogador (mesmo que pouco mais) experiente, vê-se derrotado de formas que geralmente o surpreendem e o deixam admirado. «O meu adversário pôs ali a Torre há umas quantas jogadas e agora ela está no sítio certo para ele vencer-me facilmente agora. Parece que foi planeado ou assim...»
Um famoso internacionalmente jogador de Xadrez português foi Pedro Damião (1480-1544), também conhecido pela versão italiana do seu nome, Pedro Damiano. Nascido em Odemira, era farmacêutico de profissão. Em 1512, escreveu o livro Questo libro e da imparare giocare a scachi et de li partiti (Este livro e como jogar xadrez e [jogar] partidas), que teve 8 edições durante o século XVI (numa era em que a imprensa tinha menos de um século de existência): foi um best-seller na sua altura. Nele, Pedro Damião descreve as regras do jogo, dá conselhos sobre estratégias a usar e faz a análise de algumas jogadas e aberturas de jogo. É também o primeiro livro onde aparece referida a regra de que o tabuleiro deve ser colocado, frente ao jogador, com o quadrado da direita na fila mais próxima de si de cor branca (ou, o que é o mesmo, com o quadrado da esquerda de cor preta).

Pormenor de um quadro de VermeyenE a verdade é que um ser humano, quando verdadeiramente sabe jogar Xadrez, sabe como e onde colocar as peças para planear as jogadas futuras, não se limita à jogada imediata. Faz o planeamento, a antecipação, certos padrões de colocação das peças, algumas jogadas e os seus possíveis desfechos. Um computador não pode fazer a maioria destas coisas. Poderá ter um programa que lhe identifica padrões de peças mas não pode planear, ou antecipar, ou colocar-se no papel do adversário.
A imagem é um detalhe do quadro, do pintor renascentista holandês Jan Cornelisz Vermeyen (1500 - 1559), «Von Sachsen jouant aux échecs avec un noble espagnol» (Von Sachsen joga Xadrez como um nobre espanhol), pintado em 1549. Na verdade, Varmeyen nasceu em Beverwijk, cidade da província da Holanda do Norte, um das 12 províncias do país incorrectamente designado, em vários países, por Holanda (há duas, Holanda do Norte e Holanda do Sul, dentro do país). Ver o artigo Novas e demónios para mais sobre esta questão, sobre o declínio do Império Português no Oriente e para se saber a ligação entre a província da Zelândia e a Nova Zelândia.

Mas então como foi possível um computador ganhar a um ser humano? As regras de movimentação são simples e até uma criança as pode saber e usar mas isso não significa que se saiba jogar Xadrez por isso. (Da mesma forma, qualquer um pode dar um chuto numa bola mas nem todos são bons o suficiente para serem convocados para uma selecção.) Poder-se-á pensar que a simplicidade das regras do Xadrez poderá explicar a vitória de Deep Blue. Bastaria que o computador analisasse todas as possibilidades de como as peças podem ser movidas e escolhesse, de cada vez, as que dão origem a uma vitória sua.

Por vezes, surge a dúvida sobre se se deve escrever «analisasse», «escolhesse», «comesse»,... ou «analisa-se», «escolhe-se», «come-se»,... A primeira forma (sem travessão) é o pretérito imperfeito enquanto a segunda é o presente. Uma mnemónica que se pode usar é a de que a sílaba tónica (o «acento» caso ele estivesse presente) não está ao pé do travessão. «Ana-b>lisa-se» e «analisasse». Mais uma vez, como referido no artigo Esdruxulamente é importantíssimo saber onde a sílaba tónica está presente na palavra analisada.

Acontece que o número de jogadas possíveis num jogo de Xadrez ultrapassa até o número de átomos existentes no Universo (estima-se que seja aproximadamente 1075 o total de átomos no Universo inteiro). Devido à complexidade do jogo, e ao crescimento explosivo de jogadas possíveis à medida que o jogo decorre, há várias estimativas para o total de posições no tabuleiro.

Em 1950, o matemático norte-americano Claude Elwood Shannon estimou que o número total de jogadas possíveis num jogo com 40 turnos era, numa estimativa por baixo, de 10120 (um 1 seguido de 120 zeros), o chamado Número de Shannon. Para se ter uma ideia da magnitude deste número, o Universo tem aproximadamente
13 mil milhões de anos (13,73 × 109) = 1,373 × 1010 anos.
Um ano tem 365,25 dias, cada dia tem 24 horas, cada hora 60 minutos, cada minuto 60 segundos. Multiplicando todos estes números, o Universo tem um total de
410 mil biliões, 248 biliões e 800 mil milhões = 4,1 × 1015 segundos de existência.
Este é um número vastamente inferior aos 10120.
Outro exemplo, o Universo tem milhares de milhões de galáxias, sendo a nossa (a Via Láctea) apenas uma delas. Estima-se que a nossa galáxia tenha apenas perto de
200 mil milhões (2 x 109) de estrelas.

E apenas numa partida com 40 turnos (a média nos jogos internacionais)...
Ver o artigo Termos ordinais para mais sobre ordinais e cardinais.

Ou seja, um computador nunca conseguiria planear, no início de uma partida, todas as jogadas que deve fazer para ganhar o jogo. Demorar-lhe-ia muito mais do que todo o tempo de vida do Universo para efectuar apenas a primeira jogada de uma estratégia vencedora. No máximo, consegue planear as jogadas seguintes mais próximas. Mas, se os seres humanos são muito mais capazes de planificação e antecipação, como pode um computador não só jogar como ganhar a um ser humano?

Em primeiro lugar, é necessário avaliar a força das peças que o computador e o jogador têm disponíveis. Para isso, é atribuído, a cada peça, um valor numérico que indica quão importante ela é. Assim, são geralmente atribuídos os seguintes valores às peças de Xadrez (outras numerações são possíveis, mas esta é geralmente a mais aceite):

Rainha - 9 pontos;

Torre - 5 pontos;

Bispo - 3 pontos;

Cavalo - 3 pontos;

Peão - 1 ponto;

Estes são os valores que o computador atribui às peças que tem e às peças que o adversário tem para avaliar o equilíbrio de forças. Com os cálculos efectuados, um computador podia fazer uma «árvore de decisão»: no início da partida, o jogador «branco» tem 20 possibilidades de jogar (cada um dos 8 peões pode avançar 1 ou 2 casas - 16 possibilidades - e um dos dois cavalos pode avançar para um de dois quadrados - 4 possibilidades). Como resposta, o jogador «preto» tem as mesmas 20 possibilidades de jogar. Dependendo da peça jogada, o jogador «branco« tem depois um número variável de possibilidades de jogo, assim como o jogador «preto». Como forma de facilitar o cálculo, suponhamos que cada jogador tem novamente 20 possibilidades de jogar no turno seguinte. No segundo turno, no qual o jogador preto» joga, há 20x20 = 400 possibilidades de jogadas. No terceiro turno, no qual joga o jogador «branco», há 400x20 possibilidades de jogadas. Continuando estes cálculos (simplificados, não esquecer), chega-se ao turno 12 (cada jogador fez apenas 6 jogadas) com 4x1015 jogadas possíveis, tantas como os segundos de existência do Universo!
Assim, numa partida de 40 turnos, usando esta simplificação, haveria 2040 = 1,1x1052 jogadas possíveis (um número tão grande que não há, em qualquer língua humana, um nome comum para esta ordem de grandeza. Os nomes acabam-se no «decalião» 1033).
Ver o artigo Termos ordinais para mais sobre como nomear os números acima do milhão.


O computador-jogador de Xadrez, DeepBlue conseguia efectuar 11,38 gigaflops (ou seja, uma vez que 1 FLOPS «FLoating Operations Per Second» indica 1 operação por segundo, isto significa que é capaz de efectuar 1,138x1010 operações por segundo, ou uma dezena de milhares de milhões de operações num segundo). As partidas efectuadas entre Kasparov e Deepblue foram 12, divididas por 2 jogos de 6 partidas cada. O quadro acima faz um resumo dessas partidas:
~ na primeira coluna, o número da partida;
~ na segunda coluna, quantos turnos teve cada partida;
~ na terceira coluna, quem ganhou a partida;
~ na quarta coluna, quantas jogadas seriam necessárias calcular (se acordo com o cálculo simplificado apresentado acima);
~ na quinta coluna, quantos segundos demoraria DeepBlue a efectuar esse cálculo;
~ na sexta coluna, quantos anos demoraria a efectuar esses cálculos.
O valor 45,9167 é a média de turnos de cada partida ao longo dos dois jogos.
Mesmo na partida mais curta, a última, com apenas 19 turnos jogados, DeepBlue demoraria 1 mil e quinhentos milhões de anos a calcular todas as jogadas possíveis!
A tabela que compilei pode ser encontrada aqui Jogadas de Xadrez

Um computador moderno, por mais avançado que seja, baseia todo o seu poder de processamento em cálculos brutos, ao contrário de um ser humano. Por exemplo, imagine-se que é necessário calcular metade de 512. Um computador efectuaria mesmo a divisão, após transformar o número da base decimal para a base binária, chegando ao valor de 256 na base binária e transformando o resultado para a base decimal. Um ser humano poderia, por exemplo fazer os seguintes raciocínios:
512 = 500 + 10 + 2. Metade de 500 é 250, metade de 10 é 5, metade de 2 é 1. Tudo somado é 250+5+1 = 256. Um outro exemplo poderia ser o cálculo do dia da semana a que calha (ou calhou) determinada data, poderia usar a Regra de Zeller e efectuar todos os cálculos. Um ser humano poderia apenas somar (ou subtrair) 7 em 7 de uma data de que conhece o dia da semana (por exemplo, o dia em que está).
Para mais sobre a Regra de Zeller e como efectuar cálculos para determinar o dia da semana de uma data a partir de outro, veja-se Problema calendarii.

Mas, de os cálculos necessários, demorariam muito mais do que o tempo que o Universo tem vida, como se programa um computador, mesmo os modestos computadores domésticos, para jogar e ganhar uma partida de Xadrez?

O TurcoSe um computador (ou um ser humano) conseguisse calcular TODAS as jogadas possíveis de uma partida, bastar-lhe-ia, em cada turno, escolher a jogada que levaria à sua vitória. Mas acontece que não consegue. Já houve máquinas com a reputação de saberem jogar (e ganhar) a seres humanos numa partida de Xadrez, sendo o mais famoso «O Turco», exibido pela Europa e América entre 1770 e 1854, tendo até derrotado Napoleão Bonaparte, em 1808. Em 1859, foi desvendado o segredo das vitórias d'O Turco: um operador humano escondia-se no interior da «mesa» onde se desenrolava a partida, manobrando engrenagens para que o boneco fizesse as famosas movimentações de peças e ganhasse partidas. Por um elaborado sistema de painés de madeira, o operador era escondido quando se abriam as portas que «mostravam» o mecanismo de funcionamento.

Mas foi apenas com o advento dos computadores, na segunda metade do século XX, que foi possível ter máquinas que verdadeiramente jogavam e derrotavam seres humanos. Usavam, além do seu poder de cálculo, um teorema demonstrado, em 1928, pelo matemático John von Neumann, o Teorema Minimax, que permite analisar, numa situação como uma disputa de recursos, a determinação da melhor estratégia a adoptar, um jogo (de Xadrez ou algo tão simples como o Jogo do Galo, conhecido como «Jogo da velha» no Brasil).

Começa por verificar todas as jogadas possíveis ao fim de 3 turnos. Tendo em conta os valores das peças presentes no tabuleiro nesse jogada, bem como a sua posição e vários outros parâmetros (como a existência de padrões que conduzem a estratégias já conhecidas), o computador calcula o valor dessa posição. Faz o mesmo para cada uma das (aproximadamente) 20x20x20 = 8 mil. Escolhe então a posição mais vantajosa para si (o máximo) e verifica as posições da jogada anterior (a do adversário) que conduziram a essa. Desta vez, faz a mesma análise para as (sensivelmente) 400 jogadas anteriores mas escolhe o valor mais baixo (o mínimo) uma vez que a pior jogada do adversário é a melhor para si. Verifica então as (mais ou menos) 20 jogadas que conduziram a esse valor mínimo do adversário, escolhendo a jogada que poderá fazer que tem uma disposição de peças com o valor mais elevado. É por ter essa procura que oscila enre a procura de um máximo e de um mínimo que o teorema é chamado de Minimax. Usando o Algorimo Alfa-Beta, o computador elimina os ramos que são o resultado de uma posição com um valor muito baixo (caso seja um turno em que jogaria) ou um valor muito alto (caso seja um turno do adversário). Esse mínimo esse máximo recebem o nome de Alfa e Beta (daí o nome do Algoritmo), permitindo ao computador reduzir até quase metade os cálculos a efectuar. Este método relaciona-se com o Método de Condorcet, aplicável a eleições (onde se escolhe o cadidato com mais escolha dos eleitores). Em Portugal, além das eleições directas para Presidente da Reública para Primeiro-Ministro, usa-se o Método de D'Hondt (ver D'Hondt vem?) para as eleições para o Parlamento nacional (situação em que há vários vencedores).
Para um exemplo, em Português, do algoritmo em funcionamento ver O algoritmo Alfa-Beta.

Adicionando a possibilidade de o computador poder mudar os valores das posições (de onde escolhe a melhor para si e a pior para o adversário), de modo a reflectir os jogos que vai efectuando (os jogos de Xadrez domésticos em computadores não têm essa opção mas computadores que são unicamente jogadores de Xadrez como o famoso DeepBlue), o computador não só pode efectuar bons jogos, ganhá-los bem como «aprender» com os jogos que vai efectuando.

Garry KasparovOu seja, a vitória de DeepBlue, longe de pressagiar o fim do controlo humano sobre os computadores, na verdade é uma demonstração de quão longe o espírito humano pode compreender e ultrapassar-se a sim mesmo: um simples teorema matemático e o avanço que os seres humanos estão sempre a criar para as suas máquinas em termos de cálculos em bruto.

A vitória de Deepblue sobre Kasparov apenas demonstra a força e capacidade do espírito humano e a sua capacidade de se ultrapassar. A inteligência humana não sai manca do embate contra DeepBlue, sai mais forte e reforçada.

O primeiro registo de um jogo semelhante ao Xadrez surgiu, no século VI DC, na Índia, com o nome de «Chaturanga» (que significa «4 divisões militares»: Infantaria (peões), Cavalaria (cavalos), Elefantes de guerra (bispos) e Carros de combate (torres). Um século depois, é adoptado na Pérsia, com o nome de «Shatranj». Os Árabes introduziram depois, no século XX, o jogo na Península Ibérica, onde «Shatranj» se transformou em «Xadrez». Nos países anglófonos, do persa Xá («šāh») derivou a palavra «Chess» que usam para o jogo. O termo «Cheque» derivou da mesma palavra persa («šāh»), vindo a ser incorporado no vocabulário francês arcaico como «eschec». De «eschec» derivou, por evolução convergente, o termo «cheque», usado quando o Rei está ameaçado mas tem possibilidade de se defender ou afastar do ataque. O termo «Cheque-mate» deriva do persa «Shah Mat» que significa "O Rei (Xá) está indefeso" ou "O Rei está desprotegido". É comum pensar-se que significa «O Rei está morto", mas não é esse o seu significado. A palavra «mate» evoluiu da palavra persa «mandan», que entronca na mesma raíz que a palavra latina «mancu». «Mandan» é utilizado no contexto de abandonado (ou surpreendido sem protecção) e «mancu», que evoluiu para o «manco» português, tem o significado usual de desprovido de um membro.



Publicado por Mauro Maia às 09:26
Atalho para o Artigo | Adicionar aos favoritos

De Maria Papoila a 8 de Maio de 2008 às 13:52
Olá Mauro: um jogo que é considerado desporto. Será que o computador atingiu a máxima inteligência possível? Ficou clara a explicação da expressão cheque-mate, que não sabia de origem persa. Beijos.


Comentar:
De
  (moderado)
Nome

Url

Email

Guardar Dados?

Este Blog tem comentários moderados

(moderado)
Ainda não tem um Blog no SAPO? Crie já um. É grátis.

Comentário

Máximo de 4300 caracteres


Copiar caracteres

 



O dono deste Blog optou por gravar os IPs de quem comenta os seus posts.

Cognosco ergo sum

Conheço logo sou

no Cognosco
 
Cogitações recentes
Pergunta feita por um menino de 14 anos... Mas a p...
Essa pergunta é interessante: será que ele se quei...
O fogo é fruto de uma reação química, não tem esta...
Olá Ribeiro. Eis um link atualizado para a folha d...
Seria possível fornecer um link atualizado para o ...
Artigos mais cogitados
282 comentários
74 comentários
66 comentários
62 comentários
44 comentários
Artigos

Setembro 2018

Novembro 2017

Outubro 2017

Agosto 2017

Julho 2017

Junho 2017

Maio 2017

Abril 2017

Março 2017

Fevereiro 2017

Janeiro 2017

Dezembro 2016

Novembro 2016

Outubro 2016

Julho 2016

Março 2015

Dezembro 2014

Outubro 2013

Maio 2013

Fevereiro 2013

Outubro 2012

Setembro 2012

Agosto 2012

Junho 2012

Janeiro 2012

Setembro 2011

Abril 2011

Fevereiro 2011

Dezembro 2010

Maio 2010

Janeiro 2010

Abril 2009

Fevereiro 2009

Janeiro 2009

Novembro 2008

Outubro 2008

Agosto 2008

Julho 2008

Junho 2008

Abril 2008

Fevereiro 2008

Janeiro 2008

Novembro 2007

Outubro 2007

Agosto 2007

Julho 2007

Junho 2007

Maio 2007

Abril 2007

Março 2007

Fevereiro 2007

Janeiro 2007

Dezembro 2006

Novembro 2006

Outubro 2006

Setembro 2006

Agosto 2006

Julho 2006

Junho 2006

Maio 2006

Abril 2006

Março 2006

Fevereiro 2006

Janeiro 2006

Dezembro 2005

Novembro 2005

Outubro 2005

Setembro 2005

Julho 2005

Junho 2005

Maio 2005

Abril 2005

Março 2005

Fevereiro 2005