´ picos sobre Jogos Mancala - To ´ tica e Inteligˆ Matema encia Artificial∗ Jeroen Donkers, Jos Uiterwijk & Alex de Voogt Univ. Maastricht, Univ. Maastricht, Univ. Leiden A fam´ılia de jogos Mancala oferece boas oportunidades para efectuar nova investiga¸c˜ao, tanto no dom´ınio da Matem´ atica como no da Inteligˆencia Artificial. Para ilustrar este facto, iremos apresentar um resumo de resultados h´ a muito conhecidos e de outros mais recentes sobre estes jogos. Embora os investigadores de jogos de tabuleiro possam conhecer os jogos Mancala, as propriedades gerais desta fam´ılia de jogos ser˜ ao explicadas, na medida em que s˜ao relevantes para a compreens˜ao dos resultados. Estes reflectem, sobretudo, as caracter´ısticas matem´aticas dos jogos Mancala, embora as ciˆencias inform´aticas tenham tamb´em desempenhado um papel importante na investiga¸c˜ao apresentada. O artigo inclui tamb´em investiga¸c˜ao no dom´ınio da Inteligˆencia Artificial, terminando depois com uma an´ alise sobre as novas oportunidades de investiga¸c˜ao, tanto em Matem´atica como em Inteligˆencia Artificial. Estas oportunidades n˜ ao se restringem a` investiga¸c˜ao te´orica pura, incluindo tamb´em quest˜oes que permitem a coopera¸c˜ao interdisciplinar no dom´ınio da investiga¸c˜ao aplicada.
Os jogos Mancala Os jogos Mancala s˜ao jogos de tabuleiro utilizados praticamente em todo o mundo com diversas varia¸c˜oes, que seria imposs´ıvel descrever aqui na sua totalidade. Para obter uma panorˆ amica circunstanciada, consultar as obras de Murray (1952) e Russ (2000). At´e agora, todos os jogos Mancala parecem partilhar as seguintes propriedades: 1. S˜ ao jogados num tabuleiro com um certo n´ umero de c´elulas ou casas, normalmente dispostos em duas ou mais filas. Por vezes, s˜ao utilizadas c´elulas adicionais a que chamaremos dep´ositos. ∗
Traduzido do original “Mancala games”, in Step by Step, J. Retschitzki & R. HaddadZubel (eds), com as devidas autoriza¸co ˜es.
Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
70
Jogos Mancala
2. S˜ ao jogados com uma colec¸c˜ao de contas iguais (pedras, sementes, moedas ou conchas). 3. Os jogadores possuem c´elulas e n˜ao contas. Frequentemente, um jogador tem todos as c´elulas de um dos lados do tabuleiro. 4. As jogadas s˜ ao feitas por sementeira, que ´e uma forma de contar (ver abaixo). 5. Depois (ou durante) a sementeira, as contas podem ser capturadas. (Por isso, os jogos Mancala s˜ ao tamb´em chamados jogos de contar-ecapturar). 6. O objectivo geral do jogo ´e capturar o maior n´ umero poss´ıvel de contas. Normalmente, os jogos Mancala envolvem dois jogadores, mas s˜ao conhecidos jogos solit´arios, assim como jogos para trˆes ou mais jogadores. As jogadas s˜ ao feitas por sementeira, o que significa que o jogador selecciona uma das suas c´elulas, pega em todas as contas nela contidas e coloca-as uma por uma em c´elulas consecutivas, no sentido dos ponteiros do rel´ ogio ou no sentido inverso. Por vezes, a sementeira ´e feita em m´ ultiplas voltas, o que significa que, se a sementeira acaba numa c´elula que n˜ ao est´a vazia, todas as contas dessa c´elula s˜ ao retiradas e a sementeira continua at´e que seja encontrada alguma condi¸c˜ao de paragem. Em alguns jogos, um jogador pode continuar com uma nova jogada, se a sementeira terminar no seu dep´ osito. Se a sementeira envolver muitas contas, poder´ a alcan¸car a c´elula de onde partiu. Depender´ a das regras saltar ou n˜ao essa c´elula. Depois ou durante a sementeira, pode ocorrer uma captura: o jogador fica com todas as contas de uma c´elula e coloca-as no seu dep´osito (ou mant´em-nas `a parte se n˜ ao existir dep´osito). Em alguns jogos, as pedras capturadas entram de novo na fila de c´elulas desse jogador. A condi¸c˜ao segundo a qual uma captura pode ser feita e qual a c´elula que pode ser esvaziada depende das regras do jogo. Em termos gerais, h´ a quatro tipos de captura: 1. Captura de n´ umero: ´e permitido ao jogador capturar contas quando a sementeira termina numa c´elula do advers´ ario que, por exemplo, cont´em 2 ou 3 contas depois da sementeira. Em alguns jogos, tamb´em todas as c´elulas anteriores do advers´ario que contˆem 2 ou 3 contas podem ser esvaziados. (Esta regra ´e utilizada no Awale e no Awari e ser´a chamada a regra de captura 2-3). Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
71
2. Captura de lugar: ´e permitido ao jogador capturar se a sementeira terminar numa determinada c´elula. Por exemplo, se algu´em terminar numa c´elula sua que estava vazia, a conta dessa c´elula e todas as contas da c´elula oposta do advers´ ario podem ser capturadas. (Esta regra ´e utilizada em muitos jogos asi´aticos e tamb´em no Kalah, e ser´a chamada a regra da captura oposta). Nos jogos Mancala indianos, os resultados de uma sementeira, por exemplo, a captura ou a continua¸c˜ao/conclus˜ao, n˜ ao dependem da c´elula em que a u ´ltima conta foi colocada, mas sim da c´elula seguinte. 3. Captura en-passant (uma forma especial de captura de n´ umero): durante uma jogada, o advers´ ario pode capturar as contas numa c´elula sua, assim que ele contenha, por exemplo, 4 contas. 4. Captura em dep´ osito (uma forma especial de captura de lugar): as contas que, se permitido, forem colocadas no dep´osito de um jogador durante uma jogada s˜ ao por ele capturadas automaticamente. (Esta regra ´e comum no Dakon). Para al´em destas regras, muitos jogos tem outras regras como o “empr´estimo”de contas em alguns jogos indianos ou o encerramento de c´elulas em jogos de s´eries m´ ultiplas como o Dakon. Normalmente, o jogo termina quando um dos jogadores captura a maior parte das contas ou quando um dos jogadores j´ a n˜ ao consegue jogar mais.
A matem´ atica dos jogos Mancala Os jogos Mancala parecem simples, quando se verifica que s˜ ao determin´ısticos (n˜ ao h´ a acaso envolvido), que se disp˜ oe de perfeita informa¸c˜ao (excepto no que se refere `a dificuldade de recordar o conte´ udo de uma c´elula cheia) e que n˜ ao h´ a muitas op¸c˜oes por jogada, normalmente n˜ ao mais do que o n´ umero de c´elulas numa fila. No entanto, o facto de uma u ´nica jogada poder ter efeito sobre o conte´ udo de todas as c´elulas do tabuleiro, torna dif´ıcil prever as consequˆencias mesmo de apenas algumas jogadas e ainda menos do resultado final do jogo.
As posi¸ c˜ oes Mancala Uma propriedade matem´ atica que pode dar uma ideia da complexidade dos jogos Mancala ´e o n´ umero de posi¸c˜oes poss´ıveis. Uma posi¸c˜ao nos jogos ManBoletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
72
Jogos Mancala
cala consiste numa certa distribui¸c˜ao das contas pelas c´elulas do tabuleiro, mas inclui tamb´em as contas capturadas quer nos dep´ ositos no tabuleiro, quer guardadas pelos jogadores se n˜ ao houver dep´ ositos. Al´em disso, uma posi¸c˜ao inclui o conhecimento de qual o jogador que dever´ a jogar a seguir. O n´ umero de posi¸c˜oes poss´ıveis depende do n´ umero de c´elulas (e dep´ ositos) e do n´ umero de contas. Este n´ umero p pode ser calculado atrav´es da seguinte f´ ormula deduzida a partir do c´ alculo combinat´ orio b´ asico: p=k
n+m−1 m
Nesta f´ormula, k ´e o n´ umero de jogadores, m ´e o n´ umero total de contas e n ´e ou o n´ umero total de c´elulas e de dep´ositos ou o n´ umero total de c´elulas somado ao n´ umero de jogadores, se n˜ ao existirem dep´ositos. O n´ umero p aumenta muito rapidamente com o aumento do n´ umero de c´elulas e de contas. A tabela seguinte mostra o n´ umero de posi¸c˜oes para um tabuleiro de Mancala com duas filas de seis c´elulas e dois dep´ositos, no caso de dois jogadores
(1 (2 (3 (4 (5 (6
conta por c´elula) contas por c´elula) contas por c´elula) contas por c´elula) contas por c´elula) contas por c´elula)
m 1 2 3 4 5 12 24 36 48 60 72
p 28 210 1 120 4 760 17 136 10 400 600 7 124 934 600 5,25194 × 1011 1,313244 × 1013 1,725416 × 1014 1,4776 × 1015
Evidentemente, o n´ umero de posi¸c˜oes poss´ıveis diminui quando apenas s˜ao consideradas as contas ainda em jogo (como se faz, por exemplo, na an´ alise de Retschitzki -1990). S´ o um certo n´ umero de todas as posi¸c˜oes poss´ıveis pode surgir efectivamente durante os jogos, dependendo da posi¸c˜ao de partida e das regras exactas do jogo. No jogo de Kalah (ver abaixo), s´ o cerca de 5% das posi¸c˜oes poss´ıveis podem surgir num jogo real (Irving et al., 2000). Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
73
Aparentemente, s´o algumas posi¸c˜oes especiais dos jogos Mancala podem ser compreendidas integralmente do ponto de vista matem´ atico. Em primeiro lugar, iremos analisar um conjunto de posi¸c˜oes especiais no jogo Tchoukaillon.
Posi¸ c˜ oes Tchoukaillon Broline e Loeb (1995) analisaram os jogos Mancala, recorrendo a uma sua variante solit´aria, criada artificialmente: o Tchoukaillon. Este jogo foi desenvolvido por Deledicq e Popova e ´e jogado num tabuleiro com apenas uma fila de c´elulas e com um dep´osito no extremo direito das c´elulas. No in´ıcio, todas as c´elulas, excepto o dep´osito, contˆem um determinado n´ umero de contas. O objectivo ´e recolher todas as contas no dep´ osito. S´o s˜ao permitidas as jogadas que terminam directamente no dep´ osito, n˜ao sendo admitidas sementeiras para al´em do dep´ osito. A solu¸c˜ao do Tchoukaillon passa por encontrar a ordem correcta das jogadas que faz com que todas as contas sejam colocadas no dep´ osito. Aparentemente, s´o algumas posi¸c˜oes de Tchoukaillon podem ser efectivamente resolvidas. A tabela seguinte cont´em as primeiras dez dessas posi¸c˜oes. 1 2 3 4 5
0 0 0 0 0
0 0 0 0 0
0 0 0 3 3
0 2 2 1 1
1 0 1 0 1
6 7 8 9 10
0 0 0 0 0
0 0 0 0 5
4 4 4 4 3
2 2 2 2 1
0 0 2 2 1
0 1 0 1 0
Para cada n´ umero de contas ainda em jogo, parece haver apenas uma posi¸c˜ao que pode ser resolvida. Para compreender isso, ´e necess´ario ter em conta que em qualquer posi¸c˜ao dada, apenas uma jogada ´e adequada. Se houver mais do que uma c´elula que contenha o n´ umero suficiente de contas para atingir o dep´ osito, ´e preciso seleccionar a que estiver mais `a direita. Se se seleccionar outra c´elula, o conte´ udo da c´elula mais `a direita ir´ a aumentar de uma conta, o que significa que a posi¸c˜ao deixar´a de poder ser resolvida. As posi¸c˜oes que podem ser resolvidas s˜ao chamadas posi¸c˜oes Tchoukaillon. Estas podem ser deduzidas atrav´es de um algoritmo simples: 1. A primeira posi¸c˜ao Tchoukaillon ´e a posi¸c˜ao com apenas uma u ´nica conta na c´elula mais `a direita. 2. Dada uma posi¸c˜ao Tchoukaillon, a posi¸c˜ao seguinte pode ser constru´ıda tirando uma conta de cada c´elula, come¸cando pela direita, at´e Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
74
Jogos Mancala
que seja encontrado uma c´elula vazia. Colocam-se todas as contas recolhidas mais uma extra nessa c´elula vazia. As posi¸c˜oes Tchoukaillon n˜ ao desempenham apenas um papel neste jogo artificial. Em qualquer jogo Mancala que inclua a regra de que um jogador pode jogar de novo se uma sementeira terminar no seu dep´ osito, estas posi¸c˜oes s˜ao importantes. Estes jogos incluem o Kalah, o Dakon, o Tchuka Ruma e muitos outros. Se ocorrer uma posi¸c˜ao Tchoukaillon do lado do jogador, este pode ent˜ ao capturar todas as contas nessa posi¸c˜ao. Tamb´em os jogos Mancala que utilizam a regra de captura 2-3 e n˜ao tˆem dep´ ositos (como o Wari e o Awale) beneficiam de posi¸c˜oes Tchoukaillon. Observe a seguinte fase final do Awale: a)
1 0
0 0
0 4
0 3
0 1
0 1
b)
0 1
0 0
0 4
0 3
0 1
0 1
c)
1 1
0 0
0 0
0 *4
0 *2
*1 *2
d)
0 1
0 0
0 0
0 *4
1 *2
*0 *2
e)
0 1
0 0
0 0
0 *4
0 *2
*1 *0
f)
0 1
0 0
0 0
0 *4
1 *2
*0 *0
g)
0 1
0 0
0 0
0 *0
0 *3
*1 *1
h)
0 1
0 0
0 0
0 *0
1 *3
*0 *1
i)
0 1
0 0
0 0
0 *0
0 *0
*1 *0
j)
0 1
0 0
0 0
0 *0
1 *0
*0 *2
k)
0 1
0 0 0 0 0 0 *0 *0 Fim do jogo
*1 *0
Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
75
Os n´ umeros em negrito indicam a c´elula que vai jogar. Nas jogadas c) a k) as zonas asteristicadas indicam as posi¸c˜oes Tchoukaillon. Seguindo essas jogadas, o jogador Sul consegue capturar 8 contas. No melhor dos casos, ´e poss´ıvel at´e capturar 20 contas, utilizando uma sequˆencia de 21 posi¸c˜oes Tchoukaillon. O jogo dever´ a ter atingido a seguinte rara posi¸c˜ao com Norte a jogar: 0 0 0 0 0 1 7 5 3 1 2 2 Estes “finais Tchoukaillon” tˆem algumas semelhan¸cas com as famosas t´ acticas do Awale, chamadas “2-1” e “3-1” (Retschitzki, 1990; N’Guessan, 1992).
Tchuka Ruma O Tchoukaillon deriva do jogo Mancala para um jogador j´ a existente, o Tchuka Ruma. A origem deste jogo, por sua vez, e onde ´e efectivamente jogado ´e ainda tema de debate cient´ıfico (Campbell e Chavey, 1995). Diferentes autores referem-se `a ´India, a`s Filipinas, `as Maldivas e at´e `a R´ ussia. O nome sugere uma origem indon´esia ou malaia. Provavelmente, o jogo ter´a sido inventado independentemente em diversos lugares, uma vez que as suas regras s˜ao apenas um pequeno subconjunto das regras de muitos jogos Mancala para dois jogadores. O Tchuka Ruma pode ser jogado em qualquer tabuleiro de Mancala, com ou sem dep´ ositos. O jogador selecciona apenas uma c´elula ou dep´ osito como dep´osito principal (o ruma) e decide que outras c´elulas incluir no jogo. O objectivo do Tchuka Ruma ´e recolher todas as contas no ruma. Ao contr´ ario do Tchoukaillon, a sementeira ´e feita em m´ ultiplas voltas e pode ultrapassar o ruma. O jogo come¸ca com um n´ umero igual de contas em cada c´elula. O Tchuka Ruma pode ser jogado na Internet no site: http://fanth.cs.unimaas.nl/games/ruma/index.html. Parece ser um jogo bastante dif´ıcil. A maior parte das pessoas s´o consegue resolvˆe-lo com um n´ umero muito pequeno de c´elulas (at´e 4) e de contas por c´elula (1 ou 2). Exactamente como o Tchoukaillon, nem todas as posi¸c˜oes iniciais de Tchuka Ruma podem ser resolvidas. Campbell e Chavey (1995) apresentam uma an´ alise circunstanciada da matem´atica do jogo, mostrando que ´e poss´ıvel provar que algumas posi¸c˜oes iniciais n˜ao podem ser resolvidas. Por exemplo, se existirem n c´elulas e k contas por c´elula, n˜ ao h´ a solu¸c˜ao se k = (n + 1)i com i 1 ou se k = n(n + 1)i , com i 0. Mostram tamb´em Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
76
Jogos Mancala
que ´e imposs´ıvel provar que uma dada posi¸c˜ao de Tchuka Ruma pode ser resolvida, excepto produzindo efectivamente uma solu¸c˜ao. Com uma pequena altera¸c˜ao das regras, podemos definir uma “solu¸c˜ao” como a sequˆencia de jogadas que captura o maior n´ umero poss´ıvel de contas. Na tabela seguinte, apresentamos o m´ aximo n´ umero de contas que podem ser capturadas para um certo n´ umero de posi¸c˜oes Tchuka Ruma.
C´elulas 1 2 3 4 5 6 7 8 9 10 11 12
1 1 3 3 3 3 5 5 5 5 7 7
1 2 4 8 7 10 14 12 15 17 19 19
3 1 2 7 14 15 19 24 27 30 33 36
Contas 3 4 8 10 1 15 2 1 6 2 24 30 27 35 32 40 36 45 40 50 44 55 48 60
por c´elula 6 7 7 14 17 21 24 28 1 35 2 1 13 2 48 9 54 63 60 70 66 77 72 84
7 16 24 32 40 48 1 2 72 80 88 96
8 4 27 36 45 54 63 1 2 90 99 108
9 20 30 40 50 60 70 80 1 2 110 120
As entradas enfatizadas na tabela indicam as posi¸c˜oes em que nem todas as contas do tabuleiro podem ser capturadas. As c´elulas perto da diagonal s˜ ao posi¸c˜oes em que K = n ou K = n + 1, ambos casos especiais da f´ ormula anterior. A tabela sugere que ´e mais prov´ avel existirem solu¸c˜oes, se tanto o n´ umero de c´elulas como o n´ umero de contas por c´elula aumentarem. Campbell e Chavey verificaram as posi¸c˜oes at´e 10 c´elulas para uma grande quantidade de contas (100 000). Os seus resultados confirmam esta sugest˜ao. Depois de saber se todas as contas podem ser capturadas, ´e tamb´em interessante determinar qual o n´ umero m´ınimo de jogadas que ´e necess´ario ´ uma tarefa trivial escrever um para capturar todas as contas poss´ıveis. E programa inform´ atico para encontrar estas solu¸c˜oes “´optimas”. O Tchuka Ruma ´e claramente um jogo dif´ıcil para os humanos, mas trivial para os computadores, o que n˜ ao ´e certamente o caso de outros jogos Mancala, como o Awari e o Bao. Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
77
Dakon Um dos jogos Mancala relacionado com o Tchuka Ruma ´e o Dakon, jogado sob diferentes nomes nas Maldivas, na Indon´esia e nas Filipinas. Este jogo para duas pessoas ´e jogado num tabuleiro com duas filas de c´elulas e dois dep´ ositos. Recorre `a sementeira em m´ ultiplas voltas e inclui a regra da captura oposta. Um jogador pode continuar uma jogada se uma sementeira terminar no seu dep´ osito. Para conhecer as regras exactas, consultar Donkers et al., 2000. O Dakon consiste em s´eries m´ ultiplas. A primeira s´erie come¸ca com tantas contas em cada c´elula quantas as c´elulas em cada fila. Os jogadores jogam a` vez, at´e que um deles j´a n˜ ao consegue jogar mais. Para a segunda s´erie, ambos os jogadores enchem as c´elulas com as contas capturadas. Cada c´elula tem de conter a quantidade original de contas. Se um jogador n˜ ao consegue encher todas as suas c´elulas completamente, as c´elulas (parcialmente) vazias s˜ao cobertas com uma folha e n˜ ao contam nessa s´erie. Um jogador que n˜ ao consiga encher qualquer c´elula perde o jogo. Atrav´es de c´alculos manuais, chegou-se `a conclus˜ao que, para um Dakon com 8 c´elulas de cada lado, ´e poss´ıvel ao primeiro jogador na primeira s´erie recolher tantas contas na primeira vez, que o advers´ ario j´ a n˜ ao consegue capturar contas suficientes para iniciar a s´erie seguinte. Assim, este jogo pode ser ganho pelo primeiro jogador numa u ´nica jogada. Isso significa que, do ponto de vista matem´ atico, este n˜ao ´e um jogo para duas pessoas mas um mero puzzle para um jogador, muito semelhante ao Tchuka Ruma. A u ´nica diferen¸ca entre resolver o Tchuka Ruma e encontrar uma sequˆencia de jogadas vencedora no Dakon ´e que neste um jogador n˜ ao pode seleccionar todas as c´elulas para jogar a partir delas, mas apenas as c´elulas do seu lado do tabuleiro. Uma vez que n˜ ao ´e poss´ıvel seleccionar todas as c´elulas, n˜ ao ´e poss´ıvel capturar todas as contas de uma s´o vez. Se houver n c´elulas de cada lado do tabuleiro, ent˜ ao ´e imposs´ıvel capturar mais do que n/2 -1 contas. Esta f´ ormula fornece apenas um limite inferior; a tabela seguinte mostra o n´ umero exacto de contas que n˜ ao podem ser capturadas para diferentes valores de n. n 4 5 6 7 8 9 10 2 3 2 2 3 3 4 Para um computador n˜ ao ´e dif´ıcil encontrar estas sequˆencias correctas de jogadas no Dakon, mas para jogadores humanos trata-se de uma tarefa complicada. O facto de estes u ´ltimos terem sido capazes de encontrar essa sequˆencia para n = 8 ´e not´ avel, especialmente porque as sequˆencias enconBoletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
78
Jogos Mancala
tradas s˜ ao muito longas: uma delas tem 93 jogadas. Em Donkers et al., 2000, mostr´amos que o computador pode ser utilizado para analisar como foi poss´ıvel encontrar estas sequˆencias manualmente. Em vez de nos limitarmos a executar a simples tarefa de encontrar uma solu¸c˜ao no computador, tent´ amos reproduzir o comportamento cognitivo humano. As sequˆencias de jogadas que, deste modo, obtivemos no computador eram semelhantes `as sequˆencias encontradas pelos humanos. Gostaria de dizer que o facto de se saber que existem aberturas vencedoras n˜ ao impede o jogo de ser jogado. Mesmo com uma pequena adapta¸c˜ao das regras, o Dakon ainda ´e um jogo muito dif´ıcil. Uma altera¸c˜ao singular que foi efectivamente adoptada nas Filipinas ´e come¸car a primeira s´erie simultaneamente com os dois jogadores.
Bao ´ O Bao ´e uma variante dos jogos Mancala muito popular na Africa Orien´ tal, sendo tamb´em jogado de forma organizada oficialmente na Tanzˆ ania. E jogado por dois jogadores num tabuleiro com quatro filas de c´elulas. N˜ao existem dep´ositos (embora haja duas c´elulas especiais no centro do tabuleiro). A sementeira ´e feita em m´ ultiplas voltas. Regras adicionais podem ser encontradas na tese de De Voogt (1995). Durante um jogo de Bao, pode acontecer que uma sementeira pare¸ca perp´etua: depois de um certo per´ıodo, o jogador desiste ou aplica-se alguma regra especial para poder continuar o jogo. Assim, a pergunta te´ orica que pode ser colocada ´e se uma sementeira no Bao pode efectivamente ser perp´etua. Depois de algum tempo, a posi¸c˜ao de partida original dever´ a surgir de novo. Sabe-se que na ´India (ver o artigo do Dr. Balambal Ramaswamy neste volume) esta sementeira perp´etua existe e ´e praticada como uma variante de Pallankhuzi, chamada Seethi Pandi. A forma mais simples de sementeira perp´etua ´e num tabuleiro com apenas duas c´elulas. (Obviamente, a situa¸c˜ao trivial com uma c´elula apenas deve ser ignorada). A primeira c´elula tem trˆes contas, a segunda tem uma conta. Se a sementeira come¸car na primeira, ocorre uma sequˆencia perp´etua. N˜ao ´e dif´ıcil ver que no caso de duas c´elulas, a sementeira perp´etua ocorre se a quantidade maior de contas ´e um n´ umero duas vezes superior ao n´ umero mais pequeno mais um ((3,1), (5,2), (7,3), (9,4) e, em geral, (2k + 1, k)). A sementeira deve come¸car sempre com a quantidade maior. Depois de cada volta da sementeira, o conte´ udo das c´elulas muda ((1,3)-(3,1)-(1,3)-...). Se o jogo come¸car com sete contas numa c´elula e uma noutra, mais Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
79
uma vez ocorre uma sementeira perp´etua, mas agora com um padr˜ ao mais umeros complicado: (7,1)-(3,5)-(6,2)-(3,5)-(1,7)-(5,3)-(2,6)-(5,3)-(7,1). Os n´ sublinhados indicam a c´elula a partir da qual se continua. Depois de oito sementeiras, a posi¸c˜ao original surge de novo. Dizemos que o per´ıodo desta sementeira ´e oito. O padr˜ ao seguinte tem um per´ıodo de apenas trˆes: (9,1)(4,6)-(7,3)-(9,1). Se o jogo come¸car com (7,2), o per´ıodo da sequˆencia parece ser 24. Uma breve an´ alise produz a tabela seguinte em que k ´e um qualquer n´ umero positivo: Posi¸c˜ao inicial [2k+1, k] [4k+2, k] [6k+3, k] [8k+4, k] [10k+5, k] [12k+6, k]
Per´ıodo 2 4 3 6 10 12
´ poss´ıvel provar que todas as posi¸c˜oes da forma (2ak + a, (2b + 1) (E k + b), em que k 1, a 1 e b 0, provocam sementeiras perp´etuas, se a sementeira come¸car com a primeira c´elula.) No caso de duas c´elulas, poder´ a ser poss´ıvel encontrar uma f´ ormula para todas as sementeiras perp´etuas poss´ıveis e respectivos per´ıodos. Para quantidades maiores de c´elulas, esta tarefa ´e muito mais complexa, para n˜ao falar do caso de tabuleiros de verdadeiros jogos Mancala com 10, 12 ou mais c´elulas envolvidas. Alguns jogadores de Bao sugeriram que a situa¸c˜ao do tabuleiro em que o conte´ udo de todas as c´elulas alterna entre 2 e 3 produzir´ a uma sementeira perp´etua, se se come¸car com uma c´elula com duas contas. Com a ajuda de um pequeno programa de computador, verific´ amos isso e descobrimos que ´e verdade. O espantoso ´e que os per´ıodos destas sementeiras perp´etuas s˜ao muito grandes. N˜ ao ´e dif´ıcil perceber por que raz˜ ao ningu´em alguma vez conseguiu verificar a propriedade perp´etua da sementeira: A coluna s´eries indica o n´ umero de vezes que a sementeira d´a a volta a todo o tabuleiro antes de surgir de novo a posi¸c˜ao de partida. Suponhamos que um jogador r´ apido consegue fazer uma s´erie num segundo. No caso de uma sementeira num tabuleiro de 2×8 c´elulas, que ´e a situa¸c˜ao comum no Bao, o jogador teria de continuar a semear durante um mˆes inteiro antes de o padr˜ ao original voltar a surgir. Num tabuleiro de 2×13 c´elulas, isso demoraria mais de 800 anos! Permanece em aberto a quest˜ao de saber que outras sementeiras perp´etuas Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
80
Jogos Mancala
Tamanho do tabuleiro 2 × 1 c´elulas 2 × 2 c´elulas 2 × 3 c´elulas 2 × 4 c´elulas 2 × 5 c´elulas 2 × 6 c´elulas 2 × 7 c´elulas 2 × 8 c´elulas 2 × 9 c´elulas 2 × 10 c´elulas 2 × 11 c´elulas 2 × 12 c´elulas 2 × 13 c´elulas
Per´ıodo
S´eries
60 260 6 312 13 535 118 824 905 471 11 944 136 38 810 079 362 728 700 418 038 808 4 460 747 004 177 651 347 042
(sem sementeira perp´etua) 55 161 2 943 5 038 37 271 245 520 2 835 141 8 228 045 69 414 849 72 909 333 715 501 875 26 365 775 535
podem ocorrer em tabuleiros de Bao reais, mas a an´alise do tabuleiro de 2 c´elulas sugere que deve haver muitas posi¸c˜oes que provocar˜ ao sementeira perp´etua. Uma quest˜ ao em aberto mais importante ´e saber se essas posi¸c˜oes podem ocorrer durante um jogo real de Bao. A investiga¸c˜ao etnogr´afica dever´ a revelar se as sementeiras perp´etuas s˜ao efectivamente utilizadas, como no jogo Seethi Pandi.
Os jogos Mancala na Inteligˆ encia Artificial A Inteligˆencia Artificial (IA) ´e um ramo das ciˆencias inform´aticas que tem por objectivo fazer com que um computador assuma aquilo que normalmente ´e considerado um comportamento inteligente (humano). Existem duas motiva¸c˜oes principais para esta investiga¸c˜ao: a primeira ´e minorar o esfor¸co humano com o aux´ılio dos computadores; a segunda ´e tentar compreender de que modo a inteligˆencia humana ou as opera¸c˜oes mentais funcionam, atrav´es de simula¸c˜oes de computador. Os jogos tˆem desempenhado um papel importante na Inteligˆencia Artificial, n˜ ao s´o porque o jogo ´e considerado uma tarefa tipicamente inteligente, mas tamb´em porque os jogos constituem quase sempre um ambiente fechado com possibilidades limitadas e regras claramente definidas. ´ esta u E ´ltima raz˜ ao que faz com que seja muito mais f´acil para os inBoletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
81
vestigadores de IA lidarem com jogos do que lidarem, por exemplo, com o mercado bolsista. O mais famoso resultado em termos de IA nos jogos ´e obviamente o facto de os computadores actuais conseguirem jogar xadrez ao n´ıvel de grande mestre e de terem mesmo conseguido derrotar o anterior campe˜ao do mundo. Na competitiva corrida entre programas inform´ aticos de xadrez, foram desenvolvidas muitas t´ecnicas que agora v˜ao sendo aplicadas com regularidade noutras a´reas da IA e da inform´ atica. Poder-se-ia dizer que os jogos (e em especial o xadrez) s˜ao a F´ ormula-1 da inform´ atica. A fam´ılia dos jogos Mancala foi introduzida na Inteligˆencia Artificial relativamente cedo, embora a maior parte da investiga¸c˜ao se limite a apenas dois jogos: o Kalah e o Awari.
Kalah O Kalah ´e uma variante moderna, comercial de Mancala. Foi introduzido na d´ecada de 1950 por uma empresa chamada “The Kalah Game Company” (propriedade de W.J. Champion). Em 1960, foi criada uma primeira vers˜ao computorizada do jogo e muitas outras se lhe seguiram. Hoje em dia, ´e at´e mesmo poss´ıvel jogar Kalah no telem´ ovel (numa variante chamada Bantumi; ver http://www.nokia.com/games/bantumi.html). No dom´ınio da Inteligˆencia Artificial, o Kalah tinha sido estudado j´ a em 1964 por Richard Russel, o qual escreveu um programa chamado KALAH que conseguia efectivamente jogar. Em 1968, A.G. Bell escreveu um outro programa inform´atico que conseguia aprender de alguma forma com os erros que fazia. Um ano mais tarde, Slagle e Dixon (1969, 1970) utilizaram o Kalah para ilustrar um outro algoritmo de jogos. Depois deste per´ıodo, o Kalah perdeu o interesse para os investigadores de IA, at´e ao ano passado. Utilizando algumas das t´ecnicas avan¸cadas que foram desenvolvidas para o xadrez, Irving, um aluno de licenciatura da Universidade Caltech, conseguiu descobrir a estrat´egia vencedora para o jogo (Irving et al., 2000). O Kalah ´e jogado por duas pessoas num tabuleiro com duas filas de seis c´elulas e dois dep´ositos adicionais. No in´ıcio, h´ a quatro contas por c´elula. Utilizam-se sementeiras em volta u ´ nica e a regra da captura oposta. O dep´ osito do jogador ´e inclu´ıdo na sementeira, mas o do advers´ ario ´e saltado. Uma sementeira que termine no dep´ osito do pr´ oprio jogador permite-lhe jogar de novo. Em alguns dos programas Kalah, a c´elula a partir da qual a sementeira tem in´ıcio ´e saltado durante uma grande sementeira, mas noutros casos isso n˜ao acontece. O jogo termina quando um dos jogadores j´ a n˜ ao consegue jogar. O outro jogador fica ent˜ ao com todas as contas das suas Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
82
Jogos Mancala
pr´ oprias c´elulas. Ganha o jogador que ficar com mais contas. ´ poss´ıvel alterar um pouco as regras do Kalah e jogar com mais ou E menos contas por c´elula, ou com outro n´ umero de c´elulas por fila. A tabela seguinte mostra o valor te´orico de casos de Kalah, i.e., se o jogador que come¸ca pode ganhar, perder ou empatar, se ambos os jogadores jogarem a um n´ıvel o´ptimo.
1 2 3 4 5 6
c´elula c´elulas c´elulas c´elulas c´elulas c´elulas
Contas por c´elula 1 2 E P G P E G G G E E G G
3 G P G G G G
4 P P G G G G
5 G G G G G G
6 E G P E G ?
Os casos mais simples de Kalah foram resolvidos, considerando todas as posi¸c˜oes poss´ıveis que podem efectivamente surgir durante um jogo. Constru´ıram-se bases de dados onde foram introduzidas todas as posi¸c˜oes e o seu respectivo valor te´ orico. Os casos mais complexos de Kalah foram resolvidos atrav´es de uma a´rvore de pesquisa do jogo. Para estes casos, s´o ´e conhecida explicitamente uma estrat´egia vencedora a partir da posi¸c˜ao de abertura. O programa ´e contudo capaz de encontrar uma estrat´egia o´ptima para todas as posi¸c˜oes que podem ocorrer durante um jogo. Isto significa que o Kalah deixou de ter interesse para os investigadores de IA que querem que o computador jogue como substituto do ser humano ou que lhe seja superior. Por´em, para aqueles investigadores de IA e psic´ologos que est˜ ao interessados no aspecto humano do jogo, os resultados encontrados para o Kalah continuam a ser u ´teis.
Awari O outro jogo Mancala que ganhou interesse para os investigadores de IA ´e ´ o Awari. Este jogo ´e jogado na Africa Ocidental e nas ´Indias Ocidentais, ´ jogado num tabuleiro sendo tamb´em conhecido como Wari ou Awale. E com duas filas de seis c´elulas e sem dep´ositos. A sementeira acontece em voltas u ´nicas e as capturas s˜ao do tipo 2-3. Se o advers´ario j´ a n˜ ao tiver mais contas dispon´ıveis, o jogador deve seleccionar uma jogada que traga novas contas para as c´elulas do advers´ ario. Se isso n˜ ao for poss´ıvel, o jogo Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
83
termina. No Awari, tal como foi programado, a c´elula a partir da qual a sementeira come¸ca n˜ao ´e exclu´ıdo durante uma sementeira longa (com 12 ou mais contas), enquanto noutras variantes do jogo esta c´elula ´e saltada. Esta diferen¸ca nas regras ´e importante para a constru¸c˜ao dos kroos: trata-se de c´elulas contendo tantas contas que uma sementeira d´ a uma volta e meia ao tabuleiro. Desta forma, podem ser capturadas muitas contas numa s´ o jogada. Construir e jogar um kroo ´e um estratagema importante no Awari. O interesse pelo Awari entre a comunidade de IA come¸cou pela constru¸c˜ao de um programa chamado “Lithidon” (Van der Meulen et al., 1990) e tem vindo a aumentar desde ent˜ao. O Awari ´e o u ´nico jogo Mancala que ´e jogado nas Olimp´ıadas da Inform´ atica. Trata-se de um acontecimento em que todos os tipos de programas inform´ aticos competem em v´arios jogos cl´assicos, como o xadrez, as damas e o Go, mas tamb´em em jogos novos e artificiais, como o Hex e o Lines Of Action. No ano passado, decorreu a quinta edi¸c˜ao das Olimp´ıadas da Inform´ atica e o Awari tem estado presente na competi¸c˜ao todos os anos. Embora o Awari seja jogado com a mesma quantidade de c´elulas e a mesma quantidade de contas por c´elula que o Kalah, parece ser mais dif´ıcil para o computador do que este u ´ltimo. Uma vez que o Kalah foi originalmente concebido como um jogo para crian¸cas e o Awari ´e jogado sobretudo por adultos, parece que o Awari ´e tamb´em o jogo mais dif´ıcil para os humanos. Uma das raz˜ oes para isto ´e o facto de no Kalah as contas serem automaticamente capturadas se uma sementeira passa pelos dep´ositos, o que significa que n˜ ao ´e poss´ıvel uma repeti¸c˜ao de posi¸c˜oes. Assim, um jogo de Kalah durar´ a em m´edia menos do que um jogo de Awari. O n´ umero de op¸c˜oes no Awari e no Kalah ´e o mesmo, de modo que o segundo deve ser, no seu conjunto, seguramente mais f´ acil do que o primeiro. O facto de um estudante ter resolvido o Kalah, mas v´ arias equipas rivais de investigadores de IA ainda n˜ ao terem conseguido resolver o Awari, apesar dos seus esfor¸cos nesse sentido, ilustra tamb´em esse facto. Na competi¸c˜ao para resolver o Awari, uma das estrat´egias das equipas participantes ´e construir grandes bases de dados de fases finais. Estas bases de dados contˆem, para um grande n´ umero de posi¸c˜oes, o n´ umero de contas que pode ser capturado e qual a melhor jogada a fazer. A equipa de Lincke (2000) j´ a construiu bases de dados contendo todas as posi¸c˜oes com 35 contas ´ certo que ´e imposs´ıvel criar uma base de dados ou menos ainda em jogo. E completa com todas as posi¸c˜oes poss´ıveis. A expectativa ´e que, brevemente, a ´arvore de pesquisa a partir da posi¸c˜ao inicial e a base de dados de fases finais possam encontrar-se a meio caminho. Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
84
Jogos Mancala
Conclus˜ oes Os jogos Mancala podem colocar muitas quest˜ oes aos matem´aticos. Por´em, s´o algumas dessas quest˜oes foram ainda apresentadas, tendo algumas delas sido respondidas, com ou sem o apoio da inform´ atica. Em alguns casos, estas respostas podem ajudar a desenvolver melhores estrat´egias para jogar Mancala (as posi¸c˜oes Tchoukaillon), mas muitas outras s˜ao menos relevantes para os jogadores (as sementeiras perp´etuas). Esperamos que este artigo possa induzir o leitor a colocar novas quest˜ oes. Os investigadores de Inteligˆencia Artificial analisaram apenas alguns jogos Mancala. Esta abundante fam´ılia de jogos proporciona jogos que diferem muito do Awari e do Kalah, tanto em complexidade como em estrat´egia. Para os investigadores de IA que querem jogar ou resolver novos jogos nos seus computadores, estes jogos oferecem muitas oportunidades. Algumas das quest˜ oes que podem valer a pena ser respondidas pelos investigadores s˜ao: • Qual ´e o efeito de uma regra na complexidade de um jogo Mancala (para diferentes tipos de complexidade?) ´ poss´ıvel prever a complexidade de um jogo Mancala com base num • E dado conjunto de regras? • Que heur´ıstica pode ser utilizada para um computador jogar Mancala? • Como dever˜ao ser tratadas regras especiais, como o empr´estimo de contas, a cobertura de uma c´elula ou a batota? Os jogos Mancala oferecem tamb´em oportunidades para a investiga¸c˜ao interdisciplinar. Na nossa investiga¸c˜ao sobre o Dakon, mostr´amos que o computador pode ser utilizado para apoiar a investiga¸c˜ao cognitiva-psicol´ogica. Retschitzki e N’Guessan recorreram a um programa inform´atico inteligente para investigarem os processos de aprendizagem dos jogadores. O programa foi apenas utilizado como parceiro fixo. Em Donkers et al., 2001, ´e proposto um algoritmo que recorre a conhecimentos sobre o advers´ario. Este algoritmo pode, em princ´ıpio, ser tamb´em utilizado para determinar a estrat´egia que um jogador (humano) est´ a a utilizar contra um computador. Poder´ a, pois, ser utilizado numa investiga¸c˜ao desenvolvimentista-psicol´ ogica sobre a aprendizagem de jogos Mancala por crian¸cas. Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
Jeroen Donkers, Jos Uiterwijk & Alex de Voogt
85
Referˆ encias [1] Bell, A. G. (1968). “Kalah on Atlas”. Em D. Mitchie (Ed.), Machine Intelligence 3 ( pp.181–193). Edimburgo: University Press. [2] Broline, D. M., & Loeb, D. E. (1995). “The combinatorics of mancala-type games: ayo, tchoukaillon, and 1/pi, (www).”Dispon´ıvel em: http://www.labri.ubordeaux.fr/Equipe/CombAlgo/membre/loeb/awari/. [3] Campbell, P. J., & Chavey, D. P. (1995). “Tchuka ruma solitaire”. UMAP Journal 16(4), 343–365. [4] Deledicq, A., & Popova, A. (1977). Wari et solo. Le jeu de calcul africain. Paris: Cedic. [5] Donkers, H. H. L. M., Voogt, A. J. de, & Uiterwijk, J. W. H. M. (2000). “Human versus machine problem-solving: winning openings in Dakon.”Board Game Studies, 3, 79–88. [6] Donkers, H. H. L. M., Uiterwijk, J. W. H. M., & Herik, H. J. v. d. (2001). “Probabilistic Opponent-Model Search.”To appear in Information Sciences Journal. [7] Irving, G., Donkers, H. H. L. M., & Uiterwijk, J. W. H. M. (2000). “Solving Kalal.”ICGA Journal, 23(3), 139–146. [8] Lincke, T. R., & Marzetta, A. (2000). “Large endgame databases with limited memory space.”ICGA Journal, 23(3), 131–138. [9] Meulen, M. v. d., Allis. L. V., & Herik, H. J. v. d. (1990). “Lithidion, an Awari-playing Program.”(Technical Report CS 90-05). Maastricht: Universiteit Maastricht. [10] Murray, H. J. R. (1952). A history of board games other than chess. Oxford: Oxford University Press. [11] N’Guessan Assand´e, G. (1992). M´ecanismes d’apprentissage de l’aw´el´e. Friburgo: Editions universitaires. [12] Retschitzki, J. (1990). L’Harmattan.
Strat´egies des joueurs d’aw´el´e. Paris:
[13] Russ, L. (2000). The complete mancala games book. Nova Iorque: Marlowe & Co. Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
86
Jogos Mancala
[14] Russel. R. (1964). “Kalah — the game and the program.”(Artificial Intelligence Project Memo no 22). Stanford: Universidade de Stanford. [15] Slagle, J. R., & Dixon, J. K. (1969). “Experiments with some programs that search game trees.”Journal of the Association for Computing Machinery, 16(2), 189-207. [16] Slagle, J. R., & Dixon, J. K. (1970). “Experiments with the M & N searching program.”Communications of the ACM, 13(3), 147–159. [17] Voogt, A. J. d. (1995). Limits of the mind: Towards a characterisation of Bao mastership. Tese de doutoramento n˜ ao publicada, Universidade de Leiden, Instituto de Investiga¸c˜ao CNWS, Leiden.
Jeroen Donkers & Jos Uiterwijk P.O. Box 616 6200 MD Maastricht The Netherlands {donkers,uiterwijk}@cs.unimaas.nl
AJ de Voogt Okeghemstraat 10-2 1075 PM Amsterdam The Netherlands
[email protected]
Boletim da SPM, n´ umero especial Jogos Matem´ aticos, pp. 69–86
