Pokémon est un jeu formidable. En plus de fuguer de chez ses parents à tout juste 10 ans et demie pour capturer des animaux sauvages et organiser des sortes de combats de chiens, on y fait des tas de choses : on y fait du vélo, on cultive des plantes et on pêche. Soyez donc sans craintes, car c'est bien de pêche virtuelle dans ce jeu dont il s'agit. Je ne vous invite en aucun cas à rompre le confinement pour aller vous asseoir au bord d'une rivière et aucun poisson réel n'a été blessé ni même contrarié dans ses velléité de rester peinard au frais et au fond de l'eau dans la préparation de cet article.

Les gens qui ont créé pokémons aiement les farces et les histoires morales et c'est la raison pour laquelle existe Magicarpe. Magicarpe est un gros poisson sans capacité d'attaque aucune, ce qui le rend extrêmement dur à faire évoluer. Tout dresseur·se raisonnable l'abandonnerait au bout de quelques niveaux en voyant qu'il n'a toujours appris aucune compétence utile et bim ! Sans prévenir, niveau 20, le voilà qui se transforme subitement en un dragon, monstre de rage et de destruction. Comme quoi faut se méfier des faux-calmes.

Ça, c'était dans la toute première génération de Pokémon. Au cas où ça ne suffirait pas, dans la troisième génération on en remet une couche avec un deuxième couple de pokémon «relou-inutile» / «méga-balèze & en plus trop beau» : j'ai nommé Barpau et Milobellus. Mais, histoire de corser un peu les choses, il est en plus super dur de trouver un Barpau. Il ne vit que dans une seule rivière, où il a une chance assez faible d'apparaître (taux de rencontre de 15% — quand un pokémon est rencontré, le jeu tire au sort de quelle espèce il va s'agir parmi les quelques espèces présentes dans une zone donnée, il n'y a que 15% de chances que ce soit un Barpau), **sur 6 cases seulement** dans toute la rivière (qui fait quand même au bas mot 400 cases). On ne vous dit pas lesquelles, ça va sans dire.

![Une vue d'ensemble d'un coude de la rivière-à-Barpau](/media/2020/rivière.png)

Il est donc évident qu'il faut une certaine dose de patience si l'on veut pouvoir capturer ce charmant poisson qui deviendra plus tard ce «dragon» envoûtant à l'allure racée. La question est de savoir exactement quelle dose de patience. Car il est possible de tomber accidentellement sur une case contenant potentiellement des Barpaus mais de pêcher longtemps sans en ferrer un. Pour être certain de ne pas abandonner trop tôt, il faut pêcher potentiellement longtemps, très longtemps, qui est autant de temps perdu sur 394 cases de cette rivière. Oui, mais longtemps à quel point ? Deux fois, cinq fois, vingt fois par case ? [Certains](https://fr.wikihow.com/attraper-Barpau-dans-Pok%C3%A9mon-%C3%89meraude) recommandent de pêcher cinq fois sur chaque case. Pourquoi ce nombre ? Serait-il possible de déterminer une stratégie qui minimise le nombre de tentatives de pêche avant de rencontrer un Barpau, et donc de déterminer au moins une case-à-Barpau (`C⁺`) de la rivière, sur laquelle il sera ensuite possible de revenir à loisir pour trouver le Barpau de ses rêves ?

## Lancés répétés

La première question à laquelle nous devons répondre pour comprendre les mécanismes en œuvre est celle du risque de ne pas trouver de Barpau en pêchant sur une case `C⁺`. Comment ce risque évolue-t'il ? Que signifient les 15% mentionnés plus haut ? Peut-on s'assurer de pêcher un Barpau au bout de suffisamment de tentatives ?

On va donc se placer en pensée sur une case `C⁺` pour cette première analyse. En un lancé, il est facile de répondre à la question, c'est la définition du taux de rencontre : il y a 15% de chances de trouver un Barpau à ce premier essai, ce qui signifie aussi, vu dans l'autre sens qu'il y 15% de chance que notre première tentative soit la bonne et que nous trouvions un Barpau dès la première pêche sur cette case. Et au bout de deux pêches sur cette case ? Là, les choses deviennent subitement beaucoup moins évidentes à exprimer si l'on n'a pas l'habitude de manier les probabilités.

J'entends «0.15²» : non, évidemment ! «0.15²» est inférieur à «0.15», intuitivement, la probabilité va quand même croître au fur et à mesure que l'on va pêcher. J'entends aussi «2 \* 0.15». Bon, là, je comprends mieux l'idée derrière, intuitivement, mais ça ne tient guère mieux : l'addition correspond à l'union de résultats disjoints (la probabilité que le prochain arbre qu'on voit soit «un chêne ou un érable» est égale à la somme de la probabilité que le prochain arbre qu'on voit soit un chêne et de celle qu'il soit un érable). Donc, déjà, on comprend que cette opération sur les probabilités ne correspond pas à celle sur nos résultats de pêche. Plus simplement, il y a un problème avec les sommes, c'est que ça devient vite très grand. Il se trouve que `7 * 0.15 = 1.05`, que faire de cette probabilité supérieure à 1 ? Il y a plus de cas où ça se réalise au bout de 7 cas que de cas existant ? Ça se réalise dans un autre espace que celui dans lequel nous pêchons ? Bien, lequel ? Est-ce que l'univers tel que nous le connaissons disparaît si on pêche 7 fois sur la même case ? Tout cela paraît quand même un peu fantaisiste.

Non, on s'égare. Quand on est perdu·e, en probabilités, le mieux est de revenir aux bases. Ce nombre, là, c'est pas de la magie, ça désigne juste le nombre d'issues d'un tirage qui a une propriété qui nous intéresse sur l'ensemble de tous les tirages possibles. Attention, ça n'a rien à voir avec des tirages successifs. Il est plus utile de le voir plutôt avec l'interprétation des «mondes parallèles». Cette pêche (unique), dans 15 de ces «mondes», a donné un Barpau, et dans 85 d'entre eux a donné autre chose. Et si on repêche une deuxième fois, et si les tirages sont indépendants (ce qui est le cas dans le jeu et dans la plupart des jeux de hasard auxquels on joue), il va se produire exactement la même chose : 15 issues «Barpau» et 85 issues autres. Avec cette représentation, il est sans doute un peu plus facile de comprendre comment les choses se composent. La probabilité de deux événement indépendants (l'un et/puis l'autre) est le produit de leur probabilité individuelles. Ça se voit particulièrement bien dans ces cas finis, puisqu'on peut bien se représenter l'ensemble des issues des deux tirages comme le produit cartésien de chacun des tirages (un tableau de dimension le nombre de tirages). Nous en sommes restés à 2, ça tombe bien on va pouvoir faire un joli tableau !

| 1er tirage  | Barpau | pas Barpau |
| ----------- | :----: | :--------: |
| issues      |   15   |    85      |

| 2ème tirage  | Barpau | pas Barpau |
| ------------ | :----: | :--------: |
| issues       |   15   |    85      |

Ce qui, mis ensemble dans un tableau à 2 dimensions (2 tirages) donne :

|      x     | Barpau | pas Barpau |
| ---------- | :----: | :--------: |
| Barpau     | 15\*15 = 225  | 15\*85 = 1275 |
| pas Barpau | 85\*15 = 1275 | 85\*85 = 7225 |

Donc, la probabilité que nous ayons un Barpau au bout de 2 tentatives maximum est `Pb = (15*15 + 2*15*85) / 10000 = 0.15*(0.15+2*0.85) = 0.15 * (1 + 0.85)` (la probabilité que les deux lancers aient donné un Barpau, plus celle que le premier ait donné un Barpau mais pas le deuxième plus celle que le deuxième ait donné un Barpau mais pas le premier, ces deux dernières étant identiques). Ce qui est plus facile à exprimer par son complémentaire (plutôt que d'ajouter trois cases du tableau, on va soustraire juste la dernière) `Pb = 1 - 0.85²`. Cela nous donne en plus cette interprétation qui sera bien plus facile à manier : en fait, l'événement dont il est facile de calculer la probabilité est l'événement contraire : on a sorti deux fois de suite autre chose qu'un Barpau, celui-là sa probabilité est `0.85²`. La probabilité de l'événement qui nous intéresse, à savoir avoir un Barpau en 2 essais maximum est `Pb = 1 - 0.85²` [^complémentaire].

Et si on continue ? Avec notre nouvelle expression, c'est bien plus simple. Trois tirages ? Le risque qu'on en trouve pas est le risque de faire une série de trois sans Barpau, dont la probabilité est `0.85³`, et donc la probabilité qui nous intéresse `Pb = 1 - 0.85³`. On comprend que le raisonnement va se généraliser extrêmement bien sous cette forme. Quelle est la probabilité que l'on ait trouvé notre Barpau, en pêchant sur cette case à Barpau, au bout de `n` essais ?

```
Pb(n) = 1 - 0.85 ^ n
```

<div id="expDecay" class="graph"></div>

On voit la probabilité de succès augementer comme une jolie exponentielle avec le nombre de tentatives, pour s'approcher indéfiniment de 1 (sans jamais l'atteindre ! c'est une asymptote, aussi improbable soit-il, il est possible de tirer une série sans Barpau arbitrairement longue — si vous jouez assez longtemps, vous aurez des séries de 100 pêches sans un seul Barpau, des séries de 10 000, 1 000 000…). Ce graphe nous donne aussi une explication de pourquoi certains recommandaient de pêcher 5 fois par case. Regardez, sur le graphe : c'est le moment où la probabilité de rencontrer un Barpau passe le seuil des 0.5. À partir de 5 pêches sur une case à Barpau, vous avez plus de chance d'en avoir rencontré un que pas.

## Oui, mais les cases ?

Bon, on a déjà bien avancé. Mais qu'en est-il maintenant si l'on prend en compte le fait que toutes les cases ne sont pas des cases à Barpau ? Essayons de réévaluer la formule précédente. Elle continuera à être vraie dans le cas où la case est `C⁺`, ce qui se produit pour 6 cases sur 400. Tout se passe donc comme si l'on avait deux tirages, dont l'issue du deuxième dépend du premier : s'il s'avère que la case ne contient pas de Barpau (`C⁻`), alors le risque de ne pas obtenir de Barpau est de 1; dans le cas contraire `C⁺`, le modèle précédent s'applique. Pour éviter les notations lourdingues, on va appeler `P⁺` la probabilité de l'événement `C⁺` et `P⁻` celle de l'événement `C⁻`, c'est à dire pour une case donnée que l'on considère, les probabilités respectivement que cette case soit une case à Barpau ou pas. Numériquement, `P⁺ = 3/200` et `P⁻ = 197/200` mais cela n'est pas très important. Si l'on traçait donc notre tableau avec ces deux tirages cette fois différents, il aurait cette allure :

|      x     | C⁻ | C⁺ |
| ---------- | :----: | :--------: |
| Barpau     | P⁻ * 0 = 0  | P⁺ * 0.15 = 2.25e-3 |
| pas Barpau | P⁻ * 1 = P⁻ | P⁺ * 0.85 = 1.275e-2 |

Ici la distinction entre les deux issues «Barpau / pas Barpau» pour le cas `C⁻` est superflue mais je l'ai faite pour vraiment justifier pourquoi je peux adapter la formule précédente et écrire ceci pour évaluer notre probabilité d'avoir un Barpau en une pêche sur la première case de la rivière : `Pb = 1 - (P⁻ + 0.85*P⁺)`. Le sens de cette formule est le suivant : «la probabilité qui nous intéresse est celle du complémentaire («`1 -`») de l'événement défavorable "ne pas avoir trouvé de Barpau", qui se produit exactement quand la case n'était pas une case à Barpau (`P-`) ou (`+`) quand c'en était une mais, comme dans 85% des cas, nous avons tiré autre chose qu'un Barpau dessus».

Avec ce qui précède, il est cette fois très facile de généraliser ça à plusieurs pêche. Le terme de case `P⁻` ne change pas, le nombre de tentatives n'influe pas sur le fait que la case contienne ou pas un Barpau (le jeu ne tire pas à chaque fois, pour rappel, les cases sont distribuées une fois pour toute avant la pêche[^distribution]), et l'autre terme va diminuer exponentiellement comme précédemment :

```
Pb(n) = 1 - (P⁻ + P⁺*0.85^n)
```

<div id="oneTile" class="graph"></div>

On a bien sûr la même forme que précédemment, mais cette fois au lieu de tendre vers 1 («c'est sûr, cette case est une case à Barpau, avec assez de persévérance on en pêchera un»), on tend vers `P⁻` («à force de pêcher, on élimine le facteur variable de la malchance, qui expliquerait que l'on n'ait pas encore de Barpau, pour ne plus subir que le terme constant, indépendant de notre tenacité à pêcher : si y a pas d'Barpau, y a pas d'Barpau»). Et cela est vrai tant que l'on pêche sur cette première case. Le dernier grand saut conceptuel que nous allons devoir faire pour apporter une réponse utile à notre question initiale va être de regarder ce qui se passe pour une stratégie où nous pêchons `p` fois sur la même case avant de passer à la suivante.

## Stratégie, stratégie

On va forcément pêcher un nombre fini de fois sur chaque case. On va donc parcourir une portion plus ou moins longue de l'exponentielle ci-dessus, avant de passer à la case suivante. Si l'on considère une case particulière, la probabilité qu'elle soit `C⁺` est avec ce que nous avons posé ci-dessus `P⁺`. Mais une fois que l'issue des tirages de plusieurs cases est connue, cela influe sur les tirages suivants : si par exemple nous avons déjà 6 cases `C⁺`, alors la probabilité que les suivantes soient `C⁺` n'est plus de `P⁺`, elle tombe subitement à 0 car il ne s'agit pas d'un tirage case par case, mais nous savons au contraire qu'il y a 6 cases exactement qui ont été réparties sur ces 400 cases de rivière. Inversement, si par un manque cruel de chance nous sommes à la 394ème case sans Barpau, la probabilité que chacune soit `C⁺` devient égale à `1` : par élimination, nous avons trouvé l'ensemble des 6 cases contenant les Barpaus, il n'y a plus aucune autre configuration possible.

Cette réserve étant posée, nous allons quand même assimiler la répartition de ces cases à une distribution uniforme de probabilité `P+` pour simplifier les choses dans un premier temps mais nous reviendrons dans un [prochain article](/articles/Dans%20les%20arbres.html) sur la pertinence de ce choix en analysant plus finement la combinatoire. Avec cette hypothèse il devient possible d'étendre la formule suivante en ajoutant le paramètre `p` du nombre de pêches par case.

Tant que nous pêchons un nombre de fois `n ≤ p`, la formule précédente continue de s'appliquer :

```
Pb(p, n) = 1 - (P⁻ + P⁺*0.85^n)
```

En passant à la `p+1`ème pêche, on pêche pour la première fois sur la case suivante, qui a à son tour avec l'hypothèse de distribution uniforme une probabilité `P⁺` d'être une case à Barpau `C⁺`. Comme nous avons combiné les résultats défavorables précédemment pour comprendre ce qui se passait au bout de plusieurs tirages sur une case, il nous suffit de considérer l'ensemble des issues expliquant que nous n'ayons pas pêché de Barpau à l'issue de ce `p+1`ème tirage pour en évaluer le risque. Il faut et il suffit que [la première case ait été `C⁻` ou qu'elle ait été `C⁺` et que nous ayons tiré une série de `p` sans Barpaus] *et* que [la seconde case soit une `C⁻` ou qu'elle soit `C⁺` mais que nous venons de tirer autre chose qu'un Barpau]. Soit pour 

```
Pb(p, p+1) = 1 - (P⁻ + P⁺*0.85^p)*(P⁻ + P⁺*0.85^1)
```

Et maintenant que nous sommes sur la deuxième case, le premier terme du produit ne bouge plus :

```
Pb(p, n) = 1 - (P⁻ + P⁺*0.85^p)*(P⁻ + P⁺*0.85^(n[p]) pour p < n ≤ 2*p
```

en notant `n[p]` le reste de la division de `n` par `p`, son *modulo*. À ce point, on comprend bien comment cela va se généraliser. Des blocs de la forme du premier ci-dessus pour les paquets entiers de `p` (c'est le «`floor(n/p)`» dans la formule qui suit, c'est à dire qu'on regarde le quotient dans la division de `n` par `p` correspondant au nombre de cases qui ont été fouillées «complètement», c'est à dire en fait `p` fois) et un terme comme celui pour une case unique pour la case en cours. Preuve par récurrence, ou un truc comme ça.

```
Pb(p, n) = 1 - (P⁻ + P⁺*0.85^p)^(floor(n/p)) * (P⁻ + P⁺*0.85^(n[p])
```

<div id="uniform" class="graph"></div>

Ce graphe représente la formule qui précède pour des stratégies allant de 1 à 10 pêches par case. Jouez avec, hein, il est là pour ça, n'hésitez-pas à zoomer dessus, c'est là qu'on voit bien ce qui se passe. On croirait encore une famille d'exponentielle mais en fait non : regardez, ez en zoomant assez, et ça se voit mieux avec la stratégie 10 pêches par case, on voit des petites «vaguelettes». Il s'agit des portions d'exponentielles précédentes sur chaque plage de `p` cases (c'est pour ça que ça se voit mieux pour `p = 10`, elles sont un peu plus longues) pendant laquelle le dernier terme du produit est le seul qui améliore nos probabilités de trouver un Barpau, jusqu'à ce qu'on change de case et que la probabilité refasse un petit bond.

Le résultat que nous attendions est aussi contenu dans ce graphe : les courbes se séparent assez vite, et ne se croisent pas. Elles sont en ordre décroissant : plus le nombre de pêche par case augment, moins notre probabilité de trouver un Barpau en `n` tentatives croît vite. En effet, dans la formule ci-dessus, le terme qui finit par peser le plus est le `P⁻ ^ floor(n/p)`, c'est lui qui fait diminuer le risque de ne pas trouver de Barpau, et notre intérêt est de le faire croître le plus vite possible, c'est à dire en ne restant qu'une fois sur chaque case. Et donc, ce conseil de 5, tout à fait valable sur une case à Barpau, bin en fait, se révèle pas si utile que ça. Certes, vous allez diminuer vos chances de louper un Barpau sur une bonne case (diminuer, mais ça arrivera, 56% de chances c'est pas la panacée non plus). Oui, mais pour ce faire, vous allez tester les cases à un rythme bien moins rapide.

C'est le moment où le graphe va commencer à montrer ses limites avec son hypothèse de distribution uniforme mais en 400 pêches, à raison d'une pêche par case, vous aurez couvert toute la rivière. Vous n'aurez pêché qu'une fois sur chaque case à Barpau, oui, mais vous aurez vu les six, donc votre chance d'en avoir trouvé un (et c'est différent de la formule précédente, qui sous-estime la probabilité puisqu'avec une distribution uniforme, il existe un risque que nous ayons vu moins de 6 cases `C⁺` en 400 pêches) sera de :

```
P(1, 400) = 1 - 0.85^6 = 0.62
```

En autant de pêche, avec une stratégie de 5 pêches par cases, vous n'aurez visité que 80 cases. Il est assez probable que vous ayez déjà vu au moins une case à Barpau, mais vous avez quand même plus de 44% de chances de l'avoir loupé… Bien sûr, on sait que le graphe ci-dessus montre des limites, mais il se trompe à priori moins que pour la stratégie «1 pêche par case» puisque nous n'avons visité que 80 cases, et donc les effets de bords de «nous avons visité 400 cases, il est certain d'avoir rencontré 6 cases `C⁺` s'appliquent moins fortement» et si on regarde la valeur à 400 pêches, elle est de 48.8%. C'est sans doute un peu plus, mais très vraisemblablement inférieur aux 62% ci-dessus. Avec 10 pêches par case, on voit à quel point c'est pire. Certes, si vous avez eu la chance d'avoir une case `C⁺` dans vos 40 premières, il est peu vraisemblable que vous l'ayez loupée mais… vous n'en avez testé que 40. En 800 pêches, soit 80 cases avec cette stratégie, vous avez probablement vu 1 case (une répartition homogène des cases donnerait une case `C⁺` toutes les 66.7 cases), et donc pu tenter votre chance 10 fois. Avec la stratégie «1 pêche par case», vous avez fait 2 fois le tour de la rivière, vous avez donc déjà pêché 12 fois sur une case `C⁺`… En bref, changez tout le temps de case, ne restez pas pêcher plusieurs fois sur la même.

## Conclusion

Forte de toutes ces considérations, j'ai donc sorti ma plus belle canne à pêche (je dis pas ça en vain, y a vraiment plusieurs cannes à pêche dans le jeu), et je suis allée tenter ma chance sur toutes les cases de la rivière, une par une, en ne pêchant pas plus d'une fois par case, donc. Je commençais à sérieusement approcher la fin de la rivière et à me faire une raison (après, tout, il était plus probable de trouver un Barpau dès le premier passage que pas mais bon, 62% de chances, c'est pas si élevé) quand…

<video src="/media/2020/Feebas.webm" controls>
	Une vidéo qui montre la rencontre de mon joli Barpau : )
</video>

Et voici la bête

![Mon Barpau, et un futur Milobellus !](/media/2020/Barpau.png)

Purée c'est quand même beau quand ça marche.

[^complémentaire]: `1 - x`, c'est le complémentaire à `1` de `x`, donc c'est la probabilité de l'événement complémentaire de l'événement `Ex` dont la probabilité est `x` puisque c'est la probabilité de tout, `1`, moins la probabilité de `Ex`. 

[^distribution]: plus exactement, la distribution dépend d'un certains nombres de facteurs «constants» pour un jeu donné (le numéro de dresseur, peut-être un serial de la cartouche ou des trucs cachés comme ça mais qui ne changent pas pour qui joue) et d'une phrase prononcée devant un PNJ à un moment du jeu — il est ainsi possible de «relancer les dés» en générant une autre distribution en allant reparler à ce PNJ, mais cela est hors propos pour notre question qui est de savoir, pour une distribution de rivière donnée, quelle est la stratégie la plus rapide pour trouver un Barpau.

<script src="/media/2020/On va à la pêche_graphs.js"></script>