Bonjour à tous !
 
 J'ai actuellement un projet en cours d'algo et je dois réaliser un jeu de dames. Le probleme que j'ai est la représentation du damier. Je comptais utiliser un tableau[10][10] d'entiers, mais  
question utilisation de la mémoire, vu que je devrai en stocker des centaines (construction d'un arbre minimax) ce n'est pas top...
 Donc je pensais plutot utiliser quelques entiers et pouvoir mettre directement leurs bits à 0 ou 1 et comparer, etc... Je ne trouve rien là dessus...
 En fait, je voudrais me servir d'entier (ou de tout autre type) comme tableau de bits directement accessibles. Pour positionner le 3ieme bit  à zéro de i, on ferais ainsi:
 int i;
 i[3] = 0; //acces direct aux bits
 
Est ce que quelque chose de ce type existe ou voyez vous un autre moyen ?

tu as les bitset en C++
mais c'est pas top si tu programmes en C
sinon en C,
tu peux definir des donnees
sur 1 ou n bits (n differents de 8).
 
struct packed_struct {
   unsigned int e1:1;
   unsigned int e2:1;
   unsigned int e3:1;
   unsigned int e4:1;
} packed;
 
A+
LEGREG

Ah oui ! Mais...
dans ce cas, là, tu es sur que la place en memoire se limite à 4 bits (ou 8, ou 16 pour des histoires de taille mini, je ne sais pas...) et non pas à 4 fois la taille d'un unsigned int ?
 
Sinon pour les bitsets, ca à l'air seulement en C++, non ? Moi en tout cas, c'est du C pur que je doit utiliser ("pondre" plutot qu'"utiliser" !)

A mon avis un truc simple serait d'utiliser les opérateur &(et), et |(ou) qui te permette de manipuler les bits.
 
exemple :
 
unsigned char a = 0x00000000, // je suis pas sûr pour l'ecriture de l'octet
              b = 0x00000001, // toujours pas sûr
              c;
 
c = a & b; on aura c = 0x00000000 // si je me trompe pas
c = a 1 b; on aura c = 0x00000001 // si je me trompe pas
 
Bon mon exemple est foireux mais tu vois l'idée.
 
 
Sinon pour alléger ta mémoire au lieu d'utiliser MinMax utilise AlphaBeta fait recherche tu verras c'est une optimisation du MinMax.
 
Voilà
@+

Ok, je vais voir, merci.
 
Quand à l'algo de l'alphaBeta, je vais l'implementer aussi ! En fait, je doit d'abord faire un minMax tout con (enfin "tout con" on en reparlera quand j'aurais réussi à le faire   ) puyis ensuite utiliser l'alphaBeta.
J'ai du boulot moi      

En fait, j'ai commencé à ecrire ca:
 
typedef struct {
    unsigned int case1 :1;    unsigned int case2 :1;
    unsigned int case3 :1;    unsigned int case4 :1;
    unsigned int case5 :1;    unsigned int case6 :1;
    unsigned int case7 :1;    unsigned int case8 :1;
    unsigned int case9 :1;    unsigned int case10:1;
    unsigned int case11:1;    unsigned int case12:1;
    unsigned int case13:1;    unsigned int case14:1;
    unsigned int case15:1;    unsigned int case16:1;
    unsigned int case17:1;    unsigned int case18:1;
    unsigned int case19:1;    unsigned int case20:1;
    unsigned int case21:1;    unsigned int case22:1;
    unsigned int case23:1;    unsigned int case24:1;
    unsigned int case25:1;    unsigned int case26:1;
    unsigned int case27:1;    unsigned int case28:1;
    unsigned int case29:1;    unsigned int case30:1;
    unsigned int case31:1;    unsigned int case32:1;
    unsigned int case33:1;    unsigned int case34:1;
    unsigned int case35:1;    unsigned int case36:1;
    unsigned int case37:1;    unsigned int case38:1;
    unsigned int case39:1;    unsigned int case40:1;
    unsigned int case41:1;    unsigned int case42:1;
    unsigned int case43:1;    unsigned int case44:1;
    unsigned int case45:1;    unsigned int case46:1;
    unsigned int case47:1;    unsigned int case48:1;
    unsigned int case49:1;    unsigned int case50:1;
 
} t_PiecesDamier;
 
 
typedef struct {
 t_PiecesDamier damesNoires;
 t_PiecesDamier damesBlanches;
 t_PiecesDamier pionsBlancs;
 t_PiecesDamier pionsNoirs;
 
 unsigned int couleurJoueur :1;
} t_Damier;
 
 
...mais en fait il y a un gros probleme: je ne peux pas acceder aux cases, comme on le ferait pour un tableau, par de simples indices de 1 à 50. Ou alors je suis obligé de creer une fonction d'acces prenant ce numero en parametre et avec un switch-case de 50 ligne. Ca serait moche ! On peut vraiment pas faire des tableaus de bits ???

je suis peut etre con et j'ai pas tout lu mais pour ton dernier pb..si tu fais un pointeur vers ta structure....tu pourrais la manipuler comme un tableau

 
attention si tu recherches des performances
le cout de manipulation supplementaires sur le bit
aura un impact sur tes performances.
On ne peut pas adresser directement au niveau du bit
pour repondre a la question de spice.
Hum 10*10 char = 100 octets pour un tableau. Quelques centaines de ces choses la ca fait quelques dizaines de kilooctets..
Je me trompe peut-etre mais ca tient surement dans un cache
L2 peut etre L1
 
A+
LEGREG

 
en fait je disais juste que si il fesait un pointeur vers la structure,il pourrait acceder a chacun des membres comme on le fait avec un tableau, sans faire de switch 50 fois...

Yop
 

 
Si tu te pose tant de questions pour la représentation du damier, ben mon vieux t pas couché qd tu voudra représenter l'arbre qui va avec l'algo de recherche.
Deja le damier a une taille fixe de 100, bon je sais pas ce que tu veux stocker dedans mais des char ou des ints devraient suffir, ce qui n'est pas dramatique nivo place en memoire...
donc jte dirais juste passe a la suite t'occupe pas trop de choses comme la représentation en memoire du plateau de jeu. Le damier prendra toujours une taille de memoire fixe, et je pense insignifiante à coté de la place que pourra prendre l'arbre lors du calcul. Donc pour éviter que ton IA fasse rebooter ta machine , concentre toi plutot sur la partie "recherche et evaluation de coups à jouer" pour ne pas te retrouver avec un arbre mal évalué ou mal élagué.

[edtdd]--Message édité par kwiky--[/edtdd]

Oui je suis d'accord avec ce qui a été dit précédemment 100o c'est pas grand chose et si tu t'amuses à traiter des bit tu vas y passer beaucoup plus de temps et ca va être compliqué.
 
100o x 1000 = 100 000o ~ 98Ko
 
Tonc tu es tranquille pour la mémoire.

Le probleme, c'est que dans mon arbre minimax, je vais stocker à chaque noeud un damier (avec la position de chaque piece, donc). Ce qui fais que quand l'ordi jouera, il y aura des centaines et des centaines de damiers en mémoire... Et là, je ense que le probleme de la place devient important.
C'est sur que s'il n'y avait qu'un damier pour représenter le jeu une fois our toute, ce ne serait pas un probleme.
Je ne pense pas non plus que je puisse faire comme le suppose Spice di connasse (je suis fan de ton nom !) car avec un pointeur, on ne peut que sauter d'octet en octet, et non pas de bit en bit...

Ben en bit as bit c'est un peu chiant mais tu peux faire comme ca :
 
octet & 1        => bit de rang 0
(octet >> 1) & 1 => bit de rang 1
...
 
Mais bon c'est le bordel mais ca marche.

Tiens voila même une ligne de code pour extraire le i° bit d'un nombre (i : de 0 à 7 ou plus).
 
bit = (byte >> i) & 1;
 
Pour mettre à jour :
 
byte = byte | (1 << i); // mettre à 1 le i° bit
byte = byte & Not(1 << i); // mettre à 0 le i° bit

Ok, merci, mais en fait, je crois que je vais faire comme ca:
 

 
y'a pas grand chose à expliquer, j'ai tapé ca cet apres midi, je vous laisse voir. En fait, au niveau temps de calcul, lors de la construction/evaluation de l'arbre, ca risque de pas etre super rapide. Mais mon prof m'a dit de limiter la place memoire, donc j'essaie de lui faire plaiz' !

Je tiens quand même à rajouter que lorsque tu utiliseras l'alpha-bêta ton problème de mémoire risque de devenir obsolète, de plus tu peux aussi (et je te le recommande) limiter la profondeur de l'esploration de ton arbre en fonction des performances de ta machine.
 
Sinon plutôt que de stocker toutes les cases avec l'utilisation d'un tabelau représentant le damier, le mieux serait d'utiliser une liste des pièces du jeux ce qui fait que chaque position aura entre 2 et 80 int. A toi de voir ce qui est mieux dans ton cas.

as-tu pense a t'inspirer de la notation des echecs
(fou en a5, echec)?
 
Faudrait peut-etre d'abord etudier tes besoins en memoire
avant de faire de la suroptimisation.
des centaines et des centaines de tableaux ca fait
toujours pas grand chose..
 
A+
LEGREG

 
oups je viens de me rendre compte qu'il faut aussi gérer la couleur et le type de la pièce ce qui donne commme info :
deux int pour la position
et on va dire un char pour la couleur
et un char bouléen pour savoir si c'est une dame ou pas.
 
Je peux te dire que l'idée de la liste est utilisée dans les jeux d'échecs donc je pense qu'elle doit pas être mauvaise.
 
Mais farnchement je te conseilles de jouer sur la profondeur de l'arbre si tu veux pas que ta machine explose.

un truc qu'on oublie souvent
 
1Ghz = 1 Milliard de cycles d'horloges par sec.
1Go = 1 milliard d'octets (ordre de grandeur)
combien de tableaux de 100 octets tu stockerais
dans un milliard d'octets? (quelque chose comme
10 millions).
 
A+
LEGREG

Par exemple pour savoir si le bit 3 d'une variable est allumé :
 
if(variable & 8)
printf("le bit 3 de la variable est sur 0" );
else
printf("le bit 3 est sur 1" );
 
On peut aussi savoir si deux bit sont allumées en faisant la somme des puissances de 2 représentées par les différents bits.Par exemple pour tester les bits 0 et 1:
 
if(variable & 6) == 6)
printf("les bits 0 et 1 sont sur 1" );
else
printf("les bits 0 et 1 sont éteints" );
 
Pour allumer ou éteindre des bits c'est le même principe sauf que l'on utilise l'opérateur OU:
 
variable |= 8;