>> Why did we jump from the “many heuristics” vision to “one single heuristic”? What I would have liked to have seen is an explanation of this specific point: Why is a game with a shitload of heuristics and no hard calculation considered to have less depth to a game that has both heuristics and calculation?

This is a really good question.

A game with a ton of heuristics would, in fact, have a high degree of d, because the algorithm for describing the best strategy would be very complex.

In a sense, it’s all search. 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.

]]>>> 1) In the first graph, for example, what do you identify with “solution strength” ? [...] If you use a proxy for solution strenght (like ELO), the value is influenced by factors like length of the game (i.e. number of “non-moot decisions) and cycles (A beats B who beats C who beats A).

Yes, by “solution strength” we basically mean rating based on performance in some kind of very thorough tournament. It is true that this leads to potential problems like non-transitive strategies (A>B>C) but we feel this is still the best criteria for evaluating partial solutions in the context of games.

>> 2) Also in the first graph, how do you define a “strategy” ?

You start by choosing a well-defined language for expressing strategies. Every strategy is a complete instruction for how to play the game expressed in this language. In this method you can never look at a complete population of all possible strategies for the game, you can only ever compare the strategies that are expressible in this language. So you would never be able to say anything about the “true d” of a game, you can only talk about the d within language L.

>> 3) It looks you mean something different with “strategy” [...] So a strategy in this definition is an algorithm (possibly time bound ? ) which would output differently based on the resource given.

In this graph strategies are dots, not lines. The x-axis is basically algorithmic complexity. We’re thinking of it as strategies that require more and more computational resources to execute, rather than strategies that give different outputs based on resources given. This is admittedly the least-worked-out part of the whole approach and most in need of additional thinking and clarity.

>> how do we know that there is not a “trivial” solution to Chess or Go ?

In our approach, the discovery a trivial solution to a game would, in fact, cause us to re-evaluate the d of the game and show it to be lower than we previously thought.

]]>>> In both cases the description of how to find the best move is short.

>> But in deep games the best description for finding the best move is long and complicated.

1) It’s subjective, but: How long would the description be for the best move in a deep game? Is the scale for the whole game or an encounter?

2) Search, Heuristic, and semi-ordered. Can I get some real world examples, perhaps jrpg related? I think “Always heal when below 30% health” is a heuristic and “Always heal when below 30% health, unless you’re fighting Biggs” is technically a deeper game. I’m not sure what a useful heuristic size is in order to allow for a semi-ordered game space.

]]>Quick question for clarification. The article states, ‘You can have a game whose solution is arbitrarily difficult to compute without guaranteeing that the game will have the kind of features we are looking for – the capacity to reward life-long learning and support a large, long-term community of serious, dedicated players.’ Are you implying that this feature is ‘depth,’ the topic of the study? It seems you are saying that this feature is desirable and I would agree, but doesn’t the desirability of the feature make it normative and place value on depth?

The criteria Scott provided for meaningful choices in a game and the revisions you added are interesting. Maybe I’m missing something, but it seems that Scott’s definitions were more independent of player psychology than the revisions you provided. For example, the reference to R/P/S choices becoming meaningful when an unknown opponent plays non-randomly incorporates player psychology and understanding the opponent’s psychology. Maybe I struggle with the idea that players and their strategies and choices cannot be separated from human psychology. Similarly, while games are mathematical, the decisions the designer’s make cannot be separated from their psychology.

What makes this discussion particular interesting to me is that the desired state of life, long learning toward mastery (and depth), meaningful choices made while learning for future play, and that in game design that motivates these kinds of player decisions are some of the opportunities in games for education.

Thanks for the clarification.

]]>A quick thing: DanC brought up that whole “candyland” concept – how a child finds candyland to be deep but an adult does not. This is supposed to be evidence that a game’s depth is subjective. I actually think the better way to look at it is that games have an objective amount of depth and different humans, depending on their cognitive ability/skill, are able to reveal more and more of whatever depth that’s there. Candyland is just a more shallow game than League of Legends, so a child (or an adult with adequately low cognitive ability) is unable to discover the limit of its depths. But this spectrum goes across all games, really. Smarter humans are attracted to games with more depth because they solve/semi-solve games with less depth. This does not suggest that the amount of depth a system has changes based on a person’s perception.

FTA:

>The more heuristics a game can support the more you can combine them into better and better strategies and the more you can improve with effort and study. But wait – it’s not quite that simple. Imagine a game in which there was a heuristic that allowed you to play perfectly.

Why did we jump from the “many heuristics” vision to “one single heuristic”? What I would have liked to have seen is an explanation of this specific point: Why is a game with a shitload of heuristics and no hard calculation considered to have less depth to a game that has both heuristics and calculation?

(My argument on this, for the record, is that it’s impossible to make a game that is “only heuristics” yet isn’t extremely random and inefficient.)

Anyway, great article! Sorry I only found it now.

]]>In particular: What knowledge can the player have/gain that reduces the effective branching factor and the depth?

So, in your trivial two-color coin example, the player gains the knowledge that the coin is irrelevant and thus reduces the size of the state space.

This causes us to focus on the question: For a given game, how many such constraints can be found, and how do they impact the size of the game. I’d argue that the best games have many layers of constraints that can be found, but they never reduce the game completely. If I know more constraints than you do, I can reduce what I need to analyze in the game and have an advantage over you.

The question which I can’t (yet) answer is how a machine can find/learn and express these constraints in a compact and usable way.

]]>]]>

1) In the first graph, for example, what do you identify with “solution strength” ?

The “correct” parameter would be the rate of error per decision made, where an error is identified as a decision which does not conserve the game theoretic value (win or draw) of a position.

But to evaluate this parameter you need to know the perfect play in any position, which can only be done for trivial games.

If you use a proxy for solution strenght (like ELO), the value is influenced by factors like length of the game (i.e. number of “non-moot decisions) and cycles (A beats B who beats C who beats A).

2) Also in the first graph, how do you define a “strategy” ?

In game theoretical sense, a strategy is a plan of action for every possible position. This can be modeled as a look-up table (position–>move) or as an algorithm which will always return a legal move when the input is a position.

But the “sTrategy Space” (TS) that you need to observe is incredibly, large.

You can estimate it based on the “State space”(SS) and the “average branching factor (bf).

TS ~ bf^SS

This is much bigger than even the game tree complexity (GT) , which is estimated on the average game length (gl)

GT ~ bf^gl

to give an idea, I took 3 games

TicTacToe –> SS=10^3, GT=10^5, TS=10^620

Othello –> SS=10^28, GT=10^58, TS=10^(10^28)

Go –> SS=10^170, GT=10^360, TS=10^(2*10^170) !!

3) It looks you mean something different with “strategy”.Each circle (which would be a strategy in game theory) is connected by a line; if interpret correctly, then each strategy is this line and it would give different results with different computational resource.

So a strategy in this definition is an algorithm (possibly time bound ? ) which would output differently based on the resource given.

But the issue with this is that it’s implementation dependent; in this case the possible strategies are indeed infinite, so you can’t really find a granularity or a “chain”.

Moreover, you seems to assume that each “strategy-algorithm” asymptotically converges to perfect play; while this is true for alpha-beta or monte-carlo UCT, it is not universal for “any algorithm” (think of “Null Moves” or “Pruning”).

Lastly, it is also possible for two strategies to scale differently with resources, so to “cross” in your graph.

4) I like the analysis of the “high ordered” games with “one weird trick” or “superpowerful heurisic”. Typical examples would be NIM or

BRIDG-IT. But the issue is that the “weird trick” may be there without anybody being aware; how do we know that there is not a “trivial” solution to Chess or Go ? It is very similar to solving P vs NP if you ask me.

First, in our approach, you can theoretically have a rich, multi-step skill chain in a game that is already fully solved. The lower steps in this skill chain are all strategies that are smaller/faster/less-complex than the ones above them. Admittedly, this is a bit hand-wavey at this point, but we are talking about some combination of k-complexity of the strategy itself + time it takes to run + memory required. This process of evolving more and more complex, effortful, and powerful strategies (roughly) reflects the learning process that human players experience in their journey into deep games.

This becomes an issue when there is a strategy that produces perfect play which is smaller/faster/less-complex than lower steps on the chain, all these lower steps would be wiped out and the d would be shown to be smaller, in fact, than previously thought.

In terms of avoiding fractal recursion, non-transitive strategies, and other pitfalls of practical application, the main idea is that there is no pure, abstract version of the d of any game, it never exists outside the context of a specific, well-defined set of conditions, including most importantly a language within which to express strategies. Therefore you can only measure the d of a game for such-and-such language and conditions, but this still gives you a way to compare games to each other and make hopefully useful observations.

As to whether such a measure might be discovered for an actual, real-world, deep game, the short answer is it probably can’t? We are in the early stages of trying to do it for smaller games, notably Blackjack, and we think it will be interesting to, for example, do it for tiny versions of Go (2×2, 3×3, 4×4, etc) and then try to extrapolate from that to implications for real-world Go (and beyond.)

]]>