Solving Cordial Minuet



University of UtahSolving Cordial MinuetA sketch of a game theory solutionCurtis Miller3/27/2015Cordial Minuet is a gambling game played on a magic square of order 6 with two players, with no random elements beyond the creation of the game board. In this paper, I find an approximate solution to a version of the game played on a magic square of order 4 using game theory techniques and fictitious play solution approximation. The smaller version of the game likely has a value very close to zero, and optimal strategies usually involve trying to guarantee at least a tie.Curtis MillerMATH 5750 DATE \@ "MMMM d, y" March 27, 2015ProjectSolving Cordial MinuetA sketch of a game theory solutionLast year, a blogger named Stephen Totilo [2] published an article on the gaming website Kotaku about a multiplayer game in development called Cordial Minuet by a game designer named Jason Rohrer. It is a gambling game but with no element of chance beyond the initial creation of the game board (and also the game employs an aesthetic referencing the occult, but this has no impact on gameplay; notice that Cordial Minuet is an anagram for "demonic ritual"). The game has strategic depth, but it appears to be a game that could easily fit into a framework allowing for game theory analysis.Every game is played on a magic square of order 6; the sum of each row, column, and the two diagonals is 111, and the sum of all the numbers on the game board is 666 (which fits nicely with the game's occult themes). A new magic square is generated every game. (The number of magic squares of order 6 are surely finite and less than 36!, though I do not know the method being used to generate the magic squares and how many magic squares are possible with it. The only method I am aware of for generating magic squares is the medjig method [3], but I do not know the number of magic squares this method could generate.)As the game is still in development, the rules of the game may change, but I will use the rules described in [1] and [2]. The game has a minimum pay-in of $2. The game was designed so that the player sees himself as the column player, but I will stick with game theory convention and treat the row player as player one (PI) and the column player as player two (PII). Players do not make specific bets but instead wager a percentage of their pay-in. The players start by betting 1% of their pay-in. (Opponents are paired at random and anonymously, with opponents having similar pay-ins being more likely to be paired, though they are not guaranteed to have the same pay-in; this is not revealed to the players.)The game is played in three rounds. In each round, PI will select a row for himself and a row for his opponent. He can choose any combination of rows so long as neither row was selected for either himself or his opponent in a previous round. PII will do the same for the columns. The value of the square where the row PI picked for himself and the column PII assigned to him intersect will be added to PI's score. The value of the square where the column PII picked for herself and the row PI assigned to her intersect will likewise be added to PII's score. At the end of each round, the row (column) that PI (PII) assigned to PII (PI) will be revealed to PII (PI), so both players will know their own scores. However, they will not know what the other player's score is; the other column (or row) that the opponent selected is not revealed. At the end of each round the players may wager any additional percentage of their initial pay-in they desire. Betting rules are similar to the rules of poker, where a player makes a bet, and the other player may call, raise or fold.At the very end of the game, after all rows and columns have been assigned to PI or PII, both players will reveal one of the squares corresponding to their own payoff to their opponent. A round of betting follows. Finally each player's score is revealed. The winner at the end of the game is the one with the highest cumulative score, and he earns the pot. If there is a tie, each player receives the amount he or she bet (i.e. neither player profits). (To see examples, both [1] and [2] demonstrate play.)An important property of the game is that at the end, every row will have been assigned to either PI or PII, with three rows being assigned to PI and three rows assigned to PII. The same is true of the columns. So each player's score will be the sum of three squares on the game board, with no two squares sharing a row or column. If the row and column of a square is represented as an ordered pair x,y, with x a row and y a column, no winning squares will share the same x or the same y.The full game of Cordial Minuet is complex, since there are 6! ways for a player to assign his rows or columns, and decisions are made in three steps, not to mention the numerous betting strategies. I am not interested in the betting strategies so much as in how to win the game, so I will ignore the betting aspect. I will analyze a simpler version of the game, one played on a magic square of order 4 and in two rounds of play. This preserves the properties I described in the preceding paragraph and still allows for a large number of tactics, preserving at least some of the depth that makes the full version of the game so interesting.In this reduced version of the game, PI picks a row for himself and a row for PII, and PII does likewise for the columns. After PI and PII have made their choices, PI sees the column PII assigned to him, and PII sees the row PI assigned to her. Then the second round of the game is played. PI decides which of the two remaining rows will be assigned to himself and which to PII, and PII does likewise for the columns. After the players have made their choices, the final scores are revealed, with PI's final score being the sum of the cells of the square where the rows and columns assigned to him intersect, and PII's score is found similarly. The player with the highest score wins.I begin by describing the game in extensive form. Despite being a simplified version of Cordial Minuet, the game is still far from simple, and the game tree is too large to draw. I feel the best way to describe the tree is through words, so I will describe how the tree would be drawn if we could.We will use the notation irP,jrP to describe a strategy. r is the number of the round in which a strategy is picked, and P is the player picking the strategy. The first coordinate, irP, is the row (or column) player P picks for himself (or herself) in round r, and the second coordinate, jrP, is the row (or column) player P picked for his or her opponent (i will always be used for the row or column player P picked for himself, and j will always be the row or column designated to the opponent). Notice that for a player P, all coordinates are unique; in other words, i1P≠j1P≠i2P≠j2P. For convenience, I may write i,j instead of irP,jrP; r and P will be clear from the context.For a square on the game board itself, I use the notation x,y to denote the value of the square at row x and column y. This means that for PI, the value of the square (irI,jrII) will be added to his score in round r, and for PII, the value of the square (jrI,irII) will be added to her score. So PI's total score will be SI? i1I,j1II+(i2I,j2II) and PII's total score will be SII? j1I,i1II+(j2I,i2II). If SI>SII, PI wins; if SI<SII, PII wins. Otherwise, there is a tie.We will let PI move first (the game tree will be designed so that it does not matter who moves first). What choices are available to him? He needs to select a row for himself and a row for PII, and there are 4×3=12 ways to do so. We will label each of these pure strategies in round one with unique i,j, each corresponding to the unique way to pick a row for PI and a row for PII (PI's information set consists only of the top node).PI selects his strategy, and now it is PII's turn. PII does not know what PI did in round one yet, so she will have only one information set consisting of all the nodes corresponding to PI's choice in round one. In round one, PII also has the choice of 12 pure strategies of the form i,j, so from each node spawning from PI's choice, PII will have 12 branches, each labeled with a unique i,j. There are now 144 nodes, each corresponding to a unique combination of i1I,j1I and i1II,j1II.PII selects a strategy and each player sees the j that was selected by their opponent. Now it is PI's turn again. What are his information sets? Both players have perfect recall, so their information sets will be limited to the branch of the tree corresponding to the i1P,j1P selected. Since PI knows what j1II is, his information set will be further reduced to those nodes with a common j1II. So in each branch of the tree corresponding to i1I,j1I, there will be four information sets, each one corresponding to a common j1II. In round 2 there will be 48 information sets total for PI, and every information set will contain three nodes.In round two, PI has only two pure strategies available, since there are only two ways to assign the remaining two rows (the ones not assigned in round one) to himself and his opponent. So there will be two branches from each node, each labeled with an i,j where neither i nor j are equal to either i1I or j1I. There are now 288 nodes.After PI makes his choice, PII now selects her round two strategy. What are her information sets? PII has perfect recall, so all information sets are limited to nodes with a common label representing PII's chosen strategy in round one; in other words, all nodes in an information set have the same i1II,j1II. PII also knows the row PI picked for her in round one, j1I, so only nodes with a common j1I for PI will be in an information set. Since PII does not know what strategy PI chose in round two, all nodes that PI could have taken in round two subject to the above restrictions will be included in an information set. All told, there will be 48 information sets for PII, each containing six nodes. Like PI, PII will have only two pure strategies available, with labels subject to similar constraints PI's round two labels faced.There are now 576 terminal nodes. In this game, a player can only win, lose, or tie, and we can represent this with payoffs of 1, -1, and 0, respectively (we are ignoring betting). Recall that PI's final score is SI? i1I,j1II+(i2I,j2II), and SII? j1I,i1II+(j2I,i2II). PI wins if SI>SII and loses if SI<SII (in other words, PI wins if his score is higher than PII's, and loses if his score is less than PII's). Otherwise, there is a tie. Using indicator functions, I represent the payoff function as: 1i1I,j1II+i2I,j2II>j1I,i1II+(j2I,i2II)-1i1I,j1II+i2I,j2II<j1I,i1II+j2I,i2II=1SI>SII-1SI<SII*This completely describes the game tree.Using this description of the game in extensive form, we can then represent the game in strategic form and find the matrix of the game. Each player has 49 information sets total. The procedure for converting a game from extensive form to strategic form is to represent a pure strategy in strategic form with a choice of a strategy from each of a player's information sets. In this context, however, this procedure would result in dominated strategies through strict equality. This results from the players' perfect recall ability. Information sets in round two condition on a player's strategy chosen in round one and what is known about the strategy the opponent chose in round one. Since a player knows what strategy he or she chose in round one, including rules of play that condition on that player choosing a different strategy in round one from what that player actually chose (according to that strategy) only result in redundant pure strategies. Therefore, I can simplify the matrix by representing a pure strategy in strategic form by a choice of strategy in row one, and a choice of strategy from each of the four information sets following that choice of strategy. This makes intuitive sense since it says a pure strategy is a combination of two rows (or columns, in the case of PII) in round one, and then for each column (row) that PII (PI) could assign to PI (PII) in round one, a response of a combination of the two remaining rows (columns) is assigned. This results in a square matrix with 192 rows and 192 columns.I wrote an R script that can process a game, create a game matrix representing it in strategic form, and can find an approximate solution. In practice, the resulting payoff matrix is singular due to rows or columns being linearly dependent through equality, and the only way to solve this linear dependence is to eliminate dominated strategies (it does not check for strategies that could be dominated by certain mixed strategies, since doing so would be a nightmare to program, at least with my current programming abilities). The resulting matrix is not square and therefore not invertible, so a solution needs to be found using a method that does not require inverting the matrix. I tried using the pivot method for solving a game, but the matrix is too large to reach a solution in any reasonable time. The method I actually use is the fictitious play method (with PI's first pure strategy being selected at random), and my script can find an approximate solution after a specified number of iterations or when a specified level of "accuracy" (defined as the distance in absolute value between the lower bound and upper bound of the value of the game) is first reached (be aware that the convergence of the lower bound and upper bound of the value of the game found by the fictitious play algorithm is not monotone).I found approximate solutions of different games (i.e. different magic square game boards) with accuracies of at least 0.001. The lower bound of the value was always less than zero and the upper bound always greater than zero, though their absolute values were always unequal. Optimal mixed strategies also seemed to guarantee at least a tie for both players. It seems that if the value of the game is not zero, it is very close to zero, and the players' optimal strategies are to choose combinations of rows and columns that, while not guaranteeing ties (there were no saddle points in the payoff matrix, so neither player has a pure strategy that will guarantee at least a tie), make ties very likely when an opponent plays optimally.Much more can be said about Cordial Minuet. I did not solve the full six by six game, and I do believe a solution is possible. I believe the procedure I used to analyze the simpler version of the game could be adapted to analyze the full game. Cordial Minuet's third round of play will be the most difficult to translate to strategic form, but I believe that doing so is possible, given a good notation scheme.Betting strategies would also be interesting to analyze. It may seem that since the value of the game is zero, the best betting strategy would be to match your opponent but not raise by more than what is necessary to continue play (in practice, however, an aggressive player might assume that his opponent is not playing optimally and therefore his expected payoff when playing optimally is positive, so he will want to encourage his opponent to invest as much of her pay-in as he can).The exception to this is the final round of betting, when players begin to reveal the squares they got. At this phase of the game, a player may decide that winning is highly unlikely, and therefore fold. Perhaps the best way to analyze this phase of the game is to imagine it being an entirely separate game (similar to how insight is drawn from endgame poker).For example, suppose two players are playing a card game where the player holding the hand with the larger sum wins (all card have a numeric value). There is a probability p that PI’s hand is a winning hand, a probability q that PI’s hand is a losing hand, and a probability 1-p-q that the hands are of equal value. The players see their own hands but not their opponent’s hand. When the players receive their hands, there is a round of betting. After this round of betting, each player reveals one card of their choice from their hands. Another round of betting ensues, then the players reveal their entire hands, with the winner taking the pot.There are a number of questions for how this game is played. How do the players decide to reveal their first card? Do they select their best, worst, or middle card? How does a player react to the card his opponent revealed? How do the players bet? Answering these questions may be enlightening to playing the final round of Cordial Minuet, since the problem is similar.Cordial Minuet has strategic depth. Game theory analysis could provide answers to how to play, though probably not before the game is released. Hopefully they are found after release, though; otherwise, interest in the game might fade and it may never be released.References[1] Rohrer, S.C. Cordial Minuet: How to Play in Three Minutes. Retrieved April 4th, 2015 from [2] Totilo, S. A Mildly Satanic New Video Game That You Can Only Play Online With Money. Retrieved April 4th, 2015 from [3] Wikipedia. Magic Square. Retrieved April 4th, 2015 from ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download