Mister
Level: Master Delver
Rank Points: 104
Registered: 02-27-2003
IP: Logged

File: Silicon Valley v2.1.hold (4.4 KB)
Downloaded 137 times.
License: Other
From: Unspecified

Ok, here is my "Silicon Valley" hold. It is NOT intended to be played by humans, as is impossibly hard (except maybe one room).

You are welcome to try, of course, but the challenge is basically for programmers to try some [efficient] algorithm to solve them (that's how I created the rooms in the first place).

Only two, repetitive, floors, but give it a try!

EDIT v2: now with c.b.l.f-friendly rooms and a useful "demo roach".

EDIT v2.1: rearranged the c.b.l.f rooms so that my future projects fit better


[Edited by Mister on 08-11-2003 at 07:10 AM]

ErikH2000
Level: Legendary Smitemaster

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

Too much for my merely human capacities. But if I build a robot...

-Erik

____________________________
The Godkiller - Chapter 1 available now on Steam. It's a DROD-like puzzle adventure game.
dev journals | twitch stream | youtube archive (NSFW)

ClaytonW
Level: Smitemaster

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

Wow... I couldn't beat the first room...

Mister
Level: Master Delver
Rank Points: 104
Registered: 02-27-2003
IP: Logged

Maybe I should add a "carbon-based-life-form-friendly" first room

StuartK
Level: Smitemaster

Rank Points: 564
Registered: 06-10-2003
IP: Logged

Mister wrote:
Maybe I should add a "carbon-based-life-form-friendly" first room

There's some interesting rooms with 2 or (possibly) 3 mimics, and a longer time limit (or none) I've managed to do 2 mimics within the limit so far, and 3 and 4 mimics in about 60 turns, with only one or two missed trapdoors (so not very useful, heh) I think 3 or 4 without any time limit may be possible for a c-b-l-f...

bdcribbs
Level: Smiter
Rank Points: 390
Registered: 04-08-2003
IP: Logged

My computer's been chugging away for at least an hour and hasn't found any solutions. It's a pretty stupid algorithm though, it starts with all four mimics activated, then just tries random moves (starting over after every 30 moves).

StuartK
Level: Smitemaster

Rank Points: 564
Registered: 06-10-2003
IP: Logged

File: failed!.png (45 KB)
Downloaded 89 times.
License: Other
From: Unspecified

I think 3 or 4 without any time limit may be possible for a c-b-l-f...

Except that no time limit means the player could just do one or two mimics at a time...

How about a room with more than 4 mimics? Would that be impossible to design, and be solvable?


My best so far for the first room (in it's original configuration) is three areas complete, and one mimic blocked with 8 trapdoors missed in one area, at turn 65 (I've also had 7 misc. trapdoors, at turn 67, with all mimics in the centre) And of course, unless I specifically record one before starting (I've tried the room many times) there isn't a demo. What took up the time was, when starting, I end up with a mimic at the top, and 3 at the bottom, and some had to be moved in certain ways that left the others stationary (or I'd have more orphan trapdoors) Since there's only around 47 turns (from the first mimic placement) to clear 40 trapdoors (such that the last placed mimic has a maximum of 3 turns it can remain stationary through a turn) there's no such leaway.

Could you tell me if the solutions require that all the mimics end up moving around their individual areas in syncronisation with each other? That would greatly reduce the number of solutions that have to be tested, if only the first and last moves really 'count'

Anyway, I'm convinced this room can be completed without algorithmic aid. It's turning into a little obsession


...another attempt, 58 turns, 3 trapdoors missed, all mimics in the centre. I'm getting closer. Still no damned demo, I keep forgetting to record them :buh Screenshot attached, anyway.



[Edited by StuartK on 08-09-2003 at 04:54 PM GMT: smiley overdose]

[Edited by StuartK on 08-09-2003 at 04:55 PM GMT: messed up secret tags]

Mattcrampy
Level: Smitemaster

Rank Points: 2388
Registered: 05-29-2003
IP: Logged

If only I could remember my A*...

Anyway, I reckon I might be able to knock up a search tree easily enough. The pruning algorithm will be a lot more difficult, but I reckon it's in my limited capabilities.

Matt

____________________________
What do you call an elephant at the North Pole?

mrimer
Level: Legendary Smitemaster

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

Hmm...what situations would confirm it's now impossible to solve it? Possibly player/mimic position, # of trapdoors left...What others? The right cutoff point makes magic!

____________________________
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.

Schik
Level: Legendary Smitemaster

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

Situations that my program is checking against are:
- (obviously) Beethro needs to be able to make the move
- At least one mimic must move
- A mimic must not be surrounded by pits (unless ALL trapdoors in his area are gone)
- All trapdoors (per area) must be connected
- There can't be dead ends - i.e. a trapdoor that has only one trapdoor neighbor. (unless the mimic is ON that trapdoor)

I think that's all I'm checking against right now, other than # of turns. There are still countless possibilities, as my program seems to be discarding about 20K configurations a second, and has been running more than a day. I sure hope I don't have some logic bug that's causing it to skip over a solution.

____________________________
The greatness of a nation and its moral progress can be judged by the way it treats its animals.
--Mahatma Gandhi

Mister
Level: Master Delver
Rank Points: 104
Registered: 02-27-2003
IP: Logged

Wow, StuartK... I've never got that far playing by myself.

Schik, you are checking for the right stuff, seems like the algorithm I used to create the room. It was slow as hell (only having a 300Mhz [emergency] machine at that moment), and it improved DRASTICALLY just by adding a "not too many trapdoors left per area" check.

Some numbers: in most of the original rooms, the last trapdoor must be dropped with move 58 at most (in fact, it's impossible to do it before). Supposing you grab the upper-left potion first (a reasonable assumption), this would be done with move 11, so you have only 47 moves to drop 160 trapdoors with 4 mimics, the last one having only 44 moves at most to drop his share of 40 trapdoors.
You can only move in diagonals (unless you manage to reach the entrance), and supposing you have limitless space, the total universe of moves combinations available is equal to 4^47, about
250.000.000.000.000.000.000.000.000.000.

There are plenty of solutions. So many that I came up with the next rooms, that are just the same with extra restrictions (don't go there, go there, finish here).


EDIT: ok, some "training" rooms where added for those cblf stubborn enough to try beating the rooms by themselves. Also, included an easier way to record demos and made the last mother killable (for those purists that MUST kill everything ). Grab version 2 at the first post.


[Edited by Mister on 08-10-2003 at 10:59 AM]

StuartK
Level: Smitemaster

Rank Points: 564
Registered: 06-10-2003
IP: Logged

File: SV Mimic Quads 1S.demo (754 bytes)
Downloaded 69 times.
License: Other
From: Unspecified

I sure hope I don't have some logic bug that's causing it to skip over a solution.

Some random stuff about optimising and catering for all possible solutions



Cool puzzle. I'm not going to get the solution here, but I've enjoyed the process

Here's a 58 move demo with two trapdoors remaining. My best and final effort, given how much of a time-suck this has been. If I were an algorithm, I'd just keep plugging away, but humans have other things to do...

Mister
Level: Master Delver
Rank Points: 104
Registered: 02-27-2003
IP: Logged

Cool puzzle. I'm not going to get the solution here, but I've enjoyed the process

I have lots of similar ideas, and from now on, I'll always include a c.b.l.f "training" area so you can have some victory demos

By the way, the potions positions were not selected at random. It is the configuration with the shortest solution possible.

[Edited by Mister on 08-11-2003 at 07:25 AM]

Mister
Level: Master Delver
Rank Points: 104
Registered: 02-27-2003
IP: Logged

StuartK wrote:
How about a room with more than 4 mimics? Would that be impossible to design, and be solvable?

I'll work on that (along with more nasty ideas )

Could you tell me if the solutions require that all the mimics end up moving around their individual areas in syncronisation with each other?

I really don't know. I have archived all possible "unique" solutions (about 6000) but never tried all of them. I've seen some with two mimics sincronized, but no more.

Anyway, I'm convinced this room can be completed without algorithmic aid. It's turning into a little obsession

Try the last room. Your movements are VERY limited there so it should be easier. Also, its solution can be used to solve 1S and 2S too.

StuartK
Level: Smitemaster

Rank Points: 564
Registered: 06-10-2003
IP: Logged

I have archived all possible "unique" solutions (about 6000) but never tried all of them. I've seen some with two mimics sincronized, but no more.

A human being isn't, I think, going to see a solution that doesn't involve some kind of pattern (maybe stumble across something through blind luck)

I have also noticed that it's possible, if you have a mimic on the edge of it's area, one wall around clockwise from the previous, that they can both be moved efficiently (without either having to remain stationary for a turn) This might possibly have some use for the actual solution, if I were a programmer

Anyway, I'm convinced this room can be completed without algorithmic aid. It's turning into a little obsession

Try the last room. Your movements are VERY limited there so it should be easier. Also, its solution can be used to solve 1S and 2S too.

I did, but I didn't find it much help After a few turns, the number of possibilities is still exponential (instead of 4 move options, there's usually 2 or 3) It'd be a useful room to base a checking algorithm on, though, since there's a known solution

I've completed the cblf level though I completed the last room by the skin of my teeth (the first few rooms could be completed two mimics at a time, but then I was forced to use my imagination ) I won't attach a demo for it though...

Lucky Luc
Level: Smitemaster
Rank Points: 1215
Registered: 08-19-2012
IP: Logged

File: solutionmaybe.png (461.2 KB)
Downloaded 220 times.
License: Public Domain

Bump.



Not sure if you guys remember it, but a little while back, I told chat this might be fun to solve with DRODscript.

It wasn't.

(Well, it kinda was)

My algorithm was far from efficient, though. I didn't use any heuristic to order movement attempts (which would have probably made this a lot faster), which would've been more ugly to script, but probably still possible. Also, I missed some obvious loss conditions; and I must admit, I simply didn't think of including them (One would have been maybe 10 lines of script, the other a bit more, but concerning how long it took to run, it would've been worth it).

Still, I want to point out that I'm not sure how accurate the move counter is -- I failed to abort the cutscene after a valid solution was found, and I left my computer running on its own for a while. D'oh. The "real" value was however already above 10 millions, and I think the game calculated one move a frame, i. e. 60 moves per second, so you can figure out how long this took to finish.

EDIT: Also, I should probably note that I only searched for a single solution, so this doesn't even solve the hold

Bottom line: It is possible to brute-force things with DRODscript, but it's probably worth to put some more effort into your solving algorithm.

(By the way, ignore that last arrow. Sloppy scripting.)

---

[Last edited by Lucky Luc at 01-15-2017 05:57 PM]

Lucky Luc
Level: Smitemaster
Rank Points: 1215
Registered: 08-19-2012
IP: Logged

File: A DRODsolver in DRODscript.hold (3.5 KB)
Downloaded 43 times.
License: Public Domain

And here's the hold file, only altered by inserting a cut scene abort. Not recommended for playing, neither by carbon- nor silicon-based lifeforms.