{"id":1893,"date":"2020-09-05T17:12:17","date_gmt":"2020-09-05T17:12:17","guid":{"rendered":"http:\/\/blog.atlant.is\/?p=1893"},"modified":"2021-06-12T09:05:40","modified_gmt":"2021-06-12T07:05:40","slug":"hats-calculator","status":"publish","type":"post","link":"https:\/\/blog.douzeb.is\/?p=1893","title":{"rendered":"Hats Calculator (2\/3)"},"content":{"rendered":"\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img decoding=\"async\" loading=\"lazy\" width=\"495\" height=\"577\" src=\"http:\/\/blog.atlant.is\/wp-content\/uploads\/2020\/09\/hats-medic.png\" alt=\"The hats medic\" class=\"wp-image-1882\" srcset=\"https:\/\/blog.douzeb.is\/wp-content\/uploads\/2020\/09\/hats-medic.png 495w, https:\/\/blog.douzeb.is\/wp-content\/uploads\/2020\/09\/hats-medic-257x300.png 257w\" sizes=\"(max-width: 495px) 100vw, 495px\" \/><figcaption>The hats medic<\/figcaption><\/figure><\/div>\n\n\n\n<p>This is the second in a series of three <em>exercices de style<\/em> to show some interesting aspects of the <em>game of hats<\/em>: a puzzle which was initially proposed by Lionel Levine.<\/p>\n\n\n\n<ul><li><a href=\"https:\/\/blog.atlant.is\/?p=1183\">First exercice<\/a><\/li><li><a href=\"https:\/\/blog.atlant.is\/?p=1893\">Second exercice<\/a><\/li><li><a href=\"https:\/\/blog.atlant.is\/?p=2817\">Third exercice<\/a><\/li><\/ul>\n\n\n\n<p>Here we introduce the <em>hats calculator<\/em>: a toy application which implements the operations introduced <a href=\"https:\/\/blog.atlant.is\/?p=1183#Operations_on_strategies\">in the first exercice<\/a>.<\/p>\n\n\n\n<h2>Try it yourself<\/h2>\n\n\n\n<iframe id=\"auto-iframe\" name=\"auto-iframe\" src=\"https:\/\/douzebis.github.io\/hats\/hats.html\" width=\"100%\" height=\"330\" frameborder=\"0\" scrolling=\"yes\"><\/iframe>\n\n\n\n<!--more-->\n\n\n\n\n\n<h2>Installing the hats calculator<\/h2>\n\n\n\n<p>The hats calculator is a single file JavaScript application.<\/p>\n\n\n\n<p>Clone it from the <a href=\"https:\/\/github.com\/fredatatlantis\/hats\">repository on GitHub<\/a>:<\/p>\n\n\n\n<pre style=\"font-size:15px !important;\" class=\"command-line\" data-prompt=\"$\"><code class=\"language-bash\"><!--git clone git@github.com:douzebis\/hats.git\ncd hats--><\/code><\/pre>\n\n\n\n<p>Use the <a href=\"https:\/\/v8.dev\/docs\/d8\">D8 JavaScript shell<\/a> to run in from the terminal.<\/p>\n\n\n\n<h2>Evaluating strategies<\/h2>\n\n\n\n<p>The syntax for evaluating strategy expressions is as follows:<\/p>\n\n\n\n<pre style=\"font-size:15px !important;\" class=\"command-line\" data-prompt=\"$\"><code class=\"language-bash\"><!--d8 hats.js -- eval '<expr>'--><\/code><\/pre>\n\n\n\n<p><code>&lt;expr&gt;<\/code> can be a strategy or a call to an operation on strategies.  Strategies are keyed in as arrays, strings (shortened notation), or using predefined constant names.<\/p>\n\n\n\n<pre style=\"font-size:15px !important;\" class=\"command-line\" data-prompt=\"$\" data-output=\"2,4,6,8\"><code class=\"language-bash\"><!--d8 hats.js -- eval '[0,1,0,0]'\n\"0100\" mu = 5\/16 = 31.25%\nd8 hats.js -- eval '\"0100\"'\n\"0100\" mu = 5\/16 = 31.25%\nd8 hats.js -- eval '[1,1,-1,-1]'\n[1,1,-1,-1] mu = 0\/16 = 0%\nd8 hats.js -- eval 'C3'\n\"01002120\" mu = 22\/64 ~ 34.38%--><\/code><\/pre>\n\n\n\n<p>Predefined constants include:<\/p>\n\n\n\n<ul><li><code>T0<\/code>: Top strategy $\\mathbf{T}_0$<\/li><li><code>W0<\/code>, $\\cdots$, <code>W9<\/code>: Lowest-white strategies $\\mathbf{W}_n$<\/li><li><code>B0<\/code>, $\\cdots$, <code>B9<\/code>: Lowest-black strategies $\\mathbf{B}_n$<\/li><li><code>C1<\/code>, $\\cdots$, <code>C9<\/code>: Carter strategies $\\mathbf{C}_n$<\/li><li><code>R0<\/code>, $\\cdots$, <code>R3<\/code>: Reyes strategies $\\mathbf{R}_n$<\/li><\/ul>\n\n\n\n<p>Available operations include:<\/p>\n\n\n\n<ul><li><code>lr(a, b)<\/code>: <code>a<\/code> left-reset by <code>b<\/code>  ($b \\rightarrow a$)<\/li><li><code>rr(a, b)<\/code>: <code>a<\/code> right-reset by <code>b<\/code>  ($a \\leftarrow b$)<\/li><li><code>dr(a, b)<\/code>: <code>a<\/code> double-reset by <code>b<\/code>  ($DR(a, b)$)<\/li><li><code>ls(a)<\/code>: <code>a<\/code> left-shifted  ($\\uparrow\\!a$)<\/li><li><code>rs(a)<\/code>: <code>a<\/code> right-shifted  ($a\\!\\uparrow$)<\/li><li><code>ds(a)<\/code>: <code>a<\/code> double-shifted  ($a\\!\\Uparrow$)<\/li><li><code>emb(a, n)<\/code>: <code>a<\/code> embedded in $\\mathbb{S}_\\text{n}$  ($e_n(a)$)<\/li><li><code>crush(a)<\/code>: a transform of <code>a<\/code> with the same hit score but such that $\\forall t, \\; a(t) \\le t$.<\/li><\/ul>\n\n\n\n<pre style=\"font-size:15px !important;\" class=\"command-line\" data-prompt=\"$\" data-output=\"2,4,6,8-9\"><code class=\"language-bash\"><!--d8 hats.js -- eval 'dr(dr(W2,W1),W1)'\n\"30122013-30122013\" mu = 80\/256 = 31.25%\nd8 hats.js -- eval 'dr(W2,dr(W1,W1))'\n\"30133013-30133013\" mu = 80\/256 = 31.25%\nd8 hats.js -- eval 'dr(W2,dr(W1,W1))'\n\"30133013-30133013\" mu = 80\/256 = 31.25%\nd8 hats.js -- eval 'dr(ds(W1),ds(W1))'\n\"31002123-41002124--31002123-31002123\n 51002125-41002124--51002125-31002123\" mu = 1432\/4096 ~ 34.96%--><\/code><\/pre>\n\n\n\n<h2>Searching for optimal strategies<\/h2>\n\n\n\n<p>The syntax for searching for optimal strategies is as follows:<\/p>\n\n\n\n<pre style=\"font-size:15px !important;\" class=\"command-line\" data-prompt=\"$\" data-output=\"\"><code class=\"language-bash\"><!--d8 hats.js -- search [-n <num>] [-s <seed>] [-d <distance>] [-a] [-q] [-c]--><\/code><\/pre>\n\n\n\n<ul><li><code>-n<\/code>: specifies the height of the strategies (defaults to $1$)<\/li><li><code>-s<\/code>: limits the search to strategies close to a seed strategy (defaults to the constant zero strategy)<\/li><li><code>-d<\/code>: limits the search to strategies within a specified hamming distance of the seed strategy (defaults $0$ which means no limit)<\/li><li><code>-a<\/code>: displays all occurrences of optimal strategies, not just the first one<\/li><li><code>-q<\/code>: works quietly, displays only a summary line<\/li><li><code>-c<\/code>: don&rsquo;t actually perform the search; instead: prints the optimized JavaScript code which performs the search<\/li><\/ul>\n\n\n\n<pre style=\"font-size:15px !important;\" class=\"command-line\" data-prompt=\"$\" data-output=\"2-4,6-8\"><code class=\"language-bash\"><!--d8 hats.js -- search -n 4 -q\nDone comparing 100\u202f663\u202f296 strategie(s) in 0.818s.\nBest win rate is 89\/256 ~ 34.77% (102 occurrences).\nE.g.: \"00003030-22223130\"\nd8 hats.js -- <\/span>search -n 5 -d 6 -q\nDone comparing 1\u202f876\u202f630\u202f200 strategie(s) in 54s.\nBest win rate is 292\/1024 ~ 28.52% (155 occurrences).\nE.g.: \"00000000-00000000--00004040-40404040\"--><\/code><\/pre>\n\n\n\n<h3>Performance<\/h3>\n\n\n\n<p>Measured on chrome on a MacBook Pro 2015.<\/p>\n\n\n\n<p>For $n = 4$, the search for the optimal strategy takes about $0.8$ second and compares $100\\,663\\,296$ strategies.<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td># of strategies compared<\/td><td>$100\\,663\\,296$<\/td><\/tr><tr><td>Processing time<\/td><td>$0.82$ s<\/td><\/tr><tr><td>Duration per strategy rating<\/td><td>$8.15$ ns<\/td><\/tr><tr><td># of processor cycles per rating<\/td><td>$25$<\/td><\/tr><\/tbody><\/table><figcaption>Search performance for $n = 4$ (chrome on MacBook Pro 2015, 3.1 GHz)<\/figcaption><\/figure>\n\n\n\n<p>For $n = 5$ the search for the optimal strategy would theoretically take $\\approx 113\\,000$ years and would compare $178\\,813\\,934\\,326\\,171\\,875\\,000$ strategies!<\/p>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\"><table><tbody><tr><td># of strategies compared<\/td><td>$178\\,813\\,934\\,326\\,171\\,875\\,000$<\/td><\/tr><tr><td>Processing time<\/td><td>$\\approx 113\\,000$ years<\/td><\/tr><tr><td>Duration per strategy rating<\/td><td>$\\approx20$ ns<\/td><\/tr><tr><td># of processor cycles per rating<\/td><td>$\\approx62$<\/td><\/tr><\/tbody><\/table><figcaption>Search performance for $n = 5$ (chrome on MacBook Pro 2015, 3.1 GHz)<\/figcaption><\/figure>\n\n\n\n<h2>Implementation tips<\/h2>\n\n\n\n<p><code>hats.js<\/code> implements several optimizations to increase the performance of the search.<\/p>\n\n\n\n<ol><li>Uses the fact that the hit score is independent on the choice a strategy makes for a tower all black or all white. For $n = 5$ this decreases the cardinality of the problem by a factor of $25$.<\/li><li>Uses an argument on \u00ab\u00a0positions permutation\u00a0\u00bb which allows to consider only <em>crushed<\/em> strategies (for which $\\forall s, \\; s(t) \\le t$). For $n = 5$ this decreases the cardinality of the problem by an additional factor of $6$.<\/li><li>Computes the hit score incrementally, changing one strategy choice at a time. For $n = 5$ this decreases the execution time by an additional factor of $32$.<\/li><li>Uses a smart representation of strategy choices as bit patterns, which enables a faster computation of the incremental hit score.<\/li><li>Eliminates most loops, indices, and array accesses by automatically generating \u00ab\u00a0unfolded specialized\u00a0\u00bb search code, optimized for each specific search query<span id='easy-footnote-1-1893' class='easy-footnote-margin-adjust'><\/span><span class='easy-footnote'><a href='https:\/\/blog.douzeb.is\/?p=1893#easy-footnote-bottom-1-1893' title='This technique leverages the ability of JavaScript to process &lt;em&gt;self-modifying&lt;\/em&gt; code, for example using the &lt;em&gt;worker&lt;\/em&gt; construct.'><sup>1<\/sup><\/a><\/span>. To have a look at the generated code, try e.g.: <code>search -n 4 -c<\/code> in the <em>Try it yourself<\/em> window.<\/li><li>Tries to keep code and data of the search algorithm as much as possible within the processor cache. (Significant performance decrease is observed with less concise code.)<\/li><\/ol>\n\n\n\n<pre style=\"font-size:15px !important;\"><code class=\"language-js\"><!--\/\/ Compute incremental hit score of choices for tower 3\nfunction x3(H) { \/\/ H is the current hit score\nx4(H);\nlet e = ((s1 + s5 + s7 + s9 + s11 + s13 + s15) << 1) + s3;\nH -= ((e + (e >> 5)) & 31)\ns3 = 32;\ne = ((s2 + s6 + s7 + s10 + s11 + s14 + s15) << 1) + s3;\nx4(H +((e + (e >> 5)) & 31));\ns3 = 1024;\ne = ((s4 + s5 + s6 + s7 + s12 + s13 + s14 + s15) << 1);\nx4(H + ((e + (e >> 5)) & 31));\ns3 = 32768;\ne = ((s8 + s9 + s10 + s11 + s12 + s13 + s14 + s15) << 1);\nx4(H + ((e + (e >> 5)) & 31));\ns3 = 1;\n}--><\/code><\/pre>\n\n\n\n<figcaption role=\"textbox\" aria-multiline=\"true\" aria-label=\"R\u00e9digez la l\u00e9gende\u2026\" class=\"rich-text block-editor-rich-text__editable\" style=\"white-space: pre-wrap;\" contenteditable=\"true\">Automatically generated code pattern for the search algorithm<\/figcaption>\n\n\n\n<p>Unfortunately, these optimization do not make the $114\\,000$ years computation time for $n = 5$ any more accessible. Different methods than brute force are definitely needed.<\/p>\n\n\n\n<h2>What&rsquo;s next<\/h2>\n\n\n\n<p>In the next article I plan to go back to the theory of the game of hats and tackle the problem of playing with infinite towers.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>This is the second in a series of three exercices de style to show some interesting aspects of the game of hats: a puzzle which was initially proposed by Lionel Levine. First exercice Second exercice Third exercice Here we introduce the hats calculator: a toy application which implements the operations introduced in the first exercice. [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":1882,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[23,16,5],"tags":[],"ppma_author":[76],"authors":[{"term_id":76,"user_id":1,"is_guest":0,"slug":"fred","display_name":"Fred","avatar_url":"https:\/\/secure.gravatar.com\/avatar\/ec0326d654fdf9f66e9eb42bb34a9bc4?s=96&d=mm&r=g","description":"","first_name":"","last_name":"","user_url":""}],"_links":{"self":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/1893"}],"collection":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=1893"}],"version-history":[{"count":175,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/1893\/revisions"}],"predecessor-version":[{"id":4130,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/posts\/1893\/revisions\/4130"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=\/wp\/v2\/media\/1882"}],"wp:attachment":[{"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1893"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1893"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1893"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/blog.douzeb.is\/index.php?rest_route=%2Fwp%2Fv2%2Fppma_author&post=1893"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}