{ "cells": [ { "cell_type": "markdown", "id": "dac6f272-5c28-419c-8e30-672d594a1023", "metadata": {}, "source": [ "#
Practical Session 1 : Impartial games - Sprague-Grundy Theorem" ] }, { "cell_type": "markdown", "id": "09c55c4b-cc0f-4452-9a8b-23a3543fadc7", "metadata": {}, "source": [ "In this practical session, we will apply the main concepts introduced during the first lecture:\n", "\n", "- P-positions and N-positions;\n", "- subtraction games;\n", "- the XOR strategy for Nim;\n", "- optimal moves in combinatorial games;\n", "- Sprague-Grundy functions;\n", "- recursive computation of Grundy values.\n" ] }, { "cell_type": "markdown", "id": "5c670bb8-2f0a-4425-ac69-5574ff29181f", "metadata": {}, "source": [ "## Exercise 1 — Subtraction Game 1\n", "\n", "We consider a subtraction game. A position consists of a pile containing \\(n\\) tokens. At each turn, a player can remove a number of \n", "tokens belonging to a fixed set $S$. The player who removes the last token wins." ] }, { "cell_type": "markdown", "id": "51110700-389d-456c-b587-1e2620514809", "metadata": {}, "source": [ "### Question 1. \n", "Consider the initial position:\n", "\n", "
\n", "$$ n=31 $$\n", "
\n", "with:\n", "\\[\n", "S=\\{1,2,3,4,5,6\\}\n", "\\]\n", "\n", "Determine whether the first player has a winning strategy. Explain your reasoning by identifying the losing positions (P-positions)." ] }, { "cell_type": "markdown", "id": "15a9aa44-4634-47ce-983a-df18a75af316", "metadata": {}, "source": [ "### Question 2.\n", "We now want to automate the previous reasoning. Write a Python function that determines whether a position is:\n", "- a **P-position** (previous player wins, losing position);\n", "- an **N-position** (next player wins, winning position).\n", "\n", "The function should work for any:\n", "- number of tokens \\(n\\);\n", "- subtraction set \\(S\\)." ] }, { "cell_type": "code", "execution_count": 3, "id": "7c44f68c-5f73-461d-857e-5f23e82b7e79", "metadata": {}, "outputs": [], "source": [ "def classify_position(n, S):\n", " # returns \"P\" or \"S\"\n", " pass" ] }, { "cell_type": "markdown", "id": "a7ce8eea-4dbe-4bef-9674-afaf310b8138", "metadata": {}, "source": [ "## Exercise 2 — Nim: Finding Winning Strategies\n", "The game of Nim is one of the most famous examples of impartial combinatorial games.\n", "A position consists of several piles of tokens. At each turn, a player chooses one pile and removes any positive number\n", "of tokens from that pile. The player who removes the last token wins. \n", "\n", "For a position:\n", "$$ (a_1,a_2,\\dots,a_k) $$\n", "\n", "the Sprague-Grundy theorem tells us that the Grundy value is:\n", "$$ g(a_1,a_2,\\dots,a_k)\n", "=\n", "a_1\\oplus a_2\\oplus\\dots\\oplus a_k $$\n", "\n", "where $\\oplus$ denotes the bitwise XOR operation. The position is:\n", "\n", "- a **P-position** (losing position) if $g(a_1,a_2,\\dots,a_k)=0.$\n", "\n", "\n", "- an **N-position** (winning position) if $g(a_1,a_2,\\dots,a_k)\\neq0.$\n", "\n", "The goal of this exercise is to determine winning positions and to implement the optimal strategy for Nim." ] }, { "cell_type": "markdown", "id": "6821139a-b6fe-42e7-b5f4-1480e017d2c9", "metadata": {}, "source": [ "### Question 1 — Determine whether positions are winning or losing\n", "\n", "Consider the following Nim positions:\n", "\n", "$$ A = (11,7,5) $$\n", "\n", "$$ B = (27,18,4) $$\n", "\n", "For each position:\n", "1. Compute the XOR value of the sizes of heaps. \n", "2. Determine whether the position is a P-position or an N-position." ] }, { "cell_type": "markdown", "id": "b429ada3-b861-43c3-990f-8a3ff539b849", "metadata": {}, "source": [ "### Question 2 — Implement a Nim classifier\n", "Write a Python function that determines whether a Nim position is winning or losing.\n", "The function should work for any number of piles. Check your results of the previous question.\n", "\n", "**Remainder :** The bitwise XOR operation in Python is ^." ] }, { "cell_type": "code", "execution_count": 7, "id": "7a009c87-1804-45a9-9026-3028ac936bf9", "metadata": {}, "outputs": [], "source": [ "def nim_value(heaps):\n", " result = 0\n", " for h in heaps:\n", " result ^= h\n", " return result" ] }, { "cell_type": "markdown", "id": "acb67c40-e101-4424-8437-25280ab90eb5", "metadata": {}, "source": [ "### Question 3 — Find the optimal move by hand\n", "\n", "Consider again the Nim position:\n", "$$ (27,18,4) $$\n", "\n", "The position is winning because $27\\oplus18\\oplus4 \\neq0$. The objective of the optimal strategy is to make the XOR value equal to zero after your move:\n", "$$\n", "a_1\\oplus a_2\\oplus a_3=0\n", "$$\n", "\n", "Find the winning move manually. Write down the binary decomposition of the sizes of the heaps, and then determine :\n", "1. Which pile should be modified?\n", "2. How should it be modified to make the XOR equal to 0.\n", "3. What is the resulting position?" ] }, { "cell_type": "markdown", "id": "c8942f6f-4bfa-4197-a195-a4d9fcf3b71a", "metadata": {}, "source": [ "### Question 4 — Implement the optimal Nim move\n", "\n", "We now want to automate the strategy discovered in the previous question. Write a Python function that finds an optimal move in Nim.\n", "\n", "The function should:\n", "- compute the XOR value of the current position;\n", "- determine whether a winning move exists. If not, returns None.\n", "- find the pile that should be modified;\n", "- return the new state of the game, once again as a list of integers." ] }, { "cell_type": "code", "execution_count": null, "id": "6a709227-896f-4f29-9e5c-72ebf746cb69", "metadata": {}, "outputs": [], "source": [ "def nim_best_move(heaps):\n", " #heaps is a list of integer\n", " pass" ] }, { "cell_type": "markdown", "id": "01d935ed-625e-4ad4-aebc-5ec9e1207da2", "metadata": {}, "source": [ "### Question 5 - Beat your friends !\n", "You can now ask one of your friends to play a game of Nim against you. Make sur to bet a lot of money on it ! You can thank me with zombies later on :-)" ] }, { "cell_type": "markdown", "id": "bdc18059-a46c-486a-b96d-baf860f9fbca", "metadata": {}, "source": [ "\n", "\n", "## Exercise 3 — Kayles I: Computing Grundy Values by Hand\n", "In the previous exercises, we studied Nim, where the Grundy value is directly given by the XOR of the pile sizes.\n", "The goal of this exercise is to compute Grundy values manually and understand how the Sprague-Grundy theory applies to games that are not directly Nim.\n", "\n", "We now consider a more general impartial game: **Kayles**. Kayles is played on a row of pins. We denote by $K_n$ a position containing \\(n\\) consecutive pins.\n", "At each turn, a player can:\n", "\n", "- remove one pin;\n", "- remove two adjacent pins.\n", "\n", "The player who removes the last remaining pin wins.\n", "\n" ] }, { "cell_type": "markdown", "id": "ccb53757-5061-4345-9b9b-cd528b600928", "metadata": {}, "source": [ "### Question 1\n", "Compute the values of the Grundy functions for the positions $K_2$, $K_3$, $K_4$ and $K_5$. For each case, you might answer the following questions :\n", "1. Enumerate all possible moves.\n", "2. Compute the Grundy values of the resulting positions.\n", "3. Apply the mex rule to determine the correct value." ] }, { "cell_type": "markdown", "id": "f30eb4ae-0a5c-431f-b87d-532398b136e3", "metadata": {}, "source": [ "## Exercise 4 — Kayles II: Computing Grundy Values Automatically\n", "\n", "In the previous exercise, we computed manually the Grundy values of the first Kayles positions $\n", "g(K_1), g(K_2), g(K_3), g(K_4). $\n", "\n", "We now want to automate this computation. **The goal is to write a Python function that computes $g(K_n)$ for any number of pins \\(n\\).**\n", "\n", "### Question 1 — Generate all possible moves\n", "\n", "Write a function that generates all possible moves from a Kayles position $K_n$. \n", "A move can:\n", "- remove one pin;\n", "- remove two adjacent pins.\n", "\n", "A move may split the game into two independent sub-games. For example, in $K_5$ if you remove the middle pin you then obtain a sum $K_2+K_2$.\n", "The function takes as a parameter the integer $n$, and should return a list of all the possible subgame. A subgame can itself be a list if the move splits the game into two independent segments." ] }, { "cell_type": "code", "execution_count": 14, "id": "9e1a9f3a-6e6d-4edf-9680-ef8631754b90", "metadata": {}, "outputs": [], "source": [ "def generate_moves(n):\n", " pass" ] }, { "cell_type": "markdown", "id": "9a0da75c-4a15-4a26-a439-ac37629fc9f3", "metadata": {}, "source": [ "### Question 2 — Implement the mex function\n", "Write a Python function that returns the mex of a set of values." ] }, { "cell_type": "code", "execution_count": 12, "id": "c692405d-27aa-4bea-a4c2-ad9bc3ac110d", "metadata": {}, "outputs": [], "source": [ "def mex(values):\n", " pass" ] }, { "cell_type": "markdown", "id": "d433ff3a-4214-4987-bd4e-c7403f977833", "metadata": {}, "source": [ "### Question 3 — Implement the Grundy function\n", "We now want to compute automatically the Grundy value of a Kayles position $\n", "K_n$\n", "\n", "Write a recursive function that calculates the value of $g(K_n)$ for any integer $n$. The function should:\n", "1. generate all possible moves from $K_n$ using the previous function *generate_moves*;\n", "2. compute using recursion the grundy value of every resulting position. Be careful ! When a move splits the game into two independant parts,\n", "combine the two Grundy values using the XOR operation;\n", "3. store all reachable Grundy values in a list or a set;\n", "4. returns the mex of all these values.\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "f3a6f8b9-c5e3-4c6b-85b5-308bce53fbae", "metadata": {}, "outputs": [], "source": [ "def grundy(n):\n", " pass" ] }, { "cell_type": "markdown", "id": "bc7a9f94-a4e8-48d5-816b-f53991e01eed", "metadata": {}, "source": [ "You can now print the first 100 values of the Grundy function for the game of Kayles ! But the recursion of the step 2 above might be very heavy and take a lot of time...\n", "You should improve your function using a dynamic programming trick called **memoisation** ! If you are not familiar with it, the idea is to store the values that have already been computed in an apropriate data\n", "structure (eg a dictionary in Python) and check before computing anything if the value is already stored in the dictionary." ] }, { "cell_type": "code", "execution_count": 18, "id": "f4db870f-0349-4dbd-af1c-833ecf03c5c1", "metadata": {}, "outputs": [], "source": [ "def grundy_memo(n):\n", " pass" ] }, { "cell_type": "markdown", "id": "f5f01c6e-feff-435c-b9f3-24ef3820df1a", "metadata": {}, "source": [ "### Question 4 - Compute the best move\n", "\n", "You're playing a Kayle's game with $13$ pins. Of the 13 bowling pins in the row, the second has been knocked down. You are in the following situation:\n", "\\[ 1011111111111 \\] \n", "Prove that this is an N-position. You may use the previous function to compute the Grundy values you need.\n", "Then, find a winning move~: which pin(s) should be knocked down ? \n" ] }, { "cell_type": "code", "execution_count": null, "id": "a1fbc698-61ba-4ee2-aa65-649d90af25d3", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "SageMath 9.5", "language": "sage", "name": "sagemath" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.10.12" } }, "nbformat": 4, "nbformat_minor": 5 }