1. Este site usa cookies. Ao continuar a usar este site está a concordar com o nosso uso de cookies. Saber Mais.

inteligencia artificial e C

Discussão em 'Programação' iniciada por Koncaman, 20 de Maio de 2005. (Respostas: 8; Visualizações: 1832)

  1. Koncaman

    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: 20 de Maio de 2005
  2. Sadino

    Sadino I'm cool cuz I Fold

  3. DnlCY

    DnlCY Power Member

    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
     
  4. Sadino

    Sadino I'm cool cuz I Fold

    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
     
  5. Koncaman

    Koncaman Utilizador Saloio

    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. ;)
     
  6. greven

    greven Folding Artist

    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. :)
     
  7. Sadino

    Sadino I'm cool cuz I Fold

    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=

    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 :)
     
  8. DnlCY

    DnlCY Power Member

    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:)
     
  9. Koncaman

    Koncaman Utilizador Saloio

    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 :)
     

Partilhar esta Página