Which popular games are the most mathematical? - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-19T18:54:31Z http://mathoverflow.net/feeds/question/13638 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical Which popular games are the most mathematical? Douglas Zare 2010-02-01T09:42:11Z 2013-05-17T11:22:14Z <p>I consider a game to be mathematical if there is interesting mathematics (to a mathematician) involved in </p> <ul> <li>the game's structure, </li> <li>optimal strategies, </li> <li>practical strategies, </li> <li>analysis of the game results/performance.</li> </ul> <blockquote> <p>Which popular games are particularly mathematical by this definition?</p> </blockquote> <p><hr /></p> <p><strong>Motivation</strong>: I got into backgammon a bit over 10 years ago after overhearing Rob Kirby say to another mathematician at MSRI that he thought backgammon was a game worth studying. Since then, I have written over 100 articles on the mathematics of backgammon as a columnist for a backgammon magazine. My target audience is backgammon players, not mathematicians, so much of the material I cover is not mathematically interesting to a mathematician. However, I have been able to include topics such as martingale decomposition, deconvolution, divergent series, first passage times, stable distributions, stochastic differential equations, the reflection principle in combinatorics, asymptotic behavior of recurrences, $\chi^2$ statistical analysis, variance reduction in Monte Carlo simulations, etc. I have also made a few videos for a poker instruction site, and I am collaborating on a book on practical applications of mathematics to poker aimed at poker players. I would like to know which other games can be used similarly as a way to popularize mathematics, and which games I am likely to appreciate more as a mathematician than the general population will. </p> <p>Other examples:</p> <ul> <li>go</li> <li>bridge</li> <li>Set.</li> </ul> <p><strong>Non-example</strong>: I do not believe chess is mathematical, despite the popular conception that chess and mathematics are related. Game theory says almost nothing about chess. The rules seem mathematically arbitrary. Most of the analysis in chess is mathematically meaningless, since positions are won, drawn, or tied (some minor complications can occur with the 50 move rule), and yet chess players distinguish strong moves from even stronger moves, and usually can't determine the true value of a position. </p> <p>To me, the most mathematical aspect of chess is that the linear evaluation of piece strength is highly correlated which side can win in the end game. Second, there is a logarithmic rating system in which all chess players say they are underrated by 150 points. (Not all games have good rating systems.) However, these are not enough for me to consider chess to be mathematical. I can't imagine writing many columns on the mathematics of chess aimed at chess players.</p> <p><strong>Non-example</strong>: I would exclude Nim. Nim has a highly mathematical structure and optimal strategy, but I do not consider it a popular game since I don't know people who actually play Nim for fun. </p> <p><hr /></p> <p>To clarify, I want the games as played to be mathematical. It does not count if there are mathematical puzzles you can describe on the same board. <strong>Does being a mathematician help you to learn the game faster, to play the game better, or to analyze the game more accurately?</strong> (As opposed to a smart philosopher or engineer...) If mathematics helps significantly in a game people actually play, particularly if interesting mathematics is involved in a surprising way, then it qualifies to be in this collection. </p> <p>If my criteria seem horribly arbitrary as some have commented, so be it, but this seems in line with questions like <a href="http://mathoverflow.net/questions/2556/real-world-applications-of-mathematics-by-arxiv-subject-area" rel="nofollow">Real world applications of math, by arxive subject area?</a> or <a href="http://mathoverflow.net/questions/5450/cocktail-party-math" rel="nofollow">Cocktail party math</a>. I'm asking for applications of real mathematics to games people actually play. If someone is unconvinced that mathematics says anything they care about, and you find out he plays go, then you can describe something he might appreciate if you understand combinatorial game theory and how this arises naturally in go endgames. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13641#13641 Answer by Douglas Zare for Which popular games are the most mathematical? Douglas Zare 2010-02-01T09:54:32Z 2010-02-01T09:54:32Z <p><strong>The game of Go</strong> is mathematical in several ways. Its rules involve connected sets of pieces rather than pieces. Many combinatorial games including infinitesimals can be represented as positions in go endgames, as was described in <a href="http://math.berkeley.edu/~berlek/cgt/gobook.html" rel="nofollow">Mathematical Go: Chilling Gets the Last Point</a></p> <p><img src="http://senseis.xmp.net/diagrams/43/88b3fdd02b849b49818e153dd2e17910-thumb.jpg" alt="alt text" /></p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13643#13643 Answer by Andrea Mori for Which popular games are the most mathematical? Andrea Mori 2010-02-01T10:11:25Z 2010-02-01T10:43:10Z <p>Well, most card games have mathematical implications, of course.</p> <p>I'm disappointed at your considering chess non-mathematical. Wonder what Noam Elkies would think. :-)</p> <p>When I was a teenager I would play a lot a board game named here "Risiko!" (I believe that the English name is "Risk"). My impression then was that there were some mathematical aspects that could be considered while planning a strategy.</p> <p>(added later)</p> <p>Also Hex should be added to the list of mathematically interesting games.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13644#13644 Answer by aorq for Which popular games are the most mathematical? aorq 2010-02-01T10:11:48Z 2010-02-01T10:11:48Z <p>The ability to <em>embed</em> mathematical problems into chess (like combinatorial game theory into go) should not be underestimated. Papers by <a href="http://www-math.mit.edu/~rstan/chess/queue.pdf" rel="nofollow">Richard Stanley</a> and <a href="http://www.emis.de/journals/EJC/Volume%5F11/PDF/v11i2a4.pdf" rel="nofollow">Noam Elkies</a> demonstrate problems where the objective is to determine the number of ways to perform a given task. They include problems where the answer is</p> <ul> <li>A Catalan number, say the 7th or even the 17th. (Problems A and B from Stanley. Problem A from Elkies.)</li> <li>Fibonacci numbers, arbitrarily large. (Problem 4 from Elkies.)</li> <li>The coefficients of the Maclaurin series for tangent, say the 7th or 9th. (Problem D from Stanley. Problems B and 1 from Elkies.)</li> <li>Directly computable from the Selberg integral $\int_0^1 \cdots \int_0^1 \prod_{1\le i\lt j\le 4} (x_i - x_j)^2 dx_1\cdots dx_4$. (Problem E from Stanley.)</li> </ul> <p>Of course, the answers are this for some mathematical reason, not accidentally. Many of the problems are also elegant from a chess perspective.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13645#13645 Answer by aorq for Which popular games are the most mathematical? aorq 2010-02-01T10:14:22Z 2010-02-02T23:29:09Z <p><a href="http://en.wikipedia.org/wiki/Set%5F%28game%29" rel="nofollow"><strong>Set</strong></a> is a card game that is very mathematical.</p> <p><img src="http://upload.wikimedia.org/wikipedia/en/thumb/8/8f/Set-game-cards.png/250px-Set-game-cards.png" alt="alt text" /></p> <p>Set is played with a deck with 81 cards. Each card corresponds to a point in affine 4-space over $\mathbb Z/3$, with 3 possible colors, shadings, shapes, and counts. The players must identify Sets, sets of 3 cards corresponding to collinear points. Sets are also triples of cards which <a href="http://mathoverflow.net/questions/7881/sum-of-n-vectors-in-mathbb-z-nk/13025#13025" rel="nofollow">add up to the 0-vector</a>. The three cards pictured form a Set.</p> <p>A natural question which arises during play is whether there are any Sets among the cards which have been dealt out. There can be 9 cards in a codimension 1 subspace which do not contain a Set, corresponding to a nondegenerate conic in affine 3-space such as $z=x^2+y^2$. There can be <a href="http://www.math.rutgers.edu/~maclagan/papers/set.pdf" rel="nofollow">at most 20 cards not containing a Set</a>, corresponding to a nondegenerate conic in the projective 3-space containing 10 points. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13650#13650 Answer by aorq for Which popular games are the most mathematical? aorq 2010-02-01T10:36:30Z 2010-02-01T10:36:30Z <p><strong><a href="http://en.wikipedia.org/wiki/Tic-tac-toe" rel="nofollow">Tic-tac-toe</a></strong> and <strong><a href="http://en.wikipedia.org/wiki/Gomoku" rel="nofollow">Gomoku</a></strong> (five-in-a-row) are common games that have fairly mathematical rules. Players alternately choose points from some subset of a lattice and try to form a line segment of a certain length.</p> <p>The <a href="http://en.wikipedia.org/wiki/Hales%E2%80%93Jewett%5Ftheorem" rel="nofollow">Hales–Jewett theorem</a> is a result from Ramsey theory that essentially says that however long the lines must be, a draw is not possible in a sufficiently large dimension.</p> <p>Gomoku has been solved, constructively. (The first player wins.)</p> <p>The game of <strong><a href="http://en.wikipedia.org/wiki/Connect%5FFour" rel="nofollow">Connect Four</a></strong> adds the additional element of "gravity". It has also been solved. (The first player wins on the standard board size, but not on some boards of slightly different size.)</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13652#13652 Answer by Michael Greinecker for Which popular games are the most mathematical? Michael Greinecker 2010-02-01T10:42:00Z 2011-01-14T20:18:09Z <p><a href="http://en.wikipedia.org/wiki/Hex_%28board_game%29" rel="nofollow"><strong>Hex</strong></a> is a popular game with some interesting mathematical properties. John Nash gave an easy proof that the first player can force a win, his famous "stealing strategies" argument. His proof gives no indication as to what the optimal strategy actually looks like. </p> <p>There is also a nice AMM paper by David Gale in which he shows that the fact that Hex can not end in a draw is equivalent to the Brouwer fixed point theorem (for higher dimensions, one needs a higher dimensional version of Hex).</p> <p><img src="http://upload.wikimedia.org/wikipedia/commons/thumb/e/e9/Hex_board_11x11.svg/180px-Hex_board_11x11.svg.png" alt="11x11 Hex board"></p> <p>One variant is called <a href="http://en.wikipedia.org/wiki/Y_%28game%29" rel="nofollow"><strong>Y</strong></a>. Both players attempt to create a group connecting all sides of a triangular board. As with Hex, there are no ties possible. A commercial version adds 3 points of positive curvature, with 5 neighbors instead of 6. </p> <p><img src="http://upload.wikimedia.org/wikipedia/en/thumb/b/b6/Yhalfsize.png/200px-Yhalfsize.png" alt="Commercial version of Y"></p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13653#13653 Answer by aorq for Which popular games are the most mathematical? aorq 2010-02-01T10:43:25Z 2010-02-01T10:43:25Z <p><strong><a href="http://en.wikipedia.org/wiki/Dots%5Fand%5FBoxes" rel="nofollow">Dots and boxes</a></strong> is a pencil-and-paper game with a reasonably deep mathematical theory. The game is often played by schoolchildren.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13656#13656 Answer by Nurdin Takenov for Which popular games are the most mathematical? Nurdin Takenov 2010-02-01T10:52:22Z 2010-02-01T10:52:22Z <p><a href="http://en.wikipedia.org/wiki/Heads%5For%5FTails" rel="nofollow">Heads or Tails</a> - Is it popular game? There is a lot of mathematics related with this game. For example, it's non-transitive variant - <a href="http://en.wikipedia.org/wiki/Penney%27s%5Fgame" rel="nofollow">Penney's game</a>.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13658#13658 Answer by Douglas Zare for Which popular games are the most mathematical? Douglas Zare 2010-02-01T10:59:11Z 2010-02-01T10:59:11Z <p><strong>Backgammon</strong> is a game of skill and chance. </p> <p>The doubling cube emphasizes absolute evaluations as opposed to relative evaluations, although it makes some some equities not exist, as the relevant series diverge. </p> <p>Several areas of backgammon, from determining the appropriate doubling strategy to analyzing the race, are well-approximated by random walks with absorbing barriers. </p> <p>The analysis of backgammon positions and strategies frequently involves Monte Carlo analysis, variance reduction techniques, and statistics. </p> <p>Backgammon has been a success for artificial intelligence since neural networks have been able to learn to play at or above the level of the best human players from self-play. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13674#13674 Answer by Douglas Zare for Which popular games are the most mathematical? Douglas Zare 2010-02-01T13:51:01Z 2010-02-01T13:51:01Z <p><strong>Rock-Paper-Scissors</strong> remains a popular children's game. It's a simple 0-sum game with a mixed Nash equilibrium. </p> <p>In practice, even if that is your goal, it's hard to generate a uniformly random choice from {rock,paper,scissors} which is independent from what you and your opponent have chosen before. While the unexploitable strategy is simple in theory, exploiting people is complicated, and can involve statistics and hidden-Markov models. </p> <p>There is an gambling site which lets you play rock-paper-scissors against an opponent, charging a rake so that the Nash equilibrium strategy will lose on average. </p> <p>Cryptographic issues arise if you want to be confident that a distant opponent's choice was not made with knowledge of yours. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13703#13703 Answer by Sam Lichtenstein for Which popular games are the most mathematical? Sam Lichtenstein 2010-02-01T16:21:52Z 2010-02-01T16:21:52Z <p>Since you mentioned bridge in the question, but nobody has said anything about it, I'll take a stab. Interestingly, bridge has several more-or-less orthogonal mathematical aspects to it. </p> <ol> <li><p>The play of the hand necessarily involves calculating or estimating probabilities. These are not so difficult as to be mathematically interesting, but I do think they can be slightly more challenging that counting your outs in poker. In bridge there are often multiple possible ways of combining chances to make your contract, some highly dependent for their success upon the order in which the chances are taken. </p></li> <li><p>Coming up with efficient communication schemes is central to both bidding and defense. I don't really know enough of the theory behind designing bidding systems to comment. But designing an efficient "relay" system probably involves a smidgen of math.</p></li> <li><p>Finally there's more esoteric stuff. For instance, since bridge is not a game of complete information, one doesn't usually expect combinatorial game theory structures to arise. However it can happen that the bidding and play reveal enough information so that everyone knows what cards everyone else has, in which case there is of course complete information. Sometimes this actually brings added complexity though! One manifestation of this is <a href="http://www.bridgeworld.com/default.asp?d=esoterica&amp;f=johan.html" rel="nofollow">higher order throw-ins</a>, which can be analyzed via nimbers, etc.</p></li> </ol> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13710#13710 Answer by Bill Johnson for Which popular games are the most mathematical? Bill Johnson 2010-02-01T17:27:41Z 2010-02-01T17:27:41Z <p>In bridge, missing QJxx in a suit, if the Q or J drops on the first round, it is better to finesse if possible on the second round if nothing else is known about the distribution. This is obvious to a mathematician, but the simple conditional probability is so difficult for the average person that bridge teachers have incorporated the principle into the qualitative "Rule of Restricted Choice", which says that if an opponent plays a card that can be from equals (such as the "quack" from QJ), it increases the probability that the other opponent has the second equal card.</p> <p>In mathematics we often prove uniqueness before existence. The one thing I find appealing about Sudoko is that knowing a solution is unique can help in finding the solution.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13712#13712 Answer by Alex R. for Which popular games are the most mathematical? Alex R. 2010-02-01T18:00:16Z 2010-02-01T18:00:16Z <p><a href="http://mathworld.wolfram.com/LightsOutPuzzle.html" rel="nofollow"><strong>Lights Out</strong></a> is a game which has effectively been reduced to a problem in linear algebra, particularly a routine exercise in Gaussian elimination. A good link can be found <a href="http://www.jstor.org/pss/2690705" rel="nofollow">here</a>. What's particularly interesting is the fact that operations in the game commute, which allows for the linear algebra approach. </p> <p>I wonder if there are any non-commutative turn based games which can also be solved mathematically? Certainly, chess is out of the question!</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13718#13718 Answer by Richard Stanley for Which popular games are the most mathematical? Richard Stanley 2010-02-01T18:22:08Z 2010-02-02T22:58:29Z <p><strong>Poker</strong> is a family of card games.</p> <p>Many model games from game theory approximate poker situations, and some of the earliest work on game theory featured model games for betting and bluffing in poker (despite the popular misconception that bluffing is not mathematical) studied by <a href="http://www.math.ucla.edu/~tom/papers/poker1.pdf" rel="nofollow">Borel and von Neumann</a>.</p> <p>Nes Ankeny wrote a book <em>Poker strategy: Winning with game theory</em> in 1981 which gives an interesting mathematical approach to poker. Ankeny was a number theorist who was also a world-class poker player. </p> <p>Tournament poker often rewards lower places than first. This means the value of chips is nonlinear, and several models have been used to determine the appropriate risk aversion by finding good functions from the distributions of chips to probabilities of finishing in each place. One is diffusion, which led to an <a href="http://www.math.ucla.edu/~tom/papers/poker3.pdf" rel="nofollow">application</a> of the Riemann map of an equilateral triangle, although the difficulty of computing this and higher dimensional diffusion led to the widespread adoption of the independent chip model instead: Shuffle all chips, and rank players by their highest chips. Equivalently, remove the chips from play one by one.</p> <p>Bill Chen and Jerrod Ankenman wrote <em>The Mathematics of Poker</em> aimed more at mathematicians than poker players. They studied model games in which players are dealt numbers from [0,1] instead of cards. They also computed the Nash equilibrium strategies for some situations in NL Texas Hold'em, the most popular variant at the moment. They also addressed a few topics outside of game theory, such as the risk of ruin probability with an unknown but normally distributed true win rate, and with a distribution skewed enough that the Brownian approximation fails, as for tournament play.</p> <p>When the first few players fold, and we know they are more likely to have folded 8-4 than ace-ace, what can we say about the distributions of hands for the remaining players? Jerrod Ankenman <a href="http://www.pokerroad.com/forums/showpost.php?p=99242&amp;postcount=29" rel="nofollow">remarked</a>, "the problem of finding the hand distributions of the blinds given that the first n players have folded a specified set of distributions [sets of hands] is NP-hard." </p> <p>[I merged two answers about poker.]</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13721#13721 Answer by Mitch for Which popular games are the most mathematical? Mitch 2010-02-01T18:33:54Z 2010-02-01T18:33:54Z <p>Believe it or not, <a href="http://en.wikipedia.org/wiki/Battleship_%28game%29" rel="nofollow">Battle Ship</a> is an interesting mathematical game. Well, at least if you play it in high enough dimension: <em>Finding small explicit sets that hit all large enough combinatorial rectangles</em> (ships) has been studied quite a lot and there are still a couple of open problems. See for instance, <a href="http://www.springerlink.com/content/t2q334233l262128/" rel="nofollow">here</a>.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13738#13738 Answer by Matt Noonan for Which popular games are the most mathematical? Matt Noonan 2010-02-01T20:59:58Z 2010-02-01T20:59:58Z <p>Call a two player deterministic game <i>finite</i> if the game tree has finite depth. Now we can play...</p> <p><b>Hypergame</b>: Player one names a finite game $\Gamma$, for which player two will play the first move. Play then proceeds as normal, with the winner of $\Gamma$ winning hypergame.</p> <p>Question: for the first move, can player one choose $\Gamma = \text{Hypergame}$?</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13799#13799 Answer by Douglas S. Stones for Which popular games are the most mathematical? Douglas S. Stones 2010-02-02T06:01:14Z 2010-02-02T06:01:14Z <p>What about <strong><a href="http://en.wikipedia.org/wiki/Pool%5F%28cue%5Fsports%29" rel="nofollow">Pool</a></strong>? It contains quite a lot of geometry.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13802#13802 Answer by Douglas S. Stones for Which popular games are the most mathematical? Douglas S. Stones 2010-02-02T06:36:45Z 2010-02-02T06:36:45Z <p>There's also the famous <a href="http://en.wikipedia.org/wiki/Rubik%27s%5FCube" rel="nofollow">Rubik's Cube</a>, which is popular and heavily maths-related.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/13821#13821 Answer by Q.Q.J. for Which popular games are the most mathematical? Q.Q.J. 2010-02-02T12:28:19Z 2010-02-02T12:28:19Z <p>Blokus is a fairly new game that's gaining popularity (though there are older games with a similar set-up). There are several versions, and the four-player version has some non-cooperative elements to the gameplay.</p> <p>Each player takes turns to place polyominoes of size 1 squares through five (the monomino, domino, triominoes, tetrominoes, and pentominoes) so that they touch a previously played piece of their own colour, but only at the corners. The overall aim of the game is to try and cover as much area with your own pieces as possible. The countertactics to stop a player doing this involve placing your pieces in a way that will block them from making good moves.</p> <p>I think this game would fit your criteria. It is relatively unstudied from a mathematical point of view as far as I know. I imagine some familiarity with some of the mathematical work on tessellations of polyominoes would have to give a player at least a marginal advantage in planning a long-term strategy. It probably fits the criteria in other ways too.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/15469#15469 Answer by mmccoo for Which popular games are the most mathematical? mmccoo 2010-02-16T15:59:46Z 2010-02-16T15:59:46Z <p>My vote is for the game "Clue".</p> <p>It's a simple game that young children can learn and enjoy. When they first start playing, they use simple elimination. As they progress they can continue to more advanced strategies. They learn to observe what the other players are asking of each other, who's passing and on what guesses.</p> <p>Clue may not be a game that adults will play on their own, but when it comes to including the little ones, it's fantastic.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/16258#16258 Answer by kakaz for Which popular games are the most mathematical? kakaz 2010-02-24T13:12:10Z 2010-02-24T13:12:10Z <p>Clay Institute in its lectures on millennium problems list as one of it question <a href="http://www.claymath.org/millennium/P_vs_NP/" rel="nofollow">"P vs NP Problem"</a> and simple Minesweeper is listed as example for which finding strategy is equivalent to solution of such problem....which was proved by Richard Kaye referenced below. Here is the <a href="http://www.claymath.org/Popular_Lectures/Minesweeper/" rel="nofollow">beginning of minesweeper article</a>:</p> <blockquote> <p>The connection between the game and the prize problem was explained by Richard Kaye of the University of Birmingham, England ('Minesweeper is NP-complete', Mathematical Intelligencer volume 22 number 4, 2000, pages 9-15). And before anyone gets too excited, you won't win the prize by winning the game. To win the prize, you will have to find a really slick method to answer questions about Minesweeper when it's played on gigantic grids and all the evidence suggests that there isn't a slick method. In fact, if you can prove that there isn't one, you can win the prize that way too.</p> </blockquote> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/16279#16279 Answer by Richard Stanley for Which popular games are the most mathematical? Richard Stanley 2010-02-24T16:48:25Z 2010-02-24T16:48:25Z <p>For some applications of combinatorial game theory to actual chess endgames, see the article by Elkies at <a href="http://arxiv.org/abs/math/9905198" rel="nofollow">http://arxiv.org/abs/math/9905198</a>. For an article I wrote with Elkies on the mathematical aspects of the knight in chess (but with little significance to the actual game of chess), see <a href="http://math.mit.edu/~rstan/papers/knight.pdf" rel="nofollow">http://math.mit.edu/~rstan/papers/knight.pdf</a>.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/20638#20638 Answer by Nate Eldredge for Which popular games are the most mathematical? Nate Eldredge 2010-04-07T15:38:30Z 2010-04-07T15:38:30Z <p>More puzzles than games, but many of the number puzzles published by <a href="http://www.nikoli.co.jp/en/puzzles/" rel="nofollow"><strong>Nikoli</strong></a> are quite mathematical in nature. They tend to involve an interplay between local and global conditions that have to be satisfied simultaneously, and one can glimpse geometric and graph-theoretic properties lurking.</p> <p>The multi-player game <a href="http://en.wikipedia.org/wiki/Carcassonne_%28board_game%29" rel="nofollow"><strong>Carcassonne</strong></a> has many of the same aspects, especially the issue of farms separated by roads, which sort of brings in the Jordan curve theorem and a lot of interesting parity issues. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/52119#52119 Answer by Orange for Which popular games are the most mathematical? Orange 2011-01-14T21:35:22Z 2011-01-14T21:35:22Z <p>Being a mathematician allows you to play the game of chess better. </p> <p>Mathematicians perform calculations quickly and accurately. Mathematicians are creative. Mathematicians are good at identifying the important component to a problem. Mathematicians are accustomed to encountering new problems and challenges. Mathematicians are good at comparing alternatives. </p> <p>Now consider the game of chess. At any level 90%+ of chess games end as a result of an oversight in calculation. This often happens because one misses a surprising or unconventional move that requires creativity. In chess there are many strategic components, pawn structure, piece activity, material imbalance, king safety etc. but often one of these takes center stage. Almost always in a game of chess there will be a situation you have never encountered before. 90+% of grandmaster chess moves would be listed in the top 5 choices of any tournament player but consistently play the third or fourth choice move is a recipe for disaster even in scholastic chess. </p> <p>I can not think of a profession better suited to playing chess than that of mathematician! </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/52122#52122 Answer by Mark Bennet for Which popular games are the most mathematical? Mark Bennet 2011-01-14T21:52:32Z 2011-01-14T21:52:32Z <p>There are various map/graph colouring games which are more subtle than determining the chromatic number. For example take a planar graph or map (particular or restricted to some category) - how many colours can P1 force P2 to use: or who wins if the first person forced to use a fifth colour loses?</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/67150#67150 Answer by Diego de Estrada for Which popular games are the most mathematical? Diego de Estrada 2011-06-07T15:49:24Z 2011-06-07T16:31:30Z <p><a href="http://en.wikipedia.org/wiki/Bulls_and_cows" rel="nofollow">Bulls and cows</a> and its modern variant <a href="http://en.wikipedia.org/wiki/Mastermind_%28board_game%29" rel="nofollow">Mastermind</a>, for which Don Knuth demonstrated that the codebreaker can win in at most five moves. Playing this game with pencil and paper (in a way where both players are codemakers and codebreakers) can be very fun.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/67155#67155 Answer by Diego de Estrada for Which popular games are the most mathematical? Diego de Estrada 2011-06-07T16:16:56Z 2011-06-07T16:16:56Z <p>There is a popular game in current cellphones called Pixelated (in BlackBerry) or Flood-It (in iPhone) that has a very interesting analysis (its generalization is equivalent to the Shortest superstring problem): <a href="http://arxiv.org/abs/1001.4420" rel="nofollow">http://arxiv.org/abs/1001.4420</a> http://www.cs.bris.ac.uk/Research/Algorithms/BAD10/Slides/Jalsenius.pdf</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/67156#67156 Answer by Diego de Estrada for Which popular games are the most mathematical? Diego de Estrada 2011-06-07T16:28:30Z 2011-06-07T16:28:30Z <p><a href="http://en.wikipedia.org/wiki/Khet_%28game%29" rel="nofollow">Khet</a> is a great new game awarded by Mensa. There is even a master thesis dedicated to it: <a href="http://www.personeel.unimaas.nl/Uiterwijk/Theses/MSc/Nijssen_thesis.pdf" rel="nofollow">http://www.personeel.unimaas.nl/Uiterwijk/Theses/MSc/Nijssen_thesis.pdf</a></p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/67157#67157 Answer by Per Alexandersson for Which popular games are the most mathematical? Per Alexandersson 2011-06-07T16:32:14Z 2011-06-07T16:32:14Z <p>StarCraft, a very popular RTS, which is taught at Berkeley. <a href="http://kotaku.com/5141355/competitive-starcraft-gets-uc-berkeley-class" rel="nofollow">http://kotaku.com/5141355/competitive-starcraft-gets-uc-berkeley-class</a></p> <p>where "Calculus and Differential Equations are highly recommended for full understanding of the course.".</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/77433#77433 Answer by Junyan Xu for Which popular games are the most mathematical? Junyan Xu 2011-10-07T08:04:28Z 2012-06-30T12:12:39Z <p><strong><a href="http://en.wikipedia.org/wiki/Sprouts_%28game%29" rel="nofollow">Sprouts</a></strong> is a game contrived by J. H. Conway and M. S. Paterson in the 1960s.</p> <p>It is an impartial game for two players played on a plane with some spots. Each move consists of both</p> <ol> <li>joining two spots (could be the same spot) with a simple curve which does not go through existing spots or curves, such that the degree of each spot after the move does not exceed 3; and</li> <li>placing a new spot on that curve.</li> </ol> <p>Who makes the last move is the winner/loser according to normal/misère play convention.</p> <p>This game is of topological nature but there are only finitely many inequivalent options at each move, and the game always terminates after finitely many moves (in fact, bounded by number of initial spots), making it an combinatorial game.</p> <p>It enjoys some popularity, as reflected by the existence of a world association (the <a href="http://www.wgosa.org/" rel="nofollow">WGOSA</a>, World Game of Sprouts Association).</p> <p>There are rich graph-theoretic results concerning this game, for example see <a href="http://nrich.maths.org/2413" rel="nofollow">this page in NRICH</a> and <a href="http://www.math.uic.edu/~kauffman/Conway.pdf" rel="nofollow">this section in <em>Winning Ways</em></a>. Experienced players make use of these results to set up goals.</p> <p><a href="http://sprouts.tuxfamily.org/" rel="nofollow">Here</a> is a website dedicated to the determination of the theoretical winners. A pattern with period 6 emerged under both play conventions. The researchers have published several papers and even considered <a href="http://arxiv.org/abs/0812.0081" rel="nofollow">Sprouts on general surfaces</a> ("compact" is not essential, I think), and proved that the theoretical winner of the Sprouts game with a fixed number of spots on different compact surfaces is ultimately periodic in genus, with period 1/period 2 in the case of orientable/non-orientable surfaces.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/77464#77464 Answer by Countably Infinite for Which popular games are the most mathematical? Countably Infinite 2011-10-07T15:54:59Z 2013-01-29T13:42:08Z <p>Dear All,</p> <p>This was a favorite pass time on my mobile. Its pushing blocks also known as Sokoban:</p> <p><img src="http://upload.wikimedia.org/wikipedia/en/thumb/1/18/Sokoban_animation.gif/108px-Sokoban_animation.gif" alt="Sokoban Animated Small"></p> <p>Some years ago it came as a little surprise to me that it is NP complete. Here is one paper saying that:</p> <p>Demain, E.D. and Hoffmann, M.<br> Pushing Blocks is NP-Complete for Noncrossing Solution Paths, 2001<br> <a href="http://www.inf.ethz.ch/~hoffmann/pub/dh-pbnns-01.pdf" rel="nofollow">http://www.inf.ethz.ch/~hoffmann/pub/dh-pbnns-01.pdf</a></p> <p>Best Regards</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/77475#77475 Answer by Timothy Chow for Which popular games are the most mathematical? Timothy Chow 2011-10-07T17:45:59Z 2011-10-07T17:45:59Z <p>The game of <a href="http://en.wikipedia.org/wiki/Mafia_%28party_game%29" rel="nofollow">Mafia</a>, also marketed as Werewolf, depends in practice mostly on how skillful the players are at lying, but there are some fascinating mathematical questions that arise when tries to devise optimal strategies for expert players. Let me describe one such expert strategy to give the flavor. In what follows, I will assume basic knowledge of the (simple) rules, which you can find at the above Wikipedia link.</p> <p>Suppose there is a detective, who secretly learns someone's identity each night. How can the detective communicate his knowledge without exposing himself to the Mafia? Each day, each townsperson claims to be the detective, and announces the piece of information he learned the previous night. The real detective tells the truth, but the Mafia will usually not be able to distinguish the real detective from all the impersonators. Of course, the townspeople will not know either&mdash;until the detective is killed. Then the townspeople, being expert players with excellent memories, will remember everything the detective said before being killed, and will therefore get a windfall of truthful information that they can they exploit to their advantage.</p> <p>Many questions arise naturally. What is the probability that the townspeople win if they use this strategy? The Mafia have some extra information (they know who they are) and hence if some townsperson makes a false statement while impersonating the detective, the Mafia will detect this and know that that townsperson is not the detective. So perhaps the detective should lie occasionally to counter this strategy? How should the townspeople lie? Should they attempt to give mutually consistent stories or not? As far as I know, these strategic issues have remained largely unexplored.</p> <p>See also <a href="http://mathoverflow.net/questions/38119/where-to-publish-a-paper-on-the-mafia-game" rel="nofollow">this MO question</a> that announces a mathematical paper on the Mafia game.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/77479#77479 Answer by Todd Trimble for Which popular games are the most mathematical? Todd Trimble 2011-10-07T18:38:25Z 2011-10-07T18:38:25Z <p>There's also <a href="http://en.wikipedia.org/wiki/Nine_Men%27s_Morris" rel="nofollow">Nine Men's Morris</a>, which is a very ancient game. My understanding is that it has been effectively solved in recent years with the help of computer analysis. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/77483#77483 Answer by Todd Trimble for Which popular games are the most mathematical? Todd Trimble 2011-10-07T18:58:01Z 2011-10-07T18:58:01Z <p>I didn't see mention of Conway's <a href="http://www.bitstorm.org/gameoflife/" rel="nofollow">The Game of Life</a>. Is it a game? Well, Conway calls it a zero-player game! Other people call it a cellular automaton. You decide. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/93403#93403 Answer by joro for Which popular games are the most mathematical? joro 2012-04-07T11:04:43Z 2012-04-07T11:04:43Z <p>Untangle (available in Debian based distros and <a href="http://duketek.com/apps/untangle/" rel="nofollow"><em>easy</em> online HTML5 version</a></p> <p>From the documentation:</p> <blockquote> <p>You are given a number of points, some of which have lines drawn between them. You can move the points about arbitrarily; your aim is to position the points so that no line crosses another.</p> </blockquote> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/93415#93415 Answer by Barry Cipra for Which popular games are the most mathematical? Barry Cipra 2012-04-07T13:02:26Z 2012-04-07T13:02:26Z <p><strong>Baseball</strong> fits the criteria of math underlying the game's structure, its optimal and practical strategies, and the analysis of results and performance. It certainly fits the criterion of popularity.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/100855#100855 Answer by Damien S. for Which popular games are the most mathematical? Damien S. 2012-06-28T11:24:50Z 2012-06-28T15:40:57Z <p>There is the amazing set of one-player games presented by S. Tatham (especially loopy and towers):</p> <p><a href="http://www.chiark.greenend.org.uk/~sgtatham/puzzles/" rel="nofollow">http://www.chiark.greenend.org.uk/~sgtatham/puzzles/</a></p> <p>You should try it !</p> <p>Damien.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/104259#104259 Answer by unknown (google) for Which popular games are the most mathematical? unknown (google) 2012-08-08T06:11:45Z 2012-08-08T06:11:45Z <p>Just a two cents worth here. :) Chess itself might perhaps not be too mathematical, but the chess evaluation functions of any chess-playing computer program seems like a mathematical object. After all, these are maps from the set of chess positions to $\mathbb{R}$ and they are bound to satisfy various properties. Given any two chess programs that are both strong and might be expected to be decent (in terms of current technology) approximations to objective truth, one might probably expect them to be "close" in some meaningful way that one could perhaps attempt to define.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/104274#104274 Answer by none for Which popular games are the most mathematical? none 2012-08-08T12:16:58Z 2012-08-08T12:16:58Z <p>The Legend of Zelda and several other classic Nintendo games are NP-hard. <a href="http://arxiv.org/pdf/1203.1895v1.pdf" rel="nofollow">http://arxiv.org/pdf/1203.1895v1.pdf</a></p> <p>Following the example of Rubik's Cube (i.e. maybe not exactly a game), as a kid I was fascinated by Spirograph and played it for hours on end.</p> <p>There is always "Who can name the bigger number" (you can win the computable version (second link below) with large cardinals):</p> <ul> <li><a href="http://scottaaronson.com/writings/bignumbers.html" rel="nofollow">http://scottaaronson.com/writings/bignumbers.html</a></li> <li><a href="http://web.archive.org/web/20110718091437/http://borcherds.wordpress.com/2007/05/26/my-dad-has-more-money-than-yours/" rel="nofollow">http://web.archive.org/web/20110718091437/http://borcherds.wordpress.com/2007/05/26/my-dad-has-more-money-than-yours/</a></li> </ul> <p>Pool (aka billiards) has always seemed mathematical to me. A buddy of mine told me he learned about PDE's from trying to calculate the motion of a ping pong ball (laminar airflow etc).</p> <p>Enough, I'll stop.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/108067#108067 Answer by Russell May for Which popular games are the most mathematical? Russell May 2012-09-25T15:32:02Z 2012-09-25T15:32:02Z <p>The game of <a href="http://en.wikipedia.org/wiki/Cootie_%28game%29" rel="nofollow">Cootie</a>, where players roll dice to collect parts of an insect (cootie), is a variant of the coupon collector's problem.</p> <p><img src="http://upload.wikimedia.org/wikipedia/en/thumb/a/a6/Original_Cootie_box_cover_and_components.jpg/250px-Original_Cootie_box_cover_and_components.jpg" alt="alt text"></p> <p>Instead of collecting a single instance of each coupon, players must collect multiple copies (6 legs, 2 eyes, 1 head, etc.) to win. It turns out you can compute the expected number of rolls to win at Cootie (even with a weighted die) with a <em>finite</em> sum. </p> <p>In particular, if you have $L$ objects to collect and for each object <code>$\ell&lt;L$</code> you need $q_\ell$ copies and the probability of getting the object is $p_\ell$, then the expected number of rolls to get all of the needed objects is</p> <p><code>$\displaystyle\sum_{\ell\in L} \frac{{p_\ell}^{q_\ell}}{(q_\ell -1)!}\int_0^\infty x^{q_\ell}\exp(-x) \prod_{k\in L-\{\ell\}}(\exp(p_k x)-\exp_{&lt;q_k}(p_k x))dx.$</code></p> <p>If you're interested, check out my <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v15i1n31" rel="nofollow">paper</a> out for the full computation.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/118790#118790 Answer by Curt Monash for Which popular games are the most mathematical? Curt Monash 2013-01-13T08:57:59Z 2013-01-13T08:57:59Z <p>Diplomacy was pretty much invented to illustrate points in cooperative game theory. At least, that's how Martin Shubik told me the story. :)</p> <p>Actually, I think he invented a card game called "So long, Sucker", and claimed Diplomacy was based on that.</p> <p>That said, the core points are psychological -- if somebody knows he is losing but has the power to choose the winner, on what basis does he choose?</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/118807#118807 Answer by Michael Murray for Which popular games are the most mathematical? Michael Murray 2013-01-13T13:09:34Z 2013-01-13T13:09:34Z <p><a href="http://en.wikipedia.org/wiki/Rummikub" rel="nofollow">Rummikub</a> ? It encourages some logical thought and analysis. It seems to have at least one mathematical paper on it </p> <p><a href="http://comjnl.oxfordjournals.org/content/49/6/665.abstract" rel="nofollow">http://comjnl.oxfordjournals.org/content/49/6/665.abstract</a></p> <p>and it's popular and fun. </p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/120199#120199 Answer by Felix Goldberg for Which popular games are the most mathematical? Felix Goldberg 2013-01-29T11:41:21Z 2013-01-31T09:26:34Z <p>I am a bit surprised that <a href="http://en.wikipedia.org/wiki/Dominion_%28card_game%29" rel="nofollow">Dominion</a> has not been mentioned yet. I am referring less to the gameplay itself rather than to the analyzes that people do in order to assess the "intrinsic worth" or "situational worth" (my terms) of a card or a strategy, using a <a href="http://dominionsimulator.wordpress.com/" rel="nofollow">rather complicated simulator</a>. I perceive it as a kind of Monter Carlo analysis.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/120241#120241 Answer by Mike for Which popular games are the most mathematical? Mike 2013-01-29T18:38:30Z 2013-01-29T18:38:30Z <p>Blood Bowl! All about managing probability. <a href="http://en.wikipedia.org/wiki/Blood_bowl" rel="nofollow">http://en.wikipedia.org/wiki/Blood_bowl</a></p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/120242#120242 Answer by rdm for Which popular games are the most mathematical? rdm 2013-01-29T18:40:31Z 2013-01-29T18:40:31Z <p>I would be tempted to include <a href="http://en.wikipedia.org/wiki/Blackjack" rel="nofollow">Blackjack</a> in the list of mathematical games. It's supposedly a game of chance, but gambling establishments routinely forbid card counting, because a mathematical approach to the game gives the player too big of an advantage. This rule is typically enforced through a mathematical analysis of the player's bets.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/120264#120264 Answer by Abel Stolz for Which popular games are the most mathematical? Abel Stolz 2013-01-29T22:04:30Z 2013-01-29T22:04:30Z <p>The page <a href="http://www.toothycat.net/~hologram/Turing/index.html" rel="nofollow">http://www.toothycat.net/~hologram/Turing/index.html</a> claims that the popular trading card game Magic: The Gathering is Turing complete. Some mathematician who knows the rules should recheck the proof.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/120276#120276 Answer by ex0du5 for Which popular games are the most mathematical? ex0du5 2013-01-30T01:20:50Z 2013-01-31T01:46:59Z <p>Games are mathematical. That's not something you can avoid. If there are rules for moves and goal states, you've already entered mathematics through logic and proof theory. And even for the simplest games, there is a rich mathematical theory studying it's structure and analysing results.</p> <p>Mathematicians aren't just interested in finding optimal strategy and assigning a solution to a game. They also look to generalise and abstract theories of the gameplay and find ways to evaluate statements in the ontology of the game. Even simple games have rich logical calculi, and there are questions of rule independence and game extensions that can always be asked.</p> <p>Dynamic Epistemic Logic is one of the general settings in which more advanced theories of game play have been formulated. Whenever two or more people are involved in gameplay, there are important distinctions between belief, knowledge, shared knowledge, and strategy that must be made to fully understand the dynamics. DEL (and a number of related settings) have been used to evaluate many common games, from simple pebble and card games to complicated board games and beyond, as a means to understand the evolution of belief systems and evaluate strategy during the play.</p> <p><a href="http://www.illc.uva.nl/lgc/translation/papers/GamesinDEL.pdf%20%22The%20Dynamic%20Epistemic%20Logic%20of%20Games%22" rel="nofollow">The Dynamic Epistemic Logic of Games</a></p> <p><a href="http://olivier.amonbofis.net/docs/logic_decision_and_game_theory_final.pdf" rel="nofollow">Epistemic Logic and the Foundations of Decision and Game Theory</a></p> <p><a href="http://www.cs.bham.ac.uk/~mhe/.talks/mgs2011/escardo-theoretical-mgs2011.pdf" rel="nofollow">Selection Monads and the Relation Between Game Theory and Proof Theory</a></p> <p>I think the real mathematical answer to your question, then, is every popular game. There's no "most mathematical". Proof theory, models, modal logics, agent calculi and bisimulation lie at the heart of all games.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/130939#130939 Answer by Waldemar for Which popular games are the most mathematical? Waldemar 2013-05-17T10:08:41Z 2013-05-17T10:08:41Z <p>I’d like to emphasize that typical sports games (eg. played at Olympic games, NFL, MLB, NBA, NHL) often fit at least three criteria mentioned in the question. Before me, Barry Cipra mentioned baseball. These games are very useful to ‘popularize mathematics’, more precisely applied mathematics (operations research). Being a mathematician can help you play the game better (sometimes as a coach because we think of optimal strategies). And ‘mathematics is involved in a surprising way’ as people (students) generally don’t expect mathematics can help in such situations. The techniques used involve eg. dynamic programming, probability trees, game theory and Monte Carlo methods. As examples, I could give the following papers: a) Beaudoin, D., &amp; Swartz, T. B. (2010). Strategies for pulling the goalie in hockey. The American Statistician, 64(3), 197-204; b) Clarke, S. R., &amp; Norman, J. M. (2012). Optimal challenges in tennis. Journal of the Operational Research Society, 63(12), 1765-1772 c) Annis, D. H. (2006). Optimal end-game strategy in basketball. J Quant Anal Sports, 2(2). d) Kostuk, K. J., &amp; Willoughby, K. A. (2006). Curling's paradox. Computers &amp; operations research, 33(7), 2023-2031. e) Chiappori, P. A., Levitt, S., &amp; Groseclose, T. (2002). Testing mixed-strategy equilibria when players are heterogeneous: the case of penalty kicks in soccer. American Economic Review, 1138-1151. f) Tibshirani, R. J., Price, A., &amp; Taylor, J. (2011). A statistician plays darts. Journal of the Royal Statistical Society: Series A (Statistics in Society), 174(1), 213-226.</p> <p>For more on the topic, I recommend (Wright MB. “50 years of OR in Sport”. Journal of the Operational Research Society (2009) 60:S161-S168) or the short intro to this paper to be found here: <a href="http://ifors.org/web/ifors-september-2009-newsletter/" rel="nofollow">http://ifors.org/web/ifors-september-2009-newsletter/</a>. Moreover, Journal of Quantitative Analysis in Sports can also be of interest.</p> http://mathoverflow.net/questions/13638/which-popular-games-are-the-most-mathematical/130941#130941 Answer by Denis Serre for Which popular games are the most mathematical? Denis Serre 2013-05-17T11:22:14Z 2013-05-17T11:22:14Z <p>The two-player single suit whist has been analyzed completely in <a href="http://www.combinatorics.org/Volume_12/PDF/v12i1r43.pdf" rel="nofollow">this paper</a> by Johan Wastlund. This was mentionned by Alison Miller in her answer to my <a href="http://mathoverflow.net/questions/64525" rel="nofollow">MO question</a> <em>Bridge game with only one suit: strategy</em>.</p>