Evolução

É com imenso prazer que anuncio uma versão funcional (não completa) do jogo do galo.
MenteGalo (BETA)

Esta versão inicial serve o propósito de "DEMO". Neste ponto estou a recrutar "beta testers", e se aceitarem o desafio enviem comentários para esta publicação com bugs encontrados ou sugestões.

Os progressos têm sido lentos dado que ando na época de frequências académicas e tenho um projecto "TOP SECRET" que estou a concluir. Mas quero ver se tenho o modo "impossível" a funcionar até o final de 2007. Uma vez concluído este modo vou passar à fase de "cosmética", entretanto ficam com uma versão visualmente pobre do jogo.

A implementação.
O modo "Dois Jogadores" foi o primeiro a ser implementado, ficou pronto à cerca de um mês atrás. O motor é relativamente simples, programei uma callback para o evento de click nos movieclips das casas, cada jogada implica que uma variável alterne entre o jogador 1 e 2, verifica em seguida se algum dos jogadores ganhou ou se empataram.
A matriz:
Uma matriz 3*3 controla o quadro do jogo, as comparações são feitas por intermédio de multiplicações. Esta operação é útil no sentido em que posso utilizar as propriedades do elemento neutro e absorvente para determinar o resultado de uma linha ou coluna do quadro.
A matriz assume exclusivamente os seguintes valores:
1 - Jogador 1 marcou uma "bola" no elemento.
2 - Jogador 2 marcou uma "cruz" no elemento.
0 - Não foi efectuada nenhuma jogada no elemento
ex:

A situação exemplificada na imagem resulta na matriz [{2,2,1},{1,0,2},{0,0,0}]
aplicando uma multiplicação á primeira linha: matriz[0][0] * matriz[0][1] * matriz[0][2] retorna o valor 4, que é insignificante, os resultados que interessam é 1 e 8, dado que determinam que jogador ganhou.
Uma vez esgotadas todas as possibilidades do jogo (Empate por preenchimento de todas as casas possíveis do jogo ou vitória de um dos jogadores), são actualizados os valores da pontuação de cada um dos jogadores, e o jogo é reiniciado.

Estes conceitos são aplicados nos restantes modos, e cada folha da árvore de soluções (jogador vs CPU) tem uma destas matrizes na sua estrutura.

Modo Jogador VS CPU
- Simples
Não é computada nenhuma solução para este nível, o programa limita-se a fazer jogadas aleatórias, até que o jogo termine. O algoritmo está programado para que as jogadas incidam sobre posições vazias(0) da matriz do jogo.

- Médio
Neste nível o programa recorre a uma árvore que se estende à profundidade de dois níveis/jogadas, procura a jogada mais sensata (Perde, Ganha e Aleatória)
- Ganha: O pc calculou que nesta jogada ele ganha.
- Perde: O pc calculou que na próxima jogada (humano) ele perde
- Aleatória: O pc não encontrou situações acima mencionadas e por isso joga ao acaso


- Impossível
Está em fase de desenvolvimento, a abordagem em que estava a trabalhar não vai de encontro ao algoritmo MinMax e vou ter de voltar a analisar e proceder a alterações. Tenho de optimizar o processo de cálculo e avaliação de pesos, nesta abordagem o programa entra num ciclo de computação de 9 níveis que demora cerca de 7 segundos, um programa que recorre a este tipo de algoritmo para calcular as soluções demora em média 1 segundo.

Modo Online:
Quero implementar a possibilidade de jogar online com outros jogadores por intermédio da tecnologia XMLsocket, mas só vou trabalhar nessa funcionalidade depois de Janeiro de 2008.

Agradecia que contribuíssem com comentários sobre o jogo.
Abraço e bom natal, caso leiam isto amanha (25 Dezembro)

Hanoi, padrões e mais padrões...

Para solucionar qualquer problema independentemente da sua escala, o primeiro passo é sem duvida entender a sua génese. Identificar e analisar cada mutação, e se possível definir uma formula cujo resultado será um estado verificado no respectivo estágio do problema.
As torres de Hanoi (clique aqui para ver a definição na wikipedia sobre as torres de Hanoi)é um problema típico em que a solução varia em função dos seus argumentos (discos), mas essa mesma solução obedece a um padrão. A existência de padrões normalmente implica uma fórmula matemática computável.

Dissecação do problema

Para começar, é necessário ter uma noção visual do problema e de que forma ele “cresce” em função dos discos

imagem 1


Analisando a imagem 1 podemos concluir que o numero de iterações (coluna i) para a solução de um determinado numero de discos é de ordem exponencial:
Discos - 1: 1 passo
Discos - 2: 3 passos
Discos - 3: 7 passos
Discos - 4: 15 passos
Discos - 5: 31 passos
A solução neste caso é (2^n + 1). Na abordagem iterativa, esta formula é vital, pq permite-nos estabelecer a condição de paragem para o ciclo.

Ciclos dentro de ciclos.
Outro fenómeno observável é a repetição de sequências de passos nas iterações

imagem 2

Identificamos a partir da imagem 2 outro padrão
Discos - 3: 2x(1,2,1)
Discos - 4: 4x(1,2,1), 2x(3,1,2,1)
Discos - 5: 8x(1,2,1), 4x(3,1,2,1), 2x(4,1,2,1,3,1,2,1)
é de notar que cada solução de (n discos) aparece repetida duas vezes na solução de ([n + 1] discos), e que a ocorrência de uma sequência de iterações numa solução aparece a dobrar na solução seguinte.

Já temos uma noção mental da solução das torres de hanoi para qualquer que seja o seu argumento. É no fundo uma repetição de soluções, em que cada sequência contem uma sub-sequência. Mas este conceito baseia-se numa abordagem recursiva. O próximo passo é identificar o processo iterativo, para isso vamos identificar a frequência com que os discos se movem numa solução

Imagem 3


Basicamente o corpo do nosso ciclo está visível nesta imagem. Temos então os seguintes factos:
- O disco 1 é sempre o primeiro disco a ser movido.
- O disco 1 move-se sempre num intervalo de 2 movimentos (1,x,1), e sp numa iteração ímpar.
- Se argumento do numero de discos for par o disco 1 move-se no primeiro passo para a haste B e move-se da esquerda para a direita, caso contrário move-se no primeiro passo para a haste C e move-se da direita para a esquerda.
- Nas iterações pares, move-se o menor disco livre para uma haste livre para ele e excluindo a haste de origem desse disco(lembre que o disco 1 não se move nas iterações pares).

Em suma, esta análise resulta no seguinte fluxograma que utilizei para a abordagem iterativa para as torres de hanoi(presente em "Hiperligações dos meus trabalhos -> Hanoi Soluçao" ).

Fluxograma

Hanoi V1

Serve o presente documento digital, para oficializar o lançamento do "Hanoi V 1.0" :P
Paralelamente ao desenvolvimento da solução das torres de hanoi, estive a desenvolver uma versão jogável deste mesmo problema.
Gráficamente está pobre, e se eventualmente ficar um disco a flutuar no meio do ecrã tenham paciência.
Vou tentar publicar ainda hoje uma explicação da minha abordagem.
Divirtam-se com o Hanoi v1.0 Feedback com comentários e criticas construtivas são bem vindos e quiçá lance a v2.0 :D

Clique em cima da imagem para abrir o jogo


Clique aqui para ir para o jogo

Hanoi anyone

Boas,
estou a publicar uma mensagem rápida, para disponibilizar o resultado de um estudo que fiz sobre o problema das torres de hanoi.



Clique aqui http://members.netmadeira.com/robertocamara/hanoi/hanoi1.html ou em cima da imagem para ver a simulação da solução mais eficiente das torres de hanoi.

Nota: A computação da solução é feita antes do início da animação, se o numero de discos for superior a 12 o script irá demorar a calcular a solução e poderá aparecer "warnings" do flash.

Regresso ao passado :)

Já estou á 20 horas acordado, são quatro da manha e entrei no meu quarto às 18 para resolver o algoritimo iterativo. Gastei perto de cinco folhas com fluxogramas, que resultavam sp em ciclos infinitos.
Finalmente, optei por fazer as coisas passo por passo(voltei à fase de criação de ramificações de nós). e registei esses passos como se estivesse numa maquina URM e EUREKA!!! a solução para este problema formou-se à minha frente com 6 estados !!! BRUTALISSIMO. Pronto, estou a sensacionalizar um bocado a solução, mas os passos vitais reduzem-se a 6 :D

Vou tentar mostrar muito sumariamente através de um cenário para um Array de 4 casas com uma jogada efectuada.

quadro[1,0,0,0], com um array B[x,3,2,1] com o numero de filhos de cada nó por nivel, e um array A[x,0,0,0] cópia do array A mas com todos elementos a 0.

os estágios totais resultantes deste cenário seriam:
1 - [1,0,0,0]----------------------A[1,0,0,0]
2 - [1,2,0,0]----------------------A[1,1,0,0]
3 - [1,2,1,0]----------------------A[1,1,1,0]
4 - [1,2,1,2]----------------------A[1,1,1,1]
5 - [1,2,2,0]----------------------A[1,1,2,0]
6 - [1,2,2,1]----------------------A[1,1,2,1]
7 - [1,0,2,0]----------------------A[1,2,0,0]
8 - [1,1,2,0]----------------------A[1,2,1,0]
9 - [1,1,2,2]----------------------A[1,2,1,1]
10 - [1,0,2,1]----------------------A[1,2,2,0]
11 - [1,2,2,1]----------------------A[1,2,2,1]
12 - [1,0,0,2]----------------------A[1,3,0,0]
13 - [1,1,0,2]----------------------A[1,3,1,0]
14 - [1,1,2,2]----------------------A[1,3,1,1]
15 - [1,0,1,2]----------------------A[1,3,2,0]
16 - [1,2,1,2]----------------------A[1,3,2,1]

Com as seguintes acções por iteração
1 -
2 - marca, avança
3 - marca, avança
4 - marca, avança
5 - Limpa, Recua, Marca, Avança
6 - marca, avança
7 - Limpa, Recua, Limpa, Recua, Marca, Avança
8 - marca, avança
9 - marca, avança
10- Limpa, Recua, Marca, Avança
11- marca, avança
12 -Limpa, Recua, Limpa, Recua, Marca, Avança
13 -marca, avança
14 -marca, avança
15 -Limpa, Recua, Marca, Avança
16 - marca, avança

Basicamente o que acontece, é que a árvore é construída na forma (Norte->Sul) - (Oeste - Este).


Com o seguinte esquema de estados / fluxograma



Fica assim registada a nova estratégia para o algoritmo recursivo. Infelizmente tenho de estudar amanha pq as frequencias estão aí à porta, não posso adiantar muito amanha :(

Abraço

Reajustes

Boas,
Estou a publicar um comentário rápido, pq já estou bêbedo com sono :P estive desde as 21.00 até à 1 a trabalhar na nova abordagem, começei com fluxogramas e simulações de pequenas estruturas de 3 unidades. Concluí que o cálculo para os estágios estava incorrecto. O novo valor é 2.154.258 estágios. Tenho uma teoria que o Flash tb era capaz de lidar com este nivel de recursividade. dado que é um programa que simula um programa (tem a sua maquina virtual, assumi um conceito semelhante ao do java virtual machine) e que será por isso mais flexivel para a call-stack. Apesar desta teoria, a minha nova abordagem já não contempla um algoritimo recursivo, mas sim iterativo.
A nova abordagem tb ajudou-me a planificar uma melhor estratégia para os vários niveis de dificuldade e controlar o numero de calculos para as jogadas possiveis com base em niveis limitadores.
Amanha à noite penso ter algo mais "cientifico" para publicar cá
Abraço

Stack Overflow

Há conceitos em programação, que somos advertidos várias vezes, mas que nunca ligamos muito a eles, o "Stack Overflow" é um deles. Percebi hoje, da pior forma ( diga-se de passagem ) que a programação recursiva têm algumas consequências.

O stack Flow ocorre qdo a call stack fica cheia, e a colocação das chamadas do programa começam a trasbordar para fora da stack! Ou algo assim no género.
Na abordagem que estava a fazer ao programa a minha call-stack teria de ter tamanho para alojar as 1.077.000 funções.
Trabalhei com abordagens recursivas para a mesma finalidade no flash e no gcc. Curiosamente o flash suporta 33.000 estágios e o gcc suportou 12.000

De qualquer maneira deixo neste link a minha abordagem em c++ (uso o bloodshed dev c++ v 4.9.9.2)

ficheiro

Atritos programação

Estou frustrado!!!
Tentei implementar o código que desenvolvi em actionscript para c++, o resultado foi desastroso. Estou muito destreinado em c++, e o pior é que tenho uma frequencia de c++ em duas semanas.
Ontem e hoje foi-me dificil dedicar tempo ao projecto porque passei o dia em aulas e formação :( estive 1.30 h no café a praguejar e fumar cigarros, enquanto lamentava não ter prestado mais atenção às aulas da cadeira. Mas, como tristezas não pagam dívidas vou tentar ainda hoje fazer progressos no c++, a ver se consigo obter pelo menos o numero de estágios que tinha calculado.
~1.077.130.
A abordagem matemática do problema é (9(8(7(6(5(4(3(2(1(1)+1)+1)+1)+1)+1)+1)+1)+1)+1)
isto dá as 1.077.130 possibilidades de preenchimento da grelha.
1 (grelha nula)
2 (grelha 1 casas, com 2 símbolos)
5 (grelha 2 casas, com 2 símbolos)
16 (grelha 3 casas, com 2 símbolos)
65 (grelha 4 casas, com 2 símbolos)
326 (grelha 5 casas, com 2 símbolos)
2.137 (grelha 6 casas, com 2 símbolos)
14.960 (grelha 7 casas, com 2 símbolos)
119.681 (grelha 8 casas, com 2 símbolos)
1.077.130 (grelha 9 casas, com 2 símbolos)

Isto parece-me um factorial com uma propriedade meia marada, o resultado tb mostra alguma relação com a sequencia fibonacci.

Se alguem tiver uma ideia de como simplificar o processo, ou tiver uma abordagem mais "bonita", agradecia que entrasse em contacto comigo.

Tb foi anunciado o projecto da cadeira de programação, ironicamente tb é um jogo, o "sokoban".

Abordagem Inicial

Arte, definitivamente, não é o meu forte.

O layout é a típica grelha sem as bordas exteriores, com bolas e cruzes para representar os símbolos típicos do jogo (bolas e cruzes), o background é branco!
Tenho uma versão funcional, para dois utilizadores a jogar no mesmo applet (Flash). é relativamente simples e implica que o jogador tenha um amigo ao lado, para que a experiência tenha interactividade.
Dado que nem toda gente tem amigos ( dispostos a jogar galo no mesmo momento que nós), decidi incluir no jogo a opção "Jogador VS CPU".
A complexidade de desenvolvimento do jogo aumentou exponencialmente com a decisão do parágrafo anterior.

Estive a pesquisar alguns conceitos, e optei pela a técnica Árvores MiniMax. Sumariamente esta técnica é aparentemente a estratégia Brute-Force dos algoritmos I.A
Na implementação do algoritmo em actionscript optei pela abordagem recursiva! Optei muito mal, pq após n tentativas verifiquei que o flash parava na instância ~14000 recursiva da função que gerava a arvore.
O que inicialmente parecia um erro semântico nas condições de paragem, viria a ser solucionado com uma perspectiva matemática à questão. Após 2 horas de cálculos verifiquei a possibilidade de 1077120 estágios de preenchimento da grelha. Desconfio que o flash consiga lidar com essa carga de operações.
Estratégia para solucionar a carga computacional:
Adaptar o código para c++, obter a arvore com todos os estágios, e proceder à eliminação dos estágios pós-victoria ou empate. Carregar a arvore no applet flash como objecto estático

Apresentação MenteGalo

Boas,

Decidi criar este blog para manter um registo histórico do desenvolvimento de um jogo para a www

Titulo do Projecto:
- MenteGalo ( limitação criativa)


Motivação:
Adquirir conhecimentos na área de I.A.
Criar num passatempo saudável e construtivo.

Data de início:
17-Novembro-2007