Discussion :

[Chewbi]

Bonjour,

Mon programme jouant aux dames fonctionne maintenant assez bien, mais il reste "deterministe"; pour varier les parties lorsqu'il joue contre lui-meme j'aimerais qu'il choisisse son coup aleatoirement ; pour cela j'ai essayé (coups etant un vector<Coup> de la stl):

Code :

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

1
2
3
4
5
6
 
 
srand((unsigned)time(NULL));  
int attente=0;   
for (int j=N; j>=0; j--) attente++; // pour laisser un petit temps d'attente
return coups[(int)(N*(float)rand()/(RAND_MAX+1.0))];

ce qui fonctionnait jusqu'a ce que j'optimise le programme avec -O3 (je suppose que le compilateur supprime alors ce "attente++"

Ensuite j'ai essayé:

Code :

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

1
2
3
4
5
 
 
#include <algorithm>
random_shuffle(coups.begin(),coups.end());
return coups[0];

etrangement cela ne fonctionne pas :-/

Enfin j'ai trouvé un code de bon generateur aleatoire sur le net, mais la suite des nombres generes est deterministe (genre 24 78 38..etc pour une loi uniforme sur 1..100); etant donne que le nombre d'appels sera deterministe dans mon cas, je retombe sur le meme probleme..

Bref, le problème est de prendre [0..n] en entree et de retourner un coups[k] où k est non deterministe dans [0..n] (il y a moins d'une seconde entre l'appel de fonction et le return coups[k])

Merci d'avance,
Chewbi, qui espère que son problème est résoluble (y'a bien rand() sur les calculatrices ^^)

[Laurent Gomila]

Il ne faut pas appeler srand à chaque fois que tu veux un nombre aléatoire, une fois suffit.

[Chewbi]

le problème, c'est que l'interface fournie par l'ecole (devant etre utilisée pour un petit tournoi entre modules que l'on fera d'ici 1 mois) prend en parametre notre programme+un damier+une couleur+un temps, et le programme doit donner un coup en sortie, puis est tué..etc

L'appel à srand doit donc se faire dans la fonction alpha-beta, et le return rand(..) à la fin; je ne fais qu'un seul appel, mais le resultat est bien deterministe :-/

[superspag]

ça m'a toujours fait rire les problème de génération aléatoire. Pour une fois qu'on aimerai bien faire n'importequoi on y arrive pas

J'ai un peu de mal à suivre ton pb deterministe / non deterministe mais je peux essayer de t'expliquer une ou deux choses qui pourons t'aider (je l'espere).

Dis toi bien que tu ne peux pas faire du vrai hasard en informatique, c'est impossible (à par avec l'informatique quantique mais je dois avouer que ce domaine m'echape...).

La seule solution, c'est d'utiliser des fonctions qui ont un comportement aléatoire. Pour cela, on selectionne des fonctions trés instable avec une periode trés grande. Donc au fur et à mesure que tu avance dans cette fonction en recuperant un rand, tu as vraiment l'impression d'avoir de l'aleatoire et pendant longtemps.

Cela dit, il y a quand meme un hic :
- Quelque soit la fonction, elle finit toujours par se repeter (peutetre au bout de la 1015420549845 ème demandes mais ça finit toujours par arriver...)
- à chaque fois que tu recommence l'utilisation de cette fonction, tu retrouves la meme sequence...

Pour pallier à ça, il existe une multitude de germes/fonctions que tu peux selectionner avec srand... et donc pour en venir à ton problème, si tu obtient des resultats deterministes/repetables, c'est que à quelque part :
- soit tu te place à chaque fois sur le meme germe avec le srand et donc tu repetes la meme sequence.
- soit tu appeles srand sans arret avec la meme sequence que tu n'utilise qu'une seule fois...

Je ne suis peut etre pas tres claire... lol

[Chewbi]

c'est plus clair en effet

Je suis dans le premier cas: "tu te place à chaque fois sur le meme germe avec le srand et donc tu repetes la meme sequence", car comme je l'ai expliqué on tue le programme après chaque coup trouvé :-/

Je ne vois pas trop comment m'en sortir

[superspag]

Qu'est ce que tu entend par : tuer le programme ? c'est un exe que tu lances à chaque fois ?

[Chewbi]

Oui.

A chaque appel je lance un programme écrit de la façon suivante:

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
 
 
pour tous les coups possibles {
    jouer(coup) 
    evaluerAlphaBeta(coup) {
        si l'evaluation est mieux que bestEvaluation, bestEvaluation:=evaluation
        stocker l'indice du coup dans un tableau
    }    
    defaire(coup)
}
 
initialiser un vecteur "tmp" à vide
pour toutes les evaluations trouvees, faire {
    si (evaluation meilleure ou egale à bestEvaluation) ajouter indiceCorrespondant à tmp
}
 
puis choix aleatoire dans tmp, contenant les indices des meilleurs coups ex-aequo..

Et ce appelé à chaque coup joué avec les arguments décrits plus haut (temps, couleur, damier..etc)

Voilou..

C'est résoluble?! :-/

[Gandalf]

Sur quelle plateforme es-tu ?

Es-tu sur de ne pas pouvoir faire deux prog ?
l'un tué à chaque fois, et l'autre pas ?

ne peut-tu pas changer la formule de ta graine afin de faire en sorte que la graine soit différente même si time est identique ?

[Chewbi]

non je ne peux avoir qu'un seul programme qui tourne à la fois (contrainte imposée par les profs); en revanche je peux p-e trouver une formule pour initialiser la graine.

En entrée j'ai une position du jeu de dame, et je calcule l'ensemble des coups possibles. Mais meme si j'initialise la graine en fonction de la position et des coups trouvés, comment faire pour que le programme ne répète pas toujours les memes parties lorsqu'il joue contre lui-meme?

J'ai bien l'impression qu'il n'y a pas de solution :-/

[Strab]

Il existe une autre méthode de génération de nombres pseudo-aléatoires que celle indiquée par superspag. Il existe sur certaines plateformes des générateurs de nombres aléatoires fournis par un appel système qui se base sur des données physiques et à priori imprévisibles : mouvements de la souris et frappes de claviers, vitesse de rotation du disque dur, température du processeur, etc.

Ce n'est donc plus une fonction cyclique et il n'y a pas besoin de graine. Par contre je ne sais pas si tu as ce genre de fonctions à disposition. Sur quel OS travailles-tu ?

[Jean-Marc.Bourguet]

non je ne peux avoir qu'un seul programme qui tourne à la fois (contrainte imposée par les profs); en revanche je peux p-e trouver une formule pour initialiser la graine.

En entrée j'ai une position du jeu de dame, et je calcule l'ensemble des coups possibles. Mais meme si j'initialise la graine en fonction de la position et des coups trouvés, comment faire pour que le programme ne répète pas toujours les memes parties lorsqu'il joue contre lui-meme?

J'ai bien l'impression qu'il n'y a pas de solution :-/

Tu peux aussi combiner cela avec le resultat de time et eventuellement d'autres choses dependante de la plate-forme (un process id, une base de temps de resolution superieure, ...)
Si ta plate-forme offre un generateur de vrai nombres aleatoires, tu peux en prendre un comme graine (ou n'utiliser que cela, mais c'est une ressource relativement rare et il est conseille de n'en consommer beaucoup que si c'est reellement necessaire).

[Chewbi]

C'est une version de Linux (Unix?), j'obtiens ça en tapant "uname -a":

Linux ensibull 2.6.7-BAS3V13-16k-pagesize #1 SMP Wed Oct 6 11:39:33 CEST 2004 ia64 ia64 ia64 GNU/Linux

Mais je ne sais pas trop ce que ça veut dire ^^

[fearyourself]

Sur le forum C, on a eu une discussion là-dessus, et Emmanuel a expliqué que la version mingW (je n'ai pas pu vérifier n'ayant pas de Windows sous la main) du générateur aléatoire a un petit défaut, il donnera toujours le même nombre au premier rand() appelé.

Pour que le programme soit un peu plus aléatoire et parce qu'ici tu dois appeler srand à chaque appel, il serait donc bon de faire un rand "poubelle" avant de faire ton rand "utilisé" pour le programme.

Donc si ton programme tourne sous windows, ceci est sûrement la source de tes ennuis,
Jc

[fearyourself]

C'est une version de Linux (Unix?), j'obtiens ça en tapant "uname -a":

Linux ensibull 2.6.7-BAS3V13-16k-pagesize #1 SMP Wed Oct 6 11:39:33 CEST 2004 ia64 ia64 ia64 GNU/Linux

Mais je ne sais pas trop ce que ça veut dire ^^

Donc ce n'est pas ça ...

[EDIT pour ne pas faire 3 posts d'affilés]

Pourquoi ne pas utiliser une combinaison temps + pid puisque tu lances à chaque fois un nouveau programme?
Ou juste le pid?

[/EDIT pour ne pas faire 3 posts d'affilés]

[Chewbi]

Pourquoi ne pas utiliser une combinaison temps + pid puisque tu lances à chaque fois un nouveau programme?
Ou juste le pid?

Très bonne idée ça (elle avait déjà été suggérée je crois mais je n'ai pas encore essayé car.. je ne sais pas comment récupérer le pid à partir de mon programme :-/)

Bon, je regarde sur la faq C et si je trouve rien je demande ici :p

EDIT: j'ai trouvé, c'est getpid()
joie

Merci à tous!