Page du cours du M1 Big Data 2016-2017

Bonjour,

Cette page est destinée à contenir les documents du cours de M1 Big Data que j'assure au second semestre 2016--2017.

Jean Méhat

Contenu des cours

Lundi 23 janvier

Qu'est-ce qu'un jeu ? Les classes de jeux. Un jeu comme un graphe avec état = noeud et coups = arcs. Trouver un coup gagnant dans un graphe. À la main sur Peg Solitaire simplifié. Trouver un coup gagnant avec une exploration en profondeur d'abord d'un arbre plongé dans le graphe (pseudo-code) : code plus simple, économie de mémoire, (temps supérieur). [Pas de mention du noyau de Grundy]

      // imprime (à l'envers) une séquence de coups gagnante si elle existe
      Position p;

      int explorer(){
        if (p est une position finale)
          return p est-il une position gagnante ?
        else {
          pour (chaque coup c légal dans p){
            jouer c dans p
            tmp = explorer();
            de-jouer c de p (= remettre p dans son état avant qu'on joue c)
            if (tmp == Vrai){
              imprimer c;
              return Vrai;
            }
            return Faux;
          }
        }
      } // fin d'explorer()
    

À faire pour le lundi 30 janvier, au choix :

Il est impératif de réaliser ce travail pour lundi prochain, éventuellement à plusieurs. Vous devez m'adresser le résultat par mail à l'adresse jm@ai.univ-paris8.fr avant dimanche 23 heures 59.

Corrigé : on peut trouver un corrigé dans les fichiers peg.c et peg.h

.
Lundi 30 janvier

Corrigé du devoir

Le jeu de Nim

L'algorithme Minimax :

	Position p;

	int
	maximiser(){
          if (p est finale)
            return valeur(p);
          else {
            val = -infini;
            pour chaque coup c légal dans p {
              jouer(c);
              tmp = minimiser();
              dejouer(c)
              if (tmp > val)
                val = tmp;
           }
           return val;
	}
      
Il y a une fonction minimiser qui est presque pareille.

À faire pour la semaine prochaine : écrire un programme qui reçoit une position à Nim (sur la ligne de commande, avec une suite de nombres) et qui utilise Minimax pour choisir un bon coup (s'il existe). Le résultat est à m'envoyer sur l'adresse jm@ai.univ-paris8.fr, avec un sujet qui commence par [Bida] avant le dimanche 5 février minuit.

Si vous avez du temps, ce serait bien de regarder l'évolution du nombre de noeuds explorés suivant le nomnre de tas et le nombre d'allumettes de chaque tas.

Je vous rappelle que ce n'est pas une bonne idée en général d'utiliser Minimax pour choisir un coup à Nim. (Il y a mieux.)

Le jeux des checkers ; les règles ; le programme de Samuel ; Chinook, Jonathan Schaeffer et l'université d'Alberta.

L'exploration à profondeur limitée. Les fonctions d'évaluation. La profondeur et l'évaluation dans le programme de Samuel ; bribes d'apprentissage.

Lundi 6 février

Alpha-béta

À faire pour la semaine prochaine : reprendre le programme de la semaine dernière (qui explorait une position à Nim avec minimax) ; le corriger (notamment tenir compte de mes remarques) ; s'en servir de base pour compter le nombre de noeuds explorés dans une position par (1) minimax (2) alphabeta(-infini, +infini) et (3) alphabeta(perdu, gagne). À rendre par mail avant dimanche minuit.

Corrigé : j'ai publié un corrigé pour cet exercice qu'on trouve ici.

Lundi 13 février

Transposition, hachage à la Zobrist, approfondissement itératif.

À faire pour la semaine prochaine : reprendre le programme de la semaine dernière (celui qui explorait les positions avec AlphaBeta(perdu, gagne)) ; lui rajouter les tables de transpositions ; compter le nombre de noeuds explorés.

Ce pourrait être une bonne idée aussi d'implémenter la bonne méthode pour trouver les coups gagnants (celle à base de XOR vue au tableau).

Lundi 20 février

Les jeux impartiaux dans la théorie combinatoire des jeux ; les nimbres et l'addition des nimbres ; comment toujours gagner aux jeux impartiaux

À faire pour dans quinze jours :

  • Corrigé ici.

    Lundi 6 mars

    La théorie des jeux : forme extensive, information set, forme normale, passage de la forme extensive à la forme normale, coups dominés, valeur d'un jeu, points selles, stratégies mixtes, équilibres de Nash.

    Pas de devoir demandé.

    Lundi 13 mars

    Choix du sujet : puissance 4 en version misère.

    MCTS : on s'est arrêté à MC (avant TS).

    Lundi 20 mars

    À rendre pour le 27 mars : générateur de coups pour puissance 4 version misère. Obligatoire et en binome déja formés. Il sera obligatoire de ré-utiliser ce code dans la version finale du projet.

    MCTS