Quiz d'auto-évaluation

--- secondary_color: lightgray --- # Théorie des jeux combinatoires Dans le contexte de la théorie des jeux combinatoires, à quoi correspond une arène ? - [ ] Une zone fermée souvent circulaire. - [x] Un graphe dans lequel chaque sommet résume un état possible du jeu, et les arêtes décrivent comment évoluer d’un état à un autre. - [ ] Un graphe dans lequel chaque sommet est un joueur. - [ ] La version en ligne de Magic: the Gathering. # Théorie des jeux combinatoires Qu’est-ce qu’une stratégie ? - [x] Une fonction qui associe à un sommet de l’arène une décision pour un joueur donné. - [ ] Un arbre enraciné. - [ ] Une fonction qui calcule une solution approchée du TSP. # Théorie des jeux combinatoires Le morpion (tic-tac-toe) est un jeu où deux joueurs choisissent successivement une case vide d’une grille $3 \times 3$ pour la remplir de leur couleur. Le premier joueur à obtenir trois cases alignées (horizontalement, verticalement ou en diagonale) de la même couleur gagne la partie. Décrivez à quoi pourrait ressembler un sommet de l’arène du morpion : - [ ] Un couple $(i, j)$ où $1 \leq i, j \leq 3$. - [x] Une grille $3 \times 3$ partiellement colorée avec une indication du joueur devant jouer ensuite. - [ ] Une liste des cases vides. # Théorie des jeux combinatoires Imaginez un jeu dans lequel l’arène contient $n$ sommets. Supposons qu’un joueur ait exactement 3 actions possibles depuis chaque sommet de l’arène. Quel est le nombre maximal de stratégies possibles ? - [ ] $n$. - [ ] $3n$. - [ ] $n^3$. - [x] $3^n$. # Théorie des jeux combinatoires Parmi les propriétés suivantes, lesquelles s'appliquent à PyRat ? - [x] Les joueurs prennent leurs décisions simultanément. - [x] Le jeu est non coopératif. - [x] Le jeu est à somme nulle. - [x] Le nombre de stratégies pures est fini. - [ ] Chaque joueur connaît le coup de l'adversaire avant de choisir le sien. # Théorie des jeux combinatoires Qu'est-ce qu'une stratégie mixte ? - [x] Une stratégie qui attribue une probabilité à chaque décision possible. - [ ] Une stratégie qui combine les décisions de plusieurs joueurs d'une même équipe. - [ ] Une stratégie qui alterne minimisations et maximisations. - [ ] Une stratégie qui change de cible à chaque tour. # Théorie des jeux combinatoires Que garantit le théorème du minimax de von Neumann pour un jeu à deux joueurs, non coopératif, simultané, à somme nulle, avec un nombre fini de stratégies pures ? - [x] Il existe une situation stable, dans laquelle aucun des deux joueurs n'a intérêt à changer seul de stratégie mixte. - [ ] L'un des deux joueurs a toujours une stratégie pure gagnante. - [ ] Le joueur qui commence a toujours une stratégie gagnante. - [ ] La partie se termine toujours par une égalité. # Théorie des jeux combinatoires Les deux joueurs ont choisi chacun une stratégie pure. Que peut-on dire de la partie ? - [x] Elle est entièrement déterminée : c'est un parcours dans l'arène. - [ ] Elle ne peut pas être prédite, car les joueurs jouent simultanément. - [ ] Elle se termine forcément par une égalité.

--- secondary_color: lightgray --- # Calcul des positions gagnantes dans un jeu Dans un jeu, à quoi fait référence une stratégie gagnante ? - [ ] Une stratégie dans laquelle certains choix de l'adversaire peuvent mener à la victoire. - [x] Une stratégie dans laquelle tous les choix possibles de l'adversaire mènent à la victoire. # Calcul des positions gagnantes dans un jeu Quelle est la région gagnante d'un jeu pour un joueur ? - [x] Les sommets dans l'arène à partir desquels le joueur a une stratégie gagnante. - [ ] L'ensemble des stratégies de l'adversaire contre lesquelles le joueur a une stratégie gagnante. - [ ] Le nombre de jeux possibles gagnés par le joueur. # Calcul des positions gagnantes dans un jeu Quel(s) joueur(s) ont une stratégie gagnante dans un jeu de morpion ? - [ ] Les deux joueurs. - [ ] Le premier à jouer. - [ ] Le second à jouer. - [x] Aucun d'eux. # Calcul des positions gagnantes dans un jeu Imaginez que nous jouons à un jeu sur un graphe. Nous commençons avec un graphe contenant $n$ sommets (avec $n \geq 3$) et aucune arête. À chaque tour, un joueur doit ajouter une arête au graphe. Le premier joueur à ajouter une arête qui forme un triangle (*c'est-à-dire*, il existe $v_1$, $v_2$, $v_3$ tels que $\{v_1, v_2\}$, $\{v_2, v_3\}$, $\{v_1, v_3\}$ sont des arêtes) gagne le jeu. Pour quelles valeurs de $n$ le premier joueur à ajouter une arête a-t-il une stratégie gagnante ? - [ ] Jamais. - [ ] Lorsque la division entière de $n$ par 2 est paire. - [x] Lorsque la division entière de $n$ par 2 est impaire. # Calcul des positions gagnantes dans un jeu Pourquoi un sommet de l'arène ne peut-il pas être gagnant pour les deux joueurs ? - [x] Si les deux joueurs suivaient leurs stratégies gagnantes, ils gagneraient tous les deux la même partie, ce qui est impossible. - [ ] Parce que l'arène est un arbre. - [ ] Parce que le jeu est simultané. # Calcul des positions gagnantes dans un jeu Comment construit-on la région gagnante d'un joueur ? - [x] On part des sommets où la partie est déjà gagnée, puis on ajoute tant que possible les sommets depuis lesquels le joueur peut, quoi que fasse l'adversaire, atteindre un sommet déjà identifié comme gagnant. - [ ] On part du sommet initial, et on ajoute les sommets atteints par un algorithme glouton. - [ ] On ajoute les sommets depuis lesquels au moins un choix de l'adversaire mène à un sommet gagnant. # Calcul des positions gagnantes dans un jeu Pour décrire un sommet de l'arène de PyRat, pourquoi suffit-il de savoir, pour chaque morceau de fromage, s'il a été mangé ou non ? - [x] Parce que les morceaux de fromage ne bougent pas pendant la partie : leurs emplacements sont connus dès le début. - [ ] Parce que les morceaux de fromage mangés réapparaissent ailleurs. - [ ] Parce que le score des joueurs suffit à retrouver leurs positions. # Calcul des positions gagnantes dans un jeu C'est à nous de jouer, et nous avons trois coups possibles. Après le coup A, l'adversaire peut nous laisser un gain de 4 ou de 9. Après le coup B, un gain de 6 ou de 7. Après le coup C, un gain de 1 ou de 12. Quel coup l'algorithme maximin choisit-il ? - [ ] A. - [x] B. - [ ] C. # Calcul des positions gagnantes dans un jeu Que fournit l'algorithme maximin ? - [x] Le coup qui maximise le gain que l'on peut garantir face à un adversaire qui joue de manière optimale. - [ ] La séquence de coups qui mène au gain le plus élevé possible. - [ ] Le coup qui minimise le gain de l'adversaire, quel que soit notre gain. # Calcul des positions gagnantes dans un jeu Pourquoi ne peut-on pas, en pratique, calculer les régions gagnantes au début d'une partie de PyRat standard ? - [x] Parce que le nombre de configurations du jeu est trop grand ; ce calcul n'est réaliste qu'avec un petit labyrinthe et peu de morceaux de fromage. - [ ] Parce que les régions gagnantes n'existent que pour les jeux à tour de rôle. - [ ] Parce que l'adversaire peut changer de stratégie pendant la partie.