Je ne me fais pas trop de souci pour le coût (du moment qu'il n'est pas trop catastrophique) : plus on capture une grosse chaîne, plus c'est un évènement dramatique qui arrive peu souvent dans la partie. Capturer 30 pierres décide de la partie. Capturer 3 pierres est déjà un évènement important. Alors que capturer une seule pierre est très rapide si on a le v ancêtre.


De plus, garder l'historique permettrait peut être, si tout est bien calculé, de reprendre un coup.
Et ça ça serait vachement cool, parce que ce qui me fait peur, c'est le coût de duplication du graphe...

de plus garder l'historique permet de trivialiser mon problème initial : décider si une chaîne de fin de partie est obtenue à partir de telle chaîne de début de partie.

Et je ne pense pas que cette historique soit si grosse que ça (à vérifier...)