Catégories

## d8 cheatsheet

d8 is V8 developer shell1: a powerful JavaScript interpreter and a convenient tool for developing CLI-based utilities.

Useful documentation for d8 include:

Of particular interest:

#### New Worker with inlined script

This undocumented syntax2 allows for spawning a Worker and passing the script parameter directly as a string.

Note that d8 does not support the location construct for passing environment variables to a new worker: instead simply set the variables directly in the code of the worker.

Catégories

## Suites de Cauchy

Cet exercice s’inspire d’une des méthodes classiques de construction des réels à partir des rationels.

Considérons l’ensemble des suites de Cauchy dans $\mathbb{R}$, noté $\mathbf{C}(\mathbb{R})$.

Soit $\equiv_\mathbb{R}$ la relation entre suites de Cauchy définie comme suit:

$$\forall u, v \in \mathbf{C}(\mathbb{R}) \quad u \equiv_\mathbb{R} v \;\stackrel{\text{def}}{\iff}\; \text{lim }u = \text{lim }v$$

(1) Montrer que $\equiv_\mathbb{R}$ est bien définie.

(2) Montrer que $\equiv_\mathbb{R}$ est une relation d’équivalence.

(3) Trouver une formulation de $\equiv_\mathbb{R}$ qui ne fasse pas intervenir explicitement de nombre réel (c’est à dire par exemple qui ne fasse pas référence à la limite des suites $u$ et $v$).

(4) Utiliser la formulation trouvée au (3) pour définir une relation d’équivalence $\equiv_\mathbb{Q}$ similaire à $\equiv_\mathbb{R}$, mais pour l’ensemble $\mathbf{C}(\mathbb{Q})$ des suites de Cauchy dans $\mathbb{Q}$.

(5) Construire une bijection entre l’ensemble des réels $\mathbb{R}$ et le quotien des suites de Cauchy $\mathbf{C}(\mathbb{Q})$ par la relation $\equiv_\mathbb{Q}$.

$\Box$

### Indices

La question (3) est difficile. Deux mots indice:

1. Entrelacement
2. Différence

### Indices++

1. Si $u$ et $v$ sont deux suites de Cauchy, considérer la suite w définie comme suit: $$\forall n\in\mathbb{N}, w_{2n}= u_n\text{ et }w_{2n+1}=v_n$$
2. Si $u$ et $v$ sont deux suites de Cauchy à valeurs dans $\mathbb{Q}$, $\mathbb{R}$ ou $\mathbb{C}$, considérer la suite w définie comme suit: $$\forall n\in\mathbb{N}, w_n=v_n-u_n$$
Catégories

## RIP David

As Malcolm Harris recalls on his September 9th paper:

I met David Graeber on August 2, 2011, at the first general assembly of Occupy Wall Street. The GA was chaotic, with socialists using a microphone to try to wrangle us anarchists. We wanted something a little less hierarchical, so a handful of us got up and sat in a circle at the other side of the small Wall Street park. Graeber saw us and came over to introduce himself: “Hi, I’m David. Can I sit with you?”

Visit the Anarchist Library to find more about David Graeber’s works.

Catégories

## Zotpress

A useful plugin by Katie Seaborn to manage bibliography for your articles: brings Zotero and scholarly blogging to your WordPress website.

There is a small glitch with version 7.1.5 and WordPress Twenty Twenty theme: the bibliography block is flushed to the left instead of being aligned with the other blocks.

Enjoy this quick hack:

Update: version 7.1.6 provides a clean fix for the problem.

Catégories

## SecretLens

A nice VS Code extension by Fernanco Crespo for managing secrets in a plain text file. Download it:

/!\ Don’t forget to activate the pbkdf2 option for improving the security of your secrets.

Catégories

Catégories

## Hats Calculator (2/3)

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.

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

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

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!

## 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 query1. 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.

Catégories

## Towers of hats (1/3) A towering pillar of hats (number $4$)

This is the first 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, and arose from his work with Tobias Friedrich on

I borrow the introduction from :

Two players each have countably many hats put on their heads.
Each hat is either black or white with equal probability. Furthermore, the players are only able to see the hats on the other person’s head. Simultaneously each player points to a hat on their own head. They win if both players pick out a white hat.

The question is what is the optimal strategy for this game? It should be noted that each individual player will pick a white hat with probability one half regardless of the strategy employed. The challenge then is to correlate their choices.

At a first glance, it may seem that there is no strategy with better than random ($1 \over 4$) chance of winning. This can be quickly discounted by the following simple strategy: each player looks for the first white hat on the partner’s head and chooses the corresponding hat on his or her own head.

Observe that if both players have a white hat first ($1 \over 4$ chance) then they win, if the two first hats are different ( $1 \over 2$ chance) then they lose, and if the two first hats are both black ($1 \over 4$ chance) then effectively they replay the game with the first hat removed. So, we see that the chance of winning is $x = {1 \over 4} + {1 \over 4} \cdot x$, so $x = {1 \over 3}$.

## Finite case

### Definitions and notations

#### Towers

Consider a tower of $n$ stacked hats ($n$ finite), each hat either black or white. We refer to $n$ as the tower’s height. By identifying each hat with a bit (value $0$ for black, $1$ for white), we can view the tower as the binary representation of a natural number, the first hat being the least significant bit.

Let $\mathbb{T}_n$ denote the set of all possible towers:

\begin{align}
\end{align}

where $[n] = \{0, …, n-1\}$ is the set of natural numbers strictly smaller than $n$.

Let $t$ be a tower in $\mathbb{T}_n$.

As an element of $[2^n]$, $t$ is a plain natural number, which provide a convenient way to name it. For instance, $4 \in \mathbb{T}_3$ is the tower consisting of one white hat on top of two black hats.

$$4 \quad = \quad \begin{array}{c} ○\\ ●\\ \end{array}$$

Alternately, as an element of $\{0, 1\}^{[n]}$, $t$ is a map: $[n] \rightarrow \{0, 1\}$. Given a position $p$ in $[n]$, $t(p)$ tells us the color of the hat at position $p$ in the tower ($0$ for black or $1$ for white). $t(p)$ is also the value of the $p$th bit in the binary representation of $t$.

To avoid confusing $t(p)$ (map application) with $t \cdot (p)$ (multiplication of numbers), we write $\overline{(t)}(p)$ (overlined) for the map application. Also, we extend the domain of $\overline{(t)}$ to the set of integers:

\begin{equation}
\forall t \in \mathbb{T}_n, \forall p \in \mathbb{Z}, \quad
\overline{(t)}(p) \;\stackrel{\text{def}}{=}\; (t \gg p) \mathbin{\%} 2,
\end{equation}

(where $\gg$ is the bitwise right shift operator and $\mathbin{\%}$ the remainder operator).

##### Example

\begin{align*}
\overline{(4)}(-1) &= 0 \\
\overline{(4)}(0) &= 0 \\
\overline{(4)}(1) &= 0 \\
\overline{(4)}(2) &= 1 \\
\overline{(4)}(3) &= 0
\end{align*}

#### Strategies

A (deterministic) strategy $s$ for the game of $n$ hats is a way for each player, when presented with the tower of hats on top of their partner’s head, of choosing the position of a (hopefully white) hat on their own head. In other words: $s$ is a map from $\mathbb{T}_n$ to $\mathbb{Z}$.

Note that we allow a strategy to choose a position outside of the tower ($\ge n$ or $< 0$).

Let $\mathbb{S}_n = \mathbb{Z}^{\mathbb{T}_n}$ denote the set of all possible strategies for towers of $n$ hats:

\begin{equation}
\mathbb{S}_n \; \stackrel{\text{def}}{=} \; \mathbb{Z}^{\mathbb{T}_n}.
\end{equation}

A natural way to name a strategy is to use a $2^n$-uple for enumerating the choices it makes.

For instance if $s \in \mathbb{S}_2$ is such that:

$$\left\{ \begin{array}{ll} s\left(\begin{array}{c} ●\\ \end{array}\right) = s(0) = 0,\\ s\left(\begin{array}{c} ●\\ \end{array}\right) = s(1) = 0,\\ s\left(\begin{array}{c} ○\\ \end{array}\right) = s(2) = 1,\\ s\left(\begin{array}{c} ○\\ \end{array}\right) = s(3) = 0, \end{array} \right.$$

then we write:

$$s = (0,0,1,0).$$

When there is no ambiguity (e.g.: all positions are single digit), we shorten the notation:

$$s = .$$

And for clarity, when $n$ gets too big, we use hyphens to separate groups of digits, e.g.: write $[0100 \text{-} 2123 \text{-} 0100 \text{-} 2120]$ for $ \in \mathbb{S}_4$.

##### Hit score

A configuration for the game of $n$ hats is a pair of towers $t$ and $u$ in $\mathbb{T}_n$: one for each player’s head. Given a strategy $s$ in $\mathbb{S}_n$, we denote by $\eta_{t,u}(s)$ the outcome of applying strategy $s$ in the configuration $(t, u)$: $1$ for hit (win), $0$ for miss (loss).

\begin{equation}
\eta_{t,u}(s) \; \stackrel{\text{def}}{=} \; \overline{(t)}\big(s(u)\big) \cdot \overline{(u)}\big(s(t)\big)
\end{equation}

We call hit score of $s$, denoted by $\eta(s)$, the sum of all such outcomes, i.e. the count of all game configurations where the team wins.:

\begin{equation}
\eta(s) \; \stackrel{\text{def}}{=} \; \sum_{t,u \in \mathbb{T}_n}\eta_{t,u}(s)
\end{equation}

##### Win rate

Given a strategy $s$ in $\mathbb{S}_n$, we denote by $\mu(s)$ the win rate (or measure) of $s$, i.e. the probability that a team applying the strategy wins.

\begin{equation}
\mu(s) \; \stackrel{\text{def}}{=} \; {1 \over{4^n}} \cdot \eta(s)
\end{equation}

##### Equivalence

We call two strategies $a$ and $b$ in $\mathbb{S}_n$ equivalent, when they agree on the winning configurations:

\begin{equation}
a \equiv b \; \stackrel{\text{def}}{\iff} \; \forall t,u \in \mathbb{T}_n, \eta_{t,u}(a) = \eta_{t,u}(b).
\end{equation}

Note that two strategies $a$ and $b$ in $\mathbb{S}_n$ which differ only in the choice of $a(0) \neq b(0)$ are equivalent. This is because they make different choices only when one of the players is presented with tower $0$ (all black hats), which is always a losing situation for the team.

\begin{equation}
\big(\forall t \in \mathbb{T}_n \setminus \{0\}, \;\; a(t) = b(t)\big) \quad \implies \quad a \equiv b.
\end{equation}

Of course, equivalent strategies have the same hit score and win rate:

\begin{equation}
\forall a, b \in \mathbb{S}_n, \quad a \equiv b \implies \eta(a) = \eta(b).
\label{EquivRate}
\end{equation}

### Examples of strategies

#### Constant strategies

We call constant a strategy $s \in \mathbb{S}_n$ which always chooses the same position:

$$s \text{ constant } \;\stackrel{\text{def}}{\iff}\; \forall t, u \in \mathbb{T}_n, \; s(t) = s(u)$$

Observe:

• all constant strategies of height $0$ are equivalent,
• a constant strategy which chooses position $p \not\in [n]$ has hit score and win rate $0$,
• a constant strategy of height $>0$ which chooses position $p \in [n]$ has hit score $4^{n-1}$ and win rate of $1 \over 4$.

In particular, we denote by $\mathbf{T}_n$ (top $n$) the strategy in $\mathbb{S}_n$ which chooses position $n-1$ (i.e. the top position in the tower, when the tower is not empty).

\begin{equation}
\forall t \in \mathbb{T}_n, \quad \mathbf{T}_n(t) \stackrel{\text{def}}{=} n-1
\end{equation}

#### Lowest-white strategies

We denote by $\mathbf{W}_n$ (white n) the strategy in $\mathbb{S}_n$ which chooses the position of the lowest white hat, or $n-1$ if there is no white hat.

##### Example

$\mathbf{W}_2 = $ chooses position $1$ when the first hat is black, position $0$ otherwise.

$\mathbf{W}_2$ has hit score $5$ and win rate $5 \over 16$.

#### Lowest-black strategies

We denote by $\mathbf{B}_n$ (black n) the strategy in $\mathbb{S}_n$ which chooses the position of the lowest black hat, or $n-1$ if there is no black hat.

##### Example

$\mathbf{B}_3 = $ chooses position $2$ when the lowest two hats are white, otherwise position $1$ when the lowest hat is white, otherwise position $0$.

$\mathbf{B}_3$ has hit score $21$ and win rate $21 \over 64$.

### Operations on strategies

#### Embedding

Given a strategy $s$ in $\mathbb{S}_n$ and an integer $m > n$, we can use $s$ to play the game of $m$ hats. Simply: do not »looking » at the hats above position $n$ ($n$ included). This defines an embedding $e_m: \mathbb{S}_n \rightarrow \mathbb{S}_m$:

\begin{align*}
e_m: \mathbb{S}_n \rightarrow \mathbb{S}_m\\
s \mapsto e_m(s)
\end{align*}

\begin{equation}
\forall t \in \mathbb{T}_n, \;\; \big(e_m(s)\big)(t) \stackrel{\text{def}}{=} s(t \mathbin{\%} 2^n)
\end{equation}

(where $\mathbin{\%}$ is the remainder operator).

Win rate is invariant under embedding into $\mathbb{S}_m$:

\begin{equation}
\forall s \in \mathbb{S}_n, \forall m > n, \;\; \mu(s) = \mu(e_m(s))
\end{equation}

#### Left reset

Given two strategies $a \in \mathbb{S}_m$ and $b \in \mathbb{S}_n$, we call « $a$ left-reset by $b$ », denoted by $LR(a,b)$, the following strategy in $\mathbb{S}_{m+n}$: whenever the lowest $m$ hats in the tower are not all black, use strategy $a$; otherwise, use strategy $b$ on the remaining $n$ hats. Formally:

\begin{align}
LR(a,b): \; & \mathbb{T}_{m+n} \rightarrow [m+n] \nonumber \\
\nonumber \\
& t \stackrel{\text{def}}{\mapsto}
\left\{
\begin{array}{l}
a(t) \quad\text{if } t \not \equiv 0 \bmod 2^m\\
m + b(t \gg m) \quad\text{otherwise}
\end{array}
\right.
\end{align}

(where $\gg$ is the bitwise right shift operator).

Left reset is associative:

$$\forall a, b, c, \quad LR(a, LR(b, c)) \,=\, LR(LR(a, b), c)$$

so we make it into a binary operator:

\begin{equation}
b \rightarrow a \;\stackrel{\text{def}}{=}\; LR(a, b),
\end{equation}

and the following holds:

\begin{equation}
\forall a, b, c, \;\; (c \rightarrow b) \rightarrow a \,=\, c \rightarrow (b \rightarrow a) \,=\, c \rightarrow b \rightarrow a
\end{equation}

#### Right reset

Given two strategies $a \in \mathbb{S}_m$ and $b \in \mathbb{S}_n$, we call « $a$ right-reset by $b$ », denoted by $RR(a,b)$, the following strategy in $\mathbb{S}_{m+n}$: whenever the lowest $m$ hats in the tower are not all white, use strategy $a$; otherwise, use strategy $b$ on the remaining $n$ hats. Formally:

\begin{align}
RR(a,b): \; & \mathbb{T}_{m+n} \rightarrow [m+n] \nonumber \\
\nonumber \\
& t \stackrel{\text{def}}{\mapsto}
\left\{
\begin{array}{l}
a(t) \quad \text{if } t \not\equiv -1 \bmod 2^m\\
m + b(t \gg m) \quad \text{otherwise,}
\end{array}
\right.
\end{align}

where $\gg$ is the bitwise right shift operator.

Right reset is associative:

$$\forall a, b, c, \;\; RR(a, RR(b, c)) \,=\, RR(RR(a, b), c)$$

so we make it into a binary operator:

\begin{equation}
a \leftarrow b \;\stackrel{\text{def}}{=}\; RR(a, b),
\end{equation}

and the following holds:

\begin{equation}
\forall a, b, c, \;\; (a \leftarrow b) \leftarrow c \,=\, a \leftarrow (b \leftarrow c) \,=\, a \leftarrow b \leftarrow c
\end{equation}

#### Double reset

Given two strategies $a \in \mathbb{S}_m$ and $b \in \mathbb{S}_n$, we call « $a$ double-reset by $b$ », denoted by $DR(a, b)$, the following strategy in $\mathbb{S}_{m+n}$: whenever the lowest $m$ hats in the tower are not all black and not all white, use strategy $a$; otherwise, use strategy $b$ on the remaining $n$ hats. Formally:

\begin{align}
DR(a,b): \; & \mathbb{T}_{m+n} \rightarrow [m+n] \nonumber \\
\nonumber \\
& t \stackrel{\text{def}}{\mapsto}
\left\{
\begin{array}{l}
a(t) \quad \text{if } t \not\equiv 0 \text{ and } t \not\equiv -1 \bmod 2^m \\
m + b(t \gg m) \quad \text{otherwise,}
\end{array}
\right.
\end{align}

where $\gg$ is the bitwise right shift operator.

Double-reset is not associative.

#### Left shift

Given a strategie $s \in \mathbb{S}_n$, we call « $s$ left-shifted« , denoted by $\uparrow\!s$, the following strategy in $\mathbb{S}_{n+1}$:

\begin{equation}
\forall t \in \mathbb{T}_{n+1}, \quad (\uparrow\!s)(t) \stackrel{\text{def}}{=}
\left\{
\begin{array}{ll}
n & \text{if } t = 2^n\\
s(t \mathbin{\%} 2^n) & \text{otherwise,}
\end{array}
\right.
\end{equation}

where $\mathbin{\%}$ is the remainder operator.

#### Right shift

Given a strategie $s \in \mathbb{S}_n$, we call « $s$ right-shifted« , denoted by $s\!\uparrow$, the following strategy in $\mathbb{S}_{n+1}$:

\begin{equation}
\forall t \in \mathbb{T}_{n+1}, \quad (s\!\uparrow)(t) \stackrel{\text{def}}{=}
\left\{
\begin{array}{ll}
n & \text{if } t = 2^n – 1\\
s(t \mathbin{\%} 2^n) & \text{otherwise,}
\end{array}
\right.
\end{equation}

where $\mathbin{\%}$ is the remainder operator.

#### Double shift

Given a strategie $s \in \mathbb{S}_n$, we call « $s$ double-shifted« , denoted by $s\!\Uparrow$, the following strategy in $\mathbb{S}_{n+2}$:

\begin{equation}
\forall t \in \mathbb{T}_{n+2}, \quad (s\!\Uparrow)(t) \stackrel{\text{def}}{=}
\left\{
\begin{array}{ll}
n+1 & \text{if } t = 2^{n+1} + 2^n\\
\big(\uparrow\!(s\!\uparrow)\big)(t) & \text{otherwise.}
\end{array}
\right.
\end{equation}

### Win rate computation

Brute-force computing the win rate would be expensive for large values of $n$. In the remainder of this section, we give simple formulae for calculating the win rate of certain strategies.

#### Observations

Let $a$ be a strategy in $\mathbb{S}_n$. Recall that the hit score of $a$ is $\eta(a) = \sum_{t,u \in \mathbb{T}_n}\eta_{t,u}(a)$, where $\eta_{t,u}(a)$ denotes $\overline{(t)}(a(u)) \cdot \overline{(u)}(a(t))$.

Let $\sum\mathcal{M}$ denote the sum of all coefficients of matrix $\mathcal{M}$.

Then $\eta(a)$ can be written as:

\begin{align*}
\sum
\begin{pmatrix}
\big(\eta_{0,0}(a) & \eta_{0,1}(a) & \cdots & \eta_{0,2^n-2}(a) & \eta_{0,2^n-1}(a) \\
\big(\eta_{1,0}(a) & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \eta_{1,2^n-1}(a) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\big(\eta_{2^n-2,0}(a) & \eta_{2^n-2,1}(a) & \cdots & \eta_{2^n-2,2^n-2}(a) & \eta_{2^n-2,2^n-1}(a) \\
\big(\eta_{2^n-1,0}(a) & \eta_{2^n-1,1}(a) & \cdots & \eta_{2^n-1,2^n-2}(a) & \eta_{2^n-1,2^n-1}(a)
\end{pmatrix}
\end{align*}

Which simplifies to:

\begin{equation}
\sum
\begin{pmatrix}
0 & 0 & \cdots & 0 & 0 \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \eta_{1,2^n-1}(a) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & \eta_{2^n-2,2^n-1}(a) \\
\cdot & \cdot & \cdots & \cdot & \eta_{2^n-1,2^n-1}(a)
\end{pmatrix}
\end{equation}

Which when $a \in [n]^{\mathbb{T}_n}$ further simplifies to:

\begin{equation}
\!\!\!\!\!\!\!\!\!\!\!\!\sum
\begin{pmatrix}
0 & 0 & \cdots & 0 & 0 \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \overline{(1)}\big(a(2^n-1)\big) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & \overline{(2^n-2)}\big(a(2^n-1)\big) \\
\cdot & \cdot & \cdots & \cdot & 1
\end{pmatrix}
\end{equation}

Note that:

• these matrices are symmetric
• the coefficients of the first line add up to $0$
• the coefficients of the last column add up to:

$\quad\quad \left\{ \begin{array}{ll} 2^{n-1} & \text{when } a(2^m-1) \in [n]\\ 0 & \text{otherwise} \end{array} \right.$

Consequence: two strategies $a$ and $b$ in $[n]^{\mathbb{T}_n}$ which differ only in the choice of $a(2^n-1) \neq b(2^n-1)$ have the same hit score and win rate:

\begin{equation}
\big(\forall t \in \mathbb{T}_n \setminus \{2^n-1\}, \;\; a(t) = b(t)\big) \;\; \implies \;\; \eta(a) = \eta(b).
\label{SameRate}
\end{equation}

#### Win rate after left reset

Let $a \in \mathbb{S}_n, b \in \mathbb{S}_m$:

\begin{equation}
\mu(b \rightarrow a) = \mu(a) + {\mu(b) \over 4^n}
\label{LeftResetRule}
\end{equation}

Proof:

\begin{align*}
& {\eta(b \rightarrow a) \over 4^m} \\

& \;\;=\;\; \sum
\begin{pmatrix}
\mu(b) & 0 & \cdots & 0 & 0 \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & \eta_{1,2^n-1}(a) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & \eta_{2^n-2,2^n-1}(a) \\
\cdot & \cdot & \cdots & \cdot & \eta_{2^n-1,2^n-1}(a)
\end{pmatrix} \\

& \;\;=\;\; \eta(a) + \mu(b) \\

& \;\;=\;\; 4^n \cdot \left(\mu(a) + {\mu(b) \over 4^n}\right) \quad \Box
\end{align*}

#### Win rate after right reset

This formula works for strategies which choose positions within the tower.

Let $a \in \mathbb{S}_n, b \in \mathbb{S}_m$:

\begin{equation}
\left\{
\begin{array}{l}
a \in [n]^{\mathbb{T}_n} \\
b \in [m]^{\mathbb{T}_m}
\end{array}
\right. \;\; \implies \;\; \mu(a \leftarrow b) = \mu(a) + {\mu(b) \over 4^n}
\label{RightResetRule}
\end{equation}

Proof:

\begin{align*}
& {\eta(a \leftarrow b) \over 4^m}
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
0 & 0 & \cdots & 0 & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(0))\big) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(1))\big) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(2^n-2))\big) \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
0 & 0 & \cdots & 0 & {1 \over 4^m} \sum_{u\in\mathbb{T}_m}\sum_{t\in\mathbb{T}_m} \overline{(t)}(b(u)) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 4^m} \sum_{u\in\mathbb{T}_m}\sum_{t\in\mathbb{T}_m} \overline{(t)}(b(u)) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 4^m} \sum_{u\in\mathbb{T}_m}\sum_{t\in\mathbb{T}_m} \overline{(t)}(b(u)) \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix}
\end{align*}

Now since $0 \le b(u) < m, \quad \sum_{t\in\mathbb{T}_m} (\overline{(t)}(b(u)) = 2^{m-1}$.

Hence:

\begin{align*}
{\eta(a \leftarrow b) \over 4^m} \;\;
&= \;\; \sum
\begin{pmatrix}
0 & 0 & \cdots & 0 & {1 \over 2} \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 2} \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 2} \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\

&= \;\; \eta(a) + \mu(b) \\

&= \;\; 4^n \cdot \left(\mu(a) + {\mu(b) \over 4^n}\right) \quad \Box
\end{align*}

#### Win rate after double reset

This formula works for strategies which choose positions within the tower.

Let $a \in \mathbb{S}_n, b \in \mathbb{S}_m$:

\begin{equation}
\left\{
\begin{array}{l}
a \in [n]^{\mathbb{T}_n} \\
b \in [m]^{\mathbb{T}_m}
\end{array}
\right. \;\; \implies \;\;
\mu(DR(a, b)) = \mu(a) + {{4 \mu(b) – 1} \over 4^n}
\label{DoubleResetRule}
\end{equation}

Proof:

\begin{align*}
& {\eta(DR(a, b)) \over 4^m} \\
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
\mu(b) & 0 & \cdots & 0 & \mu(b) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(1))\big) \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 4^m} \sum_{t,u\in\mathbb{T}_m} \big(\overline{(t)}(b(u)) \cdot \overline{(2^n-1)}(a(2^n-2))\big) \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\
\\
& \;\;=\;\; \sum \\
& \begin{pmatrix}
\mu(b) & 0 & \cdots & 0 & \mu(b) \\
\cdot & \eta_{1,1}(a) & \cdots & \eta_{1,2^n-2}(a) & {1 \over 2} \\
\vdots & \vdots & \ddots& \vdots& \vdots \\
\cdot & \cdot & \cdots & \eta_{2^n-2,2^n-2}(a) & {1 \over 2} \\
\cdot & \cdot & \cdots & \cdot & \mu(b)
\end{pmatrix} \\
\\
&= \;\; \eta(a) + 4 \mu(b) – 1 \\
\\
&= \;\; 4^n\left(\mu(a) + {{4 \mu(b) – 1} \over 4^n}\right) \quad \Box
\end{align*}

#### Win rate after left shift

Let $s \in \mathbb{S}_n$:

\begin{equation}
\mu(\uparrow\!s) = \mu(s) + {1 \over 4^{n+1}}
\label{LeftShiftRule}
\end{equation}

Proof:

Note that the strategy $(\uparrow\!s)$ is equivalent to $( \rightarrow s)$.

Hence $(\ref{EquivRate})$ they have the same hit score and win rate. Applying $(\ref{LeftResetRule})$ we get:

\begin{align*}
\mu(\uparrow\!s) \;\;=\;\; \mu( \rightarrow s) \;\;=\;\; \mu(s) + {\mu() \over 4^n} \quad \Box
\end{align*}

#### Win rate after right shift

This formula works for a strategy which chooses positions within the tower.

Let $s \in \mathbb{S}_n$:

\begin{equation}
s \in [n]^{\mathbb{T}_n} \;\;
\implies \;\; \mu(s\!\uparrow) = \mu(s) + {1 \over 4^{n+1}}
\label{RightShiftRule}
\end{equation}

Proof:

Note that the strategies $(s\!\uparrow)$ and $(s \leftarrow )$ make the same choices except when presented with a tower with only white hats.

Hence $(\ref{SameRate})$ they have the same hit score and win rate. Applying $(\ref{RightResetRule})$ we get:

\begin{align*}
\mu(\uparrow\!s) \;\;=\;\; \mu(s \leftarrow ) \;\;=\;\; \mu(s) + {\mu() \over 4^n} \quad \Box
\end{align*}

#### Win rate after double shift

This formula works for a strategy which chooses positions within the tower.

Let $s \in \mathbb{S}_n$:

\begin{equation}
s \in [n]^{\mathbb{T}_n} \;\;
\implies \;\; \mu(s\!\Uparrow) = \mu(s) + {1 \over 4^{n+1}}+ {2 \over 4^{n+2}}
\label{DoubleShiftRule}
\end{equation}

Proof:

Consider $s_1 = \uparrow\!(s\!\uparrow)$ and $s_2 = s\!\Uparrow$:

The only difference between $s_1$ and $s_2$ is the position they choose for tower $k = 2^{n+1} + 2^n$:

$$s_2(k) = n + 1 \neq s(0) = s_1(k)$$

Let’s compare the hit scores. Since the $\eta_{t,u}$ are equal unless $t$ or $u$ equals $k$, we have:

\begin{align}
\eta(s_2) – \eta(s_1) \;\; & =\;\; \sum_{t,u \in \mathbb{T}_{n+2}} \big(\eta_{t,u}(s_2) – \eta_{t,u}(s_1)\big) \nonumber \\

& =\;\; 2 \!\!\sum_{t \in \mathbb{T}_{n+2}, t \neq k}\!\!
\big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \label{PartialDoubleShift}\\
& \;\;\;\;\;\; + \big(\eta_{k,k}(s_2)\big)^2. \nonumber
\end{align}

Now:

\begin{align}
& \sum_{t \in \mathbb{T}_{n+2}, t \neq k}
\big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \nonumber \\

& \quad = \!\!\sum_{t \in \mathbb{T}_{n+2}, t \neq k}\!\!
\big(\overline{(t)}(s_2(k))\cdot\overline{(k)}(s_2(t))
– \overline{(t)}(s_1(k))\cdot\overline{(k)}(s_1(t))\big) \nonumber
\end{align}

Because $k = 2^{n+1} + 2^n$ (all bits null but the two most significant), for the terms in this sum it holds that:

$$\left\{ \begin{array}{l} \overline{(k)}(s_2(t)) \neq 0 \implies s_2(t) \ge n \implies t \in \{2^n-1, 2^{n+1}, 2^{n+1}-1\} \\ \overline{(k)}(s_1(t)) \neq 0 \implies s_1(t) \ge n \implies t \in \{2^n-1, 2^{n+1}, 2^{n+1}-1\} \end{array} \right.$$

Hence:

\begin{align*}
& \sum_{t \in \mathbb{T}_{n+2}, t \neq k}
\big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \\
\\
& \quad = \;\;\; \overline{(2^n-1)}(s_2(k)) \,- \overline{(2^n-1)}(s_1(k)) \\
&\quad \;\;\; + \overline{(2^{n+1})}(s_2(k)) \,- \overline{(2^{n+1})}(s_1(k)) \\
&\quad \;\;\; + \overline{(2^{n+1}-1)}(s_2(k)) \,- \overline{(2^{n+1}-1)}(s_1(k)) \\
\\
& \quad = \;\;\; \overline{(2^n-1)}(n+1) \,- \overline{(2^n-1)}(s(0)) \\
&\quad \;\;\; + \overline{(2^{n+1})}(n+1) \,-\overline{(2^{n+1})}(s(0)) \\
&\quad \;\;\; + \overline{(2^{n+1}-1)}(n+1) \,- \overline{(2^{n+1}-1)}(s(0))
\end{align*}

Finally since $0 \le s(0) < n$:

\begin{align*}
\sum_{t \in \mathbb{T}_{n+2}, t \neq k}
& \big(\eta_{t,k}(s_2) – \eta_{t,k}(s_1)\big) \\
\\
\\
\end{align*}

Going back to $(\ref{PartialDoubleShift})$, we conclude:

\begin{align*}
\eta(s_2) – \eta(s_1) \;\; & =\;\; \big(\eta_{k,k}(s_2)\big)^2 \;\;=\;\; 1 \\
\eta(s\!\Uparrow) \;\; & =\;\; \eta(\uparrow\!(s\!\uparrow)) + 1 \\
& =\;\; \big( 16 \cdot \eta(s) + 4 + 1\big) + 1 \\
& =\;\; 4^{n+2} \cdot \big(\mu(s) + {1 \over 4^{n+1}} + {2 \over 4^{n+2}}\big)
\end{align*}

### Efficient strategies

#### Top strategies

The top strategies are obtained by repeatedly double-resetting the strategy $$:

\begin{align}
\mathbf{T}_0 \;
&\stackrel{\text{def}}{=} \; [-1] \\
\forall n \in \mathbb{N}, \quad \mathbf{T}_{n+1} \;
&\stackrel{\text{def}}{=} \; DR(, \mathbf{T}_n) \nonumber
\end{align}

\begin{align}
\mu(\mathbf{T}_0) &= 0\\
\forall n > 0, \quad \mu(\mathbf{T}_n) &= {1 \over 4}\\
\end{align}

#### Lowest-white strategies

The lowest-white strategies are obtained by repeatedly left-resetting the strategy $$:

\begin{align}
\mathbf{W}_0 \;
&\stackrel{\text{def}}{=} \; [-1] \\
\forall n \in \mathbb{N}, \quad \mathbf{W}_{n+1} \;
&\stackrel{\text{def}}{=} \; \mathbf{W}_n \rightarrow  \nonumber
\end{align}

Applying $(\ref{LeftResetRule})$ we get:

\begin{equation}
\mu(\mathbf{W}_n) = {1 \over 3} \cdot \big(1 – {1 \over 4^n}\big).
\end{equation}

As the height of the towers goes to infinity, the win rate of the lowest-white strategies converges to $1 \over 3$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{W}_n) = {1 \over 3} \approx 33.33\%.
\end{equation}

#### Lowest-black strategies

The lowest-black strategies are obtained by repeatedly right-resetting the strategy $$:

\begin{align}
\mathbf{B}_0 \;
&\stackrel{\text{def}}{=} \; [-1] \\
\forall n \in \mathbb{N}, \quad \mathbf{B}_{n+1} \;
&\stackrel{\text{def}}{=} \;  \leftarrow \mathbf{B}_n \nonumber
\end{align}

Applying $(\ref{RightResetRule})$ we get:

\begin{equation}
\mu(\mathbf{B}_n) = {1 \over 3} \cdot \big(1 – {1 \over 4^n}\big).
\end{equation}

As the height of the towers goes to infinity, the win rate of the lowest-black strategies converges to $1 \over 3$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{B}_n) = {1 \over 3} \approx 33.33\%.
\end{equation}

#### Carter strategies

Carter strategies are defined by repeatedly shifting and double-shifting the strategy $$:

\begin{align}
\end{align}

Applying $(\ref{LeftShiftRule})$ & $(\ref{DoubleShiftRule})$ we get:

\begin{align}
\mu(\mathbf{C}_{2n+1}) \quad &= \quad {7 \over 20} – {1 \over 10 \cdot (16)^n}, \\
\mu(\mathbf{C}_{2n+2}) \quad &= \quad {7 \over 20} – {3 \over 80 \cdot (16)^n}.
\end{align}

As the height of the towers goes to infinity, the win rate of the Carter strategies converges to $7 \over 20$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{C}_n) = {7 \over 20} = 35\%.
\end{equation}

#### Reyes strategies

Reyes strategies are defined by repeatedly double-resetting the Carter strategy $\mathbf{C}_3$:

\begin{align}
\mathbf{R}_1 \;
&\stackrel{\text{def}}{=} \; \mathbf{C}_3 \\
\forall n > 0, \quad \mathbf{R}_{n+1} \;
&\stackrel{\text{def}}{=} \; DR(\mathbf{C}_3, \mathbf{R}_n). \nonumber
\end{align}

Applying $(\ref{DoubleResetRule})$ we get:

\begin{equation}
\mu(\mathbf{R}_n) = {7 \over 20} – {1 \over {10 \cdot (16)^n}}.
\end{equation}

As the height of the towers goes to infinity, the win rate of the Reyes strategies converges to $7 \over 20$:

\begin{equation}
\lim_{n \to \infty}\mu(\mathbf{R}_n) = {7 \over 20} = 35\%.
\end{equation}

## Recap and Whereto?

I came across the game of hats through Numberphile’s . Then Google pointed to the interesting article by Stan Wagon .

Wagon provides a state of the art as of 2014:

• Gives a list of best known symmetric strategies due to Carter and Reyes, up to $n = 8$ (hence the christening of the $\mathbf{C}_n$ and $\mathbf{R}_n$ strategies in this article). Carter and Reyes strategies are proven optimal by brute force for $n < 5$. For $n = 5$ Wagon mentions an indirect proof by Jim Roche and him, further confirmed by a different proof by Rob Pratt. For $n > 5$ we don’t know.
• Mentions a proof by Walter Stromquist that $15\over40$ is an upper bound for the win rate of any symmetric strategy.
• Tells about asymmetric strategies (it is believed that they do not lead to better the win rates than the symmetric strategies).
• Tells about playing the game with more than two players.
• Shows how to leverage the axiom of choice to define a strategy for the game with countably infinitely many hats.

Wagon’s state of the art doesn’t give the explicit value of the Carter strategies beyond $\mathbf{C}_8$, nor does it give a procedural way to construct them. It even asks the question: « What about n = 9 or larger? ». By contrast this article provides an explicit construction of $\mathbf{C}_n$ for all $n > 0$.

In the next article I plan to describe a « hat calculator » which implements the operations defined in this article and lets you play with strategies. It also implements an efficient brute-force algorithm to look for optimal strategies (other than Carter’s).

Catégories

## git filter-repo

Eventually you will commit a huge file to your git repository by mistake. Use git-filter-repo to remedy the situation.

Installation:

Example:

Catégories

## Schizo: a different sudoku solving technique

Over the years, several tips and techniques have been developed to help solve sudoku puzzles with logic rather than brute force. To name a few, sudoku9x9 mentions (among others) hidden single, naked single, x-wing.

## At least one solution

These techniques are all based on a common principle: they work « ad absurdum », by eliminating moves that would lead to an invalid grid: a puzzle with zero solution. For example, the grid below illustrates the hidden single technique:

 2 1 3 2

Number 2 cannot be placed in any of the red cells because this would lead to a grid with no solution. Therefore it must be placed in the green cell, leading to the next step:

 2 1 2 3 2

## At most one solution

Here is a (novel?) technique based on the opposite principle: it works by eliminating a move that would lead to a grid with more than one solution. (By current rules, well formed sudoku puzzles must have a single solution.)

The grid below illustrates this technique, which we call schizo (as in schizophrenia):

 3 6 1 2 2 5 1 48 478 9 3 6 6 3 2 478 5 1 9 2 48 48 7 1 7 1 9 5 3 6 2 8 4 1 9 2 4 2 7 1 3 5 1 9 5 8 2 5 6 2 4 1

Number 7 cannot be placed in the red cell because this would eventually lead to two equally valid solutions:

 3 6 1 2 2 5 1 4 8 9 3 6 6 3 2 7 5 1 9 2 8 4 7 1 7 1 9 5 3 6 2 8 4 1 9 2 4 2 7 1 3 5 1 9 5 8 2 5 6 2 4 1
 3 6 1 2 2 5 1 8 4 9 3 6 6 3 2 7 5 1 9 2 4 8 7 1 7 1 9 5 3 6 2 8 4 1 9 2 4 2 7 1 3 5 1 9 5 8 2 5 6 2 4 1

Therefore 7 must be placed in the green cell, leading to the next step:

 3 6 1 2 2 5 1 48 7 9 3 6 6 3 2 48 5 1 9 2 48 48 7 1 7 1 9 5 3 6 2 8 4 1 9 2 4 2 7 1 3 5 1 9 5 8 2 5 6 2 4 1

$\Box$