"Résoudre" le jeu Reversi (une variante du jeu Othello)

Détails
Robot Aibo jouant au jeu Othello Reversi@home est un projet BOINC slovaque administré par des étudiants de l'Université de Technologie de Bratislava (STU), Faculté d'Informatique et des Technologies de l'Information (FIIT). Reversi est un jeu de stratégie combinatoire abstrait inventé dans les années 1880 par deux gentlemen anglais, Lewis Waterman et John W. Mollett, (ces deux acolytes se disputèrent longtemps la paternité de ce jeu en se traitant mutuellement d'escrocs). Ce jeu fut extrêmement populaire en Angleterre à la fin du XIXème siècle. Le 1er décembre 1895, dans un article consacré aux nouveaux jeux en vogue, le New York Times écrivait que "le Reversi, c'est comme Go Bang, ça se joue avec 64 pièces" [1] (Go Bang est une comédie musicale anglaise dont la première représentation a eu lieu le 10 mars 1894 au Théâtre Trafalgar Square). En 1895, le célèbre fabricant allemand de jeux Ravensburger entreprit la commercialisation du Reversi. Ce fut d'ailleurs l'un des premiers succès commerciaux de la société. Le Reversi est aujourd'hui libre de droits. 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é.
Une variante du Reversi a été inventée en 1971 au Japon par Goro Hasegawa, ce jeu a été baptisé "Othello" en analogie avec les rebondissements de la pièce de Shakespeare (ce nom a été suggéré par le père de Goro qui était professeur de littérature anglaise au Japon). Il y a seulement deux différences avec Reversi : une seule position de départ est autorisée, et on peut emprunter des pions à l'adversaire s'il est obligé de passer. Dès 1973, le jeu devient un succès commercial au Japon et le premier championnat national est organisé. En 1976, le jeu d'Othello envahit les États-Unis et l'Angleterre.

L'objectif de Reversi@home est de "résoudre" le jeu. C'est-à-dire de partir du principe que les deux joueurs ont un jeu "parfait", puis de déterminer qui va gagner la partie : 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. Lorsque que cette solution aura été trouvée, le projet pourrait par la suite s'intéresser à d'autres jeux de société combinatoires. Un vote sera donc organisé pour trouver un nouveau nom à ce projet (par exemple SGame@home, SymetricGameSolver, BoardGameSolver, Gambler,...)

INSCRIPTION
URL du projet : http://dawn.ynet.sk/test1/

Le fonctionnement de l'algorithme, l'annulation des unités inutiles

L'algorithme du projet est doté d'une fonction qui permet de déterminer l'utilité des unités à un instant t (après analyse des unités calculées précédemment, en t-1). Les unités "non nécessaires" ne pourront pas influencer le résultat final, c'est la raison pour laquelle ces unités sont annulées et que vous ne recevrez que des unités jugées utiles à un instant t. Ce processus accélère la progression du projet. Avant l'envoi des unités aux utilisateurs, il est impossible de distinguer les unités inutiles des autres.


Détails techniques :
Durée d'une unité :  extrêmement variable, de 10 minutes à plus de 4 heures (sur un Core 2 Quad Q6600 : 2,4 Ghz)
Utilisation mémoire max. : ~ 9,8 Mo (Reversi game solver 3.01)
Téléchargement : 38 octets par unité
Délai de retour des unités : 7 jours
Points de sauvegarde : 1 minute
Système d'exploitation :  Windows, Unix et Linux, MacOS
Autre :  l'avancement ne fonctionne pas correctement (il peut monter jusqu'à 300% voire plus)

Source : wikipédia, fédération française d'Othello
   

Articles en rapport