Re: sokoban

["Paulo Santa Rita" <p_ssr@xxxxxxxxxxx>]

Ola Pessoal,

Para efeitos de contraditorio e para que o colega Niski, que propos a 
questao, nao se sinta desistimulado em sua louvavel pretensao de formalizar 
o jogo de sokoban, e importante que se registre que o interesse em encontrar 
um algoritmo para o jogo nao esta, a principio, preocupado com aspectos 
operacionais ...

Para a Tecnologia e a para a Pratica as questoes de tempo, eficiencia e 
eficacia sao fundamentais e irremediaveis, isto e, em qualquer projeto e 
fundamental provar que ele, alem de bom e correto, seja tambem viavel nas 
dimensoes do tempo ( vamos gastar um tempo "bem finito" para realiza-lo ? ) 
e das financas ( Ha dinheiro suficiente pra realiza-lo ? )

Nao me parece que estes aspectos operacionais sejam relevantes  em um estudo 
teorico. Sao, sim, nesta dimensao pura e teorica, aspectos de somenos 
importancia ... Hoje nos sabemos, pela teoria Teoria da Relatividade Geral, 
que podemos causar efeitos temporais sensacionais, tais como aqueles 
expressos no paradoxo do gemeos. Nao ha ainda tecnologia para implementa-los 
: significa que devemos abandonar tais estudos simplesmente porque eles sao 
, atualmente, operacionalmente irrealizaveis ? Evidentemente que nao ! E o 
imaginario dos homens que cria a praxis do futuro, assim dizia Gaston 
Bachelar !

Se o algoritmo do jogo sokoban que viermos a achar seja de natureza 
exponencial ( cresce muito rapido ) ou polinomial ( cresce mais lentamente ) 
e irrelevante, na dimensao de discussao teorica em que nos encontramos. E 
inclusive irrelevante se vamos ou nao achar um algoritmo ... O investimento 
da inteligencia em investigar e por si so compensador e louvavel, 
independente dos resultados praticos que dai promanem !

Por outro lado, e evidentemente falso e TALVEZ uma demonstracao de pura 
prepotencia avaliarmos que qualquer outra(s) mente(s) diferente da nossa nao 
possa encontrar algo melhor do que aquilo que conseguimos fazer e que ja 
conhecemos : Se aquilo que eu conheco e consigo fazer e so forca bruta DEVO 
CONCLUIR que MUITO PROVAVELMENTE alguma outra inteligencia podera e devera 
encontrar algo melhor que isso ... Nao o contrario : Pois e isso que a 
historia da ciencia vem demonstrando acontecer ao longo dos seculos !

Considere o seguinte problema :

Existe um algoritmo que recebe uma equacao diofantina generica e devolve 
sim, caso ela tenha uma solucao no anel dos inteiros, ou nao, no caso 
contrario ?

Um Matematico Russo provou que nao existe um tal algoritmo. Significa, 
portanto, que jamais existira um programa de computador que implemente este 
algoritmo, em tempo polinomial ou nao, qualquer que seja a linguagem.

Nao devemos, portanto, nunca mais estudar  quaisquer equacoes diofantinas 
... Ah, eu ia esquecendo ... Nem toda  Matematica  cabe no copinho da teoria 
de computacao ...

Um abraco
Paulo Santa Rita
5,1337,19072001
















>From: Fábio Dias Moreira <fabiodias@ieg.com.br>
>Reply-To: obm-l@mat.puc-rio.br
>To: obm-l@mat.puc-rio.br
>Subject: Re: sokoban
>Date: Thu, 19 Jul 2001 01:38:23 -0300
>
>-----BEGIN PGP SIGNED MESSAGE-----
>Hash: SHA1
>
>Em Qua 18 Jul 2001 09:40, Paulo Santa Rita escreveu:
> > [snip]
> >
> > DIAGRAMA DE UMA ESTRATEGIA
> >
> > Uma estrategia pode ser descrita assim ( vou imaginar duas caixas e um
> > motor )
> >
> > [snip]
> >
> > Evidentemente que o problema ainda esta longe de ser resolvido, mas ja
> > temos alguns instrumentos matematicos que podem descreve-los. Nao sei se
> > sao os melhores, mas e um comeco. E entao, eu dei o passe : voce agora 
>faz
> > o gol ?
>
>Vou adicionar aqui que, provavelmente, qualquer algoritmo que resolve um 
>jogo
>de Sokoban não deve ser muito melhor que força bruta. O site [URL:
>http://web.cs.ualberta.ca/~joe/Preprints/Sokoban/paper.html] prova que é
>possível simular uma máquina de Turing com o jogo de Sokoban. Em 
>particular,
>é possível implementar um problema NP-completo.
>
>Como os problemas NP-completos levam tempo exponencial (pelo menos com os
>melhores algoritmos conhecidos), resolver um jogo de Sokoban também deve
>levar tempo exponencial (a não ser que vcs encontrem um algoritmo esperto o
>bastante, o que implica num algoritmo melhor para resolver problemas
>NP-completos). Em particular, se vcs encontrarem um algoritmo que rode em
>tempo polinomial, vcs podem se considerar donos de um milhão de dólares :)
>[URL: http://www.claymath.org/prizeproblems/statement.htm] [URL:
>http://www.claymath.org/prizeproblems/pvsnp.htm].
>
>[]s,
>
>- -----------------------------------------------------------------
>          Fabio Dias (fabiodias@ieg.com.br, ICQ# 31136103)
>           RPG em Revista: A sua revista virtual de RPG!
>            ====> http://www.rpgemrevista.f2s.com/ <====
>-----BEGIN PGP SIGNATURE-----
>Version: GnuPG v1.0.6 (GNU/Linux)
>Comment: For info see http://www.gnupg.org
>
>iD8DBQE7VmRJW7XDIUgHE2YRAgsMAKCVdHh7zL6x3Sim9BDe3NfSoM77wgCdGrpq
>3B/ekH7e1ltTA05a7Ma66nA=
>=Yz4k
>-----END PGP SIGNATURE-----


_________________________________________________________________
Seja avisado de novas mensagens do Hotmail e use o comunique-se com seus 
amigos com o MSN Messenger em http://messenger.msn.com.br