# Tag Info

## Hot answers tagged game-theory

### 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 ...
• 2,062

### 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 ...
• 5,400
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 ...
• 13.6k
Accepted

• 121

### 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 ...
• 278k
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)...
• 278