Imaginez un
duel au
sommet, deux joueurs omniscients s'affrontent autour d'un tablier de 64
cases dans une partie endiablée de Reversi
(l'ancêtre du jeu Othello). Qui va gagner ? C'est la
question à laquelle tente de
répondre le projet Reversi@home.
À
défaut de pouvoir répondre immédiatement à cette interrogation, le projet vient tout juste de terminer les calculs dans un tablier de 36 cases.Quatre mois
après le lancement officiel du projet et un peu moins d'un
mois
après l'annonce de l'envoi des dernières
unités, tous les calculs de la première phase du
projet Reversi@home
ont été effectués. L'analyse des
résultats est en cours et devrait
durer un certain temps étant donné qu'elle est
effectuée manuellement. A l'issue de cette analyse, on
connaitra la "solution" du Reversi dans un tablier de 6x6
cases. C'est-à-dire qu'en partant du principe que
les deux joueurs ont un jeu "parfait", on connaitra, avant
même que la partie ne commence, qui va gagner : le premier
joueur (celui
qui inaugure la partie en posant le premier pion), le
deuxième joueur,
ou si le jeu va se terminer sur un match nul.
La résolution du problème dans un tablier de 36 cases n'est qu'une première étape avant la résolution du jeu de Reversi classique se déroulant dans un tablier de 64 cases (8 x 8 cases).
Le résultat du projet Reversi@home sera confronté à la solution obtenue en 1993 par le Professeur Joel Feinstein (Forty Billion Nodes Under The Tree). A l'époque, ce champion d'Othello et mathématicien britannique avait utilisé les ordinateurs de la faculté des Sciences et Mathématiques de l'université de Nottingham pour calculer la solution du Reversi 6x6 cases. Il avait découvert, après 7 semaines de calcul, que le second joueur l'emportait quel que soit la configuration de départ des 4 premiers pions. Le second joueur l'emportait 20 à 16 avec une configuration de départ des pions classique (disposition initiale du jeu Othello) et 19 à 17 avec une configuration des pions alternative (les deux pions noirs et les deux pions blancs sont placés parallèlement sur les 4 cases centrales du jeu) (voir les deux solutions possibles). Le professeur Joel Feinstein avait calculé qu'en utilisant la même technique, il lui aurait fallu 1014 plus de temps, soit 3,8 milliers de milliards d'années avec les moyens informatiques de l'époque pour résoudre le jeu de Reversi classique (8x8 cases). Aujourd'hui, avec l'amélioration considérable de la puissance de calcul des ordinateurs et avec l'aide du calcul partagé, la résolution de ce problème en un temps raisonnable devient enfin possible
Les règles du jeu Reversi
Le jeu est composé d'un tablier de 64 cases (8 sur 8) et de 64 pions (traditionnellement rouge d'un coté, noir de l'autre). En début de partie, les deux joueurs posent alternativement un pion sur les 4 cases centrales. Ensuite, chaque joueur, rouge et noir, pose l'un après l'autre un pion de sa couleur sur le tablier. Le but est de capturer (retourner) le maximum de pions de l'adversaire. La capture de pions survient lorsqu'un joueur place un de ses pions à l'extrémité d'un alignement de pions adverses contigus et dont l'autre extrémité est déjà occupée par un de ses propres pions. Les alignements considérés peuvent être une colonne, une ligne, ou une diagonale. Le jeu s'arrête quand les deux joueurs ne peuvent plus poser de pion. On compte alors le nombre de pions. Le joueur ayant le plus grand nombre de pions de sa couleur sur le tablier a gagné.
Le futur du projet Reversi@home
L'application va maintenant être entièrement reprogrammée pour pouvoir effectuer les calculs beaucoup plus rapidement. Les responsables du projet espèrent multiplier par dix l'efficacité de l'algorithme. Les calculs devraient reprendre l'année prochaine, peut être même dès le 1er Janvier. Il s'agira cette fois d'effectuer une deuxième fois les calculs dans un tablier de 36 cases pour observer la rapidité de l'algorithme mais aussi et surtout s'assurer que les calculs sont justes.
Ensuite, une fois que l'efficacité du nouvel algorithme aura été démontrée, Reversi@home pourra débuter les calculs dans un tablier de 64 cases.
Pour patienter, un sondage va être organisé pour fixer le nom du projet (un message électronique sera envoyé à tous les participants au projet pour avertir de l'ouverture de la votation). Plusieurs noms circulent déjà : SGame@home, SymetricGameSolver, BoardGameSolver, Gambler,...
A très long terme, le projet pourrait s'intéresser à d'autres jeux de société combinatoires.
La résolution du problème dans un tablier de 36 cases n'est qu'une première étape avant la résolution du jeu de Reversi classique se déroulant dans un tablier de 64 cases (8 x 8 cases).
Le résultat du projet Reversi@home sera confronté à la solution obtenue en 1993 par le Professeur Joel Feinstein (Forty Billion Nodes Under The Tree). A l'époque, ce champion d'Othello et mathématicien britannique avait utilisé les ordinateurs de la faculté des Sciences et Mathématiques de l'université de Nottingham pour calculer la solution du Reversi 6x6 cases. Il avait découvert, après 7 semaines de calcul, que le second joueur l'emportait quel que soit la configuration de départ des 4 premiers pions. Le second joueur l'emportait 20 à 16 avec une configuration de départ des pions classique (disposition initiale du jeu Othello) et 19 à 17 avec une configuration des pions alternative (les deux pions noirs et les deux pions blancs sont placés parallèlement sur les 4 cases centrales du jeu) (voir les deux solutions possibles). Le professeur Joel Feinstein avait calculé qu'en utilisant la même technique, il lui aurait fallu 1014 plus de temps, soit 3,8 milliers de milliards d'années avec les moyens informatiques de l'époque pour résoudre le jeu de Reversi classique (8x8 cases). Aujourd'hui, avec l'amélioration considérable de la puissance de calcul des ordinateurs et avec l'aide du calcul partagé, la résolution de ce problème en un temps raisonnable devient enfin possible
Les règles du jeu Reversi
Le jeu est composé d'un tablier de 64 cases (8 sur 8) et de 64 pions (traditionnellement rouge d'un coté, noir de l'autre). En début de partie, les deux joueurs posent alternativement un pion sur les 4 cases centrales. Ensuite, chaque joueur, rouge et noir, pose l'un après l'autre un pion de sa couleur sur le tablier. Le but est de capturer (retourner) le maximum de pions de l'adversaire. La capture de pions survient lorsqu'un joueur place un de ses pions à l'extrémité d'un alignement de pions adverses contigus et dont l'autre extrémité est déjà occupée par un de ses propres pions. Les alignements considérés peuvent être une colonne, une ligne, ou une diagonale. Le jeu s'arrête quand les deux joueurs ne peuvent plus poser de pion. On compte alors le nombre de pions. Le joueur ayant le plus grand nombre de pions de sa couleur sur le tablier a gagné.
Le futur du projet Reversi@home
L'application va maintenant être entièrement reprogrammée pour pouvoir effectuer les calculs beaucoup plus rapidement. Les responsables du projet espèrent multiplier par dix l'efficacité de l'algorithme. Les calculs devraient reprendre l'année prochaine, peut être même dès le 1er Janvier. Il s'agira cette fois d'effectuer une deuxième fois les calculs dans un tablier de 36 cases pour observer la rapidité de l'algorithme mais aussi et surtout s'assurer que les calculs sont justes.
Ensuite, une fois que l'efficacité du nouvel algorithme aura été démontrée, Reversi@home pourra débuter les calculs dans un tablier de 64 cases.
Pour patienter, un sondage va être organisé pour fixer le nom du projet (un message électronique sera envoyé à tous les participants au projet pour avertir de l'ouverture de la votation). Plusieurs noms circulent déjà : SGame@home, SymetricGameSolver, BoardGameSolver, Gambler,...
A très long terme, le projet pourrait s'intéresser à d'autres jeux de société combinatoires.