ViO#9rlKQ|^ T>tF=U\w0% $I!F<ۛ)蚹^1E!P*5Ӕl%qL7D2'THl.>UA]!Ɍ >^B~J:i-ο +tWOa0{ˋ Xh!c۳MǦ9+"+c7z̍JIY#oKWT$~ p++nSp )(̛*Yu@FSo!'w&>qFx u+ 3QB=Č,ŧQJ=3S: |8!,lc}&.5ҩcV^ڵF"³:< ur+_0 C FYF& OZS `ƸFꖵ,9Ybh4eBMkѴ2_cmB[N-$LM>7SNcXB69T^2%i¨jYpgK\2.JҪei b z·,p̡zyZK}L$;1h^NKAz]; RL!8ChV|>&@C 9RwEBoCF K5)нbʲPȉ65N9urH?dy@N*!OVݩ¬Xd3QtMKg^(@}9>/1F^\7Tql5Yπ{6LZQ[3cm2nVrl`ʦ4XZC" QZ!q˥>:9+j4뒵oy?p\xbD!Ż>1e{^&eiWIo]VzYze1jާؑiQkUtSpC*Mb:sh6(8Krz1>ܤkY';E/cSQ&;;DL{ ?L6x98v@Q_rw IO=|v8a݆*^z\WsU|-ʈE^Ͱ{XZyLvX&mȦZ^Shpe)n3{\4T?)];}\gWl+hP

Speculative Physics

Mathematics of Game Design: Game Theory and Related Concerns

by Mendel Schmiedekamp
Oct 31,2003

 

Mathematics of Game Design: Game Theory and Related Concerns

RPG design has a tenuous relationship with game theory. On one hand, RPGs are considered to have far to many strategies to accommodate a game theoretic approach. On the other, game theory is often perceived as an attempt to solve a game. For most designers this means breaking their game. This puts a natural impetus for RPGs to be as detached from game theory as possible.

Alternatives are possible. RPGs can be designed to account for game theoretic approaches, to insure that they cannot be solved by any one simple strategy. RPG design can even incorporate the approaches of game theory to allow the solving of portions of the game to become a source of entertainment for the players. Lastly, even if the desire is simply to avoid the application of game theory altogether, understanding the basics of game theory is essential to this outcome as well.

Games

Core Elements:

     Players - A game is played by some number of players, at least two. From the perspective of modeling real situations a player is anyone who has influence or interest in the game.

     Strategies - In a mathematical game all the choices made by a player are combined into one lump decision, called a strategy. Once the strategies of all the players has been determined the final result of the game is determined.

     Payoffs - The pay-off of a game is the gains or losses acquired by each player due to the strategies chosen. The usual assumption is that all players wish to maximize their gains, or minimize their losses. Perhaps the most significant assumption of game theory is that of quantifiable and comparable results of a game. Often this requires ad hoc guesses for the value of certain results. In more complex cases this causes games to be very complex as different payoffs could exist based on very personal features of the players, for example how much a player values money over free time.

Optional Features:

     The Chance Player - Many games involve a significant element of chance. In order to involve this into a mathematical game, an additional player is considered, often called the chance player. This player chooses strategies each with some probability, and receives no payoffs.

     Mixed Strategy - A mixed strategy is a method of playing choosing strategies which picks a given strategy with a fixed probability. For example, assuming no knowledge of your opponent, the best way to play a game of rock-paper-scissors is to choose a (pure) strategy with equal probability.

     Zero Sum Games - A zero sum game is a very special subtype of game where the total payoff over all players is zero for any combination of strategies. Intuitively this relates to the most competitive style of play where compromise is not advantageous. There is a result, called the minimax theorem, which says that any 2-player zero sum game is has an ideal mixed strategy (see above).

     Non-Cooperative Games - This is the general type of game which does not permit cooperation between players. Note, a zero sum game need not be non-cooperative, it simply gains no advantage from cooperation if it is permitted. Often trying to find solutions for non-cooperative games is very difficult. Any good approach involves knowing about your opponent's strategy, however it is not as difficult to find the strategy with the highest result assuming the opponents have chosen the optimal counter strategies, often called the maximin.

     Supergames - A supergame is a game that is played many times, with the outcomes accumulating. The advantage of a supergame is that a player may begin to approximate the strategies of other players, and hence react accordingly. Of course, since all players have this option supergames can become enormously complex.

     Cooperative Games - One way to incorporate cooperation into games is to allow the forming of unbreakable agreements between players. There are a variety of approaches to players coming to a decision of what strategies to choose. Often the optimal result is based on choosing an outcome where each player does better than the non-cooperative maximin payoff. This generates a pre-game bargaining which then determines what happens in the game itself.

     Coalition Games - While a cooperative game allows agreements it does not allow the payoffs to be transferred. Adding this option permits different players to form coalitions, where each player is paid from the total payoff of the coalition, based on how strong their position is in the game. Coalition forming is complex, since the players forming the coalition and the specific payoffs to each player can vary.

Advantages:

Games provide a mathematical description of how people interact. Often they can be added to an RPG to generate some subgame within the larger design. In addition games can be used to describe the larger scale player of the RPG as well, using different payoffs and even strategies to describe different approaches to play.

Disadvantage:

Games ultimately cannot describe the continuum of social interaction. Also the difficulty in locating discrete strategies and quantitative payoffs can make the application of game theory almost impossible.

Solving Games

In some cases game theory will be of interest in order to find solutions to an RPG design question. However, just as often it is important to prevent games from being solved, at least using a particular method.

Minimax:

Minimax is the brute force analysis to find the best way to minimize losses in the game.

     Easy Problems - Non-cooperative games are often the simplest to approach using this method. In particular 2-player zero sum games are always solvable with minimax.

     Hard Problems - Complex games often prove too difficult for this method. Cooperative and coalition games provide at best very bad strategies using this method. Lastly, even if a solution exists, mixed solutions are often very hard to implement, people are rarely random enough.

Responsive Stragtegy:

Responsive strategies are ways to adapt one's strategy to account for previous choices of one's opponents. Often this is a more direct and engaging approach to strategy.

     Easy Problems - Based on supergames responsive development of strategy is often best served in a sequence of games. While it is hard to custom develop a responsive strategy, it is often easy to find an existing one which is applicable to the game in question. One of the most successful of these strategies is called Tit-for-tat, which is basically a codification of "do onto others as they do unto you."

     Hard Problems - Responsive strategies need to respond to something. This usually requires multiple games to be played. Also responsive strategies often require a significant amount of effort if the game is very dynamic.

Negotiation:

Negotiation is developed from cooperative and coalition games. It seeks to find a way to improve results in the game by making agreements with other players.

     Easy Problems - This works best in games where there is a strong incentive to cooperate. A common example of such a game is the prisoner's dilemma. Here two players agree to confess or not. If they confess and the other person does not, then the first player goes free, and the later gets ten years in jail. If they both confess they both get four years in jail. If neither confesses they only get one year each. Obviously the best strategy is to agree not to confess. However this is only feasible if you can negotiate.

     Hard Problems - Negotiation falls apart when betrayals can occur. In addition in zero sum games negotiation has no benefit, making this approach useless there as well.

Heuristics:

An approach to artificial intelligence, heuristics are guidelines which may be used to select a strategy. While not always the best approach, heuristics allow a solution to a larger variety of games with a single approach. In a sense heuristics are bit-sized strategies, that are more accessible to people.

     Easy Problems - Heuristics apply best to games with frequent patterns and regularities. These are then exploited to generate heuristics. Often heuristics appear in situations where more involved solutions are repeatedly discovered. One design goal can be generating a hierarchy of heuristics, so as to reward strategic players with more advanced heuristics, while letting less involved players use the simpler ones without too much reduction in payoff.

     Hard Problems - Heuristics derive from patterns, without significant or consistent patterns in strategies and payoffs, heuristics are at best flawed. Also first developing a heuristic can be very difficult in complex situations, even if patterns exist. However communicating these after the fact is still likely to be easy, making for an evolving meta-game.

Hill Climbing:

Hill climbing is a simpler approach to finding a good solution. It operates iteratively searching for better solutions in the local area to the current solution chosen. When it doesn't find any, it stops and uses the current solution.

     Easy Problems - Hill climbing works best when the possible strategies are simple. Hill climbing is also good if the player does not want to devote too much time and effort to the problem, but doesn't want too poor of a solution. Essentially hill climbing gives a good solution quickly, but usually not the best solution.

     Hard Problems - The final strategy chosen by hill climbing depends on the initial starting point, so that first choice can have a significant effect on the performance of the player. Also, hill climbing for complex problems often finds itself in the locally best solution, but almost never finds the globally best solution.

Artificial Annealing:

Artificial Annealing is a variant on hill climbing which adds a random element to the search. The result is an approach which can find it's way to the globally optimal solution, but will take an agonizingly long time to reach it. The name of this method refers to genetic mutations and so is sometimes referred to as an evolutionary algorithm.

     Easy Problems - This approach is best used in situations where many different locally good solutions exist. Also this is preferable if the best solution is desired, as it is significantly better than an exhaustive search.

     Hard Problems - Annealing is not a quick method. Nor is it as good as hill climbing for simple strategies, as the random element begins to get in the way of hill climbing. Also this is an approach which can continue endlessly, it will find the best strategy, but it won't be certain when it has found it.

Next Month: What are the odds?

TQo0~^DҒt< ek&Ǿ$\۵ZFȃuwݝIŃU QYir2HR2.u3MFoعq]4#A`pP5(b& )b)ⰾp7(i<[-2gL#5[f g?*rVGf8*)s'+20ϟ̑F}KB<7wSL\gbvm9WiRބYŜvd y0'p2I_Fc2>#o A )VL[Qk?3`)<У[(*W.JH ?tXCt谙 X:@ \0w ~LqĤE-rFkYœj4q 5AQ6[AxG [>w|?( fХθY䝛$c=_qNĦoǸ>O_|&/_Mi7"宥CЧk0dӷLh;TmuCGU-!Ul{ h<\bQX.~"O2*yPcz!ŠGg

What do you think?

Go to forum!\n"; $file = "http://www.rpg.net/$subdir/list2.php?f=$num"; if (readfile($file) == 0) { echo "(0 messages so far)
"; } ?>

Previous columns

Other columns at RPGnet

TQo0~^DҒt< ek&Ǿ$\۵ZFȃuwݝIŃU QYir2HR2.u3MFoعq]4#A`pP5(b& )b)ⰾp7(i<[-2gL#5[f g?*rVGf8*)s'+20ϟ̑F}KB<7wSL\gbvm9WiRބYŜvd y0'p2I_Fc2>#o A )VL[Qk?3`)<У[(*W.JH ?tXCt谙 X:@ \0w ~LqĤE-rFkYœj4q 5AQ6[AxG [>w|?( fХθY䝛$c=_qNĦoǸ>O_|&/_Mi7"宥CЧk0dӷLh;TmuCGU-!Ul{ h<\bQX.~"O2*yPcz!ŠGg