K2xL.com

Discuss life, the internet, games, and everything in between.
It is currently August 17th, 2017, 7:06 pm

All times are UTC - 5 hours [ DST ]




Post new topic Reply to topic  [ 48 posts ]  Go to page Previous  1, 2, 3, 4, 5
Author Message
 Post subject: Re: Solver algorithm?
PostPosted: July 1st, 2008, 12:56 pm 
Offline

Joined: March 14th, 2008, 8:26 am
Posts: 109
Data structures apply to multiple languages, just in Java they have created the container classes for you.


Top
 Profile  
 
 Post subject: Re: Solver algorithm?
PostPosted: July 1st, 2008, 1:14 pm 
Offline

Joined: March 26th, 2008, 10:12 pm
Posts: 101
I'm thinking of learning C++ or Basic... But does that mean you have to allocate things into say, a hashtable, all by yourself in one of these languages? Bah. This is really confusing!

_________________
:D


Top
 Profile  
 
 Post subject: Re: Solver algorithm?
PostPosted: July 5th, 2008, 12:39 am 
Offline

Joined: March 14th, 2008, 8:26 am
Posts: 109
As far as I know yes, you would have to write the code yourself to implement and keep maintained the data structure you have in question, but I am sure there are places you can find the base code for certain structure types.


Top
 Profile  
 
 Post subject: Re: Solver algorithm?
PostPosted: January 20th, 2011, 9:47 pm 
Offline

Joined: January 18th, 2011, 4:56 pm
Posts: 3
I've actually written a solver for PP1 in the past few days, my philosophy being that it's okay to use computer assistance provided you write the program yourself. This is of course justified by the complexity of the problem of writing the solver...

I think I've used a different technique than has been discussed so far: I am treating a move plus a block push as a single node, and using Dijkstra's algorithm to find possible moves and to generate the initial distance-to-exit map. This has so far made duplicate detection unnecessary, though I might end up adding it soon as I discover the limitations of solving more advanced levels.

So far it is producing results for levels 1-24 within seconds, but is taking much longer over 25-27 (all of which I have solved by hand). At one point I got a solution for level 25 in 25 minutes, but adjustments to try and solve level 26 have apparently made that worse. It appears that the very large number of reachable blocks and the inconvenient holes in the wall structure (which make the exit seem closer than it is) are defeating my impossibility detection heuristic, causing much larger numbers of nodes to be processed than for earlier levels.

As a workaround, I've introduced another heuristic which makes it try to push the same (or an adjacent) block again, before moving on to blocks that are further away. This means that it should be likely to carry on pushing a block down a corridor rather than hyperactively running all over the map. Of course if that turns out to be an incorrect branch of the search tree, then it still needs to run around like a headless chicken until it gets back to the incorrect move. I suppose this is where duplicate detection might start to help.

EDIT: I've now implemented an opportunistic duplicate detection, and removed my previous sorting heuristics. This has halved the time-to-first-solution for level 25 (to 12.5 minutes), which bodes well for more complex levels. The method I've used for this involves an enormous multidimensional array, which is left uninitialised, and a separate counter array. The size of the main array precludes much use on 32-bit machines, but the actual memory consumption is not very high because it is written only sparsely.


Top
 Profile  
 
 Post subject: Re: Solver algorithm?
PostPosted: January 29th, 2011, 10:22 pm 
Offline
User avatar

Joined: March 13th, 2008, 5:28 pm
Posts: 279
Location: Deep Inside a canadian forest
That's great!

I've learned a lot about programming since my first post in this topic, a few years ago. I would be able to write such a program, now. I'd be happy to do so. I wish I had the time to ^^.

I'd do it in C or C++ of course :D. (Java can go die in a fire)

_________________
Diablillo: Yeah, you're very tough.
Diablillo: You're like Rambo.


Top
 Profile  
 
 Post subject: Re: Solver algorithm?
PostPosted: January 30th, 2011, 8:17 am 
Offline

Joined: January 18th, 2011, 4:56 pm
Posts: 3
Well, I seem to be having trouble with the de-duplicator now. It didn't seem to be detecting enough duplicates, so I made it keep *every* position for checking rather than limiting it - at which point the RAM usage ballooned and it still hadn't solved level 26 overnight.

The next stage might be to explicitly incorporate "push by N spaces" into the definition of a single move, since that reduces the opportunities for needless backtracking. The de-duplicator can handle the fallout from that after some retuning.

Still not sure why it can't cope with level 27, though.


Top
 Profile  
 
 Post subject: Re: Solver algorithm?
PostPosted: June 23rd, 2015, 8:33 pm 
Offline
User avatar

Joined: March 14th, 2008, 8:26 pm
Posts: 278
Here's something a friend of mine did. It's pretty successful, though it can't solve lock levels really.

http://hungryomii.github.io/Psychopath_Solver/

_________________
"Never underestimate the power of human stupidity." - Robert Heinlein


Top
 Profile  
 
 Post subject: Re: Solver algorithm?
PostPosted: July 19th, 2015, 4:53 pm 
Offline

Joined: January 18th, 2011, 4:56 pm
Posts: 3
Javascript? Oh dear...

It looks like a good algorithm, but the language is too inefficient to deal with large problems. Recoding it in a more efficient language (both in speed and the ability to use compact storage formats) might help it to deal with levels beyond its current capabilities.

I still have my own solver somewhere, but I might have to dig to figure out where I left it. Or I could rewrite it from scratch - it's not amazingly complex.

I am however still trying to figure out what he means by:
Quote:
...slightly changing the heuristic to look at 2 adjacent squares instead of individual squares.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 48 posts ]  Go to page Previous  1, 2, 3, 4, 5

All times are UTC - 5 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
cron
Powered by phpBB® Forum Software © phpBB Group