La théorie des jeux frappe encore
Une équipe de chercheurs en informatique de l'Université de l'Alberta vient de foutre mon après-midi en l'air.
Vous connaissez les dames? (Je parle bien sûr de ce jeu que vous vous êtes empressés d'oublier le jour où vous avez appris à jouer aux échecs.) Éh bien, figurez-vous que les dames ont été « craquées », pour utiliser un terme cher aux ti-culs qui essaient de voler votre numéro de carte de crédit sur Internet. Non contents d'avoir créé un logiciel de jeu de dames plutôt fortiche il y a une quinzaine d'années, puis de l'avoir perfectionné au point de le rendre pratiquement imbattable vers le milieu des années 90, ces authentiques geeks d'Edmonton ont finalement publié dans le dernier Science un papier dans lequel ils présentent les résultats de leurs travaux. Pour résumer, Chinook, leur fameux logiciel, est maintenant techniquement invincible. Le plaisir durait depuis quatre siècles, ça devait bien se terminer un jour.
Il faut dire que les dames, à l'instar du morpion (je ne vous cacherai pas que j'ai toujours appelé ça le tic tac toe, en anglois, parce que franchement, morpion, ouache), sont un jeu passablement limité, avec quelques règles simples et un ensemble restreint de mouvements possibles. L'extrême simplicité du morpion (765 états possibles) fait qu'il y a déjà un bon bout de temps que l'algorithme représentant la stratégie parfaite est connu et que l'humain ne peut plus battre l'ordinateur — depuis 1952, un joueur « parfait » doit se contenter d'un match nul. Les dames n'étant que marginalement plus complexes, avec à peu près cinq cent trillions d'états possibles, ce n'était qu'une question de temps avant qu'un logiciel puisse connaître toutes les possibilités et choisir la meilleure stratégie à chaque coup.
Personnellement, même si ça faisait à peu près vingt-cinq ans que je n'avais pas pensé aux dames avant de tomber sur cet article du New York Times, tout ça me déprime. C'est en quelque sorte tout le domaine des jeux caractérisés par un ensemble discret de solutions, dont les échecs et le go (bientôt craqués sur un ordinateur près de chez vous, n'en doutez pas), qui s'en trouve discrédité. Au bout du compte, les humbles mortels que nous sommes ne pouvons apprécier ces jeux qu'en raison de nos cerveaux limités, de nos intellects dérisoires. C'est un peu humiliant. Même lorsqu'il s'agit de rigoler, nous sommes relégués à l'analogique.
***
Si le coeur vous en dit, faites-vous écrabouiller par Chinook, totalement gratos.
Commentaires
S'il vous plaît, dessinez-moi un mouton...
François, le Lundi 23 juillet 2007 à 22:11 [permalien] :
Un jour, Windows jouera tout seul au démineur ou à la dame de pique au lieu de travailler.
Nic, le Mardi 24 juillet 2007 à 08:57 [permalien] :
Wikipedia: "Go (is)solved for board sizes up to 4×4. The 5×5 board is weakly solved for all opening moves."
(www.cs.unimaas.nl/~vander... )
Ça me fait penser à ce concours qui consistait à découvrir un message encrypté en 56 bits. Le message était : "It's time for those 128-, 192-, and 256-bit keys."
Peut-être que la résolution progressive des échecs et du go nous forcera à trouver des jeux encore plus difficiles -- voire des jeux qui implique une vision différente de la complexité, de l'intelligence et de la victoire.
(Ou, plus probablement, nous y verrons la preuve supplémentaire que les mathématiciens dirigent le monde.)
JP, le Mardi 24 juillet 2007 à 10:58 [permalien] :
C'est Bobby Fischer qui avait suggéré de tirer au sort les positions initiales des pièces du jeu d'échecs ?
Hugo, le Mardi 24 juillet 2007 à 11:33 [permalien] :
C'est vrai qu'on peut voir un lien entre la cryptographie et les jeux de damier, dans la mesure où leur insolubilité repose sur la puissance -- ou plutôt l'impuissance -- de calcul des participants. Les humains trouvent les échecs et le go intéressants parce qu'ils sont incapables de calculer plus de quelques coups possibles à l'avance, ce qui crée l'illusion de l'indétermination. Or, c'est l'indétermination qui divertit.
Il est encore possible de s'amuser en jouant aux échecs ou au go contre un ordinateur parce que celui-ci, pour l'instant, doit se contenter d'utiliser les mêmes stratégies (heuristique) que l'humain, en n'ayant que l'avantage de pouvoir calculer un certain nombre de coups à l'avance. Tout n'est pas encore déterminé. Ainsi, il est encore possible qu'il fasse sinon des erreurs, du moins des choix non optimaux. Dans ce contexte, un joueur "parfait" (c'est-à-dire un joueur qui applique avec rigueur les stratégies gagnantes) a de bonnes chances d'avoir le dessus sur la machine.
Ceci étant dit, j'étais un peu déprimé, hier, je crois. Au bout du compte, cette sorte de course à l'armement des jeux de damier n'est pas une mauvaise chose : lorsque tous les jeux auront été craqués, les Chinook et autres Deep Blue seront envoyés à la retraite. Il n'y a pas beaucoup de plaisir, même intellectuel, à observer deux ordinateurs faire match nul à l'infini. Les humains pourront alors continuer leurs dérisoires petits affrontements indéterminés bien paisiblement, en sirotant un verre de vin et en s'entretraitant poliment de salauds.
Au fond, vive l'analogique.
Nic, le Mardi 24 juillet 2007 à 14:18 [permalien] :
Luddite, va.
Mo, le Mercredi 25 juillet 2007 à 08:33 [permalien] :
C'est drôle que ça t'atteigne ! Tant qu'à choisir un sujet d'angoisse dans l'actualité, je préfère personnellement les algues bleues.
Hugo, le Mercredi 25 juillet 2007 à 14:23 [permalien] :
Mo : Boaf, quand je suis fatigué et dans le jus, j'ai tendance à perdre un peu l'actualité de vue, à devenir insensible aux drames planétaires. Je lis les grands titres en diagonale et rien ne m'interpelle. Quoique les maudites algues bleues...
Nic : Même quand on s'éloigne des jeux à information parfaite (comme les échecs ou le go) et qu'on s'aventure dans le domaine plus "organique" des jeux à composante psychologique, les ordinateurs prétendent encore régner. En fin de semaine, il va y avoir un affrontement entre un logiciel de poker et deux des meilleurs joueurs de poker au monde : www.expressnews.ualberta....
Nic encore : Luddite, moi? Et qui c'est qui gueulait contre les cyclocomputeurs récemment? :)
Il n'y a aucun trackback pour le moment.
Ajouter un commentaire
Les commentaires pour ce billet sont fermés.
Les trackbacks pour ce billet sont fermés.
« En petits morceaux » est un projet Takefu qui sent le bambou. Certains droits sont réservés.