Self-assessment quiz

--- secondary_color: lightgray --- # Combinatorial game theory In the context of combinatorial game theory, what does an arena refer to? - [ ] An enclosed area that is often circular in shape. - [x] A graph in which each vertex summarizes a possible state of the game, and edges describe how to evolve from one state to another. - [ ] A graph in which each vertex is a player. - [ ] The online version of Magic: the Gathering. # Combinatorial game theory What is a strategy? - [x] A function that associates a vertex in the arena with a decision for a given player. - [ ] A rooted tree. - [ ] A function that computes an approximate solution to the TSP. # Combinatorial game theory Tic-tac-toe is a game where two players successively choose one empty cell of a $3 \times 3$ grid to be filled with their respective color. The first player to have three aligned cells (horizontal, vertical, or diagonal) of the same color wins the game. Describe what a vertex in the arena of tic-tac-toe could look like: - [ ] A couple $(i, j)$ where $1 \leq i$ and $j \leq 3$. - [x] A partially colored $3 \times 3$ grid with an indication of which player should play next. - [ ] A list of the empty cells. # Combinatorial game theory Imagine a game in which the arena contains $n$ vertices. Consider that a player has exactly 3 possible actions from each vertex of the arena. What is the maximum number of possible strategies? - [ ] $n$. - [ ] $3n$. - [ ] $n^3$. - [x] $3^n$.

--- secondary_color: lightgray --- # Computing winning positions in a game In a game, what does a winning strategy refer to? - [ ] A strategy in which some choices of the opponent may lead to victory. - [x] A strategy in which all possible choices of the opponent leads to victory. # Computing winning positions in a game What is the winning region of a game for a player? - [x] The vertices in the arena from which the player has a winning strategy. - [ ] The set of strategies of the opponent against which the player has a winning strategy. - [ ] The number of possible games that are won by the player. # Computing winning positions in a game Which player(s) have a winning strategy in a game of tic-tac-toe? - [ ] Both players. - [ ] The first one to play. - [ ] The second one to play. - [x] None of them. # Computing winning positions in a game Imagine that we play a game on a graph. We start with a graph containing n vertices and no edges. On each turn, a player must add an edge to the graph. The first player to add an edge that forms a triangle (*i.e.*, there exists $v1$, $v2$, $v3$ such that $\{v1, v2\}$, $\{v2, v3\}$, $\{v1, v3\}$ are edges) wins the game. For which values of $n$ does the first player to add an edge have a winning strategy? - [ ] Never. - [ ] When the integer division of $n$ by 2 is even. - [x] When the integer division of $n$ by 2 is odd.