Answers.Body: <p>See <a href="https://en.wikipedia.org/wiki/Endgame_tablebase" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Endgame_tablebase</a>.</p>
  <p>With infinite computer power, one could build such a table for the starting position and <a href="https://en.wikipedia.org/wiki/Solving_chess" rel="nofollow noreferrer" title="solve chess">solve chess</a>.</p>
  <p>In practice, only positions with up to seven &quot;men&quot; (pawns and pieces, counting the kings) have been solved using current supercomputers, so we are very far from solving chess. The complexity of the problem increases exponentially with the increase in the number of pieces.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T22:49:42.770Z
Answers.Text: As a side note, if you actually produced such a table, no matter what you stored the information on, it would weigh roughly 10^43 times as much as the observable universe; considering there are ~10^123 possible chess positions and only ~10^80 baryons in the observable universe.
Answers.UserDisplayName: Shufflepants
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T23:12:20.327Z
Answers.Text: Can this answer be summarized as "retrograde analysis is an algorithm that would solve chess if given an infinitely powerful computer"?
Answers.UserDisplayName: ryanyuyu
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T23:46:18.243Z
Answers.Text: @Shufflepants who said i was storing it using baryons?
Answers.UserDisplayName: Michael
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T00:24:48.507Z
Answers.Text: @ryanyuyu, yes, pretty much. Isn't it amazing what one can do when resources are infinite? The universe being finite is just a technicality. :-)
Answers.UserDisplayName: itub
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T10:01:17.683Z
Answers.Text: @Shufflepants FWIW If I calculated correctly then you could store it in a black hole with a radius in the range of 10^24 - 10^25 km. That's only a few times the size of the observable universe...
Answers.UserDisplayName: Christoph
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T14:58:48.633Z
Answers.Text: @Christoph And assuming conservation of information, and assuming you had a detector and your super computer with infinite processing power, you could slowly over the course of something like a googolplex years read out the tablebase as hawking radiation.
Answers.UserDisplayName: Shufflepants
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T17:50:59.637Z
Answers.Text: @Shufflepants Note that an actual winning strategy might require much less space than a full tablebase. For instance, Nim has a winning strategy that is simple to describe, there is no need to build a huge table of all possible states.
Answers.UserDisplayName: Federico Poloni
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T09:57:15.827Z
Answers.Text: This solution as stated is not viable.  The mass of such a table would form a black hole and it would be impossible to exfiltrate data from it.
Answers.UserDisplayName: emory
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-19T17:50:27.597Z
Answers.LastActivityDate: 2020-08-25T09:49:31.977Z
Answers.LastEditDate: 2020-08-25T09:49:31.977Z
Answers.UserDisplayName: itub
Answers.Body: <p>If you really had <em>infinite</em> processing power, such an algorithm would be actually <strong>trivial</strong> to write. As chess has a <a href="https://www.webcitation.org/5oFLE7Mgx?url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf" rel="noreferrer">finite</a> number of possible states, you could in theory just iterate through them all until you find a path of perfect play. It would be horribly inefficient, but if you have <em>infinite</em> processing power, it wouldn't matter.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T20:05:33.030Z
Answers.Text: That's not true. He said you have infinite processing power, but not did not say anything about infinite space.
Answers.UserDisplayName: ubadub
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T21:35:01.717Z
Answers.Text: @ubadub : We wouldn't need infinite space. The length of a game is limited due to the 50-move rule, and a rule can be made up to sort all possible moves from a position. As they can be sorted, they can be stored as an integer. This is all the memory required to walk the whole tree. And if you have infinite time, you can walk the tree as often as you want, so you don't have to store every possible chess game.
Answers.UserDisplayName: vsz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T23:43:36.527Z
Answers.Text: The length of the game is limited, but it is extremely large; as someone else pointed out, if you produced a table to store all such games, "no matter what you stored the information on, it would weigh roughly 10^43 times as much as the observable universe; considering there are ~10^123 possible chess positions and only ~10^80 baryons in the observable universe
Answers.UserDisplayName: ubadub
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-24T09:57:47.100Z
Answers.Text: @ubadub : That is true, but I was not talking about "a table to store all such games". There are many tree-related algorithms which don't have to hold all the nodes of the whole tree in memory.
Answers.UserDisplayName: vsz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-25T02:45:01.637Z
Answers.Text: @ vsz good point
Answers.UserDisplayName: ubadub
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T07:27:26.710Z
Answers.LastActivityDate: 2017-12-20T07:27:26.710Z
Answers.UserDisplayName: vsz
Answers.Body: <p>To directly address the question: yes there is such an algorithm. It is called minimax. (The endgame tablebases are generated by using this algorithm (backwards!), but the plain old simple minimax algorithm is all you need). This algorithm can play any two player zero sum game perfectly. Find pseudocode here:</p>
  <p><a href="https://en.wikipedia.org/wiki/Minimax" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Minimax</a></p>
  <p>note that variants of this algorithm are used by modern computer chess programs.</p>
  <p>This algorithm basically generates the move which will minimize the opponent's chances, i.e., it would choose a move for White that is +2 instead of +1. Then, it generates the opponent's move which will maximize his chances, i.e., it would choose a move for Black that is -2 instead of -1.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-01T00:02:15.260Z
Answers.Text: I understand the minimax with an evaluation that can be ordered for a given partial tree with many leaves.  But I get lost even with a 2 outcome class big enough branching degree tree.    I should be able to scale down the minimax to having the trivial ordering of win and lose..  Say.  just binary tree even. 2 paths at each node to chose, even without any transposition, how is one comparing compounded min max operations backward when there is no addition defined. Are my simplificatoin assumptions having consequences that distort the reasoning.  What would the minial tree to show my flaw be.
Answers.UserDisplayName: dbdb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-01T00:06:39.767Z
Answers.Text: by addition I may have assumed the tree to have enough outcome diversity so that I could pick.  I guess the one just have to pick the exiting win if there . or the next best of the outcomes.  Having fine grain outcome forcasters to perdict those might be my real problem.  But being able to back track from an win leaf should be possible. it existend and the branch leading there would be the one side win choices, and if there existed a branch out of the opponent choices, that was not win, then.  what.  I guess not good at this.
Answers.UserDisplayName: dbdb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-01T00:07:33.370Z
Answers.Text: Should I make this a min max confusion question?  Please find my reasoning flaw, or missing chunk from the premises I did not apply yet?
Answers.UserDisplayName: dbdb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-20T05:31:29.890Z
Answers.LastActivityDate: 2020-08-25T09:51:31.450Z
Answers.LastEditDate: 2020-08-25T09:51:31.450Z
Answers.UserDisplayName: chessprogrammer
Answers.Body: <p>Not only is there an algorithm to play perfect chess, it is possible to write a short program that will (given infinite resources) play <em>any deterministic perfect-knowledge finite-duration two-player game</em> perfectly.</p>
  
  <p>The game engine does not even need to know the rules of the game it is playing. All it needs is an opaque representation of a "game state" and functions that (a) given any game state, provide a list of legal next game states and (b) given a game state, decide if it is a win for player 1, a win for player 2, a draw, or it is not an end state.</p>
  
  <p>Given those functions a simple recursive algorithm "solves" the game.</p>
  
  <p>This fact has been alluded to in previous answers by chessprogrammer (minimax) and by Acccumulation (who provides a version of the program in python).</p>
  
  <p>I wrote such a program over 20 years ago. I tested it by playing noughts-and-crosses (tic-tac-toe if you are American). Sure enough it played a perfect game.</p>
  
  <p>Of course this will fall over quickly on any imaginable computer for any serious game. Because it is recursive it is effectively building the entire game tree on the stack, so you will get a "stack overflow" (pun very much intended) before you get anywhere near analysing the 10^123 states of chess referred to in other answers. But it is fun to know that in principle this small program would do the job.</p>
  
  <p>For me this also says something interesting about AI: however much "intelligence" you think is exhibited by Deep Blue, or Go Zero, or indeed by a human playing Chess or Go there is a sense in which these games have trivial, exactly computable optimal solutions. The challenge is how to get a good though not optimal solution in a reasonable time.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-22T18:59:15.120Z
Answers.Text: Your algorithm only works for perfect-knowledge two-player games.  It will fall over for hidden-information games such as [Stratego](https://en.wikipedia.org/wiki/Stratego), because any implementation of function (a) violates the game rules.  It also fails for games of potentially infinite duration: for example, drop the 50-move rule from chess, and it can't tell that two kings chasing each other around the board isn't a winnable state.  All it can tell is that it's not an end state.
Answers.UserDisplayName: Mark
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T19:36:44.923Z
Answers.Text: Valid points. I will edit my answer.
Answers.UserDisplayName: gareth
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T10:53:01.253Z
Answers.LastActivityDate: 2017-12-23T19:38:22.493Z
Answers.LastEditDate: 2017-12-23T19:38:22.493Z
Answers.UserDisplayName: gareth
Answers.Body: <p>I will ignore the possibilities of draws or infinite sequences of moves for simplicity. Once the algorithm is understood, it is not particularly difficult to extend it to those cases.</p>
  
  <p>First, some definitions:</p>
  
  <ol>
  <li><p>Any move that wins the game for the player who makes that move is a winning move.</p></li>
  <li><p>Any move that loses the game for the player who makes that move is a losing move.</p></li>
  <li><p>Any move that leaves the other player with at least one winning move is also a losing move. (Since the opponent can take that move and force a loss.)</p></li>
  <li><p>Any move that leaves the other player with only losing moves is also a winning move. (No matter what move your opponent makes, you will win.)</p></li>
  <li><p>A perfect strategy means always making winning moves if any remain and resigning when one has only losing moves remaining.</p></li>
  </ol>
  
  <p>Now, it's trivial to write a perfect strategy. Simply explode all possible move sequences and identify winning/losing moves. Ignoring stalemate, this will eventually identify every move as either a winning move or a losing move.</p>
  
  <p>Now, the strategy is trivial. Look at all your possible moves. If any winning moves remain, take one and win. If only losing moves remain, resign, since your opponent can force you to lose.</p>
  
  <p>It is not difficult to adjust the strategy to include the possibility of a stalemate.</p>
  
  <p><strong>Update</strong>: Just in case it's not clear how this identifies every move as a winning more or a losing move, consider:</p>
  
  <ol>
  <li>Every move that results in a win is a winning move.</li>
  <li>Every move that results in a loss is a losing move.</li>
  <li>Every move that results in the opponent having only winning or losing moves is either a winning or a losing move.</li>
  <li>Call <code>n</code> the number of moves in the longest possible chess game. (We are ignoring unbounded sequences for now, though including them is not difficult.)</li>
  <li>There are no moves with <code>n</code> prior moves we need to consider.</li>
  <li>Every move with <code>n-1</code> prior moves is either a winning move or a losing move since <code>n</code> moves ends the longest game.</li>
  <li>Thus every move at depth <code>n-2</code> is followed by only winning moves or losing moves and thus is itself a winning move or losing move.</li>
  <li>And so on back to the first move.</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T20:47:55.667Z
Answers.Text: Your definitions of winning and losing moves are not comprehensive enough. The first move, for instance, neither wins the game (#1), nor leaves the opponent with only losing moves (#4), so it isn't a "winning move". Neither does it lose the game (#2), nor leave the opponent with any winning move (#3), so it isn't a "losing move". Your strategy requires that every move is defined either as a "winning move" or a "losing move", which simply isn't the case as you've defined it.
Answers.UserDisplayName: Nuclear Hoagie
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T20:59:26.350Z
Answers.Text: @NuclearWang It does define every move as either a winning move or a losing move. What do you think the third alternative is? Visualize the tree of all possible chess games (and remember, we're excluding ties or infinite sequences for now). Every chain ends in either a win or a loss. This percolates up through the tree eventually identifying every move as either a winning move or a losing move.
Answers.UserDisplayName: David Schwartz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T21:04:45.020Z
Answers.Text: @NuclearWang either the first move *is* a winning move for one player, or else chess is (like tic-tac-toe) a drawn game with perfect play. We don't know which because no one has ever had the computing power to run this algorithm to completion, and no one has found a more direct proof.
Answers.UserDisplayName: hobbs
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T21:22:36.997Z
Answers.Text: There is no randomness and no hidden information in chess, which leaves no room for "maybe". Every position is won, lost, or drawn (even if we haven't managed to *identify* them as such). And this explanation is leaving out the "drawn" option for simplicity, but it mostly amounts to 1) a position is drawn if it's drawn according to the rules, and 2) a position is drawn if it has no winning moves, but has at least one move that leaves the *opponent* with no winning moves.
Answers.UserDisplayName: hobbs
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T14:25:00.343Z
Answers.Text: @hobbs the first move could (it's unlikely to say the least.... but still) be a "losing move" for white, how can you exclude that?
Answers.UserDisplayName: Francesco
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T16:36:17.597Z
Answers.Text: In what sense would resigning ever be a better strategy than playing an arbitrary move?  Unless one knows that one's opponent is perfect and in good health, I see no reason to believe that picking a move at random would not yield some non-zero probability of winning (even if the opponent would have nothing but forced winning moves the opponent forfeit because of time or other considerations).
Answers.UserDisplayName: supercat
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T18:04:20.973Z
Answers.Text: @supercat Sure, one can try to trick one's opponent into making a mistake, but there's a lack of perfection in that strategy. If you accept that sometimes you should make a move just in the hopes that it will cause your opponent to make a mistake or you might benefit from your opponent's quirks, then there is no such thing as perfect chess.
Answers.UserDisplayName: David Schwartz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T18:27:16.157Z
Answers.Text: @DavidSchwartz: Unless someone is in a losing position, every move that isn't perfect is bad.  In a losing position, there would generally be no single "perfect" move [except in a forced-move situation] since any legal move could have some probability of being the only winning or drawing move in some conceivable (possibly highly contrived) circumstances.  Resigning, however, would seem the unambiguous worst "move".  Suppose the game is proven solved as a win for White with d4.  Would you want to play a chess program which responded to `1. d4` with `...resigns`?
Answers.UserDisplayName: supercat
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T18:28:19.377Z
Answers.Text: @supercat And yet, it is the perfect move.
Answers.UserDisplayName: David Schwartz
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T04:50:44.170Z
Answers.Text: @DavidSchwartz: Designing a good program to play any perfect-information abstract game is not logically forced. It is true that against a perfect player resignation of a lost position is no different from playing to the end. However, a good program will not resign until it evaluates that the opponent is likely to win. Common chess programs are like that, as was AlphaGo. From a losing position, one can choose the next move based on many factors, such as the number of moves the opponent needs to guarantee a win, or the fraction of opponent responses that are imperfect.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T09:38:53.347Z
Answers.Text: @Francesco I didn't exclude it, I just used less-than-ideal phrasing. I counted "lost for white" as "won for black", even though white is to move :)
Answers.UserDisplayName: hobbs
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T20:40:31.723Z
Answers.LastActivityDate: 2017-12-19T21:05:14.567Z
Answers.LastEditDate: 2017-12-19T21:05:14.567Z
Answers.UserDisplayName: David Schwartz
Answers.Body: <p>Suppose you have three functions: <code>win_state</code> , <code>get_player</code>, and <code>next_states</code>. The input for <code>win_state</code> is a game state, and the output is -1 if white is in checkmate, 0 if it’s a draw, 1 if black is in checkmate, and <code>None</code> otherwise. The input for <code>get_player</code> is a game state, and the output is -1 if it’s black’s turn and 1 if it’s white’s turn. The input for <code>next_states</code> is a list of possible next game states that can result from a legal move. Then the following function, when given a game state and a player, should tell you what game state to move to for that player to win.</p>
  
  <pre><code>def best_state(game_state,player)
    def best_result(game_state):
       if win_state(game_state):
          return(win_state)
       else:
           player = get_player(game_state)
           return max([best_result(move)*player for move in next_states(game_state)])*player
    cur_best_move = next_states(games_state)[0]
    cur_best_outcome = -1
    for state in next_states(game_state):
       if best_result(state)*player &gt; cur_best_outcome:
             cur_best_outcome = best_result(state)*player
             cur_best_move = state
  return(best_move)
  </code></pre>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T21:07:56.437Z
Answers.LastActivityDate: 2017-12-20T21:07:56.437Z
Answers.UserDisplayName: Acccumulation
Answers.Body: <h2>Use a look-up table</h2>
  
  <p>Yes. It's easy. You don't even need infinite processing power. All you need is a look-up table that contains, for each possible board position, the best move to play in that position. Here is the pseudo-code:</p>
  
  <pre><code>def play-move(my-color, board-position):
      return table-of-best-moves[my-color, board-position]
  </code></pre>
  
  <h2>The catch</h2>
  
  <p>The only catch is that this look-up table would have to be very, very large—perhaps larger than the Milky Way galaxy—and it would take a long time to construct it—perhaps longer than the current age of the universe, unless there's some undiscovered regularity in chess that makes it much simpler than we can see right now. But if you had this look-up table, the subroutine to choose a perfect move every time could be implemented in as little as one CPU instruction.</p>
  
  <p>Also, given our current knowledge of chess, there's no way to be sure that perfect play guarantees that you won't lose. For example, if perfect play guarantees a win for White, then Black would lose even if Black plays perfectly.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-22T14:19:44.403Z
Answers.LastActivityDate: 2017-12-22T14:19:44.403Z
Answers.UserDisplayName: Ben Kovitz
Answers.Body: <p>Does an algorithm exist?  Yes.  According to <a href="https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)" rel="noreferrer">Zermelo's Theorem</a>, there are three possibilities for a finite deterministic perfect-information two-player game such as chess: either the first player has a winning strategy, or the second player has a winning strategy, or either player can force a draw.  We don't (yet) know which it is for chess.  (Checkers, on the other hand, <a href="http://science.sciencemag.org/content/317/5844/1518?ijkey=jVmVcXy2%2FNTnY&amp;keytype=ref&amp;siteid=sci" rel="noreferrer">has been solved</a>: either player can force a draw.)</p>
  <p>Conceptually, the algorithm is quite simple: construct a <a href="https://en.wikipedia.org/wiki/Game_tree" rel="noreferrer">complete game tree</a>, analyze the leaf nodes (the game-ending positions), and either make the winning initial move, resign (if the opponent has a forced win), or offer a draw (if the position is a draw).</p>
  <p>The problem lies in the details: there are approximately 10<sup>43</sup> possible positions, and an even larger number of moves (most positions can be reached in more than one way).  You really need your infinitely-powerful computer to take advantage of this, since a computer that can take advantage of this algorithm either can't fit in the known universe, or won't finish computation until sometime after the universe ends.</p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T22:52:45.773Z
Answers.Text: That would be a stupid algorithm, actually.  It assumes that the *other* player is a perfect player also.  Even if the supercomputer is in a "losing position" assuming a perfect opponent, that doesn't mean it will in fact lose.
Answers.UserDisplayName: Wildcard
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T23:12:21.220Z
Answers.Text: @Wildcard No, it doesn't assume anything: it just contains *all* possibile legal games of chess and it will pick all those ones where the player at hand does not lose.
Answers.UserDisplayName: gented
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-19T23:19:02.540Z
Answers.Text: @gented, I was referring to the "resign" step of the algorithm.  That's not a necessary step at all.
Answers.UserDisplayName: Wildcard
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T04:25:23.423Z
Answers.Text: The 'perfect' computer would need to know which branches lead to 'resign' in order to avoid them
Answers.UserDisplayName: Black
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T09:25:01.367Z
Answers.Text: The three-repetition rule bounds the search space, so the computer does not have to be _infinitely_ powerful, merely astronomically powerful.
Answers.UserDisplayName: Hoa Long Tam
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T13:49:09.810Z
Answers.Text: For reference, compare a lower bound for the number of possible games ([10^120](https://en.wikipedia.org/wiki/Shannon_number)) to the number of atoms in the observable universe (on the order of [10^80](https://en.wikipedia.org/wiki/Observable_universe#Matter_content)). The simplest algorithm would have to find all those games and store their data. Storing one game per atom would take 10^40 times as many atoms as we estimate in the observable universe.
Answers.UserDisplayName: Engineer Toast
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T18:19:08.267Z
Answers.Text: @EngineerToast that's why we use iterative deepening breath first search instead of breadth first search when the state space gets big. Or in this case, a good old forgetful DFS. Then you don't need ridiculous amounts of memory, just ridiculous amounts of CPU power.
Answers.UserDisplayName: John Dvorak
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T18:47:42.497Z
Answers.Text: @JohnDvorak I am incredibly ignorant of search algorithms. Are you saying it's possible to solve chess with our current storage capacity if only we had enough time and / or processing speed?
Answers.UserDisplayName: Engineer Toast
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-20T19:16:45.940Z
Answers.Text: @EngineerToast Of course it is! Just google depth-first search! For it the storage capacity needed will be approximately number_of_moves_at_any_point * longest_game_possible (excluding cycles). The longest possible game (with our present draw rule) is just shy of 6,000 moves, well within storage capacity. The problem is that this only produces an end result + next best move, not an entire strategy, and it cannot reuse already looked at positions (excluding cycles), so will end up searching through some games multiple times. But who cares - it's finite time.
Answers.UserDisplayName: Ordous
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T00:30:49.723Z
Answers.Text: An infinitely powerful computer would be infinitely more powerful than the one we need to solve chess.  Assuming we do some basic caching and merging of vertices on the game tree, a mere 10^45 Hz processor with a decent amount of RAM (10^45 bytes or so) could solve chess in just a few seconds.
Answers.UserDisplayName: Ray
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T09:15:20.127Z
Answers.Text: @EngineerToast: yes, but when the heat death of the universe happens we won't have made visible progress yet.
Answers.UserDisplayName: RemcoGerlich
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T17:24:08.443Z
Answers.Text: 8x8 checkers has been solved, 10x10 not yet as far as I know.
Answers.UserDisplayName: user1803551
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-21T22:52:48.620Z
Answers.Text: This answer is great until the very end when you refer to an "infinitely powerful computer".  That's *not* what you mean, and that phrase doesn't belong in the question nor the discussion.
Answers.UserDisplayName: Don Hatch
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-22T13:25:00.430Z
Answers.Text: Brute forcing is just ONE possibility. And it is maybe useless since it is not known whether there is a game strategy that allows you to win 100% of times. With infinite power you can apply other strategies; for instance you can hack the nuclear weapons controlling computers, launch one of them and then tell the other player "resign or I'll have it land on your house". Maybe hacking the PCs is a bit more hard on a computational way, but given infinite power the two algorithms will take the same time to execute...
Answers.UserDisplayName: frarugi87
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-22T15:56:14.723Z
Answers.Text: @HoaLongTam The three-repetition rule is not needed to limit the search space - as any forced win with the rule can be played without repetition. If a player can force a repetition they could do it not only 3 times but 25 times and thus it would be a draw due to the 50-move rule.
Answers.UserDisplayName: Hans Olsson
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-22T17:26:03.783Z
Answers.Text: Does the situation improve with quantum computers?
Answers.UserDisplayName: user1997744
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T04:40:39.240Z
Answers.Text: @Black: Wildcard is simply correct. If you have ever programmed a computer chess player before, you would understand what he is saying.
Answers.UserDisplayName: user21820
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T05:08:45.470Z
Answers.Text: @EngineerToast But what about subatomic particles like quarks and electrons? =)
Answers.UserDisplayName: jpmc26
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-23T05:12:34.480Z
Answers.Text: @frarugi87 A brute force algorithm can tell you which category of games chess falls into. If one player can force a win, then the brute force algorithm will discover this. If the game can be forced into a draw, the brute force algorithm will find this. And it can additionally do so with any starting position of the board; it merely needs to trace down to all the leaves. There is no way in which it would not be useful.
Answers.UserDisplayName: jpmc26
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-25T16:44:08.800Z
Answers.Text: The finiteness of the board also bounds the search space. Even if you didn't have the three repetition rule or the 50 moves rule, you would know if you found the same position again that the game must continue in the same way from there, so there is no need for further searching of the tree.
Answers.UserDisplayName: N. Virgo
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-25T20:53:12.050Z
Answers.Text: @Nathaniel: From a bare computability perspective, that is true. However, if we (like some of the above commenters) are interested in trading time for space, then the 50-move rule seems to be vital for keeping the recursion depth you might need to deal with small.
Answers.UserDisplayName: hmakholm left over Monica
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-26T02:40:45.060Z
Answers.Text: @HenningMakholm I'm not sure if that's correct or not. Without the 50 move rule and three repetition rule you can immediately stop searching if you re-encounter the same board position, but with those rules in place you can't, because it's actually a different game state (the move counter is different). So it makes the search tree bigger in some ways, as well as smaller in others, and I'm not sure which wins out. In any case, "small" in this context is still large compared to the physical universe, so if you really want to cut it down to a manageable size you'd need a lot more clever tricks.
Answers.UserDisplayName: N. Virgo
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-26T14:24:21.973Z
Answers.Text: @Nathaniel: Actually you can stop searching when the 50-move rule applies, because two perfect players cannot _both_ prefer to continue the game (assuming they have a weak preference of an explicit draw over an infinite game). The only situation where we may need to continue searching from a position where the rule applies is if the _first_ player to have the option can _immediately_ move a pawn or capture a piece (in which case it is still possible that he may force a win). So there will be progress.
Answers.UserDisplayName: hmakholm left over Monica
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-12-26T14:31:17.783Z
Answers.Text: And "small" in this case is, according to Ordous above, about 6000 moves, which is quite manageable. Recall that here we're talking about the _depth_ of the tree (which is what governs the _space_ requirements of DFS), not the total number of nodes.
Answers.UserDisplayName: hmakholm left over Monica
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-08-01T01:37:41.167Z
Answers.Text: How robust to errors is such notion of solving?
Answers.UserDisplayName: dbdb
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2017-12-19T22:26:06.450Z
Answers.LastActivityDate: 2020-08-25T20:24:08.940Z
Answers.LastEditDate: 2020-08-25T20:24:08.940Z
Answers.UserDisplayName: Mark
Body: <p>Does there exist such an algorithm where, if given infinite processing power, a computer could play chess perfectly, i.e., it can generate perfect moves from any position?</p>
  <p>If so, where can I find the pseudo-code for it?</p>
  
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T19:53:53.333Z
Comments.Text: What do you mean by perfect chess?
Comments.UserDisplayName: Herb
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T20:36:28.890Z
Comments.Text: @HerbWolfe I assume he means that it never makes a move that permits its opponent to force it to lose and resigns if, and only if, every possible move permits its opponent to force it to lose.
Comments.UserDisplayName: David Schwartz
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T20:58:32.857Z
Comments.Text: Negamax/minimax don't make mistakes but they're not optimal at provoking mistakes in weaker opponents.
Comments.UserDisplayName: CodesInChaos
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T23:09:19.070Z
Comments.Text: @CodesInChaos Notice that minimax are always cut down to certain depths, therefore they don't really see the *whole* game.
Comments.UserDisplayName: gented
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T23:27:56.680Z
Comments.Text: @DavidSchwartz - "perfect chess", of course, can't be defined. Neither can "infinite processing power". Does this mean "executes all instruction sequences in 0 time"? "Has an infinite number of processors available"? FWIW - my definition of "perfect chess" is "never loses a game".
Comments.UserDisplayName: Bob Jarvis - Слава Україні
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T23:28:28.800Z
Comments.Text: @BobJarvis Then what happens if two such algorithms play each other?
Comments.UserDisplayName: David Schwartz
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T23:29:40.723Z
Comments.Text: @DavidSchwartz: they take infinite time to achieve a draw. :-)
Comments.UserDisplayName: Bob Jarvis - Слава Україні
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-19T23:45:36.403Z
Comments.Text: Yes, it's called brute force.  With infinite processing power you don't need to do alpha-beta pruning, although you may also need a rather large amount of storage to hold your search tree.
Comments.UserDisplayName: Michael
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-20T09:01:04.793Z
Comments.Text: If something takes infinite time (never ends), it is by definition not an algorithm. The question should say "arbitrary" processing power.
Comments.UserDisplayName: RemcoGerlich
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-20T11:07:18.263Z
Comments.Text: If you have infinite processing power you don't need a particular algorithm, you can simply calculate every possible position
Comments.UserDisplayName: Darren H
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-20T23:48:00.777Z
Comments.Text: The concept of an "algorithm" and the concept of infinite processing power don't really mix. The theory of algorithms and of computability is all based on an assumption of achieving a result in a finite number of steps. If you're allowed an infinite number of steps, the distinction between what is computable and what isn't disappears.
Comments.UserDisplayName: Michael Kay
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T08:14:29.977Z
Comments.Text: Please don't use term "infinite power" (infinite means so many different things), for chess you only need a finite but very very long time. So long, that it is actually not usable.
Comments.UserDisplayName: Jean-Baptiste Yunès
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T20:53:30.670Z
Comments.Text: @BobJarvis actually infinite processing power is well emdefined. We just don't have the abilities to implement it. See this article on wikipedia: https://en.m.wikipedia.org/wiki/Hypercomputation
Comments.UserDisplayName: user64742
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T20:54:53.703Z
Comments.Text: @MichaelKay actually there are hypercomputation algorithms in existence. However it is a pretty stale thing to read about as nobody can implement them yet.
Comments.UserDisplayName: user64742
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-21T20:57:43.417Z
Comments.Text: @DavidSchwartz depends on whether or not a player in chess can force a win.
Comments.UserDisplayName: user64742
Comments.ContentLicense: CC BY-SA 3.0
Comments.CreationDate: 2017-12-25T02:04:04.077Z
Comments.Text: The answer is yes for any game where all players have perfect information (which Chess is). In fact, most answers can be applied to any game in this category.
Comments.UserDisplayName: Jasper
Tags: <chess-algorithms>
Title: If given infinite processing power, is there an algorithm that would play chess perfectly?
ThreadText: # If given infinite processing power, is there an algorithm that would play chess perfectly?
  
  (Asked by: username_0 on 2017-12-19)
  
  Does there exist such an algorithm where, if given infinite processing power, a computer could play chess perfectly, i.e., it can generate perfect moves from any position?
  
  If so, where can I find the pseudo-code for it?
  
  **Tags:** chess-algorithms
  
  > **Comments:**
  > **username_1**: What do you mean by perfect chess?  
  > **username_2**: @HerbWolfe I assume he means that it never makes a move that permits its opponent to force it to lose and resigns if, and only if, every possible move permits its opponent to force it to lose.  
  > **username_3**: Negamax/minimax don't make mistakes but they're not optimal at provoking mistakes in weaker opponents.  
  > **username_4**: @username_3 Notice that minimax are always cut down to certain depths, therefore they don't really see the *whole* game.  
  > **username_5**: @username_2 - "perfect chess", of course, can't be defined. Neither can "infinite processing power". Does this mean "executes all instruction sequences in 0 time"? "Has an infinite number of processors available"? FWIW - my definition of "perfect chess" is "never loses a game".  
  > **username_2**: @BobJarvis Then what happens if two such algorithms play each other?  
  > **username_5**: @username_2: they take infinite time to achieve a draw. :-)  
  > **username_6**: Yes, it's called brute force.  With infinite processing power you don't need to do alpha-beta pruning, although you may also need a rather large amount of storage to hold your search tree.  
  > **username_7**: If something takes infinite time (never ends), it is by definition not an algorithm. The question should say "arbitrary" processing power.  
  > **username_8**: If you have infinite processing power you don't need a particular algorithm, you can simply calculate every possible position  
  > **username_9**: The concept of an "algorithm" and the concept of infinite processing power don't really mix. The theory of algorithms and of computability is all based on an assumption of achieving a result in a finite number of steps. If you're allowed an infinite number of steps, the distinction between what is computable and what isn't disappears.  
  > **username_10**: Please don't use term "infinite power" (infinite means so many different things), for chess you only need a finite but very very long time. So long, that it is actually not usable.  
  > **username_11**: @BobJarvis actually infinite processing power is well emdefined. We just don't have the abilities to implement it. See this article on wikipedia: https://en.m.wikipedia.org/wiki/Hypercomputation  
  > **username_11**: @username_9 actually there are hypercomputation algorithms in existence. However it is a pretty stale thing to read about as nobody can implement them yet.  
  > **username_11**: @username_2 depends on whether or not a player in chess can force a win.  
  > **username_12**: The answer is yes for any game where all players have perfect information (which Chess is). In fact, most answers can be applied to any game in this category.  
  
  ---
  
  ## 8 answers
  
  ### Answer by username_24 on 2017-12-19. Score: 70 | Accepted answer
  
  Does an algorithm exist? Yes. According to [Zermelo's Theorem](https://en.wikipedia.org/wiki/Zermelo%27s_theorem_(game_theory)), there are three possibilities for a finite deterministic perfect-information two-player game such as chess: either the first player has a winning strategy, or the second player has a winning strategy, or either player can force a draw. We don't (yet) know which it is for chess. (Checkers, on the other hand, [has been solved](http://science.sciencemag.org/content/317/5844/1518?ijkey=jVmVcXy2%2FNTnY&keytype=ref&siteid=sci): either player can force a draw.)
  
  Conceptually, the algorithm is quite simple: construct a [complete game tree](https://en.wikipedia.org/wiki/Game_tree), analyze the leaf nodes (the game-ending positions), and either make the winning initial move, resign (if the opponent has a forced win), or offer a draw (if the position is a draw).
  
  The problem lies in the details: there are approximately 1043 possible positions, and an even larger number of moves (most positions can be reached in more than one way). You really need your infinitely-powerful computer to take advantage of this, since a computer that can take advantage of this algorithm either can't fit in the known universe, or won't finish computation until sometime after the universe ends.
  
  > **Comments:**
  > **username_32**: That would be a stupid algorithm, actually.  It assumes that the *other* player is a perfect player also.  Even if the supercomputer is in a "losing position" assuming a perfect opponent, that doesn't mean it will in fact lose.  
  > **username_4**: @username_32 No, it doesn't assume anything: it just contains *all* possibile legal games of chess and it will pick all those ones where the player at hand does not lose.  
  > **username_32**: @username_4, I was referring to the "resign" step of the algorithm.  That's not a necessary step at all.  
  > **username_33**: The 'perfect' computer would need to know which branches lead to 'resign' in order to avoid them  
  > **username_34**: The three-repetition rule bounds the search space, so the computer does not have to be _infinitely_ powerful, merely astronomically powerful.  
  > **username_35**: For reference, compare a lower bound for the number of possible games ([10^120](https://en.wikipedia.org/wiki/Shannon_number)) to the number of atoms in the observable universe (on the order of [10^80](https://en.wikipedia.org/wiki/Observable_universe#Matter_content)). The simplest algorithm would have to find all those games and store their data. Storing one game per atom would take 10^40 times as many atoms as we estimate in the observable universe.  
  > **username_36**: @username_35 that's why we use iterative deepening breath first search instead of breadth first search when the state space gets big. Or in this case, a good old forgetful DFS. Then you don't need ridiculous amounts of memory, just ridiculous amounts of CPU power.  
  > **username_35**: @username_36 I am incredibly ignorant of search algorithms. Are you saying it's possible to solve chess with our current storage capacity if only we had enough time and / or processing speed?  
  > **username_37**: @username_35 Of course it is! Just google depth-first search! For it the storage capacity needed will be approximately number_of_moves_at_any_point * longest_game_possible (excluding cycles). The longest possible game (with our present draw rule) is just shy of 6,000 moves, well within storage capacity. The problem is that this only produces an end result + next best move, not an entire strategy, and it cannot reuse already looked at positions (excluding cycles), so will end up searching through some games multiple times. But who cares - it's finite time.  
  > **username_38**: An infinitely powerful computer would be infinitely more powerful than the one we need to solve chess.  Assuming we do some basic caching and merging of vertices on the game tree, a mere 10^45 Hz processor with a decent amount of RAM (10^45 bytes or so) could solve chess in just a few seconds.  
  > **username_7**: @username_35: yes, but when the heat death of the universe happens we won't have made visible progress yet.  
  > **username_39**: 8x8 checkers has been solved, 10x10 not yet as far as I know.  
  > **username_40**: This answer is great until the very end when you refer to an "infinitely powerful computer".  That's *not* what you mean, and that phrase doesn't belong in the question nor the discussion.  
  > **username_41**: Brute forcing is just ONE possibility. And it is maybe useless since it is not known whether there is a game strategy that allows you to win 100% of times. With infinite power you can apply other strategies; for instance you can hack the username_25 weapons controlling computers, launch one of them and then tell the other player "resign or I'll have it land on your house". Maybe hacking the PCs is a bit more hard on a computational way, but given infinite power the two algorithms will take the same time to execute...  
  > **username_42**: @username_34 The three-repetition rule is not needed to limit the search space - as any forced win with the rule can be played without repetition. If a player can force a repetition they could do it not only 3 times but 25 times and thus it would be a draw due to the 50-move rule.  
  > **username_43**: Does the situation improve with quantum computers?  
  > **username_29**: @username_33: username_32 is simply correct. If you have ever programmed a computer chess player before, you would understand what he is saying.  
  > **username_44**: @username_35 But what about subatomic particles like quarks and electrons? =)  
  > **username_44**: @username_41 A brute force algorithm can tell you which category of games chess falls into. If one player can force a win, then the brute force algorithm will discover this. If the game can be forced into a draw, the brute force algorithm will find this. And it can additionally do so with any starting position of the board; it merely needs to trace down to all the leaves. There is no way in which it would not be useful.  
  > **username_45**: The finiteness of the board also bounds the search space. Even if you didn't have the three repetition rule or the 50 moves rule, you would know if you found the same position again that the game must continue in the same way from there, so there is no need for further searching of the tree.  
  > **username_46**: @Nathaniel: From a bare computability perspective, that is true. However, if we (like some of the above commenters) are interested in trading time for space, then the 50-move rule seems to be vital for keeping the recursion depth you might need to deal with small.  
  > **username_45**: @HenningMakholm I'm not sure if that's correct or not. Without the 50 move rule and three repetition rule you can immediately stop searching if you re-encounter the same board position, but with those rules in place you can't, because it's actually a different game state (the move counter is different). So it makes the search tree bigger in some ways, as well as smaller in others, and I'm not sure which wins out. In any case, "small" in this context is still large compared to the physical universe, so if you really want to cut it down to a manageable size you'd need a lot more clever tricks.  
  > **username_46**: @Nathaniel: Actually you can stop searching when the 50-move rule applies, because two perfect players cannot _both_ prefer to continue the game (assuming they have a weak preference of an explicit draw over an infinite game). The only situation where we may need to continue searching from a position where the rule applies is if the _first_ player to have the option can _immediately_ move a pawn or capture a piece (in which case it is still possible that he may force a win). So there will be progress.  
  > **username_46**: And "small" in this case is, according to username_37 above, about 6000 moves, which is quite manageable. Recall that here we're talking about the _depth_ of the tree (which is what governs the _space_ requirements of DFS), not the total number of nodes.  
  > **username_22**: How robust to errors is such notion of solving?  
  
  ---
  
  ### Answer by username_13 on 2017-12-19. Score: 27
  
  See <https://en.wikipedia.org/wiki/Endgame_tablebase>.
  
  With infinite computer power, one could build such a table for the starting position and [solve chess](https://en.wikipedia.org/wiki/Solving_chess "solve chess").
  
  In practice, only positions with up to seven "men" (pawns and pieces, counting the kings) have been solved using current supercomputers, so we are very far from solving chess. The complexity of the problem increases exponentially with the increase in the number of pieces.
  
  > **Comments:**
  > **username_14**: As a side note, if you actually produced such a table, no matter what you stored the information on, it would weigh roughly 10^43 times as much as the observable universe; considering there are ~10^123 possible chess positions and only ~10^80 baryons in the observable universe.  
  > **username_15**: Can this answer be summarized as "retrograde analysis is an algorithm that would solve chess if given an infinitely powerful computer"?  
  > **username_6**: @username_14 who said i was storing it using baryons?  
  > **username_13**: @username_15, yes, pretty much. Isn't it amazing what one can do when resources are infinite? The universe being finite is just a technicality. :-)  
  > **username_16**: @username_14 FWIW If I calculated correctly then you could store it in a username_33 hole with a radius in the range of 10^24 - 10^25 km. That's only a few times the size of the observable universe...  
  > **username_14**: @username_16 And assuming conservation of information, and assuming you had a detector and your super computer with infinite processing power, you could slowly over the course of something like a googolplex years read out the tablebase as hawking radiation.  
  > **username_17**: @username_14 Note that an actual winning strategy might require much less space than a full tablebase. For instance, Nim has a winning strategy that is simple to describe, there is no need to build a huge table of all possible states.  
  > **username_18**: This solution as stated is not viable.  The mass of such a table would form a username_33 hole and it would be impossible to exfiltrate data from it.  
  
  ---
  
  ### Answer by username_19 on 2017-12-20. Score: 20
  
  If you really had *infinite* processing power, such an algorithm would be actually **trivial** to write. As chess has a [finite](https://www.webcitation.org/5oFLE7Mgx?url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf) number of possible states, you could in theory just iterate through them all until you find a path of perfect play. It would be horribly inefficient, but if you have *infinite* processing power, it wouldn't matter.
  
  > **Comments:**
  > **username_20**: That's not true. He said you have infinite processing power, but not did not say anything about infinite space.  
  > **username_19**: @username_20 : We wouldn't need infinite space. The length of a game is limited due to the 50-move rule, and a rule can be made up to sort all possible moves from a position. As they can be sorted, they can be stored as an integer. This is all the memory required to walk the whole tree. And if you have infinite time, you can walk the tree as often as you want, so you don't have to store every possible chess game.  
  > **username_20**: The length of the game is limited, but it is extremely large; as someone else pointed out, if you produced a table to store all such games, "no matter what you stored the information on, it would weigh roughly 10^43 times as much as the observable universe; considering there are ~10^123 possible chess positions and only ~10^80 baryons in the observable universe  
  > **username_19**: @username_20 : That is true, but I was not talking about "a table to store all such games". There are many tree-related algorithms which don't have to hold all the nodes of the whole tree in memory.  
  > **username_20**: @ vsz good point  
  
  ---
  
  ### Answer by username_21 on 2017-12-20. Score: 13
  
  To directly address the question: yes there is such an algorithm. It is called minimax. (The endgame tablebases are generated by using this algorithm (backwards!), but the plain old simple minimax algorithm is all you need). This algorithm can play any two player zero sum game perfectly. Find pseudocode here:
  
  <https://en.wikipedia.org/wiki/Minimax>
  
  note that variants of this algorithm are used by modern computer chess programs.
  
  This algorithm basically generates the move which will minimize the opponent's chances, i.e., it would choose a move for White that is +2 instead of +1. Then, it generates the opponent's move which will maximize his chances, i.e., it would choose a move for username_33 that is -2 instead of -1.
  
  > **Comments:**
  > **username_22**: I understand the minimax with an evaluation that can be ordered for a given partial tree with many leaves.  But I get lost even with a 2 outcome class big enough branching degree tree.    I should be able to scale down the minimax to having the trivial ordering of win and lose..  Say.  just binary tree even. 2 paths at each node to chose, even without any transposition, how is one comparing compounded min max operations backward when there is no addition defined. Are my simplificatoin assumptions having consequences that distort the reasoning.  What would the minial tree to show my flaw be.  
  > **username_22**: by addition I may have assumed the tree to have enough outcome diversity so that I could pick.  I guess the one just have to pick the exiting win if there . or the next best of the outcomes.  Having fine grain outcome forcasters to perdict those might be my real problem.  But being able to back track from an win leaf should be possible. it existend and the branch leading there would be the one side win choices, and if there existed a branch out of the opponent choices, that was not win, then.  what.  I guess not good at this.  
  > **username_22**: Should I make this a min max confusion question?  Please find my reasoning flaw, or missing chunk from the premises I did not apply yet?  
  
  ---
  
  ### Answer by username_23 on 2017-12-21. Score: 6
  
  Not only is there an algorithm to play perfect chess, it is possible to write a short program that will (given infinite resources) play *any deterministic perfect-knowledge finite-duration two-player game* perfectly.
  
  The game engine does not even need to know the rules of the game it is playing. All it needs is an opaque representation of a "game state" and functions that (a) given any game state, provide a list of legal next game states and (b) given a game state, decide if it is a win for player 1, a win for player 2, a draw, or it is not an end state.
  
  Given those functions a simple recursive algorithm "solves" the game.
  
  This fact has been alluded to in previous answers by username_21 (minimax) and by username_30 (who provides a version of the program in python).
  
  I wrote such a program over 20 years ago. I tested it by playing noughts-and-crosses (tic-tac-toe if you are American). Sure enough it played a perfect game.
  
  Of course this will fall over quickly on any imaginable computer for any serious game. Because it is recursive it is effectively building the entire game tree on the stack, so you will get a "stack overflow" (pun very much intended) before you get anywhere near analysing the 10^123 states of chess referred to in other answers. But it is fun to know that in principle this small program would do the job.
  
  For me this also says something interesting about AI: however much "intelligence" you think is exhibited by Deep Blue, or Go Zero, or indeed by a human playing Chess or Go there is a sense in which these games have trivial, exactly computable optimal solutions. The challenge is how to get a good though not optimal solution in a reasonable time.
  
  > **Comments:**
  > **username_24**: Your algorithm only works for perfect-knowledge two-player games.  It will fall over for hidden-information games such as [Stratego](https://en.wikipedia.org/wiki/Stratego), because any implementation of function (a) violates the game rules.  It also fails for games of potentially infinite duration: for example, drop the 50-move rule from chess, and it can't tell that two kings chasing each other around the board isn't a winnable state.  All it can tell is that it's not an end state.  
  > **username_23**: Valid points. I will edit my answer.  
  
  ---
  
  ### Answer by username_2 on 2017-12-19. Score: 3
  
  I will ignore the possibilities of draws or infinite sequences of moves for simplicity. Once the algorithm is understood, it is not particularly difficult to extend it to those cases.
  
  First, some definitions:
  
  1. Any move that wins the game for the player who makes that move is a winning move.
  2. Any move that loses the game for the player who makes that move is a losing move.
  3. Any move that leaves the other player with at least one winning move is also a losing move. (Since the opponent can take that move and force a loss.)
  4. Any move that leaves the other player with only losing moves is also a winning move. (No matter what move your opponent makes, you will win.)
  5. A perfect strategy means always making winning moves if any remain and resigning when one has only losing moves remaining.
  
  Now, it's trivial to write a perfect strategy. Simply explode all possible move sequences and identify winning/losing moves. Ignoring stalemate, this will eventually identify every move as either a winning move or a losing move.
  
  Now, the strategy is trivial. Look at all your possible moves. If any winning moves remain, take one and win. If only losing moves remain, resign, since your opponent can force you to lose.
  
  It is not difficult to adjust the strategy to include the possibility of a stalemate.
  
  **Update**: Just in case it's not clear how this identifies every move as a winning more or a losing move, consider:
  
  1. Every move that results in a win is a winning move.
  2. Every move that results in a loss is a losing move.
  3. Every move that results in the opponent having only winning or losing moves is either a winning or a losing move.
  4. Call `n` the number of moves in the longest possible chess game. (We are ignoring unbounded sequences for now, though including them is not difficult.)
  5. There are no moves with `n` prior moves we need to consider.
  6. Every move with `n-1` prior moves is either a winning move or a losing move since `n` moves ends the longest game.
  7. Thus every move at depth `n-2` is followed by only winning moves or losing moves and thus is itself a winning move or losing move.
  8. And so on back to the first move.
  
  > **Comments:**
  > **username_25**: Your definitions of winning and losing moves are not comprehensive enough. The first move, for instance, neither wins the game (#1), nor leaves the opponent with only losing moves (#4), so it isn't a "winning move". Neither does it lose the game (#2), nor leave the opponent with any winning move (#3), so it isn't a "losing move". Your strategy requires that every move is defined either as a "winning move" or a "losing move", which simply isn't the case as you've defined it.  
  > **username_2**: @NuclearWang It does define every move as either a winning move or a losing move. What do you think the third alternative is? Visualize the tree of all possible chess games (and remember, we're excluding ties or infinite sequences for now). Every chain ends in either a win or a loss. This percolates up through the tree eventually identifying every move as either a winning move or a losing move.  
  > **username_26**: @NuclearWang either the first move *is* a winning move for one player, or else chess is (like tic-tac-toe) a drawn game with perfect play. We don't know which because no one has ever had the computing power to run this algorithm to completion, and no one has found a more direct proof.  
  > **username_26**: There is no randomness and no hidden information in chess, which leaves no room for "maybe". Every position is won, lost, or drawn (even if we haven't managed to *identify* them as such). And this explanation is leaving out the "drawn" option for simplicity, but it mostly amounts to 1) a position is drawn if it's drawn according to the rules, and 2) a position is drawn if it has no winning moves, but has at least one move that leaves the *opponent* with no winning moves.  
  > **username_27**: @username_26 the first move could (it's unlikely to say the least.... but still) be a "losing move" for white, how can you exclude that?  
  > **username_28**: In what sense would resigning ever be a better strategy than playing an arbitrary move?  Unless one knows that one's opponent is perfect and in good health, I see no reason to believe that picking a move at random would not yield some non-zero probability of winning (even if the opponent would have nothing but forced winning moves the opponent forfeit because of time or other considerations).  
  > **username_2**: @username_28 Sure, one can try to trick one's opponent into making a mistake, but there's a lack of perfection in that strategy. If you accept that sometimes you should make a move just in the hopes that it will cause your opponent to make a mistake or you might benefit from your opponent's quirks, then there is no such thing as perfect chess.  
  > **username_28**: @username_2: Unless someone is in a losing position, every move that isn't perfect is bad.  In a losing position, there would generally be no single "perfect" move [except in a forced-move situation] since any legal move could have some probability of being the only winning or drawing move in some conceivable (possibly highly contrived) circumstances.  Resigning, however, would seem the unambiguous worst "move".  Suppose the game is proven solved as a win for White with d4.  Would you want to play a chess program which responded to `1. d4` with `...resigns`?  
  > **username_2**: @username_28 And yet, it is the perfect move.  
  > **username_29**: @username_2: Designing a good program to play any perfect-information abstract game is not logically forced. It is true that against a perfect player resignation of a lost position is no different from playing to the end. However, a good program will not resign until it evaluates that the opponent is likely to win. Common chess programs are like that, as was AlphaGo. From a losing position, one can choose the next move based on many factors, such as the number of moves the opponent needs to guarantee a win, or the fraction of opponent responses that are imperfect.  
  > **username_26**: @username_27 I didn't exclude it, I just used less-than-ideal phrasing. I counted "lost for white" as "won for username_33", even though white is to move :)  
  
  ---
  
  ### Answer by username_30 on 2017-12-20. Score: 3
  
  Suppose you have three functions: `win_state` , `get_player`, and `next_states`. The input for `win_state` is a game state, and the output is -1 if white is in checkmate, 0 if it’s a draw, 1 if username_33 is in checkmate, and `None` otherwise. The input for `get_player` is a game state, and the output is -1 if it’s username_33’s turn and 1 if it’s white’s turn. The input for `next_states` is a list of possible next game states that can result from a legal move. Then the following function, when given a game state and a player, should tell you what game state to move to for that player to win.
  
  ```
  def best_state(game_state,player)
    def best_result(game_state):
       if win_state(game_state):
          return(win_state)
       else:
           player = get_player(game_state)
           return max([best_result(move)*player for move in next_states(game_state)])*player
    cur_best_move = next_states(games_state)[0]
    cur_best_outcome = -1
    for state in next_states(game_state):
       if best_result(state)*player > cur_best_outcome:
             cur_best_outcome = best_result(state)*player
             cur_best_move = state
  return(best_move)
  
  ```
  
  
  ---
  
  ### Answer by username_31 on 2017-12-22. Score: 1
  
  ## Use a look-up table
  
  Yes. It's easy. You don't even need infinite processing power. All you need is a look-up table that contains, for each possible board position, the best move to play in that position. Here is the pseudo-code:
  
  ```
  def play-move(my-color, board-position):
      return table-of-best-moves[my-color, board-position]
  
  ```
  
  ## The catch
  
  The only catch is that this look-up table would have to be very, very large—perhaps larger than the Milky Way galaxy—and it would take a long time to construct it—perhaps longer than the current age of the universe, unless there's some undiscovered regularity in chess that makes it much simpler than we can see right now. But if you had this look-up table, the subroutine to choose a perfect move every time could be implemented in as little as one CPU instruction.
  
  Also, given our current knowledge of chess, there's no way to be sure that perfect play guarantees that you won't lose. For example, if perfect play guarantees a win for White, then username_33 would lose even if username_33 plays perfectly.
  
  
  ---
  
  