Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [two-player-games]

The tag has no usage guidance.

1
vote
0answers
100 views

Is this algorithm similar to any none in the literature?

I thought of the following algorithm for game AI, which is kind of a mashup of miniMax and Monte Carlo Tree Search. We assume that we have a heuristic function that assigns game states a value in the ...
1
vote
0answers
215 views

Impagliazzo lemma, unclear detail in its proof

In Arora-Barak's book on page 378 in the proof of Impagliazzo's Hard Core lemma why did they choose the number 50 in this line: Set $t = \frac{50n}{\epsilon^2}$ ? How this choice then yields the size ...
0
votes
0answers
40 views

Digraph game reduction problem

Let A and B be 2 players and D=(V,E) a digraph and v0 an fixed vertex. A chose v0 v1 B chose v1 v2 and so on.The player who can't chose anymore loses.(they are not allowed to chose an edge adjacent ...
12
votes
1answer
653 views

Have these coloring games been solved?

In the paper "On the complexity of some coloring games", Bodlaender gives some open questions about the complexity of deciding if player 1 or 2 has a winning strategy in some graph coloring games. ...
12
votes
1answer
429 views

Practical applications of parity games

Are there examples of practical applications of parity games, ie systems, in the real world, that can be represented as parity games ? Usually related documentation on parity games has almost never a ...
7
votes
1answer
209 views

Is there a gadget that reduces generalized geography to undirected graphs?

The directed Generalized Geography game is well-known to be PSPACE-complete, however, I could not find anything for the undirected version. I saw that in Hans L. Bodlaender, Complexity of path-forming ...