An Infinite Drinking Game

Éloïse and Abélard are spending an infinite evening together and are looking for a way to kill time. After a bit of to-ing and fro-ing over what to do, they decide they better go out and buy some bottles of wine.

Having successfully purchased a nice assortment of different wines at different price points, they return to Éloïse’s house in a jubilant mood.

Éloïse is a big fan of board games and has left a variety of boards and pieces lying on her kitchen table. Most of these boards have the form of a graph, consisting of some squares connected by directed edges showing how to move a piece from one square to the next.

In order to maximally enjoy their wine over the course of the infinite evening, Éloïse suggests using one of these graph-like game boards as a basis for a new drinking game. She proposes the following idea: some squares will be coloured green and “owned” by her, and some squares will be coloured red and “owned” by Abélard. They place some glasses of wine on the squares in such a way that every cycle contains at least one glass of wine. They then place a single piece on the board. The rule is that if Éloïse owns the square the piece is on, she gets to move it. If Abélard owns the square the piece is on, he gets to move it. Any time the piece is on a square with a wine glass, the owner of that square drinks half of what’s left.

The game is played over an infinite amount of time,¹ after which the winner is whoever consumed the most expensive glass among all glasses of wine fully consumed.

Importantly, it is only the single most expensive glass which counts; all other drinking is irrelevant in determining the winner. And not a single drop of wine is allowed to remain for a glass to be considered consumed!

Abélard, having the slightly annoying tendency of always being critical of Éloïse’s suggestions, is a bit unsure if this game will work. He asks her to clarify what happens in the case one of them becomes stuck after the piece lands on a square they own from which it is not possible to make any more moves. She suggests that in such a case the player who is unable to move simply loses immediately. He also agrees that it will be possible to consume entire glasses of wine by drinking half the glass and then a quarter of the glass and then an eighth and so on across their infinite evening. In any case, it is for the better that they spread out the drinking of the wine like this since some of the wine was fairly expensive.

In the image above you can see that if the game piece were to start at node 0, neither Éloïse (green) nor Abélard (red) have an incentive to do anything other than cycle it around nodes 0, 1, 2, 0, 1, 2… as if Abélard moves to 3 from 1 he loses, and if Éloïse moves to 4 from 2 she loses. In this case there is only a single wine glass and Éloïse will consume it entirely after the infinite play and so will be able to win.²

This is a rather good drinking game, as the optimal strategy at any point does not depend on remembering any historical gameplay, and so is amenable to being slightly tipsy.

More interesting still, it is possible to play without drinking! It is completely deterministic and with complete information. Each possible initial game is either a win for Éloïse or Abélard, and so they can save themselves an infinite amount of time by simply looking at the setup, working out the winner and then leaving without ever having to bother playing at all. It is currently unknown if there is a way of doing this in polynomial time.³

This game may sound a little silly, however it provides a good way of understanding the meaning of alternating fixed points in temporal logic. The idea is to imagine Éloïse trying to convince Abélard of the truth of some formula while Abélard is trying to falsify her claim. In fact, my original inspiration for this article was Clemens Kupke’s talk on game semantics for the modal μ-calculus at SPLV.