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

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

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.


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

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

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

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

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

"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

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


3

Your instructor might have been reading the article Stackable and queueable permutations by Peter G. Doyle, who considers two exercises in Knuth's Art of Computer Programming. The context is that the string in question is a sequence of distinct numbers, and the task is to output them in increasing order (Doyle's article actually discusses the other ...


3

First, while the Gale-Shapely algorithm guarantees that at least one stable matching exists, it need not be unique$^*$. However, note that when the male-optimal and female-optimal matchings are the same, the stable matching is indeed unique, as shown in this answer. As the male-optimal and female-optimal matchings coincide, both can be considered the '...


3

For simple games, you use the following strategy: You check whether a game position is won, lost, drawn, or not decided yet. In the first three cases, the position has a value of +1, -1, or 0. In the latter case, you try out all your possible moves, calculate the value of every move recursively, and the value of the position is the value created by your ...


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