لطفا منتظر باشید ...
Decision Trees
As a formal approach to understanding games, game theory looks at games as a series of strategic decisions made by the players of a game. What does it mean to reduce a game to its strategic decisions? One common game theory method is to create a decision tree for a game. A decision tree is a branching tree-style diagram that outlines all of the possible moves a player can make in a game. Decision trees are a common way of flow-charting interactive experiences. For example, if you are programming an interactive story that has a hypertext structure, you might draw a diagram that shows all of the links between the different parts of your story. This kind of diagram would be a decision tree.
Creating a decision tree for a game is more complicated than creating a decision tree of a hypertext structure. The difference is that in a typical hypertext, the links and the actions that a player can perform at any location in the larger structure do not change as the participant moves through the structure. A reader's first choice in a hypertext structure does not change the way that the other hypertext links function. The only thing that changes is where the reader is positioned in the structure. A game is more complex. In a game, what you can do at any given moment depends on what has already happened in the game. At the beginning of a game of Chess, for example, you can't move either of your rooks because they are both blocked by pawns. Later in the game, you might be able to move your rooks if your pawns have been maneuvered out of the way. The complexity of games leads to a system of many possible actions. Which actions can happen at a given moment is contingent on the current state of the game. Because Chess is a complicated game to diagram as a decision tree, let's start with a simpler example: Tic-Tac-Toe. In Prisoner's Dilemma, a book about game theory and its historical context, writer William Poundstone leads us through the process of making a decision tree of the game of Tic-Tac-Toe. Ticktacktoe starts with the first player ("X") putting a mark in any of nine cells. There are consequently nine possible first moves. The nine choices open to Player X on the first move can be diagrammed as nine lines radiating up from a point. The point represents the move, the moment of decision, and the lines represent the possible choices. Next it's Player O's move. There are eight cells still open—which eight depending on where the X is. So draw eight secondary branches at the top of each of the nine primary branches. That leaves seven open cells for X on his second move. As the diagram of possible moves is continued upward, it branches like a very bushy tree. As you continue the process, you will eventually diagram moves that put three markers in a row. That's a win for the player who moves. It's also the termination of that particular branch in the diagram, for the game ends when someone gets three in a row. Mark that point (call it a "leaf" of the diagram) as a win for X or O as the case may be. Other branches of the diagram will terminate in a tie. Mark them as ties. Obviously, the game of ticktacktoe cannot go on forever. Nine moves is the maximum. So eventually, you will have a complete diagram of the game of ticktacktoe. Every possible ticktacktoe game—every game that ever has been played or ever will be played—must appear in the diagram as a branch starting at the "root"(X's first move) and continuing up to a "leaf" marked as a win for X, a win for O, or a tie. The longest complete branches/games are nine moves long. The shortest are five moves (this is the minimum for a win by the first player).[2]
Creating a decision tree can be a powerful way of understanding the formal structure of a game. It is in essence a way of mapping out a game's formal space of possibility. For a simple game such as Tic-Tac-Toe, the complete space of possibility can in fact be diagrammed. However, not all games can be mapped out in this way. Being able to make a decision tree of a game or other interactive structure implies that the decisions participants make are discrete decisions that lead to knowable outcomes. For example, a game that involves physical skill, such as American Football, does not have self-contained moments of decision making that can be diagrammed like the alternate turn-taking of Tic-Tac-Toe. Instead, the game exists as a continuous flow of action. When the ball is hiked, a quarterback does not take a single discrete action. Instead, the game flows forward in a complex web of activity. Perception, movement, and the granularity of the real world creates a non-discrete game space.
Although the moment-to-moment play of Football is continuous, the game can be broken down into a system of separate plays. Does that mean it is possible to create a decision tree of Football by widening the frame of analysis, so that each decision point on the chart represents the choice of a play by one team's coach? The answer is no. The problem with this proposal is that to create a decision tree, the result of a decision needs to be a knowable outcome or set of outcomes. Think about a game of Tic-Tac-Toe. When a player makes a decision to place an X or an O in a particular square, there isn't any doubt that the player will finish the action and make the mark. On the other hand, just because a Football team picks a certain play does not mean that they will be able to successfully complete it, or complete it in a way that can be predicted with any accuracy. The outcome of picking a particular play in a Football game could result in a yardage loss or gain, a penalty, a fumble, a reversal, or a touchdown, making it impossible to diagram the outcome in the same way that we could Tic-Tac-Toe. (Note also that "X and O" play diagrams that show where players will run on certain plays can be used to schematize the play of Football. But these play diagrams do not qualify as decision trees.) What kinds of games can we turn into decision trees? Decision trees work for any game that has the following qualities:
Time in the game takes place in turns or other discrete units.
Players make a finite number of clear decisions that have knowable outcomes.
The game is finite (it can't go on forever).
Although this disqualifies many games (including Football), it does include a wide variety of games, such as turn-based strategy games like Tic-Tac-Toe, which clearly fulfills all three criteria listed above. What about Chess? Chess takes place in turns and decisions have clear outcomes, but is it finite? Chess might seem like an infinite game (imagine an endgame with two kings shuffling back and forth between the same squares forever), but in fact there are rules that resolve the game in a stalemate when a certain number of moves have elapsed without a capture. How about a game such as Chutes and Ladders? It seems to fit the three criteria, but it does have a random die roll. Could we map it out with a decision tree? Surprisingly, yes we could. The first point or "root" of the decision tree would have six branches coming out, depending on what the first player rolled. Each of those six branches would have six more, depending on what number the next player rolled. And so on. Of course, there would have to be a different tree for a two-player game, a three-player game, and a four-player game. Although the decision tree for games as simple as Tic-Tac-Toe might seem large, a decision tree for a game such as Chess or Chutes and Ladders would be extraordinarily vast and complex. Remember that the decision tree contains all of the possible games that have ever or will ever be played. The decision tree for Chutes and Ladders would have to contain every possible die roll at every possible moment in the game with every possible arrangement of players on the board, in every possible sequence that could logically occur. The decision tree for Chess would have to contain every possible move and every possible response to every possible response to every possible move. The decision trees for these games would be immense. According to Poundstone, if a decision tree for Chess were graphed out on paper at a legible size, the diagram would span the solar system. If decision trees for games are so unwieldy in the real world, how are they possibly useful for game designers? Decision trees are more theoretical constructs than engineering tools. At the same time, the ability to understand what a decision tree is and how it works is crucial to game design. Why? Because a decision tree is also a diagram of the formal space of possibility of a game. Being able to conceptualize the space of possibility you are designing is an important game design skill.
Even though true decision trees are usually impossible to create, often you can create very useful decision trees for sections or aspects of a game. For example, say you are designing a mis-sion-based strategy game that contains many level "missions" that the player has to complete. A player can succeed or fail at a mission, and the next mission depends on the outcome of the most recent mission. While it might be impossible to draw a decision tree of the battle that takes place within an individual mission, it would be extremely useful to chart out the relationships between missions.
Making a decision tree of the game's missions will tell you, for example, how many missions a single player will play through in an average game. Or it will help you eliminate game designs that loop back on themselves.When you can make use of them, decision trees are a straightforward and useful way of understanding the structure of a game. Perhaps more importantly, however, decision trees are an important part of understanding game theory. [2]William Poundstone, Prisoner's Dilemma (New York: Doubleday, 1992),
