Skip to main content
10 votes

In what ways can we distinguish between a human and bot behavior?

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 ...
manlio's user avatar
  • 2,062
8 votes

Solve parity game in polynomial time?

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 ...
Thomas Klimpel's user avatar
5 votes
Accepted

How does "solving" a game like connect four or tic-tac-toe work?

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 ...
orlp's user avatar
  • 13.6k
5 votes
Accepted

In Minimax, how should we handle draws?

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 &...
Yuval Filmus's user avatar
5 votes
Accepted

Why does Min-Max algorithm delays a good move indefinitely?

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 ...
Dennis Soemers's user avatar
4 votes
Accepted

Solving the 10 players duel game

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$ ...
D.W.'s user avatar
  • 161k
4 votes
Accepted

Optimal strategy in repeated cake-cutting

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 ...
orlp's user avatar
  • 13.6k
4 votes
Accepted

How to express the existence of winning strategy of the starter of a game in temporal logic?

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$ ...
Pål GD's user avatar
  • 16.7k
4 votes
Accepted

Must the champion of an entire tournament beat the champion of a possible tournament among other players?

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 ...
Yuval Filmus's user avatar
4 votes
Accepted

Winning strategy for a given game on graphs

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 ...
Narek Bojikian's user avatar
3 votes
Accepted

Unique Stable Solution in Stable Marriage Problem: Is it Pareto-efficient and a Nash Equilibrium?

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 ...
Discrete lizard's user avatar
  • 8,303
3 votes
Accepted

Analysis of the Banana Game

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 ...
Yuval Filmus's user avatar
3 votes

How does "solving" a game like connect four or tic-tac-toe work?

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 ...
gnasher729's user avatar
  • 30.5k
3 votes
Accepted

Analysis of komi values for increasing Go board sizes and agents strength

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 ...
kubus's user avatar
  • 46
3 votes
Accepted

Winning strategy of Nim game when picking from multiple piles is allowed

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" ...
Yuval Filmus's user avatar
3 votes
Accepted

Why isn't chess an impartial game?

Yes, I believe your changes turn chess into an impartial game. As you mention, stalemate and three-fold repetition can be dealt with by declaring loss. Your trick decouples players (P1 and P2) from ...
sdcvvc's user avatar
  • 3,491
3 votes

Why isn't chess an impartial game?

"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 ...
DukeZhou's user avatar
  • 249
3 votes
Accepted

Evaluation functions of Minimax algorithm

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, ...
manlio's user avatar
  • 2,062
3 votes
Accepted

Number of winning combination in Nim

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 ...
advocateofnone's user avatar
3 votes

Determining the existence of a forced win vs determining the best outcome

They are equivalent under Turing reductions, assuming that the game has finite/polynomial-size branching factor (i.e., only that many moves are possible from each position). I don't know if they are ...
D.W.'s user avatar
  • 161k
3 votes

Why does Min-Max algorithm delays a good move indefinitely?

This is because you are not using a discount factor in your search. A discount factor $\gamma$ is a number between 0 and 1. The discount factor describes the preference of an agent for current ...
ryan's user avatar
  • 4,511
3 votes
Accepted

Zero-Sum Games and Halting Problem

Turing proved that the halting problem is undecidable. No algorithm that you can come up with will solve the halting problem.
Yuval Filmus's user avatar
3 votes
Accepted

What is the optimal algorithm for playing the hangman word game?

It is possible to compute the optimal strategy, but the computation might be fairly intensive, and I'm not sure whether it will give you much of a gain over simple heuristics. I'll explain how below. ...
D.W.'s user avatar
  • 161k
3 votes
Accepted

how does the shap algorithm work in polynomial time?

First, some notation. A decision tree is a binary tree in which each internal node is labelled by one of $x_1,\ldots,x_n$, and has two outgoing edges labelled $0$ and $1$. Leaves are labelled with ...
Yuval Filmus's user avatar
2 votes

Number of winning combination in Nim

(added) As I now realise, you are asking for the number when the total number of stones is given. It seems to be easy to count the number of loosing positions when the maximum number of stones in ...
Hendrik Jan's user avatar
  • 30.8k
2 votes
Accepted

Reccurrence for the game of pile of stones

AS I asked for hints only, apart from the hints I have provided one can solve the question with grundy numbers.
advocateofnone's user avatar
2 votes

Metagame Paradox: what is wrong with this explanation?

This is a set theory paradox, rather than a computability paradox. Let us define: a game is any set $X$. The initial game state of game $X$ is the set $X$ itself; taking a move means moving from a set ...
Mike Rosoft's user avatar
2 votes

Nim Games: Is it possible to reduce following using Grundy Number?

Your game is an impartial game, and so it is covered by the Sprague–Grundy theorem, which say that it is equivalent to a "nimber". Note that the state of the game consists of the current value of the ...
Yuval Filmus's user avatar
2 votes
Accepted

Complexity of parity game solving compared to PLS, PPA, and PPAD

Yes, solving parity games is known to be in PPAD (and thus PPA and PPP too) and PLS, and is thus unlikely to be hard for either (since this would imply containment of one of these classes in the other)...
Rahul Savani's user avatar
2 votes

Fair division of two-dimensional cake

I did not find a suitable answer, so I had to write one myself. It was the first part of my Ph.D. thesis. There are still a lot of open questions in this field.
Erel Segal-Halevi's user avatar

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