Desafio matador!

Há tempos tive uma dúvida complicada sobre alpha e o pessoal do fórum conseguiu solucionar. Também tive uma dúvida sobre conversão de número hexadecimal de forma eficiente, conseguiram me ajudar! Agora lanço um desafio diferente e fico agradecido desde já à quem conseguir solucionar.

Um amigo que tenho, estuda em outra faculdade que eu. Meu curso é de Tecnologia da Informação, o dele de Ciência da Computação. Há uns dias, a turma dele resolver fazer uma pequena feira mostrando o trabalho de alunos da faculdade e projectos paralelos e ele me convidou para solucionarmos um problema sugerido pelo professor dele.

O problema é complicado, mas conseguimos solucionar de uma forma diferente (e menos eficiente) da que queríamos. Segue o problema:

Alguém provavelmente já jogou aqueles brinquedos "racha-cuca", onde há 16 números dispostos em grade, onde você movimenta um número para um espaço vazio e libera o movimento para outros números para que no final consiga ordená-los corretamente.



Fizemos o jogo, é super simples criar, mas o que nós queremos é justamente a parte difícil: fazer o computador jogar sozinho, realizando o mínimo de movimentos necessários para se chegar à ordem correta das peças. O método que usamos foi de tentativa de todas as jogadas possíveis até que se chegue à solução e discriminar aquela que usar menos movimentos.

Para isso julgamos cada jogada como uma possibilidade que geram outras 1, 2 ou 3 novas possibilidades de movimento. Usamos uma grade de vetor (vocês devem conhecer isso como a ds_grid no Game Maker) para indexar as jogadas e as possibilidades, enraizando como uma "árvore", e ao final de cada número máximo de movimentos (no nosso caso é de 81) ele retornaria e tentaria outro caminho.

O resultado é demorado, porém exacto. Mas o que nós queremos é uma forma mais rápida de se conseguir essa mesma solução, pois nosso algoritmo demora entre 3 e 5 minutos dependendo da disposição das peças.

Enfim, é um desafio que eu considero difícil, há dias venho tentando pensar em uma forma diferente, já descartei a possibilidade de haver alguma fórmula matemática para isso, não acredito que haja. Bom, alguma ideia???

Isso é bem difícil, uma IA desse nível e que seja eficiente deve ser muito complicado de criar.
Eu nem saberia por onde começar...
Vocês estão usando C++ ou outra linguagem?
Pelo o que você disse a maneira que você fez o seu sistema funciona bem, mas o que falta é velocidade né.....
Isso é um grande desafio, mas desafios foram feitos para serem superados.
Não desista, e boa sorte!

Grotle escreveu:Isso é bem difícil, uma IA desse nível e que seja eficiente deve ser muito complicado de criar.
Eu nem saberia por onde começar...
Vocês estão usando C++ ou outra linguagem?
Pelo o que você disse a maneira que você fez o seu sistema funciona bem, mas o que falta é velocidade né.....
Isso é um grande desafio, mas desafios foram feitos para serem superados.
Não desista, e boa sorte!

Estamos usando C++. Por algum motivo a faculdade dele adotou o Dev C++, mas nesse projecto estamos usando o Borland C++ Builder pois gostamos mais dele. O programa é puramente em modo texto, assumimos fazê-lo da forma mais simples possível por questão de velocidade.

Sabemos que a questão da demora não está só na análise exagerada de passos, mas dentro de um loop como esse, qualquer "if" pode significar perda ou ganho de tempo. Por isso estamos buscando uma outra forma de fazê-lo, pois dentro do que fizemos, acredito que esteja bem otimizado.

Mas obrigado pelo incentivo, vamos continuar sim!

Oy
Eu to fazendo de sistemas de informação, e
gostaria de saber se vc pode me arrumar o código
que vc montou,
achei bem interessante,
se puder agradeço.

brigada!
Erica

Caro amigo Ninja Gaiden(), num ambiente programacional, para tudo HÁ UMA FÓRMULA MATEMÁTICA. Quando acrescentamos tal valor a X, estamos realizando uma fórmula matemática, a fórmula da adição. Sendo assim, deve haver alguma fórmula, neste momento implícita, que realize o que está necessitando. Se nós fizéssemos isso no Game Maker, não teria um mínimo de graça, é como tirar doce de criança.

Código:

if turno_da_maquina = true{
if place_free(x,y-1){
y-=[tamanho do quadrado];
}
else if place_free(x,y+1){
y+=[tamanho do quadrado];
}
else if place_free(x-1,y){
x-=[tamanho do quadrado];
}
else if place_free(x+1.y){
x+=[tamanho do quadrado];
}
turno_da_maquina = false;
turno_do_player = true;
}

... Tudo o que eu faço segue uma lógica, e esta seria ela, levando em consideração o tamanho da sprite do bloco, iria mover. Isso se colocaria no Step do objeto de bloco, e assim que UM DELES tivesse espaço livre, moveria na direção do espaço e terminaria o turno. Não sei se isso valeria também para o seu projeto de C++, mas tente reproduzir isso, pode ser que dê certo. C++ é realmente osso, não há nenhuma interface gráfica, apenas linhas e linhas, o que leva a você a se tornar um programador melhor. Qual a graça de programar sem quebrar a cabeça com códigos? Nenhuma. Portanto, mesmo que seja iniciante, tente aprender a linguagem de código do ambiente em que você está trabalhando.

Esse processo acima é rápido, pois você não tem que armazenar x valores numa grade de vetor, e o computador checar todos esses valores. Dependendo do tamanho da grade, pode demorar mais, ou menos. Nesse processo, consideraríamos nossa sprite de origem 0 em ambas as coordenadas. No C++ teriámos que checar a largura e altura do canvas antes de realizar o movimento, pois não estamos trabalhando com o Game Maker, certo? Olha, se o que eu disse não der certo, deixe pra lá, só estava tentando ajudar. Abraços e boa sorte com o vosso projeto!

@Markituh
Acho que o caso aqui não é mover as peças e sim fazer o computador encontrar Quais, Quando e Para Onde mover as peças. Fazer ele "pensar".

-
Sabe qual o jeito mais rápido, porém mais insano? Dar ao computador todas as respostas para todas as combinações, depois é só um jogo de achar os pares =P. Mas é claro que isso é inviável e não poderíamos dizer que é uma IA! hehe

Falando sério agora, creio que não exista uma formula, o único jeito deve ser na tentativa e erro. Pode demorar um pouco, nem NÓS conseguimos achar a resposta em menos de alguns minutos. Acho que o que da para fazer é tentar melhorar o código, deixá-lo mais rápido.

Você falou que o computador tenta fazer até 81 movimentos, se chegar nisso e ele não conseguiu uma resposta ele tenta outra combinação, correto? Esse 81 veio de onde? É o minimo de movimentos para o jogo mais "comprido"?
Já tentou diminuir esse limite? O que pode acontecer é:
Ele não achar uma solução OU Achar uma solução ainda mais rápido porque não vai perder tempo procurando um caminho de 81 todas as vezes.

Se ele não achar nenhum você poderia correr o teste outra vez mas com o limite maior. Mas infelizmente se ele não encontrasse na primeira vez, até terminar essa segunda poderia demorar um pouco mais.....

Não intendeu o que eu quis dizer? Veja o exemplo:
Digamos que o resultado seria encontrado na QUINTA tentativa, no movimento de número 38.

O computador passaria antes por: 81*4 = 324 movimentos.
Se esse limite fosse menor, por exemplo 60 poderia ser muito diferente:
60*4 = 240. Ele não perderia tempo nos 84 movimentos inúteis que faria do outro jeito.

Porem e se a resposta fosse encontrada no movimento 61? Ai ele não encontraria resposta e seria necessário correr o teste mais uma vez, com um limite maior, talvez 81. A resposta seria encontrada mas seriam:
5*60 + 81*4 = 624 "+ os 61" movimentos.

O que você pode fazer é fazer vários testes e ver a média de movimentos necessários em cada um e deixar esse limite nele. Se não encontrar a resposta aumentar o limite.
Outra coisa seria não perder os testes anteriores, de forma que só seja necessário fazer os testes "complementares".
(Isso é, se vocês já não fizeram isso! hehe)

Otimizar o código pode ser a melhor saída... Se você mostrar o código poderíamos ver se encontramos algo para melhorar, sempre tem alguma coisa!

EDIT:
Uma outra solução possível é fazer o computador executar mais de um teste ao mesmo tempo usando os vários núcleos do processador...

pra alguem saber fazer esse programa
teria q saber as tecnicas para fazer o puzzle,
saber como mecher cada pessa pra determinado
lugar com o minimo de movimentos possiveis

no cubo magico o segredo eh fazer todos os
lados ao msm tempo completando o topo de 4
lados e dps faz o resto + - e se vc for procurar
no youtube como fazer tem ateh os nomes dos
movimentos e nele msm o kra do video mostra
sequencia desses movimentos para fazer uma
cor ir pra um lugar(exemplo de video)

ou seja se vc quiser montar esse negocio vc
teria q colocar umas sequencias de movimento
basicas q realizasem movimentos nos quadradinhos
q aos poucos iriam se transformar no normal

tenho a menor ideia de como fazer, afinal n sei
nem as tecnicas pra montar esse puzzle, espero ter
ajudado em alguma coisa

Bem, pela resposta do Janx
ele ja matou (literalmente kkkK) a pergunta né? Se diminuir o numero de tentivas feitas pela CPU ela fará mais rápido o processo... Espero ter tentado explicar o que o Janx falou

erica.tubini escreveu:Oy
Eu to fazendo de sistemas de informação, e
gostaria de saber se vc pode me arrumar o código
que vc montou,
achei bem interessante,
se puder agradeço.

brigada!
Erica

Olá Érica, tudo bom? Sistemas de informação? Legal!!

Bom, passo pra você sim, mas se você não se importar, pode ser depois que nós o entregarmos? Vai ser dia 29 de maio, até lá, nós não vamos colocá-lo na net (por questão de segurança, entende?). Se alguém copiar nosso trabalho e provar que está na internet, nós podemos perder a nossa nota.

Markituh escreveu:Caro amigo Ninja Gaiden(Happy), num ambiente programacional, para tudo HÁ UMA FÓRMULA MATEMÁTICA. Quando acrescentamos tal valor a X, estamos realizando uma fórmula matemática, a fórmula da adição. Sendo assim, deve haver alguma fórmula, neste momento implícita, que realize o que está necessitando. Se nós fizéssemos isso no Game Maker, não teria um mínimo de graça, é como tirar doce de criança.

Claro meu amigo Markituh! Isso é de fato, fundamental. A matemática é uma ciência exata.

Bom, mas nesse caso especificamente, nós estamos trabalhando além do cálculo matemático... Perceba que a cada jogada só é possível mover uma única peça, o que influencia no movimento das demais, pos a cada peça disposta em um lugar "certo", as que estão no lugar "errado" têm uma posição a menos para se mover, entende?

Se você enxergar por esse lado, as possibilidades são infinitas. O que nós fizemos é limitar essas tentantivas até que se chegue ao caminho certo de movimentos. Usando um método de jogadas "ramificadas" (não encontrei termo melhor), por exemplo, uma jogada gera outras três ou quatro... onde a matriz principal de movimento é de 100 passos isso gera um resultado realmente absurdo. Tanto é que não há variáveis pra calcular isso e sim uma "calculadora feita com arrays (calcula números com até 1024000000 de extensão!).

O janx explicou aí, é isso mesmo. Mesmo assim, valeu pela força!

Janx escreveu:Sabe qual o jeito mais rápido, porém mais insano? Dar ao computador todas as respostas para todas as combinações, depois é só um jogo de achar os pares =P. Mas é claro que isso é inviável e não poderíamos dizer que é uma IA! hehe

Bom, é mais ou menos por aí mesmo. Ele de fato tenta todas as combinações dentro de um limite (que eu comentei). Porque se darmos a ele a possibilidade de repetir o movimento de uma peça, as possibilidades serão infinitas.

Janx escreveu:Você falou que o computador tenta fazer até 81 movimentos, se chegar nisso e ele não conseguiu uma resposta ele tenta outra combinação, correto? Esse 81 veio de onde? É o minimo de movimentos para o jogo mais "comprido"?

Bom, esse número é o limite imposto pelo professor. Tentamos de tudo, quebramos a cabeça e pensávamos que a resposta (ou alguma dica) estivesse nesse número. Mas não encontramos nada. Acho difícil haver algo em especial.

No caso da ideia da otimização eu entendi. Nesse caso, o nosso intuito é encontrar o menor número de jogadas pra se chegar ao resultado final, por isso é que mesmo que ele encontre a resposta na jogada 38 ele ainda teria que processar as outras possibilidades, para tentar encotrar a menor entre elas. Entende? Mas obrigado pela dica, nós estamos quebrando
a cabeça pra otimizá-lo ainda mais, quando estiver pronto vou colocá-lo aqui pra vocês verem!

Godsil4 escreveu:ou seja se vc quiser montar esse negocio vc
teria q colocar umas sequencias de movimento
basicas q realizasem movimentos nos quadradinhos
q aos poucos iriam se transformar no normal

É uma ideia que tivemos também. Pensamos em uns movimentos básicos pra uma peça em um lugar x chegar até o lugar y, mas é complicado porque o movimento pode atrapalhar outras peças. Se eu assumir que a peça 15 tem que chegar ao lugar dela mudando de lugar a 13 e a 14 que já estão no lugar certo, isso faria o programa mexer a 15 e retornar na 13, acho que ficaria complicado e os resultados meio "incertos".

Bom, mas vou pensar nisso com mais calma. Valeu!

Obrigado a todos pelas dicas!