[C++]Question sur les listes chainées et le conteneur Vector

Helldream · Le 29/07/2007, à 14:57

Rebonjour,

Comme promis, voici les questions concernant les listes chainées, et plus particulièrement le conteneur Vector.

Pour l'IA du jeu d'awale, j'aimerais étudier les différents coups réalisable, puis les coups que l'adversaire pourra jouer, les répliques que pourra faire l'ordinateur... Bref, prévoir plusieurs coups à l'avance, afin de ne pas tomber dans des pièges (du genre "je te donne 3 pions, mais le coup d'après je t'en pique le double). Pour ceux qui ne connaissent pas le jeu d'awale, c'est très simple, chaque "camp" a 6 trous. On a donc le choix entre 6 coups à chaque tours.

Imaginons que l'IA puisse prévoir 3 coups d'avance (et leur répercussion), on se retrouve avec 6^(3*2)=46656 cas possibles. (à chaque cas correspond plusieurs variables, telles que le nombre de pions pris, le nombre de pions perdus, la configuration du jeu finale, pour les prochains coups à étudier, ...). Pour 4 coups d'avance, on a 1 679 616 cas, pour 5 coups 60 466 176, etc.

Biensûr, il s'agit ici du nombre maximum de cas possibles : il peut y avoir moins de 6 possibilités de coup pour un tour (s'il y a des cases vides), certains "branches" pourront être stoppées, si trop de graines ont étées perdues par exemple... Mais bon, qui peut le plus peut le moins.

Je compte donc créer une structure contenant les informations à conserver pour chaque coup, et créer un conteneur Vector organisant le coup (pour créer un genre d'arbre organisant les coups possibles par profondeur de recherche).

Pour faire cette étude de possibilités, je compte mettre en place un système récursif (je lui donne le nombre de coups à étudier, et il boucle jusqu'à être arrivé à la profondeur voulue).

Passons aux questions :

1/ Le choix du conteneur (Vector) vous semble-t'il cohérent? Le but étant de faire un genre de liste chainée qui pour chaque coup, donne les 6 (ou moins) répliques possibles, puis pour chaque répliques, les 6 coups qui pourront en découler etc. D'après mes recherches, ce serait le type approprié, n'y ayant pas vraiment d'ordre de tri (ce n'est pas un classement), ni de sortie (pas une pile ou une queue), et n'y ayant pas de clé d'indexation. Mais bon, je préfère demander...

2/ Est-il envisageable de stocker dans un conteneur, un nombre important de données (on peux imaginer devoir stocker quelques millions de possibilités)? J'aimerais conserver un maximum de coups, afin de pouvoir avoir une IA "voyant plus loin que le bout de son nez", prète par exemple à sacrifier quelques graines en sachant que 2 ou 3 coups après, elle pourra en gegner plus (comme pourrait le faire un joueur humain). Qu'est ce qui définit la limite maximum du nombre de données qui pourront être stockées? La mémoire vive? Et quelle est cette limite?

Merci d'avance pour vos retours

Luc Hermitte · Le 30/07/2007, à 10:48

Regarde la FAQ C++ sur developpez. Il y a une Q/A relative à quel conteneur de la SL choisir.

Helldream · Le 30/07/2007, à 21:22

Merci de ta réponse.

Je connais cette page : http://c.developpez.com/faq/cpp/?page=S … _conteneur et c'est la première chose que j'ai consulté avant d'écrire ici. Mais hélas, c'est loin de répondre à mes deux questions... :S

littleblackdog · Le 01/08/2007, à 10:40

bon, j'ai qu'une très vague idée de ce que tu veux faire mais des structures appropriées me paraissent être :

typedef struct {
 int nbPionsPris;
 int nbPionsPerdus;
 ...
}coup;

typedef struct schoix {
  coup *c;
  schoix *ChoixSuivants[6];
}choix;

rien de vraiment compliqué, donc.
après, si t'arrives à gérer quelque chose d'approchant avec un Vector, tant mieux. j'ignore l'efficacité en termes d'accès et de stockage de ce conteneur, donc ne peux te garantir que c'est mieux ou moins bien qu'autre chose.

une chose est sûre, en termes de stockage des données, ça me parait pas mal grand, ce dont tu parles. pour arriver à gérer ça, tout dépend de la façon dont tu t'y prends : si c'est que pour consultation, ça devrait passer. mais si tu fais constamment des écritures/réécritures de données, avec parcours de tout l'arbre de choix, il te faudra une machine un minimum puissante. parce que sur un ordi d'il y a 7 ans, ...

je serais toi, j'essayerai de commencer par une IA un peu "bébête", en particulier en ne prévoyant que 2 coups d'avance, histoire de voir comment ça gère dans un premier temps. quitte à complexifier après pour customiser ton IA.

après, je sais que l'IA est une discipline à part entière, et que y a déjà des gens comme Djikstra ou Belman qui ont planché sur divers problèmes pour les résoudre de façon intelligente. cependant, même si j'aurais bien aimé, je n'ai pas suivi cette matière à la fac. donc mon conseil : renseigne-toi là dessus avant de coder. y a probablement de super algorithmes bien efficaces qui n'attendent que tu les découvres ... si j'ai bien pigé, ton but est d'apprendre à coder en C++, pas de plancher des jours sur un problème d'IA pour finir par réinventer la poudre ... si ?

[edit] en fait, je viens de m'appercevoir que je t'ai donné des structures, pas des classes. au temps pour moi (c't'habitude du C..), mais l'idée est là.

Dernière modification par littleblackdog (Le 01/08/2007, à 10:42)

trucutu · Le 01/08/2007, à 13:33

Helldream a écrit :

J'aimerais conserver un maximum de coups, afin de pouvoir avoir une IA "voyant plus loin que le bout de son nez", prète par exemple à sacrifier quelques graines en sachant que 2 ou 3 coups après, elle pourra en gegner plus (comme pourrait le faire un joueur humain). Qu'est ce qui définit la limite maximum du nombre de données qui pourront être stockées? La mémoire vive? Et quelle est cette limite?

Tu veux clairement implémenter un algorithme de type minmax utilisée de base dans la théorie des jeux. Si tu as du temps, plutôt que d'avoir une confiance absolue dans la puissance de ta machine, tu pourrais envisager un algo qui coupe certaine branche de l'arbre redondantes (alpha-beta), pour réduire le nombre de possibilités.

Enfin je dis ça, je ne connais pas le jeux dont tu parles...

littleblackdog · Le 01/08/2007, à 14:05

trucutu a écrit :

Enfin je dis ça, je ne connais pas le jeux dont tu parles...

pratique le Google-Fu !

au fait, j'y pense ... "Sébastien Hélan", "Helldream", deux fans d'awalé dont le nom commencent pareil ... cette ressemblance est une coïncidence, ou .. ?

Dernière modification par littleblackdog (Le 01/08/2007, à 14:11)

Helldream · Le 01/08/2007, à 20:06

Ou... Rien

En effet, je connais bien ce site, je suis fan d'awale... Mais je n'en suis pas le concepteur

shelan01 · Le 15/02/2008, à 14:58

Bonjour, et non aucun rapport entre "Sébastien Hélan" et "Helldream".
Mon pseudo est shelan01
ça me fait assez étrange de retrouver trace de mon jeu d'awale sur mon site préféré (et oui je suis passé à Ubuntu il y a déjà ... 2 ans (que 2 ans dirons certain...)

Pour répondre à une de tes questions si ce n'est pas trop tard, j'utilise pour mon jeu la méthode de stockage des coups déjà calculés (un arbre) comme ça à chaque coup je ne calcule que la dernière branche

voila voila ... je reste à ta disposition

Sébastien H.

Aurel34 · Le 15/02/2008, à 19:21

les algos minimax et ses variances (donc alpha-beta cité ici) me semblent aussi bien adaptés à ton problème. Ils permettent d'explorer l'arbre des possibilités "intelligemment", et sont par exemple utilisés pour les jeux d'échec.

Un bon (vieux) tuto est dispo sur le site alrj (plus updaté depuis des années et c'est dommage):
http://www.alrj.org/docs/algo/minimax.php
http://www.alrj.org/docs/algo/negamax.php
http://www.alrj.org/docs/algo/alpha-beta.php
http://www.alrj.org/docs/algo/scout.php
http://www.alrj.org/docs/algo/ameliorations.php

il y a vraiment l'essentiel, et si tu veux aller plus loin il faudra consulter des ouvrages spécialisés (genre le Russel).

Le Farfadet Spatial · Le 15/02/2008, à 23:38

Salut à tous !

J'ai peut-être lu un peu vite, mais personnellement, lorsqu'il s'agit d'avoir recours à une liste chaà®née, je préfère utiliser les listes chaà®nées... Donc, j'utiliserais plutà´t un conteneur de type list.

Pour ton intelligence artificielle, je te conseille de lire les sixième et septième parties du tutoriel pour faire un morpion avec la SDL sur le site developpez.com : http://fearyourself.developpez.com/tuto … ion/part6/.

à€ bientà´t.

Le Farfadet Spatial

Aurel34 · Le 16/02/2008, à 09:47

Le Farfadet Spatial a écrit :

J'ai peut-être lu un peu vite, mais personnellement, lorsqu'il s'agit d'avoir recours à une liste chaà®née, je préfère utiliser les listes chaà®nées... Donc, j'utiliserais plutà´t un conteneur de type list.

limite pour un parcours de graphe un stack suffit (je crois qu'il utilise un deque par défaut, mais tu dois pouvoir changer la policy pour utiliser une liste)

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 29/07/2007, à 14:57

[C++]Question sur les listes chainées et le conteneur Vector

#2 Le 30/07/2007, à 10:48

Re : [C++]Question sur les listes chainées et le conteneur Vector

#3 Le 30/07/2007, à 21:22

Re : [C++]Question sur les listes chainées et le conteneur Vector

#4 Le 01/08/2007, à 10:40

Re : [C++]Question sur les listes chainées et le conteneur Vector

#5 Le 01/08/2007, à 13:33

Re : [C++]Question sur les listes chainées et le conteneur Vector

#6 Le 01/08/2007, à 14:05

Re : [C++]Question sur les listes chainées et le conteneur Vector

#7 Le 01/08/2007, à 20:06

Re : [C++]Question sur les listes chainées et le conteneur Vector

#8 Le 15/02/2008, à 14:58

Re : [C++]Question sur les listes chainées et le conteneur Vector

#9 Le 15/02/2008, à 19:21

Re : [C++]Question sur les listes chainées et le conteneur Vector

#10 Le 15/02/2008, à 23:38

Re : [C++]Question sur les listes chainées et le conteneur Vector

#11 Le 16/02/2008, à 09:47

Re : [C++]Question sur les listes chainées et le conteneur Vector

Pied de page des forums