Comment ne pas faire pousser une forêt

Cette semaine, c'était le challenge Codingame de printemps.

Il s'agissait cette fois-ci de faire pousser des arbres, en évitant de subir l'ombre de l'adversaire. Et du fait du contexte épidémique actuel, je ne pouvais pas participer comme je l'aurai souhaité : j'ai arrêté de coder mercredi soir, et j'ai choisi très volontairement, de coder en Rust, qui n'est pas le langage le plus simple (franchement l'un des plus complexes que je connaisse, en fait).

Et comme un bonheur n'arrive jamais seul, les règles incluaient certains éléments qui ont clairement augmenté la complexité du problème.

• D'abord le fait que le terrain soit hexagonal ajoute une complexité certaine : le stockage de données dans un tableau de tableaux n'est à priori pas utilisable (j'écris à priori très volontairement parce que je conservais, depuis Coders of the Carribean, un excellent article de référence sur la modélisation de terrains hexagonaux).
• Par ailleurs, l'unité de tour de jeu, le jour, n'est en fait pas atomique : les deux joueurs vont effectuer alternativement autant d'opérations qu'ils le peuvent, en continuant même si l'adversaire n'a plus d'actions possibles. Pour moi, ça a ajouté beaucoup de complexité.
• En plus, chaque joueur a deux échelles à optimiser : le nombre de points de soleil produits chaque jour, et le score final (qui dépend des arbres récoltés, de leur ordre de récolte et de la position de la récolte).

Franchement, quand on ajoute tout ça, ça donne un résultat facilement complexe. Et comme je n'avais aucune intuition géniale, j'ai utilisé un modèle de programmation hyper classique (pour moi) :

1. Décrire chaque entité du jeu dans un type (on a donc une Action qui est un enum Rust, un struct pour chaque arbre, et enfin un modèle représentant le terrain). Petite subtilité : j'avais commencé par représenter le terrain via l'une des structures indiqué dans l'article mentionné plus haut, avant de me rendre compte que le moteur de jeu fournissait la géométrie du terrain au démarrage, du coup, il était bien plus simple de simplement stocker la géométrie dans un Vec, et le contenu dans un autre Vec.
2. A partir de là, déterminer toutes les actions possibles
3. Éliminer les actions dont le coût est supérieur aux points de soleil disponilbe
4. Et trier les actions selon une heuristique

Avec ça, j'arrive à cette solution qui atteint le niveau argent. Pas trop mal en sachant que j'ai arrêté de coder mercredi ...

Bon, là; je me donne des excuses faciles.

En vérité, je savais dès Lundi, en particulier à la lecture de cet article sur les échecs "A step-by-step guide to building a simple chess AI" que ce que je faisais n'avait pas du tout les moyens d'atteindre le haut niveau. Sauf que j'ai été intellectuellement bloqué par le fait que ce que je voyais comme l'unité de durée du tour (la journée) ne l'était pas. Et je pense sincèrement que c'est un blocage psychologique stupide de ma part. Ca veut dire quelque chose sur moi, et quelque chose de pas très chouette (mais que je sais déjà). J'ai bien l'impression d'être incapable de tenter des solutions authentiquement innovantes (pour moi) quand je suis pris par la pression du temps. Pour le dire autrement, le biais d'ancrage est fort. Suffisamment fort pour que, la prochaine fois que je suis tenté de faire un challenge codingame, je m'oblige à utiliser ces fameuses techniques de Monte-Carlo, de min-max et autres, qui impliqueront des solutions pas forcément répétables, mais ça n'est pas trop grave.

Parce qu'il y a quand même des choses qui ont bien marché !

J'ai enfin réussi à comprendre le sens des lifetimes Rust ! Et ça implique que j'ai réussi à écrire du code avec beaucoup moins de clone(). Et ça implique à son tour que ce code, qui certes ne fait pas grand chose, est beaucoup plus efficace que mes précédentes solutions.

En bonus, mon article précédent expliquant comment démarrer une solution Rust m'a vraiment beaucoup aidé : je n'ai eu aucun mal à produire une solution raisonnablement intéressante.

Bref, j'ai encore appris beaucoup sur moi, et c'est ce que je demande à Codingame !