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