Le projet chaines de Markov : Computer Chess, regroupe des notions de théorie des langages et des processus stochastiques discret d’ordre un.
ETC: 15 hours (deadline – 5 classes)
2-3 students per team
Please take your time on both quality and contents
Associate professor and assistant professors will not answer questions about the project.
BAREME : 40 points
- 10 Points
- 15 Points
- 15 points
“Cameraman: Do you think a human being will ever beat a person at chess? John: Oh... between a human being and a person? My money's on the computer.”
Partie 1 : Des données lisibles et compréhensibles
« A computer once beat me at chess, but it was no match for me at kick boxing. »
Le défi est de taille, le tournoi mondial annuel d’échec à lancer un défi aux premiers informaticiens : créer un programme capable de battre un humain aux échecs. C’est une première, et vous devez montrer au monde entier le potentiel de l’informatique.
Afin de vous familiarisez avec les règles des échecs, vous regardez en boucle les anciens tournois de Mikhail Tal, Bobby Fisher et Anatoly Karpov ainsi que les débuts prometteurs du jeune et redoutable Garry Kasparov.
Les coups possible (en termes de déplacement, et non de position) sont enregistrés comme des symboles de l’alphabet. Une suite de coup décisionnaire signifie qu’à partir d’une configuration donnée favorable, il existe au moins une stratégie permettant d’atteindre surement une position favorable d’échec et mat.
L’ordinateur va donc construire pour des configurations favorables des arbres de décisions (comme au projet 1). Prenons pour exemple les mots suivant pour une configuration favorable A :
- abbaaccad
- baacdaadd
- abaacdddd
Afin de réduire l’arbre, nous allons employer une autre technique que pour le sujet 1. En première étape, vous allez attribuer en plus du symbole, le nombre de passage par l’arc. Initialement ce nombre est égale à 1 pour chaque arc.
La deuxième étape consiste à calculer le coefficient de compatibilité entre deux états. Dans notre exemple nous allons mergés deux états s’ils sont 100% compatible. Deux états sont 100% compatible s’ils ont les mêmes symboles prédécesseurs et successeurs. Par exemple sur les préfixes abba et baab, le binôme ab ou ba sont 100% compatible. Lors de la fusion, il faut aussi fusionner le nombre de passage par les arcs (donc ici on somme 1+1).
La troisième étape consiste à merger des états 50% compatible, c’est-à-dire avec seulement les mêmes successeurs ou seulement les mêmes prédécesseurs. Il est donc possible de converger les états finaux en un seul état final, puisque tous les états finaux ont les mêmes successeurs (ici l’ensemble vide).
La quatrième et dernière étape sert à fabriquer la chaine de Markov en temps discret associé. Pour chaque état, la probabilité des arcs d’entrée (resp. de sortie) est égale au nombre de passage de cet arc divisé par la somme des nombres de passage d’entrée (ou de sortie, ce nombre est le même).
Notation
- Etape 1 (2 points)
- Etape 2 (3 points)
- Etape 3 – ne faites pas la convergence sur tous les cas possibles, deux au minimum dont l’état final (3 points)
- Etape 4 (2 points)
Partie 2 : Etude du comportement
« Beuscher: Is there any possibility that this is uh… some kind of uh… very advanced… I mean, we just gave up a queen to get his queen and now we’re basically just… um…»
Maintenant que vous avez des automates stochastiques (un délicieux mélange d’automate et de chaîne de Markov), il est temps d’étudier leur comportement, c’est-à-dire l’étude de la chaîne de Markov associé. Pensez à bien analyser les états finaux (échec et mat).
Etudiez le comportement des deux chaines de Markov en temps discret suivantes :
L’état 6 est un état final.
Les états absorbants sont les configurations « échec et mat ». L’état s0 est l’état initial, le vecteur initial commence donc uniquement par cet état.
Notation
- Chaîne 1 (7 points)
- Chaîne 2 (8 points)
Partie 3 : Réduction de l’automate et prédiction
“Chess is the struggle against the error.” – Johannes Zukertort
Maintenant que votre système d’apprentissage machine est au point, il faut penser à la partie technique. Votre ordinateur possède deux Cores et ainsi il est possible de faire du calcul parallèle. Le problème de Bus se pose alors, vous faut-il un Bus ou deux Bus pour acheminer les informations vers les processeurs ? Sachant que les informations arrivent toujours selon un processus de Poisson de taux λ et qu’ils sont servi avec un processus de Poisson de taux similaire, calculer la distribution stationnaire, l’occupation des processeurs, le nombre de messages perdus ainsi que le temps d’attente moyen avant d’être servi pour les deux configurations.
Notation
- Modélisation des deux configurations (5 points)
- Analyse de la première configuration (5 points)
- Analyse de la seconde configuration (5 points)
