2
$\begingroup$

Note: this is basically a more precise restatement of this question, which didn't get proper answers because it was vague.

Most two-player perfect information games can be represented as a finite directed graph, because although the games could theoretically go on forever, there are only finitely many possible states for the game. Chess fits into this category, for instance. Here we'll consider states to be distinct even if the only difference between them is whose turn it is, thus our directed graph is always two-colorable with the colors "White's turn" and "Black's turn".

Given a directed graph $G$ with such a two-coloring, with one priveleged node called the "initial node", a strategy for a player $P$ is a partial function $s:N(G)\to N(G)$ such that:

  1. $s$ is defined only on nodes at which it is $P$'s turn.
  2. If $s$ is defined at a node $A$, then $s(A)$ is a child of $A$.
  3. If $s$ is defined at a node $A$, it is defined at all children of $s(A)$.
  4. $s$ is defined on the initial node, or on all children of the initial node if $P$ goes second.

Now, I'll call a complete path through $G$ a path through $G$ starting at the initial node which either goes on forever or ends at a node with $0$ out-degree, such nodes are called endstates. If $S$ is some set of complete paths, we will say that player $P$ can force $S$ iff there exists a strategy for $P$ such that any complete path which obeys that strategy (I think it's obvious what this means) is in $S$.

Some endstates are marked as victories for White, some are marked as victories for Black, some are marked as draws. Let $W$ be the set of all complete paths ending in a victory for White, $B$ be the set of all complete paths ending in a victory for Black, and $D$ the set of complete paths ending in a draw. Let $I$ be the set of all infinite complete paths, which we will also conceptually think of as draws.

It is then a theorem that either White has a strategy that forces $W\cup D \cup I$, or Black has a strategy that forces $B\cup D \cup I$, or both.

Is there an algorithm which, given such a description of a game, outputs which players have such a strategy, along with the strategy itself?

I don't mind if no such algorithm is actually known, but is there an existence or impossibility proof?

$\endgroup$

3 Answers 3

2
$\begingroup$

(Note that you're excluding games with randomness, such as backgammon.)

Yes. In particular, endgame tablebases use most of such an algorithm.

Wbool,Wfull,Bbool,Bfull = set(),set(),set(),set()
keep_going = False
for v in nondraw_endstates:
 keep_going = True
 if is_a_victory_for_white_(v):
  Wbool.insert(v)
  Wfull.insert([v,0])
 else:
  Bbool.insert(v)
  Bfull.insert([v,0])
n = 1
while keep_going:
 keep_going = False
 for v in Wbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Wbool:
    continue
   if white's_turn_(u):
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Wbool:
     avoidable = True
     break
   if not avoidable:
    Wbool.insert(u)
    Wfull.insert([u,n,v])
    keep_going = True
 for v in Bbool:
  for u in nodes_with_an_edge_to_(v):
   if u in Bbool:
    continue
   if not white's_turn(u):
    Bbool.insert(u)
    Bfull.insert([u,n,v])
    keep_going = True
    continue
   avoidable = False
   for x in nodes_with_an_edge_from_(u):
    if x not in Bbool:
     avoidable = True
     break
    if not avoidable:
     Bbool.insert(u)
     Bfull.insert([u,n,v])
     keep_going = True
     continue
 if (initial_node in Wbool) or (inital_node in Bbool):
  keep_going = False
 else:
  n = n+1

Suppose the game is locally finite. If white has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Wfull's triples to all non-endstate white nodes is a winning strategy for white. ​ If black has a winning strategy then the while loop will terminate and every extension of the result of removing the middle entries from Bfull's triples to all non-endstate black nodes is a winning strategy for black. If only finitely many nodes can reach the non-draw endstates and neither side has a winning strategy then the while loop will terminate and white can always stay out of Bbool and white doing so guarantees that white won't lose. Bblack can always stay out of Wbool and black doing so guarantees that black won't lose.

If the while loop terminates, then it does so in an amount of time that's bounded above by a polynomial in (the number of nodes that can reach the non-draw endstates). Furthermore, by reduction from the circuit value problem, deciding who has a winning strategy is P-complete even when $G$ is (finite and) acyclic and there are no draw states.

$\endgroup$
1
$\begingroup$

As for chess - people use Negascout with heuristics, heavy prunning and results are poor. This comes from fact that branching factor is high.

If you have high end computation power this game is still far from being solved (which means that for every configuration you have winning strategy or draw at least).

More sophisticated games like Hex are very hard to solve - but this comes from complexity.

There are no algorithms to show strategy for player. You have to keep in mind that even gor chess people are using heuristics and change strategy addapting to oponent moves (this statement comes from my own experiments, tracking emotions and behaviour during game). So people are not repeatable players. This goes on to misleading strategy description.
Another one is number of gamed played - to get some indicator of strategy or ELO rating the more games played the better, but I do not know any human that would play for example 20000 games to define strategy, and this will change from mere fact of playing.

If nobody will give working algorithm I think it is good to treat this as too heavy computing power requirement. If you are not bothered by this good old Minimax will give you moves, but will not return patern of moves per player.

If you are able to provide solution to game - there is no indication that strategy tracking or creating good player is not possible - but still for human players there is a bit randomness in moves.

$\endgroup$
8
  • $\begingroup$ This is more of an answer to the question "Are there fast, known algorithms used in practice to solve games", but I was asking the more theoretical question "Is there a mathematical proof that no Turing machine exists capable of solving all games". $\endgroup$
    – Jack M
    Commented Dec 12, 2015 at 16:34
  • 1
    $\begingroup$ Ok. There is no proof for that. Sorry for misunderstanding. I think the point is still valid - disregarding "practical application" - pure Minimax will solve all games for you. The proof for that is straightforward by state exhaustion - you have all game states so you have full knowledge how to play. If this is still too weak, I will delete post. Have fun. $\endgroup$
    – Evil
    Commented Dec 12, 2015 at 17:00
  • $\begingroup$ I'm fairly sure minimax only applies to games with a finite game tree, no? $\endgroup$
    – Jack M
    Commented Dec 12, 2015 at 17:08
  • $\begingroup$ Well, if your strategy blocks infinite range, than it could be applied. For games like chess there are rules like 50 moves to terminate game. Repeated moves are blocked. For checkers oscilating pattern is considered a draw - so with full ruleset this games are finite. Proper games - let me call them like that, are those who are playable by humans in finite time - but sure anyone can invent game to be infinite in nature - but nobody will play it. If you are interested also in games that are infinite - I have no valid argument against, and please update question to reflect also that requirement. $\endgroup$
    – Evil
    Commented Dec 12, 2015 at 17:14
  • 1
    $\begingroup$ @David Richerby ok, thank you for your example. My additional question was beyond OPQ, and your answer is awesome. $\endgroup$
    – Evil
    Commented Dec 12, 2015 at 17:53
-1
$\begingroup$

No. I believe that if we consider games that include draws (such as chess), and if we use a board that it is arbitrarily large (i.e. "infinite"), and if we use some huygens chess pieces (a huygens is a chess piece which jumps prime numbers of squares), then no algorithm can solve such a game. This is because the set of prime numbers itself is not completely known.

$\endgroup$
3
  • $\begingroup$ What do you mean by "the set of prime numbers itself cannot be completely defined"? $\endgroup$ Commented Jul 24, 2017 at 14:03
  • $\begingroup$ I'm sorry, the complete set of prime numbers has not been calculated. I suppose it's defined, but there's an infinite number of them, and there is no simple way to find them, and there is no complete list of primes. (I changed my comment to make it a little more clear). $\endgroup$ Commented Jul 24, 2017 at 14:07
  • $\begingroup$ The question says that it is asking about games that can be represented as a "finite directed graph". Thus, examples involving infinite games aren't relevant here. $\endgroup$
    – D.W.
    Commented Jul 24, 2017 at 17:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.