Game AI has always been a popular field with many impressive achievements. Next, I will start writing a series of three posts, talking about some fundamental and important game-playing algorithms.

- Part I — Game Basics
- Part II — Monte Carlo Tree Search (MCTS)
- Part III — Counterfactual Regret Minimization (CFR)

**In Part I**, which is this post, I will explain some of the prior knowledge for game AI. Specifically, I will introduce (1) How to represent a game using computational logical structure (2) Different types of games (3) Three concepts that proven to be important for designing game-solving algorithms.

In Part II, I will present Monte Carlo Tree Search [1,3], a building block algorithm for solving perfect information games like chess and go [2]. In Part III, I will introduce Counterfactual Regret Minimization [6], an effective method of solving imperfect information games like poker [19].

I want to note in advance that I will try to make the concepts more understandable and intuitive rather than striving for rigor. The mathematical language is not standard enough in this post, and please excuse me for this.

The world is full of games, but to solve them with computers, we first need to represent them with logical structures.

**Game Tree**

The first essential structure is the game tree, which represents the process of a game with a tree whose nodes and edges represents states and actions, as explained below in a game tree of Tic Tac Toe with annotations:

Though the game tree looks simple and straightforward, it can model many vital components of a game:

- State
- Player
- Action
- Reward
*R(s, a)* - Turn
- Terminal state (end of the game)
- Decision Sequence
*(sᵢ, aᵢ)* - Strategy
*π(a|s)*, which is a distribution of actions given state. We also use*σ* to denote strategy. - Utility function
*u(s)*, which describes the usefulness of state*s* to a player and can be defined individually.

The game tree grants us a powerful mental and programmatical model to represent the playing processes of a wide variety of games.

In fact, game tree is a simplified and perceptual definition for the extensive-form game [7]. Many important games solving techniques like MCTS, Minimax Search [5], Counterfactual Regret Minimization [6] can be **generalized as a game tree construction, traversal, and node value update process.** In my opinion, I even think the game tree is one of the most important concepts, if not the most.

**Game Matrix**

Game matrix is another way to represent games, which corresponds to the normal-form game [9], as explained below with a 2×2 board of Tic Tac Toe:

As we can see, a game matrix assumes all players act simultaneously. Therefore, to model sequential decisions, the matrix has to expand the game tree exhaustively to cover all possible histories, as shown in the figure above, which makes this representation unscalable for sequential decision games.

However, the game matrix also has its advantages; there are proven methods to find a Nash equilibrium of a game matrix [8]. Nash equilibrium turns out to be extremely useful for understanding the game nature and designing game playing strategies. We will come back to the Nash equilibrium in the later section.

After we know how to represent games, we can step further to categorize them. Here I present three major categories:

## Perfect Information Game

- Every player knows the full decision sequence of the game [10].
- Examples are Chess, Go, Soduku, Tic Tac Toe, where the game board is the whole game state and can always be observed by anyone, and every player action is public.

Note that there is another concept called Perfect Recall, which means every player can memorize every event during the game process, which is irrelevant to the game category.

## Imperfect Information Game

(Opposite of the former)

- Examples are Poker, Mahjong, where you cannot know the opponents’ card stacks.

- In a game with imperfect information, players cannot observe the actual game state
*s*, which means we cannot use*π(a|s)*to represent strategy. Therefore, we introduce the definition of Information Set [23]. We will come back to this topic in Part III of this series.

## Incomplete Information Game

- Players do not have the common knowledge of the game being played, e.g. objectives, rules, and even players.
- Take an example from [11]: Two bidders bid for one item, and the auction is sold to the highest price. However, each player only knows the item’s value for himself, but not the rival’s valuation (lack of common knowledge).
- For a complete information game, we usually assume every player knows the game’s rules and every player’s objective. Therefore, the incomplete information game is indeed more generalized and realistic. Note that the game tree can represent incomplete information by introducing “chance players” [7].

We have learned about the logical structure and categories of games in the sections above. Here we look at three concepts that are behind many game-playing algorithms. In practice, they are often used in conjunction with each other. Understanding them is very helpful.

## Idea-1 Bellman Equation

Bellman equation is the basis for most methods of reinforcement learning. However, surprisingly, it comes from a straightforward definition of the state utility, also known as value function *V*: