Discussion :

[Denis Migdal]

Bonjour,


Je suis Denis Migdal, actuellement doctorant en informatique. Bien que ma thèse soit très prenante, j'ai décidé de me lancer dans un petit projet de jeu sans ambition afin de me changer quelque peu les idées sur mon temps libre.


Je vous présente donc GoGame3DBoard. Pourquoi ce nom ? Tout simplement parce que c'est un jeu de Go avec un plateau 3D, signifiant que le plateau peut prendre plusieurs formes (e.g. un cube). Une autre raison est aussi que GoGame3DBoard ne retourne aucun résultat sur Google.
Pour faire simple, le jeu de Go est un jeu opposant deux joueurs qui posent, chacun à leur tours, des pions appelés "pierres" sur le plateau. Lorsque des pierres sont entièrement entourées par les pierres adverses, elles sont "mangés". C'est à dire que ces pierres sont alors retirées du plateau et des points sont donnés au joueur adverse. À la fin de la partie, le joueur ayant le plus de points gagne.

GoGame3DBoard étant écrit en HTML5/CCS3/JS, vous pouvez tester la dernière version à cette adresse : http://migdal.ovh/GoGame3DBoard/.


Comme je l'ai affirmé, ce projet est sans ambition, et devrait être relativement rapide à "terminer", ou tout du moins, à sortir une première release. Dans un premier temps, je pense sortir une version permettant de jouer en local.
Je pensais ensuite organiser un petit concours de la meilleure IA, où vous pourriez écrire votre propre IA (en JavaScript) et la faire combattre d'autres IA.
Et pour finir, via les websockets et un serveur node.js, faire une version "online" du jeu, mais j'en reparlerais le moment venu.


J'utiliserais ce sujet pour vous présenter les règles de ce jeu au fur et à mesure de leur implémentation, ainsi que pour vous donner régulièrement mes progressions.
Vous pouvez aussi me suivre sur Twitter, où je m'exprime occasionnellement en anglais.

[Denis Migdal]

Dans la première version, j'introduis le concept de "surface" et de "socle".

Un plateau est composé de plusieurs surface (en vert), eux même composés de "socles"/"plinth" (en bleu) sur-lesquels ont pourra poser des pierres. Les socles, au survol de la souris, sont mis en valeurs, ainsi que leurs socles "voisins". Les relations de voisinage permettent de savoir si une pierre est totalement "entourée" ou non.

Vous pouvez voir une représentation "éclatée" ci-dessous. Il est possible d'obtenir une représentation 3D à partir de ces surfaces en jouant avec les "3D transfoms" de CSS3. Cependant, je souhaites me contenter d'une représentation éclatée pour le moment. Non seulement car cela facilite mon travail de développement, mais aussi parce que la représentation 3D n'apporte qu'un plus esthétique.

Voici la description HTML correspondante :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
<go-area>
	<go-surface>
		<go-line>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
		</go-line>
		<go-line>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
		</go-line>
		<go-line>
			<go-noplinth></go-noplinth>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
		</go-line>
	</go-surface>
 
	<go-surface>
		<go-line>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
		</go-line>
		<go-line>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
		</go-line>
		<go-line>
			<go-noplinth></go-noplinth>
			<go-plinth></go-plinth>
			<go-plinth></go-plinth>
		</go-line>
	</go-surface>
</go-area>

Les relations de voisinage entre les socles sont générés automatiquement (haut, gauche, droite, bas), mais peuvent ensuite être ajoutées ou retirées (e.g. pour les relations de voisinages entre socles appartenant à des surfaces différentes) :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
<!-- add/remove neighbourgs relations -->
<script>
	for(i=0; i < 3; ++i) {
		neighbourgs.set("0:2:"+i, "1:2:"+i);
		neighbourgs.set("1:2:"+i, "0:2:"+i);
	}
</script>

Chaque socle a un identifiant unique généré automatiquement de la forme : "s:l:n" où :

• s est l'identifiant de la surface ;
• l est l'identifiant de la ligne dans la surface ;
• n est l'identifiant du socle dans la ligne.

Il est ainsi possible de dire que le socle a est le voisin du socle b en écrivant :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

neighbourgs.set(b, a);

Sachant que la relation de voisinage est normalement symétrique (ce n'est pas obligé), il faudra aussi écrire :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

neighbourgs.set(a, b);

Cela ne m'a pris que peu de temps (3h), surtout le temps de tester les webcomponents et 3D-transforms. Mais il vous est déjà possible de créer vos propres plateau, très simplement, et d'en modifier l'esthétique en jouant sur le CSS et/ou en donnant des attributs aux tags go-surface, go-line ou go-plinth.

[Denis Migdal]

J'avance plus rapidement que je le pensais, développer en HTML/JS me semble bien plus rapide qu'avec des langages comme C++ ou Java.

On peut désormais poser des pierres (petits carrés rouges ou blanc) dans les socles (carrés bleu). Un groupe est défini comme l'ensemble des pierres voisines et appartenant à un même joueur. Le voisinage d'un groupe est l'ensemble des socles voisins d'au moins une des pierres du groupe (ne contenant bien évidemment pas de pierres du groupe).

Voici un petit gif animé montrant la pose de pierre et les groupes/voisinages de groupes. Au survol d'un groupe, les pierres le constituant sont mis en valeur grâce à une bordure noire, de même que les socles constituant le voisinage du groupe.

Si je continue sur le même rythme, je pense que d'ici demain, je devrais avoir une première version "jouable".

[Denis Migdal]

Voici une première version "jouable".

Lorsqu'un groupe de pierres est totalement "entouré", il est mangé et retiré du plateau.
Les scores sont calculés mais pas encore affichés, il manque aussi la gestion de la fin du jeu.

Il n'est pas possible de jouer là où on se ferait directement "manger", c'est à dire qu'on peut jouer :

• si on a au moins un socle voisin sans pierres ;
• si on "rejoint" au moins un nos groupes de pierres ayant au moins un autre socle voisin sans pierres ;
• si on mange un groupe adverse en jouant ;

Je n'ai trouvé pour le moment que 3 façons de procéder :

• stocker un état "complet" du jeu, ce qui complexifie légèrement les changements d'états (e.g. pose de pierre, fusion de groupes de pierres, destruction d'un groupe de pierres) pour garder l'état du jeu à jour ;
• stocker un état "minimal" du jeu, ce qui complexifie légèrement les calculs (e.g. combien de socles voisins libre a un groupe ?) ;
• stocker un état "minimal" du jeu avec une petite gymnastique de l'esprit pour reformuler les choses ;

Les deux premières méthodes, nécessitent de faire des parcours assez important (e.g. parcourir l'ensemble des voisins du groupe de pierre). Cependant, je n'aime pas trop faire de parcours "inutiles" quand je peux l'éviter, quand bien même je n'ai pas vraiment de problèmes de performances.
La troisième méthode nécessite uniquement de parcourir les voisins du socle sur lequel on pose la pierre, cependant le code n'est pas forcément très explicite :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
function putPawnRule(plinth, player) {
 
	if( ! isPlinthEmpty(plinth) )
		return false;
	if( typeof player == "number")
		player = players[player];
 
	neighs = neighbourgs.get(plinth.id);
	canPlay = false;
	tmp_gp_freedoms = [];
	nbFriend = 0;;
	Array.from(neighs).forEach(function(element) {
 
		gp = groups[element];
		if( gp === undefined)
			canPlay = true;
		else {
			key = gp.plinths[0];
 
			if( tmp_gp_freedoms[key] === undefined) {
				tmp_gp_freedoms[key] = gp.freedom;
				if( gp.player == player) {
					++nbFriend;
				}
			}
			if( --tmp_gp_freedoms[key] == 0) {
				if(  gp.player != player )
					canPlay = true;
				else
					--nbFriend
			}
		}
	});
 
	if( nbFriend > 0)
		canPlay = true;
 
	//TODO cannot go in previous state
 
	return canPlay;
}

Je n'ai pas vraiment l'habitude d'utiliser JavaScript et plus généralement d'un langage non-typé et très permissif.
Cela est source de nombreuses erreurs assez bêtes :

• simples coquilles ;
• confusion entre les types : e.g. entre la référence sur un objet "socle" et l'identifiant d'un socle.

Je trouve aussi dommage que for in ne soit pas adapté au parcours de tableaux, ainsi pour le moment je parcours les tableaux associatifs avec forEach ce que je trouve un peu esthétique et me demande parfois d'utiliser des variables temporaires :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
var X;
Array.from(neighs).forEach(function(element) {
        X = ... ;
}
this.X = X;

Note : Je suis juste ici pour présenter un de mes passe-temps, sans aucune prétention. Ce n'est pas tant la destination qui compte pour moi que le chemin. Je veux donc vous parler du chemin que j'emprunte, et parler un peu technique.
Je peux comprendre que cela n'intéresse pas tout le monde, je ne suis cependant pas fermé aux remarques que vous pourriez me faire. Si vous n'aimez vraiment pas, vous n'êtes pas obligés de vous forcer à me lire.

[romnair]

Hi, je me permet de répondre vis à vis de ta note.

Pour ma part, je passe surtout pour lire/voir les avancés des différents projets, c'est plus le côté évolution qui me passionne, voir un projet grandir c'est très plaisant pour moi.
Souvent, je ne poste aucun message mais dans ton cas ta note est les pouces rouges m'ont fait réagir, je pense que ceux qui mettent des pouces rouges sans justification le font juste "à la volée" ou "pour le plaisir de nuire".

Bien que, personne ne réponde il est possible que la partie active de la communautés suivent tes avancé, mais dans ton cas aucune demande d'aide n'y besoin sont fait dans tes messages(c'est plus des comptes rendus) du coup il n'est pas forcément facile pour la communautés d'agir, de plus tu te base sur un jeu existant(aucun blame n'est fait ici) donc à moin que tu fasse des erreurs de gameplay évidentes personne ne prendrat la peine d'écrire un message car tu fait un bon travaille.

Après, sa peut dépendre des gouts par exemple moi je connais pas çe jeu et en plus techniquement parlant(vu que c'est surtout la raison pour laquelle ont poste ici) je n'est pas le niveau, ni l'expérience pour que mon intervention soit pertinente/utile.

Voila, sinon continue j'aime bien suivre les avancés dans l'ombre moi !

[Denis Migdal]

Bonjour, je te remercie pour ta réponse. Effectivement, je comprend parfaitement de ne pas avoir beaucoup de retours pour le moment, pour être honnête je m'y attendais.

Je réagissais surtout par rapport aux votes. S'il y a un quelconque problème, je suis ouvert à la discussion. Si par exemple il y a un problème avec la fréquence à laquelle je donne des nouvelles de ma progression, ou si je parle un peu trop technique, n'hésitez pas à m'en faire part.

Je viens aussi de regarder le forum plus en détail, que se passe-t-il exactement ? Presque tous les messages ont au moins un vote négatif.

[Denis Migdal]

Je suis actuellement en train de me casser la tête sur une règle pourtant toute simple en apparence :
"le plateau ne peut revenir à un état antérieur".

Il me faut donc stocker à chaque tour l'état du plateau et le comparer aux états précédent. Et c'est là que le casse-tête commence, de quelle façon représenter l'ensemble des états déjà visités du plateau pour :

• minimiser le coût mémoire ;
• faciliter l'insertion d'un nouvel état ;
• faciliter la comparaison de l'état actuel avec les états précédents.

La solution triviale serait de faire un tableau de log2(nbJoueurs + 1) * nbSocles bits donnant pour chaque socle si une pierre est posée, si oui, l'identifiant du joueur. Puis de faire un tableau de chacun des états antérieurs.
Par exemple |0|1|2|0| = rien sur le premier socle, une pierre du joueur 1 sur le second, une du joueur 2 sur le troisième et rien sur le quatrième socle.

Le coût mémoire est en O( nbTours * log2(nbJoueurs) * nbSocles).
Le coût d'insertion en O( log2(nbJoueurs) * nbSocles) (copie de l'état précédant + modification d'un élément).
Le coût de comparaison est en O( nbTours * log2(nbJoueurs) * nbSocles)
La question serait alors de savoir quelle structure de donnée je pourrais adopter pour réduire quelque peu ces complexités, et si je ne peux pas utiliser quelques astuces, par exemple :

• ai-je besoin de stocker tous les états / comparer les états à chaque tours ?
• les états "consécutifs" sont très proches entre eux, est-ce qu'on pourrait en tirer quelque chose ?

Pour limiter le coût mémoire, une solution pourrait être de ne stocker que les coûts joués O( nbTours ), avec éventuellement les pierres retirées O(nbTours * ?).
Une autre serait d'utiliser un arbre, regarder quel joueur est sur le premier socle, etc. Le coût en insertion est moindre, de même que pour la consommation mémoire, et la comparaison est en O( nbSocles ).

On pourrait aussi utiliser des hashs, mais si log2(nbJoueurs) * nbSocles > 512 (sha512), alors on a un risque de collision. Ce qui est le cas pour un plateau de 19*19 à 2 joueurs (722 bits). Cependant, même avec le paradoxe des anniversaires, le risque est négligeable.

Utiliser le nombre de pierres sur le plateau pourrait me permettre de réduire considérable le coût de la recherche avec un accès en O(1) à un sous-espace ne contenant que les états ayant X pierres.

EDIT: dès qu'un groupe devient "vivant" ie qui se trouve dans un état tel qu'il ne pourra jamais être mangé, on peut supprimer l'historique précédant. De même lorsqu'une pierre sera ajouté à ce groupe.
J'oubliais qu'un mouvais joueur pouvait "tuer" un tel groupe.

Vous auriez une idée d'un forum approprié de ce site où je pourrais poser ma question ?

[Woum_]

Question bête, quand on joue sur plateau (en vrai), comment on gère le :
"le plateau ne peut revenir à un état antérieur"

Je ne connais pas le jeu, du coup j'ai peut-être mal compris quelque chose !

A chaque tour tu fais une insertion et une comparaison du coup ? Une approche que j'ai eu comme ça par rapport à ce que tu as dis, tu ne peux pas garder l'idée de l'arbre (même si j'ai pas bien compris sa construction) et à coté garder un tableau qui te permet à tout moment d'accéder à la case X qui est "un sous-espace ne contenant que les états ayant X pierres" ? Les comparaisons et insertions devront être rapide du coup, non ?

PS : Les moins que tu t'es prie viens, à mon avis, d'une personne qui a mis de - à tout les posts. Je suppose même que c'est une personne qui s'est mise à bouder puérilement après des remarques qui lui ont été faites. Mettre des - partout, je colle pas mal niveau puérilité. Ne t'en formalise pas, ton post est intéressant !

[Denis Migdal]

A chaque tour tu fais une insertion et une comparaison du coup ?

Au tour n je fais une insertion et (n-1) comparaisons. Il faut en effet que je compare l'état actuel avec tous les états précédents.

Une approche que j'ai eu comme ça par rapport à ce que tu as dis, tu ne peux pas garder l'idée de l'arbre (même si j'ai pas bien compris sa construction) et à coté garder un tableau qui te permet à tout moment d'accéder à la case X qui est "un sous-espace ne contenant que les états ayant X pierres" ?

C'est presque l'idée que j'ai trouvé hier soir.

J'essayerais de le décrire plus en détail ce soir, mais grosso-modo :

• Je fais un arbre, non pas en fonction des socles, mais en fonction des coups joués (beaucoup plus efficace) ;
• Je sépare l'état du jeu en plusieurs sous-états, en effet, les modifications sont locales, ce qui permet de réduire considérablement les coûts.
• J'utilise un tableau pour un accès en O(N) aux sous-états ayant X pierres ;

Diviser en sous-état permet de gagner légèrement en complexité au pire, mais donne des gains énormes lorsqu'on va réutiliser des sous-états. Diviser selon les joueurs fait gagner log2(nbJoueurs + 1) en mémoire lorsqu'on ne mange pas un groupe de pierres.
Diviser l'état par "zones", divise le coût mémoire par le nombre de zones (tout en rajoutant le coût d'un pointeur (2/4/8 octets) par zones) ;


Cependant, il reste plusieurs façon de représenter les états :

• un champ de bit (un peu comme la méthode naïve) ;
• le socle où on a posé la pierre + un pointeur vers l'état précédant ;
• un hash ;

Le hash n'est pas disponible de base dans JavaScript, de plus, le calcul d'un hash est "coûteux". En 19*19 le coût d'un état est de :

• 32 octets pour un SHA512 ;
• 19*19/8 = 45 octets pour un champ de bit, avec sous-états séparés selon le joueur ;
• log2(19*19)/8 + sizeof(pointer) = 2 octets + sizeof(pointer) => 6 ou 10 octets pour un "arbre".
• 10*10/8 + 4*2 = 20.5 octets octets pour un champ de bit, avec sous-états séparés selon le joueur et le plateau en 4 zones de 10x10;
• 19*19*log2(nbJoueurs + 1)/8 = 90 octets pour 2 joueurs;

Cependant, la structure en arbre demande des comparaisons / insertions plus coûteuses mais aussi plus poussées :

• lorsqu'on mange un groupe, il va falloir rajouter des "faux" états pour maintenir la structure de l'arbre ;
• lorsqu'on insère, on peut utiliser un autre état précédant avec un autre coup pour arriver au même état, et donc faire en sorte que que les comparaisons soient plus rapides ;

La solution champ de bit est assez intéressante de par sa simplicité alors que la solution "arbre" est intéressante de par son coût mémoire très faible. Si je pouvais trouver une astuce pour avoir un arbre avec des propriétés similaire au champ de bit, ce serait parfait.
EDIT : Je suis en train de me demander si je ne peux pas stocker mon champ de bit sous forme d'arbre un peu "spécial", le stockage coûterait alors au pire (sizeof(pointer) + log2(19*19)/8 ) * nbPierres, avec un tableau d'états "faux" avec en index le nombre de pierres. En s'arrangeant un peu on devrait pouvoir s'approcher des performances mémoires de l'arbre (en gros c'est le même arbre, mais avec plus d'états "faux" de sorte à accélérer les comparaisons/insertions). Le tout serait de savoir comment insérer en détail.

Voir même d'utiliser un "mix" des deux représentations.

Ne t'en formalise pas, ton post est intéressant !

Je vous remercie pour ces mots d'encouragements.

[Denis Migdal]

Bonjour,

Mes derniers messages n'étaient pas forcément très clairs, je vais essayer de prendre le temps nécessaire afin de vous présenter la structure que j'ai actuellement choisi.

Pour chaque état, je stocke une liste chaînée de chaque coups joués, c'est à dire un triplet (n° socle, n° joueur, ptr vers état précédant).
Chaque élément de cette liste chaînée est stockée dans un tableau d'ensembles dont l'indexe est le nombre de pierres présent sur le plateau - 1. Ainsi tab[0] donne la liste des états ayant 1 pierre sur le plateau.

Revenons au triplet (n° socle, n° joueur, ptr vers état précédant) des états. Le pointeur vers l'état précédant peut soit être un pointeur "normal" sur 4 ou 8 octets, soit un couple (pierres état précédant - 1, n° de l'état dans l'ensemble). C'est à dire que (0, 2) est le 2ème état de tab[0]. Le nombre de pierres de l'état précédant pouvant être déduit de l'état courant, on a juste besoin de stocker (n° de l'état dans l'ensemble), soit (2). Ce qui ne nécessite que 2 octets.

Le coût en mémoire d'un état est donc en O( log2(nbSocles) + log2(nbJoueurs) + 2*8 bits. Le coût en insertion en O( 1 ).


Cependant, lorsqu'on va manger un groupe de pierres, la structure de l'état va changer. J'ai toujours besoin du triplet (n° socle, n° joueur, ptr vers état précédant) afin de conserver l'historique des coûts, mais je veux aussi réduire le coût en comparaison d'un état qui est en O(nbTours), donc en O( tourActuel * tourActuel / 2) pour comparer avec tous les états précédant, sans compter qu'il faudra recalculer si des pierres sont mangées ou non.

Je vais donc, lors de l'insertion, ajouter à l'état un pointeur vers un état antérieur de référence, ainsi que la liste des coups à jouer pour aller à l'état actuel à partir de cet état antérieur. Ce qui permet de réduire le coût des comparaisons, et éviter de recalculer quelles pierres ont été mangées.
Cela a certes un coût mémoire, mais permet de gagner en temps de calculs. S'il y a trop de coups à jouer, on peut stocker un tableau de bits pour gagner en mémoire et en rapidité de comparaison.

Par exemple pour un état 101000, je peux partir de l'état existant 001000 et faire comme si le joueur avait joué (0, 1). Le problème est alors de choisir correctement cet état précédant, ainsi que les coups à "jouer" afin d'avoir des heuristiques pour les comparaisons et insertions futures.


Je peux par exemple ne regarder que le dernier état inséré dans chaque ensemble du tableau pour choisir l'état précédent de référence. Pour prendre un exemple, c'est comme si je faisais des retours en arrières (Ctrl+Z) jusqu'à arriver à un état qui me plaît (de référence) et re-poser des pierres pour atteindre l'état actuel.
Cette méthode a l'avantage d'avoir une insertion simple et permet des "comparaisons rapides". De plus, le triplet (n° socle, n° joueur, ptr vers état précédant), donne déjà la pose d'une pierre qui n'a donc pas besoin d'être répété dans la liste des coups à jouer.
Les "comparaisons rapides" sont assez intéressantes : si lors d'une comparaison d'un état avec l'état actuel, (sans destruction de pierres) on arrive à un état inséré en dernier dans l'ensemble des états, alors les deux états sont égaux. On devrait aussi avoir plus de chances de trouver rapidement un état identique en parcourant les états par ordre inverse d'insertion.

Pour être plus simples, les états les plus "récents" sont les plus susceptibles d'être un état de "référence" de l'état actuel, et le dernier état de chaque ensemble est un état de "référence" de l'état actuel lors d'une pose simple d'une pierre (ie sans manger un groupe).


Cependant, il n'a aucune garantie de donner l'état de référence, parmi les états existant le plus proche à l'état actuel. Cependant, on risque de perdre les heuristiques précédentes en cherchant à avoir une recherche de l'état de référence plus poussée (et donc plus coûteuse). Je pense qu'il est donc inutile de chercher à aller plus loin.


EDIT : Les liens entre mes états sont mono-directionnels. En les rendant multi-directionnels, on perd en mémoire, mais on garde la même complexité : un rajoute juste un pointeur par état.
Ce serait en fait un arbre tout bête. Ceci devrait alors faciliter la recherche et la comparaison. Cependant, il faudrait pouvoir équilibrer l'arbre de sorte à avoir quelques heuristique.

On peut conserver l'heuristique précédente en ordonnant la liste des fils d'un nœud en plaçant le fils "utilisé" lors de l'insertion d'une feuille en dernier. Pour choisir sur quel nœud rajouter une feuille on pourrait avoir plusieurs solutions :

• sur le nœud le plus éloigné de la racine (gain mémoire) ;
• ou avec des considérations de probabilités (gain temps) ;

Pour gagner en temps, il faut que les premiers nœuds soient les plus discriminants possibles.

[Denis Migdal]

Pour le moment, cela peut changer, je pense consacrer mon samedi sur ce projet, et y contribuer très ponctuellement les soirs de semaine. Donc plutôt faire du développement le samedi et en semaine, discuter ici avec vous, à justifier ma démarche ou à me casser la tête sur une problématique.

Je vais donc ici commencer à justifier ma démarche, pour poser un contexte, mais aussi briser un peu la glace. Puis je vous proposerais de continuer la réflexion sur ce stockage de l'historique des états du plateau.


Justifications

Je ne peux travailler que très ponctuellement les jours de semaines, cela ne vaut donc pas vraiment la peine de développer. De plus, ce sont surtout des travaux de réflexions, que ce soit en me levant, en prenant ma douche (c'est dingue le nombre d'idées qu'on peut trouver sous sa douche), en me rendant sur mon lieu de travail ou en me couchant (et me relevant pour aller noter mon idée).

Si les informations ou idées que je poste ici sont un peu "déstructurée", c'est principalement parce que je les note quand elles me viennent (j'essaye de tout même d'attendre une journée/nuitée que l'idée mûrisse un peu), ce qui me permet de les formaliser et de les reformuler. Il n'est alors pas rare que j'ai une idée ou trouve une solution justement en reformulant le problème ou quelques instants après. Il peut donc m'arriver d'éditer mes messages.

Je ne regarde pas l'état de l'art, je ne vais pas voir ce que font les autres, tout est issue de mes propres connaissances et réflexions. Je n'exclue pas qu'il puisse m'arriver un jour d'aller me renseigner à ce sujet, mais pour le moment j'estime ne pas en avoir le temps. Ce n'est aussi tout simplement pas mon but.


Bien que je sois, par expérience un partisan du "keep it simple, stupid" (KISS), et de "commencer par un prototype bidon, simple puis de l'améliorer", j'aime bien aussi me casser la tête et j'ai une allergie au gaspillage. J'ai donc besoin de me laisser le temps de la réflexion, d'où le fait que je préfère développer le samedi et me laisser la semaine pour réfléchir.
En gros voici mon schéma de pensée : [solution triviale] => "Aaaarg" *allergie* => solution compliquée => solution encore plus compliquée => "mais oui je suis con, il y a plus simple" => solution plus simple => "oui, mais c'est dommage, on a des priori sur les informations qu'on exploite pas" => solution compliquée => "bon, on va se calmer là" => solution plus simple.

Vous pouvez donc comprendre que c'est un joyeux bordel dans ma tête .
Plus sérieusement, dans le cas qui m'intéresse, la question du coût mémoire peut devenir importante. Il suffit qu'un petit rigolo choisisse de créer un grand plateau, avec un grand nombre de joueur, que la partie s'éternise pour qu'elle me coûte quelques méga en mémoire vive avec une solution triviale/naïve. Il suffit juste de quelques malins pour provoquer un Denial of Service (DoS) du serveur en saturant sa mémoire vive. De plus, comme mon serveur risque d'être un raspberry sur lequel j'héberge déjà plusieurs services, je n'ai pas non plus envie de faire trop de calculs coûteux et inutiles, ni de prendre trop de mémoire vive.
Même si je ne vous cache pas, que mon allergie au gaspillage doit aussi y être pour beaucoup.

De manière générale, il est toujours important de penser à l'algorithme et à sa complexité. Je ne parle pas ici de micro-optimisation, mais bien de choisir des structures et des algorithmes pour réduire les complexités en coûts mémoires et en temps. Mais pas que, j'essaye aussi de trouver un algorithme relativement simple, il faut donc que je me recadre quand je vais un peu trop loin.



Réflexion

Pour revenir à notre problème de stockage des états, je comparais les états en partant du dernier coup jouer pour remonter au premier coup. Cependant, en ajoutant un pointeur, on peut comparer les états dans "l'autre sens" ie du premier coup au dernier coup joué. Ce qui devrait être légèrement mieux en terme d'insertion et de comparaison.

Je récapitule les propriétés de cet arbre doit avoir :

• les états ayant X pierres doivent avoir une profondeur de X ;
• à chaque nœuds, dans l'idéal, il faudrait n'avoir qu'un seul sous-arbre à parcourir, les autres sous-arbres ne pouvant pas contenir l'état recherché (gain temps);
• lors d'une insertion, il faudrait insérer l'état à partir d'un nœud existant d'une profondeur maximale (gain mémoire).

Note : ici p(a,b) signifie pierre posée sur le socle a par le joueur b.

Sachant, qu'il est possible de rééquilibrer l'arbre après coup et d'en modifier les états. On peut même ajouter de faux états afin de pouvoir faciliter les comparaisons au détriment de la mémoire.

Une solution triviale serait de commencer à la racine, prendre le premier fils e.g. "p(2,1)", de se demander "est-ce que j'ai une pierre sur le socle 2 posée par le joueur 1 ?". Si oui, je rechercherais et insérerais dans ce sous-arbre, si non, je passe au fils suivant. Cela coûte en mémoire, car la première pierre posée peut être mangée en début de jeu puis être reposée 100 tours plus tard. Il faudra alors insérer soit un état du jeu complet soit renseigner ~100 pose de pierres. Cependant, on a un seul chemin à suivre, avec la garantie de l'unicité de l'état inséré.

Une solution "standard" serait d'avoir un opérateur de comparaison entre deux états et de faire un arbre binaire de recherche... mais cela demanderait de stocker l'état complet du jeu à chaque feuilles. Or on a déjà une solution plus rapide en utilisant un tableau d'ensemble ayant en index le nombre de pierres présentes sur le plateau.

Une autre solution consisterait à faire un parcours de l'arbre afin de trouver tous les nœuds sur lesquels on pourrait insérer le nouvel état, et trouver le nœud le plus approprié, et même de réorganiser les autres nœuds afin d'optimiser les recherches futures.
Ce qui est paradoxal, pour avoir une structure qui permettrait de rechercher plus rapidement, il faut rechercher tous les états précédant possibles lors d'une insertion. Or on effectue la recherche pour insérer un nouvel état. Donc à moins d'avoir une méthode rapide de recherche des états similaires à une pierre près, cela n'apporterait pas grand chose.

Pour éviter cela, une dernière solution serait d'avoir des nœuds ne servant que de discriminant et les feuilles représenteraient les états. On a donc un coût mémoire, du fait des nœuds ajoutés, autant revenir donc sur la solution triviale.


Note : j'ai vu que vous sembliez avoir bien aimé ma dernière intervention, donc je vais essayer de continuer dans cette direction.

[Denis Migdal]

Bonjour,

Je reviens ici pour vous donner quelques nouvelles.


Je prends pour le moment une petite pause dans ce projet au profit d'un "projet" académique effectué parallèlement à ma thèse (donc sur mon temps libre).
On va en effet soumettre un article à une conférence d'ici la fin de l'année, je vous donnerais plus de détails fin février s'il est accepté.


Je pense pouvoir reprendre GG3DB entre janvier et mars si je n'ai pas d'autres deadlines. Vous aurez donc de mes nouvelles d'ici quelques temps.

[Denis Migdal]

Comme promis je vous donne quelques nouvelles.


L'article en question n'a pas été accepté, je vais donc continuer à travailler dessus. Parallèlement, d'autres idées de recherche se concrétisent, j'ai donc difficilement le temps de reprendre ce hobby pour le moment.


Je vous souhaite donc une bonne continuation, même si ma présence sous cette identité a été courte. J'espère revenir sur DVP dans quelques temps, mais pour d'autres raisons.