Designing Difficulty

[requerent]

I'd like to contribute to the discussion itself of making procedurally generated content that can get you both high solvability and high complexity (thus establishing a "truly difficult" puzzle), but that sounds like a really hard thing to create even by hand. Or maybe you're just looking into ways of creating PCG that can be tweaked according to these parameters in order to change the difficulty curve?

Yep! If we can set parameters for solvability and complexity within certain probabilistic ranges, we can ensure a degree of challenge that we want. If a player in a RL scrapes by, with unlucky drops, to an arbitrary depth where Dragons may appear, but no Dragon appropriate gear has been generated, then we've boned the player in an uninteresting way. They've worked very hard to have to willingly throw themselves into the belly of a Dragon. This isn't tactically or strategically interesting. Simply avoiding it also isn't inherently interesting. Having to perform a set of varying actions to avoid it, however, is. If the level was generated with, say, a faulty column that could be struck to cause the Dragon to fall through a pit or to be crushed/weakened/stunned by falling rocks- that may be interesting and complicated if several things need to happen first.

Brogue creates these sort of dependency tree situations with it's key puzzles. A level with a key stuck behind lava will typically have a potion of fire immunity or levitation.

A lot of roguelikes, particularly older ones, like to use vast worlds and subtle gameplay structures in order to increase complexity for players who don't understand the game mechanics. This, in itself, does change the difficulty of the game to a point, but from the point of view of a player who can see everything in front of them, it's probably a lot simpler of a game. Honestly I'd say Krice nailed it, at least in terms of what we think of as a traditional roguelike. That said, designing something that really expects player creativity rather than prediction would make for an awesome game, roguelike or otherwise.

That's the idea. I find myself automatically defaulting to, "What do I need to do to prepare for this area that my character knows nothing about but that I, as a player, have experienced before?" ToME can get pretty bad about this.

[Z]

This definition is very sensitive to meaningless decisions.

For example, if we add a question about the end of game "What do you use the Amulet of Yendor for? (a) eternal life, (b) infinite wealth, (c) love, (d) knowledge, (e) death" then solvability a:b suddenly becomes 4a:b+a (assuming that "death" is a losing option). With 20 questions it becomes, say, 1000000a:b. This example is silly, but in fact there are lots of meaningless decisions during the game. A typical 2x10 room can be traversed in 1024 ways. You can use a fire spell or an ice spell, but against most monsters it is irrelevant which one you use (while against some it is relevant). And if there are 40 monsters, we get 2^40 meaningless choices.

Also you always have these obviously bad decisions. You can always lose by pressing 'Q' to quit the game, or use another method of suicide (typical for the given game). When fighting monsters you can just wait until you are killed by them, instead of fighting back (the game will be probably still solvable while you are doing it, but it will be much harder). All of these seem to greatly reduce your solvability, but they have no relevance to actual gameplay.

But let's try it in an actual game, and see if we get a reasonable result.

Suppose we are playing Chess against an extremely bad player (we assume that this player is deterministic to avoid considering their decisions in our solvability formula). Still, this player knows the very basic (that it is good for him to capture our pieces, but maybe he does not know that it is important to defend his own, etc), so, when playing randomly, we are almost sure to lose. But still, we can probably win in most situations by playing well again, unless we really spoiled it. Winning the game of Chess requires a checkmate, while any reasonable person could checkmate the opponent's king using two rooks, it requires a quite specific sequence of moves, and when playing randomly, it is much more likely that the opponent captures our two rooks, or that one of the draw rules of Chess kicks in. All this means that your solvability would be extremely low in this game. But we were still playing against an extremely bad player. Only a basic understanding of the game is sufficient to win without effort. I suppose the same would happen for an easy roguelike.

On the other hand, the game "I take 20 red or black cards, and you have to guess their colors correctly" has a solvability of 1:20, which is much higher than Chess/Roguelike despite that intuitively it is obviously far from solvable. Note that this solvability would not change if I have shown you the cards.

[requerent]

This definition is very sensitive to meaningless decisions.

That's kind of obvious.

The definition isn't complete or necessarily useful yet, but that doesn't have much bearing on the validity or value of the idea or potential. If I make a slight correction and say, "The tree of all salient game states." Then We already have a huge optimization.

Salient game states would simply be those that are... salient >_>. Completely solvable and unsolvable subtrees can be pruned. If all of a node's children are completely solvable, then this portion of the subtree is absolutely arbitrary. We can further evaluate salience relative to actions that the designer feels are more important- getting rid of obviously bad decisions. If we think of this in terms of heuristics, we may only be interested in the top N moves that are possible from a given state. Salience may be something we want to evaluate in a way that is similar but different from heuristics. For example- if an Ice spell or Fire spell have nearly equivalent outcomes (or similar heuristic costs), one could be pruned on grounds of equivalency.

This would actually make the game more complex, because we aren't considering highly equivalent actions as a contributing factor to variance when it comes to content generation. If we're in the land of 'Fire and Ice does the same thing,' we don't want to think of them as separate actions when generating complexity. This is just a side-benefit to applying salience.

Finally, we don't need the whole tree to have a useful model of solvability, we just need some samples of the hardest and easiest paths. If we're generating a room trying to satisfy a range of solvability, we might evaluate (adjust difficulty based on) the worst possible salient state (IE, player is surrounded) of a partially generated room.

Solvability also relies on Complexity for a game to be interesting. Complexity would regulate mundane repetitions and symmetrical paths during generation. Disregarding complexity for now- in a word, 'Salience' is a reasonable answer to the problem of meaninglessness.

Solvability will likely have a feature set of values (such as, at about what depth in the tree do terminal fail-states begin to appear?) that allow a designer to address difficulty in a way that isn't arbitrary.

On the other hand, the game "I take 20 red or black cards, and you have to guess their colors correctly" has a solvability of 1:20, which is much higher than Chess/Roguelike despite that intuitively it is obviously far from solvable. Note that this solvability would not change if I have shown you the cards.

Solvability isn't very useful when applied to coin tosses, but if we know what the cards are, then unoptimized solvability is sufficient to represent the entire tree. If we apply salience, solvability should become something like 1/2.

Solvability describes how solvable a game is relative to the range of decisions that can be made. Red-black is a much simpler game than Chess/Rogue, but it only has one solution. Chess is much more convoluted complex, but I think your chess example misses the mark. We don't care if players are making intelligent decisions,  player decisions throughout a challenge do NOT effect solvability! It is a measurable property of a decision tree or of a sub-tree (but we're only interested in the initial state- how solvable is a problem when the player encounters it? Or- how solvable is the problem when we generate it?). Calculate all possible board states and decision paths of chess, what is the ratio between Win and loss or draw? We obviously can't do that- but we're not trying to. We're trying to generate a challenge that probably satisfies solvability constraints.

Now- the outcome ratio of chess may not be better than red/black, but with salience it definitely would be.



BTW- Hydra Slayer is AWESOME. Is there a particular place for discussing it?

[Z]

We don't care if players are making intelligent decisions,  player decisions throughout a challenge do NOT effect solvability!

Salient game states would simply be those that are... salient >_>.

I think these two are in fact related, since salient decisions would be those which can be taken (or maybe considered) by players making intelligent decisions. Otherwise any complex game would have a very low and irrelevant solvability (as my chess example shows).

Also, I think some way of probabilistic calculation makes more sense than simply counting the paths. Otherwise you would have to calculate paths which occur in very rare situations on the same level as paths which occur frequently. This also automatically prunes meaningless decisions (like my fire/ice example).

Combining the two, we get that solvabilty would be the probability that a player wins the game (except that now this is no longer a perfect player, simply an intelligent one).

In fact I think we could try to create an AI (or a bunch of AIs of different skill levels) and see how many of them pass the challenge. I think this would make sense as a way to automatically make sure that the game is solvable. But this would be also a lot of work for most good roguelikes.

This reminds me of a tiny roguelike called 'Get Out'.  In this game the number of possible states was so low that a skilled programmer could easily verify whether the game is solvable, and probably also somehow estimate how difficult the challenge is, using something similar to your ideas. Unfortunately it was done by an unexperienced programmer, so it just generated random levels without ensuring solvability. Could be a nice testing ground.

This would actually make the game more complex, because we aren't considering highly equivalent actions as a contributing factor to variance when it comes to content generation. If we're in the land of 'Fire and Ice does the same thing,' we don't want to think of them as separate actions when generating complexity. This is just a side-benefit to applying salience.

But we should also apply this to your previous example that there are many paths when killing goblins, but not so many when killing dragons.

Calculate all possible board states and decision paths of chess, what is the ratio between Win and loss or draw? We obviously can't do that- but we're not trying to.

It should be possible to calculate this in very simple situations (like king vs king + 2 rooks and some simplifications of the draw rules).

BTW- Hydra Slayer is AWESOME. Is there a particular place for discussing it?

Thanks! So far the most discussion happened in the announcement thread and I think this is the best place. (The discussion on the New Attnam forums also could be helpful, but I think you need to be registered to get there.)

[Ancient]

@Ancient

Emergent Gameplay, as far as I am familiar with the concept, has less to do with any given challenge and more to do with how many options a player has. A player can engage in emergent gameplay to solve more difficult problems, but they don't have to be more difficult. Emergent gameplay can be implemented 'for' fun- such as in Dwarf Fortress, where lava traps and other bizarre contraptions are entirely unnecessary but completely emergent.

So emergence counts only on the player side? I thought it also applies when several rules interacting with each other creating something that was not explicitly designed fits in. There are no bosses for usual dungeon level. But that unique that happened to be generated with attack wand suddenly poses a challenge difficult enough to name that monster a boss despite it is not one in strict terms.

I'm not sure if what you're describing is really emergent gameplay. These examples are challenges that may or may not require emergent gameplay, but they don't necessarily have anything to do with emergent gameplay. 4 is the closest, but that isn't increased complexity because evasion is a repetitive action.

Okay, I definitely misunderstood something. When that centaur pops up in crawl at dungeon level three you have to constantly obscure its line of sight to you until it comes close enough you can try meleeing it. Why do you consider closing doors, reading scrolls of fog and casting stinking could to be repeatable actions? Doors can be closed only once (unless you open them but this exposes you to centaur's arrows), scrolls and mana points are finite. If you can simply walk away from a monster it is no threat worthy of discussion.

There is also nothing inherently emergent about evasion.

Note I did not claim that. I view unintended creation of such boss as emergent, not how you deal with it although there emergence may apply to that. Admittedly example 3 has absolutely nothing to do with emergence because it is a single explicit rule.

[requerent]

So emergence counts only on the player side? I thought it also applies when several rules interacting with each other creating something that was not explicitly designed fits in. There are no bosses for usual dungeon level. But that unique that happened to be generated with attack wand suddenly poses a challenge difficult enough to name that monster a boss despite it is not one in strict terms.

I don't think that is emergent gameplay. We could call it an emergent challenge- but I think the meaning is different.

The PCGenerator operates under a specific set of rules. When it produces a random set of values that liberally applies these rules, we may get a monster that violates existing patterns. The generation rules allow for the emergence of challenges that the game is not designed for.

However, emergent gameplay describes how the player is allowed to solve problems. If we generate an emergent challenge but there is no emergent solution, how does this challenge effect gameplay? The player does the same old same old- s/he may have two different approaches for fighting "Critters" and "Elites," but a unique may or may not demand emergent gameplay. The game literally may not have to be played differently to solve the emergent challenge.

-----

Kind of like arbitrarily titling a piece of incromphensible modern art. Say we have some meaningless drivel of paint splatter- when people look at it that is what they see. However, if we are to arbitrarily name the piece "The plight of Sudan," or "The romance of Joann," or "Death of a Moniker," the audience will try and marry the current image to some meaning contained in the title.

Artist makes an abstract painting without a title or meaning in mind. After the fact, he gives it a title- possibly randomly generated. After a title is slapped on it, new meaning emerges. We suddenly see the flag of sudan trodden under by flashes of red, or curving lines that copulate into coalescing forms, or the visage of visagelessness falling into darkness. These observations into what the meaning of the piece may be are emergent.  However, if a person does not know anything about the Sudan, romance, or what a monker is, then a related interpretation isn't going to emerge! They may think of something else, but it may be irrelevant- or they may default to a "Paint is pretty" interpretation... or "modern art sucks."

The painting represents the monster. The emergent challenge.
The title represents a potentially emergent solution that is associated with that monster.
The interpretation is whether or not a player is ABLE to execute that solution.

An emergent challenge may or may not result in emergent gameplay. The two aren't necessarily dependent upon one another.

[Ancient]

That settles the matter. I assumed your question to Jo dealt with emergence in general because you asked in what way that would be emergent.

By the way, my last modification to previous message did not register at posting time so I fixed it now.

[requerent]

That settles the matter. I assumed your question to Jo dealt with emergence in general because you asked in what way that would be emergent.

By the way, my last modification to previous message did not register at posting time so I fixed it now.

Oops  . I may have misread- I thought Jo was talking specifically about emergent gameplay. So, asking "in what way is that emergent?" I meant in regards to how I thought it was used originally.

I don't know how much emergent challenges make the game interesting if there isn't also emergent gameplay. The goal or spirit of 'emergence' has more to do with making the gameplay interesting. If emergent challenges don't accomplish that, then I don't know if the game itself satisfies the design goal of being emergent.

This is just me reading into things though.

---

Centaur example is totally emergent.

Evasion may or may not play a role in emergence- just an open statement.

[requerent]

The formal representation of solvability may include only unique and salient game states. Salience, however, is subject to design, so the model is as useful as it can be implemented.

I think these two are in fact related, since salient decisions would be those which can be taken (or maybe considered) by players making intelligent decisions. Otherwise any complex game would have a very low and irrelevant solvability (as my chess example shows).

Hmm... It doesn't have to do with player intelligence because the solvability is generated into the challenge. The player's actual intelligence is not factored into generation (though I don't think this is what you're saying). We don't care what actions the player is making or will make, we just want to be certain that there exists a desirable amount of decision paths that the player can take to solve the challenge. Moves of a low heuristic (dumb moves) value are not salient because we assume they are failed paths. The player's decisions don't really have anything to do with quantifying how solvability effects the challenge. Solvability should try to include some unintelligent decisions after all.

Now, if we are using heuristic pruning of some kind to simplify the problem of solvability, then we need a measure of what moves are important and what moves are not. I'm not sure if this is the player's intelligence- the player doesn't have anything to do with how the challenge is generated.

Also, I think some way of probabilistic calculation makes more sense than simply counting the paths. Otherwise you would have to calculate paths which occur in very rare situations on the same level as paths which occur frequently. This also automatically prunes meaningless decisions (like my fire/ice example).

I think I've been wrong in thinking about solvability as a tree (which could work). It should be a directed graph.

If that were the case, we could generate solutions as salient actions from the goal state with some branching factors and desired depth until we decide to converge on the initial state. If this is the case, we can explicitly generate the paths with only salient events. Any divergence from these paths may or may not result in failure (which is a problem). The greater the branching factor from the goal state on, the more solvable it is. That is- solvability describes the breadth of solutions. Complexity, then, is how many required steps from the goal state to the initial state there are- or the depth and variety of actions. Excuse the redundancy, I'm still thinking this through.

Hmm-- Suppose a Hydra is generated that the player can't solve with current equipment. We could also generate a single weapon that makes the hydra solvable in some amount of steps... or a whole slew of weapons and items that all need to be used within a particular order to solve the Hydra. Even a two-headed hydra can be turned into an incredibly complex problem pending on what weapons and tools are available. Runes can be used to auto-solve these problems or jump between salient events, but if we were to exclude them when deciding which hydras and weapons to generate, we can generate challenges whose difficulty is very measurable.

Combining the two, we get that solvabilty would be the probability that a player wins the game (except that now this is no longer a perfect player, simply an intelligent one).

I'm reluctant to use probability to describe whether or not a player wins a game, but I think we can set the probability based upon how we address solvability. If we're analyzing a game's solvability... then yes, the digested information we get is the probability. It's probably more important to look at distinct challenges, though, instead of the entire game.

This would actually make the game more complex, because we aren't considering highly equivalent actions as a contributing factor to variance when it comes to content generation. If we're in the land of 'Fire and Ice does the same thing,' we don't want to think of them as separate actions when generating complexity. This is just a side-benefit to applying salience.

But we should also apply this to your previous example that there are many paths when killing goblins, but not so many when killing dragons.

I think it still works out- if salience only cares about the highest heuristic valued moves, goblins will be more solvable because more of those moves are likely to have solution paths than in the case with the Dragon- unless, of course, that's not how the game is designed.

Calculate all possible board states and decision paths of chess, what is the ratio between Win and loss or draw? We obviously can't do that- but we're not trying to.

It should be possible to calculate this in very simple situations (like king vs king + 2 rooks and some simplifications of the draw rules).

Yea- I just mean we can't generate the entire game state tree of chess. It's one of those end of the universe problems. Of course, solvability as a model might hypothetically care about all of that, we just have to implement it in a salient way for it to matter. For really good players, chess doesn't really begin until after the 20th move or so- both players have the same amount of knowledge of the game from the initial state, they can silently agree on how the game will progress (because the best first 20 moves or so has more or less been solved). I kind of hate chess for that. Knowledge becomes more important than a person's ability to solve problems.



I'm really just trying to rationalize the most complete and useful way to regulate difficulty in a game so that it remains meaningful and challenging. Solvability and complexity, and their sub-properties, in terms of some organization of actions seems to be close- but there are a lot of gaps that need to be worked out.

[Krice]

I'm really just trying to rationalize the most complete and useful way to regulate difficulty in a game

Roguelikes are often complex and may surprise even the developer which is a good thing. Trying to create some kind of deterministic rules may lead to poor gameplay, because players can then determine everything before they get into trouble. Then again, it may be something intended, like the exact science of D&D system which makes some people work like a calculator.

[Darren Grey]

I think even with deterministic rules the game can surprise the developer.  Players outsmart devs all the time    Besides the cmoplaint is more against things like random battle mechanics, which lead to life and death in the game falling under the whim of the RNG.  Procedural content in terms of world creation and monster behaviour is still important.

A big issue with random battle mechanics is that you have to balance to balance the game around getting runs of bad rolls, as this is bound to happen in any game.  As such the game must be easier than it would be with a deterministic system, which can be boring if you keep getting good or average rolls.

[guest509]

  In games dominated by the RNG a deterministic combat system does not make the game deterministic overall. But it many circumstances it can give some much needed predictability.

-Jo

[Darren Grey]

There has to be a balance between predictability and the unexpected.  Predictability means knowing that the goblin in front of you will die in one hit, but the orc takes two.  The unexpected means not knowing how the goblin will act, or what's behind the corner that could come traipsing round whilst you're tackling the orc, or what the unided potion in your inventory does if you choose to use it.  A mixture of the predictability and the unexpected means being able to plan ahead a few turns, with the caveat that things may not go as you expected.  Too much predictability and it becomes a set puzzle, which is boring since you solve it at the start and then just go through the steps.  Too much unexpected and it loses tactical depth since you can't plan appropriately.  If you can't plan properly then the game doesn't reward you for thinking, and so is boring.

Chess is always the best comparison in my mind.  You know the immediate result of your move, and you can guess how your opponent will react, and so you can plan ahead a few turns.  But it's not fully predictable and your tactics have to change and evolve as you play.  The game rewards thought, and because it keeps changing you have to think every turn.  It is never ever boring.

[guest509]

  Good points all. I had a system in mind where your heavy weapon is more random and risky whereas the more mundane normal attack is reliable. Think fireball spell and dagger attack.

  I think the example was of ToME being too random. I didn't catch that but I'm sure there are good examples out there.

[guest509]

I dunno if this adds anything.  Bobby Fischer created this chess variant that eliminates openings. Maybe you'll like it better.
http://en.wikipedia.org/wiki/Chess960