{"id":9421,"date":"2022-02-13T16:54:36","date_gmt":"2022-02-13T15:54:36","guid":{"rendered":"https:\/\/scienceetonnante.com\/?p=9421"},"modified":"2022-02-13T16:54:36","modified_gmt":"2022-02-13T15:54:36","slug":"comment-craquer-le-jeu-wordle-sutom","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2022\/02\/13\/comment-craquer-le-jeu-wordle-sutom\/","title":{"rendered":"Comment craquer le jeu WORDLE \/ SUTOM"},"content":{"rendered":"<p>Dans ma derni\u00e8re vid\u00e9o, je me suis amus\u00e9 \u00e0 \u00e9crire un bout de code qui propose une r\u00e9solution automatis\u00e9e des jeux \u00e0 la WORDLE ou SUTOM. Tout \u00e7a m&rsquo;a \u00e9videmment \u00e9t\u00e9 inspir\u00e9 par <a href=\"https:\/\/www.youtube.com\/watch?v=v68zYyaEmEA\" target=\"_blank\" rel=\"noopener\">la formidable vid\u00e9o de 3Blue1Brown<\/a> sur le sujet !<\/p>\n<p><iframe title=\"JE CRAQUE WORDLE ! \ud83d\udfe9\u2b1b\ud83d\udfe8\u2b1b\ud83d\udfe8 (gr\u00e2ce aux maths)\" width=\"770\" height=\"433\" data-src=\"https:\/\/www.youtube.com\/embed\/iw4_7ioHWF4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen src=\"data:image\/svg+xml;base64,PHN2ZyB3aWR0aD0iMSIgaGVpZ2h0PSIxIiB4bWxucz0iaHR0cDovL3d3dy53My5vcmcvMjAwMC9zdmciPjwvc3ZnPg==\" class=\"lazyload\" data-load-mode=\"1\"><\/iframe><\/p>\n<p>J&rsquo;avais promis dans la vid\u00e9o que je partegerai le code, alors le voici avec quelques explications.<\/p>\n<p>Le code est disponible ici : <a href=\"https:\/\/github.com\/scienceetonnante\/WordleSutom\" target=\"_blank\" rel=\"noopener\">https:\/\/github.com\/scienceetonnante\/WordleSutom<\/a><\/p>\n<p>Il n&rsquo;y a vraiment rien de sophistiqu\u00e9 dans l&rsquo;algorithme une fois qu&rsquo;on a compris qu&rsquo;on cherche \u00e0 identifier le coup qui maximise l&rsquo;esp\u00e9rance de l&rsquo;information acquise. Pour faire \u00e7a, on a essentiellement besoin d&rsquo;un ingr\u00e9dient : <strong>une fonction qui d\u00e9termine si un mot peut toujours pr\u00e9tendre \u00eatre la r\u00e9ponse, \u00e9tant donn\u00e9 l&rsquo;\u00e9tat actuel la partie<\/strong>. Au d\u00e9but quand on ne sait rien, tous les mots peuvent pr\u00e9tendre \u00e0 \u00eatre la solution. Au fur et \u00e0 mesure que la partie avance, la liste des suspects se restreint.<\/p>\n<p>Pour faire \u00e7a, on doit mod\u00e9liser d&rsquo;une fa\u00e7on ou d&rsquo;une autre \u00ab\u00a0l&rsquo;\u00e9tat actuel de nos connaissances\u00a0\u00bb. Au d\u00e9but j&rsquo;ai essay\u00e9 de faire un truc subtil en maintenant une liste de lettres vertes, grises et jaunes. Et puis je me suis rendu compte que <strong>\u00e7a n&rsquo;\u00e9tait pas si simple notamment \u00e0 cause de la question des lettres doubles<\/strong>. Si on part du principe qu&rsquo;il peut y avoir des lettres qui apparaissent plusieurs fois, la notion de couleur d&rsquo;une lettre devient d\u00e9pendante du contexte (\u00e0 part pour les vertes). Avec le mot TAPIS, si vous jouez TATIN le premier T sera vert, le second gris. Mais si le mot est TARTE, TATIN donnera un vert et un jaune. Je me suis donc r\u00e9solu \u00e0 ne pas finasser, et pour repr\u00e9senter l&rsquo;\u00e9tat de connaissances, j&rsquo;enregistre b\u00eatement la liste des coups jou\u00e9s et des r\u00e9sultats obtenus.<\/p>\n<p>Pour manipuler les \u00ab\u00a0suites de carr\u00e9s de couleur\u00a0\u00bb, j&rsquo;ai choisi une repr\u00e9sentation num\u00e9rique : 0 pour gris, 1 pour jaune, 2 pour vert. Et ensuite je code un pattern du genre \ud83d\udfe9\ud83d\udfe9\u2b1b\ud83d\udfe8\u2b1b par \u00ab\u00a022010\u00a0\u00bb et donc par le nombre qu&rsquo;il repr\u00e9sente en \u00e9criture ternaire (ici \\(2 + 2.3 + 0.3^2 + 1.3^3 + 0.3^4\\)). Un motif est donc cod\u00e9 par un entier entre 0 et \\(3^K-1\\) o\u00f9 K est le nombre de lettres.<\/p>\n<p>J&rsquo;ai impl\u00e9ment\u00e9 une variante \u00ab\u00a0SUTOM\u00a0\u00bb o\u00f9 la premi\u00e8re lettre est donn\u00e9e. Ca marche bien aussi.<\/p>\n<p>Pour l&rsquo;histoire de \u00ab\u00a0jouer pour acqu\u00e9rir de l&rsquo;information\u00a0\u00bb vs \u00ab\u00a0jouer pour gagner\u00a0\u00bb, j&rsquo;ai fait un choix basique : s&rsquo;il reste moins de 3 possibilit\u00e9s, je tente une des 3. Sinon je cherche le mot qui apporte le plus d&rsquo;informations, m\u00eame s&rsquo;il n&rsquo;est pas dans la liste des candidats.<\/p>\n<p><strong>Pour les performances, j&rsquo;obtiens une moyenne de 3.5 coups sur le WORDLE classique (en fran\u00e7ais). Sur un SUTOM \u00e0 7 lettres (dont la premi\u00e8re est donn\u00e9e), je suis plut\u00f4t autour de 2.6.<\/strong><\/p>\n<p>J&rsquo;ai aussi joint une version \u00ab\u00a0interactive\u00a0\u00bb, o\u00f9 vous pouvez jouer une vraie partie sur WORDLE ou SUTOM en m\u00eame temps. Le code vous sugg\u00e8re un coup, vous entrez ce que le site vous a r\u00e9pondu, et ainsi de suite.<\/p>\n<p>Il y certainement moyen d&rsquo;am\u00e9liorer la rapidit\u00e9 du code. J&rsquo;ai choisi de faire en C++ mais je n&rsquo;ai rien parall\u00e9lis\u00e9, hors il y a moyen car il y a de la boucle imbriqu\u00e9e \u00e0 profusion ! Par exemple pour trouver la meilleure ouverture, on doit examiner 4000 ouvertures, et pour chacun des 243 motifs, il faut voir si chacun des 4000 mots candidats est possible. Ca fait donc \u00ab\u00a04000 x 243 x 4000\u00a0\u00bb it\u00e9rations. Avec 5 lettres,\u00a0la meilleure ouverture WORDLE est trouv\u00e9e en environ 1 minute (une fois connue, \u00e9videmment je l&rsquo;ai mise en dur). Une fois le premier coup pass\u00e9, \u00e7a va tr\u00e8s vite. Il y aurait un int\u00e9r\u00eat \u00e0 tabuler les ouvertures SUTOM pour chacune des 26 lettres.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Dans ma derni\u00e8re vid\u00e9o, je me suis amus\u00e9 \u00e0 \u00e9crire un bout de code qui propose une r\u00e9solution automatis\u00e9e des jeux \u00e0 la WORDLE ou SUTOM. Tout \u00e7a m&rsquo;a \u00e9videmment \u00e9t\u00e9 inspir\u00e9 par la formidable vid\u00e9o de 3Blue1Brown sur le sujet ! J&rsquo;avais promis dans la vid\u00e9o que je partegerai le code, alors le voici<\/p>\n","protected":false},"author":1,"featured_media":9423,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45,4],"tags":[140,127],"class_list":{"0":"post-9421","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-informatique","8":"category-mathematiques","9":"tag-information","10":"tag-jeux"},"jetpack_featured_media_url":"https:\/\/scienceetonnante.com\/blog\/wp-content\/uploads\/2022\/02\/vignette-1.png","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9421","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=9421"}],"version-history":[{"count":2,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9421\/revisions"}],"predecessor-version":[{"id":9424,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/9421\/revisions\/9424"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media\/9423"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=9421"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=9421"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=9421"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}