b0rsuk
Level: Smiter

Rank Points: 489
Registered: 11-23-2003
IP: Logged

I think that making a program that actually understands DROD would be fairly pointless.

With each new element, amount of possible solutions grows expotentially, more less.

BUT !! solutions don't really get longer (amount of moves). So brute force approach seems much more reasonable.

____________________________

http://www.gamasutra.com/features/20051128/adams_01.shtml

Cascade
Level: Delver
Rank Points: 46
Registered: 05-28-2005
IP: Logged

If a room takes 500 moves to solve, that's 11^500 solutions (works out around 5 with 520 zeros on the end). That's a lot of solutions to brute-force. Add additional moves to the solution, and "exponential" is exactly the word to use to describe the increase in this number...

If my maths is right, I believe such a calculation would complete several hundred billion years after the death of our sun.

In other words trying to do it this way would be kinda like trying to solve .

Edit: Quantum computing aside, of course...

____________________________
"Does a cow have Buddha nature?"

---

[Last edited by Cascade at 09-29-2005 12:16 PM]

Pinnacle
Level: Smitemaster

Rank Points: 1129
Registered: 06-10-2004
IP: Logged

Well, we obviously can't brute-force it, but in DROD,
a room consists of a series of smaller scenarios. If
a computer could scan the positions of the enemies in
relation to Beethro, and determine a solution by heuristics,
it could theoretically solve a room step by step.
After all, that is how I solve a room.

____________________________
Once (adv.): Enough.
Twice (adv.): Once too often.
~Ambrose Bierce, The Devil's Dictionary

Cascade
Level: Delver
Rank Points: 46
Registered: 05-28-2005
IP: Logged

Pinnacle wrote:
Well, we obviously can't brute-force it, but in DROD,
a room consists of a series of smaller scenarios. If
a computer could scan the positions of the enemies in
relation to Beethro, and determine a solution by heuristics,
it could theoretically solve a room step by step.
After all, that is how I solve a room.

I agree. I think it is essential to apply domain-specific knowledge. You could use this knowledge to aid a brute-force approach, in that you can use it to prune unhelpful solution paths.

The problem as I see it is that the moment you add domain-specific knowledge, like "If a 2x2 passageway is blocked by tar and it leads to the exit, prune this branch from the solution tree" then it is no longer, strictly speaking, the computer playing DROD. After all, you can add specificity all the way up to "If you are playing level x, room y, you should first kill the roach queen at coordinates 100, 205".

This is a little like us, in that I guess now when I play DROD it is not strictly me doing all the work, because some of my work was done by the wonderful people who explained to me how serpents moved, or what a good strategy was for herding goblins.

Perhaps the problem should be reduced to "Can a program be designed which is capable of solving an unseen room (also unseen by the programmers!)".

Now you can load this program with a wealth of knowledge (goblin combat tactics, snake manipulation, orb puzzle solving algorithms) that is room-independant.

This program has a fighting chance, I think, but will suffer like a human in that if it wasn't loaded with, say, snake manipulation knowledge, it would flail helplessly when forced to lure a snake into a west wall alcove. And then, just like a human, it needs either to:
A: Identify the need for more domain knowledge, identify how to get this, go about getting it then codify it
or
B: Go to the developer for help (kinda like going to the hints and solutions forum!)

So maybe we should only load the program with the information available in the help files! And also the information we have from playing loads of puzzle games, such as our knowledge of puzzle/goal structure, the idea of rooms having "themes" or central concepts, the idea of rooms often being based in stages... ideas of "symmetry" or heuristics based on assuming the room designer had certain aesthetics in mind...

The original question is rapidly eroding under layers of qualifications and exceptions...

I think maybe my signature has the answer?

____________________________
"Does a cow have Buddha nature?"

BenStandeven
Level: Delver
Rank Points: 34
Registered: 10-06-2003
IP: Logged

File: Computational Complexity.hold (2.5 KB)
Downloaded 54 times.
License: Public Domain

Here is the NP-problem hold I created.

I found a proof of the PSPACE-completeness of Sokoban at:
http://web.cs.ualberta.ca/~joe/Preprints/Sokoban/paper.html

It seems quite straightforward to adapt it to DROD; in fact several of the gadgets used in the proof become simpler, especially the crossover.