Is there an algorithm to find the best strategy for a game?

Question

Let,

• game be the state of a 2-player, turn based game
• actions game player -> [move] be a function that gets the state of a game and returns all valid moves, where a move if a function move game -> game that updates the state of the game
• state game -> state returns wether a game is incomplete, won by player1 or won by player 2

Countless games such as chess and tic-tac toe can be described this ways. Is there an algorithm that, given such description, returns the optimal strategy, where strategy takes the game state as input and returns the optimal move for that turn?

Answer 1

Your notion of "strategy" is very ill defined. Exactly what kind of object do you want this algorithm to return? Do you want it to return another algorithm?

There is an algorithm which takes a current board state and returns the optimal move. It's called Mini-Max, you can read about it here. It basically is a depth-first search for a move that doesn't allow for a losing situation. It's called minimax because it alternates for one player minimizing the benefit for player 1 (i.e. player 2) and the other player maximizing the benefit for player 1 (i.e. player 1).

There are techniques, such as Alpha-Beta pruning, which make Minimax faster, however, it is still painfully slow. For Tic-Tac-Toe, it works. For chess, a complete run is completely infeasible. In practice, instead of doing a full search, the search is done to a specific level, and then heuristics are used to evaluate which game states are the most favorable.

So, technically, an algorithm which always returned minimax would fulfill your requirement for a strategy: you could give it a game state and it would output the possible move. However, this is far beyond the capabilities that computers will ever have: expanding the full minimax tree would probably take more memory than there are atoms in the universe.

Answer 2

If we consider finite deterministic games, then there is always an algorithm that calculates if one of the two players have a winning strategy or one of the two players can force a draw (just make a full search on the game space) ... the problem (as noted by jmite) is that it requires too much time and space :-)

But if we consider games that are "unlimited" (in some way), then there are two-person win-lose games (rather artificial) with decidable rules but no computable winning strategies.

A classical example is the following: given a computable function $f: \mathbb{N}^{m} \to \{A,B\}$, the two players alternately choose a natural number $x_i$ (player A begins). The games ends after $m$ turns (suppose that $x_1, x_2, ..., x_{m}$ are the picked numbers); the winner is player $A$ if and only if $f(x_1, x_2, ..., x_{m}) = A$. For this game, given $m$ and $f$, there is no algorithm that can tell you if A (or B) has a winning strategy. Rabin [Rab57] proposed a similar simple three moves game (m = 3) for which player B has a winning strategy, but it is not computable.

A still open problem (as far as I know it is still open :-) is a chess game played on an infinite board:

Given a finite set of chess pieces and their position on an infinite bidimensional $\mathbb{Z} \times \mathbb{Z}$ board, is there a winning strategy for white?

For other references see: J. P. Jones, Some undecidable determined game

(I'm not an expert, and I would like to know if there are more natural undecidable games)

[Rab57] Michael O. Rabin, Effective computability of winning strategies, Contributions to the theory of games, vol. 3, Annals of Mathematics Studies, no. 39, Princeton University Press, Princeton, N. J., 1957, pp. 147-157.

Answer 3

If you are referring to a generalization of games, you should have a look at General Game Playing.

As an alternative to traditional, search-based methods such as minimax/alpha-beta, there is also a simulation-based method called monte carlo tree search..