- Ce notebook Jupyter, utilisant OCaml (via le kernel IOcaml), est une correction non officielle d'un texte de modélisation pour l'option informatique de l'agrégation externe de mathématiques.
- Il s'agit du texte public2012-D3.
- Cette tentative de correction partielle a été rédigée par Lilian Besson (sur GitHub ?, sur Bitbucket ?), et est open-source.
- Une autre version, en Python 3, est disponible (aussi sur GitHub).
Feedbacks?
- Vous avez trouvé un bug ? → Signalez-le moi svp !, merci d'avance.
- Vous avez une question ? → Posez la svp !
Attention : ce document ne prétend pas être LA correction du texte, mais un exemple de solution.
Initialisation du générateur de nombres aléatoires et d'une fonction généralisée d'affichage.
In [1]:
Random.self_init ();;
let print = Format.printf;;
Out[1]:
Out[1]:
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 et des explications sur Format.
Il suffit de retenir que printf s'utilise comme ça :
In [2]:
print "Chaine de caractere\n";;
Out[2]:
In [3]:
print "Chaine avec variables : il faut retenir %%i, %%f, %%s et %%c...\n" ;;
print "\n - %%i pour un entier : %i, " 1 ;;
print "\n - %%f pour un flottant : %f, " 3.1415 ;;
print "\n - %%s pour une string : %s, " "OK?" ;;
print "\n - %%c pour un caractère : %c\n" 'c' ;;
Out[3]:
Out[3]:
Out[3]:
Out[3]:
Out[3]:
Pas besoin d'un type de données trop complexe :
In [4]:
type nim = int array;;
Out[4]:
On va d'abord écrire une fonction toute simple qui affiche une configuration, en mode texte.
In [5]:
let print_nim =
Array.iteri (fun case total -> begin
print "\n%i: " case;
for j = 1 to total do
print "! ";
done;
end);;
Out[5]:
On peut définir et afficher deux exemples de configuration d'un jeu de Nim, venant de la figure 1.
In [6]:
let a = [| 1; 3; 5 |] ;;
print "\n Configuration (a) de la Figure 1 :";
print_nim a;;
Out[6]:
Out[6]:
In [7]:
let b = [| 1; 3; 2 |] ;;
print "\n Configuration (b) de la Figure 1 :";
print_nim b;;
Out[7]:
Out[7]:
Elle est donnée par le corollaire 1. en page 6/7 du texte.
On a besoin du xor ("ou exclusif", cf cette page) bit à bit, obtenu en OCaml avec l'opérateur lxor) :
Petit rappel sur cette fonction xor :
| Entrée | Entrée | Sortie | |
|---|---|---|---|
| False | $\oplus$ | False | = False |
| False | $\oplus$ | True | = True |
| True | $\oplus$ | False | = True |
| True | $\oplus$ | True | = False |
On peut la définir avec l'opérateur infixe :
In [8]:
let somme_nim = ( lxor ) ;;
Out[8]:
Ou bien plus simplement :
In [9]:
let somme_nim x y = x lxor y ;;
Out[9]:
Quelques exemples, juste pour vérifier.
0 et 1 :
In [10]:
somme_nim 0 0;; (** = 0 *)
somme_nim 0 1;; (** = 1 *)
somme_nim 1 0;; (** = 1 *)
somme_nim 1 1;; (** = 0 *)
Out[10]:
Out[10]:
Out[10]:
Out[10]:
In [39]:
somme_nim 3 5;; (** 3 xor 5 = 011_2 xor 101_2 = 111_2 = 6 *)
somme_nim 5 9;; (** 5 xor 9 = 0101_2 xor 1001_2 = 1100_2 = 12 *)
somme_nim 12 1;; (** 12 xor 1 = 1100_2 xor 0001_2 = 1101_2 = 13 *)
somme_nim 12 2;; (** 12 xor 2 = 1100_2 xor 0010_2 = 1110_2 = 14 *)
Out[39]:
Out[39]:
Out[39]:
Out[39]:
D'après le corollaire 1., il suffit d'appliquer un xor bit à bit à chaque valeur du tableau pour calculer $\gamma$.
En OCaml, on peut faire ça avec une boucle, une fonction récursive, ou plus concisement avec Array.fold_left.
In [12]:
Array.fold_left ;;
Out[12]:
Rappel : fold_left prend une fonction f(x,y) et x0 calcule
f( ... f( f( x0, a[0] ), a[1] ), a[n-1] ).
Ici, pour f = somme_nim, il faut donner x0 = 0 pour que le premier calcul f(0, a[0]) = a[0].
In [13]:
let gamma = Array.fold_left somme_nim 0;;
Out[13]:
In [14]:
print "\nGamma(a) = %i" (gamma(a));;
print "\nGamma(b) = %i" (gamma(b));;
Out[14]:
Out[14]:
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.
On a d'abord besoin d'une exception pour signaler s'il n'y a pas de stratégie gagnante.
In [15]:
exception Pas_de_Strat_Gagnante;;
Out[15]:
In [40]:
let next ?(id=0) config =
let g = gamma config in
(** La prop. 5 donne directement : si g(s_0) = 0 alors échec. *)
if g = 0 then raise Pas_de_Strat_Gagnante;
(** Sinon, on calcul les gamma des fils, et on pointe vers le fils avec un gamma nul. *)
print "\n\nIl y a une stratégie gagnante :\n";
(** En pratique, on aurait pas besoin de calculer chaque fils,
comme on sait que g != 0, et on doit obtenir g' = 0,
on peut s'arreter au premier coup qui donne g' = 0.
*)
let config' = Array.copy config in
let colonne = ref 0 and
nb = ref 1 in
(** Il suffit d'explorer toutes les configurations accessibles depuis l'état actuel : *)
for j = 0 to (Array.length config') - 1 do
for i = 1 to config'.(j) do
config'.(j) <- config'.(j) - i; (** On essaie d'appliquer ce coup. *)
if (gamma config') = 0 then begin
(** On a trouvé un coup gagnant, on le stocke. *)
colonne := j;
nb := i;
end;
config'.(j) <- config'.(j) + i; (** On annule ce coup. *)
done;
done;
(** On applique le coup retenu, dernier coup à donner gamma(c') = 0. *)
print "\nLe joueur courant (numéro %i) doit enlever %i allumette à la %i-ième rangée." id !nb !colonne;
config'.(!colonne) <- config.(!colonne) - !nb; (** On retire nb allumette sur cette colonne. *)
(* assert ((gamma config') = 0); (** Si on veut vérifier *) *)
config'
;;
Out[40]:
Note : cette fonction utilise la notation
?(id=0)dans sa définition pour définir un argument optionnel avec valeur par défaut. La fonctionnextpeut être appelée de deux façons :
next a: sans spécifierid, qui vaudra donc0,next ~id:1 a: en spécifiantid=1, qui vaut ici1.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.
On peut tester cette fonction sur nos deux configuration a et b :
In [41]:
try
print_nim (next ~id:0 a);
with _ -> print "\n\nBlocage durant la simulation 1 (sur a).";;
Out[41]:
In [42]:
try
print_nim (next ~id:1 b);
with _ -> print "\n\nBlocage durant la simulation 2 (sur b).";;
Out[42]:
On a d'abord besoin de deux fonctions utilitaires :
array_filter, pour filtrer un tableau (comme List.filter mais pour un array). 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. choose pour choisir un élément aléatoire (uniforme) dans un tableau. En Python, on aurait 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).(Et oui, la libraire standard de OCaml est assez limitée)...
In [19]:
let array_filter pred a =
Array.of_list (List.filter pred (Array.to_list a));;
let choose a
= a.(Random.int (Array.length a));;
Out[19]:
Out[19]:
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").
La stratégie aléatoire fonctionne en trois étapes :
array_filter, dans le tableau indices),i (uniformément),1 et xi, pour xi le nombre d'allumette dans la rangée i (i.e., xi = config.(i)).
In [20]:
(** Un adversaire stupide qui joue aléatoirement. *)
let random ?(id=1) config =
print "\nLe joueur courant (numéro %i) joue aléatoirement.\n" id;
let indices = array_filter ( fun i -> (config.(i) > 0) ) (Array.init (Array.length config) (fun i -> i)) in
let i = choose indices in
print "Le joueur (%i) choisi de regarder la %i-ième rangée.\n" id i;
let nbAEnlever = 1 + Random.int config.(i) in
print "Le joueur (%i) choisi d'enlever %i allumettes parmi les %i disponibles.\n" id nbAEnlever config.(i);
let config' = Array.copy config in
config'.(i) <- config.(i) - nbAEnlever;
config';
;;
Out[20]:
On peut ainsi faire un exemple de début de partie entre deux joueurs "stupides" :
In [43]:
let a0 = a ;; (* Debut du jeu *)
print_nim a0 ;;
let a1 = random ~id:0 a0 ;;
print_nim a1 ;;
let a2 = random ~id:1 a1 ;;
print_nim a2 ;;
let a3 = random ~id:0 a2 ;;
print_nim a3 ;;
(* ... etc *)
Out[43]:
Out[43]:
Out[43]:
Out[43]:
Out[43]:
Out[43]:
Out[43]:
Out[43]:
On peut aussi faire le même exemple de début de partie entre un joueur "optimal" et un joueur "stupide" :
In [44]:
let c = [| 2; 3; 2 |] ;;
let a0 = c ;; (* Debut du jeu *)
print_nim a0 ;;
let a1 = next ~id:0 a0 ;;
print_nim a1 ;;
let a2 = random ~id:1 a1 ;;
print_nim a2 ;;
let a3 = next ~id:0 a2 ;;
print_nim a3 ;;
(* ... etc *)
Out[44]:
Out[44]:
Out[44]:
Out[44]:
Out[44]:
Out[44]:
Out[44]:
Out[44]:
Out[44]:
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 !).
In [23]:
exception Perdu of int;;
Out[23]:
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).
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).
In [45]:
let kpas config id nbPas =
let id = ref id in
let config' = ref (Array.copy config) in
for i = 1 to nbPas do
print "\nTour numéro %i." i;
print_nim !config';
print "\n";
if (Array.fold_left ( + ) 0 !config') = 0 then raise (Perdu !id);
begin
if !id = 0 then (** Le joueur 0 joue bien. *)
config' := next ~id:(!id) !config'
else (** Mais le joueur 1 joue aléatoirement. *)
config' := random ~id:(!id) !config'
end;
id := 1 - !id; (** Juste pour alterner entre 0 et 1 : 0 -> 1, 1 -> 0 *)
done;
!config';
;;
Out[45]:
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 :
In [46]:
let simulation config =
(** On compte le nombre total d'allumettes. *)
let n = Array.fold_left (fun i j -> i + j + 1) 0 config in
(** Puis on lance le joueur 0 avec au plus [n] pas. *)
kpas config 0 n;
;;
(** Dernière fonction, [nim], qui lance [simulation] et rattrape les exceptions. *)
let nim a =
let resultat =
(* try ignore (simulation a) with *)
try ignore(simulation a); None with
| Perdu i -> (Some i)
| Pas_de_Strat_Gagnante -> None
in
begin
match resultat with
| None -> print "Blocage à cause de la stratégie optimisée.\n\n"
| Some i -> print "\n ==> Le joueur %i a perdu !\n\n" i
end;
resultat
;;
Out[46]:
Out[46]:
In [47]:
nim a;;
Out[47]:
In [48]:
nim b;;
Out[48]:
Pas très utile jusqu'ici...
In [49]:
nim c;;
Out[49]:
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.
La fonction randomstart(k, p) va générer une configuration aléatoire :
{1, ..., k},{1, ..., p} pour chaque ligne.
In [29]:
let randomstart k p () = Array.init (1 + Random.int k) (fun i -> 1 + Random.int p);;
Out[29]:
Par exemple :
In [30]:
let c = randomstart 5 8 ();;
print_nim c;;
Out[30]:
Out[30]:
In [31]:
let c = randomstart 5 8 () ;;
print "Configuration random c :" ;;
print_nim c;;
nim c;;
Out[31]:
Out[31]:
Out[31]:
Out[31]:
In [37]:
c = randomstart 5 8 () ;;
print "Configuration random c :" ;;
print_nim c ;;
nim c ;;
Out[37]:
Out[37]:
Out[37]:
Out[37]:
C'est effectivement possible que le joueur 0 (celui qui commence) perde, même en suivant sa stratégie gagnante.
Si le joueur aléatoire 1 a de la chance...
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).
Quelques remarques :
optimal() (cf. plus haut).Edit : j'avais une erreur dans mon calcul de
next, corrigée le 11/01/17.
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 !
Il faut aussi :
C'est tout pour aujourd'hui les amis ! Allez voir d'autres notebooks si vous voulez.