Bot C++17 pour le challenge EXOTEC Snake Byte de CodingGame (hiver 2026).
Jeu de snake multijoueur en vue latérale avec gravité, plateformes et équipes de 1 à 4 serpents.
La grille est vue de côté. Les serpents sont soumis à la gravité : après chaque déplacement, tout corps sans support tombe case par case jusqu'à reposer sur une plateforme, une énergie ou un autre serpent. Manger une énergie allonge le corps d'une case. Rentrer dans un obstacle ou tomber hors grille fait perdre une case (mort si ≤ 3 cases). La victoire revient au joueur dont les serpents cumulent le plus de cases à la fin des 200 tours.
Contrainte temps réel : 50 ms par tour, sortie sur stdout, debug sur stderr.
answer.cpp — fichier de soumission standalone (~800 lignes)
bot_core.hpp — logique extraite en header partagé (tests)
sim.cpp — simulateur headless pour évaluation hors CG
Le bot est structuré en deux niveaux :
- Minimax avec alpha-beta — décision principale, lancé dans un thread dédié avec timeout dur
- Fallbacks BFS par rôle — utilisés si le minimax n'a pas convergé ou est interrompu
- Minimax alpha-beta avec profondeur itérative (deepening), interrompu proprement à 35 ms via
atomic<bool> g_timeout - Move ordering par flood fill + proximité énergie pour maximiser les coupures alpha-beta
- Profondeur dynamique selon le nombre de serpents vivants (2 → depth 5, 8+ → depth 2)
- Thread dédié via
ThreadPool(libftpp) — le thread principal reste réactif pour le timeout
score = (territoire_moi - territoire_adv) × 3
+ (longueur_moi - longueur_adv) × 10
+ bonus_énergie_atteignable
- malus_énergie_adv
+ pénalité_mobilité
+ pénalité_collision_têtes
- Voronoi multi-sources pour mesurer le territoire : BFS simultané depuis toutes les têtes alliées et adverses
- BFS global par tête pour l'énergie : un seul BFS par serpent couvre toutes les énergies à portée (O(N_serpents × REACH²) au lieu de O(N_serpents × N_énergie × REACH))
- Flood fill pour détecter les dead ends (pénalité si espace < 5 cases)
simMove+applyGravitysimulent fidèlement la physique du jeu à chaque nœud minimax- Les corps alliés sont inclus comme obstacles (anti-collision fratricide)
Toutes les grilles (obstacles, énergie, corps, visités) sont des bitset<2560> (grille 64×40) :
- Lookup O(1) sans hashing
- Opérations ensemblistes en une instruction (
energy & ~claimed) - ~10× plus rapide que
unordered_set<int>pour les BFS répétés à chaque tour
- Rôles dynamiques : COLLECTOR (collecte énergie) ou BLOCKER (intercepte un adversaire plus court à portée ≤ 3 cases, seulement si nettement plus long)
- Pré-réservation d'énergie : avant la boucle d'action, chaque COLLECTOR se réserve sa cible la plus proche — évite que deux serpents alliés visent la même énergie
- Détection de stuck : patterns A-A-A, A-B-A, A-B-A-B détectés sur les 4 dernières positions ; handler dédié avec priorité aux directions horizontales (corrige les bounces gravité)
Simulateur autonome pour évaluer le bot sans passer par CodingGame :
g++ -O2 -std=c++17 -pthread -o sim sim.cpp
./sim 100 2 mixed # 100 parties · 2 serpents/joueur · carte mixte
./sim 200 1 flat # 200 parties · 1v1 · terrain plat
./sim 50 2 platforms # 50 parties · 2v2 · avec plateformesLe simulateur instancie deux copies du bot en mémoire (mirror match), les fait jouer via decideTurn() et collecte :
- Taux de victoire / draws
- Longueur moyenne et médiane finale
- Distribution des durées de partie
- Détection d'asymétrie positionnelle (spawn centré depuis le milieu de la grille)
| Config | P0 wins | P1 wins | Draws | Avg turns |
|---|---|---|---|---|
| 1v1 flat (50 parties) | 32% | 32% | 36% | 157 |
| 2v2 mixed (50 parties) | 20% | 76% | 4% | 153 |
Le mirror match 1v1 flat converge à 50/50 (symétrie parfaite confirmée).
Le déséquilibre 2v2 est un signal actif : biais de coordination multi-serpents en cours d'investigation via le simulateur.
| Langage | C++17 |
| Parallélisme | std::thread, std::future, std::atomic |
| Structures | bitset<2560>, unordered_map, deque |
| Algorithmes | Minimax α-β, BFS, Voronoi, Flood fill |
| Build | g++ -O2 -std=c++17 -pthread |
| Fichier | Rôle |
|---|---|
answer.cpp |
Soumission CodingGame (standalone, ~800 lignes) |
bot_core.hpp |
Header partagé — toute la logique extraite |
sim.cpp |
Simulateur headless, moteur de jeu complet |
Challenge CodingGame — EXOTEC Snake Byte — Hiver 2026