113
$\begingroup$

I consider a game to be mathematical if there is interesting mathematics (to a mathematician) involved in

  • the game's structure,
  • optimal strategies,
  • practical strategies,
  • analysis of the game results/performance.

Which popular games are particularly mathematical by this definition?


Motivation: 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.

Other examples:

  • go
  • bridge
  • Set.

Non-example: 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.

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.

Non-example: 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.


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. Does being a mathematician help you to learn the game faster, to play the game better, or to analyze the game more accurately? (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.

If my criteria seem horribly arbitrary as some have commented, so be it, but this seems in line with questions like Real world applications of math, by arxive subject area? or Cocktail party math. 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.

$\endgroup$
21
  • 70
    $\begingroup$ Yeah, well the rules of mathematics are chessly arbitrary. $\endgroup$ Feb 1, 2010 at 11:19
  • 43
    $\begingroup$ I think it's a mischaracterization to say chess is nonmathematical; it's just that chess, like so many things one encounters in the real world, is neither elegant nor simple from the point of view of mathematics. That game theory can't tell us much about chess tells us more about the limitations of game theory than about the mathematical nature of chess. That said, your suggested examples are definitely better. $\endgroup$ Feb 1, 2010 at 14:29
  • 11
    $\begingroup$ This is very far from 'give a list of all games.' One hope is to find other popular games whose play involves mathematics. Another is to learn more real mathematics about games I already know. A third idea is to see what resonates with other mathematicians. I'm sorry if you don't find these interesting, or if you find my criteria arbitrary--I don't see a huge difference between this and questions like, "What are neat applications of mathematics/this field?" $\endgroup$ Feb 1, 2010 at 17:56
  • 12
    $\begingroup$ You disagree with my statement that Nim is not actually played for fun? I can show you go clubs, bridge clubs, backgammon clubs, even a "world championship of rock-paper-scissors," etc. I've never seen a Nim club or heard someone describe himself or herself as a Nim player. There are many theoretical games people don't actually play, and I don't think it's arbitrary to exclude those. I'll clarify my reasons for excluding chess later. $\endgroup$ Feb 1, 2010 at 23:17
  • 22
    $\begingroup$ In "l'année dernière à Marienbad" ("last year in Marienbad"), a movie by Alain Resnais, you can see people playing Nim for fun. Now this just moves the problem, because I don't know anyone watching that movie for fun. (I just mean that peculiar movie. Resnais made a lot of very good movies. But that one is a serious contender for the prize of the most boring movie ever). $\endgroup$
    – Joël
    Oct 7, 2011 at 19:31

54 Answers 54

95
$\begingroup$

Set is a card game that is very mathematical.

12 Set cards

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 add up to the $0$-vector. The three cards pictured form a Set.

A natural question which arises during play is how many cards you can deal out without producing a Set. 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 at most $20$ cards not containing a Set, corresponding to a nondegenerate conic in the projective $3$-space containing $10$ points.

Lest anyone think it is "just a game", this has led to quite a bit of research, including applications to computational complexity of matrix multiplication.

$\endgroup$
11
  • 7
    $\begingroup$ Here's an online version for people wanting to see what it's like: setgame.ath.cx $\endgroup$ Feb 1, 2010 at 13:19
  • 2
    $\begingroup$ Does this satisfy the "popular" criterion? I haven't exactly seen many Set clubs around. $\endgroup$ Feb 2, 2010 at 5:58
  • 15
    $\begingroup$ It is at least popular enough that Set decks can be found in big-box bookstores like Borders or Barnes & Noble. $\endgroup$ Feb 2, 2010 at 6:31
  • 2
    $\begingroup$ I've seen people playing Set in public places a few times. $\endgroup$ Feb 2, 2010 at 10:31
  • 9
    $\begingroup$ Set is very popular with certain types of student clubs (e.g. math clubs), although I don't think it's really the kind of game that warrants its own clubs. $\endgroup$ Jun 7, 2011 at 16:14
71
$\begingroup$

Hex 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.

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).

11x11 Hex board

One variant is called Y. 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.

Commercial version of Y

$\endgroup$
4
  • 1
    $\begingroup$ I wonder: would it be possible to define a Hex analogue on the heptagonal or octagonal tiling of the hyperbolic plane? $\endgroup$
    – Eriek
    Feb 13, 2017 at 15:55
  • 1
    $\begingroup$ @Eriek Any progress on that thought? 😉‎ $\endgroup$ Sep 19, 2017 at 11:46
  • 2
    $\begingroup$ @Tobias Kienzler Yes, not hard to do. You can just play it on an embedding of the hyperbolic plane, like a Poincare disk. I found a way to play it on graph paper that (seems to) preserve the mechanics of the hyperbolic version: hexandoct.net16.net. Turns out Bill Taylor discovered an equivalent game he called "Quickway" prior to me. groups.google.com/d/msg/rec.games.abstract/dhDKiR1edBk/… $\endgroup$
    – Eriek
    Sep 22, 2017 at 20:22
  • $\begingroup$ @Eriek Making diagonal connections on a square grid is very different from octagonal tiling of the hyperbolic plane. $\endgroup$ Mar 12, 2018 at 7:23
55
$\begingroup$

This was a favorite pass time on my mobile. Its pushing blocks also known as Sokoban:

enter image description here

Some years ago it came as a little surprise to me that it is NP complete. Here is one paper saying that:

Demain, E.D. and Hoffmann, M.
Pushing Blocks is NP-Complete for Noncrossing Solution Paths, 2001
https://people.inf.ethz.ch/hoffmann/pub/dh-pbnns-01.pdf

Best Regards

$\endgroup$
2
55
$\begingroup$

Dots and boxes is a pencil-and-paper game with a reasonably deep mathematical theory. The game is often played by schoolchildren.

$\endgroup$
4
  • 2
    $\begingroup$ One thing interesting about Dots and Boxes is that it can often be well approximated by Nimstring which itsef can be mapped onto Nim. So the theory of Nim is important even if Nim itself isn't that interesting. $\endgroup$
    – Dan Piponi
    Feb 1, 2010 at 17:38
  • 5
    $\begingroup$ FWIW, at a very high level of play on a small board, nim theory is surprisingly irrelevant. Dots and boxes is a very mathematical game, but nim is only one component of it, and there are plenty of expert-level players on a 5x5 board who know nothing at all about nim but who will still wipe the floor with anyone who has read Winning Ways and assumes that they are now an expert. See for example littlegolem.net/jsp/forum/topic2.jsp?forum=110&topic=69 , a discussion which is visibly (a) mathematics and (b) relevant to dots and boxes, but (c) has nothing to do with Nim. $\endgroup$ Feb 2, 2010 at 11:34
  • 6
    $\begingroup$ It's mentioned in the Wikipedia article, but it may as well be mentioned again: Elwyn Berlekamp wrote a book on the mathematical theory of dots and boxes. $\endgroup$
    – Todd Trimble
    Oct 7, 2011 at 12:27
  • $\begingroup$ There's also wccanard.wetpaint.com . $\endgroup$ Oct 7, 2011 at 18:16
48
$\begingroup$

The game of Go 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 Mathematical Go: Chilling Gets the Last Point

alt text
(source: xmp.net)

$\endgroup$
18
  • 4
    $\begingroup$ Though I love Go, I can't agree that it has a mathematical feel except in the endgame. Set and Sudoku both seem to use the same sort of "proof" process that we're already used to; with the exception of Go endgames and perhaps complex ko fights, I rarely have the familiar "proving / deriving" feeling during a game. $\endgroup$ Feb 1, 2010 at 20:52
  • 4
    $\begingroup$ I think many of the ideas which you can prove in the go endgame (before infinitesimals) are present but too complicated to prove in much earlier stages. In addition, the connectivity fights in go seem like they should give you that feeling of proving elementary statements. You sometimes want to prove that you can connect one group of stones to another provided that there is no enemy stone added to a particular area. The smaller the area, the less you need to worry about that connection. $\endgroup$ Feb 2, 2010 at 1:47
  • 1
    $\begingroup$ go is so complex! clearly, it is mathematical, but my favorite part is its organic nature that openings and middle game take or feel like. $\endgroup$ Apr 7, 2010 at 3:01
  • 4
    $\begingroup$ Bu the way i've been thinking for a long time to a "continuous version" of go, where you can play anywhere on the field (not just at intersections). There would be some rules to modify but the overall seems more natural to me. Unfortunately I don't have the skills to program it, would someone be interested? $\endgroup$ Aug 27, 2011 at 14:35
  • 2
    $\begingroup$ @Aaron Mazel-Gee: There are big problems with this measure of complexity. Mixing luck in with skill does not cancel the skill, but it can decrease this measure of complexity to below 1. In the other direction, replacing a game with a best-of-n match does not change what it takes to learn to play the game, but it increases that measure of complexity. $\endgroup$ Jan 14, 2013 at 19:58
42
$\begingroup$

Believe it or not, Battle Ship is an interesting mathematical game. Well, at least if you play it in high enough dimension: Finding small explicit sets that hit all large enough combinatorial rectangles (ships) has been studied quite a lot and there are still a couple of open problems. See for instance, here.

$\endgroup$
1
  • 10
    $\begingroup$ Many children's games are surprisingly mathematically interesting. These games typically have very simple rules and very little scope for player strategy. This means that that the entire evolution of the game can be described by simple rules, which in turn means that the game can be treated mathematically. Even games like War and Candyland, which have no player strategy whatsoever, lead to interesting math. $\endgroup$ Jan 14, 2011 at 20:29
41
$\begingroup$

The ability to embed mathematical problems into chess (like combinatorial game theory into go) should not be underestimated. Papers by Richard Stanley and Noam Elkies demonstrate problems where the objective is to determine the number of ways to perform a given task. They include problems where the answer is

  • A Catalan number, say the 7th or even the 17th. (Problems A and B from Stanley. Problem A from Elkies.)
  • Fibonacci numbers, arbitrarily large. (Problem 4 from Elkies.)
  • The coefficients of the Maclaurin series for tangent, say the 7th or 9th. (Problem D from Stanley. Problems B and 1 from Elkies.)
  • 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.)

Of course, the answers are this for some mathematical reason, not accidentally. Many of the problems are also elegant from a chess perspective.

$\endgroup$
2
  • $\begingroup$ I have seen some problems they have constructed, however, the ones I have seen do not follow the normal objectives of chess, which is quite different from the connections between go and combinatorial game theory. $\endgroup$ Feb 1, 2010 at 10:29
  • 9
    $\begingroup$ Let me add that I am impressed by their ability to embed interesting problems in a game I still view as not mathematical. $\endgroup$ Feb 1, 2010 at 10:37
38
$\begingroup$

There's also the famous Rubik's Cube, which is popular and heavily maths-related.

$\endgroup$
4
  • 7
    $\begingroup$ But is that considered a game? $\endgroup$
    – Todd Trimble
    Oct 7, 2011 at 12:35
  • 2
    $\begingroup$ Rubik Cube has already been suggested (cannot add comment due to rep), although do not see why this is not a game, nevertheless lets just quote a couple of studies on the group theory of Rubik Cube Group Theory and the Rubik’s Cube and The Mathematics of the Rubik’s Cube Thanks $\endgroup$
    – Nikos M.
    May 23, 2014 at 18:18
  • 4
    $\begingroup$ Solving the Rubik's cube may be considered a one-player game. There are also many people who compete in speedcubing. en.wikipedia.org/wiki/Speedcubing $\endgroup$ May 23, 2014 at 19:04
  • $\begingroup$ To add to Douglas's comment, solving rubik's cube in fewest possible moves(FPM) is another event in cube championships, and this is more mathematically interesting. $\endgroup$ Jun 24, 2020 at 7:06
33
$\begingroup$

Poker is a family of card games.

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 Borel and von Neumann.

Nes Ankeny wrote a book Poker strategy: Winning with game theory in 1981 which gives an interesting mathematical approach to poker. Ankeny was a number theorist who was also a world-class poker player.

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 application 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.

Bill Chen and Jerrod Ankenman wrote The Mathematics of Poker 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.

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 remarked, "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."

[I merged two answers about poker.]

$\endgroup$
2
  • 3
    $\begingroup$ See also Alspach's articles: math.sfu.ca/~alspach/pokerdigest.html $\endgroup$ Feb 2, 2010 at 8:04
  • $\begingroup$ Thanks for the references. I'm trying to track down Ankeny's book, since I'm writing a book on practical poker math myself. The Brian Alpach articles I've read are applications of very basic combinatorics, e.g., using inclusion-exclusion to count how often there are k pairs dealt among n players. There is a lot more to poker math than the odds of various deals. $\endgroup$ Feb 2, 2010 at 22:08
32
$\begingroup$

Lights Out 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 here. What's particularly interesting is the fact that operations in the game commute, which allows for the linear algebra approach.

I wonder if there are any non-commutative turn based games which can also be solved mathematically? Certainly, chess is out of the question!

$\endgroup$
2
  • 2
    $\begingroup$ I gave a talk at MathFest in 2007 on the $n$-dimensional generalization of this game. Just assume your playing the game on a lattice and pressing a light changes all lights touching it. We also generalized the solution to include things like lights out on a torus or a sphere or a mobius band... The point is, all the solutions are similar and the generalization follows fairly easily by reconstructing the "button vectors" which are related to the change of state when pressing a particular button. $\endgroup$
    – B. Bischof
    Feb 2, 2010 at 17:43
  • 4
    $\begingroup$ I'm not sure about non-commutative turn based games, but certainly the puzzles presented in a number of popular video games can be easily described with non-abelian groups. One that comes to mind was a lever puzzle in the first God of War game. The state of a device was manipulated with two levers and a particular state would open the door. It turns out that the state space of this device was a group generated by the actions of the two levers. So proceeding in the game was equivalent to finding a representation of a given group element in terms of the generators. $\endgroup$ Oct 7, 2011 at 18:28
28
$\begingroup$

Clay Institute in its lectures on millennium problems list as one of it question "P vs NP Problem" 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 beginning of minesweeper article:

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.

$\endgroup$
27
$\begingroup$

What about Pool? It contains quite a lot of geometry.

$\endgroup$
1
26
$\begingroup$

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.

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.

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.

$\endgroup$
23
$\begingroup$

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.

  1. 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.

  2. 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.

  3. 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 higher order throw-ins, which can be analyzed via nimbers, etc.

$\endgroup$
5
  • $\begingroup$ I did have a short stub on bridge, but yours is better, so I'll delete mine. $\endgroup$ Feb 1, 2010 at 18:01
  • 2
    $\begingroup$ I understand that Meckstroth and Rodwell, probably the best pair in the US if not the world, once used the Fibonacci sequence in their bidding system. Never got to ask how… $\endgroup$
    – Chad Groft
    Apr 8, 2010 at 1:18
  • 3
    $\begingroup$ Hmm... I've never learned much about this, but some googling (see orig.gibware.com/moscito/moscito.pdf) suggests that common to all relay systems is the principle that a bid X permits the transfer of roughly the golden ratio times as much information as the bid X+1 permits. So that would sort of suggest designing your relay system around the fibonacci sequence, except successive EARLY fibonacci numbers are not that THAT close to the golden ratio, and probably it is these early values which would arise most often in actual play. So that might cost your system efficiency. $\endgroup$ Apr 8, 2010 at 15:34
  • $\begingroup$ I would add two more points: 1. "Restricted choice" (en.wikipedia.org/wiki/Principle_of_restricted_choice) is bridge player jargon for Bayes law. I am not sure there is any large community, other than strong bridge players, that contains many high school dropouts and where everyone is able to apply Bayes Law with reasonable accuracy. (Even bridge players who think of them as less mathematical/analytical would be annoyed to find out they made a play with 60% success rate, when there was one with 70% success rate available.) $\endgroup$ Aug 10, 2012 at 9:02
  • $\begingroup$ 2. The accepted standard approach to analyzing suit combinations is actually a fairly rigorous game-theoretic approach. Problem: Given declarer's and dummy's holding in a suit, how should declarer play this suit to get at least x tricks. The assumption is that he has to lead the suit every time (no endplays), and can lead from hand or from dummy at any trick as he chooses (sufficent entries). Analysis: Find a Nash equilibrium under the assumption that the defenders know declarer's hand, whereas declarer does not know the defenders' hands. The defenders' will often play a mixed strategy. $\endgroup$ Aug 10, 2012 at 9:11
20
$\begingroup$

Rock-Paper-Scissors remains a popular children's game. It's a simple 0-sum game with a mixed Nash equilibrium.

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.

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.

Cryptographic issues arise if you want to be confident that a distant opponent's choice was not made with knowledge of yours.

$\endgroup$
2
  • 8
    $\begingroup$ For what it's worth (i.e. nothing), Rock-Paper-Scissors is a commutative, non-associative magma. $\endgroup$ Oct 7, 2011 at 8:42
  • 12
    $\begingroup$ This game, also known as Roshambo, is surprisingly subtle if you try to design an algorithm that will win a round-robin tournament that includes some intentionally weak strategies. Exploiting weak strategies without opening yourself to exploitation is a tricky business. See for example webdocs.cs.ualberta.ca/~darse/rsbpc.html $\endgroup$ Oct 7, 2011 at 17:20
20
$\begingroup$

Sprouts is a game contrived by J. H. Conway and M. S. Paterson in the 1960s.

It is an impartial game for two players played on a plane with some spots. Each move consists of both

  1. 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
  2. placing a new spot on that curve.

Who makes the last move is the winner/loser according to normal/misère play convention.

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.

It enjoys some popularity, as reflected by the existence of a world association (the WGOSA, World Game of Sprouts Association).

There are rich graph-theoretic results concerning this game, for example see this page in NRICH and this section in Winning Ways. Experienced players make use of these results to set up goals.

Here 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 Sprouts on general surfaces ("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.

$\endgroup$
2
16
$\begingroup$

My vote is for the game "Clue".

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.

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.

$\endgroup$
2
  • $\begingroup$ This one: en.wikipedia.org/wiki/Cluedo ? $\endgroup$ Sep 11, 2015 at 7:27
  • 2
    $\begingroup$ There is some mathematical analysis of Clue(do) in Chapter 11 of van Ditmarsch and Kooi, One Hundred Prisoners and a Light Bulb. $\endgroup$ Nov 19, 2017 at 8:15
16
$\begingroup$

Tic-tac-toe and Gomoku (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.

The Hales–Jewett theorem 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.

Gomoku has been solved, constructively. (The first player wins.)

The game of Connect Four 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.)

$\endgroup$
4
  • 5
    $\begingroup$ FWIW, it is widely believed by expert players that connect 4 on an 8x8 board is a win for the 2nd player. Some expert players on the internet have played hundreds if not thousands of games over the last year or two and occasionally lose as player 1, but never as player 2. $\endgroup$ Feb 2, 2010 at 11:35
  • 4
    $\begingroup$ My goto-source for this kind information is the link homepages.cwi.nl/~tromp/c4/c4.html which has all boards with width+height <= 15. However, en.wikibooks.org/wiki/… claims that 8x8 is known to be a black (second player) win. $\endgroup$
    – aorq
    Feb 2, 2010 at 18:00
  • 3
    $\begingroup$ Tic-tac-toe can in fact be mapped: xkcd.com/832 $\endgroup$ Jun 28, 2012 at 11:43
  • $\begingroup$ Can anyone give a reference for the fact that Connect Four has been solved as a first player win? $\endgroup$ Jan 9, 2018 at 21:28
15
$\begingroup$

Backgammon is a game of skill and chance.

The doubling cube emphasizes absolute evaluations as opposed to relative evaluations, although it makes some some equities not exist, as the relevant series diverge.

Several areas of backgammon, from determining the appropriate doubling strategy to analyzing the race, are well-approximated by random walks with absorbing barriers.

The analysis of backgammon positions and strategies frequently involves Monte Carlo analysis, variance reduction techniques, and statistics.

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.

$\endgroup$
15
$\begingroup$

For some applications of combinatorial game theory to actual chess endgames, see the article by Elkies at https://arxiv.org/abs/math/9905198. 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 https://math.mit.edu/~rstan/papers/knight.pdf

$\endgroup$
14
$\begingroup$

I didn't see mention of Conway's The Game of Life. Is it a game? Well, Conway calls it a zero-player game! Other people call it a cellular automaton. You decide.

$\endgroup$
14
$\begingroup$

The game of Mafia, 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.

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—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.

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.

See also this MO question that announces a mathematical paper on the Mafia game.

$\endgroup$
3
  • $\begingroup$ Do you usually play with roles revealed on death? I think Mafia is more interesting if you don't do this precisely because it's easier to fake roles. $\endgroup$ Oct 7, 2011 at 19:01
  • $\begingroup$ Qiaochu: Yes, I've always played with roles revealed on death. Taking a quick look at the Wikipedia page, I see that this seems to be the most common way of playing the game. $\endgroup$ Oct 7, 2011 at 20:19
  • $\begingroup$ We always played without the roles revealed on death. $\endgroup$ Jun 28, 2012 at 13:36
13
$\begingroup$

More puzzles than games, but many of the number puzzles published by Nikoli 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.

The multi-player game Carcassonne 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.

$\endgroup$
0
12
$\begingroup$

Call a two player deterministic game finite if the game tree has finite depth. Now we can play...

Hypergame: 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.

Question: for the first move, can player one choose $\Gamma = \text{Hypergame}$?

$\endgroup$
5
  • 4
    $\begingroup$ This game is slightly more interesting if player two gets to choose who goes first in Gamma. As it stands, player one can choose to play the game "first player loses", so player two loses. $\endgroup$
    – aorq
    Feb 1, 2010 at 23:56
  • $\begingroup$ I hadn't thought about that variation.. it makes the question "What is the optimal strategy for player one?" much more interesting! $\endgroup$ Feb 2, 2010 at 1:55
  • 5
    $\begingroup$ Answer: No, because Hypergame is not a finite game. There are game trees of arbitrarily large depth. $\endgroup$
    – Chad Groft
    Apr 8, 2010 at 1:16
  • 1
    $\begingroup$ It depends on what you mean by "finite game", I suppose. I didn't mean that there was a uniform bound on the height of the game tree, but rather that there is no infinite sequence of moves. For example, take the game "n" where player one picks a natural number $n$ and play alternates for exactly $n$ moves, with the last player winning. I want to count this game as finite. $\endgroup$ Jun 13, 2011 at 16:40
  • 4
    $\begingroup$ This is actually the hypergame paradox, a game theoretic version (sort of) of Mirimanoff's paradox on well founded sets. Both answers lead to contradiction. $\endgroup$
    – godelian
    Oct 8, 2011 at 3:04
11
$\begingroup$

The game of Cootie, where players roll dice to collect parts of an insect (cootie), is a variant of the coupon collector's problem.

alt text

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 finite sum.

In particular, if you have $L$ objects to collect and for each object $\ell<L$ 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

$\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_{<q_k}(p_k x))dx.$ `

If you're interested, check out my paper out for the full computation.

$\endgroup$
1
  • $\begingroup$ The French version of te game is "Le cochon qui rit". English translation "The laughing pig". $\endgroup$ May 17, 2013 at 11:08
10
$\begingroup$

Bulls and cows and its modern variant Mastermind, 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.

$\endgroup$
2
  • 2
    $\begingroup$ Thanks, I had forgotten Mastermind, even though I worked on it as an undergraduate. There is a strategy known which takes the minimal expected number of guesses under the assumption that the code is chosen uniformly. That doesn't solve the $2$-player game but it is great progress. The strategy of guessing randomly among the codes consistent with the past information is only off by a fraction of a guess on average, IIRC about $4.7$ instead of $4.4$. I believe I read these results in the Journal of Recreational Mathematics. $\endgroup$ Jun 7, 2011 at 17:41
  • $\begingroup$ In a 1995 sci.math article, Mike Wiener announced a solution to the 2-player game with 4 pegs and 6 colors. groups.google.com/forum/?fromgroups=#!msg/sci.math/212BmJ5v7y0/… I do not know if anyone has independently confirmed this result. See also Near-optimal strategies for the game of Logik by Heeffer and Heeffer. logica.ugent.be/albrecht/thesis/Logik.ps $\endgroup$ Jan 30, 2013 at 16:05
9
$\begingroup$

Peg solitaire which I played on chess board in childhood. Let me explain this solitary game; consider the following table consisted of 33 holes.

There is a peg in all except one of the holes.(Assume that one is in the center). You can move a peg horizontally and vertically. The permissible move consists of jumping one peg over another into an empty hole and simultaneously removing the peg has been jumped over. One can continue this process to reach a situation than cannot have an acceptable move. And the player is winner if the last situation has only one peg.

Thus we can ask some question:

  1. Does this play has a winning strategy?

  2. What are the possible last situations?

enter image description here

The interesting point is the analysis of this game relates to the finite field with 4 elements, GF(4). The answer to question 1 is yes. For question 2 please consult the paper "A solitaire game and its relation to a finite field" by N. G. de Bruijin.

It seems the result of the paper can be extended. I think it is useful in a course in algebra, I exposed the paper when I was a TA in algebra 2.

$\endgroup$
3
  • 2
    $\begingroup$ There's also a discussion of this game in the beginning of Winning Ways, Volume 4, by Berlekamp, Conway, and Guy. $\endgroup$
    – Todd Trimble
    Nov 23, 2015 at 6:00
  • $\begingroup$ @ToddTrimble Thank you. I see it, that's interesting. $\endgroup$
    – Rahman. M
    Nov 23, 2015 at 8:15
  • $\begingroup$ Is it intentional that the title of the paper contains a link that goes to a picture? (Probably yes - at least Scholar Google doesn't return some link which would be a good replacement.) $\endgroup$ May 23, 2022 at 5:41
8
$\begingroup$

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.

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.

$\endgroup$
1
  • 2
    $\begingroup$ Indeed. If you meet someone who understands the "principle of restricted choice", they are almost certainly a mathematician or a bridge player (or both, of course). $\endgroup$
    – maproom
    Apr 30, 2014 at 14:18
8
$\begingroup$

Diplomacy was pretty much invented to illustrate points in cooperative game theory. At least, that's how Martin Shubik told me the story. :)

Actually, I think he invented a card game called "So long, Sucker", and claimed Diplomacy was based on that.

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?

$\endgroup$
2
  • $\begingroup$ If you can choose the winner (other than yourself), you are called the kingmaker. That's a common phenomenon in games with $3$ or more sides. en.wikipedia.org/wiki/Kingmaker $\endgroup$ Jan 15, 2013 at 20:12
  • $\begingroup$ A more mathematical aspect of diplomacy is the existence of end-game strategies that are not forced wins, but strategies exist with probability p of success for any p<1. See uk.diplom.org/pouch/Zine/F1995M/Dreier/Endgame.html and followup articles. $\endgroup$ Jan 18, 2019 at 3:00
8
$\begingroup$

I would be tempted to include Blackjack 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.

$\endgroup$

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