Depth and Design: Contrasting AI and Human Understandings

Updated on

This talk was an invited lecture at the AAAI-18 Workshop on Knowledge Extraction from Games.

Slides

The slides have captions in many cases; hover over them when in a window to see them (if you click on the slides to see them larger, they won’t show up).

Video

PDF

Depth and designDownload

Transcript

HOST: Thank you so much for your patience as we try to get this whole thing figured out.

RAPH KOSTER: Oh, no worries. No worries. I was following along on the stream.

HOST: Okay. Let me just plug you in here. Can you make sure you’re up on there? Let me see. Okay. Great. We’re going to go on our end, so feel free to start up whenever you’re comfortable.

RAPH KOSTER: All right. Gosh, it’s weird doing this without being able to see any of you.

I’m going to talk a little bit about, as you can see here, depth in design, and in particular I’m interested in the boundaries here between AI and humans, and what exactly it is that we end up seeing as creators.

Here’s the thing about this. I’m coming at this as a designer of games, right? Not really as an academic, although I end up doing some academic stuff on the side. My main interest in academic work is actually in order to help me make games better, which made me quite intimidated to come talk to this group about anything related to this topic. You can ask Joe in particular how much I dithered about actually doing this.

In particular, I’m not that interested in questions of how computers can beat games. In fact, I’m more than a little ambivalent every time a computer does. I’m also not that interested in what a computer thinks is a good game, and I’m not particularly interested in making games or AIs that eliminate my job. I enjoy my job. I enjoy making games, and I want to keep doing it.

That leaves me with an interesting research interest, you might call it, which is leveraging as much of the computer as I can in order to help me make games without it actually being self-destructive.

Part of the problem right off the bat is trying to figure out what exactly “good” is. I did a book now over a dozen years ago called A Theory of Fun, in which I tried to approach that from a cognitive psychology point of view and relate it back to other media and other art forms.

About ten years ago, I started looking into what now gets called game grammar, which is an approach looking at the complexity of games and seeing if we can find linkages between fun, or good, and complexity.

It very quickly became apparent that an enormous amount of games don’t even happen in what we normally think of as computational space. For example, games that are about figuring out how other people think: think Apples to Apples or Cards Against Humanity. Games that are about mastering your own body’s reactions, such as the fun you get while on a roller coaster.

Lately, there’s been some discussion around the communities with which I hang out around the question of depth, and what exactly that even means. There isn’t really a good formal definition of depth. We know it can’t mean certain things, such as really large state spaces for a game. Go is both deep and enormous, but enormity doesn’t imply depth.

It can’t just mean branching and lots of choices, because you can have games where you make lots of endless choices, such as moving back and forth one pixel at a time in Mario, and not actually get something deep out of it.

The reason I want to tackle this is in order to help me make deeper games that are also fun.

That game grammar project ended up being something relatively informal. There wasn’t anything as rigorous as a BNF grammar, although today in the PCG community we do see things like BNF grammars being used for procedural level design. We might think of that as a grammar more for the data that is input as statistical variation into a game. For example, the levels in a Mario-style platformer can be thought of as statistical variation running into effectively the same game system.

There is, of course, the ongoing project of identifying grammatical elements, and it’s seen some interesting success. We have in particular Machinations by Joris Dormans. I know Julian Togelius has picked up and run with that in various other directions.

An interesting question is whether we might work towards a grammar, and even develop a full context-free grammar, and not actually end up with answers to questions that are deeply relevant to designers, such as what is depth and how do we make it?

That wouldn’t actually be surprising, because many formal systems, such as music, are actually fairly well understood in terms of grammars. We actually know quite a lot about harmony, voice leading, the ways in which different timbres resonate. There’s a ton of science and grammar and formalism there, and it doesn’t really help most songwriters write a better song.

So it wouldn’t be surprising if we weren’t fully able to extract knowledge from that. But at the same time, there is interesting value that is derived from having those formalisms. For one thing, it does help us teach music theory and composition, and some percentage of those people go on to make interesting music. So it’s at least correlated, if not an answer.

I wanted to step back and think about this problem more holistically.

If we go back, as we often do in situations like this, to simple base cases, and we look at something like the coin flip, the coin flip is a really, really simple game that we use in order to determine binary outcomes. We tend to think of it as chance-driven, right?

But of course, we all know that coin flips are not actually like that at all if we start to analyze them more rigorously. We are imparting an upwards force via our thumb, which is not a particularly precise instrument. That means in practice, not only are we dealing with gravity—at least that’s a constant—but we’re also dealing with how high I’m holding my hand when I’m going to catch the coin, how much lateral force I have imposed because my thumbnail isn’t flat, what is the nature of the spinning that the coin is going to go through as I push on it, and even the fact that coins themselves aren’t actually unbiased chance generators.

Pennies, for example, are slightly heavier on Lincoln’s face, because it takes slightly more metal to make it. So they actually have a slight bias towards falling face down.

That doesn’t even count all kinds of other things. How hot or cold was it? That’s going to affect the elasticity of the surface, the coin, how many bounces, how regular was the surface, blah, blah.

It’s pretty standard for us to throw away all of this kind of complexity in favor of a simpler analysis whereby we can look at it in a more abstract way. This coin is a decision engine and a complex machine. And we treat it as if it were chance.

That’s a key point about games. We tend to use chance in games to simulate absent simulation. We use chance in the case of, you know, if I told you to implement the coin flip, you’d probably do a random number generator from zero to one. And you would fail to simulate all of this stuff. That’s fine. That’s actually normal. That’s how we tend to approach the problem.

All of our random number generators are also inaccurate simulations of randomness. And so it just keeps going on down, right? We all know our random number generators aren’t really random.

Right off the bat, we have a viewpoint that tends to make us see games, and in particular this game, as kind of binary win-loss situations. When we think in more analog terms, it often tends to be in the strength of the result. For example, a score. If I play Space Invaders, a score is kind of a strength of the result of how I did winning or losing.

In an awful lot of games, for example the coin flip, what happens if I drop the coin and it goes down the sewer grate? Then we have an indeterminate result. We don’t know what the result of the coin flip was.

I’ll actually make the case that that’s a core component of games, and one that we—it’s not so much that we don’t model it. It’s more that we intentionally try to avoid getting indeterminate output. We try to quantify our output at every possible step, because that’s a cognitive process that we go through when we play a game.

As an example of that, with a single coin flip, we try to go through iterations in order to make the result basically more determinative. More simple games are often played iteratively.

Here’s a model of a best-of-five. As soon as you hit three victories for one side or the other, then the iteration ends. Then we measure the victory at the end of that process. Typically, the victory condition causes a stop to the iteration process. So some branches on this tree exit early because the victory condition is met before all the iterations can even take place. That’s a pretty standard way to think about it.

We can think about that as bounds that are driven by an objective, a goal, something that we can express essentially in a binary form. Best-of-five has a point bound of three. You get to three, we know this is settled, and we can prune away the rest of the tree. It’s just not going to matter.

Connect Four is a game that actually has a point bound of just one. The moment somebody gets four in a row, the game is over. That’s the victory condition. There’s only one of those that ends up needing to happen.

But there are many cases of games—take Reversi, for example—which has 64 spaces. You effectively have a fixed set of turns, and victory points are being accrued all along. During that time period, we’re carefully counting, how many victory points do I have on one side or the other?

So we might think of these all as bounded games. That number of turns, or number of points, or whatever, tells us, “Hey, we are now at the point where we’re going to read the output.” Everything else previously was essentially premature.

The idea that there might be games that are unbounded gives me, as a designer, a practical handle on what we tend to call toys. But that’s really a discussion for another day. The debate over what is a toy, what is a puzzle, what is a game usually doesn’t have sufficient rigor in it for us to really be able to think about it well. Many of the things that we consider games might properly be termed collections of puzzles, for example.

It would be useful as a designer to be able to have a handle on those kinds of things. That’s the sort of research output that I look for when I think about formalisms and applying computation to my game design practice.

Victory points is a term out of tabletop games. We don’t use it all that much in video games, really. Often victory points are effectively invisible counting systems. The game is bounded by this, and we don’t really expose it to players as something that is happening as we go, even though it might very well be tracked.

In Mario, for example, to beat the game, you have to beat all the levels. So really, you’re accruing a victory point per level. But nothing in Mario’s presentation suggests that you should think about the game that way. Instead, we focus you on very different things.

Some types of games have more than one sort of victory point, and you can actually achieve an end to the branching process and the iteration process by hitting a threshold in either bound. It doesn’t matter which one gets hit first. Pente is a good example of that. If you get five in a row, or if you execute a certain number of captures.

Score, interestingly, usually is not the victory point in a video game. But it might be the victory point in a higher-order metagame. That’s also a really important thing for us to think about, which is that we do tend to speak in terms of minigames, metagames, and subgames. I’ll talk a little bit more about that in a moment.

Sometimes victory points move with turns. Let’s say a game like Reversi, where you are filling up a board. Victory points and turns move in tandem up and down, but they might not necessarily.

The topology of the space in which something is played causes interesting results with the victory points. We happen to play Reversi on an even-squares board. So it has an even number, and that means it theoretically admits of a draw. Victory points could be split 50-50.

So it’s a game that could actually, rather than being a binary outcome like we were talking about with coin flips, be a ternary operator. It could output minus one, one, or an indeterminate value in between. We can output effectively a non-answer to who won.

That’s actually useful. That’s the kind of simple mathematical axiom that is not actually as available to game designers as one might think. Even though it seems like it’s trivial, that isn’t the sort of thing that we necessarily teach game designers.

If you want to have a game that supports an arbitrary number of players, then its state space for turns and/or victory points, depending on how the game is bounded, needs to be a multiple of every possible number of players if you want to be able to achieve binary outcomes versus indeterminate outcomes.

That sort of axiom is not actually commonly stated. So we would say, hey, if you want to support three-player Othello and still have a tie, you actually need to have a board with 69 squares on it. It’s intuitively true after you work through the math, but it’s not necessarily the kind of thing that has become an axiom that we can hand to designers, even though it’s a pretty trivial result.

Those are the kinds of things that end up being passed down as rules of thumb for designers, and ironically end up being what is really useful, even though they often don’t have this sort of proof behind them.

What that means is that it kind of reveals to us a key point. First of all, thinking in binary terms of the game is probably a really big mistake. Indeterminacy is core to how a given game system operates. The fact that a statistic in the game happens to be evenly divisible by a number or not should not be thought of as a structural property of game systems.

That means game systems are probably ternary operators. They’re probably ternary output machines that spit out yes, no, and indeterminate.

The second thing that is revelatory there is that we should be thinking about that metagame, subgame, and minigame modality, and realizing that when we talk about games, we should be thinking of them as fractal or self-similar structures.

The way this is often discussed in game design circles is that games are made of games. This is one of the foundational tenets of what gets called game grammar. You may also have heard of game designer Dan Cook’s notion of skill atoms, or the chemistry of game design, which is the idea that game structures are self-similar, they’re all oriented around learning, and that they nest.

A lot of the work around loops and grammar, including my stabs at notation systems and things like Machinations, tend to unroll games into flowcharts. Those tend to not capture this nesting quality. It can be represented, of course, particularly using software as an interface. You can click into a node and expand it and see that there’s a self-similar machine deeper down.

But it isn’t really the way in which we tend to think about games much of the time, particularly because we tend to think in terms of state space or unrolled trees.

So just as an example of how this ends up having super concrete impact on us as game designers, let’s think of the racing game.

The very first challenge you have, let’s say you’re racing just a simple oval, is a cognitive problem: how do I traverse this oval in the most efficient way? The first step there is actually a perceptual one: is this track oval or not, and what are the angles of the curves? Followed by a planning stage: how do I then plot a path that follows that?

Of course, as we begin to play, we run into the fact that it’s probably not just an oval. We have to go through this planning stage and figure this out pretty much in real time, because we may not have visibility until we learn the course. We may not have visibility or enough foreknowledge of what’s coming up to really assess this best-fit curve.

That’s a pretty substantial cognitive challenge with tight reaction times. It involves perceiving a bunch of complex stuff, curves in motion, at speed, a lot of mental calculus.

Then we have to be able to adapt and modify our idealized plan on the fly, which is yet an additional cognitive problem. The additional statistical variation of other cars on the road and the like is an additional cognitive problem that we have to deal with.

Then we have the problem of actually following that path, which becomes a haptic problem. Now we’re dealing with the controllers, the analog stick, the racing wheel, whatever it is.

This is an example of the nesting of these sorts of games, how we have to dig deeper and deeper into the process. It’s quite a load, so much of a load that the modern racing games just give you a ghost track to follow, so you don’t have to solve the first couple of problems at all. Even then, the games are plenty challenging, even though what we might think of as the high-order computational problem is removed.

All of that falls into that basic idea that designers tend to work with, particularly UX designers, of this classic learning loop, where the player has a mental model, they form an intent, given that intent they look at what they can do with the control, they do something that changes the model, they feed data into the model, the model state changes, you’re informed about those changes, and you move on.

If we were to try actually doing the crazy BNF thing that I don’t actually claim any expertise in, we might start capturing some of these principles in this way.

We might say, well, a game sometimes is just done, and that’s it, and often games are made of games with results. And results are, in fact, the outputs of systems and actions that have ternary outputs, with indeterminate sometimes being present and sometimes not.

We might actually end up saying, look, we can mathematically treat an entire game as a function of X, where X is statistical variation, player actions, and all the rest.

We can even go further and attempt to capture that haptic control problem, and think about actions as being the verb that is formulated by a player given the data it has taken in through whatever its perceptual model is, forming an intent with that data, marrying it to an input, which involves perceiving an affordance in whatever the controls are.

Even that game of perception might very well be a game in its own right, because the nesting of that can be very difficult. “Oh, I didn’t see that coming,” is an example of a perceptual-level game.

This gets validated as a theoretical model pretty trivially, because when we play, let’s say in this example chess, where I decide, “Oh, well, I want to control the center. I have a knight with which to do it. I will pick it up with my hand, and I will move the knight,” and now that goes over to my opponent through the rules of chess, we can translate it by swapping out only one of these atoms, so to speak, only one of these nested games. Use a controller instead of a hand and still recognizably preserve the integrity of chess, still call it chess.

There’s an interesting question there: why can we call computer chess still chess? Why can we call Texas hold ’em the same thing as five-card stud poker, when they are so different?

This lens lets us think about the ways in which the number of changed nested games or atoms, and critically where they reside in the nesting, whether they are input-level or not and so on, really makes us think of something as a game, a variant, a clone, a genre, and so on. That is a useful output to me.

And so we end up having to amend this grammar to say, actions might actually—inputs are games also. And now we have captured that haptic controller game of a racing game.

What that leads me to is that—and this is something that comes up from the game studies side quite a lot, although they tend to use Derrida and the term free play rather than the word indeterminacy—I think it’s fair to actually analogize these. We could think of free play as the range within which the indeterminacy can occur.

The idea of solving games via searches of possibility trees is basically about finding ways through indeterminacy by weighting the nodes with probability calculations of everything that’s further down that branch. That’s how we make simple naïve lookahead AIs. “Oh, I’m going to tally up some kind of arbitrary victory point or other metric that allows me to weight branching as we move down the system.”

The thing about that is that it does give us interesting outputs, even in a naïve way. For example, it’s extremely common even in everyday language for us as humans to describe indeterminacy tracks: movement through the indeterminacy in particular ways.

For example, these patterns we tend to call blowouts. This is an indeterminacy track that trended strongly towards a particular result from early on, and did not deviate very much from it.

Whereas we call this one a comeback. This is a strong trend that was reversed and ended up in the opposite direction.

Then we often call this one a hard-fought game: one where leadership in this indeterminacy track often tilts just slightly one way and slightly the other before arriving at a conclusion that was very difficult to predict from early on.

In fact, this particular configuration, this indeterminacy track, this trace, this gameplay trace, is often our objective in competitive games, to the degree that we will often use Monte Carlo modeling in order to look at the indeterminacy tracks, which are essentially the scoring history over the course of a game, to make sure that in fact it tipped over that midpoint frequently and regularly because it made for a more exciting game.

This then connects back to fun, because games that are blowouts do not tend to actually be that enjoyable. Suddenly we’re able to connect the formalism back to a very human quality.

[Brief technical difficulty with the slides.]

We often use limited lookahead, of course, in games because we may not have a full solver, or even because using full lookahead—well, obviously in AI, we often have limited lookahead. We know players have limited lookahead. In fact, if we give too much lookahead to a game AI that is an opponent, then the game usually sucks for the player, and that’s no fun.

One interesting thing about using lookahead and limited lookahead is that strategies often involve pushing somebody down a path where the indeterminacy is pushed to one side or the other. In common language, we use words like, “You’re in a bad position.”

You can almost think of this as a parity problem. We are at positive or negative. Any choice after which a victory point total exceeds that of the other player puts you in a positive state. Any choice that puts you below leaves you in a negative state. If you hit the bounds, you’re going to win.

One way to think of this, then, is nodes effectively acting as strategies. This is sort of a human-centric rather than computer-centric view, because when we unroll trees, we tend to think of it in terms of actual inputs and choices that players make.

But as a designer, it’s actually super useful to think of these nodes as things like the choice between attacking and defending: choices between high-level strategies, or heuristics, or approaches to the game. This is the kind of thing that leaves us sort of blank-faced when we look at AlphaGo’s play, because we can’t perceive something like the heuristics that it’s using.

The other thing about this is that it forces us to consider that to a human, not all affordances are visible. In other words, not all players can see all strategies at a given moment. Perceiving strategies, perceiving affordances, perceiving heuristics, being aware of their presence, is effectively a game in its own right.

Moving through these as parity problems—we could think of it in the complexity-theory sense or the permutation sense—then gives us design things. Think of something like a simple hot-potato game, where passing effectively shifts the parity burden onto the other player. Suddenly that becomes an important strategic choice in the game.

A practical takeaway for us as designers that emerges from this kind of analysis is the idea that when you look at a tree and analyze it in terms of parity, you tend to look at it in the context of only one type of victory point at a time.

But if a game offers more than one type of victory point, and as many branches as possible are equally rewarding, just in different victory tracks—meaning orthogonally forced choices, such as, “Do I maximize territory or strength?”—that really classic choice that you end up making every time you do character creation in an RPG, for example, where do I allocate my points? That instantly adds that quality we would perceive as depth, because we have to start juggling more than one win condition and worry about which direction we’re working towards, or whether we’re working towards both of them at once.

To a computer, that problem may actually never appear, particularly if it has sufficient lookahead. But to a human, it’s a very ever-present problem. So that becomes a concrete takeaway for us as designers attempting to make better games.

Fundamentally, though, trees end up being a toy model, because so many games are cyclical. Think of any kind of game where you move back and forth over a battlefield, and it can be hard-fought, but you are not necessarily moving decisively towards a conclusion.

All sorts of games, particularly narratively centered games, cause you to revisit areas, and the state changes happen at a level that is not intimately tied to the game’s bounds condition.

Think, for example, about moving through a game like What Remains of Edith Finch, or Gone Home, narratively centered games, or even adventure games, where what changes is actually your perceptual tools rather than statistical values. That gets to be something difficult for us to model.

Most games incorporate cycles in various ways, and this is why systems theory approaches tend to be so popular in all of the grammar-style approaches. Most recently, the book by Mike Sellers, Advanced Game Design: A Systems Approach, gives a great overview of things like feedback loops, non-linearity, chaos, emergence, and so on.

There are specific characteristics we can look for in games beyond narrative. Plain old state shifting, such as moving tokens, where we might arrive at fitness functions for token movement and placement, but they might not be the real ones, which is in part what turned out was going on with AlphaGo. Games where pieces can be added and removed, leading to cycles and loops.

Because of these situations, many games special-case loops. For example, we have recursion limits in chess. When the same movement occurs three times, it’s called draw by threefold repetition. In Go, there is the ko rule, which is effectively defined as an illegal branch. You are not allowed to return the game to a state that existed previously.

But many, many, many sorts of games actually rely deeply on cyclical repetition, which is a real problem for any sort of tree-based approach.

Another key thing that grammar leads us to, and that I’m a big advocate of, is the idea that actually there’s an opponent in the mix. We may be working with the actual rules there in the middle, but really what’s going on is that you change state and update mental model, put something into the system of the game, and then an opponent updates their notion of what’s going on in the game.

This opponent might just be a system. It might be an AI. It might just be a state machine, leaving the question of what systemic game design is at that point in the center.

A great example of this might actually be Space Invaders. Space Invaders takes place, I believe, in a 228-by-221-pixel area. The “AI” of Space Invaders is incredibly stupid, but it is engaging in a resource-management problem. It had limited CPU cycles with which to draw. Therefore the game gets faster when there are fewer enemies on the screen, because it has fewer pixels to plot.

You could literally think of the incredibly simple system of Space Invaders as using the tabletop term action points. How many cycles do I get in my turn to perform actions? How many actions can I do?

It chooses to spend all of them on moving. Therefore, when it has fewer candidates to move, they move faster because it can allocate more points into fewer resources.

Thinking this way actually does give us insight into games. The nice thing about it is that it allows us to think of the “opponent”—the AI strategy or other players—on the same grounds, leaving us even thinking of Space Invaders as being a contest between myself, which has a complex strategy and is playing the game of “destroy aliens,” versus an AI that has a simple strategy and is playing the game of “move one alien to the bottom.”

Completely orthogonal victory conditions. That’s a way for us to think about non-symmetrical gaming in general, as systems where the tree effectively has completely different orthogonal victory conditions for the two sides, as opposed to symmetrical games. All of that can, of course, still be expressed in formal grammars.

So where does that leave us with something like depth?

Frank Lantz and a bunch of other folks started talking about this a bit at a conference I was at in Banff on computational modeling of games. This got presented, I think, last year at a workshop very much like this one with a different three-word title.

They ended up trying to define it as the capacity for a system to allow ranked strategies. So basically, moving through strategies and finding more and more advanced strategies, where “advanced” is defined as costs more to compute. It’s effectively using more computational resources.

This has a whole bunch of implications. First, it maps really well to the idea that an indeterminate node is also a strategy choice, because effectively, indeterminate strategies and heuristics pair up really well. These are things a player can discover as they proceed towards mastery.

Shallow games kind of pop out. Anything that you can compute trivially, well, you solve it easily, so that’s boring. Something where you can’t discover new strategies feels like it lacks depth because you can’t figure out how to get to the next one.

That actually has a formal hole in it, of course, because how do you think about skill-chaining or learning? How do you capture that in this graph? That’s difficult to capture. But at least we can think of this process as being very much like in a mathematical proof, where we might move through lemmas, intermediate-stage solutions.

It also has some interesting mappings to everyday discussion. “Control the center” suddenly becomes very easy to think about. Heuristics: stay in this area of the state space.

Tree regularity, they point out, is effectively a way to look at indeterminacy. If tree regularity is too high, you get degenerate strategies, and it’s easy to arrive at optimal play. That’s another way of saying too many of the nodes are not indeterminate. Too many of the nodes are deterministic.

Too-low regularity means no heuristics will work because there’s excessive variability. That’s an interesting one, because excessive variability is what we liked in that Monte Carlo model of a hard-fought game. We like it under that scenario.

So really what that means is that we have to think of excessive variability from a perceptual point of view, not an actual point of view. We’re talking about the ability of a player to perceive how much variability or order there is in the system. This model doesn’t capture that. The Lantz model doesn’t have a way to capture that.

The heuristics, of course, are brute-force search shortcuts, which is great.

This has problems for me as a designer because it doesn’t reflect that learning loop very well. A classic thing that we know from educational theory is that abandonment of heuristics is a critical part of learning. Heuristics do not actually stack cleanly at all. That is not how these work.

It doesn’t account very well for non-transitive strategies. Think rock, paper, scissors, where you have equivalent strategies and equivalent heuristics. Attack and defend are deeply contextual in terms of their computational complexity and in terms of their solution strength.

So we can’t actually say that a given heuristic can fall cleanly on a two-dimensional graph in any way. We also don’t have any good way to measure the alleged computational complexity of a given heuristic.

If we solve the game, what often happens is that all heuristics are retroactively disproven. So they may have actually not been computationally complex at all. They may have just been foolish.

All of that sums up into a critique that Dan Cook left on an early draft of this paper, which I think is critically important for us as designers, because as designers, our canvas is not the computer, but the human mind.

Any rubric for depth that does not include a psychological filter will always result in examples that are interesting for a machine, but not for a human. That’s a bit of a blanket statement, because I do think that this shows us results that are interesting for humans, but not in a sufficiently reliable, predictable way. It ends up giving us rules of thumb yet again.

As an example, I’d offer up a game that has many heuristics, all of the same strength, all that require the same computational resources, where solution strength is not achieved by which heuristic you pick, but by selecting and combining them. That reveals how much of this, particularly for human players, is about affordances.

This is a game that I don’t know if all of you have played called Set. I can see you guys. How many of you are familiar with this game?

Okay. So this is a pattern-matching game that works this way. You have a deck of cards where the cards are each unique and present these patterns on more than one axis. You can see color is an axis, shape is an axis, number is an axis, and shading is an axis.

What you are trying to do is find sets. So it’s a classic 3SAT problem on four axes, which is lovely because it means we can instantly bucket it in that lovely NP-hard pile there in the large scale, if extrapolated out.

In this toy version of that problem, we have that first set that is a yes: it is either the same on an axis or different on an axis. That must be true for all four axes.

So this one is different in number, different in color, different in shape, and different in shading. The second yes is the same in number, the same in color, different in shape, and different in shading.

A different way to phrase this is, two repeats fails. Three repeats or one repeat are okay. The third example here fails because it repeats the solid shading value.

That’s the game of Set. It’s typically played by laying out a tableau, and then people call out sets as quickly as they can perceive them. Those cards are removed from the tableau and replaced from the deck.

Now, if we set a computer to play this, what we instantly see is—let’s assume it can either have access to the data immediately, or that it can image-recognize it trivially. It isn’t going to care about which order to do this search in. It doesn’t care if it searches by number, or shading, or color. It doesn’t really matter to it, and a brute search for it is incredibly trivial.

The only difference between computer algorithms here would be the order in which they choose to do the searches. Literally the ordering of the algorithm: do my branching ifs check number first? That’s basically down to programmer whim.

Where the strategy emerges versus an equal competitor here is going to be about looking over the long term across the deck. If a computer selects an if-statement ordering that increases search time for the other computers in the mix, that is its winning strategy.

The way to do that would be to know, “Oh, that one searches number first. So I’m going to intentionally search sets in a way that reduces the likelihood of number-based sets by selectively capturing cards off the board and card types, and counting those.” By making that its first if branch, it will exit sooner out of the algorithm and gain a microsecond of advantage that will over time pile up into a persistent deficit for a computer player that uses a different ordering.

But a computer that chooses the search ordering randomly would not be as vulnerable to this attack. That means that the next-order strategy is actually to build a mental model. The computer must build a model, based on how the other players play, of what search ordering they are using, which is directly analogous to a player assessing what strategies another player uses.

The interesting thing is the comparison here with humans. Humans find some kinds of congruency easier to see. It’s a perceptual limitation in the brain. We can’t help it.

In particular, congruency is easier for us than non-congruency. Finding same matches is just easier for us. Sequence of one, two, three is just easier for us. It is easier for us to parse.

Having played quite a lot of Set, I’ll tell you that shading is the hardest of these to parse for typical human players. Human cognition clusters this stuff, and it’s probably driven by the way in which we think, by the chunking processes that our cognition functions off of.

So that means that a player who focuses first on shape-difference sets might actually be disrupting the default human algorithm by destroying viable sets of congruity that remain in the deck. Optimal human strategy is about increasing the entropy of spreads.

If you start playing with novices, this would be the first set they tend to pick. It’s an easy one to see. One, two, three, all the same shape, all the same color, all the same. Congruity popping up, numbering order popping up.

They’re far less likely to see this set until they’re an expert player. It’s just the way it works.

What’s happening here is that there’s a form of indeterminacy being introduced into the algorithm that is basically in our brains. This is not unusual. There are many forms of indeterminacy that end up affecting computational resources.

What I just described are two heuristics that have differing computational resources depending on whether we are a human or a computer player. There are many others.

Input randomness: this is where statistical variation in the landscape of the system’s problem, think a different Mario level, affects what our strategies might be.

Output randomness: this is where we say we are not going to simulate down to the level of the coin flip. RPGs: we’re going to roll dice for everything that happens below the level of swinging the sword. We roll dice for that and randomize rather than simulate. This forces contingency planning and probability estimation; in other words, indeterminacy.

Hidden information effectively creates bounds on the indeterminacy that we have about the mental model that other players have formed. What cards do they have in their hand? For a computer, that can be dealt with by increasing raw search, but that tends to not be available to a human.

Then there’s literal non-computability, where the boundaries of what we can do as humans around the time it takes to perceive something—which is on the order of two to five milliseconds, depending on which cog-sci experiment you want to believe—reaction time, which is on the order of autonomic sub-265 milliseconds, and conscious thought, 265-plus milliseconds. Those are fairly hard boundaries.

We can train autonomic to a degree, but not too far.

Execution time starts being indeterminacy introduced by things like, how responsive is the button on my fighting-game controller? All kinds of indeterminacy start getting introduced, and these might analogize to computational complexity, but they aren’t it. They’re something else. And yet they introduce that quality that is trying to be called D, or depth.

That leaves us with a question: as a designer, for me, what is depth about?

Is it about the actual complexity of the game? Using NP-hard systems, or actually any system above PSPACE-complete, is a proven useful tool for me, but is not in its own right going to just provide depth.

A great example of this is a system like minimum cut, which is an NP-hard—it’s one of Karp’s 21 NP-hard problems—but it’s simply the problem of running through a graph, running through a field: there are dots and edges, make a line that cuts through every edge as efficiently as possible.

We do this every time in a game we run through a field with enemies, trying not to get hit. But we also all know it’s really easy to make that game and have it not be fun or deep at all. So just having computational complexity is not necessarily sufficient.

If it’s about learning more ways to approach the game, which is kind of suggested by Lantz et al., then we can’t leave out the question of how the player learns these, which isn’t in the model. We can’t leave out that question of building the mental model and thinking about the other player’s mental state as part of the game.

Lastly, the question of building that mental model, and the term here that often gets used, particularly in the fighting-game community, is the notion of yomi, which is a Japanese word that basically means building the mental understanding of something or someone else.

Bear in mind, we’ve only talked about adversarial games, not even about co-op games, where the building of mental models of teammates is incredibly critical and a massive, massive driver of what we know of as fun in the game.

So I end up playing, after all this experimentation, with: could we use things like formal grammars to find different takes on what depth could be? Could we just count the number of iterations and possible nodes where parity is not negative one or one, and where the parent is not also indeterminate trivially, so that we could capture complexity and discard trivial branching?

Maybe that would capture these non-computational forms of complexity. I don’t know. I don’t know a good way for us to assess that when looking at a game design.

Could we look at it in terms of the number of hidden affordances or possible actions? That moves the complexity question to perceptual problems. The challenge there is that we look at something like AlphaGo, which clearly found heuristics and strategies that we were completely unable to perceive. That raises the question of, well, as a designer, how do I create those intentionally?

That does not give me an answer. The number of intents that are possible for a player to have, in other words. And I still end up at a loss as a designer on how to create a situation like that.

All of that is relevant because of this famous moment in esports history. How many of you have heard of Moment 37?

Okay, so I’ll have to explain it.

Moment 37 was a championship-tournament-level game between Daigo Umehara and Justin Wong, two of the top Street Fighter III players in the world. Justin had been playing very, very well. This was the final match of a best of three.

Justin, if you look here, you can see that Justin was playing Chun-Li, has plenty of health left. Ken has a pixel left. Any tiny contact, game is over, Daigo loses. Pretty bad situation for Daigo.

Daigo is getting pretty pissed off. He’s visibly angry at this situation. The commentators notice it. Meanwhile, Justin is extremely confident. He’s managed to whittle away at Daigo through the entire match.

Daigo arrives, and as he tells the story in his own words, effectively, completely intuitively, using an inborn heuristic, completely intuitively arrives at the conclusion that Justin is going to attempt to finish this not in what you might call a low-risk way, by whittling away the last pixel in an undramatic fashion, but instead is going to go for a big finish by using a powerful super move that has 15 separate blows in it, any one of which would be fatal.

This would result in a massive ending, and the whole crowd would go nuts. That’s a very human thing to do, right? “Oh, I’m not just going to kill you. I’m going to destroy you.”

Daigo arrives at that mental model of his opponent and anticipates that his opponent is going to do that move. That move does not have a particularly visible warmup.

Daigo manages to become aware of the move happening within the space of a frame or two, which is the kind of accuracy, execution accuracy, that is demanded in order to pull off what he did: to position himself in a pixel-perfect location on screen within a seven-millisecond window and then execute 15 perfect parries with frame-level accuracy of seven milliseconds each, which is almost superhuman.

And so Justin’s killer move went away. It was 100% blocked, followed by Daigo executing his own super attack and pulling off the big finish to win the match.

It is the single most famous event in esports video-game history. And the question of whether this was depth, I think, if you ask a player, they will say undeniably. But I do not think it’s well captured by our current formalisms around what exactly depth is in terms of computational complexity.

It doesn’t help me, sadly, necessarily make more games with a computer leveraging the tools of AI, as opposed to making games the way I have until now, leveraging rules of thumb. Because this is a phenomenal comeback moment, one of those particular gameplay traces through indeterminacy that we as humans love.

In the end, we might build that BNF grammar of games, which I’ve been trying to do for over a decade. And I think we have to face up to the fact that it might tell us jack squat about how to actually achieve the goals that we as designers pursue when creating games that entertain and teach players.

On the other hand, I’m kind of glad that these formal grammars end up full of things like mind, experience, body, and perception. Call it squishy stuff. Because that makes my job less vulnerable to the hypothetical game-designing AI of the future, because I am fairly confident that AI isn’t modeling any of that anytime soon.

That implies that depth for us probably is going to mean all of these kinds of things, all of these loopholes. And as somebody who is a formalist, I do believe there probably are rules of thumb underlying all of these things, but we’re not likely to find them solely within mathematical or computational fields.

I find that reassuring. It leads me on an adventure of expanding the game loop into all of these other fields instead: haptics and mythology and dynamics and meditation and sports training and zones of proximal learning and human hierarchy structures and all kinds of wonderful other things that become entire academic disciplines. Cultural anthropology, cinematography, semiotics, you name it.

What that suggests to me is that after spending a decade on grammar, I think I might be ready to move on and start thinking instead about a step beyond grammar. It might be time for us to start thinking about, instead, a poetics of play.

Thank you.

HOST: Do we have any quick questions? I’m going to do one, two questions at most. No? All right. Well, let’s go ahead.

I guess I have two questions. First, I’m sorry that you couldn’t make it in person, but we very much appreciate you taking the time to talk with us today.

Do you have any questions for us, or things that we should certainly care about or worry about that we’re not currently worrying about? Is there research that maybe could be happening which might be relevant to you, or that you would like to throw a bomb at or something?

RAPH KOSTER: First, I do think that I am not a BNF grammarian by any means, and I do know that that kind of thing is absolutely more in the bailiwick of academia.

So one direction that I do think is interesting: there have been interesting gaps and divides between game studies folks, what I would call industry-practitioner game grammar folks. I would name Stephane Bura, Tadhg Kelly, Dan Cook, Richard Garfield, and Elias, Skaff, and Gutschera, and so on, as people who are coming at this from the industry side, and often with a decently high level of mathematical skill and awareness.

But I do think that there are interesting canyons in between the game studies folks, the computational modeling folks, and the practitioners who work on game grammar, as well as interesting bridges there.

So I applaud the idea that we should continue to dig in there and keep exploring some of those things. I think I personally would love to see some of the academic rigor, and frankly resources and knowledge, brought to bear on something like an actual BNF grammar of what games are like, as opposed to just what game content is like for a particular game.

That’s fantastic for level designers, but not necessarily for those like me who are attempting to create game systems ex nihilo, from nothing.

That’s one thing.

I think another thing that I would just urge is the ongoing, and I would say necessary, work of specialists in individual fields moving towards what I would call a resilient worldview of how these different fields and the bodies of literature within them are often full of different kinds of formalisms, even if they aren’t necessarily mathematically expressible in the usual ways.

I think moving axioms across fields that seem wildly disparate is often incredibly illuminating. I would love to see more of that coming out of, well, frankly, out of all of us. Out of all of the aforementioned groups.

If I had a particular project personally, I wish one of you would come up with a tool, or even a set of rules, that I could use to sanity-check a game prototype or idea so that I can early-out of the process of game development earlier.

All of this investigation for me has given me a whole bunch of tools that do that, and it’s made my game design practice effectively more efficient. I now create more games than I can publish, actually, realistically.

But that tool is vital to innovation and the refreshing of the field. Historically, game design has proceeded through apprenticeship and rules of thumb. So I think that would actually be a really significant contribution to the field.

The only request I would have along the way is: please don’t solve games in the process and render them all boring. That would be bad.

HOST: Okay, I think we get to talk. Thank you so much.

RAPH KOSTER: Thank you.

Original essay notes

These notes were what eventually became the presentation. They include some dead ends, some stuff that I ended up leaving out altogether, and also have at the very end my first notes on a BNF grammar for games.

Suppose you take a simple game like flipping a coin. There is a rich set of mathematical stuff behind it, but it boils down to a binary outcome. Most games have rich stuff behind them, but boil down to binary outcomes.

Victories are generally measured at an end of an iteration process. One common victory condition is to cause the stop to the iteration process. This can take the form of blocking all opponent’s moves.

In the event that the iteration process is of fixed length and cannot be stopped, the point is naturally arrived at by iterating completely through whatever is used as the counter. For example, each player may have a fixed number of turns. “Best of three matches of rock paper scissors” is an example of this.

Or there may be a fixed number of spaces on which to place a counter, as in the game of Reversi. The game always proceeds through precisely the same number of turns.

Or each player may have a fixed number of tokens all of which may be placed.

Let’s term all of those bounded games, and that number of turns to be the bounds of the game.

Now, let’s generalize outwards. There may be some invisible or visible counting system, which we can call “victory points” or vp for convenience, and the game is bounded by reaching this arbitrary figure. Many games may bound at merely reaching one – as in Connect Four. In fact, the case of the bounded game is simply one where the number of victory points is determined in tandem with the bounds.

This then implies that games can have either binary or ternary outcomes, with the ternary choice being a tie.

In a two player game, the basic scenario works this way. Either the iterated rock-paper-scissors or Othello can both be expressed as the win condition being vp > bound/2. In the case of an even number for the boundary, ties are possible, with vpa = vpb = bound/2. In the case of an uneven number, there is no even split, and there are only two possible answers to the overall game process.

In the case of a three player game, these change to vp > bound / 3 and vpa = vpb = vpc = bound/3. We can generalize this to vp > bound / numplayers for a game with binary outcome; for each player, the result is either true or false. A three way tie in a game now demands that the boundary be a multiple of three.

We can then determine whether a game is binary or ternary simply: if the boundary is perfectly divisible by the number of players, it can reach a tie state and therefore return an indeterminate value, though of course many of the possible outcomes could include one of the possible players achieving a vp > bound/numplayers. If the boundary is not perfectly divisible, then it is impossible for it to reach a tie, and always outputs a binary result.

number of playersboundaryeven split
26432ternaryties possible
36421.33333binary
36923ternaryties possible
46416ternaryties possible
26532.5binary

For a binary game to support varied numbers of players, it must have bounds that are perfectly divisible by each number of players; e.g., either the bounds are different based on the number of players, or a common set of bounds is used regardless of number of players, and it is a figure that is perfectly divisible by all the possible numbers of players. For a binary game to work for both head to head and three player, the bounds must not be divisible by 2 or by 3, or else it will be binary in one case and ternary in the other and admit of ties.

210.5binary
210.5binary
310.333333binary
221ternaryties possible
320.666667binary
231.5binary
331ternaryties possible
242ternaryties possible
341.333333binary
252.5binary
351.666667binary
263ternaryties possible
362ternaryties possible
273.5binary
372.333333binary

 

In some sense, games are generators of outcomes, distillers of processes back down to yes and no and (sometimes) maybe.

Since games are made out of games, it follows that each given subsystem in a game can be broken down into a binary or ternary outcome. And indeed, the idea of “solving” games via full searches of the entire possibility tree works this way. You can “unroll” all the choices that are made, by atomizing the game, and see each decision made as a step along a branching tree.

With some foreknowledge of the tree, a player (human or artificial) can make choices that are steps on the path towards a particular outcome, and can prune whole large swaths of the tree.

A given binary choice has implications not just in the current choice, but in affecting the odds of a given outcome later on.

If two players both always choose optimally on their turns because they have full knowledge of the tree, they have mapped the entirety of the possibility space. If the game is binary, it’s a guaranteed win for one player enforced by the structure of the game. If the game is ternary, it’s either a guaranteed win or a guaranteed tie.

In an unsolved game, the player has limited look-ahead. Each will always choose the branch that leads to maximizing the odds of arriving at a win state for that player.

This forcing down the wrong path can therefore be thought of as a parity problem… As players march down the tree, they gain or possibly lose victory points. Any choice after which their victory point total exceeds that of the other player puts them in a positive state; any choice which puts them below or at the other player’s total leaves them in a negative state. In a binary game, when the bounds are reached, if you are at 1, you win, and if you are zero, you lose. A ternary game permits both players to lose.

A win state isn’t necessarily the last leaf on the tree. If what is left below a leaf cannot alter the final parity outcome, then all subsequent choices are irrelevant.

In some games, given a zero-sum victory condition, each player playing optimally at every step will lead to a loss that is inbuilt in the structure of the system. This result can then be “rolled up” to the earliest point in the tree where we can see that outcome become determined. With perfect knowledge, we can “early out” at that point and the player who has been forced down the wrong path can concede. A game like tic-tac-toe is considered solved because the outcome for optimal players is determined.

In a game where victory points aren’t distributed evenly, a node in the tree may have branches below it where a later branch has many positive parity nodes and another branch has less positive parity nodes, because gaining a lead in vp’s can mean an unassailable positive parity.

 

A node as win, lose, tie, or indeterminate. Are tie and indeterminate the same thing really? If so, that means that indeterminacy at a node level is the same thing as a ternary game. Are there tactics or techniques for dealing with ternary situations? Odds of a tie fall with how the scoring system is constructed – the more VPs the lower the odds of a tie, right? Though depending on how they are allocated (bell curve?) it might flatten out?

 

Evaluating stuff lower down based on assessing odds of one branch leading to parity. Creating internal victory points, call them “position” as in good or bad position.

 

Multiple victory conditions effectively mean navigating multiple choice trees at once. Cognitive load caps your lookahead. This is why orthogonal rules are so valuable.

 

In some games, moves exist solely in order to swap parity positions with the other player. Pictyure a game where whoever is player 1 will win, because of a first mover advantage or some other determined setup. If a player can pass in such a way that they now take the place of player 1, and shift the win scenario onto them, that can be thought of as a parity shift.

 

Consider if the move made by an opponent is unpredictable (random, let’s say, perfect odds of choosing left or right). Model it out.

 

Pruning the tree based on topological symmetry, as in Othello or tic tac toe.

 

Players look at choices and select based on odds to win, not degree of victory. They therefore weight each node with percentage chances that are an aggregate of what is beyond.

 

Think about Set. There are a series of rules for building a set… all the same, all different, on three axes. Humans find certain types of congruency easier to see. All the same on any axis is easiest to match. Next easiest is sequence (1, 2, 3). Next is probably shading set. Shape set is hardest. Human thinking groups, rather than run brute force across a 12 card spread and all the possible algorithms, and most players preferentially start with that order. A player who focuses on shape difference sets first may well disrupt the strategies of other players by destroying the viable sets they have remaining in the deck.

If a computer were searching and had image recognition capability, it has equal capability to group things. It would have no preference in algorithm other than that which is hardcoded in its if statements, and it would simply match every card to every card using brute force. If competing with other computers or players of equal computation and perceptual ability, choice of which pattern to match against first is the differentiator. The strategy would lie in selecting an algorithm based on what would be more likely to reduce the types of sets that opponents search first, so that their computation speed on average tends to get longer. So if all computers search color first, the computer that searches for patterns that tend to reduce color commonality sets would gradually come out ahead. In general, a player who searches noncongruity first benefits from a noncongruent (high entropy) spread, and they can work to maximize noncongruent spreads via which sets they choose to call from those available.

If different computer opponents kept doing this, then to execute this strategy they need to ascertain what algorithms an opponent is favoring. This involves building a mental model of the opponent’s strategy – which requires greater computation, but may pay off overall.

An opponent who selects pattern preference randomly won’t be predictable in this way.

In practice, Set is played on a timer, so you don’t get to consciously engage in that strategy. Instead, the game likely simply favors those who practice perceiving noncongruity. But one can envision a turn-based Set without the timer element where strategy would arise from card-counting and odds calculating what spread you are leaving the opponent with.

 

We could think of depth as being size of the tree, but that’s false because any large bounds create that. We could think of depth as meaning keeping the game indeterminate until the last possible moment, but it’s easy to think of very shallow games that do that – plain old random outcomes at every point do. Instead, since it is a characteristic of choice, the metric has to be consequential choices. What makes a consequential choice? One that entails risk or tradeoffs; in other words, the number of indeterminate or tie nodes in the lookahead space?

 

Lantz et all suggest that d is a quality of the number of intermediate strategies, or heuristics short of optimality, that a player can discover as they proceed to complete mastery. A game you can play optimally or near optimally with a computationally cheap strategy lacks d. A game you can’t discover new strategies in will also lack d  because it’s based on skill chaining or learning. In a sense, depth by their criteria is based on lemmas, on plateaus. But they don’t arrive at a way to actually measure strategy strength, much less how strategy is unveiled over time in the proper order. They rely on computational resources as an axis, but this doesn’t apply to human cognition in a regular linear way.

They make the point that heuristics rely on regularity within the tree structure. “Control the center” in chess is shorthand for “stay in this area of the state space.” A game with too much regularity, however, falls prey to degenerate strategy. A game with no regularity cannot have any heuristics. Therefore there is a sweet spot in terms of regularity on the nodes. They arrive at the conclusion that a mixed amount of regularity must therefore alternate regularly between heuristics and raw brute force search, and that is what conveys the feeling of depth.

Also see Danc’s comments at http://gamedesignadvance.com/?p=3124 and Frank’s note “Heuristics are ways of compressing and speeding up search. Every heuristic is a shortcut that reduces the amount of raw search you do. Intuitively, in a game with a high degree of depth, you would expect strategies in the middle ranges to have a balance of heuristics and raw search, because the places they do raw search are the places where they can be improved by additional heuristics.” So the ladder would be starting with raw search and little lookahead, then converting to heuristic, so you can more raw search. I think that logic is missing heuristic abandonment, which is crucial – dismantling a prior heuristic in order to build a new one.

Need toy model game with which to show that. Tiny Castle?

 

So how do you design for mixed regularity? What does mixed regularity look like? If we made a map of state spaces that showed clusters of configurations, and the high level board eval led us to see those as common groupings, we could probably abstract board configs into “higher-level games” or dense areas… places where many paths in the state space converge and come apart… almost like scale free network maps? Maps that fold over one another as signs of depth? Don’t unroll, teleport to congruent layouts?

 

This relates to this somehow. https://en.wikipedia.org/wiki/Parity_of_a_permutation

 

Is the stuff at the top wrong? Are games actually ALL ternary logic? https://en.wikipedia.org/wiki/Three-valued_logic After all, the Unknown value for truth is critical to the sense of depth. There are a LOT of permutations of the truth table for ternary logic which means over 16000 operators… http://wiki.c2.com/?ThreeValuedLogic

 

game → game + result

result → system( action ) = ( ( -1, [ 0,] 1 ) | 1 )

system → side + side { [, side] }

side → player + mechanic + statistic { , statistic }

player → ( mind + experience + body | AI ) + perception

mechanic → rule { , rule } + statistic { , statistic }

rule → token { , token } expression { , expression } statistic { , statistic }

action → verb [ { + action } ]

verb → intent + input

input → affordance + action [ + game ]