zex20913
Level: Smitemaster

Rank Points: 1721
Registered: 02-04-2003
IP: Logged

The task is very difficult: Can you make an effective DROD solver?

I know nothing about coding (beyond Prolog, which is mildly useless for this sort of thing) so I'm not going to partake, but I think some general guidelines are appreciated here.

1. Global>local. While it's great if you can kill a roach with an algorithm, doing so may very well prevent another monster from being killed. KDD L19 anyone? (I think it's 19 anyway--I'm away from my DROD compy for a while.)

2. More enemies>fewer enemies. Again, while it's great that you can kill a roach, killing more is better. And then there are other monsters to account for. And tar. And spawners. You all know the drill.

3. Elegance>Brute force. This is how it is with all programs. But especially for DROD solvers and the like. The phrase "intelligent design" comes to mind. You may need to apply your DROD skills to your programming ones, and come up with some efficient programming.

4. More rooms/objectives>fewer. It's great if you can make a program to solve JtRH L1, Entrance. I bet my grandmother could do it too, and she's never seen the game (or, it seems, a computer.) While I am exaggerating a bit (and mispelling at least one word) solvers that actually solve interesting rooms are better than those that solve trivial or noninteresting rooms. If you need some clarification on what is interesting or not, search for a room in question on H&S. If it is there, it is interesting. If not, then it is likely noninteresting.

5. Teamwork>individuality>teamwork. This nontransitivity is brought to you by the Clay institute. If you can, by yourself, create an efficient DROD solver, then your work shall be glorified by mathematicians and programmers, and your name will be up there with those of Hilbert, Riemann, and Goedel. It may also end up in contention with the big two: Einstein and Newton. As this is unlikely, however, and we have plenty to do aside from tearing out our follicles in the effort to make a DROD solver, working together is smiled upon, even encouraged. Help each other out. Delegate responsibility if need be--you do some trapdoors, I'll do some serpents, this guy over here will look into ortho square modifications (and I'm not talking beauty pageants here.)

6. Have fun. Keep your day jobs. Don't worry too much about it--it is a very challenging task, as far as I understand it, and should fall into the extracurricular section of life.

I think that's a good set of guidelines, to start out with. However, they are only guidelines, and are NOT comprehensive. There are probably better guidelines out there. There are certainly more. But pay close attention to 5&6. That's what I think the attitude should be.

____________________________

Jatopian
Level: Smitemaster
Rank Points: 1842
Registered: 07-31-2005
IP: Logged

Do specific-need aids such as orb solvers count, or must this be an AI player sort of program?

____________________________
DROD has some really great music.
Make your pressure plates 3.0 style!
DROD architecture idea generator

zex20913
Level: Smitemaster

Rank Points: 1721
Registered: 02-04-2003
IP: Logged

Whatever the heck you want to do is fine. The challenge is to see what parts of solving DROD you can automate, be it orbs, trapdoors, or (my goodness) goblins.

____________________________

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

File: drodsolver.7z (76.7 KB)
Downloaded 161 times.
License: Public Domain

Ok, here is my drod solver.
(You can download archiver at www.7-zip.org if you haven't it)

Now you can check yourself what it can solve with human help and what it can't.

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

Why *did* you make such a fuss about this? Why didn't you simply post here in the first place, saying that you wrote a brute force solver, and telling us about the results?

What you don't get is that this isn't the kind of place where cheating is a problem. We didn't need you to tell us about brute force, and that it could help cheaters in a small way. There are easier ways to cheat, anyway. The only thing that came out of all this is that brute force is slightly more effective than we thought. Instead of 10-20 moves, you can go as high as 30, maybe even more. So what? That's still a long way from 100 or 1000. I don't care exactly how ineffective it is. I'd be interested in something that can solve more than a handful of rooms, using something more interesting than brute force. Unlike you, I wouldn't use it to cheat.

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

In Beethro Teacher L1:1N2E DROD solver calculated more than 200 moves. So the number of moves isn't important at all if you have a good score function.

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

Did it calculate 200 moves in one stretch, or sections of 30 moves or so each?

PS You should have let it done everything for you, instead of thinking you could finish off yourself. What's the score now? For all that trouble you got 5 #1s, lost three of them, and one of the remaining two very likely isn't optimal. And you cheated for that little bit. tsk-tsk-tsk

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

For 1N2E, I have to change score function about every 30 turns without droping variants. I can write universal score function but this idea came to me when I finished up calculating room.

My #1 scores mostly not optimal because they contain human parts. It is quicker to press a button than create complex score function and run solver. So I optimized mostly non-trivial parts of the room. Also solver wasn't support many game elements at the beginning and some #1 score is the result of trying to solve the room, not trying to archive #1 score.

My using of solver before starting poll were mostly testing it. After poll I understood that it is becaming cheating (because of too many #1 for average player) and stoped uploading computer demos.

PS Have you need to see my demo in order to beat my #1? There is a simple test (if you want to participate of course). Can you beat/archive 587 move demo for Beethro Teacher L4:4S1E?

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

Of course I looked at your demo. I wouldn't normally, but this case is different. I noticed the mistake days ago when I suspected you had such a program and looked at your demos, and when you brought it up now, I couldn't resist.

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

Ah, I found stupid mistake in the program. Find all "lock mov" in SearchEngine.pas (procedure TCalcThread.run) and replace with "mov".

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

halyavin wrote:
Can you beat/archive 587 move demo for Beethro Teacher L4:4S1E?

586. Your turn. No cheating, 'kay?

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

With so cool players there is nothing to afraid to.

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

Here is the stats:
You reached first checkpoint at 196 turn, computer reached first checkpoint at 196 turn. You killed the first snake at 306 turn, computer killed the first snake at 304 turn (and wait 2 turn after that because it is not safe to press button this time). You start killing the second snake at trapdoor at 387 turn, computer start killing the second snake at trapdoor at 387 turn. After that the human part follow. You killed the second snake at 492 turn, in computer demo the second snake killed at 491 turn, but beethro is 2 squares further than you from the button.

NiroZ
Level: Smitemaster
Rank Points: 1302
Registered: 02-12-2006
IP: Logged

halyavin wrote:
Here is the stats:
You reached first checkpoint at 196 turn, computer reached first checkpoint at 196 turn. You killed the first snake at 306 turn, computer killed the first snake at 304 turn (and wait 2 turn after that because it is not safe to press button this time). You start killing the second snake at trapdoor at 387 turn, computer start killing the second snake at trapdoor at 387 turn. After that the human part follow. You killed the second snake at 492 turn, in computer demo the second snake killed at 491 turn, but beethro is 2 squares further than you from the button.

Halyavin, by 'turn' Michthro meant for you to beat his demo in under 586 moves.

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

I understand this. I just want to say that Michthro beat computer because the last part of the room isn't obvious to calculate by it and it is worth optimize only the last part of the room now. I think that his demo is very close to the optimal one. And I doubt I can beat even computer demo myself.

Jason
Level: Smitemaster
Rank Points: 1076
Registered: 05-05-2006
IP: Logged

Well he just beat it.

____________________________
Play my holds?

Syntax
Level: Smitemaster
Rank Points: 1218
Registered: 05-12-2005
IP: Logged

Looks like michthro is pretty good at this game.
I'll have to watch my back!

Oh wait Nicely done though (on a serious note)

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

Did someone tried to compile my solver? I wonder how many peoples on this forum knows Pascal.

Briareos
Level: Smitemaster

Rank Points: 3516
Registered: 08-07-2005
IP: Logged

Well, I know it quite a bit. That's why I don't like it and why I don't like to use it...

And combining Java and Pascal in one program is... just... plain... evil.

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009)

---

[Last edited by Briareos at 01-15-2007 04:03 PM]

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

Combining Java and Pascal is impossible as writing usefull drod solve is impossible . I didn't plan to use Java but I wanted to develop program on computer without Lazarus (only plain Free Pascal) once, so I had to use Java for gui. Fortunately for me and unfortunately for the program I had JNI (Java Native Interface) module for Pascal.

BTW, I chosen Pascal for better integration with assembler. Without assembler program is too slow.

---

[Last edited by halyavin at 01-15-2007 04:17 PM]

mrimer
Level: Legendary Smitemaster

Rank Points: 5056
Registered: 02-04-2003
IP: Logged

halyavin wrote:
BTW, I chosen Pascal for better integration with assembler. Without assembler program is too slow.

I know Pascal. In my opinion, it's less effective to use Pascal for speed, even though it has some assembly. I'd recommend rewriting this in C with some assembly.

____________________________
Gandalf? Yes... That's what they used to call me.
Gandalf the Grey. That was my name.
I am Gandalf the White.
And I come back to you now at the turn of the tide.

---

[Last edited by mrimer at 01-15-2007 07:40 PM]

Briareos
Level: Smitemaster

Rank Points: 3516
Registered: 08-07-2005
IP: Logged

halyavin wrote:
Combining Java and Pascal is impossible as writing usefull drod solve is impossible

I said "evil", not "impossible". Java is for writing portable applications and making use of the powerful libraries it comes with. Combining it with natively compiled languages and, even worse, some platform specific assembler absolutely kills that. But that's getting off-topic...

(As for Pascal - writing code in it feels sooo clunky to me compared to other, C-like languages it's not even funny. And having had to use Oberon at the university was the final nail on Pascal's coffin for me - even though my boss then was one of the people who created Oberon... )

np: Tarwater - Seven Ways To Fake A Perfect Skin (Animals, Suns & Atoms)

____________________________
"I'm not anti-anything, I'm anti-everything, it fits better." - Sole
R.I.P. Robert Feldhoff (1962-2009)

---

[Last edited by Briareos at 01-15-2007 05:21 PM]

Stephen4Louise
Level: Smitemaster

Rank Points: 548
Registered: 04-06-2005
IP: Logged

halyavin wrote:
Did someone tried to compile my solver? I wonder how many peoples on this forum knows Pascal.

I was able to compile without too many problems, but once compiled, it wasn't the most intuative program to use.

I did do some Pascal back in uni, and my dissertation was a speech compression program written in Java, but these days I'd be doing well to write a "Hello World!" program.

Steve.

bateleur
Level: Roachling
Rank Points: 13
Registered: 05-05-2006
IP: Logged

This may be way too obvious to post, but I feel a need to point out that writing a genuinely efficient DROD solver could win you a million dollars.

Why ?

Well... it's possible to build logic gates using DROD components. In fact some switches essentially are logic gates. As a consequence of this, any instance of the satisfiability problem can be expressed as a DROD level which is soluble if the expression is satisfiable and not if it isn't.

Since the problem in question is known to be NP complete, solving DROD levels must be at least that hard.

So once you have your efficient general-purpose DROD solver, you should get in touch with those Millennium Prize chaps to claim your bounty.

But don't get too excited about your million pounds, because there's some bad news too: It's also clearly (!) possible to build Turing machines using DROD maps. DROD being Turing-complete means it's subject to the Halting Problem.

Or in layman's terms: it's impossible to write a computer program that will tell you whether DROD levels are soluble or not with 100% reliability.

(Sorry about that little outburst. I'll go back to lurking now.)

---

[Last edited by bateleur at 01-24-2007 10:03 AM : Removed email notification - thread topic has moved on]

AlefBet
Level: Smitemaster
Rank Points: 979
Registered: 07-16-2003
IP: Logged

bateleur wrote:
It's also clearly (!) possible to build Turing machines using DROD maps. DROD being Turing-complete means it's subject to the Halting Problem.

I'm not sure about this. How do you simulate an arbitrarily sized memory tape using DROD rooms? It seems to me that DROD-computable functions would be limited to LBA or at best PSPACE.

____________________________
I was charged with conspiracy to commit jay-walking, and accessory to changing lanes without signaling after the fact .

++Adam H. Peterson

halyavin
Level: Delver
Rank Points: 52
Registered: 02-20-2006
IP: Logged

bateleur
There is no need in 100% reliability. My drod solver gives answers for some of practical rooms (with human help) - this is enough for me.

bateleur
Level: Roachling
Rank Points: 13
Registered: 05-05-2006
IP: Logged

AlefBet wrote: How do you simulate an arbitrarily sized memory tape using DROD rooms?

I was thinking of an arbitrarily long line of rooms. I mean yes, OK, there's a limit on the length in practice, but I think that's no more profound than pointing out that pooters themselves are finite beasts.

State can just be handled via a switch. Beethro (our heroic program counter) is guided down a different passage for "0" and "1" states respectively. State can be set (or unset) by sending Beethro down further tunnels from which he can only emerge after toggling a switch.

AlefBet
Level: Smitemaster
Rank Points: 979
Registered: 07-16-2003
IP: Logged

bateleur wrote:

AlefBet wrote: How do you simulate an arbitrarily sized memory tape using DROD rooms?

I was thinking of an arbitrarily long line of rooms. I mean yes, OK, there's a limit on the length in practice, but I think that's no more profound than pointing out that pooters themselves are finite beasts.

Sure, I'll allow you to have as many rooms as you want. But if you correspond the rooms to the "program" part of the computation, then it needs to be fixed in size before computation begins. All the computational models I've studied have the "state" part of the machine fixed and finite. FSMs, PDAs, and Turing Machines all have a set number of states and transitions arranged to formulate the solution of the problem, which means that however many rooms you want (and I'll even allow for arbitrarily sized rooms as long as the actual required size can be nailed town), you have to stick with.

Alternatively, the rooms can be thought of as at least partially the formulation of the input, or the specific instance to be solved, which would mean that the number of rooms you get is some function of the size of the input. That would allow someone more space for solving a larger problem than a smaller one, certainly, but DROD doesn't have predicates for creating new rooms or resizing old rooms on the fly (although now that it's been mentioned, it may turn up on the FR board). There are computable problems whose space constraint is not easily expressed as a function of the size of the input, so we appear to me to fall short of the domain of Turing-complete.

Before we decide to reason about the computing ability of DROD with such an extension, we have to answer the question of what is in those new rooms as we create them. Adding empty rooms won't buy us very much, and adding just about anything else feels to me like adding program state, which goes beyond what Turing machines and their relatives are generally allowed. Not that I think that adding new program state is cheating, per se, but when you do that, you can't be wishy-washy about exactly what kind of program state you're adding.

____________________________
I was charged with conspiracy to commit jay-walking, and accessory to changing lanes without signaling after the fact .

++Adam H. Peterson

michthro
Level: Smitemaestro
Rank Points: 679
Registered: 05-01-2005
IP: Logged

bateleur wrote:
I was thinking of an arbitrarily long line of rooms. I mean yes, OK, there's a limit on the length in practice, but I think that's no more profound than pointing out that pooters themselves are finite beasts.

Another way would be to go into the editor and add some tape when you run out, then start over. Then at least you avoid infinity (How long is an arbitrarily long line? It has some finite length, or it's infinite.) But, then we're not talking about DROD. Conclusions about infinite DROD or edit DROD don't apply to DROD.

For instance, what does "DROD is subject to the Halting Problem" mean? It boils down to that there is no algorithm that will tell you whether a given hold can be conquered. This is clearly not true for real DROD holds, because any given hold has finitely many states, and a recursive upper bound on the number of states, hence exhaustive search will always work. If you're going to allow infinite holds or rooms, sure, but that makes all the difference, and not because computers are finite, but because it completely changes the game itself. I'm not saying it's not an interesting theoretical topic, but it has nothing to do with DROD. Infinite DROD is another game.

DROD is a finite game, hence solvable by computer (however long it takes), so the question is how efficiently it can be done. Infinite DROD is a whole different (theoretical) game, which can't be solved by computer. Knowing that infinite DROD can't be solved doesn't tell us anything about finite DROD.

bateleur
Level: Roachling
Rank Points: 13
Registered: 05-05-2006
IP: Logged

AlefBet wrote:
Sure, I'll allow you to have as many rooms as you want. But if you correspond the rooms to the "program" part of the computation, then it needs to be fixed in size before computation begins.

Very true. So you're correct that it's not really Turing Complete. On the other hand, any soluble DROD level must correspond to a computation that does actually terminate and therefore uses only a finite amount of workspace. So in fact the consequences for solvers remain much the same assuming one enters each level with the certain knowledge that it can be solved somehow.

michthro wrote:
Knowing that infinite DROD can't be solved doesn't tell us anything about finite DROD.

Although "infinite DROD" makes it sound like we're talking about a DROD level which has an infinite number of puzzles on it. That's not quite the same thing.

(And your statement sounds a bit suspect anyway. The theory of Computability deals entirely with infinite machines and manages not to be completely irrelevant to real computers, noted for their finiteness.)