home.md

@@ -96,15 +96,44 @@ Of course, not all trees with the above structure are valid players. To represen
 
 ---
 
-**Example** The following tree does not represent a valid breaker:
+**Example.** The following tree does not represent a valid breaker:
 
 ![Example of invalid  tree](example_invalid_tree.png)
 
-To show this, consider again the `RRR` secret code. The first guess is BRG with feedback $`1, 0`$. Going down on the corresponding branch, the second guess is BBB with feedback $`\langle 0, 0 \rangle`$. Then the third guess is GGG and the feedback is again $`\langle 0, 0 \rangle`$. Now the breaker does not know how to play because the node GGG does not have a subtree labeled $`\langle 0, 0 \rangle`$.
+To show this, consider again the `RRR` secret code. The first guess is BRG with feedback $`\langle 1, 0 \rangle`$. Going down on the corresponding branch, the second guess is BBB with feedback $`\langle 0, 0 \rangle`$. Then the third guess is GGG and the feedback is again $`\langle 0, 0 \rangle`$. Now the breaker does not know how to play because the node GGG does not have a subtree labeled $`\langle 0, 0 \rangle`$.
 
 ---
 
+## Generating a random population
 
+We will construct a valid tree by playing games for each possible code. At each game the breaker will follow a path in the tree while this is possible. Then it will complete the path with random not yet used guesses.
+
+1. Start with a tree containing only a root node with a random guess.
+2. Play a game for each code $`c \in \mathbb{C}`$
+  1. Start at the root node.
+  2. Get a feedback $`f`$ for the current node's guess.
+  3. If $`f = 0`$, stop.
+  4. If the current node has not a child labeled $`f`$, create this child and initialize it with a random guess not yet used in this game.
+  5. The child labeled $`f`$ becomes the current node, go to step 2.2.
+
+The trees created by this algorithm are rather deceiving:
+
+![Initial tree](tree_unshrunk.png)
+
+However, there is an obvious way to significantly reduce their height. Notice the long paths without branches consisting of many wrong guesses followed by the right one. Consider for example the leftmost one starting at GBG and finishing in BGG. These paths correspond to situations where there is only one code consistent with the previous guesses. We can shrink each path of this kind to a single node:
+
+![Tree after shrinking](tree_shrunk.png)
+
+There is another way to optimize the structure of our trees. A common pattern is a triangle formed by a non terminal node who has two leaf children. There are seven of them in the picture above, rooted (from left to right) in RGR, GGB, BRB, BRG, RBB, RGR and BBR. These triangles can be transformed as follows:
+  * Replace the father's guess by the guess of one of the children
+  * Remove this child
+  * Relabel the remaining child to match the new father's guess
+
+![Triangle optimization](triangle_opt.png)
+
+Here is the result after transforming the seven triangles from the previous example:
+
+![Tree after triangle optimization](tree_triangle_opt.png)
 
 # References