Announcement: Be excellent to each other.


Caravel Forum : Caravel Boards : Development : Drod Robot (Has anyone actually considered it?)
Page 1 of 2
2
New Topic New Poll Post Reply
Poster Message
TripleM
Level: Smitemaster
Rank Points: 1373
Registered: 02-05-2003
IP: Logged
icon Drod Robot (0)  
So has anyone actually considered making a program that would actually attempt to solve drod levels? I always notice it on the development forum-thing, and thought about it again after I had to write a little program to solve one of the trapdoor/force arrow mazes in A Quiet Place. Of course it would be far too complicated to do one in general, but it may be possible to do one with just a room full of roaches.. and trapdoor mazes shouldn't be too hard either.
11-29-2004 at 12:15 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
Stefan
Level: Smitemaster
Avatar
Rank Points: 2119
Registered: 05-25-2004
IP: Logged
icon Re: Drod Robot (0)  
I've actually done one that can solve small roach puzzles. It's very difficult to configure and use, as all information about the room is hard-coded into the source-code.

I also have a generic orb-puzzle solver (also very hard to use and configure).

Both programs work, but I hardly ever use them. It usually takes less time to figure out what to do yourself than to enter the required data in the program(s) and wait for the solution to pop out.

____________________________
0.099³
11-29-2004 at 12:39 AM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
RoboBob3000
Level: Smitemaster
Avatar
Rank Points: 1978
Registered: 10-23-2003
IP: Logged
icon Re: Drod Robot (+1)  
I consider myself to be a DROD robot.

____________________________
http://beepsandbloops.wordpress.com/
11-29-2004 at 10:50 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
masonjason
Level: Smiter
Avatar
Rank Points: 349
Registered: 12-29-2003
IP: Logged
icon Re: Drod Robot (0)  
I'm no programmer, but if I were trying to make a robot for DROD, I'd probably take the "exhaustive search" approach. Of course, that would get VERY system-intensive when checking 11^200 possible move sequences with a brain in the room. Eliminating moves into walls or pits would possibly cut that down a bit, though, and it could be a good way of automatically solving short, relatively simple rooms.
All you computer people tell me if I'm being stupid.

____________________________
Eighty people came to the bazaar.
11-30-2004 at 08:56 AM
View Profile Send Private Message to User Visit Homepage Show all user's posts This architect's holds Quote Reply
joker5
Level: Smitemaster
Rank Points: 607
Registered: 11-25-2003
IP: Logged
icon Re: Drod Robot (0)  
Nope.

And any DROD robot that I wrote would be much simpler.... probably along the lines of a deductive thingy what starts with the last possible moves and patiently works its way back to the start of the room in a viable sequence of undos.

~joker5

____________________________
Criminals, like other people, dislike being shot. ~FBI study on guns

www.badgerbadgerbadger.com

"Two words: Beam Waffle!" -me
11-30-2004 at 03:24 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
Schik
Level: Legendary Smitemaster
Avatar
Rank Points: 5381
Registered: 02-04-2003
IP: Logged
icon Re: Drod Robot (0)  
I'm pretty sure that "simple DROD robot" is an oxymoron. But good luck with that, let me know how it goes. :)


____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi
11-30-2004 at 03:59 PM
View Profile Send Private Message to User Send Email to User Show all user's posts High Scores Quote Reply
masonjason
Level: Smiter
Avatar
Rank Points: 349
Registered: 12-29-2003
IP: Logged
icon Re: Drod Robot (0)  
joker5 wrote:
Nope.

And any DROD robot that I wrote would be much simpler.... probably along the lines of a deductive thingy what starts with the last possible moves and patiently works its way back to the start of the room in a viable sequence of undos.

~joker5
Wouldn't that be less simple? After all, when Beethro makes a move there's only one way the monsters can act. But after an undo, there are several places monsters could have come from... and a huge number of possible final layouts, and only one initial one.

____________________________
Eighty people came to the bazaar.
11-30-2004 at 04:59 PM
View Profile Send Private Message to User Visit Homepage Show all user's posts This architect's holds Quote Reply
joker5
Level: Smitemaster
Rank Points: 607
Registered: 11-25-2003
IP: Logged
icon Re: Drod Robot (0)  
Eh... you could only pick so many paths from the end and so many from the beginning and quite frankly I'd rather have a bunch of innovative wasteage than a lot of forseen wastage (moving straight towards a roach that's 1 square away, for instance).

~joker5

____________________________
Criminals, like other people, dislike being shot. ~FBI study on guns

www.badgerbadgerbadger.com

"Two words: Beam Waffle!" -me
12-01-2004 at 01:07 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
ErikH2000
Level: Legendary Smitemaster
Avatar
Rank Points: 2794
Registered: 02-04-2003
IP: Logged
icon Re: Drod Robot (0)  
Here's my suggestions for anybody who wants to build a DROD robot. (They called you CRAZY! And they were right!)

You can't be exhaustive in your searches for a room solution. Consider that a solution to the 8x8 chessboard (i.e. "White always wins if these instructions are followed") has not been discovered yet with all the brainpower and heavy machinery that has been assigned to it. DROD has a 38x32 board, eleven possible moves on most turns, and rooms typically require many more turns to complete than single games of chess do.

A decent swordfighting AI might be possible with node searches that go 3 or so turns ahead, and that would be interesting to see. For figuring out general strategy to a room other than just finding and killing monsters, oh boy... Hard! Even for Mr. Rimer, a man with published papers on artificial intelligence, and who coded up the unassailable 39th Slayer!

-Erik

____________________________
The Godkiller - Chapter 1 available now on Steam. It's a DROD-like puzzle adventure game.
dev journals | twitch stream | youtube archive (NSFW)
12-01-2004 at 01:21 AM
View Profile Send Email to User Show all user's posts This architect's holds Quote Reply
Scott
Level: Smitemaster
Rank Points: 578
Registered: 02-12-2003
IP: Logged
icon Re: Drod Robot (0)  
I wote a program to try and solve that room on level 15. But it was going to take so long to run that I solved it much faster on a piece of paper.
12-01-2004 at 03:01 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
patmo98
Level: Delver
Rank Points: 39
Registered: 03-14-2003
IP: Logged
icon Re: Drod Robot (0)  
I have no programing skill, but if the sulution is 50 moves long that is 11^50. I think that 100,000 moves per second is to many, but lets say you have a fast computer. That gives you about 10^47 seconds, or about 3*10^39 years. :no I think this thought needs to be put to rest until computers get faster.
12-01-2004 at 05:02 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
masonjason
Level: Smiter
Avatar
Rank Points: 349
Registered: 12-29-2003
IP: Logged
icon Re: Drod Robot (0)  
Yup.
So is DROD, like Go, something computers just can't do? Or is it like chess in that programs can be written to defeat a human master?

____________________________
Eighty people came to the bazaar.
12-01-2004 at 04:35 PM
View Profile Send Private Message to User Visit Homepage Show all user's posts This architect's holds Quote Reply
Maurog
Level: Smitemaster
Avatar
Rank Points: 1501
Registered: 09-16-2004
IP: Logged
icon Re: Drod Robot (0)  
DROD is a way of life.

Personally I think that if a bot will be smart enough to beat DROD, then it would pass easier things like Turing's Test without any problem :)

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!
12-01-2004 at 04:50 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
patmo98
Level: Delver
Rank Points: 39
Registered: 03-14-2003
IP: Logged
icon Re: Drod Robot (0)  
Maurog wrote:
DROD is a way of life.

Personally I think that if a bot will be smart enough to beat DROD, then it would pass easier things like Turing's Test without any problem :)

What is Turing's Test?
12-01-2004 at 06:02 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Maurog
Level: Smitemaster
Avatar
Rank Points: 1501
Registered: 09-16-2004
IP: Logged
icon Re: Drod Robot (0)  
The Turing Test defines a level of AI which wasn't yet reached by any existing program, I believe.
If it passes Turing's Test it's practically human - for example, it must know how to lie :)

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!
12-01-2004 at 06:07 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Oneiromancer
Level: Legendary Smitemaster
Avatar
Rank Points: 2936
Registered: 03-29-2003
IP: Logged
icon Re: Drod Robot (0)  
Google is your friend...

The first link.

Simply put, it's a test to determine if an Artificial Intelligence can pass for human.

Game on,

____________________________
"He who is certain he knows the ending of things when he is only beginning them is either extremely wise or extremely foolish; no matter which is true, he is certainly an unhappy man, for he has put a knife in the heart of wonder." -- Tad Williams
12-01-2004 at 06:07 PM
View Profile Send Private Message to User Send Email to User Show all user's posts This architect's holds Quote Reply
DiMono
Level: Smitemaster
Avatar
Rank Points: 1181
Registered: 09-13-2003
IP: Logged
icon Re: Drod Robot (0)  
The basis of the Turing Test is that you sit in front of a computer holding a conversation with either a person or an AI, but you're not told which. If the AI can fake you in to thinking it's human, it passes the test. Several AIs have come close, but none have actually passed this test yet.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!
12-01-2004 at 06:27 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts This architect's holds Quote Reply
bdcribbs
Level: Smiter
Rank Points: 390
Registered: 04-08-2003
IP: Logged
icon Re: Drod Robot (0)  
Maurog wrote:
The Turing Test defines a level of AI which wasn't yet reached by any existing program, I believe.
In some competetions, programs have passed the Turing test, and amusingly enough, humans have failed it.
Edit: I searched for a web reference to that fact but didn't find it. I read it in some book or article by Douglas Hofstader, who has much to say on the topic.

[Edited by bdcribbs at Local Time:12-01-2004 at 06:34 PM]
12-01-2004 at 06:32 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts Quote Reply
trick
Level: Legendary Smitemaster
Rank Points: 2580
Registered: 04-12-2003
IP: Logged
icon Re: Drod Robot (+1)  
I don't think a DROD bot would need to pass the Turing test. After all, DROD is based on strict rules, without any randomness at all. I don't know whether human behaviour is strictly based on rules or not, but if they are, they're incredibly more complicated than anything else (and may be modified at any time by new nerve paths growing in stimulated parts of the brain)... We humans can do wildly illogical things for apparently no other reason than that we wanted to. There's no reason for a DROD bot to be able to do that.

So, the difficulty in creating a DROD bot isn't that it needs to think like a human. The rules are set, there's no randomness... All the bot has to do is to examine the current room situation based on the game's rules, and it will be able to win every time. There's no reason why this shouldn't be possible, if given an infinite amount of processing power... The difficulty lies in that there's an incredible amount of possible combinations, and if the bot should examine each one, we'd probably need a supercomputer working for the rest of the Earth's lifetime (or more) before coming up with an answer.

Since a bot examining each possible move combination would be useless, we need to do something else. If we could find a set of room "parts" consisting of a group of objects in a particular setup, where several of these parts could be combined to create every possible room configuration, we could teach the bot how to solve each part individually, and it should be able to combine its knowledge of how to solve the different parts of the room into a path to victory. Actually creating a relatively low amount of parts in this way doesn't seem possible, though.

So, if teaching the bot beforehand how to solve rooms isn't possible (or, maybe possible but wildly inefficient), the bot has to be able to learn. We could have the bot starting out stupid, and use some sort of self-teaching neural network to try out situations where it can get points or lose points based on what happens and modify its actions based on that... Actually creating this system so that it doesn't try too many combinations wouldn't be easy, though.

(Disclaimer: I know nothing about AI. :P)

- Gerry
12-01-2004 at 06:35 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
HappyMutant
Level: Delver
Rank Points: 36
Registered: 11-22-2004
IP: Logged
icon Re: Drod Robot (+1)  
Actually, I've been studying the rudiments of AI from a couple of angles this semester. (I'm an undergrad in college.) While I'd certainly defer to anyone who's really done much with AI, it seems to me that this is possible, though difficult.

First off, one of the difficulties in making a strong chess (or Go) program is that your opponent gets to make a large number of moves up against your own. This mitigates the complexity of short tree searches - there are only 11 possible moves (move, turn, or wait) for each of Beethro's moves, and the monsters' moves are deterministic. So, a 10-depth tree is much less expensive than the same depth for, say, chess. However, tree searches through an entire level - several hundred moves, often - are rather too deep to do naively.

On the other hand, I'm willing to bet that no one here performs exhaustive tree searches in their head when they play DROD. So how do you go about solving a room? I usually plan out a series of intermediate goals - hit that switch, place that mimic, kill a swath of roaches to reach point x. Detecting these goals is often both the most difficult part of a puzzle and the most interesting - usually, the rest is routine in a local neighborhood (swordplay in a small area, properly disposing of tar, etc.).

I think that the intermediate goals might be learnable by a neural network or genetic algorithm, as these tasks seem to be related to pattern recognition. The steps required to reach these goals are probably simpler and possibly hand-codable, though an element of self-modification would be important to handle strange cases.

So, this might be feasible, maybe. But it'd take a whole lot of time and effort. I'll put it on my list of "Things to do when I have free time." Of course, it's queued up behind at least two dozen other things. *shrug*
12-02-2004 at 03:27 AM
View Profile Send Private Message to User Visit Homepage Show all user's posts Quote Reply
wobbus
Level: Roachling
Rank Points: 9
Registered: 02-21-2005
IP: Logged
icon Re: Drod Robot (0)  
If you make a program to solve holds easily, would it be possible to write a program that could make them?

____________________________
wobbus
02-23-2005 at 12:24 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
DiMono
Level: Smitemaster
Avatar
Rank Points: 1181
Registered: 09-13-2003
IP: Logged
icon Re: Drod Robot (0)  
Sure you could, it involves a random number generator being active for each square. Now, a program to create good holds would be something.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!
02-23-2005 at 02:41 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts This architect's holds Quote Reply
rothro
Level: Delver
Avatar
Rank Points: 46
Registered: 06-29-2004
IP: Logged
icon Re: Drod Robot (0)  
Hi,

HappyMutant wrote:
[...] This mitigates the complexity of short tree searches - there are only 11 possible moves (move, turn, or wait) for each of Beethro's moves, and the monsters' moves are deterministic.
[...]
I think that the intermediate goals might be learnable by a neural network or genetic algorithm, as these tasks seem to be related to pattern recognition. The steps required to reach these goals are probably simpler and possibly hand-codable, though an element of self-modification would be important to handle strange cases.

nice analysis - my 2 pennies:

Unfortunately monster movement is deterministic, but not transparent, i.e. monster placement order has an effect on movement. There are rooms that explicitly use this feature to become solveable (or more difficult...) Or think of mazes under tar. Thus two indistinguishable inputs will potentially need vastly different solutions. They all mean that a trial and error approach in the bot must allow him to learn from previous attempts. That alone makes the problem an order of magnitude harder.

Also in many cases the solution can not be broken down, but the order in which tasks are completed, their timing, side-effects etc. are all important. Think of a puzzle where the first part could be solved easily by hitting an orb which modifies a dungeon element in a much later state in the room such that it becomes unsolveable (close a yellow door in front of the only exit, but hide it under tar). Thus the straightforward solution was the wrong one, but it is not obvious until the very end, potentially hundreds of moves in the future. A universal bot would then need to backtrack to the start of the problem.

Good examples how small modifications can seriously inflate the difficulty of a room are the various "Return to ..." holds.

My guess is (i.e. no formal proof offered), that finding a solution to every drod room may generally be in the class of problems requiring exponential time and only special cases may seem easy. Thus such a bot would be next to useless. It could do the easy cases (sometimes), but choke on all interesting ones.

So, the only solution I have is that we chip in, and pay Stefan to quietly sit in a small cabinet and move a mechanical arm that plays drod to perfection... :Notworthy

Cheers,
Rothro

____________________________
And god spake unto me "Be merry and glad in your heart, for it could be much worse!"
And I was merry and glad in my heart and it got worse!
02-23-2005 at 04:06 PM
View Profile Send Private Message to User Show all user's posts Quote Reply
b0rsuk
Level: Smiter
Avatar
Rank Points: 489
Registered: 11-23-2003
IP: Logged
icon Re: Drod Robot (0)  
Now tell me how stupid I am.

I've been thinking about solving DROD levels using.... brute force. You know, where every single combination of moves is run.
The major difficulty (aside from sheer numbers) would be making it so it doesn't make loops, like q w q w q w q w q w q w until end of time. I wonder if it's even possible .
Every attempt would run until Beethro dies, room is solved, or certain upper limit of moves is reached.
I think that at least for small rooms, brute force DRODer should be able to conquer them. You can set upper move limit to something low, like, hmm, 50.

Does this idea have future ? I don't mean future like zillions of years spent running all the combinations... One good point of this idea is that you don't have to make the program think, just optimise the algorithm so it doesn't repeat any attempt, and so on.

[Edited by b0rsuk at Local Time:03-18-2005 at 12:23 PM]

____________________________

http://www.gamasutra.com/features/20051128/adams_01.shtml
03-18-2005 at 12:21 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Stefan
Level: Smitemaster
Avatar
Rank Points: 2119
Registered: 05-25-2004
IP: Logged
icon Re: Drod Robot (0)  
As I've mentioned somewhere before (I think), I've done a DROD robot that solves (very) small roach puzzles by brute force (I could quite easily add other monster types, but right now it's a roach-only solver). It only works effectively (on a relatively fast computer) if the solution is <15 moves, though, so I don't really think anything much larger than that would be feasible. My program doesn't repeat a sequence of moves if it leads to death, but I haven't made any other optimizations, so it could be possible to make it work fast enough for, say, perhaps 30 moves?

____________________________
0.099³
03-18-2005 at 01:02 PM
View Profile Send Private Message to User Show all user's posts This architect's holds Quote Reply
b0rsuk
Level: Smiter
Avatar
Rank Points: 489
Registered: 11-23-2003
IP: Logged
icon Re: Drod Robot (0)  
Instead of reinventing the wheel, could it be possible to trim DROD to barebones version (removing graphics, sound support and so on) and make a program which simply enters some imput and stops if receives "room solved" signal ?

____________________________

http://www.gamasutra.com/features/20051128/adams_01.shtml
03-18-2005 at 01:52 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
DiMono
Level: Smitemaster
Avatar
Rank Points: 1181
Registered: 09-13-2003
IP: Logged
icon Re: Drod Robot (0)  
It's certainly possible, all you'd have to do is comment out the code that controls graphical display and run it as a command-line interface. The trouble with that is you'd have no idea if it was still running, or if it had stalled, because each room no matter how small is going to take quite a while to run through. Even if you cap the moves at 50, 11 move possibilities 50 times over is quite a large number.

____________________________
Deploy the... I think it's a yellow button... it's usually flashing... it makes the engines go... WHOOSH!
03-19-2005 at 03:53 PM
View Profile Send Private Message to User Send Email to User Visit Homepage Show all user's posts This architect's holds Quote Reply
b0rsuk
Level: Smiter
Avatar
Rank Points: 489
Registered: 11-23-2003
IP: Logged
icon Re: Drod Robot (0)  
Actually, probability is one of my favourite branches of math. And yes, 11^50 is pretty scary.

So maybe some crude optimization would help ?
Why crude - because it won't solve non-standard rooms. It could be done so that it does some moves less often than others. (For example I bet 5 is used a bit less than others.) Someone should make statistics and calculate how many times, on average, each key is pressed in typical room solution.

I still think it's more likely to happen than solving DROD by smart program. Another "strong" point of this way is that it doesn't have to care about new elements being added. I mean, JTRH is going to add good deal of new elements. Amount of combinations possible grows pretty much expotentially with each new game element added. Solutions in probability sense don't get more complex. By this I mean you still have 11 moves possible per turn, and I don't believe that typical room solution will be 50% longer now. The playing field remains same size, too, which is 38x32 I believe. So this solution might actually have future.

How about hybrid brute force-smart program ? Something like this:make a random move unless it's clearly very stupid. Very stupid moves would be bumping into walls/monsters and possibly other moves. For example moves like exiting the room if it's not cleared yet.
Would this speed up the process, or rather checking all the conditions each move would slow it down ?


____________________________

http://www.gamasutra.com/features/20051128/adams_01.shtml
03-19-2005 at 04:37 PM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
ZorbaTHut
Level: Roachling
Rank Points: 14
Registered: 12-08-2004
IP: Logged
icon Re: Drod Robot (+1)  
rothro wrote:
My guess is (i.e. no formal proof offered), that finding a solution to every drod room may generally be in the class of problems requiring exponential time and only special cases may seem easy. Thus such a bot would be next to useless. It could do the easy cases (sometimes), but choke on all interesting ones.

Slightly more formal proof:

The way to prove this, in general, is to take another problem that's known to be in that class and show that you can construct that problem in terms of this. There's a problem known to be in that class called 3-SAT.

Quick informal description of 3-SAT: You have a bunch of boolean (true/false) variables. You have a series of equations that state "either A must be false, or B must be true, or D must be false" - three boolean variables, each of them restricted to be either true or false, put together with "or"s. That series is itself strung together with "and"s.

"( not A or B or not D ) and ( A or not B or D )" is true, because you could have "not A" and "not B" and that would do it.

Obviously you could set this up in DROD easily - you just have a wide corridor with a series of gateways. Each gateway has three doors side-by-side. If you can get through any of those doors, you can get to the next gateway. And then outside the corridor, you have a bunch of orbs that you can use to create any system of booleans.

Bam. 3-SAT in DROD. DROD is NP-complete or worse, and therefore can't be practically solved, in all cases, by computers. Or humans, for that matter.

Which isn't to say that it's impossible to write a bot that could solve all human-solvable levels.
04-05-2005 at 04:46 AM
View Profile Send Private Message to User Show all user's posts Quote Reply
Maurog
Level: Smitemaster
Avatar
Rank Points: 1501
Registered: 09-16-2004
IP: Logged
icon Re: Drod Robot (0)  
Human solvable level? You mean something like telling the robot a five digit number in a scroll, then asking him to construct the number using an appropriate number of orbs (you need 35). I reckon a human will solve it rather quickly, while a robot may go for ages. In fact, if hitting a wrong orb makes it unsolvable, the robot just won't ever find a solution. How will a DROD robot know the puzzle became unsolvable? I think it will just go on and on and on.

Robots can't read scrolls.
Robots will have a really hard time checking if they are lost.

In fact, if you show me how to build a robot which can tell you if a room changed state into unsolvable, I will be very impressed.

____________________________
Slay the living! Raise the dead!
Paint the sky in crimson red!
04-05-2005 at 06:19 AM
View Profile Send Private Message to User Send Email to User Show all user's posts Quote Reply
Page 1 of 2
2
New Topic New Poll Post Reply
Caravel Forum : Caravel Boards : Development : Drod Robot (Has anyone actually considered it?)
Surf To:


Forum Rules:
Can I post a new topic? No
Can I reply? No
Can I read? Yes
HTML Enabled? No
UBBC Enabled? Yes
Words Filter Enable? No

Contact Us | CaravelGames.com

Powered by: tForum tForumHacks Edition b0.98.8
Originally created by Toan Huynh (Copyright © 2000)
Enhanced by the tForumHacks team and the Caravel team.