« Othello » a-t-il été résolu ?
(arxiv.org)- Il a été démontré par le calcul que, sur Othello/Reversi 8×8, si les deux camps jouent parfaitement, le résultat final est une nulle, ce qui place le jeu, selon les chercheurs, au stade de la résolution faible
- L’espace de recherche restait un problème bien plus difficile que les cas déjà résolus comme le checkers, avec environ 10^58 parties possibles et 10^28 positions de plateau estimées
- Ce résultat établit la valeur théorique du jeu depuis la position initiale ainsi que la stratégie permettant d’atteindre cette valeur, mais ne constitue pas une résolution forte calculant toutes les positions intermédiaires
- Les chercheurs expliquent avoir utilisé une recherche heuristique fondée sur un logiciel Othello et une alpha-beta search, et que l’ampleur de recherche nécessaire pour une solution précise était plus faible que les estimations précédentes
- Les données brutes et les programmes permettant de reproduire le résultat ont été publiés sur GitHub, Zenodo et figshare, ce qui en fait un cas vérifiable pour la recherche sur la résolution de jeux de stratégie purs
Résolution computationnelle d’Othello
- Othello sur plateau 8×8 a été faiblement résolu, et la valeur théorique du jeu depuis la position initiale a été calculée comme étant une nulle
- Si les deux joueurs jouent au mieux sans erreur, la partie se termine par une nulle, et cette étude l’a démontré par le calcul
- La Figure 1 présente une ligne de jeu optimale ainsi que son résultat final
- Si un écart survient à n’importe quel moment dans cette séquence, le logiciel des chercheurs garantit alors au minimum la nulle, voire la victoire, en jouant l’autre camp
- Ce résultat correspond à la prédiction de longue date des experts humains d’Othello, si bien que les chercheurs estiment que le résultat en lui-même n’est pas surprenant
Portée de la résolution et valeur théorique du jeu
- Résoudre un jeu à information complète consiste à déterminer le résultat final lorsque les deux camps produisent un jeu parfait, c’est-à-dire la valeur théorique du jeu
- Les jeux résolus sont généralement classés en trois niveaux
- Résolution ultra-faible (ultra-weakly solved) : on connaît seulement la valeur théorique du jeu depuis la position initiale
- Résolution faible (weakly solved) : on connaît la valeur théorique depuis la position initiale ainsi que les stratégies permettant aux deux camps d’atteindre cette valeur avec des ressources de calcul raisonnables
- Résolution forte (strongly solved) : on a calculé le résultat de toutes les positions possibles pouvant survenir pendant la partie
- Cette étude constitue un cas de résolution faible d’Othello, et non une résolution forte calculant toutes les positions possibles
- Le checkers est également présenté comme un jeu résolu au même sens
Pourquoi Othello est resté longtemps non résolu
- Othello est un jeu populaire à grande profondeur stratégique, inventé en Grande-Bretagne au XIXe siècle, puis diffusé largement sous sa forme actuelle au Japon au XXe siècle avant d’être joué dans le monde entier
- Le championnat du monde se tient chaque année depuis 1977, ce qui témoigne de sa popularité internationale
- L’espace de recherche est immense
- en moyenne environ 10 coups par position
- en moyenne environ 58 coups par partie complète
- environ 10^58 parties possibles
- environ 10^28 positions de plateau possibles
- Cette échelle est présentée comme bien plus grande que celle des jeux difficiles résolus jusqu’ici, en particulier le checkers
- En raison de cet immense espace de recherche, Othello était resté un défi de longue date en informatique
Méthode de recherche et efficacité de calcul
- Les chercheurs ont utilisé une alpha-beta search avec pour objectif une résolution faible
- Les algorithmes de résolution de jeux varient selon l’objectif et la nature du jeu
- pour une résolution faible, l’alpha-beta search est souvent utilisée
- pour une résolution forte, la retrograde analysis est souvent employée
- pour les puzzles ayant des séquences de solution très longues, des approches comme la df-pn search ont été développées
- L’alpha-beta search est un algorithme qui explore séquentiellement le graphe du jeu en profondeur, ce qui signifie qu’une simple parallélisation n’améliore pas facilement l’efficacité de recherche de façon importante
- Différentes approches ont été étudiées pour la recherche parallèle
- dans les environnements à mémoire partagée, YBWC et Lazy SMP sont des méthodes populaires
- dans les environnements à mémoire distribuée, APHID et ABDADA sont présentés comme des algorithmes pertinents
- Dans les environnements à mémoire distribuée, les conditions comme la bande passante entre nœuds et la latence varient fortement, si bien que les développeurs peuvent devoir choisir un algorithme adapté à l’environnement ou en développer un nouveau
- Même avec des clusters informatiques modernes, résoudre Othello restait un obstacle majeur, et la percée a consisté à améliorer l’efficacité de recherche en modifiant les logiciels Othello les plus récents
Autres jeux résolus et possibilités d’usage
- Avant Othello, le cas récent cité parmi les jeux difficiles résolus était le checkers
- Des jeux non triviaux comme Connect Four, Qubic, Go-Moku, Nine Men’s Morris et Awari sont aussi listés comme exemples de jeux résolus
- La difficulté de résolution d’un jeu dépend en général fortement du nombre de positions ou de situations qu’il contient
- Résoudre un jeu ne sert pas seulement à établir son résultat final, mais peut aussi être utilisé pour la génération de puzzles fondés sur ce jeu
- Les chercheurs fournissent les données brutes et les programmes de reproduction sur GitHub, Zenodo et figshare
1 commentaires
Avis sur Hacker News
« Parmi 2 958 551 positions, nous avons choisi 2 587 positions et formulé une hypothèse sur le résultat ; si toutes ces hypothèses sont correctes, cela prouve que la position initiale est une nulle », mais il n’y a pas d’explication plus détaillée
Ça donne plutôt l’impression que le jeu n’a pas été entièrement résolu, mais que l’auteur a cherché très sérieusement une suite gagnante sans en trouver
Il y est dit : « Il existe de nombreuses façons de choisir un sous-ensemble permettant de prouver que la position initiale est une nulle, mais nous avons obtenu un petit sous-ensemble avec l’Algorithm 1 »
L’Algorithm 1 est décrit comme renvoyant un sous-ensemble qui, à partir des scores prédits pour toutes les positions à 50 cases vides, fait que si toutes les positions de ce sous-ensemble sont résolues et que leurs solutions correspondent aux prédictions, alors la position initiale est elle aussi résolue par conséquent
Globalement, la présentation de l’article n’est pas intuitive. L’auteur a peut-être raison, mais il faudrait vraiment s’asseoir et suivre la logique en détail ; à première vue, je reste sceptique
On trouve ce genre de preuve ailleurs. Par exemple, le théorème des quatre couleurs a lui aussi été ramené à un nombre fini de configurations, puis traité par une coloration à la main
Le script de https://github.com/eukaryo/reversi-scripts/blob/main/reversi... joue parfaitement en supposant que l’ensemble est correct. Les autres scripts du dépôt utilisent des données calculées à partir des solutions de positions à 36 cases vides, et ce niveau de calcul semble faisable même sur une machine ordinaire
En gros, la structure paraît consister à consulter une table de moins de 300 Go contenant toutes les positions à 37 à 64 cases vides atteignables depuis la solution faible, et à résoudre les positions à 36 cases vides ou moins avec
-solved’edaxOthello est un bon jeu pour montrer à quel point de simples heuristiques peuvent devenir puissantes
À mesure que la partie avance, il y a des cases sur lesquelles il ne faut absolument pas jouer, et d’autres sur lesquelles il faut au contraire jouer si possible
Rien qu’en implémentant ce genre de règles, on obtient déjà un adversaire tout à fait correct, et il est intéressant de voir à quelle vitesse les gens attribuent de « l’intelligence » à des choses très simples
Il disait avoir opposé une appli utilisant des heuristiques simples de ce type à une autre appli à la stratégie tout aussi simple mais catastrophiquement mauvaise consistant à « retourner le plus de pions possible »
L’algorithme heuristique avait gagné haut la main ; je me souviens d’un score de 60 à 4, voire encore plus sévère
Quand il ne restait plus que 19 cases vides, il résolvait complètement le reste de la partie, ce qui était assez impressionnant
Othello était même présent sur des jeux LCD à 10 dollars fonctionnant avec deux piles AA
Si les jeux vous intéressent, le championnat du monde d’Othello, également populaire parmi les chercheurs en informatique et en intelligence artificielle, se déroule en ce moment à Rome, en Italie
Les parties sont diffusées en direct sur liveothello.com et sur YouTube @WorldOthello
Je me demande si Othello est, comme les dames, un jeu où la plupart des parties de haut niveau se terminent par une nulle
Super
Il y a une quinzaine d’années, j’avais résolu un jeu plus simple auquel je jouais avec mon frère. C’était un jeu africain avec une dizaine de trous de chaque côté du plateau et des pierres dedans
J’ai écrit un moteur alpha-bêta et il a trouvé, pour la variante que nous jouions, une stratégie gagnante systématique complètement absurde. Après ça, je me suis soudain mis à gagner toutes les parties, et mon frère n’a plus jamais voulu jouer avec moi. Un duel typique entre informaticien et optométriste
Il y a beaucoup à apprendre en regardant des Africains âgés jouer au Mancala. Ils jouent extrêmement vite, et cela donne presque une impression de poker, où la triche fait partie du jeu
Si l’on sème les pierres assez vite, on peut sauter un bol ou laisser tomber une pierre de plus pour prendre l’avantage
Je ne suis pas aussi habile et je joue en famille, donc je ne triche pas. Mais cela en fait quand même un jeu très différent. C’est un peu comme la différence entre des dames anglaises jouant lentement au Mahjong en buvant du thé et des joueurs misant de l’argent dans une salle de jeu chinoise
Si l’on gagne trop ou que l’on perd trop, on n’apprécie plus le jeu
En revanche, je ne vois pas bien en quoi le métier d’optométriste est pertinent ici
C’est vraiment sérieux ? Le fait qu’il n’y ait qu’un seul auteur et qu’il soit affilié à une startup de deep learning dont je n’ai jamais entendu parler me paraît un peu étrange
J’imagine que l’article est en cours d’évaluation par les pairs ?
Et Othello n’est pas exactement du niveau de l’hypothèse de Riemann. Il avait été moins étudié, et il restait peut-être encore quelques fruits à portée de main
Othello est l’un des meilleurs jeux à pratiquer avec un jeune enfant.
Les règles sont simples, il y a des motifs à apprendre, et le plaisir de retourner beaucoup de pions à la fois. Surtout, il est tout aussi amusant pour les adultes que pour les enfants.
J’ai pu vraiment m’amuser sans écraser mon enfant de 6 ans, et sans que cela ressemble à un simple jeu de hasard.
https://mancala.fandom.com/wiki/Hus
En théorie, il n’y a pas de hasard, mais en pratique, les réactions en chaîne empêchent de calculer aussi loin.
Le plateau est facile à fabriquer soi-même.
Si vous voulez essayer le jeu, j’ai mis en ligne celui que j’avais créé avec mes enfants : https://jawj.github.io/fliptiles
Le joueur « IA » est très faible.
J’ai appris un nouveau jeu.
L’ordinateur a marqué 33 points, moi 31.
Si vous pensez qu’Othello est trivial, essayez Zebra.
Site web de l’auteur original : http://radagast.se/othello/
Source GitHub : https://github.com/hoshir/zebra
Ce que j’aime dans Othello, c’est la contradiction entre action et territoire.
Au cours de la partie, le fait de jouer un coup à son tour est, dans un certain sens, défavorable pour soi, mais il faut quand même le faire.
Il faut donc occuper l’espace tout en restant petit et à l’intérieur, jusqu’au moment où l’espace devient trop réduit et où il faut reprendre une influence certaine.
Dans le même registre, il existe aussi une façon de jouer parfaitement à Reversi 6x6.
https://mame.github.io/6x6-reversi-oracle/
Source : https://twitter.com/mametter/status/1476379841004183556
Je ne savais pas jusqu’ici que le 8x8 n’avait pas encore été résolu.