agreg/public2012_D3 (OCaml).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Table des Matières\n",
    "* [1. Agrégation externe de mathématiques, texte d’exercice diffusé en 2012](#1.-Agrégation-externe-de-mathématiques,-texte-d’exercice-diffusé-en-2012)\n",
    "\t* [1.1 Épreuve de modélisation, option informatique](#1.1-Épreuve-de-modélisation,-option-informatique)\n",
    "\t* [1.2 *Proposition* d'implémentation, en [OCaml](https://ocaml.org/)](#1.2-*Proposition*-d'implémentation,-en-[OCaml]%28https://ocaml.org/%29)\n",
    "\t\t* [1.2.1 Pour [l'option informatique (D)](http://www.dit.ens-rennes.fr/agregation-option-d/programme-de-l-option-informatique-de-l-agregation-de-mathematiques-48358.kjsp) de l'[agrégation de mathématiques](http://agreg.org/) (en France).](#1.2.1-Pour-[l'option-informatique-%28D%29]%28http://www.dit.ens-rennes.fr/agregation-option-d/programme-de-l-option-informatique-de-l-agregation-de-mathematiques-48358.kjsp%29-de-l'[agrégation-de-mathématiques]%28http://agreg.org/%29-%28en-France%29.)\n",
    "\t* [1.3 Jeux de Nim](#1.3-Jeux-de-Nim)\n",
    "\t\t* [1.3.1 Représentation des configurations](#1.3.1-Représentation-des-configurations)\n",
    "\t\t* [1.3.2 Fonction de Sprague-Grundy pour le jeu de Nim](#1.3.2-Fonction-de-Sprague-Grundy-pour-le-jeu-de-Nim)\n",
    "\t\t* [1.3.3 Déterminer un coup à jouer selon une stratégie gagnante (s'il y en a une)](#1.3.3-Déterminer-un-coup-à-jouer-selon-une-stratégie-gagnante-%28s'il-y-en-a-une%29)\n",
    "\t\t\t* [1.3.3.1 Stratégie optimale](#1.3.3.1-Stratégie-optimale)\n",
    "\t\t* [1.3.4 Stratégie stupide](#1.3.4-Stratégie-stupide)\n",
    "\t* [1.4 Deux exemples, manuellement](#1.4-Deux-exemples,-manuellement)\n",
    "\t\t* [1.4.1 Premier exemple](#1.4.1-Premier-exemple)\n",
    "\t\t* [1.4.2 Second exemple](#1.4.2-Second-exemple)\n",
    "\t* [1.5 Un bonus : *simulation du jeu*](#1.5-Un-bonus-:-*simulation-du-jeu*)\n",
    "\t\t* [1.5.1 Simulation de plusieurs étapes](#1.5.1-Simulation-de-plusieurs-étapes)\n",
    "\t\t* [1.5.2 Exemple :](#1.5.2-Exemple-:)\n",
    "\t\t* [1.5.3 Configuration aléatoire](#1.5.3-Configuration-aléatoire)\n",
    "\t\t\t* [Le joueur *optimal* gagne souvent...](#Le-joueur-*optimal*-gagne-souvent...)\n",
    "\t\t\t* [Le joueur *stupide* peut quand-même gagner ?](#Le-joueur-*stupide*-peut-quand-même-gagner-?)\n",
    "\t* [1.5 Conclusion](#1.5-Conclusion)\n",
    "\t* [1.6 Attention](#1.6-Attention-:)\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 1. Agrégation externe de mathématiques, texte d’exercice diffusé en 2012"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.1 Épreuve de modélisation, option informatique"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> - Ce [notebook Jupyter](http://jupyter.org/), utilisant [OCaml](https://ocaml.org/) (via le [kernel IOcaml](https://github.com/andrewray/iocaml/#installation)), est une correction [non officielle](https://github.com/Naereen/notebooks/tree/master/agreg) d'un texte de modélisation pour l'option informatique de l'agrégation externe de mathématiques.\n",
    "> - Il s'agit du texte [public2012-D3](http://agreg.org/Textes/public2012-D3.pdf).\n",
    "> - Cette tentative de correction partielle a été rédigée par [Lilian Besson](http://perso.crans.org/besson/) ([sur GitHub ?](https://github.com/Naereen/), [sur Bitbucket ?](https://bitbucket.org/lbesson)), et [est open-source](https://github.com/Naereen/notebooks/blob/master/agreg/public2012_D3%20%28OCaml%29.ipynb).\n",
    "> - Une autre version, en [Python 3](https://docs.python.org/3/), [est disponible (aussi sur GitHub)](https://github.com/Naereen/notebooks/blob/master/agreg/public2012_D3.ipynb).\n",
    "\n",
    "> #### Feedbacks?\n",
    "> - Vous avez trouvé un bug ? → [Signalez-le moi svp !](https://github.com/Naereen/notebooks/issues/new), merci d'avance.\n",
    "> - Vous avez une question ? → [Posez la svp !](https://github.com/Naereen/ama.fr) [![Demandez moi n'importe quoi !](https://img.shields.io/badge/Demandez%20moi-n'%20importe%20quoi-1abc9c.svg)](https://GitHub.com/Naereen/ama.fr)\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.2 *Proposition* d'implémentation, en [OCaml](https://ocaml.org/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.2.1 Pour [l'option informatique (D)](http://www.dit.ens-rennes.fr/agregation-option-d/programme-de-l-option-informatique-de-l-agregation-de-mathematiques-48358.kjsp) de l'[agrégation de mathématiques](http://agreg.org/) (en France)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Attention** : ce document ne prétend pas être LA correction du texte, mais **un exemple de solution**.\n",
    "\n",
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Initialisation du [générateur de nombres aléatoires](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Random.html#VALinit) et d'une [fonction généralisée](https://ocaml.org/learn/tutorials/format.html) d'affichage."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val print : ('a, Format.formatter, unit) format -&gt; 'a = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 1,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Random.self_init ();;\n",
    "let print = Format.printf;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est un très bon réflexe d'utiliser `print = Format.printf` ainsi défini, elle permet d'afficher facilement du texte contenant des paramètres. Pour plus de détails, voir [la documentation de Printf.printf](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Printf.html) et [des explications sur `Format`](https://ocaml.org/learn/tutorials/format.html#Printingtostdoutusingprintf).\n",
    "\n",
    "Il suffit de retenir que `printf` s'utilise comme ça : "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 2,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print \"Chaine de caractere\\n\";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Chaine de caractere\n",
      "Chaine avec variables : il faut retenir %i, %f, %s et %c...\n",
      "\n",
      " - %i pour un entier : 1, \n",
      " - %f pour un flottant : 3.141500, \n",
      " - %s pour une string : OK?, \n",
      " - %c pour un caractère : c\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print \"Chaine avec variables : il faut retenir %%i, %%f, %%s et %%c...\\n\" ;;\n",
    "print \"\\n - %%i pour un entier : %i, \" 1 ;;\n",
    "print \"\\n - %%f pour un flottant : %f, \" 3.1415 ;;\n",
    "print \"\\n - %%s pour une string : %s, \" \"OK?\" ;;\n",
    "print \"\\n - %%c pour un caractère : %c\\n\" 'c' ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.3 Jeux de Nim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3.1 Représentation des configurations"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pas besoin d'un type de données trop complexe :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">type nim = int array\n",
       "</pre>"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type nim = int array;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On va d'abord écrire une fonction toute simple qui affiche une configuration, en mode texte."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val print_nim : int array -&gt; unit = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 5,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let print_nim =\n",
    "  Array.iteri (fun case total -> begin\n",
    "    print \"\\n%i: \" case;\n",
    "    for j = 1 to total do\n",
    "      print \"! \";\n",
    "    done;\n",
    "  end);;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut définir et afficher deux exemples de configuration d'un jeu de Nim, venant de la figure 1."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Configuration (a) de la Figure 1 :\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! ! ! ! "
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a : int array = [|1; 3; 5|]\n",
       "</pre>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let a = [| 1; 3; 5 |] ;;\n",
    "print \"\\n Configuration (a) de la Figure 1 :\";\n",
    "print_nim a;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      " Configuration (b) de la Figure 1 :\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! "
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val b : int array = [|1; 3; 2|]\n",
       "</pre>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let b = [| 1; 3; 2 |] ;;\n",
    "print \"\\n Configuration (b) de la Figure 1 :\";\n",
    "print_nim b;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3.2 Fonction de Sprague-Grundy pour le jeu de Nim"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Elle est donnée par le corollaire 1. en page 6/7 du texte.\n",
    "On a besoin du **xor** (*\"ou exclusif\"*, cf [cette page](https://fr.wikipedia.org/wiki/Fonction_OU_exclusif)) **bit à bit**, obtenu en OCaml avec l'opérateur [``lxor``](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Pervasives.html#VAL(lxor)) :\n",
    "\n",
    "$$ \\gamma(\\mathrm{Nim}(x_1, \\dots, x_k)) := \\bigoplus_{i=1}^{k} x_i = x_1 \\oplus \\dots \\oplus x_k. $$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Petit rappel sur cette fonction **xor** :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| Entrée      | |  Entrée  | Sortie  |\n",
    "| ----- |:--------:| ----- | ------: |\n",
    "| False | $\\oplus$ | False | = False |\n",
    "| False | $\\oplus$ | True  | = True  |\n",
    "| True  | $\\oplus$ | False | = True  |\n",
    "| True  | $\\oplus$ | True  | = False |"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut la définir avec l'opérateur infixe :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val somme_nim : int -&gt; int -&gt; int = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let somme_nim = ( lxor ) ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Ou bien plus simplement :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val somme_nim : int -&gt; int -&gt; int = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let somme_nim x y = x lxor y ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Quelques exemples, juste pour vérifier.\n",
    "\n",
    "- D'abord, les valeurs pour les deux entiers `0` et `1` :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 0\n",
       "</pre>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 1\n",
       "</pre>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 1\n",
       "</pre>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 0\n",
       "</pre>"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "somme_nim 0 0;; (** = 0 *)\n",
    "somme_nim 0 1;; (** = 1 *)\n",
    "somme_nim 1 0;; (** = 1 *)\n",
    "somme_nim 1 1;; (** = 0 *)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Ensuite, d'autres valeurs, juste pour tester :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 6\n",
       "</pre>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 12\n",
       "</pre>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 13\n",
       "</pre>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int = 14\n",
       "</pre>"
      ]
     },
     "execution_count": 39,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "somme_nim 3 5;;  (** 3 xor 5  =  011_2 xor 101_2  = 111_2  = 6  *)\n",
    "somme_nim 5 9;;  (** 5 xor 9  = 0101_2 xor 1001_2 = 1100_2 = 12 *)\n",
    "somme_nim 12 1;; (** 12 xor 1 = 1100_2 xor 0001_2 = 1101_2 = 13 *)\n",
    "somme_nim 12 2;; (** 12 xor 2 = 1100_2 xor 0010_2 = 1110_2 = 14 *)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "D'après le corollaire 1., il suffit d'appliquer un **xor** bit à bit à chaque valeur du tableau pour calculer $\\gamma$.\n",
    "\n",
    "En OCaml, on peut faire ça avec une boucle, une fonction récursive, ou plus concisement avec `Array.fold_left`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : ('a -&gt; 'b -&gt; 'a) -&gt; 'a -&gt; 'b array -&gt; 'a = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 12,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "Array.fold_left ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "*Rappel :* `fold_left` prend une fonction `f(x,y)` et `x0` calcule\n",
    "`f( ... f( f( x0, a[0] ), a[1] ), a[n-1] )`.\n",
    "Ici, pour `f = somme_nim`, il faut donner `x0 = 0` pour que le premier calcul `f(0, a[0]) = a[0]`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val gamma : int array -&gt; int = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 13,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let gamma = Array.fold_left somme_nim 0;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Gamma(a) = 7\n",
      "Gamma(b) = 0"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "print \"\\nGamma(a) = %i\" (gamma(a));;\n",
    "print \"\\nGamma(b) = %i\" (gamma(b));;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3.3 Déterminer un coup à jouer selon une stratégie gagnante (s'il y en a une)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On suit l'algorithme proposé par le texte, qui utilise la fonction $\\gamma$ sur la configuration pour savoir s'il y a une stratégie ou non (d'après la proposition 5.), et ensuite si elle existe on doit trouver un coup qui ammene $\\gamma$ à 0.\n",
    "\n",
    "On a d'abord besoin d'une exception pour signaler s'il n'y a pas de stratégie gagnante."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">exception Pas_de_Strat_Gagnante\n",
       "</pre>"
      ]
     },
     "execution_count": 15,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exception Pas_de_Strat_Gagnante;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### 1.3.3.1 Stratégie optimale\n",
    "L'algorithme va être assez naïf, depuis une configuration actuelle $c$ :\n",
    "- si $\\gamma(c)$ est $0$, on échoue (`Pas_de_Strat_Gagnante`),\n",
    "- sinon, on explore toutes les configurations $c'$ atteignables en un coup depuis $c$, et on choisis la première qui amène à $\\gamma(c') = 0$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val next : ?id:int -&gt; int array -&gt; int array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let next ?(id=0) config =\n",
    "  let g = gamma config in\n",
    "  (** La prop. 5 donne directement : si g(s_0) = 0 alors échec. *)\n",
    "  if g = 0 then raise Pas_de_Strat_Gagnante;\n",
    "  (** Sinon, on calcul les gamma des fils, et on pointe vers le fils avec un gamma nul. *)\n",
    "  print \"\\n\\nIl y a une stratégie gagnante :\\n\";\n",
    "  (** En pratique, on aurait pas besoin de calculer chaque fils,\n",
    "      comme on sait que g != 0, et on doit obtenir g' = 0,\n",
    "      on peut s'arreter au premier coup qui donne g' = 0.\n",
    "  *)\n",
    "  let config' = Array.copy config in\n",
    "  let colonne = ref 0 and\n",
    "      nb      = ref 1 in\n",
    "  (** Il suffit d'explorer toutes les configurations accessibles depuis l'état actuel : *)\n",
    "  for   j = 0 to (Array.length config') - 1 do\n",
    "    for i = 1 to config'.(j) do\n",
    "      config'.(j) <- config'.(j) - i;  (** On essaie d'appliquer ce coup. *)\n",
    "      if (gamma config') = 0 then begin\n",
    "          (** On a trouvé un coup gagnant, on le stocke. *)\n",
    "          colonne := j;\n",
    "          nb := i;\n",
    "      end;\n",
    "      config'.(j) <- config'.(j) + i;  (** On annule ce coup. *)\n",
    "    done;\n",
    "  done;\n",
    "  (**  On applique le coup retenu, dernier coup à donner gamma(c') = 0. *)\n",
    "  print \"\\nLe joueur courant (numéro %i) doit enlever %i allumette à la %i-ième rangée.\" id !nb !colonne;\n",
    "  config'.(!colonne) <- config.(!colonne) - !nb; (** On retire nb allumette sur cette colonne. *)\n",
    "  (* assert ((gamma config') = 0); (** Si on veut vérifier *)  *)\n",
    "  config'\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> *Note :* cette fonction utilise la notation `?(id=0)` dans sa définition pour définir un *argument optionnel avec valeur par défaut*.\n",
    "> La fonction `next` peut être appelée de deux façons :\n",
    ">\n",
    "> - `next a` : sans spécifier `id`, qui vaudra donc `0`,\n",
    "> - `next ~id:1 a` : en spécifiant `id=1`, qui vaut ici `1`.\n",
    ">\n",
    "> Cette astuce n'est pas requise, et c'est un peu de la \"frime\", inutile de la retenir et de se forcer à s'en servir. Néanmoins, ça peut être utile dans certaines situations."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "On peut tester cette fonction sur nos deux configuration a et b :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 3 allumette à la 2-ième rangée.\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! "
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "try\n",
    "  print_nim (next ~id:0 a);\n",
    "with _ -> print \"\\n\\nBlocage durant la simulation 1 (sur a).\";;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 42,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "\n",
      "Blocage durant la simulation 2 (sur b)."
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 42,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "try\n",
    "  print_nim (next ~id:1 b);\n",
    "with _ -> print \"\\n\\nBlocage durant la simulation 2 (sur b).\";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.3.4. Une stratégie \"stupide\" : complètement aléatoire"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On a d'abord besoin de deux fonctions utilitaires :\n",
    " - `array_filter`, pour filtrer un tableau (comme [`List.filter`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/List.html#VALfilter) mais pour un [`array`](http://caml.inria.fr/pub/docs/manual-ocaml/libref/Array.html)). On fait ça simplement en transformant le tableau en liste, on filtre la liste, puis la liste en tableau. Attention, la taille du tableau n'est *pas* préservée. \n",
    " - et `choose` pour choisir un élément aléatoire (uniforme) dans un tableau. En Python, on aurait [`random.choice`](https://docs.python.org/3/library/random.html#random.choice). On fait ça simplement en tirant un entier `i` aléatoire uniformément parmi `0, ..., n-1` pour `n = Array.length a`, puis en renvoyant `a.(i)`.\n",
    " \n",
    "> (Et oui, la libraire standard de OCaml est [assez limitée](http://sucre.syntaxique.fr/doku.php?id=ocaml#bibliotheque_standard))..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val array_filter : ('a -&gt; bool) -&gt; 'a array -&gt; 'a array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val choose : 'a array -&gt; 'a = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let array_filter pred a =\n",
    "  Array.of_list (List.filter pred (Array.to_list a));;\n",
    "\n",
    "let choose a\n",
    "  = a.(Random.int (Array.length a));;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Dans le but de comparer cette fonction `next`, qui implémente une stratégie optimale, on implémente aussi une stratégie complétement aléatoire (\"Dummy player\").\n",
    "\n",
    "La stratégie aléatoire fonctionne en trois étapes :\n",
    "1. trouve les rangées qui ont encore des allumettes (en calculant leurs indices, via `array_filter`, dans le tableau `indices`),\n",
    "2. choisi une rangée aléatoirement `i` (uniformément),\n",
    "3. enlève un nombre aléatoire (uniforme) d'allumette entre `1` et `xi`, pour `xi` le nombre d'allumette dans la rangée `i` (i.e., `xi = config.(i)`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val random : ?id:int -&gt; int array -&gt; int array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "(** Un adversaire stupide qui joue aléatoirement. *)\n",
    "let random ?(id=1) config =\n",
    "  print \"\\nLe joueur courant (numéro %i) joue aléatoirement.\\n\" id;\n",
    "  let indices = array_filter ( fun i -> (config.(i) > 0) ) (Array.init (Array.length config) (fun i -> i)) in\n",
    "  let i = choose indices in\n",
    "  print \"Le joueur (%i) choisi de regarder la %i-ième rangée.\\n\" id i;\n",
    "  let nbAEnlever = 1 + Random.int config.(i) in\n",
    "  print \"Le joueur (%i) choisi d'enlever %i allumettes parmi les %i disponibles.\\n\" id nbAEnlever config.(i);\n",
    "  let config' = Array.copy config in\n",
    "  config'.(i) <- config.(i) - nbAEnlever;\n",
    "  config';\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.4 Deux exemples, manuellement"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4.1 Premier exemple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut ainsi faire un exemple de début de partie entre deux joueurs \"stupides\" :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! ! ! ! \n",
      "Le joueur courant (numéro 0) joue aléatoirement.\n",
      "Le joueur (0) choisi de regarder la 2-ième rangée.\n",
      "Le joueur (0) choisi d'enlever 1 allumettes parmi les 5 disponibles.\n",
      "\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! ! ! \n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 2-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 2 allumettes parmi les 4 disponibles.\n",
      "\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! \n",
      "Le joueur courant (numéro 0) joue aléatoirement.\n",
      "Le joueur (0) choisi de regarder la 0-ième rangée.\n",
      "Le joueur (0) choisi d'enlever 1 allumettes parmi les 1 disponibles.\n",
      "\n",
      "0: \n",
      "1: ! ! ! \n",
      "2: ! ! "
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a0 : int array = [|1; 3; 5|]\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a1 : int array = [|1; 3; 4|]\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a2 : int array = [|1; 3; 2|]\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a3 : int array = [|0; 3; 2|]\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let a0 = a ;; (* Debut du jeu *)\n",
    "print_nim a0 ;;\n",
    "let a1 = random ~id:0 a0 ;;\n",
    "print_nim a1 ;;\n",
    "let a2 = random ~id:1 a1 ;;\n",
    "print_nim a2 ;;\n",
    "let a3 = random ~id:0 a2 ;;\n",
    "print_nim a3 ;;\n",
    "(* ... etc *)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.4.2 Second exemple"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut aussi faire le même exemple de début de partie entre un joueur \"optimal\" et un joueur \"stupide\" :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "0: ! ! \n",
      "1: ! ! ! \n",
      "2: ! ! \n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 1 allumette à la 2-ième rangée.\n",
      "0: ! ! \n",
      "1: ! ! ! \n",
      "2: ! \n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 0-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 1 allumettes parmi les 2 disponibles.\n",
      "\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! \n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 3 allumette à la 1-ième rangée.\n",
      "0: ! \n",
      "1: \n",
      "2: ! "
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val c : int array = [|2; 3; 2|]\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a0 : int array = [|2; 3; 2|]\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a1 : int array = [|2; 3; 1|]\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a2 : int array = [|1; 3; 1|]\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val a3 : int array = [|1; 0; 1|]\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let c = [| 2; 3; 2 |] ;;\n",
    "let a0 = c ;; (* Debut du jeu *)\n",
    "print_nim a0 ;;\n",
    "let a1 = next ~id:0 a0 ;;\n",
    "print_nim a1 ;;\n",
    "let a2 = random ~id:1 a1 ;;\n",
    "print_nim a2 ;;\n",
    "let a3 = next ~id:0 a2 ;;\n",
    "print_nim a3 ;;\n",
    "(* ... etc *)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.5 Un bonus : *simulation du jeu*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Maintenant qu'on dispose d'un joueur stupide et d'un joueur optimal, on peut rapidement coder une petite fonction qui les fera s'affronter (même si c'est un peu cruel envers le pauvre joueur \"stupide\" purement aléatoire !)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">exception Perdu of int\n",
       "</pre>"
      ]
     },
     "execution_count": 23,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "exception Perdu of int;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5.1 Simulation de plusieurs étapes"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "La fonction ``kpas`` va jouer la partie, en partant de la configuration donnée, en commençant par le joueur ``id`` et pour un certain nombre de coups joués (``nbPas``).\n",
    "Si on ne donne pas ce nombre de coups, le nombre total d'allumette est utilisé (sachant qu'une partie se termine souvent par une exception ``Pas_de_Strat_Gagnante`` lorsque le joueur optimal ne peut plus gagner)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val kpas : int array -&gt; int -&gt; int -&gt; int array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 45,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let kpas config id nbPas =\n",
    "  let id = ref id in\n",
    "  let config' = ref (Array.copy config) in\n",
    "  for i = 1 to nbPas do\n",
    "    print \"\\nTour numéro %i.\" i;\n",
    "    print_nim !config';\n",
    "    print \"\\n\";\n",
    "    if (Array.fold_left ( + ) 0 !config') = 0 then raise (Perdu !id);\n",
    "    begin\n",
    "      if !id = 0 then (** Le joueur 0 joue bien. *)\n",
    "        config' := next   ~id:(!id) !config'\n",
    "      else (** Mais le joueur 1 joue aléatoirement. *)\n",
    "        config' := random ~id:(!id) !config'\n",
    "    end;\n",
    "    id := 1 - !id; (** Juste pour alterner entre 0 et 1 : 0 -> 1, 1 -> 0 *)\n",
    "  done;\n",
    "  !config';\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut finalement implementer une jolie fonction qui simule en partant du joueur ``0`` (comme le vrai jeu de Nim) et interprète l'exception renvoyée pour afficher l'issue du jeu :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val simulation : int array -&gt; int array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val nim : int array -&gt; int option = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 46,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let simulation config =\n",
    "  (** On compte le nombre total d'allumettes. *)\n",
    "  let n = Array.fold_left (fun i j -> i + j + 1) 0 config in\n",
    "  (** Puis on lance le joueur 0 avec au plus [n] pas. *)\n",
    "  kpas config 0 n;\n",
    ";;\n",
    "\n",
    "(** Dernière fonction, [nim], qui lance [simulation] et rattrape les exceptions. *)\n",
    "let nim a =\n",
    "  let resultat =\n",
    "    (* try ignore (simulation a) with *)\n",
    "    try ignore(simulation a); None with\n",
    "      | Perdu i -> (Some i)\n",
    "      | Pas_de_Strat_Gagnante -> None\n",
    "  in\n",
    "  begin\n",
    "    match resultat with\n",
    "    | None -> print \"Blocage à cause de la stratégie optimisée.\\n\\n\"\n",
    "    | Some i -> print \"\\n ==> Le joueur %i a perdu !\\n\\n\" i\n",
    "  end;\n",
    "  resultat\n",
    ";;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5.2 Exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Tour numéro 1.\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! ! ! ! \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 3 allumette à la 2-ième rangée.\n",
      "Tour numéro 2.\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! \n",
      "\n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 2-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.\n",
      "\n",
      "Tour numéro 3.\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 2 allumette à la 1-ième rangée.\n",
      "Tour numéro 4.\n",
      "0: ! \n",
      "1: ! \n",
      "2: \n",
      "\n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 1-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 1 allumettes parmi les 1 disponibles.\n",
      "\n",
      "Tour numéro 5.\n",
      "0: ! \n",
      "1: \n",
      "2: \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 1 allumette à la 0-ième rangée.\n",
      "Tour numéro 6.\n",
      "0: \n",
      "1: \n",
      "2: \n",
      "\n",
      " ==> Le joueur 1 a perdu !\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int option = Some 1\n",
       "</pre>"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nim a;;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Tour numéro 1.\n",
      "0: ! \n",
      "1: ! ! ! \n",
      "2: ! ! \n",
      "Blocage à cause de la stratégie optimisée.\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int option = None\n",
       "</pre>"
      ]
     },
     "execution_count": 48,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nim b;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "> Pas très utile jusqu'ici..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 49,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "Tour numéro 1.\n",
      "0: ! ! \n",
      "1: ! ! ! \n",
      "2: ! ! \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 1 allumette à la 2-ième rangée.\n",
      "Tour numéro 2.\n",
      "0: ! ! \n",
      "1: ! ! ! \n",
      "2: ! \n",
      "\n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 0-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.\n",
      "\n",
      "Tour numéro 3.\n",
      "0: \n",
      "1: ! ! ! \n",
      "2: ! \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 2 allumette à la 1-ième rangée.\n",
      "Tour numéro 4.\n",
      "0: \n",
      "1: ! \n",
      "2: ! \n",
      "\n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 1-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 1 allumettes parmi les 1 disponibles.\n",
      "\n",
      "Tour numéro 5.\n",
      "0: \n",
      "1: \n",
      "2: ! \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 1 allumette à la 2-ième rangée.\n",
      "Tour numéro 6.\n",
      "0: \n",
      "1: \n",
      "2: \n",
      "\n",
      " ==> Le joueur 1 a perdu !\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int option = Some 1\n",
       "</pre>"
      ]
     },
     "execution_count": 49,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "nim c;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 1.5.3 Générer des configurations aléatoires"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut écrire une fonction qui génére une configuration aléatoire, et ensuite lancer notre simulation ``nim()`` dessus, pour voir ce que ça donne sur une configuration plus grande.\n",
    "\n",
    "La fonction `randomstart(k, p)` va générer une configuration aléatoire :\n",
    "\n",
    "- avec un nombre de lignes uniforme dans `{1, ..., k}`,\n",
    "- et un nombre d'allumettes uniforme dans `{1, ..., p}` pour chaque ligne."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val randomstart : int -&gt; int -&gt; unit -&gt; int array = &lt;fun&gt;\n",
       "</pre>"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let randomstart k p () = Array.init (1 + Random.int k) (fun i -> 1 + Random.int p);;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Par exemple :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 30,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "\n",
      "0: ! ! ! ! ! \n",
      "1: ! ! \n",
      "2: ! ! ! ! ! ! \n",
      "3: ! ! "
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val c : int array = [|5; 2; 6; 2|]\n",
       "</pre>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 30,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let c = randomstart 5 8 ();;\n",
    "print_nim c;; "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Le joueur *optimal* (d'indice `0`) gagne toujours"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Configuration random c :\n",
      "0: ! ! \n",
      "1: ! ! ! ! ! ! \n",
      "Tour numéro 1.\n",
      "0: ! ! \n",
      "1: ! ! ! ! ! ! \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 4 allumette à la 1-ième rangée.\n",
      "Tour numéro 2.\n",
      "0: ! ! \n",
      "1: ! ! \n",
      "\n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 0-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.\n",
      "\n",
      "Tour numéro 3.\n",
      "0: \n",
      "1: ! ! \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 2 allumette à la 1-ième rangée.\n",
      "Tour numéro 4.\n",
      "0: \n",
      "1: \n",
      "\n",
      " ==> Le joueur 1 a perdu !\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">val c : int array = [|2; 6|]\n",
       "</pre>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int option = Some 1\n",
       "</pre>"
      ]
     },
     "execution_count": 31,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "let c = randomstart 5 8 () ;;\n",
    "print \"Configuration random c :\" ;;\n",
    "print_nim c;;\n",
    "nim c;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Le joueur *stupide* peut-il quand-même gagner ?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Configuration random c :\n",
      "0: ! ! \n",
      "1: ! ! ! ! ! ! \n",
      "Tour numéro 1.\n",
      "0: ! ! \n",
      "1: ! ! ! ! ! ! \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 4 allumette à la 1-ième rangée.\n",
      "Tour numéro 2.\n",
      "0: ! ! \n",
      "1: ! ! \n",
      "\n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 1-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 2 allumettes parmi les 2 disponibles.\n",
      "\n",
      "Tour numéro 3.\n",
      "0: ! ! \n",
      "1: \n",
      "\n",
      "\n",
      "Il y a une stratégie gagnante :\n",
      "\n",
      "Le joueur courant (numéro 0) doit enlever 1 allumette à la 0-ième rangée.\n",
      "Tour numéro 4.\n",
      "0: ! \n",
      "1: \n",
      "\n",
      "Le joueur courant (numéro 1) joue aléatoirement.\n",
      "Le joueur (1) choisi de regarder la 0-ième rangée.\n",
      "Le joueur (1) choisi d'enlever 1 allumettes parmi les 1 disponibles.\n",
      "\n",
      "Tour numéro 5.\n",
      "0: \n",
      "1: \n",
      "\n",
      " ==> Le joueur 0 a perdu !\n",
      "\n"
     ]
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : bool = false\n",
       "</pre>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : unit = ()\n",
       "</pre>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    },
    {
     "data": {
      "text/html": [
       "<pre style=\"color:slategray;max-height:100px;overflow:hidden\" \n",
       "onclick=\"\n",
       "if (this.style.maxHeight === 'none') \n",
       "    this.style.maxHeight = '100px';\n",
       "else\n",
       "    this.style.maxHeight = 'none'; \n",
       "\">- : int option = Some 0\n",
       "</pre>"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "c = randomstart 5 8 () ;;\n",
    "print \"Configuration random c :\" ;;\n",
    "print_nim c ;;\n",
    "nim c ;;"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est effectivement possible que le joueur `0` (celui qui commence) perde, même en suivant sa stratégie gagnante.\n",
    "Si le joueur aléatoire `1` a de la chance..."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.5 Conclusion"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "C'est tout ce que j'avais eu le temps d'implémenter durant les 4h de préparation (c'est un des textes que j'avais préparé en juin 2014, dans les \"vraies\" conditions en oraux blanc, à l'ENS Cachan, et le code initial était en OCaml mais je n'ai rien changé à part l'écriture du notebook Jupyter).\n",
    "\n",
    "Quelques remarques :\n",
    "\n",
    "- durant l'épreuve de modélisation, vous êtes libres de faire ce que vous voulez, la seule partie requise est dans le paragraphe **Exercice de programmation** (ici, il s'agissait d'implémenter une fonction similaire à ``optimal()`` (cf. plus haut).\n",
    "- les quelques développements supplémentaires traites ci-dessus (stratégie stupide, configuration aléatoire, simulation de jeu), ne sont qu'une suggestion de ce qui pouvait être fait sur ce texte,\n",
    "- d'autres suggestions sont possibles, si vous avez des idées, [envoyez-moi vos notebooks !](https://github.com/Naereen/notebooks/pulls).\n",
    "\n",
    "> *Edit :* j'avais une erreur dans mon calcul de `next`, corrigée le 11/01/17."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 1.6 Attention :"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Les 35/40 minutes de passage au tableau ne doivent PAS être uniquement consacrée à la présentation de vos expériences sur l'ordinateur !\n",
    "\n",
    "Il faut aussi :\n",
    "\n",
    "- faire une introduction générale (citer des mots clés),\n",
    "- présenter le plan de votre présentation,\n",
    "- introduire les notations, les objectifs et les résultats donnés par le texte,\n",
    "- prouver ou exposer des développements **theoriques** personnels (à choisir parmi la liste proposée, mais pas seulement),\n",
    "- etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "----\n",
    "\n",
    "> *C'est tout pour aujourd'hui les amis !*\n",
    "> [Allez voir d'autres notebooks](https://github.com/Naereen/notebooks/tree/master/agreg) si vous voulez."
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "OCaml",
   "language": "ocaml",
   "name": "iocaml-kernel"
  },
  "language_info": {
   "name": "ocaml",
   "version": "4.1.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}