I understand it's very very very hard to write a drod solver. And it would require insane amount of work to make it
understand the game. I think it will happen no sooner than we have a real Artificial Intelligence. If ever.
Even something as 'simple' as optimising 20 moves can be dreadfully complex. You forgot to include monsters. A lot of rooms depend on getting some monsters to go somewhere, avoid force arrows and other snags.
Don't forget about movement order, too ! Movement order puzzles can be designed in such way that there's NO way to know if you're choosing the right move.
For this reason I think it's extremely unrewarding to write a smart drod solver. Yes, I actully think brute force program is more realistic. Humans use lots of high-level concepts to simplify things. You don't need to understand how an engine works to drive a car. It's easy to overestimate 'intelligence' of computers until you start messing with programming. Especially Assembly. Ugh.
I guess
smart_drod_solver/bruteforce_drod_solver = conventional_3D graphics/raytraced_graphics
-----------
However, I think it's quite realistic to write successful brute force solvers for narrow tasks. These can be optimised to only perform moves which may help the cause. Some rooms will be solvable.
As we know from Challenge board, some rooms are solvable without ever rotating your sword.
Let's assume a room contains only floor, pits, walls, obstacles, doors and orbs BUT not orbs linked to doors, wubbas, fuses but NOT bombs (at least not reachable ones), 100% stable tar (2x2 etc), trapdoors, no mimics, and no monsters other than wubbas.
Such a room is likely a trapdoor puzzle. It doesn't matter. What matters is that Q, W and 5 keys are pointless in such room. Instead of 11^n , where n is lenght of solution in moves, you get 8^n . That's quite a bit less.
Further optimisations can be made. If a room contains no trapdoors, no orbs linked to doors, no bombs, no monsters, sequences of moves like NWNW are redundant. I know it's a very big if, but still.
And how about ruling out obvious stupid moves like bumping into walls or monsters ? Or waiting a turn while adjacent to a monster other than wubba, lone wraithwing, tar mother or serpent head adjacent diagonally ? That should improve chances.
Ok, forget all that and assume a room is allowed to contain all devilish DROD obstacles and puzzle elements. It would be foolish to think that the sequence of moves required to solve it is fully random. I bet such a solution sequence often contains subsequences like NNN or WW
WWW. I think a lot of other interesting tendencies would show up. It would be interesting to take solution sequences for 5000 rooms and perform statistical analysis. And compare moves required to elements within the room. Find some relations. It would be VERY rare for a room solution sequence to contain subsequence like Nx40 . (it would require a tunnel).
Now if someone writes such a dirty brute-force solver which tries to perform similar (percentage) sequences of moves, chances of success should be greater. On the other hand, it would never solve some more obscure rooms.
____________________________
http://www.gamasutra.com/features/20051128/adams_01.shtml
[Last edited by b0rsuk at 01-11-2007 10:09 AM]
/dy
I can safely say that I would use a Drod room solver, but not on rooms I haven't already completed. 
