Project Euler

Standard

Euler
Project Euler est un site web proposant de nombreux problèmes d’algorithmique à résoudre. La difficulté des 388 problèmes proposés à ce jour est croissante et mettra à contribution vos méninges. La résolution du problème se fait généralement par une réflexion mathématique puis par une programmation de son idée pour obtenir le résultat attendu. Pas besoin d’avoir un super calculateur de la Nasa pour obtenir le résultat, les problèmes peuvent être résolus en “moins d’une minute” de calcul par un ordinateur domestique. Il est précisé qu’il faudra néanmoins parfois quelques heures de réflexion pour arriver à calculer un résultat, une optimisation de l’algorithme étant nécessaire pour rentrer dans des délais de calcul acceptés par l’ordinateur.

Résolution d’un problème

Tous les langages de programmation et tous les logiciels sont acceptés pour résoudre le problème. Le résultat de chaque problème demandé est un nombre, il ne faudra donc pas soumettre les méthodes de calcul de votre algorithme mais uniquement le résultat. Voici un net avantage pour vous :

  • Vous pouvez utiliser toutes les méthodes que vous souhaitez pour résoudre un problème.
  • Vous n’avez pas besoin d’attendre une quelconque validation de votre algorithme par quelqu’un de l’équipe.
  • Vous savez tout de suite si vous avez le bon résultat (ou si vous devez encore vous creuser la tête…).

Après avoir résolu un problème, vous avez la possibilité de consulter le forum associé à ce problème (et surtout pas avant l’avoir résolu !). Dans ce forum vous trouverez les solutions proposées par d’autres programmeurs qui sont arrivés au même résultat que vous, mais avec d’autres méthodes et d’autres langages. Une excellente opportunité pour découvrir de nouvelles techniques ou des optimisations très ingénieuses. Si vous vous sentez prêt, vous pouvez aussi exposer votre algorithme afin de partager votre technique avec les autres membres !

Statistiques

Quelques chiffres, pour vous donner envie de participer vous aussi :

  • 231 349 personnes ont résolu au moins un problème.
  • 3 700 797 résultats justes ont été proposés, avec une moyenne de 16 par membre.
  • 41 090 personnes ont résolu au moins 25 problèmes, ce qui représente 18 % de la totalité des membres.
  • 113 personnes ont résolu plus de 350 problèmes.

Vous pouvez trouver des statistiques sur les langages de programmation utilisés juste ici : projecteuler.net/languages.

Je veux participer !

Vous aussi vous souhaitez vous arracher les cheveux sur des problèmes mathématiques pendant des heures et exploser de joie lorsque vous aurez trouvé le bon résultat ? L’inscription se fait à cette adresse : projecteuler.net/register.

Nous participons actuellement en équipe à la résolution de ces problèmes, si vous souhaitez voir ce que nous faisons ou partager vos algorithmes avec nous : @AntoineAugusti et @ThibaudDauce sur Twitter. Et nos codes source sur GitHub : https://github.com/AntoineAug/Euler. Nous avancerons beaucoup plus durant le mois de juillet et d’août.

Bonne chance à vous dans la résolution des problèmes !

[Maths et code] Le classement Elo

Standard

Nombres
Le classement Elo est un système d’évaluation du niveau de capacités relatif d’un joueur d’échecs ou d’autres jeux à deux joueurs. Il doit son nom à Arpad Elo (1903-1992), un professeur de physique et excellent joueur d’échecs américain d’origine hongroise qui l’a mis au point. Plus généralement, il peut servir à comparer deux joueurs d’une partie, et est utilisé par de nombreux jeux en ligne. World Of Wacraft l’utilise notamment pour les cotes en arène et Mark Zuckerberg a utilisé cet algorithme pour établir un classement des filles d’Harvard (si vous avez vu The Social Network). C’est un algorithme très répandu, très utilisé et il est relativement facile à mettre en place.

Je vais vous détailler son fonctionnement mathématique puis vous expliquer comment l’implanter en PHP.

Elo, côté mathématique

Il existe plusieurs variantes du classement Elo, je vais vous en détailler une que j’ai choisi arbitrairement (il ressemble au modèle de World Of Warcraft). Vous pourrez l’adapter facilement.

Le classement Elo est un classements par points. Au début, chaque joueur commence avec 1500 points (on dit aussi une cote de 1500 ou un rang). Ce rang va évoluer selon les résultats des matchs du joueur. Schématiquement, le rang du joueur augmente quand il remporte un match et diminue lorsqu’il perd. L’augmentation ou la diminution du rang ne sera pas la même selon la difficulté du match.

Après chaque match on recalcule son rang selon la formule suivante :
Classement Elo

Résultat indique le résultat du match opposant le joueur P1 au joueur P2 :
Classement Elo

K est un paramètre permettant de régler la vitesse d’augmentation ou de diminution du rang du joueur. Dans mon modèle, j’ai choisi une ascension rapide en dessous de 1000, normale entre 1000 et 2000 et diminuée au-dessus de 2000. Vous pouvez tout à fait modifier comme vous voulez ce paramètre K en introduisant une constante ou en changeant la valeur de K selon l’intervalle que vous définissez.

J’utilise les valeurs de K suivantes :
Classement Elo

Enfin on calcule la probabilité de gagner du joueur P1 contre le joueur P2 avec la formule suivante :
Classement Elo

Rien de très compliqué ! A noter que j’ai utilisé l’excellent éditeur de texte LyX (www.lyx.org), version Linux qui se base sur le LaTeX pour créer les images des formules mathématiques.

Exemple

Dans cet exemple le paramètre est fixé tel que K = 16. Soit deux joueurs, Anne de rang 2300 et Michel de rang 1800. Calculons l’estimation de chaque joueur puis son nouveau rang en cas de victoire ou de défaite.

Classement Elo
Lorsque Anne gagne, le classement des joueurs ne change pratiquement pas vu que le résultat corrobore le classement établi. Dans le cas où Michel gagne, le classement des joueurs change de façon significative car le résultat ne correspond pas au classement établi.

Elo, côté PHP

Après avoir vu comment se comportait le classement Elo de manière mathématique, il est temps de le transformer en code PHP pour pouvoir l’utiliser.

Je vous fourni une version beaucoup commentée et affichant des statistiques volontairement pour bien comprendre le fonctionnement de l’algorithme. Dans une version de production, le code source peut (et doit) être beaucoup plus court. La seule chose à changer pour tester est la valeur des cotes des joueurs P1 et P2 et le résultat du match les opposant.

Au final on obtient quelque chose de ce style quand on exécute le script :
Classement Elo

J’espère que vous vous amuserez bien avec ceci ! Il y a de beaux projets à réaliser.