Discussion :

[samia2]

bonjour mes amis
je vous demande de m'aider ,j'ai un problème on a un projet sur les arbres binaires et je rencontre des difficultés dans mon projet j'ai écrit les structures de donnes correspondantes mai je ne sais pas comment construire l'arbre
c'est mon projet:
On considère un jeu de cartes dans lequel deux joueurs (A et B) enlèvent à tour de rôle soit la carte la plus à gauche, soit la carte la plus à droite d’une rangée de cartes disposées linéairement. A chaque fois qu’un joueur tire une carte, il gagne la valeur indiquée dessus. Le jeu s’arrête quand toutes les cartes sont tirées et le joueur qui a le plus de points gagne la partie.
Une situation est définie par le joueur à qui le tour, un n-uplet représentant les cartes restantes et les gains respectifs de A et de B.
Ex: <B,(4,10,8,5,1,2),(15,9)> représente la situation où B doit jouer, il reste les cartes suivantes : 4 10 8 5 1 2, et A a déjà gagné 15 points et B en a gagné 9 (A gagne donc 6 points).
Une partie peut donc être représentée par un arbre binaire de situations
on désire développer un programme permettant de simuler une partie entre un humain et une machine intelligente. L’intelligence de la machine est assurée par un algorithme lui permettant d’évaluer le gain (ou la perte) provoqué par le tirage d’une carte. En effet, à chaque situation, la machine a le choix entre les deux cartes aux bords et doit choisir celle qui maximise son gain dans tout le jeu et non pas la plus grande
1. Créer une configuration initiale aléatoirement.
2. Simuler une partie.
3. Déterminer le gain minimal d’un joueur donné à partir d’une situation initiale sans développer l’arbre de jeu (penser récursivement).

les structures de données que j'ai écrit sont:

Code :

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

1
2
3
4
struct gain{int gainj,gainm;};/*pour les gains joueurs et machine*/
struct carte{int t[n],nb_carte;};/*por la liste des cartes*/
struct element{gain a;carte t;char c;};/*ce sont les éléments du nœud*/
struct noeud{element e;noeud *sag,sad;};

je ne sais pas comment je veux commencer dans mon projet je désire que vous m'aider et merci beaucoup à vous

[Flynet]

Si je comprends bien ton arbre binaire va être composé de tous les chemins possibles de la partie. Donc en début de jeu, il faut générer cette arbre en fonction des cartes présentes.

Renseigne toi sur la structure d'un arbre binaire. Il y aura un élément root, des structures Element représentant les noeuds avec un pointeur sur l'élément à gauche et un autre pour la droite ainsi que la valeur de la situation (gain?) actuelle.

La branche à droite aura plus de poids que celle à gauche donc un gain supérieur. Ton chemin est tout tracé .

[samia2]

Si je comprends bien ton arbre binaire va être composé de tous les chemins possibles de la partie. Donc en début de jeu, il faut générer cette arbre en fonction des cartes présentes.

Renseigne toi sur la structure d'un arbre binaire. Il y aura un élément root, des structures Element représentant les noeuds avec un pointeur sur l'élément à gauche et un autre pour la droite ainsi que la valeur de la situation (gain?) actuelle.

La branche à droite aura plus de poids que celle à gauche donc un gain supérieur. Ton chemin est tout tracé .

salut mon ami
mon probleme est comment construire l'arbre je ne sais pas comment je veux ecrire le code correctement tu peux m'aider dans l'ecriture du code en language c et mercie a vous.

[diogene]

Sur les arbres en C, tu peux consulter le tutoriel Introduction aux arbres

[kwariz]

Bonjour,

Pour comprendre ce qui se passe on peut faire des dessins, même si dans un forum ce n'est pas forcément très pratique
Donc on va dessiner ta structure ainsi :


Prenons pour exemple le jeu [1,10,5,10]. La racine de ton arbre ressemblera à :

Ce noeud est facile à créer car tu possèdes toutes les infos pour ça. À partir de ce nœud tu peux créer les sous arbres correspondant à chaque choix. Déjà les deux sous arbre auront comme joueur l'autre joueur, pour le sous arbre gauche (=le joueur a choisi de prendre la carte à gauche) le tableau sera le tableau courant privé de son élement le plus à gauche, le score du joueur A sera augmenté de la valeur de la carte tirée. On obtient donc un noeud comme celui-ci comme racine du sous arbre-gauche :
.
La construction de la racine du sous arbre droit est similaire et on obtient :

Tu peux ensuite créer les liens entre ces nœuds :


Là on a une méthode qui à partir d'un nœud lui en ajoute deux, chacun avec le bon joueur, un tableau de taille n-1 et le score mis-à-jour.
Il faut faire attention quand le tableau n'a qu'un élément. Dans ce cas, qu'on joue «à gauche» ou «à droite» on obtient le même résultat. Comme il est souvent préférable de ne pas dupliquer des positions de jeu identiques, je te propose de ne créer que le sous arbre gauche et de laisser le droit vide :

Dans ce cas il n'est pas nécessaire de construire l'arbre plus loin car c'est la fin du jeu (plus de carte à jouer).

On vient donc de créer une méthode récursive pour construire ton arbre. L'algo est :

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
noeud_dilater( n : noeud )
début
  si longueur(n.tableau)=1 alors
    n.sag = noeud_creer(autre_joueur(n.joueur), // le joueur
                        [], // le tableau de cartes
                        gain_ajouter(n.gain, valeur_carte_gauche(n.tableau)), // màj des gains
                        NULL, // sag
                        NULL) // sad
  sinon
    n.sag = noeud_creer(autre_joueur(n.joueur), // le joueur
                        [2:k], // le tableau de cartes sans la carte de gauche
                        gain_ajouter(n.gain, valeur_carte_gauche(n.tableau)), // màj des gains
                        NULL, // sag
                        NULL) // sad
    n.sad = noeud_creer(autre_joueur(n.joueur), // le joueur
                        [1:k-1], // le tableau de cartes sans la carte de droite
                        gain_ajouter(n.gain, valeur_carte_droite(n.tableau)), // màj des gains
                        NULL, // sag
                        NULL) // sad
    // on a créé les racines des sous arbres, ne reste plus qu'à les dilater également
    noeud_dilater(n.sag)
    noeud_dilater(n.sad)
  fin si
fin

Ensuite il te faut la procédure pour créer la racine de la simulation :

Code :

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

1
2
3
4
5
6
noeud créer_simulation(cartes : int[], nbre_carte : int)
début
  racine = noeud_creer('A', cartes, (0,0), NULL, NULL)
  noeud_dilater(racine)
  renvoyer racine
fin

Implémenter ça en C peut être un peu fastidieux ...
Si j'étais toi, je me créerais une structure simulation qui contient le tableau de cartes du départ. Les nœuds eux ne contiendront qu'un pointeur vers ce tableau, ainsi que deux indices : un pour la carte la plus à gauche dispo, l'autre pour la carte la plus à droite disponible. Mais bon, ce ne sont que des détails d'implémentations

Un arbre complet donnerait :


Voilà pour la première partie, la seconde est un peu différente. Essaye déjà de coder ça et on embrayera par la suite


Plusieurs remarques:

• L'arbre peut vite devenir grand. On peut (doit ?) se poser la question sur le nombre de noeuds qu'il va contenir. On peut facilement montrer que pour N cartes au départ tu vas construire un arbre dont les N premiers niveau sont complets et le dernier rempli à moitié. On aura donc hauteur arbre = N+1, nombre de nœuds = 2^N-1 + 2^(N-1)=3x2^(N-1)-1 (pour N>0). Si on estime que la structure nœud fait dans les 40 octets (à vue de nez sur une architecture 32bits en partageant le tableau de carte ...), alors 15 cartes font 2Mo, 20 cartes frisent les 60Mo, 25 cartes les 1.9Go (ce qui est énorme pour une architecture 32bits ...).
• On peut (doit ?) remarquer que le dernier niveau de nœuds ne sert pas à grand chose, on pourrait (devrait ?) s'en passer pour gagner de la place si c'est utile.
• On peut aussi se dire qu'à un moment donné on a pas forcément besoin d'avoir tout l'arbre de développé ...

[ternel]

En fait, la situation présente une caractéristique attrayante.

Pour une représentation plus complete de l'état, on peut naviguer dans l'arbre en modifiant l'état lui-même, et donc ne pas construire l'arbre du tout.

on aurait une structure contenant:
la pile de carte
la liste des identifiants de cartes piochés par chaque joueur.