Comparing games for strategic depth

How do we compare games for depth?

I aim to assign a numerical scale to game depth, and walk through a few examplesto demonstrate the effctiveness of the scale.

The Algorithm

GameDepth = 100 * sum(TurnDepth) / Turns

TurnDepth = H * (MoveScore / AllMoves) ^ (1 / Depth)

M = MoveScore ^ Depth

MoveScore = sum(E) for all AlternateMoves

AlternateMoves = Legitimate moves - 1

E = Execution factor

H = Hidden information factor

Definitions

Move

A move is how a player changes the state of the game. Moves are the smallest possible interaction the player has with the game. During some games, players might get to make multiple sequential decisions, these are all seperate moves.

In most games, there is a discrete move set. Like in chess, you can only move the pieces you control to certain locations, based on the piece type. In tic-tac-toe, you can only place the symbol of your side in one of the 9 boxes.

In some games, particularly physical games, there are an infinite number of ways to transform the game state during your turn. In this case, a move is a group of ways to change the game that have the same immidiate goal. For example, in pool, shooting the 5 ball into the corner pocket and leaving the cue ball in a specific place is one move. If you leave the cue ball in a different place, that is a different move. If you ignore the placement of the cue ball, that is another different move.

If there are multiple moves that accomplish the same immidiate goal, or multiple move that are indistinguishable in the long term, those are all the same moves.

Turn

A turn is the time when one player makes exactly one move. Some games are turn-based, and the turns are easy to isolate.

Games that are not turn based may be evaluated in whatever manner is appropriate. A turn might be a play in football, or a possession in basketball.

Some games resist the turn classification. If there is no other way to choose, turns are simply the smallest increment of time in which a player could be expected to make a move. If you wish to analyze the strategic decisions a batter makes while a pitch is on the way in baseball, you would have to choose a very short time scale as the basis for your turn.

Legitimate moves

Legitimate moves are those that cannot be ruled out easily. In order to determine of a move can be ruled out, simply play the game out as far as you need to to explore the consequences of this move. Any move that cannot result in victory is ruled out.

There is no restriction that every players perception of game depth be the same. A more experienced player might rule out more moves, or fewer. The number of legitimate moves can change as you gain familiarity with a game.

In the same manner, a better player might be able to see that all moves are wrong, by looking further into the future. In the case that there are no legitimate moves, the turn depth is 0.

Depth

How many turns forward is the player looking in order to figure out which moves are legitimate. Does not include that player's turn.

Alternate moves

This is all legitimate moves not chosen by the player.

All moves

Simply count every valid move a player could make every turn.

Execution factor

The execution factor is the likelyhood that a player will sucessfully complete the move in question. It is always a number between 0 and 1.

Hidden information factor

The hidden information factor is the portion of all information about the game state which is hidden from the active player. The plans of opposing players are generally considered to be public information, although circumstances such as limited game literacy or simultaneous turns may render that information hidden.

Examples

Tic-Tac-Toe for a child

For this examination, we will assume the player is able to think forward only 1 turn. Once you have "solved" tic-tac-toe, the strategic depth is 0. The player has all information, and there is no chance of failing to execute the move correctly.

On the first turn (Player X's turn), the player gets 3 legitimate moves to choose from. The corners are sides are indistinguishable. That turn has a depth of 2 / 3. Most people select a corner, so our X player does that too.

The second player is forced to play in the center or the opposing corner out of 5 possible moves, so that turn scores 1 / 5. O goes in the center.

Player X again has his pick, being able to force a draw from any position, so his turn scores 3 / 4. X chooses a side adjacent to his first placement.

Turns 4, 5, 6 and 7 are all forced blocks, and score 0.

Player O realizes that the game is over, so the turn depth is 0 for the last 2 turns.

The game depth is: 100 * (2 / 3 + 1 / 5 + 3 / 4) / 9 = 18, which is not too bad. Keep in mind, this is the score for children who can only see 1 move ahead, so they have not mastered tic-tac-toe completely, as you can get caught in a fork.

Chess for an expert

For someone who has played a great deal of chess, there are significant portions of the game that are memorized. A game is broken into the Opening, Middle and Closing portions. The game averages 40 moves (Source). Chess lacks any execution elements and has no hidden information. A chess expert is able to think ~10 turns ahead.

The opening book accounts for the first ~7 turns. These turns are memorized. In the minds of the participants, there is a direct contingency for opponent moves, so these 7 turns have a turn depth of 0.

The midgame is the most depth-rich part of the game. At any given point, there are likely to be as many as 6 legitimate moves and 50 possible moves. That gives us a depth of: (5 / 50) ^ (1 / 10) = 0.79. The midgame takes all the moves that aren't in the opening or the ending, so around 28 per game.

Endings can consume a lot of moves, but may also be skipped when both players understand how the game will play out. I will assume that the ending has 3 legitimate moves and 20 possible moves, giving it a score of: (2 / 20) ^ (1 / 10) = 0.79. I estimate the endgame takes around 5 moves, which accomodates long endings, short endings, and those which don't happen due to concession.

Chess gets the overall score of: 100 * (0 * 7 + 28 * 0.79 + 5 * 0.79) / 40 = 65.53