Un scientifique japonais conquiert le jeu de société Othello

“Othello est maintenant résolu.” Avec ce résumé, un chercheur d’une société informatique japonaise a confirmé une nouvelle étape dans les réalisations du supercalculateur.

Othello, un jeu vieux de 140 ans inspiré du drame shakespearien du même nom qui dépeint le conflit entre le Maure de Venise et Desdémone, ne semble pas complexe à première vue. Il se joue sur un plateau avec des disques noirs et blancs stratégiquement positionnés en carrés sur huit rangées et huit colonnes.

Le défi, selon le bioinformaticien Hiroki Takizawa, est de concevoir un plan de match « sans erreur de la part d’aucun des deux joueurs ».

“(Cela) constitue depuis longtemps un grand défi en informatique”, a-t-il déclaré. “Dans cet article, nous annonçons que nous avons faiblement résolu Othello.”

Appliquée à la théorie des jeux, une solution « faible » fait référence à un algorithme qui assure soit une victoire contre tous les mouvements possibles d’un adversaire dès le début d’une partie, soit un match nul. Une solution « forte » est un algorithme produisant des mouvements parfaits depuis n’importe quelle position du tableau, même après que des erreurs de l’un ou l’autre des deux joueurs aient été commises.

La tâche de « résoudre » Othello est immense. Il y a 10 octillions de positions de jeu possibles, ce qui signifie que si vous aviez un ordinateur portable à la naissance de l’univers et que vous commenciez à tester un mouvement par seconde, vous seriez encore loin d’être terminé aujourd’hui.

Une telle tâche est presque un jeu d’enfant pour les systèmes informatiques massivement parallèles d’aujourd’hui.

Takizawa a utilisé le cluster de calcul intensif MN-J de son entreprise pour entreprendre cette tâche. Bien que des ordinateurs plus puissants aient été construits ces dernières années, le système MN-J comprend un composant économe en énergie qui, avec 21,1 gigaflops par watt de puissance, était considéré comme le plus puissant au monde en 2020. Il occupe désormais la 11e place.

Takizawa a développé Edax, un programme informatique utilisé pour la première fois pour analyser la stratégie d’Othello il y a des années.

“Notre percée s’est produite en améliorant l’efficacité de la recherche et en modifiant le dernier logiciel Othello”, a déclaré Takizawa.

“Le résultat d’Othello est une réalisation monumentale pour l’humanité”, a déclaré Takizawa, “qui démontre les progrès remarquables de l’informatique et de la technologie de l’IA. Résoudre Othello a été l’un des grands défis de l’IA”.

Depuis des années, les ordinateurs calculent des chiffres et battent les champions du monde dans de nombreux jeux.

DeepBlue d’IBM a conquis le champion du monde d’échecs Gary Kasparov en 1997, c’est la première fois qu’un ordinateur bat un joueur d’échecs humain dans le cadre d’un jeu formel.

De même, AlphaGo de Google a battu en 2016 le champion du monde de Go payeur Lee Sedol, considéré comme l’un des joueurs les plus forts de l’histoire du jeu. Le go est considéré comme plus difficile que les échecs. Bien que les calculs de force brute soient utilisés avec succès dans le jeu d’échecs automatique, cette approche n’est pas aussi productive au Go, où la stratégie informatique repose davantage sur l’apprentissage par renforcement.

Et les ordinateurs ont été programmés pour jouer parfaitement à Connect-4, un jeu avec 4,5 billions de scénarios de grille ; ils ne perdent jamais.

Takizawa reconnaît que certains peuvent remettre en question la légitimité des preuves informatiques. Des défauts de mémoire et des problèmes de processeur ne peuvent être exclus, a-t-il déclaré. Cependant, il a noté que la mémoire de vérification et de correction des erreurs était utilisée tout au long du processus. Il a souligné que même en cas d’erreur informatique, les chances d’infirmer ses conclusions “sont extrêmement faibles”.

Son rapport, « Othello est résolu », a été téléchargé sur le serveur de préimpression. arXiv.

© 2023 Réseau Science X