Designing Difficulty

[requerent]

Hola Roguelike likers!

I'm working on a thesis that has a little bit to do with procedural content generation and wanted to spark up some discussions to share some opinions and get some impressions. Most of the concepts I'm interested in have more to do with roguelikes than anything else, so I thought I'd start here. I'm not too sure how active this place is- but I hope that it serves as the general hub for RL development discussion that I'm assuming it does. If anyone has any suggestions as to where a better place may be, please comment!


Divorcing particular topics from the context of my entire project is a tad tedious, so hopefully I can do that without producing large blocks of text (not likely). To start, I'm interested in creating some vocabulary with which to establish a more appropriate paradigm for looking at particularly important concepts in the design of a game. I'd like to begin with defining what it is in a game that makes them difficult. By difficult I mean simply that the incremental challenge of the game is pleasurably stimulating and keeps those addictive juices flowing in the brain.


There are two basic concepts that I'm rolling around, complexity and solvability-

The first is solvability. How solvable is any given game? Upon entering a room, we can abstractly look at the 'problem' of the room in terms of an unoptimized minimax tree. The player is obviously the maximizer while the 'room' (and challenges therein) becomes the minimizer.

Within this tree of potential game states, how many terminal nodes result in a victory for the player? Or rather, How many are solutions? The more paths that result in a victory condition, the more solvable the room is (room is an arbitrary measure of scope- we can think of the entire game's solvability based upon the solvability of each region, of each level, of each room, of each monster, etc). In all games, the solvability of a game tends to decrease as the player progresses. This quality of a game, however, is only interesting if combat doesn't heavily rely on probability (Dying after a stun with 99% Stun resist in ToME is NOT fun OR interesting).

Solvability is typically addressed with an overly dependent relationship between designer and play-tester. If we can design procedurally generated content so that its solvability is within a desired margin of probability, it's possible to make difficulty less arbitrary and more procedural. This is interesting because the game world itself becomes an intelligent opponent providing us with a measurable degree of challenge. Solvability also includes stalemates (which are equivalent to NOT losing)- bypassing a room or running away.


The second concept is complexity. Complexity more or less describes the permutability and variety of actions- How many solvable game state paths already exist as an isotope? How many different actions are necessary? And how many total actions are necessary?

At the start of most games, the player has a number of total possible actions. As the game progresses, they acquire new actions. With these new actions comes the responsibility to incorporate them advantageously into normal play. In most games, they typically don't alter the outcome too much, but they reduce complexity (and thus the risk of ending up in an unsolvable path) when properly used in a situation that would normally have high complexity. Whatever the case for a particular game may be- as more actions are acquired, the difficulty of the game 'should' adjust to provide continuous challenge to ensure those new abilities are, at times, necessary components to victory or necessary for a perfect victory (one without losing a lot of HP- or something similar).

In a game where difficulty isn't increased arbitrarily, but built-in to the already randomly generated game world, we can think of this in terms of enablers. We cun run straight into Lava Lake and try to slay the Fire Dragon- but it's complexity will be greatly reduced (to the point of being possible) with that ring of Fire Immunity.




Solvability and Complexity are particularly important in Roguelikes because of their randomly generated nature. How do we know our randomly generated challenges are actually challenging the player? How can we ensure that the gameplay continues to be interesting? How can we not completely bone the player after all their hard work?


I'll talk briefly about ToME and Brogue, since they represent two ends of the Roguelike spectrum that are very successful-

The first is ToME, and the game that I feel falls the shortest in terms of being interesting in regards to Complexity and Solvability (as far as the random generation of challenges are concerned).

ToME is filled with critters and critters of enemies, but there is very very very little variety or complexity to combat. When we acquire a new ability, we will think briefly about how this ability fits into our standard mode of operation, but we don't really need to think very much about what we're doing.

Our character is either strong enough to solve a problem or isn't- the challenge has very little to do with HOW we play our character because the BEST move (and best way to build a character) is often very clear. In the case of ToME, we're playing against a random number generator- there's very little intelligence behind how the game produces challenges.

After level 10, for example, a whole new set of monsters are randomly generated. The only significant difference, in terms of difficulty, is probably the existence of stealthed enemies (which doesn't make much difference). These jumps in difficulty and complexity are arbitrary and typically uninteresting (just one more thing to think about). The game becomes much more interesting after we reach the Far East, but most contests leading up to a boss have more to do with resource management, equipment, and character design than with tactical decisions. This is in part due to the role of unrestricted resting- which is a necessity given the inherent imbalance of class abilities. The problems with class restrictions in ToME are more appropriately addressed elsewhere, but it's important to note how the structured approach to acquiring abilities and the variety of abilities that can be acquired influence complexity. There is so much variety that it's too difficult to make gameplay dependent upon it. As a result, the difficulty moves laterally about the shallow end of the pool. That isn't to say that ToME isn't hard. Just that it isn't complex (despite all the different options that a player has).

ToME seems to have a ton of depth in regards to how a player creates a character to solve the problem of the game world. However, the game world doesn't ask much from us- it's more about intelligent min/maxing and hoping that we don't get hit by a WTF dice-roll moment. For this reason, the infinite dungeon is a lot more interesting than the actual game- It, however, more readily exposes some of the problems with how difficulty changes. Don't mean to sound Harsh, in regards to ToME, it does a lot of things very successfully- but I think it's only remaining problems revolve around its difficulty.



Next up is Brogue. My longest run was contingent upon a heavily enhanced staff of discord. Brogue is interesting because we emerge with our own 'class' that we can play and build up based upon the tools we find.

Brogue starts out with very few actions possible and virtually no complexity. Because there is no complexity almost every path results in a solution for the first 4-5 levels. You can hold 'X' for the first several floors to save a lot of time.

By the fifth floor (or so), if we haven't acquired a certain set of tools (including potions), we're likely to be boned in the next few levels. The further we go along, the more we depend upon the RNG to increase our range of abilities in a way that actually allows us to deal with problems. In most cases, the order in which we use our abilities doesn't matter very much. Against a hard enemy I need to use all my charges and toss a few javelins- against easier challenges I do less. Sometimes order matters- but decision-making in Brogue is fairly straightforward.

The issue lies in the fact that Brogue's monster generation is always depth-based. If the RNG hasn't graced you with the right/enough junk, it's not likely to be a successful run. We can make decisions to reduce our consumption and increase our chances- but we can never be certain as to the solvability, given our progress, of a level. We may simply not be strong enough by the time we hit a certain depth.

Brogue also has a tendency of providing us with dead-ends or, despite a speed-running esque approach, starving us to death. Our solvability isn't assured. Starving to death when we haven't been making frivolous actions or even the slightest bit of backtracking and avoid resting at all costs is the most unrewarding death.



The overarching problem that Solvability and Complexity expose is assuring that we don't screw the player out of their hard work and ensuring that it's rewarding and meaningful (as opposed to frustrating)- or that we at least honor them with a glorious death. I haven't touched chess-rogue yet, but it's design (Being something more like a procedural DRoD than a Roguelike) seems to satisfy the objective of reducing solvability and increasing complexity. It just lacks some of the more interesting RPG-esque elements and emergent gameplay that makes Rogue interesting.

I personally think that a roguelike should give us challenges (mainly combat, but also other types) that are more puzzle-esque and strategic (and less RNG-based WTF moments). DRoD is an excellent example of this, but it's by the grace of level-designers that it explicitly satisfies complexity and solvability issues (at the expense of flexibility- it's probably less roguelike than chess-rogue). It's more interesting to have diverse solution paths that allow a player to develop their own playstyle, but to demand that that playstyle be refined over the course of a game. As a side note, fighting games do a great job of capturing a player's personality without necessarily confining them to a particular set of decisions.


Accomplishing desirable solvability and complexity procedurally is a pretty complicated problem- how can we generate a 'room' that with some certainty and in reasonable generation time, will give us solvability and complexity within a desirable range of difficulty? Some probabilistic heuristics would make it possible and there may already exist a few models to implement such an idea. In most cases, we wouldn't bother analyzing or shooting for such an objective, but just try and make sure that problems are reasonably difficult by a certain point in time by the virtue of what content is being generated (such as in Brogue or in ToME).  Unfortunately, the complexity of such a methodology is typically lacking and the solvability isn't necessarily certain- the burden of montonous work with a sudden dice-roll of death sucks. Although we aren't dissuaded from playing RLs for these reasons, I feel like RLs tend to lack completeness as a game because these two problems aren't addressed in a formal way. We don't even know if there is a solution because there may randomly be a dead-end or coincidentally unbeatable monster. They aren't necessarily solvable and they don't necessarily provide continuous challenge.


Anyhow- more to think about later. Please let me know what you think.

[Z]

Welcome!

I'm working on a thesis that has a little bit to do with procedural content generation and wanted to spark up some discussions to share some opinions and get some impressions. Most of the concepts I'm interested in have more to do with roguelikes than anything else, so I thought I'd start here. I'm not too sure how active this place is- but I hope that it serves as the general hub for RL development discussion that I'm assuming it does. If anyone has any suggestions as to where a better place may be, please comment!

As for place, I think this is one of the two best places to discuss roguelikes in general. The other place is rgrd (and also rgrm).

Brogue also has a tendency of providing us with dead-ends or, despite a speed-running esque approach, starving us to death. Our solvability isn't assured. Starving to death when we haven't been making frivolous actions or even the slightest bit of backtracking and avoid resting at all costs is the most unrewarding death.

I don't agree with this. Brogue has a "metering" system which makes sure that you get as much food as you need (and also other important resources like potions of strength and scrolls of enchantment). Starving is caused by a bad strategy, not by bad luck. I think this system works very well and I never starved, if you run out of food, this means that you should proceed to the next level and you are almost guaranteed to find more. I don't know what you mean by dead-ends, but it makes sure that you can reach everything (as every decent roguelike does).

The overarching problem that Solvability and Complexity expose is assuring that we don't screw the player out of their hard work and ensuring that it's rewarding and meaningful (as opposed to frustrating)- or that we at least honor them with a glorious death. I haven't touched chess-rogue yet, but it's design (Being something more like a procedural DRoD than a Roguelike) seems to satisfy the objective of reducing solvability and increasing complexity. It just lacks some of the more interesting RPG-esque elements and emergent gameplay that makes Rogue interesting.

ChessRogue is awesome, although it is maybe too easy to lose the game randomly (not due to randomness inherent in the game, but a typo). You should also like my Hydra Slayer, which is puzzle based, has more RPG-esque elements, no stupid maximizing (smaller weapons are often more useful than larger ones, and sometimes you have to make an enemy seemingly stronger in order to defeat it) and contains almost no ways to lose the game randomly (only an accident with a giant missile on a wrap-around level, or delaying drinking the Potion of Life one turn too long). Also try older games by Darren Grey (no hitpoints leads to better puzzles), and the popular semi-roguelike Desktop Dungeons.

Overall, I agree that effects which randomly either work or not, although so popular in roguelikes, tend to weaken the tactical quality of the game. Like the ubiquitous accuracy/dodge, or the also popular critical hit mechanics. I think Jeff Lait's You Only Live Once was the first roguelike with a deterministic combat system, and it was very good. You can try to win the game with the first character (the child), which is a very nice tactical challenge.

DRoD is an excellent example of this, but it's by the grace of level-designers that it explicitly satisfies complexity and solvability issues (at the expense of flexibility- it's probably less roguelike than chess-rogue).

DROD is a great game, but not generally considered a roguelike. I think this is partially due to it being created a long time ago, where roguelikes were more about role-playing and stats than about puzzle solving, and DROD was very different from this. Nowaday DROD feels closer to the puzzle part of the roguelike world. Still, the lack of randomness means that most people would probably call it a semi-roguelike.

[requerent]

I don't agree with this. Brogue has a "metering" system which makes sure that you get as much food as you need (and also other important resources like potions of strength and scrolls of enchantment). Starving is caused by a bad strategy, not by bad luck. I think this system works very well and I never starved, if you run out of food, this means that you should proceed to the next level and you are almost guaranteed to find more. I don't know what you mean by dead-ends, but it makes sure that you can reach everything (as every decent roguelike does).

I've run into some situations where I've gotten into an area that is inescapable. Mainly with Pit Floats or a potion of Descent- I've fallen into rooms that have no accessibility to other areas of the level. I would also not be in possession of other ways to spontaneously change my location (teleportation) or depth (another potion of descent). The Food shortage issue actually happened to me on a run-through in which my entire focus was on making no extraneous moves (I don't think I was monkeyed or went swimming X_x). These are 'bug'-like situations that shouldn't happen, but they can. I similarly see inaccessible areas in ToME (where there are items/creatures) all the time on the forest-style maps (Trollmire and the Slave area- and far portals that use that algorithm). Bugs aren't really the subject of my concern though- just side-note examples on the sort of things that shouldn't happen or that effect solvability. Many of those types of problems/bugs (accessibility) have solutions.

The main point is the solvability- Have there actually been enough tools generated to proceed to greater depths? This oftentimes isn't the case. Even if it is, there is no assurance that these tools require more interesting gameplay via increasing the complexity. With Brogue, you aren't likely to make profound discoveries in how you play the game- you use what you can and sometimes it's enough, sometimes it isn't. The decisions have more to do with whether you increase your chance of surviving now or later- based upon what items you take from treasure rooms, where you use your enchantments and when you use healing potions.



There are plenty more rogue-likes that I need to be checking out. DRoD is definitely not a rogue-like, and many of the solutions to levels are extremely restrictive-- but it has a lot of wonderful components that belong in a successful roguelike. It also manages to implement puzzles within a 'style' that is appropriate for something rogue-like~ish.

I would actually like to see resources (such as HP) be used by heuristically generated challenges so that there are situations where a player will need to make sacrifices to succeed (Brogue does this in a way- with when to use items). Typically, we NEVER want to lose HP if at all possible. HP is a buffer to losing, but also can have a place in puzzles when utilized as a resource-component when generating how solvable/complex an area may be. If we're generating a game with a large world- HP is the buffer to running away from an area that is too difficult- an important feature...

[Pueo]

I've run into some situations where I've gotten into an area that is inescapable. Mainly with Pit Floats or a potion of Descent- I've fallen into rooms that have no accessibility to other areas of the level.

I think you're missing the 's' button, for <s>earch.  No matter what, Brogue will always be completely connected.

[requerent]

I've run into some situations where I've gotten into an area that is inescapable. Mainly with Pit Floats or a potion of Descent- I've fallen into rooms that have no accessibility to other areas of the level.

I think you're missing the 's' button, for <s>earch.  No matter what, Brogue will always be completely connected.

Ah- Search should be giving user feedback on failed attempts- "I failed to find anything." Or colorize a searched square.

[guest509]

  The dead ends in Brogue have nothing to do with solvability or complexity. Because there aren't any. I cannot be certain that Brogue is beatable (solvable) with perfect play every time. I've never had an unavoidable death so far. You'd have to find a group of very good players in order to do a good study. I do know that Nethack, a game with a TON of instant death situations and long as hell, is beatable with a very high % of success. One guy had a streak of several dozen wins. See the Nethack google group here.

http://groups.google.com/group/rec.games.roguelike.nethack/topics?lnk

  On the Brogue Forums we talk a bit about this. Maybe you already read it though. Here is the link.

http://sites.google.com/site/broguegame/home/forum    [go to the Winnibility Of Brogue thread]

  A few things you said above need clarifications. Solvibility of a game does not decrease as the game progresses. This might be true in some games but definitely not the majority. There is a game record of a Moria game showing that the higher levels were not dangerous hardly at all but the early mid game was deadly. Also games like Modern Warfare 3 are easy all the way through. With maybe a few upticks in danger to keep it interesting.

  I'm not even sure a steady difficulty curve is desirable. Many games have made millions, most modern games, by having a few hard parts broken up with large sections of grinding (easy, low risk areas). Smooth game playe and little minor rewards are what keep the player motivated. The feeling of triumph is saved for the bosses (or other difficult areas). Gears of War, God of War, MW3 and other major hits are built on this model.

  I guess a steady curve is a good idea in a Roguelike. But a good roguelike with periodic bosses where the difficulty spikes up would be neato. Arguably these instances happen in all roguelikes already. In an emergent fashion.

  Your comments that ToME lacks strategic depth outside of character creation and min maxing is going to be met with eye rolling. Also the feeling that you are just trying to avoid a WTF die roll in ToME seems a strange statement. I was under the impression that ToME has very few, if any, instant death types of moves.

  Both ToME and Brogue have their own Forums. You can ask more game specific questions there.

[Krice]

The difficulty of roguelikes has roots in 8-bit games that were extending the gameplay time often with situations that were impossible to predict. You need to know what is going to happen so you can solve that the next time. I think it's just poor game design and that's it, but it's in odd way a part of what roguelikes are as games.

[requerent]

@Krice,

A few things you said above need clarifications. Solvibility of a game does not decrease as the game progresses. This might be true in some games but definitely not the majority.

...

The dead ends in Brogue have nothing to do with solvability or complexity.

I'm NOT regarding solvability as whether or not a game is 'winnable.'

(from the original post):

Within this tree of potential game states, how many terminal nodes result in a victory for the player? Or rather, How many are solutions? The more paths that result in a victory condition, the more solvable the room is (room is an arbitrary measure of scope- we can think of the entire game's solvability based upon the solvability of each region, of each level, of each room, of each monster, etc).

But rather by how discriminating the decision tree is. Solvability asks how many terminal nodes in a decision tree yield favorable outcomes. The player may have become more powerful and thus more capable of solving difficult problems, to the point in which it seems easier than earlier problems, but mistakes are typically also less forgiving.

For example- On level 1 of some game, I can run circles around goblins with lots of 'extraneous' moves (those that would normally have very low heuristic value for an AI). I can't exhibit the same amount of extraneousness on level 10 vs a dragon and expect to be as successful. This obvious and at times arbitrary increase in difficult doesn't undergo much scrutinization- I propose solvability and complexity as ways of looking at how difficulty progresses in a game. Now- if I have to waste a bunch of healing potions on that goblin, then the future solvability/complexity with the Dragon encounter is going to change- making it even more difficult to generate challenges without a negative feedback cycle (other issue).

This quality of a game doesn't necessarily decrease throughout ALL games, but in games where it doesn't change there needs to be an attractive change in complexity or a really good story. In the case of roguelikes, solvability definitely changes and tends to become more difficult as the game progresses.

Because there aren't any. I cannot be certain that Brogue is beatable (solvable) with perfect play every time.

If Brogue's solvability, in terms of winning the entire game (Which I don't really talk about), depends upon a perfect playthrough, then it has virtually no solvability. Solvability, however, changes as we go deeper. If there are a few set of rote axioms that allow a player to play Brogue more 'perfectly,' then the player is making decisions based upon how he knows how the game generates challenges. There are other concepts important in making a game interesting- if the player knows how future challenges are generated and can prepare for them without having been given an explanation, then there is quite a bit of 'learn-die-reset' going on. This isn't 'bad,' but it's something worth addressing elsewhere. The obviousness of a 'right' decision makes solvability uninteresting and inadvertantly culls the depth of complexity.

"Dead ends" have EVERYTHING to do with solvability and complexity. Allowing a player to go down a path that will assuredly become unsolvable is wasting the player's time.

I'm not even sure a steady difficulty curve is desirable.

I don't think I meant to imply this. Just that solvability should decrease. Not necessarily gradually or as some measurable curve- or even as a 'this area is harder than this area.' Difficulty changes with solvability and complexity. If we have a ring of fire immunity, the complexity and solvability for the fire pit area suddenly change.

If we incorporate solvability and complexity into the generation of a 'room' (arbitrary measure of scope), we could do something zelda-like and obligate the player to find enablers that make areas possible. If all enablers were useful in all areas- this would create a positive feedback loop as each area is defeated, making the game get easier. However, if all enablers weren't useful in all areas then the game isn't very complex and the strategy could become fairly one dimensional (assuming enablers and 'possible actions' are related). This is a serious problem. Addressing Complexity and Solvability is part of the solution.

  I guess a steady curve is a good idea in a Roguelike. But a good roguelike with periodic bosses where the difficulty spikes up would be neato. Arguably these instances happen in all roguelikes already. In an emergent fashion.

In what way would that be emergent?

Your comments that ToME lacks strategic depth outside of character creation and min maxing is going to be met with eye rolling. Also the feeling that you are just trying to avoid a WTF die roll in ToME seems a strange statement. I was under the impression that ToME has very few, if any, instant death types of moves.

It lacks strategic depth because the BEST action that a player can make, given the information s/he has, is oftentimes very obvious. Very rarely do you have to shake-up your normal operations. The game is very repetitive. What qualities of a character that maximize our ability to survive/kill stuff become a priority. Say we're on an archmage run- We're not likely to dump stat points into strength unless it is for the purpose of acquiring the minimal amount of strength to equip something (Say we found some amazing randart armor and have a feathersteel amulet and somehow we have that stat points to dump). If we're building a hybrid mage for some god-awful reason, there is a necessity to use class and stat points as frugally as possible to ensure maximal survival. While it's true that a player can create their own challenges- I'm talking about possible game states. In games, we design difficulty around the assumption that a player wants to maximize his advantage.

Yea- WTF moments and ToME don't exactly go together (in that they necessarily result in 'death'), but heavy reliance on dice rolls will always give you lameness (and WTF moments). Because success in the game is probability driven, a lot of the challenge has to be reduced so that you can progress to the end (and enjoy the wonderful story). I pretty much design builds around stun immunity, considering how often stun resist doesn't really mean anything with my Karma... I would say that dice-rolling does a lot to kill interesting difficulty in ToME.

The most interesting strategic lessons I learned playing ToME are from running as an archmage on insane difficulty (which isn't even hard)- but these lessons tend to be more rote discoveries as opposed to genuine strategy. They are a question of "How am I going to be strong enough to do this area? What stats/abilities do I need for this area?" Completely dependent upon prior knowledge.

Both ToME and Brogue have their own Forums. You can ask more game specific questions there.

Even if I erroneously refer to qualities of ToME and Brogue that aren't really there or true, I'm using them as examples for something else. This is not meant to be a discussion on how "good" ToME and Brogue are. I'm not trolling or bashing them in any way, but trying to create an objective paradigm to improve games- in this case, on the very specific subjects of complexity and solvability. Brogue and ToME just happen to be more interesting to talk about for a number of reasons.


A designer can approach the problem of solvability and complexity however s/he wants, but at least knowing the vocabulary and looking at the problem of making a game with the right tools is empowering. If we design a game without these thoughts in mind, who knows whether or not the game will be a challenge or interesting-- from here we just tweak values hoping that it's fun.

Roguelikes rely on the RNG to create content- What if that RNG was implemented more heuristically? In the case of Brogue, we run into situations where we have dependency trees (IE treasure room puzzles), but the challenge of the game revolves around using randomly generated tools to fight off randomly generated monsters. We're, in effect, playing a genetic algorithm. This is very interesting- but it doesn't always provide interesting gameplay because it doesn't assure whether or not progress is still possible.

I believe that progress should always be possible- if progress needs to be dependent upon previous actions (by design- ie, potions and other expendable resources), then it shouldn't cull all possible victories in our decision tree unless there is another path that the game will let us take. If healing potions are 'mistake tokens' or 'extra turns' that we redeem to make up for our mistakes, then their usage shouldn't be required in difficult encounters. That is, there should always be some path within the possible set of decisions that will result in victory.

[guest509]

  These thoughts are hard to follow because you are attempting to create jargon using words already commonly used to describe things when speaking about game design.
  All, or most, of my misconceptions about what you are saying stem from vocabulary. I've done academic work that fell into that same trap. I'm not saying you are on the wrong track, but if you find you are confusing people who are interested and educated on the topic, you might want to take a second look at how you are approaching things.
  It seems like some interesting work, but discussion threatens to devolve into a somewhat frivolous exercise of miscommunication and corrections based on semantics.

[requerent]

  These thoughts are hard to follow because you are attempting to create jargon using words already commonly used to describe things when speaking about game design.
  All, or most, of my misconceptions about what you are saying stem from vocabulary. I've done academic work that fell into that same trap. I'm not saying you are on the wrong track, but if you find you are confusing people who are interested and educated on the topic, you might want to take a second look at how you are approaching things.

When we ask the question- "Can this game be won?" We are asking whether or not it is solvable. If we ask the question "How many ways are there to beat this game?" We're asking "How solvable is this game?"

I think Jargon is against me because the literal meaning of solvability is to describe 'how solvable' something is. Applying solvability to a game, in terms of meaningful analysis, would involve a quantative description. Game states are the discrete progress of a game- the game state tree tells us how many paths are solvable and how many result in failed states. Solvability, then, describes the breadth of paths that result in solutions. If you think this use of the word is unreasonable and can think of a better one, I would definitely like to know!

Complexity then describes the depth of these solutions (which inherently includes properties like variety and symmetry for analysis).

  It seems like some interesting work, but discussion threatens to devolve into a somewhat frivolous exercise of miscommunication and corrections based on semantics.

That's still potentially useful. Semantic debates are important because they allow for more clear communication. In my case- I presented key terms explicitly. If they're interpreted any other way relative to how I presented them then semantic discussions are useful because I might discover more appropriate keywords to describe my ideas.

[Game Hunter]

The terms might be a bit awkward but, given what they intend to represent, they're pretty good IMO. This is how I'm interpretting requerent's concepts of solvability and complexity:

• Solvability, by a quantitative standard, is simply the number of independent ways to solve a problem. For example, if there is an enemy in my path and I need only to get past it, then I can solve the problem by removing the enemy or finding a way around the enemy that doesn't require it to be moved. These, in turn, can be split more depending on the means provided in the game:
  
  • removing the enemy could be a matter of killing it (e.g., with a weapon) or displacing it (e.g., teleportation)
  • maneuvering around the enemy could involve a separate path to your destination, or include a method of disabling the enemy (e.g., trapping) in such a way that allows you to pass over it
  • These separate possibilities can, in turn, create more ways to go about it: the key is that, so long as the critical piece of the solution is separate from the rest, it is independent. (I'm sure this much, however, is open to interpretation.)
• Complexity, by a quantitative standard, is the number of pieces (or steps depending on the kind of problem) required to solve a problem. For example, the problem of "getting past an enemy" is typically straightforward in a roguelike (attack it until it dies), but can become more complex later on (find an advantageous position and use ranged attacks, backtrack until there's a way to maneuver around the enemy entirely, set up a trap and lure the enemy into it).
• For the purpose of optimizing difficulty in terms of solvability and complexity, if multiple solutions to the same problem have varying complexities, only the least complex solution determines the overall complexity of the problem. Things like "not knowing all the possible solutions" can obscure the overall complexity.
• Solvability and complexity often follow an inverse relationship: that is, if there are many ways to solve a problem, the overall complexity of the problem is very small; and if the problem is very complex to solve, there are only a few ways to solve it. This is by no means the extent of their relationship, but it is probably the simplest to design, thus it can be considered a general case.

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?

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.

[Ancient]

  I guess a steady curve is a good idea in a Roguelike. But a good roguelike with periodic bosses where the difficulty spikes up would be neato. Arguably these instances happen in all roguelikes already. In an emergent fashion.

In what way would that be emergent?

1) An out of depth monster is generated. It is more difficult to beat than creatures native to the currently explored dungeon level. Typically this presents a low solvability problem and only slightly more experience and better equipment earlier as a reward.

2) An unique monster is generated. These are hand-designed and what values of solvability complexity to assign them varies very much. DCSS is arguably the most famous for this. Sigmund is a high threat for almost every character while Ijyb is barely noticeable foe unless he manages to lay his hands on a wand.

3) Artifact guardian is generated. ADOM does this. Usually solvability is not changed in comparison with other monsters because this is a standard creature with increased stats but complexity goes high since the guardian is buff and hits strongly. The artifact if good will severely diminish complexity of the whole game and may decrease satisfaction.

4) Something walks on polymorph trap or a shapeshifter takes upon a powerful form. Again, this usually has low solvability but often there is a high complexity solution of carefully avoiding it and waiting until timer forces the creature to turn back into its original form. See chameleons of POWDER.

[requerent]

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

1) An out of depth monster is generated. It is more difficult to beat than creatures native to the currently explored dungeon level. Typically this presents a low solvability problem and only slightly more experience and better equipment earlier as a reward.

2) An unique monster is generated. These are hand-designed and what values of solvability complexity to assign them varies very much. DCSS is arguably the most famous for this. Sigmund is a high threat for almost every character while Ijyb is barely noticeable foe unless he manages to lay his hands on a wand.

3) Artifact guardian is generated. ADOM does this. Usually solvability is not changed in comparison with other monsters because this is a standard creature with increased stats but complexity goes high since the guardian is buff and hits strongly. The artifact if good will severely diminish complexity of the whole game and may decrease satisfaction.

4) Something walks on polymorph trap or a shapeshifter takes upon a powerful form. Again, this usually has low solvability but often there is a high complexity solution of carefully avoiding it and waiting until timer forces the creature to turn back into its original form. See chameleons of POWDER.

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. Complexity necessarily requires variance and assymetry. There is also nothing inherently emergent about evasion. For emergence to exist, there need to be a variety of properties from which gameplay can emerge. Emergence typically involves a monster only in how its weaknesses can be exploited (in that weaknesses of a monster are, in a way, part of the set of tools involved in solving the problem that is the monster).

Brogue has some excellent examples of emergence- A Bloat emits explosive gas upon death. If killed at range, an incendiary dart can trigger that gas, resulting in a certain amount of roasted goblin when used appropriately. In conjunction with flammable flora, problem solving possibilities can become very interesting.

[Z]

I think Jargon is against me because the literal meaning of solvability is to describe 'how solvable' something is. Applying solvability to a game, in terms of meaningful analysis, would involve a quantative description. Game states are the discrete progress of a game- the game state tree tells us how many paths are solvable and how many result in failed states. Solvability, then, describes the breadth of paths that result in solutions. If you think this use of the word is unreasonable and can think of a better one, I would definitely like to know!

Do you intend to define solvability in an abstract and formal way, in terms of counting the paths in the game tree? I don't think this is possible (give me your definition more precisely and I'll try to show you why it is wrong). I would define solvability as the probability that the perfect player wins the game, but this seems to not be what you want (for example, in your example about having more freedom when fighting goblins than when fighting dragons, this freedom is irrelevant to perfect players).

[requerent]

I think Jargon is against me because the literal meaning of solvability is to describe 'how solvable' something is. Applying solvability to a game, in terms of meaningful analysis, would involve a quantative description. Game states are the discrete progress of a game- the game state tree tells us how many paths are solvable and how many result in failed states. Solvability, then, describes the breadth of paths that result in solutions. If you think this use of the word is unreasonable and can think of a better one, I would definitely like to know!

Do you intend to define solvability in an abstract and formal way, in terms of counting the paths in the game tree? I don't think this is possible (give me your definition more precisely and I'll try to show you why it is wrong).

Hmm... I haven't worked out the details of a formal definition, but Game Hunter does a very good job of reducing my blatherings. I'd be better off drawing a picture... which is probably what I'll do in a bit. Either way, I'm hoping that a formal definition will emerge, at some point, but a formal definition isn't necessary for the concept to be useful.

Regardless,
Consider the tree of all possible game states of a relevant scope.

For any given state that is not terminal, the solvability of a state describes how many of that state's children contain a goal state in their respective sub-trees relative to those that do not.

EX. If a state has 8 child states and 3 of those have no solutions in their sub-trees, we might say the solvability of the given state is 5/8.

This isn't inherently useful unless we look at the relationship of solvability between parents and children through each possible solution path.

EX. A state may have a solvability of 8/8, but all of it's children may have a solvability that is 1/8. For a state to represent its solvability in a useful way, it needs to take into consideration all of its children's solvability.

When we hit a state that isn't solvable, it's likely (just an assertion) that we can prune it or treat it as a terminal node. From there, we can evaluate all terminal nodes of a given state to determine its solvability in a meaningful way.

EX. If state A appears to have 3/8 solvability and it's 3 solvable children have 1/8 solvability whose solutions are terminal- we can say that there are 3 solutions to 26 failed states/paths- or that state A has an evaluated solvability of 3/26.


Obviously, time-complexity makes this sort of solvability impossible to determine. But I'm suggesting its use as a parameter in random generation. If we can probabilistically generate challenges within desirable ranges of solvability, we can be relatively certain that the game will be challenging in the way that a designer wants it to be. In conjunction with complexity, we can probabilistically generate challenges that require a variety of actions. This approach may be a bit more intuitive than arbitrarily scaling levels up or tossing in monsters with more complicated properties.

I would define solvability as the probability that the perfect player wins the game, but this seems to not be what you want (for example, in your example about having more freedom when fighting goblins than when fighting dragons, this freedom is irrelevant to perfect players).

Hmm... Solvability shouldn't care about heuristics, so it doesn't care about perfect playing. The probability of a perfect player finding a solution is determined by how we design the game. Solvability, as an explicitly defined component (as a set of values to achieve certain qualities that we define as desirable) of generated content, will result in probabilistic solvability (of the whole game) for different heuristic skill levels (either novice or 'perfect' or what not').

So, yes to both. Solvability, as a generation parameter, could be implemented to generate game content so that a perfect player will win with some amount of frequency. But it could also be used to assure a certain degree of solvability so that perfect play will always result in a winner. We can then incorporate complexity to make this more difficult, but always solvable so we never let a player continue playing when they're already in a sub-tree with only terminal fail states (unless it's local- IE, a duel or a room). That's up to the designer though.

I personally think it's better design to always have some solvability unless it's a game where a psychological component plays a role in who wins (competitive card games, or decision games with a fog of war), but that's a player vs player problem- we don't want explicit solvability because if both players play perfectly then white will always defeat black (likely the case in chess if we had the computing power to evaluate all states- but it could always result in stalemate with two perfect players). Anyways- different topic of discussion.