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

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?

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.

StackExchange Computer Science Q#12284, answer score: 4