XD blog

blog page

projets


2013-02-03 Quelques précisions sur les projets informatiques

Données textuelles, nuages de mots

Certains sujets traitent du traitement de texte et dans ce domaine, il est parfois important d'obtenir des données en grande quantité. La source la plus accessible et une des plus propres est Wikipedia dont il est possible de télécharger une copie dans n'importe quelle langue à partir de l'adresse suivante : wikipedia backups. Il faut chercher sur cette page un lien xxwiki ou xx sont les deux premières lettres d'une langue (frwiki par exemple). Il est possible de télécharger tout ou partie du site (cela peut prendre quelques heures).

Lire les informations présentes dans ces fichiers de plusieurs Go requiert quelques connaissances en XML, puis de comprendre la structure plutôt intuitive du document. Pour vous aider, vous pourrez lire l'article sur le parser XML en espérant que cela vous fasse gagner du temps.

La liste des sujets fournit quelques références concernant la construction des nuages de mots. Pour l'affichage, le language HTML est sans doute le plus simple. Il permet de composer des blocs de texte de différentes tailles et se charge de les disposer. Le code HTML suivant permet de modifier la taille du texte affiché par un navigateur (Firefox par exemple) :

<font size="6">This is some text!</font>

Taille 6Taille 16

Ce texte pourrait être la sorti d'un programme Python.

Données financières

Les sujets proposés font tous intervenir une optimisation qui requiert des données pour être menée à terme. Le programme suivant recuperation_serie_financiere.py récupèrent des données quotidiennes depuis le site de Yahoo Finance et les enregistre sous forme de fichier texte. Le programme peut être facilement modifié pour récupérer les cours de sociétés autres que celles du CAC40, ce qu'il fait par défaut. L'article TableFormula décrit un programme permettant de récupèrer les données financières ainsi enregistrées sous forme de table.

Le module MatPlotLib permet de tracer des graphes de séries financières même si ce n'est pas la seule. Le programme suivant graphohlc.py permet de représenter une série financière. Il sera facile d'adapter ce graphique pour y ajouter plusieurs séries. L'essentiel est que les axes comportent des unités et des dates.

Trend following, pair trading, gestion de portefeuille, ce document présente quelques des algorithmes de trading. Il rappelle aussi quelques définitions couramment utilisées (volatilité, rendement, ratio de Sharpe). La conception de tels algorithmes, dont l’objectif avoué est de pouvoir faire du trading sans intervention humaine, requiert une certaine rigueur afin de s’assurer de la robustesse de la stratégie financière. C’est aussi un sujet que cet exposé aborde avec la description du back testing ou la prise en compte de coûts cachés (coûts de transaction, slip edge) qui expliquent en partie que des stratégies ne soient pas aussi prometteuses que leur évaluation sur des données passées le laissait penser.

Jeux sans hasard et intelligence artificielle

Othello, Puissance 4, les échecs, les dames, sont des jeux qui opposent deux joueurs autour d'un plateau. Aucun hasard n'intervient. Pour implémenter un joueur artificiel (ou intelligence artificielle, même si intelligence est sans doute un terme galvaudé dans ce cas), on peut s'inspirer de l'algorithme MiniMax (la version anglaise est plus complète). Il s'agit d'envisager tous les coups possibles jusqu'à une certaine profondeur tout en choisissant le meilleur coup pour l'adversaire. Selon les jeux, cette approche peut être assez gourmande en calcul ce qu'il est possible d'améliorer en travaillant sur une fonction d'évaluation de chaque coup ou en ne choisissant de ne pas explorer tous les coups (voir Alpha Beta ou sa version anglaise). La plus simple des fonctions d'évaluation des coups (ou fonction de coût) consiste à compter le nombre de pièces ou de pions pris mais celle-ci peut tout-à-fait inclure des informations relatives à la disposition des pièces sur le plateau de jeu.

Jeux de hasard et intelligence artificielle

Poker, Belotte utilisent des cartes et l'état du jeu à un instant quelconque n'est pas entièrement décrit par le plateau de jeu. Il n'est pas possible d'utiliser des algorithmes de type MiniMax sans faire intervenir des simulations aléatoires. Celles-ci permettront d'estimer la probabilité que telle ou telle ensemble de cartes apparaissent. Le joueur optimisera l'espérance de ses gains. Les meilleurs stratégies incluent les décisions des autres joueurs comme au Poker mais transcire cela sous forme d'algorithme n'est pas chose facile.

Jeux et interface graphique

L'interface graphique est en général réalisée à l'aide du module PyGame. Le programme inclus alors une boucle principale qui attend des événements (un clic de souris, la pression d'une touche) et agit en conséquence. Comme exemple, voici une fonction qui a été implémentée par des élèves l'année dernière :

def Accueil():
    continuer=True
    fenetre.blit(fond,(0,0)) #affichage de l'image en haut à gauche de notre fond d'écran
    pygame.display.flip() #raffraîchissement de l'écran
    while continuer:
        for event in pygame.event.get():
            if event.type==QUIT:
                continuer=False
            if event.type==KEYDOWN and event.key==K_ESCAPE:
                continuer=False
            if event.type == MOUSEBUTTONUP and event.button == 1 and event.pos[0]>218 and event.pos[0]<587\
                and event.pos[1]>139 and event.pos[1]<206: #bouton Joueur VS. Joueur
                JvJ()
                continuer=False
            if event.type == MOUSEBUTTONUP and event.button == 1 and event.pos[0]>218 and event.pos[0]<587\
                and event.pos[1]>225 and event.pos[1]<294: #bouton Joueur VS. Ordinateur
                vsOrdi()
                continuer=False
            if event.type == MOUSEBUTTONUP and event.button == 1 and event.pos[0]>218 and event.pos[0]<587\
                and event.pos[1]>316 and event.pos[1]<383: #bouton I.A. vs. I.A.
                IAvsIA()
                continuer=False
            if event.type == MOUSEBUTTONUP and event.button == 1 and event.pos[0]>218 and event.pos[0]<587\
                and event.pos[1]>404 and event.pos[1]<471: #bouton Crédits
                Credits()
                continuer=False
            if event.type == MOUSEBUTTONUP and event.button == 1 and event.pos[0]>218 and event.pos[0]<587\
                and event.pos[1]>495 and event.pos[1]<561: #bouton Quitter
                continuer=False
        pygame.display.flip()
Vous pouvez aussi jeter un coup d'oeil sur le programme introduit au paragraphe suivant.

Propagation d'une épidémie, évoluion de population

On peut étudier ces phénomènes selon une approche macro ou micro. Les modèles macro font souvent apparaître des équations différentielles comme celles du modèle Lokta Volterra qui modélisent l'évolution des populations de proies et de prédateurs (version anglaise). L'article Factors that make an infectious disease outbreak controllable pousse cette approche pour évaluer l'efficacité de mesures pour contrôler l'évolution d'une épidémie.

Le programme suivant propose un exemple d'approche micro. Il s'agit de modéliser plus ou moins fidèlement le comportement de chaque individu puis d'étudier l'évolution d'une population.

Entre ces deux approches, une troisième est possible à mi-chemin si on considère la possibilité de représenter les interactions entre individus sous forme de graphes. Chaque noeud représente un individu, chaque arc une relation entre ces deux individus. Les propriétés du graphe ont-elle un impact sur la propagation d'une épidémie ? L'article The Effectiveness of Contact Tracing in Emerging Epidemic donne quelques idées de ce qu'on peut attendre d'une telle approche. L'article Scale Free Networks étudie différentes tolopologies de réseau et leur présence dans différents domaines.

Pour cette dernière approche, il peut s'avérer utile de dessiner des graphes, ce que propose le module yapgvb pour le langage Python.

Pentomino

Même si ce sujet semble plutôt spécifique, l'algorithme utilisé (décrit ici) pour résoudre le puzzle s'appuie sur une exploration qu'on représente sous forme d'arbre comme celle utilisée pour résoudre ce puzzle. Chaque noeud de l'arbre représente un choix, celui de positionner une pièce de cette manière ou d'une autre. Les noeuds plus bas dans l'arborescence auront tous comme point commun le choix effectué à ce moment précis de la résolution. Ce type d'approche peut être adapté à d'autres problèmes de résolution de contraintes (Sudoku, l'énigme d'Einstein). Un language de programmation logique comme Prolog inclut implicitement cette exploration arborescence à condition de savoir représenter les contraintes du problème.

Construction d'une texture

Le projet s'appuie sur une idée plutôt simple mais gourmande en calcul développée dans l'article suivant. Il s'agit de peindre un mur à partir d'un motif quelconque. Si ce motif est carré par exemple, le recopier plusieurs fera probablement apparaître un quadrillage car il est peut probable que les bords droit et gauche s'ajustent parfaitement. L'article propose un moyen de faire en sorte qu'on ne voit aucun quadrillage. Il utilise une méthode utilisée pour faire de la prédiction : les plus proches voisins. Le programme informatique devra utiliser le module numpy afin d'obtenir des temps de calculs suffisamment rapides. La librairie graphique installée à l'ENSAE n'est plus maintenue (PIL), je suggère d'utiliser Pillow qui est disponible pour les dernières versions de Python.

Jeu de plateforme

Les jeux de plateformes sont intéressants à plusieurs niveaux. Le premier défi est de réaliser une interface fluide : les personnages doivent réagier rapidement lorsqu'on presse une touche. Les personnages autres que celui manipulés par le joueur ne doivent pas tourner en rond.

En ce qui concerne le premier défi, la solution proposée plus haut présente le défaut de passer beaucoup de temps à attendre :

Si les calculs que le programme effectue entre deux pressions d'une touche dépassent 50ms, le défilement du jeu apparaît saccadé. Le joueur est frustré et appuie d'autant plus sur les touches pour faire réagir le jeu qui essaye tant bien que mal de rattraper le temps perdu. Une solution pour éviter cela est d'utiliser les threads (voir le chapitre 9 du support de cours). La réception des événements générés par l'utilisateur est un thread, les calculs en sont un autre, l'affichage un dernier. Ce mécanisme permet de traiter plusieurs événements d'un coup (le joueur a pressé dix fois la touche droite).

En ce qui concerne le déplacements des autres joueurs, la première direction est d'implémenter une fonction assez simple qu'on modifie au fur et à mesure des essais du jeu. Par exemple, si un méchant doit poursuivre un gentil, il se déplace dans sa direction. S'il est bloqué par un mur, on détecte qu'il ne bouge plus alors il doit prendre un direction au hasard et la suivre pendant quelques temps. Cette approche fonctionne dans un premier temps.

La seconde option est de prévoir une telle fonction pour tous les éléments mobiles, y compris le joueur. Cette fonction est en quelque sorte une fonction à trous : elle prend en compte des configurations (élément mobile bloqué depuis plus de deux secondes, élément mobile entouré de murs, présence d'objet récompense devant, présence d'un méchant derrière, ...) et elle retourne une décision. Cette fonction retourne des décisions différentes en fonction de paramètres : si la distance de la récompense est alpha fois plus grande que celle du méchant, alors aller vers la récompense sinon fuir.

Pour déterminer les paramètres optimaux, on peut par exemple lancer le programme un grand nombre de fois (sans interface graphique) et on optimise tour à tour :

Optimisation veut dire essentiellement choisir aléatoirement des paramètres et choisir ceux qui ont obtenus les meilleurs résultats.


Xavier Dupré