- Le casse-tête de Steve Ballmer consistant à deviner un nombre est un jeu où il faut trouver un nombre entre 1 et 100 ; une recherche binaire fixe peut être exploitée, mais en utilisant une stratégie mixte, on peut obtenir une espérance positive indépendamment du choix de l’adversaire
- Ballmer pensait que même avec un choix aléatoire, l’espérance était négative et qu’il pouvait choisir un nombre prenant longtemps à trouver, mais John Graham-Cumming a réfuté cela en montrant qu’avec un choix aléatoire, l’espérance est de 0,20 $
- Avec un schéma de recherche fixe, au moins 37 des 100 nombres nécessitent 6 questions, ce qui peut entraîner une perte ; si l’adversaire connaît la stratégie, il peut faire perdre le joueur à chaque fois
- La solution consiste à choisir probabilistiquement l’une de plusieurs stratégies de recherche pures, une stratégie mixte de théorie des jeux, afin de moyenner les écarts entre gains et pertes pour chaque nombre et d’éliminer les nombres défavorables
- Un exemple de stratégie trouvé en résolvant un problème de programmation linéaire avec
scipy.linprog()rapporte en moyenne 0,16 $ si Ballmer choisit au hasard, et une espérance de gain de 0,14 $ dans le pire des cas même s’il choisit de manière hostile
Le casse-tête de devinette de nombre et la réfutation existante
- Le casse-tête que Ballmer appréciait est un jeu où l’adversaire pense à un nombre entre 1 et 100, et indique à chaque supposition du joueur si le nombre est plus grand ou plus petit
- La récompense est de 5 $ si le joueur trouve au premier essai, puis 4 $, 3 $, 2 $, 1 $, 0 $, puis, au-delà, c’est le joueur qui paie 1 $, 2 $, 3 $
- Ballmer estimait qu’il ne fallait pas jouer à ce jeu pour deux raisons
- Il jugeait que même en choisissant un nombre au hasard, de nombreux nombres entraînaient une perte, donnant une espérance négative
- Il pensait pouvoir choisir stratégiquement le nombre qui prendrait le plus de temps à trouver par recherche binaire
- Dans “Steve Ballmer’s incorrect binary search interview question”, John Graham-Cumming a répondu que si Ballmer choisissait un nombre au hasard, l’espérance était positive, à 0,20 $
- En allant plus loin, il est possible de trouver une stratégie dont l’espérance reste positive même lorsque Ballmer choisit le nombre stratégiquement
La faiblesse d’une recherche binaire fixe
- Si le joueur utilise toujours la même stratégie de recherche binaire, 37 des 100 nombres nécessitent 6 questions avant d’être trouvés
- Si Ballmer connaît cette stratégie fixe, il peut choisir l’un de ces 37 nombres « perdants » et imposer une perte au joueur
- Cette vulnérabilité ne se limite pas à une recherche binaire particulière
- Dans n’importe quel schéma de recherche fixe, au moins 37 nombres entraînent une perte
- Si l’adversaire choisit l’un de ces nombres, le joueur perd à chaque fois
Répondre par une stratégie mixte
- Plutôt que de figer un seul schéma de recherche, on prépare plusieurs schémas de recherche, puis au début du jeu on en tire un probabilistiquement et on le conserve jusqu’à la fin
- En théorie des jeux, on appelle cela une stratégie mixte fondée sur plusieurs stratégies pures
- Un même nombre peut être gagnant dans un schéma de recherche et perdant dans un autre
- L’objectif de la stratégie mixte est de moyenner l’espérance de gain pour chaque nombre, afin que l’espérance soit positive pour tous les nombres
Trouver une stratégie par programmation linéaire
- L’objectif n’est pas de calculer la stratégie optimale maximisant l’espérance dans le pire des cas, c’est-à-dire l’équilibre de Nash, mais de trouver n’importe quelle stratégie gagnante pour tous les nombres
- Chaque stratégie pure peut être représentée par un vecteur de gains de longueur 100,
V = (v_1, .., v_100)v_kest l’espérance de gain lorsque Ballmer choisit le nombrek- Par exemple, une recherche binaire peut avoir des valeurs comme
v_50 = 5,v_25 = 4,v_0 = -1
- Si la stratégie mixte choisit la stratégie pure
V_kavec une probabilitép_k, le vecteur de gains total devientV_mixed = Σ p_i V_i - Pour trouver une stratégie gagnante, il faut une combinaison linéaire satisfaisant les conditions suivantes
- Chaque élément doit être positif
- Les coefficients, étant des probabilités, ne doivent pas être négatifs
- C’est un problème classique de programmation linéaire, que l’on peut résoudre avec
scipy.optimize.linprogde SciPy - En constituant un ensemble de stratégies pures à partir de plusieurs variantes de recherche binaire et en les injectant dans
scipy.linprog()via ce code, on obtient une stratégie mixte gagnante
Exemple de stratégie et résultats
- Le code complet se trouve dans gukoff/ballmer_puzzle
- Le résultat initial était de 0,07 $ par partie, puis Arthur O’Dwyer a ajouté de nouvelles stratégies pures et amélioré les performances
- Les performances de la stratégie mixte améliorée sont les suivantes
- Gain moyen lorsque Ballmer choisit au hasard : 0,16 $
- Gain dans le pire des cas lorsque Ballmer choisit de manière hostile : 0,14 $
- L’exemple de stratégie mixte combine plusieurs variantes de recherche binaire avec de faibles probabilités
- Probabilité 0,4714 % : première supposition 29, puis supposer le milieu de l’intervalle, et choisir la gauche en cas d’égalité
- Probabilité 0,1691 % : première supposition 33, puis supposer le milieu, et choisir la gauche en cas d’égalité
- Probabilité 0,1299 % : première supposition 36, puis supposer le milieu, et choisir la droite en cas d’égalité
- Probabilité 3,3341 % : première supposition 37, puis supposer le milieu, et choisir la droite en cas d’égalité
- Probabilité 1,7818 % : première supposition 43, puis choisir l’élément le plus à droite de l’intervalle qui n’augmente pas la complexité dans le pire des cas
- Probabilité 1,1608 % : première supposition 44, puis choisir l’élément le plus à gauche de l’intervalle qui n’augmente pas la complexité dans le pire des cas
- Probabilité 2,1310 % : première supposition 42, puis choisir un élément vers l’extrémité de l’intervalle qui n’augmente pas la complexité dans le pire des cas
- La stratégie complète tient en 74 lignes, et la liste complète omise ici est disponible dans la winning strategy sur GitHub
- Si un gain moyen de 14 cents par partie vaut le temps investi, cela peut valoir la peine de jouer même si Ballmer propose ce jeu
1 commentaires
Avis sur Hacker News
Article récent lié : la mauvaise question d’entretien sur la recherche binaire de Steve Ballmer - https://news.ycombinator.com/item?id=41434637 - septembre 2024, 240 commentaires
L’application dans cet article est intéressante, mais il me semble qu’il passe à côté de l’essentiel
L’argument de Ballmer porte fondamentalement sur le risque de queue. Si l’on accorde de l’importance à la survie, l’espérance de gain n’est pas du tout un bon critère pour parier. Parce qu’on n’a qu’une seule occasion. C’est la même raison pour laquelle il n’est pas sensé, au poker, de miser toute sa fortune chaque fois qu’on a une main qui gagne « en espérance » : on fera presque certainement faillite en quelques manches
Que la moyenne soit de +0,07 $ ou autre, l’étendue de la distribution peut clairement descendre sous 0. En moyenne, la probabilité de gagner est peut-être légèrement supérieure à celle de perdre, mais en pratique on ne reçoit qu’un seul résultat. Si l’objectif est de gagner ou d’être ruiné, et si vous ne voulez pas finir à devoir de l’argent à Ballmer, mieux vaut ne pas jouer
Ce qui serait plus intéressant, c’est de faire une simulation de Monte-Carlo de cette stratégie pour observer la distribution des victoires et des défaites. Le choix ne serait alors peut-être pas si évident
Si vous pouviez jouer quelques milliers de milliards de parties, alors bien sûr, vous pourriez le plumer :P
Et même comme exemple de risque de queue, ce n’est pas terrible. Dans la stratégie évidente, la queue est extrêmement épaisse
Sam Bankman-Fried aimait beaucoup l’espérance de gain et il est célèbre pour avoir dit qu’il lancerait une pièce qui, si elle tombait sur pile, doublerait la « valeur » du monde, mais, si elle tombait sur face, détruirait le monde
En résumé, le paradoxe de Saint-Pétersbourg est le suivant. On lance une pièce équilibrée jusqu’à obtenir pile, et le joueur reçoit 2^n $, où n est le nombre de lancers. Si pile sort au premier lancer, il reçoit 2 $, au deuxième 4 $, au troisième 8 $, au dixième 1024 $ (2^10), et ainsi de suite. Il est facile de montrer que l’espérance de gain de ce jeu tend vers l’infini
Par conséquent, une personne parfaitement rationnelle devrait être prête à payer pratiquement n’importe quelle somme pour jouer à ce jeu. Toute somme finie étant inférieure à l’infini, le gain espéré est toujours positif
Mais presque personne ne paierait probablement des millions de dollars pour y jouer. SBF est peut-être l’exception
Ce n’est un paradoxe que si l’on pense que cela montre que les gens ne sont pas « rationnels ». En réalité, cela semble plutôt signifier que l’espérance n’est pas une bonne mesure du risque, et que tout le monde le sait
Un article très complet et intéressant sur le paradoxe de Saint-Pétersbourg : https://plato.stanford.edu/entries/paradox-stpetersburg/
Contrairement à la plupart des gens ici, je pense que ce type de question est une assez bonne manière de voir comment quelqu’un réfléchit. Si l’on a une formation en maths/statistiques/informatique, on devrait au moins pouvoir engager une discussion sur ce problème
En revanche, si l’on en fait un piège en dissimulant des hypothèses ou en ajoutant arbitrairement des contraintes sans fondement, c’est là que ça ne tient plus
Si la question est « joueriez-vous à ce jeu ? », la traduction mathématique rationnelle est : déterminer si l’espérance est supérieure à 0. Si l’on veut parler de risque de queue, il faut préciser la fonction d’utilité, qui peut d’ailleurs être asymétrique entre les deux joueurs. Et il faut dire clairement que c’est l’intention
Honnêtement, j’ai l’impression que Steve n’a pas vraiment saisi la profondeur mathématique de ce problème
Si vous misez plus que la fraction de Kelly, le risque de faillite augmente, surtout à long terme
https://en.m.wikipedia.org/wiki/Kelly_criterion
Je ne dis pas que cela s’applique à la situation de l’article d’origine. Mais c’est pertinent pour le commentaire parent, et très utile dans de nombreux contextes, comme l’investissement
Quand Ballmer a parlé d’« adversaire », j’ai pensé à ce genre de stratégie. En réalité, il n’a absolument pas besoin de choisir un nombre fixe au départ. À chaque proposition, il lui suffit de donner la réponse qui laisse le plus de nombres possibles, et il peut ainsi garantir la défaite de n’importe quelle stratégie.
L’article original propose une stratégie aléatoire complexe qui garantit en moyenne au moins 0,07 $ contre n’importe quel adversaire. À l’inverse, Ballmer n’a qu’à différer son « choix » et faire traîner pour vous forcer à deviner sept fois à chaque partie et vous faire payer 1 $.
Si vous vous attendiez à gagner 0,07 $ en moyenne, combien de parties joueriez-vous avant de comprendre que vous vous faites arnaquer ?
L’article original est intéressant, mais il suppose une notion très faible d’« adversaire », où Ballmer reste engagé sur un choix initial.
Fait intéressant, si Ballmer utilise un schéma d’engagement, le joueur peut le vérifier [1]. Par exemple, au début de la partie, Ballmer génère 500 bits aléatoires, y ajoute le nombre choisi entre 1 et 100, puis hache le résultat et envoie ce hachage. À la fin de la partie, il envoie les 500 bits aléatoires, et le joueur peut vérifier qu’en concaténant le nombre désormais révélé avec ces bits puis en hachant le tout, on obtient bien le hachage envoyé au départ. Si Ballmer ment et veut changer de nombre, il doit trouver 500 bits qui, concaténés avec un autre nombre, produisent quand même le hachage d’origine, ce qui est difficile.
[1]: https://en.wikipedia.org/wiki/Commitment_scheme
C’est fait par le créateur de HATERIS, une variante de Tetris qui donne toujours le pire bloc.
Édition : ah, non. Ce commentaire est faux. Merci à fgna de me l’avoir signalé.
Il me semble qu’il existe une preuve plus simple qu’on peut battre un Ballmer adversarial. On obtient exactement la même espérance de gain qu’avec une recherche binaire contre un Ballmer aléatoire.
J’appelle mon algorithme « recherche binaire à décalage aléatoire ». Voici comment il fonctionne :
offset.offsetà la valeur et utiliser le reste de la division par 100.C’est tout. Désormais, même si Ballmer connaît cette stratégie, il ne peut pas choisir un nombre particulier pour dégrader ses performances. L’espérance reste donc de 0,20 $ par partie, ce qui est mieux que la stratégie proposée dans l’article.
Parmi les nombreuses choses sur lesquelles Ballmer s’est trompé, celle-ci semble en faire partie.
Voilà, les amis, un exemple parfait de la raison pour laquelle les processus d’entretien technique modernes relèvent de la pure folie.
La question de Ballmer semble juste, compte tenu de la complexité de la réponse qu’il attendait.
La personne candidate donnerait probablement une réponse mathématiquement incorrecte, mais montrerait son raisonnement au passage et démontrerait aussi quelques principes d’informatique.
Il faut garder à l’esprit que Ballmer a eu une longue carrière. S’il a réellement posé cette question, c’était probablement dans les années 80, et à l’époque personne ne se serait attendu à la solution complexe décrite dans l’article.
Donner la bonne réponse aurait été remarquable et aurait justifié une embauche immédiate. Mais cette question ne me paraît pas fondamentalement cassée. Qu’on accepte le pari ou non, il faut bien justifier sa réponse dans tous les cas.
En général, il y a une discussion avec tous les intervieweurs, et on ne regarde pas simplement si « le candidat a résolu le problème ». Personnellement, je trouve beaucoup de questions d’entretien des big tech idiotes, mais pour avoir été des deux côtés, je ne pense pas que le processus soit aussi cassé qu’on l’imagine.
Dans ce cas, cela revient à montrer qu’on sait raisonner sur la recherche binaire et démontrer que le gain moyen est de 0,20 dollar.
Cela dit, ça nous a quand même donné de bonnes fictions comme https://aphyr.com/posts/340-reversing-the-technical-intervie... et ses suites.
Un article qui analyse plus largement les équilibres de Nash, y compris les solutions numériques du jeu complet, se trouve sur https://bowaggoner.com/blahg/2024/09-06-adversarial-binary-s...
La fortune nette de Steve Ballmer est de 120 milliards de dollars ; si une partie du jeu prend 30 secondes, il faudrait 1,6 million d’années pour tout lui prendre
Little Mathematics Library – Elements of Game Theory : https://mirtitles.org/2012/09/06/little-mathematics-library-...
C’est un excellent livre qui traite des stratégies mixtes en théorie des jeux
Les exemples de motivation donnés dans le livre sont également excellents
« Il y a deux cartes, un as et un 2. Le joueur A en tire une au hasard, et B ne voit pas quelle carte a été tirée. Si A a tiré l’as, il dit “j’ai un as” et demande 1 dollar à son adversaire. Si A a tiré le 2, il peut soit (A1) dire “j’ai un as” et demander 1 dollar à son adversaire, soit (A2) avouer qu’il a le 2 et donner 1 dollar à son adversaire
Si l’adversaire reçoit volontairement 1 dollar, il ne peut qu’accepter. Mais si on lui demande 1 dollar, il peut soit (B1) croire qu’A a l’as et lui donner 1 dollar, soit (B2) demander à vérifier pour voir si les paroles d’A sont vraies. Si A a vraiment l’as, B doit payer 2 dollars à A. À l’inverse, si A a bluffé et avait le 2, A paie 2 dollars à B
Analysez ce jeu et trouvez la stratégie optimale et le gain espéré de chaque joueur »