Boxy Boy

Archive of the old message board

Moderator: Chad

Locked
LordGaz

Boxy Boy

Post by LordGaz » Sun Sep 16, 2001 12:30 pm

Nice work Phil for finishing Boxy Boy and to Beejay for finishing it's clone. It took me a while just to solve the first world and some of those later levels look incredibly difficult too.
<p>

About doing it in the minimum number of steps, I wonder if it is possible to write a program to solve this game. I did this a long time ago for a similar game but it only worked for certain types of levels.

<p>

Cheers, GAZ

--
garyjlee@hotmail.com

phil

Post by phil » Sun Sep 16, 2001 12:30 pm

Thanks Gary ...
As maybe some of you knows, I'm VERY VERY found of this game ; I
discovered it more than an year ago, and my recent scores on
boxyboy/soukobdx are the fruit of a long study : my only aim is to
optimize steps scores (I've improved some of them recently) even if
Mame games have a stupid scoring ... the longest distance you walk,
the highest points you get :(((( ; that's why BeeJay have a better
final score with worst steps scores on soukobdx

<p>

To study the game , I used a program Skito sent me one year ago and I
have collected in it more than 2000 levels on the net !!! If someone
is interested, I can send it to him

<p>

Concerning a program solving sokoban levels, I did find one on the
web, but for levels with more than 3 boxes, it takes too long (more
than 24 hours is sometimes not enough with a P600, I didn't try more)
; and it didn't replace the high pleasure you get when you solve
yourself a level :))

<p>

But if someone has a better program I'm interested because I still
don't manage to solve several levels of my 2000+ collections ...

--
plamat@club-internet.fr

phil

Post by phil » Sun Sep 16, 2001 12:30 pm

Oh I forgot ...
If you want more sokoban levels and highscores (I have some there), go
to this adress :
http://database.spprod.se/Soko/sokoHighscore.lasso

--
plamat@club-internet.fr

Chad

Post by Chad » Mon Sep 17, 2001 12:30 pm

There is a good program (still isn't perfect for larger levels) that
will solve optimal pushes, for rooms that have about a 500 square
area. I think it's an NP complete problem so there probably isn't a
program that will solve all problems perfectly in a reasonable amout
of time. Optimizing pushes is probably a more practical application
since it's a lot easier to walk/move than it is to push an object
depending on how heavy the object is. It definitly finds different
solutions if you are concered about optimizing moves only, like
sokoban deluxe requires.

<p>

the link to this code and algorithm is

<p>

http://www.cs.ualberta.ca/~games/Sokoban/

<p>

I've been trying to convert the code to optimize moves only but i
couldn't get it to work. The real practical way to do this is to
have an objective function that optimises both moves and pushes
together since moving and pushing require some energy, pushing
requires a bit more than moving. If anyone finds a better code link
than this please post, this one is the best i could find.

--
churritz@cts.com

Abbe

Post by Abbe » Tue Sep 18, 2001 12:30 pm

I had a sokoban period a couple of months ago and looked around for a
good solver. I found this web pages with a java applet that is faster
than most programs I tested. Unfortunately it only handles small
problems.

<p>


Takaken's sokoban solver:
http://www.ic-net.or.jp/home/takaken/so/soko/index.html

<p>


Just recently I found a french site with a solver that is using
Takaken's algorithms. It is said to be even faster than Takaken's
solver. I haven't tested it myself yet.

<p>


Solveur Sokoban:
http://perso.wanadoo.fr/paul.voyer/sokoban/solveur.html

<p>


The fastest solver I found is incorporated in a freeware Sokoban
program for OS/2 and Win32. It can handle rather large problems.

<p>


http://www.xylo.freeserve.co.uk/sokoban.htm

<p>


If anyone has any more solver I would be interested. I tried to write
one myself a year or so ago. I never did implement all of the
optimizations I had planned, though, and it turned out too slow for
larger problems.

<p>


And Phil, I _did_ manage an eagle once in Mario's Open Golf in the
form of a hole-in-one. As I remember it I put two balls out of bounds
right after that and never finished the round.

--
Albin@518.nu

Chad

Post by Chad » Tue Sep 18, 2001 12:30 pm

I think these solvers don't find optimal solutions, but they do find
solutions which is cool. I wouldn't go to the french site (maybe
site down.) I branch and bound algorithm might be possible to find
optimal sokoband pushes/moves, i also tried and never got around to
finishing a sokooptimalsolver.

--
churritz@crash.cts.com

phil

Post by phil » Tue Sep 18, 2001 12:30 pm

Paul Voyer is not french but canadian if I remember correctly ; his
solving program is the "solve.exe" I sent you, Skito

<p>

And Abbe : congrats for your hole-in-one ; I know now IT is possible

--
plamat@club-internet.fr

Chad

Post by Chad » Tue Sep 18, 2001 12:30 pm

oops i typed i "wouldn't" but i meant I "couldn't" I can now.
thanks phil.

--
churritz@crash.cts.com

Locked