Catégories

## Infinitely Many Hats (3/3)

This is the last 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 look at case where each player has a tower of countably infinitely many hats on their head and try constructing efficient strategies from the results of the first exercice.

## Definitions and notations

### Towers and strategies

We use notations inspired by .

Let $\mathbb{T}_{<\mathbb{N}}$ denote the set of all towers of finite height and $\mathbb{T}_{\mathbb{N}}$ the set of towers of countably infinite height.

\begin{align}
\mathbb{T}_{<\mathbb{N}}
&\stackrel{\text{def}}{=}\bigcup_{n\in\mathbb{N}} \mathbb{T}_n\\
\mathbb{T}_{\mathbb{N}}
&\stackrel{\text{def}}{=}[2]^{\mathbb{N}}
\end{align}

$\mathbb{T}_{<\mathbb{N}}$ is countable but $\mathbb{T}_{\mathbb{N}}$ has the cardinality of the real line. $\mathbb{T}_{\mathbb{N}}$ is also known as the Cantor space.

Let $\mathbb{S}_{\mathbb{N}}$ denote the set of strategies for the game of hats with towers of countably infinite height. A (symmetric) strategy maps a tower to a chosen position:

\begin{align}
\mathbb{S}_{\mathbb{N}}
&\stackrel{\text{def}}{=}{\mathbb{Z}}^{\mathbb{T}_{\mathbb{N}}}
\end{align}

$\mathbb{S}_{\mathbb{N}}$ has cardinality strictly greater than the real line.

### Hit set and win rate

With infinite towers we can still use $\eta_{t,u}(s)$ to denote the outcome of applying strategy $s\in\mathbb{S}_{\mathbb{N}}$ to the configuration $(t,u)$, however it is no longer possible to calculate the hit score as a sum and the win rate as a mean value.

We substitute with $\eta(s)$, the hit set of strategy $s$:

\eta(s)\stackrel{\text{def}}{=}\{(t,u)\in\mathbb{T}_{\mathbb{N}}\times\mathbb{T}_{\mathbb{N}}\mid\eta_{t,u}(s)=1\},

and write $\mu(s)$ for the win rate of strategy $s$, defined as the Baire/Borel measure of $\eta(s)$ in the space $\mathbb{T}_{\mathbb{N}}\times\mathbb{T}_{\mathbb{N}}$ (when it is measurable).

\mu(s)\stackrel{\text{def}}{=}\mu(\eta(s)).

### Embedding

For convenience we identify the towers in $\mathbb{T}_n$ with towers in $\mathbb{T}_{\mathbb{N}}$ (by completing with black hats) and the strategies in $s\in\mathbb{S}_n$ with strategies in $s\in\mathbb{S}_{\mathbb{N}}$ (by discarding hats at position $n$ and beyond).

Thus we loosely write $s(t)$ and $eta_{t,u}(s)$ even when $s$, $t$ and $u$ are a mix of finite/infinite strategies and towers.

\begin{align}
\forall i<j, \;\;
\left\{
\begin{array}{l}
\mathbb{T}_i
\subset \mathbb{T}_j
\subset \mathbb{T}_{<\mathbb{N}}
\subset \mathbb{T}_{\mathbb{N}}\\
\mathbb{S}_i
\subset \mathbb{S}_j
\subset \mathbb{S}_{\mathbb{N}}\\
\end{array}
\right.
\end{align}

## Limits

### Infinite towers as limits of finite towers

Every tower $t\in\mathbb{T}_{\mathbb{N}}$ is the limit of a sequence of towers in $\mathbb{T}_{<\mathbb{N}}$ (with the topology of the Cantor space).

Proof: if $s\!\mid\!k$ denotes the initial segment of $s$ of size $k\in\mathbb{N}$, then:

s = \lim_{n\to\infty} s\!\mid\!n

In fact, we can view $t\in\mathbb{T}_{\mathbb{N}}$ as the Cauchy completion of $t\in\mathbb{T}_{<\mathbb{N}}$.

### Finite strategies are continuous

A finite strategy $s\in\mathbb{S}_n$, embedded into $\mathbb{S}_{\mathbb{N}}$ as a mapping $s: \mathbb{T}_{\mathbb{N}} \to \mathbb{Z}$, is continuous.

### Limits of strategies

Here we allow strategies as functions $s: \mathbb{T}_{\mathbb{N}} \to \mathbb{Z}$ with partial domain.

Given a sequence $s_n\in\mathbb{S}_{\mathbb{N}}$ we define its pointwise limit:

\begin{align}
\lim (s_n):\; &\big\{t\mid \lim_{n\to\infty} s_n(t)\text{ exists}\big\} \to \mathbb{Z}\\
&\;t \mapsto \lim_{n\to\infty} s_n(t) \nonumber
\end{align}

It is natural to try constructing efficient infinite strategies as limits of finite strategies.

## Infinite lowest-white strategy

Consider the infinite lowest-white strategy $\mathbf{W}_\omega$:

\mathbf{W}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty} \mathbf{W}_n

$\mathbf{W}_\omega$ has win rate $1\over3$.

### Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{W}_n$ strategies as a tree, as shown in the picture below:

Let’s denote in gray the points where the pointwise limit is reached:

We see that $\mathbf{W}_\omega=\lim(\mathbf{W}_n)$ is defined almost everywhere1 with respect to the Baire/Borel measure, and we can squeeze its hit set the following way:

I_k \subset \eta(\mathbf{W}_\omega) \subset S_k

where:

$$\left\{ \begin{array}{l} I_k = \eta(\mathbf{W}_k) \setminus U_k\\ S_k = \eta(\mathbf{W}_k) \cup U_k\\ U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{W}_i(t)\}\neq1 \text{ or card}\bigcup_{i\geq k}\{\mathbf{W}_i(u)\}\neq1\big\} \end{array} \right.$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 1/3$, $\lim_{k\to\infty} \mu(S_k) = 1/3$, hence $\mu(\mathbf{W}_\omega) = 1/3$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{W}_\omega$ is a computable function and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

## Infinite Carter strategy

Consider the infinite Carter strategy $\mathbf{C}_\omega$:

\mathbf{C}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty}
\mathbf{X}_n,

where:

$$\left\{ \begin{array}{l} \mathbf{X}_{2k-1} = \mathbf{C}_k\!\mid\!(2k-1)\\ \mathbf{X}_{2k} = \mathbf{C}_k\!\mid\!(2k) \end{array} \right.$$

$\mathbf{W}_\omega$ has win rate $7\over20$.

### Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{X}_n$ strategies as a tree, as shown in the picture below:

Let’s denote in gray the points where the pointwise limit is reached:

We see that $\mathbf{C}_\omega=\lim(\mathbf{X}_n)$ is defined everywhere, and we can squeeze its hit set the following way:

I_k \subset \eta(\mathbf{C}_\omega) \subset S_k

where:

$$\left\{ \begin{array}{l} I_k = \eta(\mathbf{X}_k) \setminus U_k\\ S_k = \eta(\mathbf{X}_k) \cup U_k\\ U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{X}_i(t)\}\neq1 \text{ or card}\bigcup_{i\geq k}\{\mathbf{X}_i(u)\}\neq1\big\} \end{array} \right.$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 7/20$, $\lim_{k\to\infty} \mu(S_k) = 7/20$, hence $\mu(\mathbf{C}_\omega) = 7/20$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{C}_\omega$ is a computable function almost everywhere2 and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

## Infinite Reyes strategy

Consider the infinite Reyes strategy $\mathbf{R}_\omega$:

\mathbf{R}_\omega \stackrel{\text{def}}{=} \lim_{n\to\infty}
\mathbf{X}_n,

where:

$$\left\{ \begin{array}{ll} \mathbf{X}_{3k-2} &= \mathbf{C}_k\!\mid\!(3k-2)\\ \mathbf{X}_{3k-1} &= \mathbf{C}_k\!\mid\!(3k-1)\\ \mathbf{X}_{3k} &= \mathbf{C}_k\!\mid\!(3k) \end{array} \right.$$

$\mathbf{W}_\omega$ has win rate $7\over20$.

### Proof

Considering all towers in $\mathbb{T}_{\mathbb{N}}$, let’s represent the combined output of the $\mathbf{X}_n$ strategies as a tree, as shown in the picture below:

Let’s denote in gray the points where the pointwise limit is reached:

We see that $\mathbf{R}_\omega=\lim(\mathbf{X}_n)$ is defined almost everywhere3, and we can squeeze its hit set the following way:

I_k \subset \eta(\mathbf{C}_\omega) \subset S_k

where:

$$\left\{ \begin{array}{l} I_k = \eta(\mathbf{X}_k) \setminus U_k\\ S_k = \eta(\mathbf{X}_k) \cup U_k\\ U_k = \big\{(t,u)\mid \text{ card}\bigcup_{i\geq k}\{\mathbf{X}_i(t)\}\neq1 \text{ or card}\bigcup_{i\geq k}\{\mathbf{X}_i(u)\}\neq1\big\} \end{array} \right.$$

$I_k$ is an increasing sequence of sets and $S_k$ is a decreasing sequence, with $\lim_{k\to\infty} \mu(U_k) = 0$, $\lim_{k\to\infty} \mu(I_k) = 7/20$, $\lim_{k\to\infty} \mu(S_k) = 7/20$, hence $\mu(\mathbf{R}_\omega) = 7/20$. $\quad \Box$

Note (as shown in the picture below) that $\mathbf{R}_\omega$ is a computable function on its definition domain and can be written as a finite automaton that processes the stream of hats from $t\in\mathbb{T}_{\mathbb{N}}$:

## References

Kechris, A. S. (2012). Classical descriptive set theory. Springer.
Catégories

## 0! = 1

La fonction factorielle est souvent définie comme le produit : $$n!=\prod_{k=1}^n k\text{,}$$ ou bien par récurrence : $$n!=n\cdot(n-1)!\text{,}$$ en prenant par convention : $0!=1$. Mais pourquoi cette convention ?

Bien sûr c’est assez pratique pour la formule des combinaisons, car ainsi on peut écrire : $$C_n^k=\left(\begin{array}{c}n\\k\end{array}\right)={n!\over k!(n-k)!}$$ même quand $k=n$, et vérifier qu’il y a bien une seule façon de choisir $n$ éléments parmi $n$ 🙂

On peut trouver une explication plus satisfaisante en revenant au sens ensembliste de la factorielle : $n!$ c’est le nombre de permutations d’un ensemble à $n$ éléments, c’est à dire le nombre de bijections possibles entre cet ensemble et lui-même.

Du coup la question devient : quelles sont les bijections entre l’ensemble vide $\emptyset$ et lui-même ? Quel est leur nombre ?

Pour revenir aux bases, une application $f$ d’un ensemble $A$ vers un ensemble $B$ est une relation entre $A$ et $B$ — autrement dit une partie $f\subset A\times B$ — qui vérifie : $$\forall x\in A, \exists! y\in B, (x,y)\in f\text{.}$$ Et dans le cas où $(x,y)\in f$ on écrit : $y=f(x)$.

On observe que $\emptyset\times\emptyset=\emptyset$, que donc $\emptyset$ est la seule partie de $\emptyset\times\emptyset$, et on vérifie que $\forall x\in \emptyset, \exists! y\in \emptyset, (x,y)\in \emptyset$, ce qui démontre que $\emptyset$ est la seule application de $\emptyset$ vers $\emptyset$. On remarque que le domaine de (l’application) $\emptyset$ est vide, et que donc on n’a jamais l’occasion d’écrire $\emptyset(x)=y$.

Pour finir, on constate que (l’application) $\emptyset:\emptyset\to\emptyset$ est à la fois injective (son domaine est vide) et surjective (son ensemble d’arrivée est vide), ce qui démontre que $\emptyset$ est une bijection.

Il est temps de conclure : $\emptyset$ est l’unique bijection entre $\emptyset$ et $\emptyset$…

$0!=1$.$\quad \Box$

Catégories

## Classic 15 Puzzle

15-puzzle by Mark Rohlich

## Genesis

The Fifteen Puzzle consists of fifteen numbered square tiles in a 4×4 square grid, with one position empty or blank. Any tile horizontally or vertically adjacent to the blank can be moved into the blank position. The task is to rearrange the tiles from some random initial configuration into a desired goal configuration, ideally or optimally using the fewest moves possible.

The Fifteen Puzzle was invented by Sam Loyd1 in the 1870s , and appeared in the scientific literature shortly thereafter . The editor of the journal added the following comment to the paper: “The ‘15’ puzzle for the last few weeks has been prominently before the American public, and may safely be said to have engaged the attention of nine out of ten persons of both sexes and of all ages and conditions of the community.”

One reason for the world-wide Fifteen Puzzle craze was that Loyd offered a $1000 cash prize to transform a particular initial state to a particular goal state. Johnson and Story proved that it wasn’t possible, that the entire state space was divided into even and odd permutations, and that there is no way to transform one into the other by legal moves. Loyd’s impossible goal state with a \$1000 cash prize

## Proof of insolvability

The classical proof2 for the insolvability of the puzzle involves an argument on:

• the parity3 of the permutation of the squares on the grid,
• versus the parity of the taxicab distance (number of rows plus number of columns) traveled by the blank square

A summertime conversation with G.R., who was not aware of the question or the proof, lead to his suggesting a subtle and interesting variant which fully dispenses with the blank square. Here it goes…

## Variant

The classical insolvability proof works by identifying the set of possible puzzle states with the group $\mathcal{S}_{16}$ of permutations of the squares on the puzzle grid. Instead for the variant we work with the group $\mathcal{S}_{18}$ of permutations of the fifteen tiles plus three fictitious elements $a$, $b$, $c$, which represent the horizontal separations between the rows of the puzzle.

### Puzzle states

As shown in the picture below, the initial state of the puzzle is represented by the identity permutation in $\mathcal{S}_{18}$:

$$\text{Id} = \left( \begin{array}{l} 1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;11\;12\;c\;13\;14\;15\\ 1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;11\;12\;c\;13\;14\;15 \end{array} \right)$$

 Initial puzzle state Element of $\mathcal{S}_{18}$

Note that moving a tile horizontally does not change the representation in $\mathcal{S}_{18}$, but moving a tile vertically does:

 After moving tile $11$ down Element of $\mathcal{S}_{18}$

After tile $11$ has been moved down, the representation of the puzzle becomes:

\begin{align*}
&\left(
\begin{array}{l}
1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;11\;12\;c\;\;13\;14\;15\\
1\;2\;3\;4\;a\;5\;6\;7\;8\;b\;9\;10\;12\;\;c\;13\;14\;11\;15
\end{array}
\right)\\
\\
=&(11\;12\;c\;13\;14)\quad \text{(cycle of length 5)}
\end{align*}

Let $\mathcal{P} \subset \mathcal{S}_{18}$ be the set of (representations of) all possible puzzle states, legal and non-legal. Then $\mathcal{P}$ is precisely:

$$\mathcal{P} = \left\{s\in\mathcal{S}_{18}\quad \left|\quad \begin{array}{ll} &\big(s(4)=a\;\text{and}\;s(8)=b\;\text{and}\;s(12)=c\big)\\ \text{or}&\big(s(4)=a\;\text{and}\;s(8)=b\;\text{and}\;s(c)=c\big)\\ \text{or}&\big(s(4)=a\;\text{and}\;s(b)=b\;\text{and}\;s(c)=c\big)\\ \text{or}&\big(s(a)=a\;\text{and}\;s(b)=b\;\text{and}\;s(c)=c\big) \end{array} \right. \; \right\}$$

### Tile moves

We sort tile moves according to their type, where there are exactly 24 types as shown in the following picture:

$2\cdot3\cdot4=24$ types of moves

For instance, type $\downarrow_{c3}$ gather all moves like so:

• downwards,
• crossing separator $c$,
• in column $3$.
This is move type $\downarrow_{c3}$

Let $\mathcal{M}\subset\mathcal{P}\times\mathcal{P}$ be the set of (representations of) all possible tile moves, where $(s, e)\in\mathcal{M}$ is the move starting at $s$ and ending at $e$. Finally let us split $\mathcal{M}$ along move types:

$$\mathcal{M}\quad=\;\;\bigcup_{\text{all types }t}\mathcal{M}_t$$

### Tile moves are cycles

Lemma: all moves in $\mathcal{M}$ are cycles of length $5$.

We verify this by considering every move type in turn.

For example, $\forall (s, e)\in\mathcal{M}_{\downarrow_{c3}}$:

$$\begin{array}{l} e&=\left( \begin{array}{l} \;\;1\;\;\;\;2\;\;\;\;3\;\;\;\;4\;\;\;\;\,a\;\;\;\;5\;\;\;\;6\;\;\;\;7\;\;\;\;8\;\;\;b \\ s(1) s(2) s(3) s(4) \;a\;s(5) s(6) s(7) s(8) b \end{array} \right. \\ &\\ &\quad\quad\left. \begin{array}{l} \;\;\;9\;\;\;\;10\;\;\;\;11\;\;\;12\;\;\;\;c\;\;\;\;\;13\;\;\;\;14\;\;\;\;15 \\ s(9) s(10) s(12)\;\;c\;s(13) s(14) s(11) s(15) \end{array} \right) \\ &\\ &=\;\; (11\;\;12\;\;c\;\;13\;\;14)\circ s, \end{array}$$

which gives $e \circ s^{-1} = (11\;\;12\;\;c\;\;13\;\;14)$.

And so on4… Hence all moves are cycles of length $5$ and even parity:

$$\forall (s, e) \in \mathcal{M}, \quad \pi(e \circ s^{-1}) = 1$$

### Conclusion

Consider a legal puzzle state $s\in\mathcal{P}$. There exists a sequence of moves $(s_0,e_0), \cdots, (s_n,e_n)$ in $\mathcal{M}$, such that:

$$\left\{ \begin{array}{l} s_0=\text{Id}\\ \forall i < n,\quad s_{i+1}=e_i\\ e_n=s \end{array} \right.$$

It follows that:

\begin{align*}
s&=e_n\circ(s_n^{-1}\circ e_{n-1})\circ\cdots\circ(s_1^{-1}\circ e_0)\circ\text{Id}\\
&=(e_n\circ s_n^{-1})\circ(e_{n-1}\circ s_{n-1}^{-1})\circ\cdots\circ (e_1\circ s_1^{-1})\circ(e_0\circ s_0^{-1})
\end{align*}

is a permutation with even parity.

Hence Loyd’s \$1000-cash puzzle goal state is not legal.$\quad\Box$## References Gardner, M. (Ed.). (1960). More mathematical puzzles of Sam Loyd. Dover Publ. Johnson, Wm. W., & Story, W. E. (1879). Notes on the “15” Puzzle. American Journal of Mathematics, 2(4), 397–404. JSTOR. https://doi.org/10.2307/2369492 Korf, R. E. (2000). Recent Progress in the Design and Analysis of Admissible Heuristic Functions. In B. Y. Choueiry & T. Walsh (Eds.), Abstraction, Reformulation, and Approximation (pp. 45–55). Springer. https://doi.org/10.1007/3-540-44914-0_3 ## Permutations cheatsheet A permutation of the set$\{1, 2, \cdots, n\}$is a bijection of$\{1, 2, \cdots, n\}$with itself. The set of permutations of$\{1, 2, \cdots, n\}$5 is denoted by$\mathcal{S}_n$. One usual way of writing a permutation$p$is by providing the exhaustive list of$x \mapsto p(x)$mappings, in a rectangular matrix like so: $$p=\left(\begin{array}{cccccc} 1&2&3&4&5&6&7\\ 7&3&5&2&4&6&1 \end{array}\right)$$ A more concise way is by specifying$p$as a combination of cycles. For example: $$p = (1\;\;7) (2\;\;3\;\;5\;\;4)$$ A permutation that consists of a single length-2 cycle is called a transposition. Every permutation in$\mathcal{S}_n$can be expressed as a composition of tranpositions. For example: $$(1\;\;7) (2\;\;3\;\;5\;\;4) = (1\;\;7)\circ(2\;\;3)\circ(3\;\;5)\circ(5\;\;4)$$ The operation of composition gives the set$\mathcal{S}_n$a structure of group. There is a unique group morphism from$\big(\mathcal{S}_n, \circ\big)$to$\big(\{-1,1\},\cdot\big)$which maps transpositions to the value -1. This morphism is called parity (denoted by$\pi$in this article). $$\pi: \mathcal{S}_n \rightarrow \{-1,1\}$$ $$\forall x, y \in \mathcal{S}_n, \;\;\pi(y\circ x) = \pi(y)\cdot\pi(x)$$ A cycle of length even (respectively odd) has parity odd (respectively even). Catégories ## AlphaGo AlphaGo versus Lee Sedol Game 2 – March 10th 2016 Catégories ## Colors Colors are beautiful. Colors have names. Get to know them. 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. ## 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. 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) 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}_ndenote the set of all possible towers: \begin{align} \mathbb{T}_n \quad &\stackrel{\text{def}}{=} \quad \{0, 1\}^{[n]} \\ &= \quad [2^n], \nonumber \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: \forall t \in \mathbb{T}_n, \forall p \in \mathbb{Z}, \quad \overline{(t)}(p) \;\stackrel{\text{def}}{=}\; (t \gg p) \mathbin{\%} 2, (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) strategys$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: \mathbb{S}_n \; \stackrel{\text{def}}{=} \; \mathbb{Z}^{\mathbb{T}_n}. 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 = [0010].$$ 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$[0100212301002120] \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). \eta_{t,u}(s) \; \stackrel{\text{def}}{=} \; \overline{(t)}\big(s(u)\big) \cdot \overline{(u)}\big(s(t)\big) 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.: \eta(s) \; \stackrel{\text{def}}{=} \; \sum_{t,u \in \mathbb{T}_n}\eta_{t,u}(s) ##### 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. \mu(s) \; \stackrel{\text{def}}{=} \; {1 \over{4^n}} \cdot \eta(s) ##### Equivalence We call two strategies$a$and$b$in$\mathbb{S}_n$equivalent, when they agree on the winning configurations: a \equiv b \; \stackrel{\text{def}}{\iff} \; \forall t,u \in \mathbb{T}_n, \eta_{t,u}(a) = \eta_{t,u}(b). 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. \big(\forall t \in \mathbb{T}_n \setminus \{0\}, \;\; a(t) = b(t)\big) \quad \implies \quad a \equiv b. Of course, equivalent strategies have the same hit score and win rate: \forall a, b \in \mathbb{S}_n, \quad a \equiv b \implies \eta(a) = \eta(b). \label{EquivRate} ### 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). \forall t \in \mathbb{T}_n, \quad \mathbf{T}_n(t) \stackrel{\text{def}}{=} n-1 #### 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 = [1010]$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 = [01020102]$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*} \forall t \in \mathbb{T}_n, \;\; \big(e_m(s)\big)(t) \stackrel{\text{def}}{=} s(t \mathbin{\%} 2^n) (where\mathbin{\%}$is the remainder operator). Win rate is invariant under embedding into$\mathbb{S}_m$: \forall s \in \mathbb{S}_n, \forall m > n, \;\; \mu(s) = \mu(e_m(s)) #### 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$nhats. 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: b \rightarrow a \;\stackrel{\text{def}}{=}\; LR(a, b), and the following holds: \forall a, b, c, \;\; (c \rightarrow b) \rightarrow a \,=\, c \rightarrow (b \rightarrow a) \,=\, c \rightarrow b \rightarrow a #### 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$nhats. 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: a \leftarrow b \;\stackrel{\text{def}}{=}\; RR(a, b), and the following holds: \forall a, b, c, \;\; (a \leftarrow b) \leftarrow c \,=\, a \leftarrow (b \leftarrow c) \,=\, a \leftarrow b \leftarrow c #### 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$nhats. 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}$: \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. 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}$: \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. 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}$: \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. ### 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. #### Formulae #### 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: \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} Which whena \in [n]^{\mathbb{T}_n}$further simplifies to: \!\!\!\!\!\!\!\!\!\!\!\!\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} 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.

Catégories

## Shepard Fairey

Counterpoint in blue: paintings by Alexandre Motte (Dinard)

Catégories

## Ce que nous sommes

We are such stuff
Nous sommes l’étoffe
As dreams are made on; and our little life
dont sont faits les rêves ; et nos petites vies
Is rounded with a sleep.
sont bordées de sommeil.
— Prospero, The Tempest, William Shakespeare

Wir sind eine Masse, die jede Form annimmt, in die sie auf die eine oder die andere Weise hineingerät!
Nous sommes une matière qui épouse toujours la forme du premier monde venu !
— Ulrich, Der Mann ohne Eigenschaften, Robert Musil