Un groupe c'est ambigu : pour un joueur de go non informaticien, ça peut très bien être un ensemble de pierres non pas connectées, mais
connectables, voire même
faiblement connectables. Et si l'existence d'un groupe ne fait pas de doute dans l'esprit d'un joueur, l'appartenance d'une pierre donnée à ce groupe, en revanche, est un prédicat assez flou
. Bref mieux vaut employer le vocabulaire plus précis de chaîne pour des pierres solidement connectées.
GnuGo emploie aussi le terme de Worm, et il a un concept de groupe distinct des worms.
Un facteur trois c'est beaucoup quand on voit la différence de niveau entre 100 Mo de parties simulées et 300 Mo de parties simulées.
L'implémentation naïve, c'est juste m=19² et k=1 : il n'y a pas de code différent à pondre, c'est ça qu'est cool.
Bon mais de toute façon tout ça n'est plus d'actualité, j'ai trouvé bien mieux et encore plus original pour ma structure de donnée.
Un état du goban sera représenté par un graphe (non orienté).
Ce graphe est une abstraction qui ne contient pas toutes les données du jeu (positions exactes des pierres) mais seulement celles logiquement indispensables.
Les noeuds de ce graphe sont de trois types :
- Une intersection vide v du plateau
- une chaîne noire n du plateau
- une chaîne blanche b du plateau
Quant aux voisins d'un noeud :
- Les voisins d'un v sont les v, n et b adjacents sur le plateau, au nombre de 1 à 4.
- Les voisins d'un n sont ses libertés, c'est à dire les v adjacents sur le plateau, au nombre de 1 à oo.
- Pareil pour les voisins d'un b.
C'est pas encore tout à fait mûr dans ma tête (c'est surtout que je ne sais pas encore quelles décorations je vais mettre sur les noeuds), mais je suis de plus en plus convaincu que ça va donner quelque chose de très costaud.
CONs:
- Enlever des pierres (lors d'une capture de groupe), c'est un peu merdeux. Mais on doit pouvoir se débrouiller.
- C'est vachement lourd comme structure de donnée, beaucoup plus qu'un bête champ de bits.
PROs:
- Jouer un coup est très rapide. Il ne s'agit que de changer un motif simple dans le graphe en un autre motif simple. De plus il ne s'agit que d'une modification locale du graphe, pas besoin de tout recopier. Donc tout bien considéré, cette solution à base de graphe n'est pas lourde du tout en pratique, ça ne m'étonnerait pas qu'elle fasse aussi bien que les champs de bits sans cesse recopiés des programmes classiques.
- Le problème de déterminer si un groupe est vivant ou seki, autrement dit la condition d'arrêt dans les simulations Monte Carlo, qui est un horrible casse tête si on utilise la représentation classique du goban (problème pour lequel à peu près tous les programmes sont troués), devient à peu près trivial en lisant le graphe. Par exemple v-n-v est un groupe noir vivant.
- Le pattern matching indispensable aux heavy playouts peut être fait sur des bases plus proches de la logique du jeu.
- Plus généralement, ça ouvre la possibilité de pattern matching assez cool pour le moteur d'intelligence artificiel.
- Des problèmes tactiques de bas niveau peuvent être factorisés en introduisant de nouveau types de noeuds complexes, représentant un cluster de noeuds simples. Par exemple, v-n-v qui est un groupe noir vivant, peut être remplacé par un nouveau type de noeud n' : noir inconditionnellement vivant. Le graphe y gagne en simplicité et l'IA en clarté.
- De même il devient possible de factoriser facilement des coups miai (équivalents), ce qui réduit considérablement la complexité dans un grand nombre de situations (semeai par exemple)
- A ma connaissance personne n'a jamais fait un truc pareil, donc c'est chouette.
- C'est très caml-spirit, et ya pas besoin de programmer des routines dans un langage de bouseux
. C'est pour ça qu'après mon idée était d'essayer sur des plateaux ayant au contraire vachement plus de coins et de bords pour voir, mais c'est là que la représentation, 
)
