Discussion :

[ahoff]

Bonjour je suis étudient et je travaille actuellement sur un alpha-beta dans un jeux ou il est fréquent que plusieurs coup aient la même valeurs.

Mettons que mon algorithme me sorte le tableau de tuple (coup, valeur) suivant :

[c1:23, c2:-9, c3:23, c4:12, c5:23]

Je souhaite choisir un coup aléatoirement parmi c1, c3 et c5. Je voudrais donc savoir si la STL permet de faire ça simplement.

Merci d'avance.

[ternel]

je dirai oui, en utilisant un std::sort et un comparator bien pensé

[cob59]

Si le problème est de tirer un indice pair/impair :

Code :

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

1
2
3
4
5
 
std::vector<std::tuple<Coup,Valeur>> v;
 
int indice_pair = std::rand() % (v.size() / 2) * 2;
int indice_impair = std::rand() % ((v.size()-1) / 2) * 2 + 1;

[ahoff]

je dirai oui, en utilisant un std::sort et un comparator bien pensé

Merci pour ta réponse, si je comprend bien, je modifie mon comparateur de tuple

Code :

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

1
2
3
4
bool tupleCoup::greater(std::tuple<Coup, int> a, std::tuple<Coup, int> b)
{
	return std::get<1>(a) > std::get<1>(b);
}

de la manière suivante :

Code :

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

1
2
3
4
5
6
7
8
bool tupleCoup::greater(std::tuple<Coup, int> a, std::tuple<Coup, int> b)
{
	if (std::get<1>(a) > std::get<1>(b))
		return true;
	else if (std::get<1>(a) == std::get<1>(b))
		return ((rand()%100) >= 50);
	return false;
}

La liste est bien triée dans l'ordre décroissant mais les élléments egaux sont mélangés.

Merci pour ton aide

[Iradrille]

Il serait intéressant de faire des tests pour voir si la répartition est bonne. Il est probable que c1, c3 et c5 n'aient pas une chance sur trois d'être tiré chacun.

[JolyLoic]

Je conseille la lecture de http://en.wikipedia.org/wiki/Fisher%...ing_algorithms

Sinon, et si tu n'as pas des contraintes de perf trop drastiques, un simple tri, un comptage du nombre de valeurs identiques, puis un choix parmi ces valeurs me semble le plus simple.

[ahoff]

Il serait intéressant de faire des tests pour voir si la répartition est bonne. Il est probable que c1, c3 et c5 n'aient pas une chance sur trois d'être tiré chacun.

En effet, la répartition dépend du tri implémenté par std::sort, (cf. ici), mais bon on peut pas vraiment savoir quel tri est (sera) implémenté, du coup ça semble difficile de prédire si la répartition sera uniforme ou non (de toute façon les stateux dirons que ça suit une loi normale ). Mais à la rigueur c'est pas grave.

Je conseille la lecture de http://en.wikipedia.org/wiki/Fisher%...ing_algorithms

Sinon, et si tu n'as pas des contraintes de perf trop drastiques, un simple tri, un comptage du nombre de valeurs identiques, puis un choix parmi ces valeurs me semble le plus simple.

Enfaite j'ai plus des contraintes de perf (l'algo s'exécute sur un temps limité) que sur répartition. Tout ce qui compte c'est que mon IA ne bouge pas tout le temps le même pion (dans ce jeu il est très risqué et du coup l'IA campe).

[Iradrille]

En effet, la répartition dépend du tri implémenté par std::sort, (cf. ici), mais bon on peut pas vraiment savoir quel tri est (sera) implémenté, du coup ça semble difficile de prédire si la répartition sera uniforme ou non (de toute façon les stateux dirons que ça suit une loi normale ). Mais à la rigueur c'est pas grave.

Que ce soit un Quicksort ou autre, ça sera un tri en O(n log(n)), je vois mal la STL implémenter un BubleSort ou autre en O(n²), bien que ça peut être plus rapide dans certains cas précis.
(Enfin il est possible que le type de tri change en fonction de la taille du conteneur, mais c'est à prendre en compte ici)

Du coup, comme propose JolyLoic, si tu fais un tri "normal" (O(n log(n)), suivi d'une recherche linéaire pour trouver le nombre de coups optimaux (O(n)), suivi d'un choix aléatoire parmi ces coups optimaux (O(1)), tu restes en O(n log(n)) mais avec une meilleure répartition.

[JolyLoic]

Voire même, si tu te moques de louper certains résultats, tu fais un partial_sort pour ne récupérer que les 15 premiers résultats (c'est du n log(m), avec m = 15, quelque soit n). Ensuite, parmi les valeurs égales dans ces 15 premiers résultats, tu sélectionne un au hasard.