segunda-feira, Janeiro 08, 2007

Mancala



Mancala é uma designação comum a mais de uma centena de jogos de tabuleiro originários de África. O jogo existia, já, no antigo Egipto, cerca de 1580 a.C., podendo observar-se tabuleiros de pedra esculpidos nas lajes de cobertura do templo de Kurna (323-30 a.C.), no topo das paredes da entrada do templo de Carnaque e também no templo de Luxor (1557-1304 a.C.). Diz-se que o jogo tem um significado espiritual; era jogado depois da morte de uma pessoa, para alegrar o espírito do morto antes de ser enterrado.

A palavra mancala vem do árabe mangala, mingala ou magala e do verbo naqala, significando mover, deslocar. Nela reside toda a essência do jogo.

O jogo é normalmente jogado num tabuleiro, com duas filas de buracos de cada lado e um buraco maior à direita de cada jogador, o seu "mancala". As peças usadas neste jogo são "sementes", todas iguais. O objectivo do jogo é, fundamentalmente, conseguir colocar mais peças no buraco maior (depósito) que o adversário. Na maior parte das variantes, o jogo termina pois, quando um jogador se apropria (coloca no seu "mancala") mais de metade das sementes em jogo. Inicialmente, é colocado um determinado número de sementes (3, por exemplo) em cada buraco pequeno do tabuleiro.

Os jogadores alternam a fazer movimentos. O movimento "base" do jogo é pegar nas sementes que se encontram numa das casas do seu lado e distribuí-las pelas casas ao lado, por uma ordem contrária à do sentido dos ponteiros do relógio. Se passar pelo seu depósito, coloca lá uma peça; caso seja o do adversário, não. Em muitas das variantes, os jogadores podem também fazer capturas: quando colocam uma semente numa casa do adversário e esta fica com um determinado número de sementes, dependendo do jogo, podem retirá-las e colocá-las no seu depósito e, em algumas variantes, podem ir fazendo isto enquanto as casas do adversário que vão sendo percorridas satisfizerem essa condição.

Existem normalmente regras especiais, aplicáveis quando um jogador fica sem sementes. Normalmente, o jogador contrário é obrigado a fazer uma jogada que coloque sementes do lado do adversário. Da mesma forma, se um jogador realizar uma captura que deixe o adversário sem sementes, é por vezes obrigado a jogar de novo de forma a dar ao adversário sementes para que possa jogar. Em regra, muitas variantes resolvem também certas situações cíclicas que podem ocorrer no jogo forçando cada jogador a retirar as sementes do seu lado e colocá-las no depósito, fazendo-se depois uma contagem.

É um jogo puramente abstracto e matemático, o que não será de espantar dado que as civilizações de então, nomeadamente os Egípcios, tinham fortes conhecimentos em matemática. O pendor abstracto que revelam é que não deixa de ser interessante. Porventura, o potencial delas para produzirem abstracções é maior do que o nosso, na sociedade moderna : a variedade de bens materiais e outras coisas de que dispomos tornam-no díficil. O jogo também não requer praticamente recursos nenhuns para ser jogado, isto é, pode ser jogado com toda a facilidade por civilizações primitivas dado que o tabuleiro e as peças são rudimentares.

Ultimamente, têm sido aplicados técnicas da teoria combinatória de jogos que permitem compreender e analisar este jogo / família de jogos em grande profundidade. Por ser uma família de jogos puramente matemática, os computadores gozam nela de uma facilidade muito grande para vencerem os melhores jogadores humanos.

sexta-feira, Janeiro 05, 2007

O Mastermind



O Mastermind, inventando em 1970 por um israelita (Mordecai Meirowitz), é um jogo de tabuleiro muito simples, mas apesar disso muito jogado em todo o mundo. Difere dos jogos de tabuleiro que tenho apresentado aqui no facto de se tratar de um jogo de informação imperfeita, ilustrando alguns dos seus aspectos principais. Nos jogos de informação perfeita, o estado do jogo é sempre conhecido por todos os jogadores envolvidos. Neste caso, porém, o objectivo do jogo é precisamente adivinhar o seu estado através de pistas, que fica por isso escondido do jogador que o tem de fazer, que vai cruzando informação até restar uma só possibilidade. Noutros jogos, o jogador terá de decidir a sua jogada baseando-se na probabilidade do adversário possuir uma determinada carta, por exemplo.

Um jogador escolhe um código, constituido por quatro marcadores de entre seis cores diferentes possíveis, e o outro tenta adivinhar. Existem portanto 1296 = 6^3 códigos possíveis. Tem 10 tentativas para o fazer, vencendo quando colocar a combinação de cores certa no tabuleiro. Cada uma das tentativas é avaliada pelo jogador que escolheu o código, que a classifica indicando o número de marcadores que têm uma cor comum com a solução e aqueles que, para além de ter uma cor comum com a solução, se encontram alinhados com esta (na mesma posição).

O jogo é interessante pois ajuda a incentivar a construção de um raciocínio lógico para a sua solução. Podemos por exemplo pensar que o jogador deva escolher, em cada passo, a combinação que minimiza o pior caso do número de modelos possíveis da solução; uma análise por computador prova que, de facto, o jogo fica resolvido em 6 lances neste caso. Uma estratégia prática, que um ser humano poderia utilizar, é a seguinte: começar com quatro marcadores de cores diferentes; de seguida escolher somente combinações que não sejam incompatíveis com a história do jogo. Esta estratégia, que não deixa de ser extremamente intuitiva, resolve o jogo em média em 4.776 passos!

D.Knuth provou em 1977 que o jogador que tenta adivinhar o código pode sempre fazê-lo em 5 ou menos tentativas. Outros jogos em que estão disponíveis mais cores ou maior número de marcadores são de grande interesse matemático, pois são muito mais complexos do que este.

terça-feira, Janeiro 02, 2007

O xadrez (parte III) - xadrez com dois pares de jogadores

Voltando mais uma ao xadrez, tema dos ultimos posts, trata-se de um jogo que tem mais de 2 milhões de variantes, entre variantes cujo objectivo é tornar o jogo mais complexo evitando assim empates (o xadrez de Capablanca, um antigo campeão do mundo do jogo, é disso exemplo), variantes que tentam eliminar a preparação das aberturas -ou, também, a vantagem dos computadores - através da aleatorização da posição inicial do jogo (posso, aqui, citar, o xadrez de Fischer), variantes que mudam o jogo alterando a movimentação das peças ou introduzindo novas peças, ou até variantes que transformam o jogo num jogo tridimensional.

Neste post vou introduzir o xadrez com quatro jogadores - "four -way chess" que, longe de ser um jogo tradicional, mostra como a cooperação entre dois jogadores pode ocorrer.





O xadrez de quatro jogadores é um jogo jogado num tabuleiro similar ao xadrez, só com quatro conjuntos de peças, um em cada lado do tabuleiro. As variantes divergem no número de linhas entre o conjunto de peças e o "tabuleiro principal". Neste caso há uma. Nesta variante, cada par de jogadores do lado oposto do tabuleiro, pertencem à mesma equipa e cooperam no sentido de vencer o jogo, isto é, dar mate a cada um dos dois reis adversários.

Trata-se, claramente, de um jogo muito mais complexo que o xadrez normal, pelo que o seu pendor estratégico é muito mais aprofundado. Aliás, programas de computador que joguem bem este jogo são, basicamente, "ficção científica", no estado da arte das técnicas de Inteligência Artificial: com efeito, a explosão combinatória resultante de, em cada lance, 4 jogadores jogarem, torna o jogo muito mais difícil de ser analisado por um computador com a típica pesquisa alfa-beta.

Este jogo necessita de uma coordenação eficaz entre os dois jogadores. Um jogador poder-se-ia sentir tentado a não defender o seu colega de equipa contra um ataque inimigo, resguardando as suas peças, ou a não colaborar num ataque contra um rei inimigo para se proteger. Contudo, a prática revela que isso acaba por ser prejudicial para os dois jogadores, porque o inimigo consegue dar mate ao colega de equipa e depois ao jogador que tomou a opção de não o ajudar. Aliás, os jogos de equipa são interessantes por isso mesmo: a qualidade da equipa pode ser radicalmente diferente da soma das qualidades dos seus elementos. Isto pode ser considerado em analogia com muitos desportos colectivos, como por exemplo, o futebol.

A teoria do jogo encontra-se muito pouco desenvolvida devido não só ao relativo desconhecimento deste jogo como também à sua complexidade, o que o torna interessante como "plataforma exploratória". Não existem aberturas standard, embora vigorem os princípios habituais no xadrez como o controlo do centro. Os peões demoram muito a alcançar o centro do tabuleiro pelo que não existem grandes lutas entre formações de peões, servindo estes um papel importante na defesa do rei. A defesa do rei também é mais difícil de assegurar, pois o rei pode ser vítima de ataques de dois jogadores em simultâneo.

Quanto ao valor das peças, não será difícil de conjecturar que as peças deslizantes - a dama, a torre, o bispo - verão o seu valor aumentado relativamente ao jogo tradicional. A dama, em particular, vai-se tornar ainda mais poderosa do que já era devido ao seu enorme raio de acção, principalmente quando se encontra no centro do tabuleiro, e o acto do rei se colocar no fila aberta é, neste jogo, praticamente suicídio. Já o cavalo e o rei vêem o seu valor reduzido; no que se possa, eventualmente, definir como um final, este estará bastante exposto se ainda se encontrarem peças pesadas no tabuleiro, ao passo que o cavalo tem um movimento demasiado curto para o tamanho (160 casas!) do tabuleiro.

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.

segunda-feira, Novembro 20, 2006

Fases de um jogo de tabuleiro

Os quatro jogos de tabuleiro até aqui analisados, se bem que superficialmente, permitem constatar a existência de algumas tendências que se revelam comuns entre eles.

No xadrez, é bem visível uma divisão do jogo em 3 fases distintas: abertura, meio-jogo e final e, de certa maneira, isso também acontece no jogo das damas.
Estas três fases caracterizam-se por terem diferente acuidade estratégica e táctica, bem assim como o número de peças ir diminuindo gradualmente ao longo do jogo. Nem todos os jogos têm de ter as três fases (há aqueles que acabam mais cedo), mas existe uma tendência para o jogo ir evoluindo de acordo com esta divisão.


A abertura


Uma posição típica do meio jogo


Um final, com as duas torres no tabuleiro.

Contudo, esta divisão nem sempre é óbvia, como acontece no jogo do Go em que o jogo caminha, é certo, para o seu final se tivermos em conta que em cada jogada é colocada uma pedra numa intersecção, mas não é óbvio em que fase do jogo este se encontra a cada momento. De forma semelhante, o jogo "Arimaa", em baixo (página oficial) que foi inventado com o principal objectivo de ser difícil de jogar por parte dos computadores, tem sempre o mesmo número de peças no tabuleiro porque não existem capturas não existindo por isso finais no sentido do xadrez e, por outro lado, as aberturas também não têm o carácter de serem bem estudadas, como no xadrez por serem "aleatórias".


O jogo Arimaa

segunda-feira, Novembro 13, 2006

O jogo das Damas (parte II)

O jogo das damas é um jogo simples também do ponto de vista computacional. Apesar de ser jogado num tabuleiro de dimensões semelhantes ao do xadrez, apresenta diversas características que o simplificam sobremaneira:
- Apenas metade das casas do tabuleiro são efectivamente usadas;
- Todas as peças são iguais e têm movimentos simples. O facto de as peças serem iguais (à excepção dos "reis") leva a que as bases de dados dos finais tenham um número mais reduzido de posições.
- As damas 8x8 tradicionais, apresentam menos peças no tabuleiro que o xadrez.

Desde 1992 que o jogador mais forte do mundo é um programa de computador, batendo facilmente qualquer adversário humano. Nesse ano, era o programa Chinook. Actualmente já foram resolvidos todos os finais com 10 peças ou menos, tendo sido provado que algumas aberturas levam a um empate se ambos os jogadores jogarem de forma perfeita. Se bem que não se sabe ainda quando isso será possível, acredita-se que, em breve, o jogo das damas 8x8 poderá ser o primeiro jogo não trivial a ver o valor da sua posição inicial determinado (existe elevada probabilidade de ser um empate).

O jogo das Damas

Seria difícil conceber que as mesmas civilizações que criaram maravilhas abstractas do mundo como as Pirâmides, não tivessem também exercícios abstractos do intelecto como este. E, de facto,pensa-se que o jogo das damas, um dos jogos mais jogados em todo o mundo na sua multiplicidade de variantes, nasceu no Egipto. Ou, pelo menos, já lá era jogado 4000 anos antes de Cristo, sendo por isso talvez legítimo pensar-se que foi o antecessor do xadrez, até porque as regras são mais simples e as peças mais simples de fazer.


Um tabuleiro de damas, 8*8

Actualmente, o jogo joga-se normalmente em tabuleiros 10x10 (International Draughts) ou 8x8 (English Draughts, também conhecido por American Checkers), mas há muitas outras variantes que se podem jogar com as mesmas peças. Na realidade a forma de damas que eu aprendi a jogar é uma mistura entre as duas acima.

As regras são muito simples e, em moldes gerais, as seguintes: cada jogador tem o mesmo número de peças iguais, que se movem na diagonal e "saltam" sobre as peças adversárias, desde que haja espaço para tal, tomando-as. O jogador é sempre obrigado a capturar as peças do adversário caso isso seja possível. Ganha o primeiro jogador que eliminar todas as peças do adversário do tabuleiro. Existem também peças superpoderosas, os "reis", que são obtidas por um jogador quando este alcança a última fila do tabuleiro, e que podem mover-se um número arbitrário de casas na diagonal. O facto de todas as peças serem colocadas em casas de uma das cores faz com que efectivamente apenas metade das casas do tabuleiro sejam usadas no desenrolar do jogo.

O jogo das damas é normalmente mais curto que o jogo do xadrez, e claramente mais simples nas suas implicações estratégico-tácticas.

sexta-feira, Outubro 27, 2006

O gamão (parte II)

Outra coisa interessante neste jogo é que o gamão tem um número muito menor de posições legais (aproximadamente 10^20) que o Go ou mesmo que o xadrez mas não se presta a uma análise por força-bruta como este último. Isto porque o número de jogadas possíveis em cada posição, normalmente 20, multiplicado pelo número de possibilidades dos dados, torna o número de possibilidades a analisar em cada posição da ordem das centenas. Assim sendo, seria de esperar que o gamão resistisse aos ataques dos computadores. Contudo, não é esse o caso. Os melhores programas de computador de gamão estão ao nível de ou ligeiramente acima dos melhores jogadores humanos. Usam técnicas da Inteligência Artificial que parecem intuitivamente levar mais facilmente a agentes inteligentes do que pesquisa de força-bruta: redes neuronais e outras formas de aprendizagem.

Interessante ver, pois, que os jogos mais conhecidos na antiguidade são jogos de dois jogadores, mas que materializam formas diferentes de olhar para a estratégia como parte integrante de um jogo de tabuleiro. O xadrez e o Go fazem depender o seu desfecho unicamente do mérito e da perícia dos seus jogadores, ao passo que o gamão reconhece que existe um factor desconhecido, a sorte, que influencia a vida de uma pessoa.

Falo aqui ainda de jogos abstractos, que demonstram o poder de abstracção que as culturas que os inventavam, há milhares de anos atrás, já possuíam. E é talvez devido a essa universalidade que estes jogos continuam, na actualidade, a ser jogados.

O gamão



Não faria sentido falar dos três mais antigos jogos de tabuleiro sem falar do gamão. Diz-se que era jogado pelo menos 1000 anos antes do xadrez.
Joga-se numa "pista" unidimensional, sendo o objectivo do jogo levar todas as peças ("checkers") de um lado ao outro do tabuleiro.
Vence o primeiro jogador a fazê-lo, e a pontuação pode ser maior se a margem pela qual vence for muito grande (se o adversário não tiver conseguido levar nenhuma das suas peças até à fila de chegada, o jogador que vence consegue pontuação a dobrar), o que não acontece no jogo do xadrez nem no jogo do Go.
Mas o factor que o distingue de forma mais marcada dos outros dois jogos que referi é o factor sorte. O jogador move as suas peças conforme lhe seja permitido por um dado que é lançado em cada jogada. Não é, por isso um jogo completamente equilibrado como o jogo do xadrez ou o jogo do Go.

sexta-feira, Outubro 20, 2006

O jogo do Go



O jogo do Go é um dos mais simples e simultaneamente um dos mais complexos jogos de estratégia que existem, apesar de pouco divulgado no ocidente. Inventado na China, provavelmente entre 3000 e 4000 anos atrás, é um dos três jogos de tabuleiro antigos que ainda é jogado (os outros são o xadrez e o gamão).

É simples, pois as regras são bastante simples. Joga-se num tabuleiro 19x19 colocando sucessivamente pedras em intersecções livres. Para jogar basta colocar uma pedra numa intersecção que tenha linhas adjacentes livres. O objectivo é também simples: conquistar a maior parte de território possível, rodeando-o com pedras do jogador.

É complexo, pois estima-se que existam 10^700 jogos de Go diferentes. O número de estratégias possíveis é enorme, e aquilo que é bom a curto prazo (i.e ganhar território imediatamente) pode ser mau globalmente, pois o adversário pode ganhar outro tipo de vantagens. Ao contrário do xadrez não existe nenhum "balanço material" claro, o que, aliado ao facto dos jogos serem normalmente longos e existir um enorme número de lances legais em cada posição (entre 200-250 normalmente) torna impossível tentar jogar Go com uma aproximação de força bruta. Na realidade, o jogo do Go é considerado o último bastião do domínio intelectual humano, que resistiu ao ataque dos computadores.

quinta-feira, Outubro 12, 2006

Estratégia e Táctica

Ao passo que o post dois acima ilustrou um motivo táctico do xadrez, o anterior ilustra um motivo estratégico. Muitos jogos de tabuleiro apresentam uma ou as duas (táctica ou
estratégia), onde se entende a táctica como sendo um conjunto concreto de lances que
levam a ganhos importantes e a estratégia como um conjunto de ideias de médio-longo
prazo que se materializam num plano coerente. Normalmente os computadores são monstros tácticos, encontrando combinações facilmente, tendo muito maiores dificuldades em jogos/posições onde a estratégia é o elemento predominante, uma vez que o lance onde os frutos do plano são obtidos está normalmente muito para lá da sua árvore de procura. Falarei mais da forma como os computadores normalmente jogam jogos
de tabuleiro na apresentação de outros jogos de tabuleiro diferentes.

Xadrez - um jogo de tabuleiro (parte 2)


(Efim-Capablanca, 1924)

Nesta posição, de um carácter completamente diferente da anterior, as negras têm um
plano: explorar as fraquezas dos peões brancos b3 e c3, levando à sua captura ou à degradação ainda maior da posição branca. Assim, usando a pressão sobre esses peões, as negras vão conseguir vencer o jogo.

segunda-feira, Outubro 09, 2006

Xadrez - um jogo de tabuleiro

Que maneira melhor de começar esta exploração sobre jogos de tabuleiro, que não começasse naquele que é talvez o mais popular deles : o xadrez? Começar explicando as regras seria um pouco inútil, porque quase já todos as conhecem, ou então http://en.wikipedia.org/wiki/Chess
é uma boa introdução.
Deixo então aqui uma posição com um motivo táctico genial, que para mim resume uma boa parte do que é o xadrez.



As brancas jogam e dão mate em 5 [J.Sousa - A.Rodriguez, 1997]

Atenção: a solução está em baixo.

















Conseguiu adivinhar?
1.Dh5!! (este lance é impressionante, pois não só a dama fica atacada, como as duas
torres também. Agora as negras têm três maneiras de se tentarem defender contra
a ameaça de mate em h7:
1. ... gxh5 2. Bxh7 mate;
1. ... Cxd3 de nada serve pois as brancas jogam Dxh7 mate;
1. ... Bxg5 para destruir o cavalo e evitar o mate, mas as brancas jogam outro
lance espectacular 2. Dxh7+!! Rxh7 3.hxg5+. Se 3. ... Cxh1, segue-se 4. Txh1+ Rg8
5. Th8 mate e se 3. ... Ch3 segue-se 4. Txh3+ Rg8 5. Th8 mate. Obviamente que se 3. ... Rg8 segue-se logo Th8 mate.

quinta-feira, Outubro 05, 2006

Começo hoje este blog sobre jogos de tabuleiro. E, para o fazer, nada melhor do que começar pelo início. O que é um jogo de tabuleiro? Procuram-se definições.

Há a visão lúdica, para a qual um jogo de tabuleiro não é mais que uma forma de diversão.
Há a visão competitiva, em que o jogo de tabuleiro é um meio de se superiorizar a um adversário.
Há a visão de cooperação, em que vários individuos dentro de uma equipa cooperam para vencer um jogo de tabuleiro.
Há a visão matemática ou computacional, que vê um jogo de tabuleiro simplesmente como a procura de uma estratégia num espaço de estados, finito ou infinito.
E há muitas outras maneiras de ver um jogo de tabuleiro.

Neste blog, vou falar de alguns jogos de tabuleiro, e descrevê-los nas suas várias vertentes.