Jusqu'à 90% de victoire au Qui-est-ce!
Du haut de son arrogance il vous toise, le jeune freluquet. C'est à vous de lui montrer qui est le patron.
Tout le monde connait ce jeu pour enfant, où l'on doit deviner le personnage pioché par son adversaire en posant un minimum de questions. Les questions portent sur les caractéristiques physiques partagées par certains des personnages. On procède donc par élimination afin qu'il n'en reste plus qu'un qui corresponde à tous les critères. Dans le reste de cet article, nous nous baserons sur la version "historique" du jeu, il existe différentes versions avec des personnages aux physiques différents. Les concepts restent cependant les mêmes.
A noter que cette première partie d'article, concernant la méthode optimale pour gagner à "qui-est-ce ?" est très largement inspirée de l'épisode réalisé par le youtubeur Mark Rober (vidéo en anglais ici).
Méthode 0 : On élimine 1 par 1 chaque personnage.
Il ne s'agit pas vraiment d'une méthode à proprement parler puisque personne ne joue comme ça mais il est possible de poser, à chaque tour, une question qui permet d'éliminer un seul personnage. Par exemple "Est-ce que ton personnage est Anita ?". Sachant qu'il y a 24 personnages sur le plateau de jeu, cette méthode peut vous permettre de gagner en un coup (si effectivement le personnage à trouver est Anita, ce qui arrivera 1 fois sur 24) mais il est aussi possible, dans le pire des cas de ne gagner qu'en 24 coups, le personnage à trouver étant le dernier que vous proposerez.
Si vous connaissez un peu les probabilités, vous aurez reconnu un cas de tirage sans remise où la probabilité de succès est de 1/24. Avec cette méthode vous avez 1 chance sur 24 de finir en 1 coup, 1 chance sur 24 de finir en deux coups, etc ...
En moyenne vous terminerez donc la partie en 12.5 coups (on parle d'une espérance de 12.5). Il s'agit de la méthode la moins optimale possible, mais qui nous sert de référence afin d'évaluer les futures améliorations.
Espérance de la méthode 0 : 12.5
Méthodes avancées
Méthodes avancées
Pour les méthodes plus avancées, il va falloir poser des questions sur le physique des personnages sachant que dans le jeu de "qui est ce", chaque attribut physique est partagé par 5 personnages au plus. Il y a 5 roux, 5 blonds, 5 personnes au cheveux noirs, 5 chauves, 5 femmes, 5 personnes aux yeux bleus, 5 moustachus, 5 avec chapeaux, 5 avec lunettes, 5 avec un gros nez et 5 avec les joues roses.
Il existe seulement deux exceptions à cette règle : il y a uniquement 4 personnes avec les cheveux marron (forcément il faut bien réussir à tomber sur un total de 24 pour ce qui est de la couleur des cheveux) et 4 personnes seulement avec une barbe (pour une raison que j'ignore). On peut donc générer le tableau des caractéristiques de chaque personnage.
Nous disposons ainsi d'une série de questions permettant de discriminer les personnages. On peut d'ailleurs en profiter pour se rendre compte que certains couples de personnages possèdent très peu de différences (comme Alex et Max, qui ne diffèrent que par la taille de leur nez ou Paul et Sam qui ont juste une différence de calvitie) ou au contraire, des paires de personnages ayant jusqu'à 9 différences.
Il est bien évidemment possible de trouver des questions plus spécifiques pour caractériser les personnages (la forme du visage, type de cheveux...) mais elles n'apportent pas grand-chose car elles sont moins discriminantes.
Méthode 1 : On pose des questions au hasard parmi les personnages restants sans se soucier du nombre que l'on va éliminer.
C'est la méthode de base, utilisée par les enfants. On regarde les personnages restants et on pose une question en fonction des attributs physiques de ceux-ci. Il peut arriver que de telles questions n'éliminent qu'un ou deux personnages. C'est donc une méthode un peu meilleure que la première car elle permet parfois d'éliminer plusieurs personnages à la fois mais le nombre de personnages éliminés n'est pas forcement optimisé par le joueur.
Pour tester l'efficacité de cette méthode (qui possède une part d'aléatoire), le plus simple est de créer un algorithme qui simule des parties et de voir en combien de coup il est possible de trouver la réponse.
Le petit bout de code qui suit (en R) permet de générer 10 000 parties (il n'est pas forcement hyper optimisé mais cela tourne en une poignée de secondes)
La répartition du nombre de coups est donc la suivante :
On constate alors que le nombre de coups nécessaires pour trouver la solution varie de 2 questions à 12 questions. La moyenne du nombre de questions à poser (l'espérance) se situe autour de 5.6 questions. C'est quand même déjà mieux. Il est à noter que cela ne garantit pas forcément de gagner à chaque fois contre un adversaire qui utilise la méthode 0 (par exemple il peut toujours continuer de gagner en 1 tour alors qu'avec cette méthode c'est impossible) mais en moyenne vous gagnerez 76% du temps, votre adversaire gagnera 19% du temps et vous ferez un match nul 5% du temps. Vous gagnez donc 4 fois plus fréquemment que votre adversaire.
Le petit bout de code qui suit (en R) permet de générer 10 000 parties (il n'est pas forcement hyper optimisé mais cela tourne en une poignée de secondes)
# Methode 1 : Question restante random
COUNT = c()
for (K in 1:10000) { # Nombre de parties
print(sprintf("K=%i",K))
listInd <- rownames(Data) # Liste des personnages
Question <- colnames(Data)# Liste des questions possibles
Reponse <- sample(listInd, size = 1) # On pioche un personnage au hasard
count <- 0 # On initialise le nombre de tours joués
print(Reponse)
# Tant qu'il reste plus d'un individu on continue
while (length(listInd) > 1) {
question = sample(Question, size=1) # On pioche une question au hasard
vecq = Data[listInd, question] # On regarde les valeurs pour chacun des individus restants
# Si c'est une question inutile (qui ne discrimine rien)
if (length(unique(vecq)) < 2) {
# On la supprime des questions restant a poser
Question <- Question[!Question %in% question]
next # On recommence la boucle sans incrementer le nombre de coups
}
count = count + 1
# On conserve les individus qui sont dans la meme categorie que l'individu a deviner
val = Data[Reponse, question] # reponse pour l'individu a trouver
# On met a jour la liste des individus non eliminés
listInd = rownames(Data[listInd,])[Data[listInd, question] == val]
# On met a jour la liste des questions restantes
Question <- Question[!Question %in% question]
print(sprintf("count = %i - question = %s - value = %s - nbInd = %i - nbQuestion = %i",count,question,val, length(listInd), length(Question)))
}
COUNT[K]=count
}
La répartition du nombre de coups est donc la suivante :
On constate alors que le nombre de coups nécessaires pour trouver la solution varie de 2 questions à 12 questions. La moyenne du nombre de questions à poser (l'espérance) se situe autour de 5.6 questions. C'est quand même déjà mieux. Il est à noter que cela ne garantit pas forcément de gagner à chaque fois contre un adversaire qui utilise la méthode 0 (par exemple il peut toujours continuer de gagner en 1 tour alors qu'avec cette méthode c'est impossible) mais en moyenne vous gagnerez 76% du temps, votre adversaire gagnera 19% du temps et vous ferez un match nul 5% du temps. Vous gagnez donc 4 fois plus fréquemment que votre adversaire.
Espérance de la méthode 1 : 5.6
Méthode 2 : On pose une question simple pour essayer d'éliminer le plus de personnes restantes d'un coup.
Nous avons vu que chaque caractéristique physique ne concerne que 5 personnes à la fois. Dans la méthode 2 le choix de la question à poser n'est plus aléatoire mais elle cherche à optimiser la question à poser pour discriminer au mieux les individus restants. Par exemple s'il reste 10 personnages dont 5 roux (et donc 5 non-roux) et 2 avec lunettes (et donc 8 sans lunettes), la question posée sera obligatoirement celle permettant de savoir si le personnage à trouver est roux (et qui éliminera forcément 5 personnes peu importe la réponse) alors que dans la méthode 1 cela aurait aussi pu être la question concernant les lunettes (qui est moins optimale car en moyenne elle élimine 3.6 personnages) puisque la méthode 1 choisit au hasard les questions à poser.
On modifie donc le code et on relance pour 10 000 parties.
La répartition du nombre de coups est donc la suivante :
On constate qu'avec cette méthode, on trouve forcément la solution en 8 coups ou moins et la moyenne du nombre de coups nécessaires pour trouver la solution est de 5.1. La différence ne semble pas énorme par rapport à la méthode 1 mais elle permet de gagner 48% du temps, de faire match nul 16% du temps et de perdre 35% du temps. La méthode 2 permet donc de gagner 1.36 fois plus de parties (vous gagnez 4 parties quand votre adversaire en gagne 3) c'est toujours ça de pris.
On modifie donc le code et on relance pour 10 000 parties.
# Methode 2 : Question restante qui maximise la discrimination
COUNT2 = c()
sink("Out2.txt", append = FALSE)
for (K in 1:10000) {
print(sprintf("K=%i",K))
listInd <- rownames(Data)
Question <- colnames(Data)
Reponse <- sample(listInd, size = 1)
count <- 0
print(Reponse)
while (length(listInd) > 1) {
# On choisit la question qui segmente le mieux parmi toutes les questions restantes
# On regarde le ratio TRUE FALSE le plus proche de 0.5
ratio = apply(Data[listInd, Question], 2, function(x) { sum(x) / length(x) })
# On sous selectionne l'ensemble des questions les plus proches de 0.5
# Il peut y en avoir plusieurs exaequo donc on en prend une au hasard
DIFF = abs(ratio - .5)
BonnesQuestions = Question[DIFF==min(DIFF)]
question = sample(BonnesQuestions, size = 1)
vecq = Data[listInd, question]
if (length(unique(vecq)) < 2) { #question inutile
Question <- Question[!Question %in% question]
next
}
count = count + 1
# On conserve les individus qui sont dans la meme categorie que l'individu a deviner
val = Data[Reponse, question]
listInd = rownames(Data[listInd,])[Data[listInd, question] == val]
Question <- Question[!Question %in% question]
print(sprintf("count = %i - question = %s - value = %s - nbInd = %i - nbQuestion = %i",count,question,val, length(listInd), length(Question)))
}
COUNT2[K]=count
}
La répartition du nombre de coups est donc la suivante :
On constate qu'avec cette méthode, on trouve forcément la solution en 8 coups ou moins et la moyenne du nombre de coups nécessaires pour trouver la solution est de 5.1. La différence ne semble pas énorme par rapport à la méthode 1 mais elle permet de gagner 48% du temps, de faire match nul 16% du temps et de perdre 35% du temps. La méthode 2 permet donc de gagner 1.36 fois plus de parties (vous gagnez 4 parties quand votre adversaire en gagne 3) c'est toujours ça de pris.
Espérance de la méthode 2 : 5.1
Méthode 3 : On pose une question multiple qui permet de diviser par 2 le nombre de personnages restants.
Alors là, je sais d'avance que je vais en entendre râler certains, mais la règle (écrite dans la boite de jeu) stipule que chaque joueur doit, lors de son tour, poser UNE question à laquelle l'autre joueur doit répondre par oui ou non. Cette question peut donc porter sur plus d'un attribut physique à la fois. C'est là le secret de cette méthode. Par exemple, si, au premier tour, vous posez la question : "Ton personnage est-il blond ?" alors vous éliminerez 5 personnes 79% du temps ce qui n'est pas exceptionnel (et 21% du temps vous éliminerez 19 personnes). Cette question a donc une espérance de 7.94, c'est à dire qu'en moyenne elle vous permet d'éliminer environ 8 personnages.
En revanche, si votre première question est plutôt "Ton personnage est-il blond ou roux ?" vous éliminerez 10 personnes si la réponse est non (58% du temps) et 14 si la réponse est oui (42% du temps). Cette question a donc une espérance de 11.7, c'est à dire qu'en moyenne vous éliminez 11.7 personnes. Cela semble quand même bien plus intéressant pour réduire la liste des suspects. Vous pouvez même optimiser le système en posant la question suivante : "Ton personnage est-il blond ou roux ou a des moustaches ?" Dans ce cas-là, peu importe la réponse, vous éliminerez exactement 12 personnages, divisant donc parfaitement par deux le nombre de personnages restant à trouver. Au premier tour il existe 7 combinaisons de 3 questions permettant de séparer le 2 groupes de 12 les personnages.
Faisons
un petit point dans cette explication pour préciser que le "ou" utilisé
dans cette méthode est un "ou inclusif" (appelé OR par les
informaticiens, électroniciens...) et non pas le "ou exclusif" (nommé
XOR).
Dans
le cas du "ou inclusif", si le personnage est roux ET a des moustaches
on répondra OUI (et c'est bien dans ce sens que la question est posée :
"A-t-il au moins un de ces attributs physiques ?") alors que dans le cas
du "ou exclusif" on répondra NON car la question posée est alors
"A-t-il exactement un de ces attributs physique ?"
Avec cette méthode (et à condition de choisir les bonnes questions à poser), il reste forcément 12 personnages à la fin du premier tour, 6 personnages à la fin du deuxième tour, 3 à la fin du troisième tour et au quatrième tour, il reste 1 ou 2 personnages encore présents. Il vous faudra donc poser une 5ème question 66% de temps pour finalement trouver la solution. 33% du temps vous trouverez en 4 coups et 66% du temps en 5 coups. Il n'est pas forcement nécessaire de faire des simulations (bon je l'ai fait quand même et je tombe sur 33.8 et 66.2, ce qui prouve que les simulations sont correctes) et l'on peut déterminer que la répartition de la méthode 3 est :
La moyenne du nombre de coups nécessaires pour trouver la solution est donc de 4.66 c'est encore un petit peu mieux que la méthode 2.
Mais cela signifie que si vous jouez contre un adversaire utilisant la méthode 2 vous gagnerez 51% du temps, vous ferez match nul 22% du temps et perdrez 26% du temps. Vous gagnez donc 2 fois plus souvent que votre adversaire (vous gagnez 2 parties sur 3). La différence est très importante. Cela peut paraitre surprenant car la différence d'espérance est relativement faible, mais la méthode 3 permet surtout de réduire la variabilité. Avec la méthode 3 il n'est pas possible d'avoir besoin de plus de 5 coups alors qu'avec la méthode 2 cela arrive 44% du temps. Cela signifie que toutes les fois où l'adversaire aura besoin de plus de 5 coups vous êtes certain de gagner. Les seuls moments où votre adversaire est certain de gagner c'est quand il a besoin de moins de 4 coups, mais cela n'arrive que 12% du temps.
Et si vous jouez contre un adversaire utilisant la méthode 1, c'est un peu mieux : vous gagnez 55% du temps, match nul 20% du temps et perdez 24% du temps. Vous gagnez donc 2.26 fois plus souvent que votre adversaire (vous gagnez 7 parties sur 10)
Espérance de la méthode 3 : 4.7
