sábado, dezembro 30, 2006

O shogi (parte II)

O shogi parece ter, à partida, mais semelhanças com o xadrez ocidental do que o Xiangqi. Efectivamente, este jogo é mais parecido nas peças e no "layout" do tabuleiro. Curiosamente, tal como no xadrez chinês foi abandonada a rainha do xadrez original, o que diminui o poder inicial ao dispôr de cada jogador. Neste jogo optou-se por avançar os peões de uma fila ao invés de lhes dar a possibilidade de terem uma jogada inicial de duas casas.

No shogi apenas 1% dos jogos terminam empatados. Isso deve-se ao facto de as peças não saírem definitivamente do tabuleiro, havendo sempre a possibilidade de mate (não existe o chamado "stalemate"). Existem também regras que forçam o jogador que inicia um xeque perpétuo a desfazê-lo, para evitar forçar um empate dessa forma. Mais do que isso, existem muitas regras, algumas não muito bem definidas, para impedir que o jogo se torne num empate rápido. Por exemplo, poder-se-ia pensar em levar o rei até ao lado do inimigo do tabuleiro e protegê-lo aí, o que faria sentido: a reduzida mobilidade das peças do shogi a andarem para trás tornaria muito mais difícil o xeque-mate. Em situações destas, o árbitro pode decidir resolver o jogo com uma contagem de material, atribuindo a vitória ao jogador que tiver mais peças valiosas. Esta é, como não será de estranhar, uma regra bastante controversa.

Passemos, agora, a algumas considerações estratégicas sobre este jogo.

- O facto de os peões não tomarem na diagonal elimina os bloqueios e toda a estratégia que se constrói, no xadrez ocidental, à volta de posições fechadas e cadeias de peões. Há, assim, uma certa desvalorização neste jogo, do papel do peão, face ao xadrez internacional : Steinitz, campeão mundial, era conhecido por dizer que "os peões são a alma do jogo".

- O shogi é, fundamentalmente, um jogo ofensivo. Não existem grandes vantagens em nos remetermos somente à defesa; uma força atacante consegue normalmente dominar a defesa, desde que disponha de tempo suficiente. No shogi acontece, muitas vezes, por isso, que os dois lados estejam simultaneamente à beira de conseguir o xeque-mate. Assim, fica também a impressão que, neste jogo, dispor de uma vantagem material é muito menos relevante que no xadrez, onde a vantagem de um peão costuma ser suficiente para a vitória. E, de facto, assim é. Digamos que o shogi (tal como o xiangqi, mas principalmente o shogi) é um jogo muito menos materialista que os jogos ocidentais e, também, menos posicional. Tal sugere uma ligação á cultura oriental, tal como já víramos para o Go, entre outros jogos. Mas como já vimos, se o material é secundário, dispor de tempos é fundamental, daí se realizarem frequentemente sacrifícios com o objectivo de abrir as linhas do inimigo. Tudo isto é complicado pela possibilidade de se colocarem peças quase livremente no tabuleiro: uma peça capturada pode, assim, ser infiltrada nas linhas inimigas reforçando um ataque desenvolvido por um jogador. Por tudo isto conclui-se que, no shogi, a defesa não promete, a longo prazo, qualquer sucesso.

Quanto aos computadores, a associação japonesa de Shogi proibiu os seus profissionais de defrontarem máquinas sem autorização, para preservar o seu estatuto como jogadores. Contudo, podemos ver que este é um jogo bastante mais complexo que o xadrez, devido às colocações de peças no tabuleiro, que aumentam consideravelmente o "branching factor" (o número de jogadas que uma implementação de força bruta terá de considerar), ao maior tamanho do tabuleiro e maior número de peças, e também às regras bastante mais complexas que o xadrez ocidental. O benefício dos computadores da utilização de livros de aberturas também não é claro, uma vez que existem muito mais aberturas possíveis e estas não se encontram tão bem estudadas como no parente ocidental deste jogo. Existem, ainda assim, programas consideravelmente fortes e pensa-se que será apenas uma questão de tempo até este jogo também passar para o domínio dos computadores.

quarta-feira, dezembro 27, 2006

O xadrez japonês (Shogi)



Distinto de cada um dos jogos anteriores, o xadrez japonês é, contudo, claramente "reconhecível" como xadrez. É jogado por dois jogadores com 20 peças cada - mais quatro que no xadrez ocidental - num tabuleiro 9x9,sendo, como em todas as variantes do xadrez, o objectivo dar mate ao rei inimigo.

É o jogo de tabuleiro mais jogado no Japão; mais de 60% dos japoneses admitem jogá-lo regularmente, muitos mais que para o Go ou para o xadrez internacional.

Todas as peças são pentagonais, e de uma mesma cor, normalmente brancas. Este facto não é fruto do acaso - com efeito, o factor principal que torna este jogo único é que as peças que são capturadas se tornam disponíveis para o jogador que as captura jogar - e portanto o que define o jogador a que pertence uma dada peça é a sua orientação e não a sua cor. O outro factor é que quase todas as peças podem ser promovidas para outras de maior valor - não apenas os peões - e que, na maior parte dos casos, a promoção não é obrigatória mas sim decidida pelo jogador.

O shogi apresenta 9 peões - um por cada coluna no set-up inicial - e, nesse aspecto, aproxima-se do xadrez ocidental. Contudo, ao contrário do xadrez ocidental, cada lado apenas dispõe de um bispo e de uma torre, não existindo a figura da dama neste jogo. Existem, sim, três tipos de peças que são desconhecidas ao jogador do xadrez ocidental : o lanceiro, o general de prata e o general de ouro, de que cada jogador dispõe inicialmente de duas unidades.

O rei, a torre e o bispo movem-se exactamente como no xadrez ocidental. Mas a torre , quando chega à 7ª, 8ª ou 9ª fila, promove-se para um dragão. O dragão é a peça mais forte de todas, movendo-se como um rei + uma torre do xadrez ocidental. É uma peça marcadamente ofensiva. Já o bispo, nas mesmas condições da torre, transforma-se num cavalo (não num cavaleiro, são peças diferentes). O cavalo pode ser visto como bispo+rei. É a peça mais forte que costuma ser usada defensivamente.

O rei, como em (quase) todas as variantes do xadrez, encontra-se no centro do tabuleiro tendo ao seu lado os dois generais de ouro. Ao lado dos dois generais de ouro encontram-se os dois generais de prata. O bispo e a torre encontram-se à frente do cavaleiro da esquerda e da direita, respectivamente.

O peão é idêntico ao do xadrez, excepto que captura exactamente da mesma forma que se move. Para além disso, quando atinge a 7ª fila (e portanto uma das três filas a contar do fim do tabuleiro) o peão é promovido a "tokin", o que significa que passa a poder mover-se como um general dourado. Um general dourado move-se em qualquer direcção, mas não pode mover-se diagonalmente para trás. Os peões encontram-se avançados já na terceira fila.

O lanceiro é um vestígio de evolução da torre, aparecendo na mesma posição que esta, isto é, nos cantos: apenas se pode mover para a frente, isto é, não se pode mover horizontalmente ou para trás. É, por isso, uma torre com menos poderes. Quando chega à 7ª fila, tem a opção de se promover para um general dourado, e quando chega à 9ª é a tal obrigado, uma vez que ficaria imobilizada se não o fizesse.

O mesmo se pode dizer do cavaleiro, localizado junto a cada um dos dois lanceiros. O cavaleiro apenas se pode mover para a frente uma casa e diagonalmente para a esquerda ou para a direita uma casa. Ao contrário do cavalo no xadrez chinês, este cavaleiro pode saltar. Analogamente ao lanceiro, pode promover-se a partir da 7ª linha, obrigatoriamente na 9ª.

O general de prata é um "bispo enfraquecido", isto é, pode mover-se uma casa em qualquer direcção, excepto directamente para os lados ou directamente para trás. A sua promoção funciona de forma idêntica à das outras peças aqui discutidas.

Em qualquer lance, um jogador pode colocar uma peça que capturou num local do tabuleiro. A torre, o bispo e os generais não têm qualquer restrição quanto às casas em que podem ser colocados. Um peão não pode ser colocado numa mesma fila que um peão do mesmo jogador, ou na última fila, uma vez que não poderia mover-se. O mesmo se pode dizer do lanceiro (não pode ser colocado na última fila) e do cavalo (não pode ser colocado nas últimas duas filas). Também o peão não pode ser posto de forma a dar, de imediato, xeque-mate ao rei adversário.

A maior parte dos lances ilegais resultam na derrota automática do jogador que os pratica.

sábado, dezembro 23, 2006

O Xiangqi (parte 2)

Continuando na análise ao Xiangqi (xadrez chinês), este é um jogo que possui uma miríade de regras para evitar cheques e perseguições perpétuas, entre outros motivos tácticos que são muito comuns e até utilizados pelos jogadores de top no xadrez internacional para obter empates, por se considerar que isso tira a essência do jogo, de lutar por um só objectivo que é a vitória. Mais uma vez, notamos aqui a mentalidade "tudo ou nada", antagónica àquela que parece existir no Ocidente onde o médio é aceitável, que não vive tanto dos extremos.

Padrões tácticos e estratégicos que são características peculiares deste jogo incluem o facto de se poderem prender duas peças ao mesmo tempo ( a prisão de uma peça, no xadrez, e no contexto mais geral dos jogos de tabuleiro, ocorre quando esta não se pode mover sob pena de perder uma peça que se encontra atrás, ou porque tem maior valor que o atacante, ou porque não se encontra defendida). O canhão pode prender duas peças inimigas em simultâneo, porque se a que está mais perto desta se afastar, a peça mais longe fica atacada (passa a existir uma peça intermédia para esta saltar). Este é um motivo muito importante porque pode paralisar por completo a posição inimiga.

O material não tem um papel tão importante como no xadrez ocidental pois, por exemplo, é comum sacrificar-se um soldado (peão) para se obterem vantagens em termos de mobilidade e colocação das peças.

Olhando agora para a complexidade do jogo, o Xiangqi é um jogo com uma profundidade estratégica que é considerável. De facto, a complexidade da árvore de procura, ou seja o número de nós que é necessário visitar a partir da posição inicial, é estimada em cerca de 10^100 nós - facto a que não será alheio o tabuleiro ser 40% maior , em área, que o tabuleiro do Xadrez Ocidental (tem 90 casas ao passo que este apenas tem 64).

Em 2006 o melhor jogador humano ainda não foi batido pelo melhor computador, mas estima-se que isso será possível dentro de poucos anos, dados os avanços algorítmicos e de poder computacional que actualmente se observam. O jogo pode ser analisado com livros de aberturas e bases de dados de finais, como é feito para o xadrez, mas o número relativamente elevado de regras ad-hoc e a ligeiramente maior complexidade do jogo fazem a balança pender (ainda) actualmente para o lado dos melhores humanos, se bem que este jogo é jogado pelos computadores a um nível já muito elevado.

sexta-feira, dezembro 22, 2006

O Xadrez Chinês (o Xiangqi)

O tabuleiro é o primeiro dos elementos distintivos do Xiangqi. É um tabuleiro com 10x9 intersecções, seccionado ao meio horizontalmente por uma linha divisória que é conhecida por "rio", nuance relativamente ao xadrez internacional que limita desde logo o movimento de algumas peças as quais ficam, assim, comprometidas à defesa, como será visto a seguir. Por outro lado, em cada lado do tabuleiro existe um quadrado (marcado com uma cruz, o castelo) de onde o general (o rei) não pode sair.



As peças são idênticas para ambos os jogadores ( a não ser que se esteja a jogar num
sistema de handicap, para equilibrar os seus skills) e são as seguintes:

- o general (a peça que se encontra absolutamente centrada numa das duas linhas finais do tabuleiro), move-se uma casa em qualquer direcção não diagonal dentro do castelo, e não pode mover-se para a frente do outro general se não existirem peças entre eles na mesma coluna;
- o mandarim (as duas peças que se apresentam imediatamente do lado esquerdo e direito do respectivo general) serve para guardar o general e move-se um quadrado em qualquer direcção dentro do castelo;
- o elefante é outra peça defensiva que apenas se pode mover duas casas na diagonal do seu lado do tabuleiro (i.e, não pode atravessar o rio), e não pode saltar por cima de outras peças. Inicialmente os dois elefantes são colocados à esquerda e à direita dos mandarins que estão à esquerda e à direita do general, respectivamente.
- o cavalo é idêntico ao do xadrez (aparece numa posição análoga, é a segunda peça a contar do canto dos dois lados) excepto que não pode saltar por cima das peças em questão.
- a quadriga (que aparece nos cantos do tabuleiro) é uma peça que tem o poder que é conferido à torre no xadrez ocidental; pode mover-se qualquer número de casas numa direcção não diagonal.
- o canhão (há dois, na terceira fila, em frente aos cavalos respectivos) é parecido com a quadriga, com a diferença que quando captura, tem de saltar por cima de exactamente uma peça (adversária ou não)
- o soldado ou peão (de que há 5 exemplares espaçados de uma casa entre si e avançados já na quarta fila), o que permite que o jogo se desenvolva com mais fluidez face ao Xadrez Internacional, e que arranque mais depressa. O peão move-se e captura uma casa para a frente, excepto do lado contrário do rio que também se pode mover lateralmente. De notar que esta mudança aparentemente insignificante na posição, transfigura completamente o carácter estratégico do jogo. Os peões deixam de estar apoiados pelos seus colegas e, por outro lado, passam a ter mobilidade lateral quando atingem a outra margem do rio. O facto do peão não se poder promover torna-o uma peça substancialmente mais fraca que no xadrez ocidental.

O objectivo do jogo é obter o xeque-mate, situação em que o general inimigo não tem qualquer lance legal e é atacado, ou stale-mate, situação em que o adversário não dispõe de quaisquer lances legais para efectuar. De notar que, ao invés do xadrez, o stale-mate resulta na derrota para o lado que ficou sem lances legais.

O xadrez chinês não tem a peça super-poderosa que chamamos dama, nem uma peça que se possa mover arbitrariamente ao longo de uma diagonal. Compensa esse poder de ataque a menos com "quase quatro torres", as quadrigas e os canhões. Assim, a pressão ao longo das diagonais é muito reduzida.

A protecção ao general também teria necessariamente de ser aumentada, uma vez que as colunas, mais abertas que no xadrez internacional, ficam vulneráveis ao ataque das peças pesadas (quadrigas e canhões). Daí a existência de dois mandarins.

O jogo também evoluiu de forma a evitar empates quando há apenas uma pequena vantagem de um dos lados. Daí a regra de oposição dos generais mencionada atrás, e a habilidade de se mover lateralmente do soldado.

quarta-feira, dezembro 20, 2006

O Xadrez (Parte II)

Falei apenas do Xadrez que para nós é mais conhecido, o Xadrez Ocidental. Mas o Xadrez é um jogo cuja diversidade de variantes é infindável, a qual pretendo aflorar aqui.

Por exemplo, ainda falta referir aquele que é, talvez, o jogo de tabuleiro mais jogado em todo o mundo : o Xadrez Chinês, que é mais popular no Oriente que o Xadrez Ocidental, como seria natural conjecturar-se. Ou o xadrez japonês ( o Shogi ). O facto de o Xadrez ter resultado em dois jogos tão diferentes em dois países tão próximos não é certamente coincidência, mas decorre das culturas personalizadas e das rivalidades históricas entre esses dois povos.

As origens históricas deste jogo estão envoltas numa densa neblina. Pensa-se que é claro que todas as variantes do xadrez, e aquelas a que me refiro não são excepção, possuem um antecessor comum (daí terem todas o mesmo nome!). Mas de onde veio esse antecessor, e como evoluiu?

Como já vimos, a única coisa de que se tem a certeza é que uma forma do jogo chamada shatranj era jogada na Pérsia por volta do século sete depois de Cristo. Na Idade Média, o jogo começou a espalhar-se para a Europa e para o Oriente. Há quem acredite que chegou primeiro à China, pois o xadrez chinês actual é um parente mais próximo do shatranj que o xadrez Ocidental.

O que se nota aqui, e que é muito interessante, é que à imagem das teorias da evolução biológicas, os jogos de tabuleiro primitivos tendem a evoluir para jogos mais consistentes e mais interessantes, mas de forma diversa e não monótona. Assim, por exemplo, o Xadrez Chinês alivia a falta de mobilidade dos peões no jogo original, colocando-os em posições avançadas, ao passo que o xadrez ocidental inventou o lance de peão duplo inicial para suprir a mesma carência. Por outro lado, o jogo original sofria de carências importantes ao nível da mobilidade e agressividade das peças. Na Europa, esse problema foi resolvido aumentando o poder do bispo e da dama. No Xadrez Chinês resolveu reduzir-se o número dos peões no tabuleiro e introduzir uma nova peça, o canhão.

Nos próximos posts discutirei com um pouco mais de detalhe o xadrez chinês e o shogi, que nos fará compreender melhor esta dualidade.

segunda-feira, dezembro 04, 2006

O gomoku e os jogos m,n,k

Continuando na senda dos jogos abstractos de tabuleiro, o Gomoku é um jogo originário do Japão, tradicionalmente jogado num tabuleiro de Go 19x19 com as peças deste mesmo jogo. Dois jogadores alternam na colocação de peças brancas e pretas no tabuleiro, tendo o objectivo de colocar cinco peças em linha (que pode ser ao longo de uma linha, coluna ou diagonal). As regras não podiam, portanto, ser mais simples. É o jogador com as peças pretas que começa a jogar, ao contrário do xadrez ou de outros jogos tradicionais de tabuleiro.

Quando é jogado num tabuleiro 15x15, recebe o nome de Renju (imagem abaixo).



Foi provado por Victor Allis (através de uma pesquisa por computador) que o jogo termina sempre numa vitória para as pretas se estas usarem uma estratégia perfeita. Mesmo em tabuleiros de diferentes tamanhos, é bastante claro que as pretas têm vantagem e, como tal, existem diversas variantes deste jogo em que foram criadas algumas regras adicionais para nivelar o jogo.

Se generalizarmos o jogo para um tabuleiro m x n, em que um jogador para ganhar tem de fazer k peças numa linha, obtemos os jogos (m,n,k), que são de grande interesse do ponto de vista matemático, mas como é óbvio só alguns são jogados na prática. Por exemplo, o jogo (3,3,3) é o tão conhecido jogo do galo.

É interessante ver como, neste caso, com um argumento simples é possível provar que o jogador que joga em 1º caso tem pelo menos garantido o empate (pode ter garantida a vitória, dependendo do jogo, mas este argumento prova que ele, pelo menos, não perde). Imagine-se que o 2º jogador tem uma estratégia E que lhe permite ganhar (onde aqui uma estratégia não é mais do que uma árvore que a cada lance possível do adversário permite responder com um lance que continua a permitir o 2º jogador forçar a vitória na posição resultante). Então, o 1º jogador faz a primeira jogada ao acaso e depois limita-se a copiar a estratégia do seu adversário nos restantes lances. Se em algum ramo da árvore se vir forçado a jogar para uma casa em que já jogou (porque joga aleatoriamente na 1ª jogada) limita-se a jogar aleatoriamente de novo. Ou seja, o segundo jogador também tem garantida a vitória. Ora, isto é impossível porque não pode haver dois adversários a ganharem um mesmo jogo.

À primeira vista, o leitor seria levado a pensar que este argumento se aplica a quaisquer jogos simétricos (em que ambas as partes têm disponíveis os mesmos movimentos) e, portanto, ao xadrez. Contudo, existe um pormenor subtil que invalida a aplicação deste raciocínio. Nos jogos (m,n,k) não há nenhuma desvantagem que se possa imaginar de fazer o primeiro lance ao acaso - uma configuração do tabuleiro em que tenho n peças + 1 colocada ao acaso é sempre pelo menos tão boa como aquela em que tenho n peças nas mesmas posições - mas no xadrez, um lance ao acaso como por exemplo 1. Ca3 pode enfraquecer a posição branca, pelo que este argumento não se aplica ao xadrez, damas, e outros jogos de tabuleiro tradicionais.