Catégorie : Geek

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

Here we introduce the hats calculator: a toy application which implements the operations introduced in the first exercice.

Try it yourself

Installing the hats calculator

The hats calculator is a single file JavaScript application.

Clone it from the repository on GitHub:

Use the D8 JavaScript shell to run in from the terminal.

Evaluating strategies

The syntax for evaluating strategy expressions is as follows:

<expr> 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.

Predefined constants include:

• T0: Top strategy $\mathbf{T}_0$
• W0, $\cdots$, W9: Lowest-white strategies $\mathbf{W}_n$
• B0, $\cdots$, B9: Lowest-black strategies $\mathbf{B}_n$
• C1, $\cdots$, C9: Carter strategies $\mathbf{C}_n$
• R0, $\cdots$, R3: Reyes strategies $\mathbf{R}_n$

Available operations include:

• lr(a, b): a left-reset by b ($b \rightarrow a$)
• rr(a, b): a right-reset by b ($a \leftarrow b$)
• dr(a, b): a double-reset by b ($DR(a, b)$)
• ls(a): a left-shifted ($\uparrow\!a$)
• rs(a): a right-shifted ($a\!\uparrow$)
• ds(a): a double-shifted ($a\!\Uparrow$)
• emb(a, n): a embedded in $\mathbb{S}_\text{n}$ ($e_n(a)$)
• crush(a): a transform of a with the same hit score but such that $\forall t, \; a(t) \le t$.

Searching for optimal strategies

The syntax for searching for optimal strategies is as follows:

• -n: specifies the height of the strategies (defaults to $1$)
• -s: limits the search to strategies close to a seed strategy (defaults to the constant zero strategy)
• -d: limits the search to strategies within a specified hamming distance of the seed strategy (defaults $0$ which means no limit)
• -a: displays all occurrences of optimal strategies, not just the first one
• -q: works quietly, displays only a summary line
• -c: don’t actually perform the search; instead: prints the optimized JavaScript code which performs the search

Performance

Measured on chrome on a MacBook Pro 2015.

For $n = 4$, the search for the optimal strategy takes about $0.8$ second and compares $100\,663\,296$ strategies.

# of strategies compared	$100\,663\,296$
Processing time	$0.82$ s
Duration per strategy rating	$8.15$ ns
# of processor cycles per rating	$25$

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!

# of strategies compared	$178\,813\,934\,326\,171\,875\,000$
Processing time	$\approx 113\,000$ years
Duration per strategy rating	$\approx20$ ns
# of processor cycles per rating	$\approx62$

Implementation tips

hats.js implements several optimizations to increase the performance of the search.

1. 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$.
2. Uses an argument on « positions permutation » which allows to consider only crushed 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$.
3. 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$.
4. Uses a smart representation of strategy choices as bit patterns, which enables a faster computation of the incremental hit score.
5. Eliminates most loops, indices, and array accesses by automatically generating « unfolded specialized » search code, optimized for each specific search query¹. To have a look at the generated code, try e.g.: search -n 4 -c in the Try it yourself window.
6. 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.)

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.

What’s next

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.