Hippopotame (./41181) :
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.

bah suffit d'avoir 900 Mo de mémoire

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.

ok si tu peux prendre un m arbitraire (ton post laissait supposer que ça serait casé dans un entier de taille fixe, ce qui est certainement plus simple à programmer sans overhead [on a pas envie de se retrouver avec un en-tête pour décrire m à chaque hash, plus l'overhead lié à l'allocation d'un bloc de mémoire séparé])

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.

La difficulté j'imagine c'est que la structure ne tient pas compte du fait que pour un n être (physiquement) en contact avec un b est potentiellement très différent d'être en contact avec un mur ?

- C'est très caml-spirit

Caml c'est plus "arbre" voire graphe acyclique que graphe