Mia (Mäxchen) Nash Equilibrium Solver

This project is a Nash Equilibrium solver for the dice game Mia (also known as Mäxchen, Meyer, or 21).

While Mia is traditionally played in a circle with many people, this project specifically solves the 2-player version modeled as a zero-sum game.

For more information on the game, see the Wikipedia page.

The Game: Rules & Mechanics

Mia is a bluffing game played with two dice under a cup. It is similar in spirit to games like Liar's Dice, though in Liar's Dice players usually have their own hidden dice; in Mia, a single set of dice is passed between players.

Dice Values & Hierarchy

Dice are not summed. The higher die is the "tens" and the lower is the "ones":

1. 21 (Mia): The highest possible roll.
2. Doubles: 66, 55, 44, 33, 22, 11 (descending).
3. High Rolls: 65, 64... down to 31 (the lowest possible roll).

How to Play

1. Player A rolls secretly and makes a claim (e.g., "52").
2. Player B must decide:
   • Call: Reveal the dice. If the roll is lower than the claim, A loses 1 point. If it is equal or higher, B loses 1 point.
   • Trust: Accept the claim. B then rolls and must make a higher claim than A. This cycle of higher claims continues until one player decides to Call.

The "Mia" (21) Rule

Because 21 is the highest possible roll, it cannot be exceeded. If Player A claims "21", Player B has a special choice:

• Give up: B accepts the loss immediately and loses 1 point.
• Call: B reveals the dice. If it is a 21, B loses 2 points. If it is anything else, A loses 1 point.

---

The Mathematical Model

This solver treats the 2-player game as a zero-sum game. The goal is to maximize the point spread between you and your opponent.

In our model, the utilities are:

• +1 / -1: Standard outcome for lying or calling correctly.
• +2 / -2: The outcome for a failed "Mia" claim.

This solver calculates the exact probabilities for bluffing and calling to ensure a Nash Equilibrium—meaning a strategy that cannot be exploited by the opponent.

---

Module Overview

The project consists of four main modules:

1. mia.py (Core Logic & State):

   • Defines the State object holding the Game Domain, Probabilities (P_d), and Strategy Tables (P_{n|nd} and P_{c|nn}).
   • Contains utility functions (u_{ndn}, u_{unt}, u_{unnc}) for calculating expected payoffs using exact rational arithmetic.

2. solve.py (The Solver):

   • Implements a greedy algorithm to find the Nash Equilibrium.
   • It iterates through the constraint layers from the highest possible claim down to the start of the game.

3. verify.py (The Verifier):

   • Mathematically verifies that the current strategy constitutes a Nash Equilibrium.
   • Ensures no player can increase their payoff by changing their strategy.

4. shell.py (Command-Line Interface):

   • A cmd-based shell for interacting with the solver.
   • Includes persistent command history (saved in ~/.mia_shell_history).

---

How to Use

1. Starting the Shell

python3 shell.py

2. Loading a Game

• load game mia: Loads the standard Mia dice values and probabilities.
• load game eqal 20: Loads a custom domain of 20 values with equal probabilities.
• load file save.json: Loads a previously saved strategy.

3. Solving and Verifying

• solve: Calculates the optimal Nash Equilibrium strategies.
• verify: Confirms the strategy is mathematically consistent.

4. Inspecting Strategies

• get game: View the dice values and their probabilities.
• get pc_nn: Displays the table of "Call" probabilities.
• get pn_nd <ni>: Displays the table of claims for every dice roll, given a previous claim ni. (Use x0 for the very first turn of a round).

5. Simulating Actions

• action n <ni> <dk>: "If the previous claim was ni and I rolled dk, what should I claim?"
• action c <ni> <nj>: "If I previously claimed ni and my opponent claimed nj, should I call or trust?"

6. Persistence

• store file strategy.json: Save the current state to a JSON file.
• exit: Exit the shell (history is saved automatically).

---

Performance

All probabilities and utilities get stored as python fractions. This ensures exact solutions but can make the program take much longer for large instances than the big-O of operations in the algorithm would suggest. The solver runs in O(n²) because it only changes the few probabilities that are not equal to zero in the final solution and the algorithm is designed to find a solution (among the infinitely many) that has a very sparse probability distribution. The verifyer in contrast checks for every single action probability whether it is rational and therefore runs in O(n³).