inteligencia artificial e C

Koncaman

Utilizador Saloio
Boas.
Recebi uma proposta de trabalho final de uma cadeira que consiste em desenvolver um programa jogador de sokoban... aquele joguito do jovem que arruma caixotes...
o programa analisa os níveis, e dá (ou tenta dar) a melhor solução possível (i. e. a que precisa de menos movimentos)
Inicialmente vou-me preocupar em por o programa a apresentar soluções para níveis só com um caixote, mas pretendo por isto a trabalhar em níveis de vários caixotes.

Eu quando me disseram o que era para fazer, eu pensei, ahh e tal mas isso nem é preciso grande trabalho, uns for's while's e if's e arrumo o assunto, mas depois de pensar um bocadinho melhor na coisa, é que me dei conta da verdadeira complexidade do problema. Isto não vai ser fácil, mas o meu maior problema é como abordar o problema. no fim de contas isto é um problema de inteligência artificial, relativamente complicado, que para mim é uma novidade (enquanto programador).

Estou a pensar em criar uma estrutura de dados, onde o programa vai guardando o nível alterado (a cada passo efectuado) sendo que em todos os ciclos o programa tem um nível novo (baseado no nível anterior mas com um movimento) e aplicar-lhe sempre o mesmo critério de movimentação.
não sei se me faço entender... mas ate ao momento esta parece-me uma solução razoável, mas pesada. e é suposto o programa ser leve.

os níveis são recebidos num formato deste tipo:

#####
#__._#
#____#####
#_______$_#
#_@##____#
#########

onde:
# é uma parede/coluna
@ é a posição inicial do arrumador
$ é a posição inicial do caixote
. é a posição onde se pretende que fique o caixote
_ é um espaço normal

Gostava que me dessem uma dica qualquer por onde pegar nisto, e se quiserem pensar mais um bocadinho, uma solução possível para a estrutura de dados, e para o algoritmo a implementar, assim muito por alto, é só para dar um empurrãozinho...

Obrigado.
 
Última edição:
Isso é claramente um problema de procura. Eu o semestre passado tive IA e que tive k implementar em lisp varios tipos de procura por arvore para um problema generico.
Axo k a primeira coisa a pensares é que tipo de procura pretendes utilizar. Existem uns algoritmos de procura que para escolherem o proximo no a ser explorado têm em consideração o custo e a estimativa de custo, no teu caso por exemplo podia ser o custo os movimentos ja feitos e a estimativa a distancia directa k falta (obvio k pode levar a erros), sao as estrategias informadas, ha por exemplo o A* ou o SMA (+ complicado). A tua procura na arvore ha de acabar quando chegares ao estado final, qd o bloco chegar ao destino.
Espero que seja isto k querias e que tenha ajudado.
Boa sorte
 
O DnlCY tem razão, depois de ler melhor é que vi que na tua descrição não havia referência a outro jogador que seria o caso em que se aplicava o que referi :o
 
pois, isto é um programa que joga sozinho... sokoban é so para um jogador.
DnlCY para isto ser um problema de procura, tenho que ter dados a serem procurados, ou seja preciso de fazer uma espécie de descodificação do nível, para um grafo, ou para uma matriz de estruturas... enfim, uma estrutura de dados, e convêm que o algoritmo a aplicar a essa estrutura seja eficiente. porque a descodificação do nível não será, computacionalmente, leve. no fundo ou tenho uma estrutura de dados pesada, mas que me permita utilizar um algoritmo rápido, ou tenho uma estrutura de dados leve, onde uso um algoritmo pesado, ou encontro um meio termo.
eu não sei, mas é que eu acho que C não é a linguagem mais versátil para problemas deste tipo.

Obrigado pela ideia. ;)
 
Fiz um projecto semelhante, mas era uma caça ao tesouro, utilizei o Alpha-Beta. Dá algum trabalho... mas no fim é gratificante, força nisso. :)
 
Koncaman,

Parece-me que não precisas de ter muito trabalho para esse projecto já que me parece algo que já foi feito antes, pelo menos noutras áreas:

Procura simples (+ de 15 milhões de matchs)
http://www.google.pt/search?hl=pt-PT&q=search+algorithms&btnG=Pesquisa+Google&meta=

Artigo geral sobre o tema com links
http://en.wikipedia.org/wiki/Search_algorithm

Breves descrições de alguns algoritmos possíveis
http://www.cis.temple.edu/~ingargio/cis587/readings/more-search.html
http://www.cosc.brocku.ca/~cspress/HelloWorld/1999/02-feb/search_algorithms.html

E no teu caso mais particular :D
http://www.google.pt/search?hl=pt-PT&q=sokoban+search+algorithms&btnG=Pesquisar&meta=

The Sokoban Domain

Sokoban is a fairly difficult domain for single state space search. Solutions are only obtained if elaborated schemes such as state space compression, tunnel and goal macros and a minimum matching heuristic. Further refinements such as heuristic pattern databases and relevent cuts lead to several solutions to Sokoban benchmark instances in the so-called pushes-variant. Optimal solutions to the minimization of the number of moves with single state space search schemes are not published.

On the other hand, symbolic search leads to promising results in Sokoban. We present the class BddSoko based on OnePlayerGame that solves the first benchmark problem in the optimal number of 230 moves.

Advance to the search, initialisation of the puzzle has already been done: The input is read from the problem file (thereby the array table and interior are defind).
Parece-me que será mais complicado do que pensava... por isso é que é um TFC :D

P.S. Sokoban Homepage, tem uma série de papers sobre o assunto. Assim escusas de estar a inventar a roda :)
 
Koncaman. A base de um problema de procura é teres um estado inicial, estado final, e varios estados intermedios. dps tens acções que aplicas sobre cada estado para passar para outro. Tu podes ver cada estado cm um tabuleiro numa dada posicao e as acções com o movimento do boneco (cima, baixo,etc), e o estado inicial é o tabuleiro quando começas o jogo, e o estado final é quando as tuas caixas se encontram nas posicoes pretendidas. portanto so vejo aki um problema de procura. E axo k so vais precisar de guardar em cada estado uma representacao do tabuleiro e possivelmente mais o numero de movimentos efectuados, pois é isto k se pretende minimizar.

Obvio k cm o exercicio nao é meu, e portanto eu tb nao tou a perder mt tempo a pensar cm se deve fazer o trabalhar e acredito que me possa estar a fugir algo mais complicado do que estou a ver. Ate pk o sadino espeta aki com uma data de info e portanto o problema deve ser mt mais complicado...mais so desejar boa sorte:)
 
estive hoje a fazer um fluxograma do programa e ja sei mais ou menos como fazer a coisa, parecendo que não, um fluxograma é um exercicio muito bom para este tipo de problema.
efectivamente o problema baseia-se praticamente todo em procura.
vou usar um grafo. o programa descodifica o nivel para um grafo, e aplicalhe um algoritmo de procura, com bastantes condições, para procurar o melhor caminho.
agora, ainda me falta penssar na melhor maneira de fazer o upgrade para varios caixotes...

obrigado pelas dicas. e se tiverem algo mais a dizer sobre IA... força, que isto depois é para ir a campeonato. quem tiver o melhor algoritmo/estrutura de dados (i.e. o programa que ocupe menos recursos e resolva um problema em menos movimentos), leva bonificações :)
 
Back
Topo