Complexity, puzzle families, and the metagame

zed · 2013-06-08 10:05:14

jasonrohrer wrote:

The core problem is that the systems in Castle Doctrine are so general that people can build pretty much
anything with them. The puzzle space is clearly NP-complete (when generalized on NxN grids instead of
32x32).

I'm sure that's true in the abstract. But 32x32 seems to be small enough to
stop it being feasible to abuse it. I mean, with enough space I could
certainly imagine building a turing machine and requiring the player to press
switches to input an appropriate program, or with less space (but still much
more than 32x32) use similar tricks to make them find a discrete logarithm or
something.

But we certainly haven't seen anything like that, and with current limitations
I doubt that we will (I have my hat ready for eating). If someone actually
managed something like that, I would say they should be congratulated and then
some limit on (say) the number of relays should be added to make sure they
can't do it again.

In fact we've seen nothing that's even slightly complicated, abstractly, in
terms of circuitry. The hardest puzzles have involved pets - and none of it
has actually been theoretically hard, just detailed.

Perhaps it's worth thinking about what makes a puzzle interesting to solve.
Essentially, I would say: solving a puzzle is interesting precisely when it
requires surprising ideas. So the solution must involve some technique that
the solver hasn't seen before, or which it wasn't obvious would apply in this
case. Here we're using human notions of what counts as new and surprising - so
e.g. having to press a column of switches by moving up and down to maneouvre a
column of dogs over them can be interesting only once, even if the initial
conditions or other details of the setup change.

From the point of view of game design, we want to make sure that puzzles which
are hard for the population of solvers to solve are also interesting for them
to solve. So the situation we want to avoid is where there is a family of
puzzles which are identical from the human perspective, but where each one is
nonetheless hard for solvers who have seen the form before, but not solved
that particular incarnation. This is exactly what NP is getting at - although
since the size is bounded it isn't really a matter of complexity classes, just
actual complexity at the largest size you can fit in 32x32.

So we want that for any such family of puzzles, there is a method of solution
which isn't too hard for humans to find, and which doesn't take too much
calculation to apply to any particular instance. e.g. a dog column of the kind
described above is fine - once you've got used to the basic mechanics, it's
easy enough to solve any such puzzle. It's good and healthy that these kinds
of families of puzzles are possible - when they're first discovered, people
using them will have secure houses while the solvers learn to solve them, but
soon enough there'll be a large enough population who can solve them that they
won't be viable security anymore, and the puzzle setters will have to think of
something new.

So I'm not currently convinced that there's any real problem. In particular,
the solution to the "obfuscated magic dance" puzzles people complain about,
where you have to walk around in some bounded area near the entrance to
manipulate distant pets, is just to wait. Players will learn how to solve
those classes of puzzles, so setters will discover that they're not viable,
and will have to move on to something new.

jasonrohrer · 2013-06-08 11:23:01

Well, the problem here, Mr. Zed, is that the percentage of the human population who can even understand one word of what you and I are talking about here is minuscule. I suspect that the shrinkage of the player population is, in part, due to the fact that the game is veering in this direction.

Yes, I myself am rather interested in the discoveries of computer science. Reductions from 3SAT are pretty cool. Manually finding solutions for 3SAT instances, on the other hand, is not interesting to me.

And we've ended up talking about this game more and more as a puzzle game. But as I look back at my initial design notes, the word "puzzle" does not occur. This game turned into a puzzle game, despite my best design intentions.

If we think back to the early days of v5, back when we had 100s of active players.... wow, what a golden era that was! People weren't really designing or solving puzzles back then, because house design hadn't graduated up to that point yet.

No, I did not set out to design a game for computer scientists, nor did I set out to design a game that would produce hard or interesting puzzles (or even good puzzles, or puzzles at all).

I set out to make something that would feel like Rogue, moment-to-moment, but with "dungeons" that were designed by other players. Very few people would describe Rogue as a puzzle game, because of the tactical, moment-to-moment analysis and decision making that it requires. Furthermore, Rogue is full of hidden information (like what is coming next).

Puzzles, on the other hand, involve deep study of a complete system from the outside, and the discovery of very specific solutions.

I want a game where players can discover their own unique solutions to immediate sub-problems while in the thick of it.

jere · 2013-06-08 11:42:49

I set out to make something that would feel like Rogue, moment-to-moment, but with "dungeons" that were designed by other players.

Interesting. I've described it as a roguelike, but I figured it ended up being one by accident. Do you play modern roguelikes, Jason?

zed · 2013-06-08 12:13:33

Yes, I see.

If you want this game to be something other than a distributed laboratory for
maximally fiendish level design, then I agree the design needs a radical
overhaul.

In some ways this is a shame. This idea of a puzzle game with competitive
level design is one I've been dreaming of for years. In fact I was a bit
cheesed when I first learnt of this game, since I had finally started work
only a few months before on something remarkably similar - though a game
expressly intended as a puzzle game and nothing more.

Well, I'm still working intermittently on that game, and have used the lessons
I've learnt from studying this one to inform the design. So I don't mind so
much if Castle Doctrine takes a different direction. Whether my game will get
any players at all is another question... The genre "massively multiplayer
puzzle design and solution game" is certainly going to have very niche appeal,
but I think it ought to exist.

ukuko · 2013-06-08 16:00:29

zed wrote:

The genre "massively multiplayer
puzzle design and solution game" is certainly going to have very niche appeal,
but I think it ought to exist.

Do keep us informed.

ukuko · 2013-06-08 19:41:24

jasonrohrer wrote:

I set out to make something that would feel like Rogue, moment-to-moment, but with "dungeons" that were designed by other players.

Designing a dungeon for someone to enjoy solving is very different to designing a dungeon to keep someone out. As far as I can tell the goal right now for most players is to protect their stuff for long enough to ascend the ranks and then stay there for as long as possible.

I can imagine turning it into more of a dungeon design game by removing the 'protect what's yours' notion from house design:

You design a house and you rent it out. So each house has a family, but it's not yours. Folks can rob your house(s) to get loot. The amount of loot dwindles with each robbery. But you don't lose anything when they rob you. You can watch back the tapes and see an NPC family get theirs, and perhaps feel guilty for not protecting them. If your house doesn't have a great track record (fails vs robs) then maybe the next time you rent it out you'll get a poorer family in there with less money for others to rob.

Instead of a wage, say you earn a small amount for every robbery that fails in your house. If the robber dies you get their cash, or a percentage of. Robbers could rate your house based on how fun/satisfying/hard it is. If your house is horrid, nobody is going to play it. In the version of the game the emphasis would be on making something that people wanted to play, even if it was still tricky to solve.

If you earn a bunch of money, well, why not invest in another house and rent that out too?

I guess this would give the home security industry a nasty sideline in home invasion, but hey!

dalleck · 2013-06-08 21:20:36

jasonrohrer wrote:

I set out to make something that would feel like Rogue, moment-to-moment, but with "dungeons" that were designed by other players. Very few people would describe Rogue as a puzzle game, because of the tactical, moment-to-moment analysis and decision making that it requires. Furthermore, Rogue is full of hidden information (like what is coming next).
Puzzles, on the other hand, involve deep study of a complete system from the outside, and the discovery of very specific solutions.
I want a game where players can discover their own unique solutions to immediate sub-problems while in the thick of it.

It is important to understand what makes rogue what it is, and one of the keys is the computer-generated levels. If you had a player design each level for you then you could have a real headache to play through, especially if wiring and switches were at their disposal!

Here are some suggestions to help create that sense of 'randomness':

1. One issue I see with creating levels in TCD is that creator must solve it without tools. This limits the design possibilities exponentially. If you have a set of tools you could take along when you self tested, then all sorts of things would be possible when creating a trap.

2. What if at the beginning a house owner is handed an assortment of pieces, say 10 wires, 1 power supply, 40 wooden walls, 10 steel and so on, and the creator then must make a house out of this. Then when folks die in their houses they get given more random pieces to add to their house.

3. What if there were 'categories' for houses, whereby you are limited to certain pieces. The 'dog house' where you get wooden walls, pitbulls and doors. The 'switch house' where you get cats, chihuahuas 1 power supply, electric doors and floors. The 'floor of death' house, where you are given electric floors, trapdoors, cats and chihahas, etc. The rob list could show what type of house it is, and you could rob houses based on your preference.

4. Randomly generate a house for the player at the start of their life. Then, with whatever money they have they can modify it.

Whatever the case, I can see from the comments here there is a strong need to reassess the current direction of the game.

Last edited by dalleck (2013-06-08 21:21:34)

Laffinty · 2013-06-10 10:11:01

dalleck wrote:

1. One issue I see with creating levels in TCD is that creator must solve it without tools. This limits the design possibilities exponentially. If you have a set of tools you could take along when you self tested, then all sorts of things would be possible when creating a trap.

This has 2 Issues for me:
1) It is realistic because you wouldn't want to disassemble walls of your house to get to your family/vault, right?
2) It is unrealistic because if you have pitbulls you'd not expect them to bite you.

Last edited by Laffinty (2013-06-10 10:11:17)

jearr · 2013-06-10 12:30:47

ukuko wrote:

Designing a dungeon for someone to enjoy solving is very different to designing a dungeon to keep someone out.

There is little incentive to make your house fun to explore (even less with blueprints) when being robbed is so disastrous.

Suggestion: each successful robbery gives you a smaller percentage of the vault loot rather than half or all.

Suggestion: a limit on the number of times you can rob a house per day (or until the owner returns).

The goal of my suggestions is to make being robbed somewhat less disastrous, while also making it harder to be griefed. I would hope this might encourage house-builders to be more fun (particularly if blueprints are restricted).

jasonrohrer · 2013-06-10 13:12:25

Laffinty wrote:

1) It is realistic because you wouldn't want to disassemble walls of your house to get to your family/vault, right?
2) It is unrealistic because if you have pitbulls you'd not expect them to bite you.

Oh, you never expect that.... but then the damn things bite you! (Not just in the game, but in real life.)

jere wrote:

Interesting. I've described it as a roguelike, but I figured it ended up being one by accident. Do you play modern roguelikes, Jason?

In terms of turn-based ones, only a few (like The Crypts of Despair, Zaga33, and James Lantz's Mercury). But also the non-turn-based Roguelike-likes (Spelunky, Shoot First, The Binding of Isaac). They've been hugely inspiring to me.... there are also things that have a similar feel (Far Cry 2, Demon's Souls). My last game, Inside a Star-filled Sky, was like a Roguelike without permadeath.

ukuko wrote:

Designing a dungeon for someone to enjoy solving is very different to designing a dungeon to keep someone out.

Let me clarify: I never intended for players to intentionally design fun, interesting levels. Obviously, they are going to design levels where their goal is to KEEP YOU OUT AT ALL COSTS. That is natural. The kernel of this game design was that idea. What if player-generated-content had an explicit purpose?

From the point of view of the robbers, this game is like Rogue, but where the dungeons are design by other players who are trying to keep you out.

From the point of view of the house owners, this game is like Tower Defense, where the other players are the creeps.

Mesh these two gears together, and you should get a working system, assuming that it's balanced.

The problem is still imbalance. House owners have a fundamental advantage over robbers, because they can design puzzles that are unsolvable in practice. No tweaking of prices can ever correct that fundamental issue. Blueprints were an attempt to correct it, but they didn't solve the fundamental problem (unsolvable puzzles still possible) while throwing a bunch of other good stuff under the bus (tactical play in non-puzzle houses).

zed · 2013-06-10 14:00:08

jasonrohrer wrote:

The problem is still imbalance. House owners have a fundamental advantage over robbers, because they can design puzzles that are unsolvable in practice.

I still don't see that that's been demonstrated. Maybe it's possible, but I don't currently see how.

jasonrohrer · 2013-06-10 14:13:27

Well, when they're unsolvable for Me, I guess that counts as "unsolvable in practice"!

I think it's pretty clear that a 3SAT instance with N clauses and K variables can be encoded in a house map of size NxNxKxKxM (where M is a suitably-large constant) in such a way that a path to the vault involves assigning True/False values to the variables so that the corresponding 3SAT statement true.

On a 30x30 map, obviously what can be encoded is limited, but I've seen some pretty hairy nests of wires and gates that require a heck of a lot of finger-tracing and mental stack space to make any headway with. Even if we can't encode anything but tiny 3SAT instances in the 30x30 maps, what is possible still has that "think through all possible solutions" feel that is the hallmark of NP-hard stuff.

Laffinty · 2013-06-10 14:59:00

zed wrote:

jasonrohrer wrote:
The problem is still imbalance. House owners have a fundamental advantage over robbers, because they can design puzzles that are unsolvable in practice.
I still don't see that that's been demonstrated. Maybe it's possible, but I don't currently see how.

Chihuahas, Cats and Pressure plates

only you walk in a very specific pattern, you have no chance to get the vault

technically not "unsolvable" but who sits down and tries to figure ou thow to walk to guide 4 chihuahas and 2 cats over the exact spots they need to be? XD

bey bey · 2013-06-11 08:55:33

I still feel that a lot could be done by making, say, ladders useable on frying floors (on or off) and on trapdoors (on or off). This would at least limit the feasibility of magic dances to a certain degree, or move them away from being so incredibly cheap for the level of security they present. It's strange having something that cannot be beaten in the game, since the tools present an additional check for the complexity of complicated electrics - often enough, a simple cut will render complicated things useless. (Anyways, electric floors should cost the same as trapdoors.)

I find myself leaning more and more on the "animals move on sight" suggestion, it's probably the only way forward. All this would mean is that tricky dances would require windows and thus be a lot easier to figure out without replicating (which is what anyone will do to solve them...). And, beautifully enough, this would also mean that houses with dog switches would have to allow for walking around in.

ukuko · 2013-06-11 09:42:10

Jason mentioned in this post that this will be addressed like so:

jasonroher wrote:

Electric floor-based "step on it and die" traps, as you point out, would need a separate fix. Wire cutters will disable "off" electric floors. I shouldn't have left that loophole in place for so long.

As for ladders on both on and off trapdoors.. you can already do that!

zed · 2013-06-11 10:22:55

bey bey wrote:

I find myself leaning more and more on the "animals move on sight" suggestion, it's probably the only way forward. All this would mean is that tricky dances would require windows and thus be a lot easier to figure out without replicating (which is what anyone will do to solve them...). And, beautifully enough, this would also mean that houses with dog switches would have to allow for walking around in.

Seconded. Herding pets you can't even see isn't much fun.

However this would only lead to further painful calculations if vision is
based on the details of when the game decides to scroll the window. It would
have to be changed to scroll with every step, keeping the robber at the
centre.

bey bey · 2013-06-11 12:06:56

ukuko wrote:

Jason mentioned in this post that this will be addressed like so:
jasonroher wrote:
Electric floor-based "step on it and die" traps, as you point out, would need a separate fix. Wire cutters will disable "off" electric floors. I shouldn't have left that loophole in place for so long.
As for ladders on both on and off trapdoors.. you can already do that!

Woopsiedaisies. Thanks! I'm wondering, though, if this actually changes the problem, since I can simply put a magic dance in place that provides power for a nine-deep-trapdoor chain or something similar. It would need a non-destructive way to pass as is with trapdoors to be honestly effective. Hence the ladder.

bey bey · 2013-06-11 12:08:01

zed wrote:

bey bey wrote:
I find myself leaning more and more on the "animals move on sight" suggestion, it's probably the only way forward. All this would mean is that tricky dances would require windows and thus be a lot easier to figure out without replicating (which is what anyone will do to solve them...). And, beautifully enough, this would also mean that houses with dog switches would have to allow for walking around in.
Seconded. Herding pets you can't even see isn't much fun.
However this would only lead to further painful calculations if vision is
based on the details of when the game decides to scroll the window. It would
have to be changed to scroll with every step, keeping the robber at the
centre.

Second - the current view system is fun but it could be sacrificed towards better gameplay...

largestherb · 2013-06-11 14:24:33

vision centred on the player constantly gives a bit of a 'jerky disorientating' feel to me usually, but i'd be willing to see how it goes!

the houses that right now that are just single lines of dance-grid defence would be done away with the wire cutter change. you could still have dance-grids that CAN'T be cut, ie: grid routes power to some vital trapdoors later, but it would help in taking away a fair chunk of 'wiring real estate,' which would naturally limit complexity.. i think.

at any rate, i'd like to see the 'wire cutters can cut un-powered grids' change BEFORE any kind of change to backpack limitations or tools with multiple uses. maybe it can be quickly thrown in as v8.5 and see how it steers house design for a week or two?
we definitely have some brilliant house builders who are settling for these super complex dancing / animal herding single-row grid defence systems. would be nice to see what they can come up with against the current 8 tool limit!

herding animals you can't see directly is definitely not that fun as a robber. i personally find taking the blueprints into mspaint and drawing all over them to solve the puzzle (or at least try to!) to be quite fun, but i can definitely understand how grabbing a bunch of screenshots / searching a log for a string of code and using third party software to doodle all over it might not be everyone's idea of fun.

i guess pouring over blueprints is a bit more casino heist than opportunity burglary..

jasonrohrer · 2013-06-11 14:36:40

Using wire cutters on "off" electric floors doesn't help if someone builds doors and walls that are 9-thick. That still leaves 20x30 space on the other side for wiring and moving animals.

Even if you ax the animals completely (or implement them only moving if they can see you), that 20x30 space could still have a hairy nest of wires that lead to 15 or so buttons that the robber needs to press in the right order and exactly the right way. I.e., my argument about NP-Hard houses and 3SAT encodings has nothing to do with moving animals or magic dances.

zed · 2013-06-11 15:02:28

jasonrohrer wrote:

Even if you ax the animals completely (or implement them only moving if they can see you), that 20x30 space could still have a hairy nest of wires that lead to 15 or so buttons that the robber needs to press in the right order and exactly the right way. I.e., my argument about NP-Hard houses and 3SAT encodings has nothing to do with moving animals or magic dances.

It's drastic, but a hard cap on the number of relays allowed in a house would deal with that. I'd say something like 20-30, to leave room for plenty of electricity-using puzzles.

The Castle Doctrine Forums

#1 2013-06-08 10:05:14

Complexity, puzzle families, and the metagame

#2 2013-06-08 11:23:01

Re: Complexity, puzzle families, and the metagame

#3 2013-06-08 11:42:49

Re: Complexity, puzzle families, and the metagame

#4 2013-06-08 12:13:33

Re: Complexity, puzzle families, and the metagame

#5 2013-06-08 16:00:29

Re: Complexity, puzzle families, and the metagame

#6 2013-06-08 19:41:24

Re: Complexity, puzzle families, and the metagame

#7 2013-06-08 21:20:36

Re: Complexity, puzzle families, and the metagame

#8 2013-06-10 10:11:01

Re: Complexity, puzzle families, and the metagame

#9 2013-06-10 12:30:47

Re: Complexity, puzzle families, and the metagame

#10 2013-06-10 13:12:25

Re: Complexity, puzzle families, and the metagame

#11 2013-06-10 14:00:08

Re: Complexity, puzzle families, and the metagame

#12 2013-06-10 14:13:27

Re: Complexity, puzzle families, and the metagame

#13 2013-06-10 14:59:00

Re: Complexity, puzzle families, and the metagame

#14 2013-06-11 08:55:33

Re: Complexity, puzzle families, and the metagame

#15 2013-06-11 09:42:10

Re: Complexity, puzzle families, and the metagame

#16 2013-06-11 10:22:55

Re: Complexity, puzzle families, and the metagame

#17 2013-06-11 12:06:56

Re: Complexity, puzzle families, and the metagame

#18 2013-06-11 12:08:01

Re: Complexity, puzzle families, and the metagame

#19 2013-06-11 14:24:33

Re: Complexity, puzzle families, and the metagame

#20 2013-06-11 14:36:40

Re: Complexity, puzzle families, and the metagame

#21 2013-06-11 15:02:28

Re: Complexity, puzzle families, and the metagame

Board footer