Mon ensemble E, c'est l'ensemble des intersections du goban, et la partie de E, c'est une chaîne de pierres.
J'aimerais décider si une chaîne, dans une position tardive de la partie, a été obtenue par concaténation de pierres avec une chaîne du début de la partie. Le but étant de calculer des corrélations, faire de l'inférence bayésienne, ou ce genre de choses, pour qu'une IA puisse dire "telle chaîne doit vivre pour espérer gagner" ou "telle chaîne doit être connectée pour espérer vivre", etc..
Au go on utilise classiquement le hash de Zobrist : On se fixe au début du programme une fonction aléatoire f : E -> { les entiers de 64 bits } (par exemple), sous la forme d'un tableau rempli de nombres aléatoires. Le hash d'une chaîne, c'est juste le XOR des f(i) pour tout élément i de la chaîne.
C'est simple et ça a plein de qualités, notamment la réunion de deux chaînes est très rapide (un XOR). Par contre ça ne permet de savoir si une chaîne est un sous ensemble d'une chaîne plus grosse.
Bon mais en fait je crois que j'ai trouvé ce que je cherchais :
http://en.wikipedia.org/wiki/Bloom_filter
Pas sûr que ça ait des performances radicalement meilleures qu'un champ de bits, par contre, faut voir...