The Stack Overflow podcast is back! Listen to an interview with our new CEO.
10

There are a number of discussions of this game online, but you should be wary because some of them give incorrect solutions. This website gives an excellent exposition of how to solve this game. (Based in part on this paper.) You assume that all players use the same mixed strategy, and that when all players use this strategy, there is a Nash equilibrium. ...


9

The most common/obvious way is a challenge-response test that is easy for humans but hard for computers (of course, but not only, CAPTCHA). This kind of test is very effective{1} but falls under the HIP (Human Interactive Proofs) area: it's not transparent. Typical, "simple" approaches to distinguish human website traffic from Bot are: time it takes to ...


9

The thing is that with simultaneous moves, the optimal strategy is harder to guess, because you need to compute something that is not always obviously winning. Have a look at Nash equilibrium and the prisoner's dilemma if you don't know them yet. This is the kind of reasoning that you will need each time you are considering two simultaneous moves, instead ...


7

This figure (which is in fact correct) is used in the explanation of the alpha-beta pruning algorithm on a minimax tree. Alpha-beta pruning is a method used to prune parts of the minimax tree in an adversarial search problem. In the context of a tic-tac-toe game, minimax trees are meant to allow the computer to search through the space of all possible game ...


7

Consider the following cases when you are the marginal voter (i.e. you decide the election): Two men $m_1$ and $m_2$ have $>n$ votes, two other men $m_3$ and $m_4$ have $n$ votes, and one woman $w_1$ has $<n$ votes. If you support $m_3$ and $w_1$ equally and support $m_4$ less, then you should vote for $m_3$, such that both $m_3$ and $w_1$ will be in ...


7

Ultimately, unless you can prove something very interesting, you're stuck with exponential backtracking. For at least one natural encoding of positions, Toads and Frogs is NP-hard. Jesse Hull observed that the position $T^n\Box TFT^m \Box TF$ has the game value $\{m+n-1\mid \{ n\mid 2 \}\}$, which means If $T$ moves first, $T$ gets $m+n-1$ free moves. If $...


7

[The reviews are based on my first hand experience with the materials.] Quick Read: Essentials of game theory (Leyton-Brown, Shoham) - This is a ~100 page book, which will give a strong intuition (and more) on Game theory, this mostly covers the basics, the math here is also pretty lightweight, and this is very much readable (even by a college junior). ...


7

Chess violates all three conditions, so I don't really understand what there is to ask. (1) The game is not finite. Although the 50-move and threefold repetition rules allow a player to end the game under certain circumstances, they do not oblige the player to do so. (2) The game has draws. (3) As you have observed, the game definition distinguishes ...


6

The state of the art for solving parity games is now quasipolynomial time. Here are references: Deciding Parity Games in Quasipolynomial Time (PDF), by Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. A short proof of correctness of the quasi-polynomial time algorithm for parity games, by Hugo Gimbert and Rasmus ...


6

Parity games are famously known to be in $NP\cap coNP$, and in fact, in $UP\cap coUP$. However, there are no polynomial algorithms known for them. To be more specific, the best algorithms run in time that is polynomial in the number of states $n$, but exponential in the parity index $d$. The state of the art, as far as I know, is Jurdzinsky's work here. ...


6

I will say up front that I can't provide a good answer to your question (I think you could maybe get a research paper out of it if you could), but I think I can help by defining the problem formally and stating where some of the difficulties lie. Background. Let me clearly state the model for cake-cutting. We wish to divide the interval $[0,1]$ between $n$ ...


6

Assume the cake/area is a circle $C$ with radius $r$. Then, we can create $n$ fair pieces by the canonical cake cutting and thus assign each player an area of $\frac{\pi r^2}{n}$. We can then assign the $(n+1)$th a small circle around the center, and subsequent new players rings around that one (swallowing part of the inner circle), and so on. In this way,...


5

The game is actually an instance of two-persons Pebble game, as @HendrikJan pointed out, and as such is proven to be $EXPTIME-complete$. The following is a summary based on a proof by Kasai, Adachi and Iwata in SICOMP 8 (4). For starters, it's pretty obvious that the game is in $EXPTIME$ - we can simply check all the possible games and see if there is ...


5

Stan has two pure strategies for each type of card. Since there are three types of cards (H, M, L), in total he has $2\times 2\times 2 = 8$ strategies. Here is a list of them: Always stay. Always raise. Stay only if H. Stay only if M. Stay only if L. Raise only if H. Raise only if M. Raise only if L.


5

The running time of algorithms for linear programming depends not only on the number of variables but also, unsurprisingly, on the number of constraints. This is hidden in the parameter $L$ which is the input size; clearly $L$ is at least the number of constraints. If there are exponentially many constraints, then any generic algorithms must take exponential ...


5

Minimax strategies apply to games with scores. A minimax strategy maximized the guaranteed score. Assuming that you prefer a win to a draw and a draw to a loss, you can choose three scores $a > b > c$ arbitrarily and assign them as your value in the case of a win, a draw, and a loss, respectively.


4

They probably meant you to solve it using dynamic programming. Since I'm guessing this is an exercise, I won't say anything more on this front. Also, your program is incorrect: it doesn't consider the actions of Bar. The game is not really a game of strategy, since there are no choices involved, only chance. In order to compute the expected value that Foo ...


4

Shameless Advertisement: Game Theory proposal on Area 51 that you should totally follow! No. The easiest way to prove this is by counterexample. Expanding matching pennies, we can create a game with two mixed strategies (players either mix between A and B or between C and D): What might be true about that statement is for a mix of particular pure ...


4

The flaw is that your definition of "game" is deficient and does not correspond to our intuition. We also need a restriction on the number of moves that are possible at any position in the game. It doesn't really have anything to do about computability, so much as about the notion of what it means for a game to be finite. Usually we define a game as ...


4

The index set of the max operation is $A_i$, the actions of player $i$. The formula says: take each such action $a_i \in A_i$ and compute its regret (with the sub-formula you say you can implement easily), and then take the maximum of those regrets. The reason for the $\max(R,0)$ is that actions with negative regrets are performing worse than the action ...


4

Nash proved that every zero-sum game has a perfect strategy called a Nash equilibrium. This is a possibly randomized strategy for both players such that given that one player follows the strategy, it doesn't pay the other player to deviate from her strategy. As an example, consider the game rock, paper, scissors. One Nash equilibrium here has both players ...


4

An example for Expectimax (root node is a Max node): (image from CSE AI Faculty / Dan Klein, Stuart Russell, Andrew Moore) changing the evaluation function changes the action taken. For Minimax, since $f_1(s_i) \ge f_1(s_j) \implies f_2(s_i) \ge f_2(s_j)$, the best node (action taken) doesn't change (Minimax is insensitive to monotonic transformations):


4

Robert Israel's answer on Math Overflow provides the key insight: If $S$ is the set of players remaining alive and it is player $j$'s turn, player $j$ should shoot at the player $k$ such that, if $k$ dies, the remaining set gives $j$ the best survival chances. This enables us to build a dynamic programming algorithm, as Robert Israel states. I'll explain ...


4

Let $v(x) = \frac{V(x) - V(0)}{V(1) - V(0)}$ so $v(x)$ nicely goes from $0$ to $1$. Maximizing $v$ also maximizes $V$. To cover my ass for future mistakes regarding $<$ vs $\leq$, I will assume that you will never exactly guess $x = h$. Now, if $n = 1$, we can find the expected value from cutting at $x$ by integrating over all possible $h$: $$e_1(x) = E[...


4

I don't think it's possible in CTL nor LTL to model two competing players. You would probably need ATL (Alternating-time Temporal Logic). In ATL, the formula $\langle\langle A \rangle\rangle \phi$ says that agent (or coalition) $A$ can enforce $\phi$ to come about. In your case, $\langle\langle P_1 \rangle\rangle \text{Win}_1$. In modal µ-calculus, it ...


4

Here is a proof by induction. The base case, $n = 2$, is clear. Now consider a tournament in which $p_1$ wins. Suppose first that the first competition doesn't involve $p_1$. Let the new set of players be $p_1,P$. By induction, we know that $p_1$ must beat one of the possible winners of the tournament in $P$, say $p_i$. Since the first competition didn't ...


3

Because - according to the rules above - each player must divide a stack into two stacks that must be unequal.


3

The authors you cite have another paper on the topic. Would you be satisfied with a model which assumes that the properties of the surfaces to be allocated can be summarized by an arbitrarily large but finite set of one-dimensional parameters (say length, depth, northmost point, eastmost point,... really as many as you want but finite) ? If this is ...


3

O1(s) = 3. You missed another diagonal.


3

Inside the function Minimax-Value, see the line where it says "the highest Minimax-Value of..."? That is implicitly a recursive call to the Minimax-Value function, i.e., a call to yourself.


Only top voted, non community-wiki answers of a minimum length are eligible