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.