《The-Game-of-Chaos.pdf》由会员分享,可在线阅读,更多相关《The-Game-of-Chaos.pdf(6页珍藏版)》请在三一文库上搜索。
1、The Game of Chaos Peter van Emde BoasEvert van Emde Boas Abstract Game of Chaos is a red sorcery in the oldest of all customizable card games: Magic, the Gathering, trademarked by the Wizards of the Coast inc. Successfully casting this spell enables the caster to engage the opponent player in a pote
2、ntially unbounded series of coin-fl ip games about life. Initially the ante is one life. The winner decides to stop or to play a next round. However, for every next round the ante in lives is doubled. This will ensure that the game will be terminated as soon as the loser has his total amount of live
3、s reduced to zero or lower, since terminating the game of chaos at this point yields immediate victory of the duel. Given the inherent symmetry of this game the question is whether it off ers the caster any strategic advantage to play it.For every possible play which yields a positive outcome there
4、is a corresponding play which yields the same outcome to his opponent. Consequently the utility value of this game should be zero. We invoke elementary game theory in order to illustrate how this theory does confi rm this intuition. However, the same theory can also be invoked in diff erent scenario
5、s, like Thorgrims last stand where the utility value can be shown to be positive. The illustrations for this note are contained in the powerpoint presentation which is available in pdf format at the website of the fi rst author. See The game of Chaos for 12 pages displaying the sheets presented at t
6、he 1999 Dutch Mathematical Conference in Utrecht. Contents 1Game of Chaos - why play it at all?2 2Von Neumann - Morgenstern Utility Theory4 3Utilities for the game of Chaos5 1 1Game of Chaos - why play it at all? Game of Chaos is a red sorcery in the oldest of all customizable card games: Magic, the
7、 Gathering, trademarked by the Wizards of the Coast inc. The card is shown on the sheet The game of Chaos. For readers not familiar with this game: it is a customizable card game which means that every player com- poses a deck of cards to play with from a large collection of available cards. Purpose
8、 of the game is to defeat your opponent by reducing his number of lives (initially 20) to zero or less. You can damage your opponent by summoning creatures which may attack your opponent or by casting other spells which will harm him or her in some other way. You defend yourself against your opponen
9、t by summoning creatures which will block the attacking creatures (and which may get killed, destroyed or buried in the process), by countering spells cast by your opponent, by casting spells which will protect you (or your creatures), or by invoking eff ects which will repair and heal damage suff e
10、red previously in a turn, or which may damage your opponent or his or her creatures. Each spell you want to cast must correspond to a card you currently have in your hand, and it can be cast only once. The cost of using a card (casting cost) is expressed in units of mana, which is obtained by “tappi
11、ng” lands you have played earlier in the game. Mana exists in fi ve colored fl avors (red, white, black, green and blue) and a generic version. The same color labels are ascribed to most spells; a red spell will require an amount of red mana together with another amount of generic mana. Hence it is
12、not only a matter of having enough lands or other mana sources; they also should be of the right type. Overall the rules of the game are quite complex, and subject to regular revisions, partly due to the introduction of series of expansion cards, and partly due to an increased sensitivity for potent
13、ial weak spots in the game. At present the sixth edition of the game is about to appear. However the basic principle of the game is expressed by the slogan that for almost every rule in the game there exists a card generating an exception against this rule when successfully cast. A rather complete s
14、et of rules for the fourth edition can be found in 2. The Game of Chaos is just a single card in the game, which introduces in fact a subgame which may, but doesnt necessarily terminate the entire game. Successfully casting this spell enables the caster to engage the opponent player in a potentially
15、 infi nite series of coin-fl ip games about life. Initially the ante is one life. The player fl ips a coin and the opponent calls head or tails while the coin is in the air. If the outcome is correct the player gains one life and the opponent loses a life. Subsequently the winner decides to stop or
16、to play a next round. However, for every next round the ante in lives is doubled. This will ensure that the game will be terminated as soon as the loser has his total amount of lives reduced to zero or lower, since terminating the game of chaos at this point yields immediate victory of the duel (dis
17、regarding for the moment the possible eff ect of damage prevention or healing spells in the game. In fact under the new rules for the sixth edition of the game this problem evaporates: one no longer has to wait till the end of a phase in order to decide whether you are dead by having zero lives or l
18、ess). In the sequel the two players will be identifi ed by their names Thorgrim 2 and Urgat. Thorgrim is High King of the Dwarfs, whereas Urgat is an Orc Big Boss, both originating from the Warhammer world1; they have the perfect characteristics of opponents in a game: they have been involved in a f
19、eud which has lasted for over a millennium, and they hate each other. Our two friends are illustrated on sheet the players. Developing the game tree (incorporating the alternation between chance moves and deterministic moves by the two players), yields a highly symmetric structure. At a deterministi
20、c node the player who has to move can decide to terminate the game with payoff +n/ n, where n is the cumulative number of lives gained by the Thorgrim. If the player decides however to continue the next node is a chance move which has two descendant nodes (each with local probability 1/2) which are
21、deterministic, where the player who wins the coin fl ip is to move. See the illustration on sheet the game tree, where we actually have reduced the size of the tree by an abbreviation hiding the chance nodes. It is easy to see that the payoff is always odd and positive for the player who has won the
22、 last coin fl ip. But for every play with positive payoff +n/n for Thorgrim, there exists a refl ected play resulting in payoff n/ + n in favor of Urgat. Moreover both plays occur with equal probability. On behalf of this symmetry it seems that the expected value of the game is zero: there is no rat
23、ional reason to play it. Certainly it is highly irrational to pay the casting cost of three red mana, if you know that the same amount of mana could infl ict 9 damage to your opponent by casting three lightning bolts. Alternatively one could summon three 1/1 goblins2, or a 1/1 goblin together with a
24、 goblin king: a 2/2 creature with the special ability all goblins get +1/+1 and mountainwalk, which means that these goblins become unblockable when attacking a player controlling mountains, the red type of land. So why would a player even consider to insert this card in his deck? Regular players of
25、 Magic, the Gathering will indicate two possible scenarios where the Game of Chaos seems to make sense: you can play this card if one has more lives than your opponent; alternatively, you can play this card as a last stand if you are faced with certain defeat in the next turn of the opponent (you ar
26、e defenseless against a superior force of fl ying creatures with trample, and the Game of Chaos is the last card in your hand). These judgements are based on naive intuition only. The question is whether one can perform some sort of computation validating these beliefs. In this note I want to provid
27、e an affi rmative answer to this last question. A simple application of the von Neumann - Morgenstern Utility Theory illustrates that the expected value of the game is zero in a symmetric starting position like at the start of the game. On the other hand it will ascribe a positive value to the (sub)
28、game in the two scenarios suggested. 1Warhammer is a trademark of the Games Workshop 2in the notation a/b the number a denotes the attack strength which represents the amount of damage the creature does if it attacks, and b denotes the toughness representing the amount of damage the creature has to
29、absorb in order to be destroyed 3 2Von Neumann - Morgenstern Utility Theory For the purpose of this note a game is a fi nite rooted tree. Internal nodes are labeled either by the players T,U, indicating the player who has to move at this position, or the node is labeled to be a chance move (label C)
30、 in which case the outgoing edges have probabilities assigned which should sum up to 1. In our sheets these labels are indicated by colors: Thorgrims node are red; Urgats node are dark green and the chance nodes are light green. The leaves of the tree are labeled by pay-off s for both players. For t
31、he purpose of this note we focus on strictly competitive zero sum games where each pay-off has the form x/ x for some real value x. In the procedure of Backward Induction pay-off values are assigned to in- termediate nodes as well. At a node labeled T or U the player who has to move will choose the
32、descendent node with the highest pay-off to that player, and this will result into the well known min-max algorithm. At a chance node the reasonable pay-off is the expected pay-off at the descendant nodes. In the case of a zero-sum game the two operations preserve the zero-sum format, and hence the
33、procedure is well defi ned, assigning eventually a value to the root node which then becomes the value of the game. The problem is that in general the pay-off values are introduced to represent preferences rather than absolute values. If outcome X is preferred by Thorgrim over outcome Y one can ascr
34、ibe to X a higher utility value x than the value y assigned to Y . Given a set of possible outcomes ordered by Thorgrims pref- erences there exist many order preserving utility assignments all representing the same preferences. However these utility assignments will ascribe diff erent preferences to
35、 the expected utilities computed at chance nodes in the game tree. One can also look at this situation from the perspective of the strategic form of the game. A pure strategy of a player selects for every node where he or she has to play a move selecting one of the descendants in the tree. If one ap
36、plies a pair of strategies for both players to a game, truncating moves which are never made under these strategies a game with only chance moves remains. Such games are in fact Compound Lotteries where the individual outcomes occur with probabilities summing up to 1. For the application of backward
37、 induction the problem is now how to compare two of these lotteries. That this is a severe problem is illustrated by the notorious example constructed by Allais; see sheet Comparing Complex Lotteries; Allais Example.The crux of this example is that it is “irrational” to prefer the left lottery over
38、the right one in the fi rst row and have converse preferences in the second row; which is told to be a frequently observed behavior among the natives. Von Neumann - Morgenstern Utility Theory provides us with a strategy to overcome these problems. The key observation is that the problem doesnt arise
39、 in case there exist only two possible outcomes for the game: winning or loosing. These outcomes can be scaled to the values 1 and 0. Next one can ascribe to an intermediate outcome X such that Thorgrim prefers winning over X and X over loosing, a utility value q such that Thorgrim is indiff erent b
40、etween X and participating in a lottery with probability q of winning and 1q of loosing. The utility value q refl ects Thorgrims taste and appreciation for the outcome X. See 4 sheet Utility Intermediate Outcome. Systematic substituting intermediate out- comes by these lotteries in a game truncated
41、after a choice of strategy for both players yields a so-called compound lottery which can be simplifi ed to a simple one. And since these simple lotteries have two outcomes only, they can easily be compared: the preferred lottery is the one with the greater chance of winning, I.E., the one with the
42、higher utility. Moreover, the computation rule of taking the expected utility at a chance node is consistent with this interpretation of in- termediate outcomes. See sheet Utility Lottery = Expected Utility Outcomes. So what the von Neumann - Morgenstern Theory requires us to do is fi rst to assign
43、to intermediate outcomes a utility value which refl ects the taste of the player. Subsequently values of the nodes in the tree can be obtained by the calculation rule of backward induction, using expected utility at chance nodes. It can be shown that the utility values refl ecting the taste of a pla
44、yer are unique up to an affi ne scaling. One can normalize utilities by assigning the best and the worst outcome utilities 0 and 1 respectively. We have introduced this theory in the context of a strictly competitive zero sum game, but these restrictions turn out to be unnecessary. One just has to a
45、ssign separate utility values for both players to each outcome, and at chance nodes expected utilities are assigned to both players. At a deterministic node the player who is to move selects the node with the highest utility for that player. Note that even in a situation where X in fact represents a
46、n amount of money or other quantifi able goods, there is no a priori reason why the relation between this quantity and the appreciation as expressed by the utility should be represented by a affi ne or linear function. The only rationality condition which one should enforce is that less money should
47、 not be preferred over more: the relation should be at least monotone non-decreasing. 3Utilities for the game of Chaos In the game tree of the game of Chaos we can take each position where one of the players has lost all his available lives to be lost for that player and won for the other. The remai
48、ning positions where both players are still alive yield intermediate outcomes in case the player who has won the last coin-fl ip decides to terminate.To all positions we should assign utilities in order to apply the von Neumann - Morgenstern Utility theory. By selecting appropriate assignments we ca
49、n describe scenarios where playing the game is meaningless but also alternatives where the game obtains a positive value for a player. In the backward induction computation a player will compare at a node where he is to move the utility of the intermediate outcome collected by termi- nating with the average of the two utilities corresponding to winning or loosing the next coin fl ip. As long as both players use Linear Utilities which are lin- early dependent on the number of lives for the players, the outcome of this comparison will be a comparison between equal utilities d
链接地址:https://www.31doc.com/p-3800758.html