86
$\begingroup$

I'm planning out some research projects I could do with undergraduates, and it struck me that problems analyzing games might be appropriate. As an abstract homotopy theorist, I have no experience with this, so I'm writing to ask for some help. I think students will be more interested in popular games (in the US, to be precise), i.e. things they might have played growing up, e.g. Monopoly, Clue, Battleship, Sorry, Settlers of Catan, Dominion, Scrabble, Risk, Uno, Connect Four, Othello, Candyland, Checkers, bridge, war, gin rummy, etc. I suppose cell-phone games would also be interesting, but I don't know anything about them. I'm writing to get a sense of the literature, to make sure I don't duplicate something that's already been done, to get inspiration for the types of questions we could investigate, and to see where papers like this get published.

I'm looking for published papers that conduct a mathematical analysis, e.g. proving which player wins under optimal play, proving a game is NP-hard, or analyzing the probabilities (e.g. probability that there is no set in the game Set, if 12 cards are showing).

I'm already aware of the question "Which popular games are the most mathematical?" but it's asking for something different. Nevertheless, that link already discusses some math related to Chess, Go, backgammon, battleship, poker, minesweeper, mastermind, connect four, Mafia, Magic: The Gathering, and some cell-phone games: "Pushing Blocks", "Pixelated" (in BlackBerry) aka "Flood-It" (in iPhone). However, it doesn't give published references for all of these games, and doesn't discuss any other popular games, e.g. games from this list. I added links above to the closest I could find to a published reference, to give an idea of what I'm looking for.

Lastly, I am well-aware that sports can be analyzed mathematically, so no need to write an answer about baseball, basketball, etc. And, I'd like to avoid answers about games that people don't really play in the real world, like Nim, subset take-away, etc. There are a whole bunch of examples on the other mathoverflow question, but I don't think they'll capture student interest in the same way.

$\endgroup$
21

27 Answers 27

42
$\begingroup$

A few years ago several classic Nintendo games (including Mario, Donkey Kong, and Legend of Zelda) were examined from a computational complexity point of view. They proved that generalized versions of these games are NP-hard, and in some cases PSPACE-hard.

Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta, "Classic Nintendo games are (computationally) hard," Theoretical Computer Science 586 (2015), link

$\endgroup$
6
  • $\begingroup$ This is an answer on one of the linked questions too mathoverflow.net/a/104274 $\endgroup$
    – j.c.
    Jan 9, 2018 at 22:19
  • $\begingroup$ Cool, looks like Demaine does a lot in this area! He also wrote the paper about the Pushing Blocks game that I linked to in the question. And his work gets published in top journals, so maybe that's a style to emulate. Thanks! $\endgroup$ Jan 10, 2018 at 0:14
  • $\begingroup$ Were any of the "Nintendo-Hard" games like Battletoads analyzed? $\endgroup$
    – AHusain
    Jan 11, 2018 at 0:00
  • $\begingroup$ @AHusain: I just looked up "Nintendo-hard" on Wikipedia (I had never heard the term before). The Wikipedia article gives a list of Nintendo-hard games, and two of the games on that list were analyzed in the paper I linked to (Super Mario Bros.: the Lost Levels and Zelda II: the Adventure of Link). But most Nintendo-hard games are not covered by the paper. If you're curious enough, you could try looking at other papers either citing or cited in the one I linked to, and you will find similar analyses of other Nintendo games (but I don't know which ones off the top of my head). $\endgroup$
    – Will Brian
    Jan 11, 2018 at 14:20
  • 3
    $\begingroup$ @AHusain One problem with analyzing a game like Battletoads in particular from a complexity point of view is that several levels play by fundamentally different rules. Most levels are tile-based platforming sections, much like Super Mario, and most of the analysis Aloupis et. al. provided for SMB probably would apply for Battletoads as well. But there's also the bike-riding level, in which you can move up or down and jump, but are always propelled to the right. As a result, that level is arguably in P: A route can be found in O(number of obstacles) time by dodging each obstacle that appears. $\endgroup$
    – Kevin
    Jan 11, 2018 at 21:22
32
$\begingroup$

Hex (https://en.wikipedia.org/wiki/Hex_(board_game)) is a board game that was developed by John Nash (and independently and earlier, Piet Hein). It is interesting mathematically in a number of ways. For example, unlike something like chess, it is easy to see that under optimal play the first player will win a game of Hex. But though it is known that the first player should win, even for relatively small board sizes it is not known what this optimal strategy is. Nevertheless, about a decade ago a group of probabilists showed something quite surprising: if we add a little randomness to the game of Hex, then it is quite easy to describe the optimal strategy. Namely, Peres-Schramm-Sheffield-Wilson (https://arxiv.org/abs/math/0508580) considered "random turn" Hex, where a coin is flipped every turn and the player who won the coin flip gets to place a piece that turn. They showed that this game is closely connected to the theory of percolation and in particular the best space on which to put a piece is the one most likely to be "critical" in a random percolation of the open spaces on the board (this optimal move can be computed quickly e.g. via Markov chain Monte Carlo methods).

$\endgroup$
5
  • $\begingroup$ Thanks for your answer. I left Hex out of my question because I never thought it was a real game, but at the bottom of the wiki page is a link to a website called boardgamegeek.com, where you can buy it. I will note, however, that I couldn't find it on amazon.com. Not sure my students will have played it. Did you play it as a kid? Or know anyone who did? $\endgroup$ Jan 10, 2018 at 0:35
  • $\begingroup$ @DavidWhite: whoops, I think I missed that thrust of the post. Sorry. No, I did not know about Hex until I was already interested seriously in math. $\endgroup$ Jan 10, 2018 at 0:37
  • 2
    $\begingroup$ Hex is indeed a real game, in that it was played by many real people. As a personal anecdote, my late father-in-law constructed his own hex board, which is still around the apartment somewhere. In addition, the 3M company made a (non-credited) version of hex called Twixt. $\endgroup$
    – Lee Mosher
    Jan 10, 2018 at 14:02
  • $\begingroup$ @SamHopkins I suspect you mean "critical" rather than "crucial". Although some senses of these words overlap in meaning, I have never heard of "crucial" being used in percolation theory. $\endgroup$ Jan 10, 2018 at 17:56
  • $\begingroup$ @RobertFurber: sorry about that, I was following terminology from this blog post: mathtourist.blogspot.com/2007/05/random-turn-hex.html?m=1. $\endgroup$ Jan 10, 2018 at 18:47
31
$\begingroup$

The board game Monopoly is often used to explain Markov Chains to laypeople. Ian Stewart has a couple of Mathematical Recreations articles about it in Scientific American.

The first (in the April 1996 issue) has the title "How Fair is Monopoly?" (A copy it can be found here.)

The second (in the October 1996 issue) has the title "Monopoly Revisited" (A copy of it can be found here.)

$\endgroup$
5
  • $\begingroup$ (This is similar to my answer here.) $\endgroup$
    – JRN
    Jan 10, 2018 at 1:10
  • 2
    $\begingroup$ Here is a somewhat earlier (April 1973) article by Irwin Hentzel in Saturday Review of the Sciences about Monopoly. $\endgroup$ Jan 10, 2018 at 15:01
  • $\begingroup$ @AlexanderBurstein, thanks for the link! This is the first time I've heard of that journal. $\endgroup$
    – JRN
    Jan 11, 2018 at 3:51
  • $\begingroup$ @JoelReyesNoche I think Saturday Review has not been published for about 30 years now. $\endgroup$ Jan 11, 2018 at 4:02
  • $\begingroup$ On the subject of monopoly, I suggest youtube.com/watch?v=ubQXz5RBBtU as a nice accessible reference using two methods of analysis. $\endgroup$
    – Kaithar
    Jan 11, 2018 at 17:50
19
$\begingroup$

Rubik's Cube puzzle https://www.youcandothecube.com/blog/puzzling-science-using-the-rubiks-cube-to-teach-problem-solving gives an excellent possibility for some musings in mathematics and physics. See, for example, https://www.sciencedirect.com/science/article/pii/0378437182903624 https://arxiv.org/abs/1106.5736 https://arxiv.org/abs/1706.06708 https://arxiv.org/abs/1708.05598 https://arxiv.org/abs/1611.07437 https://arxiv.org/abs/1702.06217 and articles cited therein.

P.S. I'd like to add also this book https://jhupbooks.press.jhu.edu/content/adventures-group-theory (Adventures in Group Theory: Rubik's Cube, Merlin's Machine, and Other Mathematical Toys, by David Joyner).

$\endgroup$
1
  • $\begingroup$ Wow, those are some amazing references. Much deeper than I expected. Thanks! $\endgroup$ Jan 10, 2018 at 12:05
19
$\begingroup$

Winning Ways for your Mathematical Plays (Wikipedia link) by Berlekamp, Conway and Guy, 1982.

This is a book discussing two-player full-information games. It is very good. While most of the games in the book are not in any way popular, some of them are. The Wikipedia article gives a partial list.

The book builds on an earlier book On Numbers and Games (Wikipedia) by Conway, 1976. This earlier book is more mathematical and mentions far fewer games.

The methods in these books can be used for any such game. Berlekamp has later written several articles on Go and Chess.

$\endgroup$
2
  • $\begingroup$ Cool that snakes and ladders appears in the book. That's the only game I recognized but I'm not much of a gamer. Thanks for sharing! $\endgroup$ Jan 10, 2018 at 12:06
  • 4
    $\begingroup$ These books started an entire field of combinatorial game theory. Look up Games of No Chance and related books on Amazon, for example, or Mathematical Go: Chilling Gets the Last Point or Dots and Boxes: Sophisticated Child's Play. See also Fraenkel's dynamic survey: combinatorics.org/ojs/index.php/eljc/article/view/DS2 $\endgroup$ Jan 11, 2018 at 4:13
18
$\begingroup$

IMO one of the most important recent work related to the computational complexity of (puzzle) games is the Nondeterministic Constraint Logic model of computation developed by Robert A. Hearn and Erik D. Demaine:

Robert A. Hearn and Erik D. Demaine, "Games, Puzzles, and Computation", 2009

The framework can be used to easily prove the complexity of the generalization of many single player and two players puzzle games (you can find many examples in the book).

You can also find other (original) examples on my site (due to lack of time many of them are still unpublished draft results). I picked some of them from the Simon Tatham's Portable Puzzle Collection and proved their complexity for fun. So I think that another good source of "ideas" are the casual puzzle games that are available online (in flash/html5); you can make a google search to find the most played.

Note that there are also many "open problems"; for example the complexity of 1x1 Rush Hour, the complexity of Lunar Lockout without fixed blocks, wether some falling blocks games that are NP-hard are contained in NP, and so on ... you can give them a try but the proofs are probably not so easy :-D

$\endgroup$
2
  • 1
    $\begingroup$ @DavidWhite: Another recent application of the NCL framework: The complexity of snake and undirected NCL variants ;-) $\endgroup$ Jan 10, 2018 at 0:27
  • 1
    $\begingroup$ Hearn's PhD dissertation of the same title can be found on Demaine's website here. Their work introduced me to Rengo Kriegspiel - blindfolded team Go. In the book they remark that this is 'a game humans play that is not obviously decidable; we are not aware of any other such game". $\endgroup$ Jan 10, 2018 at 21:55
16
$\begingroup$

Demaine et al. proved in this paper that Tetris is NP-hard.

More of a gimmick but: Based on that paper, Szita & Lörincz tried to teach a number of algorithms to play Tetris in this paper.

$\endgroup$
4
  • $\begingroup$ That's awesome! And makes me feel better for never being able to beat the last level of Tetris $\endgroup$ Jan 10, 2018 at 12:08
  • 2
    $\begingroup$ Similarly puyopuyo is NP-complete. link.springer.com/referenceworkentry/10.1007/… $\endgroup$ Jan 13, 2018 at 9:40
  • 3
    $\begingroup$ Heidi Burgiel has a paper "How to Lose at Tetris" that shows that there is a "fatal" sequence of pieces that will cause you to lose no matter what your strategy. $\endgroup$ Jan 16, 2018 at 2:59
  • 3
    $\begingroup$ Heidi Burgiels paper can be found here. (Just because I was really curious to read it and thought I'd share it :)) $\endgroup$
    – Wolter
    Jan 16, 2018 at 6:59
12
$\begingroup$

Game of Fifteen, a.k.a. the 15-Puzzle, was very popular 100+ years ago. The game is still found in stores; for example, you can search Amazon for "15 Puzzle" and get it for about 5 dollars.

In the paper Notes on the 15 puzzle (American Journal of Mathematics, 1879, Vol. 2, No. 4, 397-404) W.W. Johnson and W.E. Story showed, via parity argument, that half of the positions in the puzzle are not solvable. The parity argument is accessible even to high school students.

Editors' note accompanying the paper by Johnson & Story (1879) in American Journal of Mathematics is quite interesting:

The "15" puzzle for the last few weeks has been prominently before the American public, and may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community. But this would not have weighed with the editors to induce them to insert articles upon such a subject in the American Journal of Mathematics, but for the fact that the principle of the game has its root in what all mathematicians of the present day are aware constitutes the most subtle and characteristic conception of modern algebra, viz: the law of dichotomy applicable to the separation of the terms of every complete system of permutations into two natural and indefeasible groups, a law of the inner world of thought, which may be said to prefigure the polar relation of left and right-handed screws, or of objects in space and their reflexions in a mirror. Accordingly the editors have thought that they would be doing no disservice to their science, but rather promoting its interests by exhibiting this a priori polar law under a concrete form, through the medium of a game which has taken so strong a hold upon the thought of the country that it may almost be said to have risen to the importance of a national institution. Whoever has made himself master of it may fairly be said to have taken his first lesson in the theory of determinants. It may be mentioned as a parallel case that Sir William Rowan Hamilton invented, and Jacques & Co., the purveyors of toys and conjuring tricks, in London (from whom it may possibly still be procured), sold a game called the "Eikosion" game, for illustrating certain consequences of the method of quaternions. -EDS.

$\endgroup$
3
  • $\begingroup$ Yes, I knew this result, but didn't know it went back to 1879. Wow! That's good motivation for the study of popular games! $\endgroup$ Jan 10, 2018 at 12:07
  • $\begingroup$ That may be an accurate reproduction of the editors' note but I thought it was called Hamiliton's Icosian game - essentially finding a Hamiltonian path or cycle on the edges of a dodecahedron $\endgroup$
    – Henry
    Jan 12, 2018 at 23:44
  • $\begingroup$ The name of Hamilton's game is derived from the Greek word "$\varepsilon\acute{\iota}\kappa o\sigma\iota$" (twenty). The editors used a spelling closer to the Greek. Mathworld as well as most modern sources use the "Icosian" spelling $\endgroup$
    – Alex
    Jan 13, 2018 at 1:05
12
$\begingroup$

There is a small industry asking how many times you have to shuffle a deck of cards to ensure it is "randomized." Answering this question is essential to ensuring fair play in card games. If the deck is not randomized, some players may have an advantage.

Answers to this question build on a simple, but powerful, model of shuffling. These models treat a shuffle as inducing a probability measure on the set of permutations of the deck. A series of shuffles is thus a Markov chain. As these chains get longer -- as the deck is shuffled more -- the probability distribution on the permutations converges to the uniform distribution. The important question is: How fast do the distributions converge? In other words: How many times must we shuffle to ensure a fair deal?

The most famous answer, seven, was given by Bayer & Diaconis, "Trailing the Dove-tail Shuffle to Its Lair," Annals of Applied Probability Vo. 2, pp. 294-313, 1992. ("Most famous answer" = they made the NYTimes.)

Using a different measure of randomness (entropy instead of variation distance) Trefethen & Trefethen say shuffling five times will do: "How Many Shuffles to Randomize a Deck of Cards?," Proceedings: Mathematical, Physical and Engineering Sciences, Vol. 456, pp. 2561-8 (2000).

Both papers are available on line, as are many, many more papers on the subject. There are also lots of blog posts discussing and summarizing the literature.

PS Your students will probably enjoy hearing a little about Diaconis' life path, which is unique under any metric.

$\endgroup$
1
  • $\begingroup$ Thanks for sharing. I knew about the Diaconis paper (and his life story), but didn't know about the follow-up. Undergrad research usually happens in the summer before senior year, and it would be a VERY rare student who knew about probability measures in their junior year. Not impossible, but rare. I'll keep these sorts of problems in mind, but it's also not clear what open problems in this area are appropriate for undergraduates. $\endgroup$ Jan 11, 2018 at 11:52
11
$\begingroup$

Coming at this from a different perspective, games designer Raph Koster gave a very interesting presentation a while back about methods of taking existing computation problems thare are known to be difficult and embedding them into games, giving a lot examples of how part or all of existing games relate to standard well known problems (e.g. knapsack problem, 3-sat, etc). See https://www.raphkoster.com/games/presentations/games-are-math-10-core-mechanics-that-drive-compelling-gameplay/ for slides and a link to a recording of the presentation (although unfortunately paywalled).

$\endgroup$
0
11
$\begingroup$

The analysis of a mathematical model of Scrabble can be found in

M. Lampis, V. Mitsou, K. Sołtys: Scrabble is PSPACE-complete, in E. Kranakis, D. Krizanc, F. Luccio (eds) Fun with Algorithms. FUN 2012. Lecture Notes in Computer Science 7288, Springer (2012).

It turns out that Scrabble-Solitaire is NP-complete and (as the title suggests) Scrabble is PSPACE-complete.

$\endgroup$
0
9
$\begingroup$

There are a few popular games where the object is to infer some unknown information, and in some cases there has been some nice mathematical analysis of advanced strategies.

  1. Peter Winkler's classic paper on The Advent of Cryptology in the Game of Bridge shows how you can covertly communicate information to your partner even when your opponents are fully informed about your bidding system. You can think of Winkler as implementing a crude form of public-key cryptography in a bridge bidding system.

  2. The game of Clue (a.k.a. Cluedo) is analyzed in the book One Hundred Prisoners and a Light Bulb by Hans van Ditmarsch and Barteld Kooi.

  3. You may not have heard of the game Hanabi because it was invented pretty recently, but it won the prestigious Game of the Year award in 2013, and is still selling pretty well. There was an article called How to Make the Perfect Fireworks Display in the Mathematics Magazine which developed a powerful strategy for Hanabi using ideas from the theory of error-correcting codes.

$\endgroup$
0
7
$\begingroup$

Not sure how often it is played, but let me include it for a bit of cultural diversity: https://en.wikipedia.org/wiki/Dreidel MR2198856 (2007c:60074) Robinson, Thomas(1-RTG); Vijay, Sujith(1-RTG) Dreidel lasts O(n^2) spins. (English summary) Adv. in Appl. Math. 36 (2006), no. 1, 85–94 The list of references is also worth checking as it has some more elementary accounts.

$\endgroup$
0
7
$\begingroup$

If solitaire games are included, then the popular sudoku puzzle qualifies. For example, after years of brute-force computer searches guided by structural analysis, it was discovered that a minimum of 17 starter cells was necessary to determine the complete 9$\times$9 matrix. This involved many researchers from 2005, culminating in the 2012 paper by McGuire et al..

$\endgroup$
1
  • $\begingroup$ Great example, thanks! $\endgroup$ May 25, 2020 at 21:49
6
$\begingroup$

Perhaps this is only tangentially relevant to what you want, as the people who are most interested in this are not mathematicians but health scientists interested in using certain games as models for the spread of disease. That said, a particularly infamous incident in World of Warcraft has attracted the attention of many serious researchers, some of whom have published papers in scientific journals on the matter (for example, the following two papers: https://www.ncbi.nlm.nih.gov/pubmed/17301707 and http://www.sciencedirect.com/science/article/pii/S1473309907702128).

A Wikipedia summary of the incident can be found here: https://en.wikipedia.org/wiki/Corrupted_Blood_incident

As a young lad I experienced this myself while playing the game.

$\endgroup$
1
  • $\begingroup$ Interesting. I agree that it doesn't help me do math research with undergraduates, but it's fascinating. Thanks for sharing. $\endgroup$ Jan 10, 2018 at 14:50
6
$\begingroup$

A couple papers about infinite chess:

In response to the MO question "Decidability of chess on an infinite board", Joel David Hamkins mentions his paper accepted to CiE2012:

D. Brumleve, J. D. Hamkins and P. Schlicht, "The mate-in-n problem of infinite chess is decidable," 10 pages, arxiv pre-print, submitted to CiE 2012.

Abstract. Infinite chess is chess played on an infinite edgeless chessboard. The familiar chess pieces move about according to their usual chess rules, and each player strives to place the opposing king into checkmate. The mate-in-$n$ problem of infinite chess is the problem of determining whether a designated player can force a win from a given finite position in at most n moves. A naive formulation of this problem leads to assertions of high arithmetic complexity with $2n$ alternating quantifiers---there is a move for white, such that for every black reply, there is a counter-move for white, and so on. In such a formulation, the problem does not appear to be decidable; and one cannot expect to search an infinitely branching game tree even to finite depth. Nevertheless, the main theorem of this article, confirming a conjecture of the first author and C. D. A. Evans, establishes that the mate-in-$n$ problem of infinite chess is computably decidable, uniformly in the position and in $n$. Furthermore, there is a computable strategy for optimal play from such mate-in-$n$ positions. The proof proceeds by showing that the mate-in-$n$ problem is expressible in what we call the first-order structure of chess $\frak{Ch}$, which we prove (in the relevant fragment) is an automatic structure, whose theory is therefore decidable. Unfortunately, this resolution of the mate-in-$n$ problem does not appear to settle the decidability of the more general winning-position problem, the problem of determining whether a designated player has a winning strategy from a given position, since a position may admit a winning strategy without any bound on the number of moves required. This issue is connected with transfinite game values in infinite chess, and the exact value of the omega one of chess $\omega_1^{\rm chess}$ is not known.

The same author responded to a similar MO question "Checkmate in $\omega$ moves?" mentioning this paper (accepted to INTEGERS) :

C. D. A. Evans and Joel David Hamkins, Transfinite game values in infinite chess, under review.

Abstract. We investigate the transfinite game values arising in infinite chess, providing both upper and lower bounds on the supremum of these values---the omega one of chess---denoted by $\omega_1^{\mathfrak{Ch}}$ in the context of finite positions and by $\omega_1^{\mathfrak{Ch}_{\hskip-1.5ex{\ \atop\sim}}}$ in the context of all positions, including those with infinitely many pieces. For lower bounds, we present specific positions with transfinite game values of $\omega$, $\omega^2$, $\omega^2\cdot k$ and $\omega^3$. By embedding trees into chess, we show that there is a computable infinite chess position that is a win for white if the players are required to play according to a deterministic computable strategy, but which is a draw without that restriction. Finally, we prove that every countable ordinal arises as the game value of a position in infinite three-dimensional chess, and consequently the omega one of infinite three-dimensional chess is as large as it can be, namely, true $\omega_1$.

If you like pictures, check this one out.

$\endgroup$
2
  • $\begingroup$ I was actually reading about logic when I came across Hamkins' blog and remembered seeing this question about games $\endgroup$
    – Ben Burns
    Jan 10, 2018 at 14:33
  • 5
    $\begingroup$ I'm sorry, but I don't really think this answers my question. Infinite Chess is the definition of something my students could never have played growing up, i.e. it's not a "popular game" because it doesn't exist in the real world. $\endgroup$ Jan 10, 2018 at 14:49
6
$\begingroup$

Many studies took place for Magic: The Gathering card game. They mainly deal about optimization of combos, and are naturally related to many problems in computability or complexity. Busy beavers are an instance of summits we can attain with Magic: The Gathering combos.

The precise mission of the article is:

to deal as much damage as you can to the opponent by the end of the first turn, yet a finite amount.

For a story of the developments of this fun yet serious problem, and description of the involved combos, see Sonic Center.

$\endgroup$
2
  • $\begingroup$ Can you give any citations or links to studies of the sort you are discussing? I'd love to read something with a bit of formal mathematics in it. $\endgroup$ Jan 17, 2018 at 14:21
  • $\begingroup$ @DavidWhite I believe the link I provided in the Sonic Center give many references and some other facts that has been studied concerning Magic: The Gathering. For instance, it is Turing complete (cf. toothycat.net/~hologram/Turing) $\endgroup$ Jan 17, 2018 at 14:24
6
$\begingroup$

T. Walsh- Candycrush is NP-hard, reference here , To generalize even match 3 games are NP-hard reference here , bejewelled, Candycrush, and more Match -3 games, Sort of used gadgetry to produce the NP hardness, and reduction to 3SAT(?). The unique version of the game was co-NP hard. May be there are other games that just are co-NP hard, or co-NP. Even went viral the proof! But, Conways' treatment of Nim, and some two player games, in "Numbers and Games", was quite rigorous, with polyminoes, and other group theoretic constructs.

Or for size the green haired "Lemmings game", in which lemmings try to escape to safety- proof by G Cormonde . Maybe the lemmings game could lead to show other path based games are NP-hard. Planar 3 SAT may be a good place for proving NP-hardness for some such games, example "Shakashaka" a sodoku like game(linked to integer programming), which is proven to be NP-complete by Demaine, others. Also, counting solutions to "Shakashaka" is also #P complete.

$\endgroup$
1
  • $\begingroup$ Thanks! One of my colleagues loves Candycrush, so maybe she'll want to get in on a project analyzing it. With so many games coming out every year, it seems you could make a whole career out of showing they are NP hard $\endgroup$ Jan 11, 2018 at 11:46
6
$\begingroup$

Cards in the card-game Spot-It! include 8 different charms (such as a scissor, a ginger-bread man, a spiderweb, etc.) chosen from a set of 57 different charms. The rules of the card-game of Spot-It! include being presented with two cards from the deck; the winner is the first person to identify the charm that's common between the two cards.

Although the game-play is not so mathematical, and the skills needed to win involve quick observation and focus, the design of the deck of cards leads to investigations of finite projective geometry and the Ray-Chaudhuri–Wilson theorem.

It’s mathematical structure (a finite projective plane of order 7) is discussed in

In short, each charm corresponds to point on the projective plane, and each card to a line on this plane. Two lines (cards) have exactly one point (charm) in common, which is the basis of the game mechanics.

See also, this recent (2021) YouTube video from Matt Parker.

$\endgroup$
1
  • $\begingroup$ Thanks, I look forward to reading about this. I don't know that game but maybe my students would. $\endgroup$ Jan 17, 2018 at 15:50
5
$\begingroup$

According to Wikipedia, termination of Beggar My Neighbour (a game of no skill whatsoever also known as Strip Jack Naked and less printable things) is still open and was listed by John Conway as an anti-Hilbert problem that should not drive mathematical research. They call it long standing; I think it was in the 1970’s that I heard of it (from Alan Ross of U/non-U fame, oddly enough).

$\endgroup$
2
  • 1
    $\begingroup$ Yeah, wikipedia says Egyptian ratscrew is a generalization of this game, and I'll bet my students would have played that at some point. Plus, I love the history as an anti-Hilbert problem. Thanks! $\endgroup$ Jan 12, 2018 at 22:57
  • $\begingroup$ I had never heard of Egyptian Ratscrew, which changes the character to something closer to Racing Demons — glad to have learnt of it! Since it is no longer deterministic the termination question no longer applies, of course. I also belatedly realise that your question was tagged [computational complexity], which I had overlooked and does not apply particularly to either game, I fear. But I now see in your highlighted section that that was just an one example of a way a game could be analysed mathematically. $\endgroup$
    – PJTraill
    Jan 12, 2018 at 23:17
5
$\begingroup$

The College Mathematics Journal has been publishing expository mathematics around games for quite a while. Starting in 2013, these have been largely focused in the September issues. Topics have included Boggle, Candy Crush, Carcassonne, Chomp, Chutes and Ladders, Instant Insanity, KenKen, Mancala, Mastermind, Nim, Quirkle, Rubik's Cube, Rubik's Slide, Rock-Paper-Scissors-Lizard-Spock, SET, Settlers of Catan, Sudoku, War, and Wheel of Fortune (not to mention several dedicated to various sports).

You might also look at the three-volume set MOVES (mathematics of various entertaining subjects) from Princeton University Press, proceedings of a biannual recreational mathematics conference sponsored by the National Museum of Mathematics. In the most recent one, for example, I analyzed a one-time smart phone game called Khalou.

$\endgroup$
4
$\begingroup$

There have certainly attempts to apply statistics and machine learning towards drafting teams in Dota 2. [1]

Alan "Nahaz" Bester does a lot of statistical analysis of Dota 2 games. Search for some of his lectures on YouTube. [2]

Sources and References:

[1] Conley, Kevin, and Daniel Perry. "How does he saw me? A recommendation engine for picking heroes in Dota 2." Np, nd Web 7 (2013).

[2] Ciubotaru, Andra. “Nahaz Interview: Balancing Dota, Family Life and Academia.” Dota Blast, 23 Jan. 2016, dotablast.com/nahaz-interview-frankfurt-major-dota-family-life-academia/.

$\endgroup$
1
  • $\begingroup$ I never heard of Dota 2, but it looks popular enough that my students will have. I like that reference [1]. Thanks for sharing! $\endgroup$ Jan 11, 2018 at 11:54
4
$\begingroup$

We did exactly that with several groups of undergraduates over several years -- studying the game of monopoly, both finding optimal strategies and analyzing the length of the game. It was a great experience for them to apply complex mathematics to something very familiar. Most of the results went in unpublished theses, but one was published in a conference, https://www.informs-sim.org/wsc09papers/036.pdf

It was fun to discover that our university president at the time had written a book on monopoly many years earlier: Lehman, J., and J. Walker. 1975. 1000 ways to win at Monopoly https://www.amazon.com/1000-Ways-Win-Monopoly-Games/dp/0440048125.

However, be warned that there is also some danger, such as a snarky newspaper article making fun of our work.

$\endgroup$
3
$\begingroup$

From Wikipedia:

The "Instant Insanity" puzzle consists of four cubes with faces colored with four colors (commonly red, blue, green, and white). The objective of the puzzle is to stack these cubes in a column so that each side (front, back, left, and right) of the stack shows each of the four colors.

The Wikipedia page discusses a solution to the puzzle using graph theory. The graph theoretic solution is also discussed in Chapter 8 of Arthur Benjamin, Gary Chartrand, and Ping Zhang's "The Fascinating World of Graph Theory" (Princeton University Press, 2015).

$\endgroup$
0
1
$\begingroup$

The game "SET" can be nicely modeled by interpreting cards as elements in $\mathbb{F}_3^4$. I don't know which is the best reference for this, but a quick search yielded https://pdfs.semanticscholar.org/4eb2/344695144ac49345515d455244517ff3bcba.pdf, which seems already interesting. It contains some further references on SET, and analyzes "SETless collections" using conics.

$\endgroup$
2
  • 2
    $\begingroup$ Did you notice that in the comments on the question there's mention of a book and a blog post on SET? $\endgroup$ Feb 14, 2018 at 11:56
  • $\begingroup$ Ah, I tried to see if work on SET had already been mentioned, but I failed to account for all the comments. $\endgroup$ Feb 14, 2018 at 12:55
1
$\begingroup$

In theoretical computer science, there is a (serious, peer reviewed, high quality) international conference series named "fun with algorithms". A lot of puzzles and board games and computer games have been studied mathematically or/and algorithmically in the volumes of this series. Be it Lemmings, Tantrix, Nurikabe, picture hanging puzzles, or hyperbolic (!) minesweeper.

See here for tables of contents: https://dblp.org/db/conf/fun/index.html

BTW, a while back the conference series went open access.

$\endgroup$
1
$\begingroup$

Checkers, or Draughts, has been solved. With best play the game is a draw. The proof took one of the longest times to compute, ever. It was written by Jonathan Schaeffer.

https://www.newscientist.com/article/dn12296-checkers-solved-after-years-of-number-crunching/

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.