11

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 ...


8

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 $...


8

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 ...


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 ...


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). ...


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,...


6

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

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

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

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

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

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

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

In short, minimax is what you're looking for. We say that a game is valued $1$ if player 1 wins, $-1$ if player 2 wins and $0$ if it's a tie. You have your brute-forced game tree. At each level you check who's turn it is. If it's player 1's turn, he/she will try to maximize the outcome. If it's player 2's turn he/she will try to minimize the outcome. So ...


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 ...


4

In a game-theoretical sense, both of the moves you describe are equally good in the scenarios you describe, so the algorithm is "correct" in that it doesn't matter which move it picks -- you do not explicitly encode a preference for faster wins (or faster gains of $+100$) over slower scores. Introducing a discount factor to explicitly encode such a ...


4

The short answer is, Player two wins if and only if the corresponding graph admits a matching that "covers" the set $H$. Here is a bit of explanation. Your idea is almost right. However, the proof is not intuitive and you might miss some details which you need if it is a theoretical question or if you need to design the exact winning strategy and not only ...


3

"To be impartial, a game must satisfy these three conditions". My understanding is that what makes a game impartial or partisan is purely a function of whether or not the same plays are available to both players. Chess is partisan because there are black and white pieces, and players can only move their own color. The other two conditions listed are not ...


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.


3

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


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

The answer assumes that you have to take the same amount of stones from each pile that you choose. Otherwise the first player always wins as long as the piles are not all empty. The rule "xor = 0" doesn't work. In particular, there is a winning position with xor = 0 (easy exercise; be creative). In order to analyze the game, you can compute which ...


3

I assume there are k piles and each pile can have stones in the range [0,n]. Then we can find the losing positions ( you can subtract from total to get no. of winning positions ) using dynamic programming. Let the number of bits in binary representation of n be b. We take a 2-D array called dp of size $kx2^b$, where dp[i][j] denotes number of ways of ...


3

From my experience of solving some other games, usually there is a huge difference between optimal player and an average player or even state-of-the-art engine. I bet the results for any other player then optimal will diverge from the results of optimal play. For example see what happened with some famous chess positions when endgame tables where developed (...


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