ZorbaTHut
Level: Roachling
Rank Points: 14
Registered: 12-08-2004
IP: Logged

I said it wasn't impossible - which in no way maps to "it's easy".

Obviously you'd need a human level of comprehension and logic. But nobody's proven that's impossible, and I find it highly unlikely that it's impossible.

Solving an NP-complete problem is, while not technically impossible, totally impractical. (Well, it's believed so - that still hasn't been proven yet either.) Something as "minor" as making an AI capable of human-level thought isn't known to be impractical - we just don't know how to do it.

It's the difference between "proven impractical" and "not known".

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

What you think about programs which can't solve arbitrary DROD rooms but which can help to solve DROD rooms? For example, you tell restrictions and the goal and the robot try's to solve this part of room or at least to optimize your solution. So you have to figure out the general idea of the room first in most cases. If such robot helps at least in some rooms, it would be useful.
How many such useful in practice programs already written, you think?

chs13
Level: Goblin
Rank Points: 15
Registered: 04-18-2007
IP: Logged

b0rsuk wrote:

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.

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

Actually this is an easy problem to fix, and the fix also reduces the search tree. I have a friend who worked on the Cray blitz chess team back in the 80s. Their solution was to save all the previous board positions and index them with a hash code. Any new board position would search for previous positions using a hash lookup, and prune itself when a duplicate position was found. You would probably want to have an option for including the state of the threat clock as part of the board position.

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

That is what I exactly do in my DROD solver. Although I don't check is positions are really equal, if they have the same hash.

Krissan
Level: Delver

Rank Points: 89
Registered: 04-08-2006
IP: Logged

Almost a year ago, I got the idea to set up a neural network and try to teach it how to handle roaches with a genetic algorithm. It soon made the dreadful "Things to do when I have free time" list that someone else posted about. Still haven't time to do it, but just checking to see if anyone has done something like that already?

The roach-puzzle solving programs, how did you do them?

____________________________
Always do sober what you said you'd do drunk. That will teach you to keep your mouth shut. - Ernest Hemingway

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

I just use brute-force droping variants with low score function (-<number of roaches> in the easy rooms).

Gutter
Level: Goblin
Rank Points: 21
Registered: 03-31-2003
IP: Logged

How about a distributed robot, like the folding@home project?

It would be amazing! Millions of cpu, possibly even PS3, searching for every room's solution and maybe even creating new playable rooms at random!

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

Gutter wrote:
How about a distributed robot, like the folding@home project?

It would be amazing! Millions of cpu, possibly even PS3, searching for every room's solution and maybe even creating new playable rooms at random!

The main problem is to find peoples who are willing to give me their cpu time. The second problem is that current algorithm hard to adopt to distributed calculation because of eliminating equal rooms - each computer must store hash values for all rooms. So computers must have very quick internet connection (in order to transmit hash values) and a lot of memory (in order to store them). And this approach would work only in small group of computers (2-5 for typical room).

But there is other approaches. Some times there is a variations in score function. So different computers can check different score functions. This approach doesn't need a lot of traffic but can be applied only to small part of rooms. I have some more ideas but I haven't thought about them much because I can't test them anyway.

PS Also there is a problem with security - peoples have to trust me because I will upload potentially dangerous code to their computers - each room need score function implemented in .dll file.

Gutter
Level: Goblin
Rank Points: 21
Registered: 03-31-2003
IP: Logged

^^^ It wasn't really a suggestion More something in the line of using a "neural network and try to teach it how to handle roaches with a genetic algorithm"