Answers.Body: <p>The answer is yes, and is usually attributed to Zermelo.</p>
  <p>Imagine a (finite, albeit impractically large) list of all possible
  chess positions.</p>
  <p>In some of the BTM (Black To Move) positions, Black is mated.  Mark those.</p>
  <p>All the WTM positions that can reach one of these positions are mates in 1.
  Mark those.</p>
  <p>In a BTM position, Black is mated in 1 if and only if
  Black is not already mated but every legal move is to
  a position on the Mate in 1 list.  Mark those.</p>
  <p>A WTM that's not already on the Mate in 1 list is Mate in 2
  if and only if White can move to a position where Black is mated in 1.
  Mark those.</p>
  <p>In a BTM position, Black is mated in 2 if nad only if
  Black is not already mated, nor mated in 1, but every legal move is to
  a position on the Mate in 1 or Mate in 2 list.  Mark those.</p>
  <p>A WTM that's not already on the Mate in 1 list and Mate in 2 lists
  is Mate in 3 if and only if White can move to a position where
  Black is mated in 2.  Mark those.</p>
  <p>Keep going.  At some point you'll not be able to mark any new positions.
  At that point, you have all the positions where White wins by force,
  and an optimal move from each one
  (where White wants to mate as fast as possible
  and Black wants to delay mate as long as possible).</p>
  <p>Do the same thing with colors reversed to find all the forced Black wins
  and an optimal move from each such position.</p>
  <p>The remaining positions are all draws; either player in a drawn position
  has at least one move to another drawn position (else either that player
  or their opponent has a forced win).</p>
  <p>This analysis ignores the rules of triple repetition and 50 moves,
  but it's easy enough (in principle, which is all we're claiming)
  to incorporate them.  For example, each position can come with a
  50-move counter; this still makes for a finite (albeit even more
  impractically large) list of possible positions.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T11:07:31.047Z
Answers.Text: Ok, far be it for me to argue with the joint creator of ZFC, but my response to this is in the answers I predicted in the body of my post expressing why I doubt chess is deterministic. I start that paragraph with "Another way to look at the same problem is...". There my reasoning is even tracing back from the end, in the manner you describe, you won't end up at the start of the game, you will hit a barrier when you eventually find a move (taking your example this time) where the opposing player has a choice whereby they can avoid being pushed into the endgame you started working back from.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T13:42:55.903Z
Answers.Text: @GeorginaDavenport in that case the starting position is a draw (as most players expect); by consulting the completed table, both players can then play forever -- or until some draw agreement or rule kicks in -- each time moving from one drawn position to another.  In principle it's no different from perfect play with K+R vs. K+R.
Answers.UserDisplayName: Noam D. Elkies
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:23:40.807Z
Answers.Text: I don't know if I agree. In that case you are assuming the oracle will only play other oracles. Maybe it will. I also agree (by assumption) that chess is like tic-tac-toe and Connect4 in that when two ideal players are pitted against each other the game always ends in a draw. The thing is though, that isn't the thing I'm trying to examine. Even with Connect 4 and tic-tac-toe being that way, this does not cause an obstruction to creating an ideal player and it does not create an obstacle in deciding what happens when you try to create an ideal player by systematisation (continued)
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:27:29.863Z
Answers.Text: First of all then, a perfect chess computer will not draw games when playing against most human players, it will win. We know for a fact that nobody has thought "it's always a draw" and stopped making chess engines and it has never been proven the game does always draw. That's only what we get with current chess engines which are not perfect chess players. Alpha Zero against StockFish doesn't draw, it wins, so we know there is still headspace for making a better chess engine even than StockFish and we know the quest continues (continued)
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:29:26.693Z
Answers.Text: Meanwhile, we are veering off track. This question is about determinism. My contention is that chess is deterministic only as long as every position is decidable. My contention is also that we already have examples of undecidable chess positions. For that reason chess is not deterministic. Should a finite state automaton be made which plays chess for that automaton to have a complete map of every possible chess game it would need to be a non-deterministic finite state automaton. For that reason I say chess is not deterministic.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T03:44:44.597Z
Answers.LastActivityDate: 2024-05-07T03:44:44.597Z
Answers.UserDisplayName: Noam D. Elkies
Answers.Body: <blockquote>
  <p>So, I say for it to be determined whether or not chess is fully deterministic it must first be established whether or not there exists some legal position, which can be arrived at by perfect play, on a path of thus-far known optimal decisions, from which there is an equal choice between best moves such that no process can possibly chose a single best move.</p>
  <p>What this comes down to is for chess to be proven deterministic it must first be proven that for every step on an optimal path the next move must always be decidable. For all we know about chess strategy now, this might not be true. There may be positions from which the next best move is undecidable, even by an oracle or God, such as with Buridan's ass wherein no choice is better than at least one other. If this latter case proves to be true then chess is not deterministic.</p>
  </blockquote>
  <p>This feels like the core of your question. Such positions are very frequent in games. To borrow from <a href="https://chess.stackexchange.com/questions/4638/is-there-a-single-best-move-in-every-position?noredirect=1&amp;lq=1">Is there a single best move in every position?</a>, here's a position with 5 such moves.</p>
  <pre><code>[FEN &quot;k7/6Q1/1K7/8/8/8/8/8 w - - 0 1&quot;]
  </code></pre>
  <p>As a matter of fact, most non tactical line positions usually have multiple moves that lead to the same best outcome with perfect play.</p>
  <p>This seems to meet your criteria. That said, I don't believe this makes chess nondeterministic as a deterministic process can still be used when multiple equal moves exist without using randomness. One example would be sorting moves alphanumerically and picking the first one.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T11:16:30.667Z
Answers.Text: Yes, it does meet the criteria which is why I link to that same position in my post which appears to me to prove my point.
  
  In my question I also pre-empt your response in the paragraph which begins with the words "If we try to change the picture and state...". In that paragraph I express why i believe that such a method as you propose leads directly to suboptimal strategy because the self-same undecidable choices (and opposition-strength statistically hard to decide choices) do not take into account the probable response from the opponent.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T11:21:17.343Z
Answers.Text: I illustrate an alternative "hard to decide" choice to shed light on a "perfect" chess strategy which fails to take into account the strategy quality of an imperfect opponent in a paragraph following the sentence "What choice to you make when you have plausible corner cases?...". What I mean with that is applying a brute approach by somewhat arbitrarily deleting options in an undecidable case and leaving only one doesn't lead to optimal strategy because it fails to account for variances in how likely a suboptimal opponent is to be able to reliably defend against different "equal" strategies.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T16:52:26.250Z
Answers.Text: "arbitrarily deleting options in an undecidable case and leaving only one doesn't lead to optimal strategy". If optimal strategy is getting the best outcome, and you have a tablebase, then arbitrarily deleting options when needed is optimal strategy. It could never result in a worse outcome.
Answers.UserDisplayName: Goose
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:32:59.280Z
Answers.Text: I disagree, which is why I wrote what I did. Optimal strategy is always being able to find the best strategy. I also argue that chess is only deterministic if the best strategy can always be determined at every move. 
  
  The reason arbitrarily deleting alternatives will not lead to optimal strategy is such a strategy for designing a chess engine ignores the permutations, and weighted probability, of the opponents reply and in ignoring those probabilities it will not find the best strategy against all players. I even provide an example of this in my question where I state my case (continued)
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:36:21.217Z
Answers.Text: I will provide an example again: The idea it's totally ambivalent choice brings with it the assumption that the chess engine will be playing against an oracle. Other answers make the same assumption. The truth is the optimal strategy will fold-in the reality that the chess engine will not be playing itself all the time. Sometimes it will play humans. That's a very different scenario in which positional and defence complexities play a role which they do not when playing an oracle. A chess engine which assumes it is playing an oracle will be less effective against a human because (continued)
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:39:33.937Z
Answers.Text: An example is this: 
  
  A move may exist which, when playing an oracle, the game ends in a draw. In fact, this may be true of all chess games right from the start when playing an oracle but chess engines do not always play against oracles, sometimes they play against humans or other chess engines with suboptimal strategy. This means, for example usually, Alpha Zero may always draw against itself but it will always win against any known human player and most other chess engines.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:45:17.310Z
Answers.Text: Let's devise a theoretical position for illustration: At any point in the game (even from the first move) there may be a position in which the perfect opponent can always pull the game into a draw but a human player usually will not achieve the same thing. A human player against an oracle will lose. That's an important difference and it has strategic implications: The Perfect chess engine Can win when playing Imperfect opponents.
  
  In my statement following my question I write a sentence which says "What if you have a move you can make and..." (continued)
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T20:49:56.517Z
Answers.Text: The purpose of that statement is to illustrate the fact that a chess engine given choices against an oracle may always be pulled into a draw but they won't against a suboptimal player which the chess engine is more likely to beat. What makes decisions complicated in that scenario is probabilistic factors come into play based on how likely the opponent is to be able to defeat the strategy. These probabilities will change depending on the strength of the opponent so arbitrarily culling choices because they make no difference when playing an oracle won't work as well when playing human opponents.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-09T14:17:09.193Z
Answers.Text: @GeorginaDavenport Yep, playing certain moves can force mistakes better than others. However in chess "the output is determined solely by the input and initial conditions" so chess is deterministic in it's mathematical definition. If this is a philosophy question you might want to try a philosophy stack exchange or forum.
Answers.UserDisplayName: Goose
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-14T02:34:42.323Z
Answers.Text: OK, I can take that but my contention is, that's easy enough to say, but ignores how to determine which output /should/ be produced by the input which, I claim, in at least some cases, is indeterminable. i.e. there is no single determinable output for any input meaning there is no "pure" cause and effect response from every given legal position. From some positions there is circuit-noise in terms of the objectively unavailable prediction of the opponents response, which can never be fully accounted for.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T03:54:02.647Z
Answers.LastActivityDate: 2024-05-07T03:54:02.647Z
Answers.UserDisplayName: Goose
Answers.Body: <p>Proof is impossible, but nobody believes that chess is a win for Black, and almost nobody believes that it is a win for White. With almost complete certainty it is a draw and very far from uniquely so. According to your definition it is therefore not deterministic. The fact that not all games between experts end in a draw is due to the fact that one or both of the players tries to win (otherwise why play?) and will create or acceed to imbalances that are not necessary.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T11:10:16.793Z
Answers.Text: Yes, I expect even the best human players, however they play, will at some stage make a move which may work against a very strong human opponent but lose against an ideal chess oracle. The point here though is even if both players are perfect chess oracles the game still is not deterministic because there will still arise positions from which an ideal next move is undecidable and therefore the game is not deterministic. My post includes reference to positions where the next move can be shown to be undecidable.
Answers.UserDisplayName: Georgina Davenport
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-05-07T03:38:32.277Z
Answers.LastActivityDate: 2024-05-07T03:38:32.277Z
Answers.UserDisplayName: Philip Roe
Body: <p>I don't know why the &quot;determinism&quot; of chess is treated as if self-evident. It isn't self evident to me.</p>
  <p>I will guess: The determinism of chess is determined by the thought experiment that, in theory, every possible legal chess game can be determined from the rules and the starting position. You could, in theory, build a database of every move in chess linked to every next legal move from any position. Obviously this database would be huge but its size doesn't alter the fact it is finite and so a complete map of every possible chess game can be constructed from a database of every legally producible chess position there is.</p>
  <p>OK..... should that be the case I don't think this theoretical &quot;complete information&quot; setup also implies chess is deterministic for the reasons below:</p>
  <p>Let me start with conjecturing that such a complete picture of chess could be constructed by way of a huge finite state automaton. Each possible legally-approached chess position (state) exists as a node on the automaton and from each node arcs lead away to every legal move from that position. If we take this literally then you need a unique state for each position plus how many times that position has recurred before specific state changes have occurred to accommodate the 50 and 75 move rules but even though it's still impossible you could save a lot of duplication by simply factoring in counters which count to 50 or 75 moves or repeat positions and reset when a necessary state change occurs which blocks the rules from being invoked.</p>
  <p>That's just modelling every state. Now I want to look at what happens when we want to change the graph so rather than just an exhaustive map of every possible chess game instead paths from one position to each it is joined to by a legal move are deleted if they lead to suboptimal play, leaving only the arcs which join each move to the next by the best available move. The problem starts below with certain possible limits to that &quot;optimal move&quot; deciding function IF no decision function can be constructed which is able to chose a best move over every other possible move.</p>
  <p>Now we are using an automaton I want to consider that the universe of finite state automata can be separated into different kinds. One way we can separate finite state automata into groups is by separating deterministic finite state automata from non-deterministic finite state automata.</p>
  <p>It is reasonable to consider whether or not such as optimised map of chess as described above can be played by a finite state automaton (assuming there are a finite number of plausible chess-board layouts consisting only of board layouts which can be arrived at by legal play and that any chessboard layout which can be created but which cannot occur through legal play can be removed from the map because it won't ever happen).</p>
  <p>The trouble though is that you cannot say for sure at the outset of this problem of optimal play whether or not chess strategy can be optimised by way of a deterministic finite state automaton or whether it can only be solved by way of a non-deterministic FSA to be soluble at all. The latter case of requiring a ND-FSA might at the outset to sound very unlikely so I will explain:</p>
  <p>A condition under which chess may not be deterministic is if there is at least one position which can be found under which, after qualitatively ranking all the available moves, is found to have at least one legal next-move of equal rank to the best move. Clarification: Yes, there definitely may exist many well understood chess positions from which there is certainly only a single best move. Many &quot;mate in...&quot; chess problems take advantage of the fact there really is sometimes absolutely one best move.</p>
  <p>The problem begins with the fact that from the outset you do not know if &quot;only one single best move&quot; is true of /every possible chess position/ arrived at by legal play or if there is in fact at least one position, arrived at legally, lying as a node on a path of optimal play, for which there is no difference in rank between at least the first and second best move. There may not be many positions with an undecidable next but there may at least one and at least one may be found to lie on the pathway of optimal play.</p>
  <p>The same but simplified: If there is any legal position in chess which can be arrived at by legal play and which lies on a (so far) optimal path for which it can be proven there exists at least one move which is different from but equally as good as the best move then chess is not deterministic.</p>
  <p>Another way to look at the same problem is by working backwards from the end rather than starting at the beginning: One might start by listing every possible position a chess game can end on and (assuming you have a method which can discover those positions), from that, list every possible single penultimate position which could have led into it. For any endgame position, taken alongside every other endgame position of equal value, when more than one chess end position of equal value can be fallen into from any other single valid chess position then when in that single valid chess position an overall best move forward cannot be found because you are in an &quot;either A or B or...&quot; state without a best choice.</p>
  <p>This suggests that /there may be/ chess positions which are the chess equivalent of Buridan's ass.</p>
  <p><a href="https://en.wikipedia.org/wiki/Buridan%27s_ass" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Buridan%27s_ass</a></p>
  <blockquote>
  <p>&quot;...a man, being just as hungry as thirsty, and placed in between food
  and drink, must necessarily remain where he is and starve to death&quot;</p>
  </blockquote>
  <p><em>— Aristotle, On the Heavens 295b, c. 350 BC</em></p>
  <p>Furthermore there may be stochastic choices which may lead to any one of a number of different states of different value without either choice being decidable because which future it lands upon depends on at least one opponent's move. What choice to you make when you have plausible corner cases? What if you have a move you can make and, after searching to the end of every branch of the decision tree thereafter you discover there are a billion different scenarios which end up with you winning and one which ends up with you losing but which turns out to be easy to defeat versus another choice of move which leads to many more loss end-states for your move but whose loss end-states are much harder to reach for your opponent? Then which is the best move may not be predictable because you cannot predict the response of your opponent.</p>
  <p>If, after that, you do indeed need find a state where you need to pick a random move from moves of equal value or else have no way to move forward if you don't, and if there are also positions like this from which it can be proven there is no solution to this decision problem, then chess is not deterministic.</p>
  <p>So, I say for it to be determined whether or not chess is fully deterministic it must first be established whether or not there exists some legal position, which can be arrived at by perfect play, on a path of thus-far known optimal decisions, from which there is an equal choice between best moves such that no process can possibly chose a single best move.</p>
  <p>What this comes down to is for chess to be proven deterministic it must first be proven that for every step on an optimal path the next move must always be decidable. For all we know about chess strategy now, this might not be true. There may be positions from which the next best move is undecidable, even by an oracle or God, such as with Buridan's ass wherein no choice is better than at least one other. If this latter case proves to be true then chess is not deterministic.</p>
  <p>If we try to change the picture and state &quot;Well, if such states with equal-best choices exist then rather than going with random choice we simply take every position where this is true and simply remove all but one decision before we begin. There you go, it's deterministic now&quot; then you still have the problem that which paths to delete leaving only one may not be decidable and if you just choose one at random then this random choice may better stronger against one kind of chess player and weaker against another: A purely stochastic approach may diminish the power of the chess computer because which one of an equal choice actually works best might be affected by knowledge of the predicted opposing strategy. A theoretical &quot;best move&quot; may be very different when playing against another oracle from what it is when playing against a human player of less than elite skill.</p>
  <p>Conclusion: Whatever the variables there may be at least one legal position in chess from which a best unique decision is impossible because from that position there is no better choice than to choose randomly from the top two (or more) moves in which case chess is not deterministic.</p>
  <p>Finally: In this chess stack exchange somebody asks the question and among the answers are some which are said to prove from some positions the next move is undecidable.</p>
  <p><a href="https://chess.stackexchange.com/questions/4638/is-there-a-single-best-move-in-every-position">Is there a single best move in every position?</a></p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-07T01:05:33.817Z
Comments.Text: Your question is very long and would benefit from separating your actual question (including your exact definition of "deterministic") from your other commentary.
Comments.UserDisplayName: D M
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-07T01:22:20.287Z
Comments.Text: True, it is long. The actual question is right at the top "Has chess been proven to be deterministic?". The definition of "deterministic" I am using is analogous to the difference between a deterministic finite state automaton (from any state each input can lead to only one next state) and a non-deterministic finite state automaton (from some states an input can lead to more than one next state with there being no possible way to decide which one). In my conclusion I link to a page where just such a state is revealed.
Comments.UserDisplayName: Georgina Davenport
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-07T08:58:34.093Z
Comments.Text: Usually we say that chess is determinist because a very large but finite automaton can determine whether the starting position is a draw or a win for either side with best play. @Naom_Elkies' answers details this math result. You seem to use a different definition : can a game be determined, i.e. each of its moves, not only its result, with the constraint that "the optimal move" is always played ? But that would depend how you define "optimal move". For our all-knowing automaton, every move that draws from a drawn position is equally "optimal", even hanging the R when you have K+R+B vs K+R...
Comments.UserDisplayName: Evargalo
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-07T11:30:57.387Z
Comments.Text: Yes, I think the problem of defining what can be meant by "optimal strategy" is difficult. As soon as I try I will be shot-down by people noting why it isn't optimal as I thought it was. Essentially my plan would be to start where I do in my question and (impossibly) iterate for every possible legal chess game until game end to create a database of every possible game. After that create a graph which, after each move, culls as many losing and drawing games from the future search tree as can be achieved until, eventually, only checkmate remains at the end of every available tree branch.
Comments.UserDisplayName: Georgina Davenport
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-07T11:36:49.183Z
Comments.Text: My argument against determinism is to predict the downfall of the strategy delineated in my previous comment is that it isn't possible. What would happen is, even if you had an unlimited computer with 0 processing time on any problem, the process would eventually hit choices which are undecidable thus leading to the conclusion chess is not deterministic. I also explain why I believe that among those undecidable choices may be cases where the options are between a win and a loss, not just positions leading to equal outcome, because the potential outcomes are altered by suboptimal opponents.
Comments.UserDisplayName: Georgina Davenport
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-07T11:42:09.630Z
Comments.Text: Illustrating the comment above: It may sound foolish to suggest a choice between a win and a loss is undecidable but the real suggestion is that for a large part of the game you will be dealing with the probability of arriving at an end state rather than certainty and that probability depends on the opponent's strength. It implies that what would certainly lead to a loss against an oracle may instead lead to a higher probability of a win against a suboptimal strategist which is the most likely case when playing chess "in the wild" against people rather than playing against oracles.
Comments.UserDisplayName: Georgina Davenport
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-18T22:11:49.910Z
Comments.Text: CRANK ALERT! Of course chess is deterministic -- this should surely be obvious to anybody. Posting 1500 words of gobbledygook won't change that! Such a determined crank can't be persuaded by any argument, so it's not worth trying.
Comments.UserDisplayName: TonyK
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-05-19T14:53:27.223Z
Comments.Text: That is nothing better than a troll post. 
  
  The point of the question is PROOF it is deterministic and insisting it is definitely is not proof.
  
  So, off you do and prove it.
Comments.UserDisplayName: Georgina Davenport
Tags: <strategy>
Title: Has chess been Proven to be deterministic?
ThreadText: # Has chess been Proven to be deterministic?
  
  (Asked by: username_0 on 2024-05-07)
  
  I don't know why the "determinism" of chess is treated as if self-evident. It isn't self evident to me.
  
  I will guess: The determinism of chess is determined by the thought experiment that, in theory, every possible legal chess game can be determined from the rules and the starting position. You could, in theory, build a database of every move in chess linked to every next legal move from any position. Obviously this database would be huge but its size doesn't alter the fact it is finite and so a complete map of every possible chess game can be constructed from a database of every legally producible chess position there is.
  
  OK..... should that be the case I don't think this theoretical "complete information" setup also implies chess is deterministic for the reasons below:
  
  Let me start with conjecturing that such a complete picture of chess could be constructed by way of a huge finite state automaton. Each possible legally-approached chess position (state) exists as a node on the automaton and from each node arcs lead away to every legal move from that position. If we take this literally then you need a unique state for each position plus how many times that position has recurred before specific state changes have occurred to accommodate the 50 and 75 move rules but even though it's still impossible you could save a lot of duplication by simply factoring in counters which count to 50 or 75 moves or repeat positions and reset when a necessary state change occurs which blocks the rules from being invoked.
  
  That's just modelling every state. Now I want to look at what happens when we want to change the graph so rather than just an exhaustive map of every possible chess game instead paths from one position to each it is joined to by a legal move are deleted if they lead to suboptimal play, leaving only the arcs which join each move to the next by the best available move. The problem starts below with certain possible limits to that "optimal move" deciding function IF no decision function can be constructed which is able to chose a best move over every other possible move.
  
  Now we are using an automaton I want to consider that the universe of finite state automata can be separated into different kinds. One way we can separate finite state automata into groups is by separating deterministic finite state automata from non-deterministic finite state automata.
  
  It is reasonable to consider whether or not such as optimised map of chess as described above can be played by a finite state automaton (assuming there are a finite number of plausible chess-board layouts consisting only of board layouts which can be arrived at by legal play and that any chessboard layout which can be created but which cannot occur through legal play can be removed from the map because it won't ever happen).
  
  The trouble though is that you cannot say for sure at the outset of this problem of optimal play whether or not chess strategy can be optimised by way of a deterministic finite state automaton or whether it can only be solved by way of a non-deterministic FSA to be soluble at all. The latter case of requiring a ND-FSA might at the outset to sound very unlikely so I will explain:
  
  A condition under which chess may not be deterministic is if there is at least one position which can be found under which, after qualitatively ranking all the available moves, is found to have at least one legal next-move of equal rank to the best move. Clarification: Yes, there definitely may exist many well understood chess positions from which there is certainly only a single best move. Many "mate in..." chess problems take advantage of the fact there really is sometimes absolutely one best move.
  
  The problem begins with the fact that from the outset you do not know if "only one single best move" is true of /every possible chess position/ arrived at by legal play or if there is in fact at least one position, arrived at legally, lying as a node on a path of optimal play, for which there is no difference in rank between at least the first and second best move. There may not be many positions with an undecidable next but there may at least one and at least one may be found to lie on the pathway of optimal play.
  
  The same but simplified: If there is any legal position in chess which can be arrived at by legal play and which lies on a (so far) optimal path for which it can be proven there exists at least one move which is different from but equally as good as the best move then chess is not deterministic.
  
  Another way to look at the same problem is by working backwards from the end rather than starting at the beginning: One might start by listing every possible position a chess game can end on and (assuming you have a method which can discover those positions), from that, list every possible single penultimate position which could have led into it. For any endgame position, taken alongside every other endgame position of equal value, when more than one chess end position of equal value can be fallen into from any other single valid chess position then when in that single valid chess position an overall best move forward cannot be found because you are in an "either A or B or..." state without a best choice.
  
  This suggests that /there may be/ chess positions which are the chess equivalent of Buridan's ass.
  
  <https://en.wikipedia.org/wiki/Buridan%27s_ass>
  
  > "...a man, being just as hungry as thirsty, and placed in between food
  > and drink, must necessarily remain where he is and starve to death"
  
  *— Aristotle, On the Heavens 295b, c. 350 BC*
  
  Furthermore there may be stochastic choices which may lead to any one of a number of different states of different value without either choice being decidable because which future it lands upon depends on at least one opponent's move. What choice to you make when you have plausible corner cases? What if you have a move you can make and, after searching to the end of every branch of the decision tree thereafter you discover there are a billion different scenarios which end up with you winning and one which ends up with you losing but which turns out to be easy to defeat versus another choice of move which leads to many more loss end-states for your move but whose loss end-states are much harder to reach for your opponent? Then which is the best move may not be predictable because you cannot predict the response of your opponent.
  
  If, after that, you do indeed need find a state where you need to pick a random move from moves of equal value or else have no way to move forward if you don't, and if there are also positions like this from which it can be proven there is no solution to this decision problem, then chess is not deterministic.
  
  So, I say for it to be determined whether or not chess is fully deterministic it must first be established whether or not there exists some legal position, which can be arrived at by perfect play, on a path of thus-far known optimal decisions, from which there is an equal choice between best moves such that no process can possibly chose a single best move.
  
  What this comes down to is for chess to be proven deterministic it must first be proven that for every step on an optimal path the next move must always be decidable. For all we know about chess strategy now, this might not be true. There may be positions from which the next best move is undecidable, even by an oracle or God, such as with Buridan's ass wherein no choice is better than at least one other. If this latter case proves to be true then chess is not deterministic.
  
  If we try to change the picture and state "Well, if such states with equal-best choices exist then rather than going with random choice we simply take every position where this is true and simply remove all but one decision before we begin. There you go, it's deterministic now" then you still have the problem that which paths to delete leaving only one may not be decidable and if you just choose one at random then this random choice may better stronger against one kind of chess player and weaker against another: A purely stochastic approach may diminish the power of the chess computer because which one of an equal choice actually works best might be affected by knowledge of the predicted opposing strategy. A theoretical "best move" may be very different when playing against another oracle from what it is when playing against a human player of less than elite skill.
  
  Conclusion: Whatever the variables there may be at least one legal position in chess from which a best unique decision is impossible because from that position there is no better choice than to choose randomly from the top two (or more) moves in which case chess is not deterministic.
  
  Finally: In this chess stack exchange somebody asks the question and among the answers are some which are said to prove from some positions the next move is undecidable.
  
  [Is there a single best move in every position?](https://chess.stackexchange.com/questions/4638/is-there-a-single-best-move-in-every-position)
  
  **Tags:** strategy
  
  > **Comments:**
  > **username_1**: Your question is very long and would benefit from separating your actual question (including your exact definition of "deterministic") from your other commentary.  
  > **username_0**: True, it is long. The actual question is right at the top "Has chess been proven to be deterministic?". The definition of "deterministic" I am using is analogous to the difference between a deterministic finite state automaton (from any state each input can lead to only one next state) and a non-deterministic finite state automaton (from some states an input can lead to more than one next state with there being no possible way to decide which one). In my conclusion I link to a page where just such a state is revealed.  
  > **username_2**: Usually we say that chess is determinist because a very large but finite automaton can determine whether the starting position is a draw or a win for either side with best play. @Naom_Elkies' answers details this math result. You seem to use a different definition : can a game be determined, i.e. each of its moves, not only its result, with the constraint that "the optimal move" is always played ? But that would depend how you define "optimal move". For our all-knowing automaton, every move that draws from a drawn position is equally "optimal", even hanging the R when you have K+R+B vs K+R...  
  > **username_0**: Yes, I think the problem of defining what can be meant by "optimal strategy" is difficult. As soon as I try I will be shot-down by people noting why it isn't optimal as I thought it was. Essentially my plan would be to start where I do in my question and (impossibly) iterate for every possible legal chess game until game end to create a database of every possible game. After that create a graph which, after each move, culls as many losing and drawing games from the future search tree as can be achieved until, eventually, only checkmate remains at the end of every available tree branch.  
  > **username_0**: My argument against determinism is to predict the downfall of the strategy delineated in my previous comment is that it isn't possible. What would happen is, even if you had an unlimited computer with 0 processing time on any problem, the process would eventually hit choices which are undecidable thus leading to the conclusion chess is not deterministic. I also explain why I believe that among those undecidable choices may be cases where the options are between a win and a loss, not just positions leading to equal outcome, because the potential outcomes are altered by suboptimal opponents.  
  > **username_0**: Illustrating the comment above: It may sound foolish to suggest a choice between a win and a loss is undecidable but the real suggestion is that for a large part of the game you will be dealing with the probability of arriving at an end state rather than certainty and that probability depends on the opponent's strength. It implies that what would certainly lead to a loss against an oracle may instead lead to a higher probability of a win against a suboptimal strategist which is the most likely case when playing chess "in the wild" against people rather than playing against oracles.  
  > **username_3**: CRANK ALERT! Of course chess is deterministic -- this should surely be obvious to anybody. Posting 1500 words of gobbledygook won't change that! Such a determined crank can't be persuaded by any argument, so it's not worth trying.  
  > **username_0**: That is nothing better than a troll post.   The point of the question is PROOF it is deterministic and insisting it is definitely is not proof.  So, off you do and prove it.  
  
  ---
  
  ## 3 answers
  
  ### Answer by username_4 on 2024-05-07. Score: 3
  
  The answer is yes, and is usually attributed to Zermelo.
  
  Imagine a (finite, albeit impractically large) list of all possible
  chess positions.
  
  In some of the BTM (Black To Move) positions, Black is mated. Mark those.
  
  All the WTM positions that can reach one of these positions are mates in 1.
  Mark those.
  
  In a BTM position, Black is mated in 1 if and only if
  Black is not already mated but every legal move is to
  a position on the Mate in 1 list. Mark those.
  
  A WTM that's not already on the Mate in 1 list is Mate in 2
  if and only if White can move to a position where Black is mated in 1.
  Mark those.
  
  In a BTM position, Black is mated in 2 if nad only if
  Black is not already mated, nor mated in 1, but every legal move is to
  a position on the Mate in 1 or Mate in 2 list. Mark those.
  
  A WTM that's not already on the Mate in 1 list and Mate in 2 lists
  is Mate in 3 if and only if White can move to a position where
  Black is mated in 2. Mark those.
  
  Keep going. At some point you'll not be able to mark any new positions.
  At that point, you have all the positions where White wins by force,
  and an optimal move from each one
  (where White wants to mate as fast as possible
  and Black wants to delay mate as long as possible).
  
  Do the same thing with colors reversed to find all the forced Black wins
  and an optimal move from each such position.
  
  The remaining positions are all draws; either player in a drawn position
  has at least one move to another drawn position (else either that player
  or their opponent has a forced win).
  
  This analysis ignores the rules of triple repetition and 50 moves,
  but it's easy enough (in principle, which is all we're claiming)
  to incorporate them. For example, each position can come with a
  50-move counter; this still makes for a finite (albeit even more
  impractically large) list of possible positions.
  
  > **Comments:**
  > **username_0**: Ok, far be it for me to argue with the joint creator of ZFC, but my response to this is in the answers I predicted in the body of my post expressing why I doubt chess is deterministic. I start that paragraph with "Another way to look at the same problem is...". There my reasoning is even tracing back from the end, in the manner you describe, you won't end up at the start of the game, you will hit a barrier when you eventually find a move (taking your example this time) where the opposing player has a choice whereby they can avoid being pushed into the endgame you started working back from.  
  > **username_4**: @username_0 in that case the starting position is a draw (as most players expect); by consulting the completed table, both players can then play forever -- or until some draw agreement or rule kicks in -- each time moving from one drawn position to another.  In principle it's no different from perfect play with K+R vs. K+R.  
  > **username_0**: I don't know if I agree. In that case you are assuming the oracle will only play other oracles. Maybe it will. I also agree (by assumption) that chess is like tic-tac-toe and Connect4 in that when two ideal players are pitted against each other the game always ends in a draw. The thing is though, that isn't the thing I'm trying to examine. Even with Connect 4 and tic-tac-toe being that way, this does not cause an obstruction to creating an ideal player and it does not create an obstacle in deciding what happens when you try to create an ideal player by systematisation (continued)  
  > **username_0**: First of all then, a perfect chess computer will not draw games when playing against most human players, it will win. We know for a fact that nobody has thought "it's always a draw" and stopped making chess engines and it has never been proven the game does always draw. That's only what we get with current chess engines which are not perfect chess players. Alpha Zero against StockFish doesn't draw, it wins, so we know there is still headspace for making a better chess engine even than StockFish and we know the quest continues (continued)  
  > **username_0**: Meanwhile, we are veering off track. This question is about determinism. My contention is that chess is deterministic only as long as every position is decidable. My contention is also that we already have examples of undecidable chess positions. For that reason chess is not deterministic. Should a finite state automaton be made which plays chess for that automaton to have a complete map of every possible chess game it would need to be a non-deterministic finite state automaton. For that reason I say chess is not deterministic.  
  
  ---
  
  ### Answer by username_5 on 2024-05-07. Score: 1
  
  > So, I say for it to be determined whether or not chess is fully deterministic it must first be established whether or not there exists some legal position, which can be arrived at by perfect play, on a path of thus-far known optimal decisions, from which there is an equal choice between best moves such that no process can possibly chose a single best move.
  >
  > What this comes down to is for chess to be proven deterministic it must first be proven that for every step on an optimal path the next move must always be decidable. For all we know about chess strategy now, this might not be true. There may be positions from which the next best move is undecidable, even by an oracle or God, such as with Buridan's ass wherein no choice is better than at least one other. If this latter case proves to be true then chess is not deterministic.
  
  This feels like the core of your question. Such positions are very frequent in games. To borrow from [Is there a single best move in every position?](https://chess.stackexchange.com/questions/4638/is-there-a-single-best-move-in-every-position?noredirect=1&lq=1), here's a position with 5 such moves.
  
  ```
  [FEN "k7/6Q1/1K7/8/8/8/8/8 w - - 0 1"]
  
  ```
  
  As a matter of fact, most non tactical line positions usually have multiple moves that lead to the same best outcome with perfect play.
  
  This seems to meet your criteria. That said, I don't believe this makes chess nondeterministic as a deterministic process can still be used when multiple equal moves exist without using randomness. One example would be sorting moves alphanumerically and picking the first one.
  
  > **Comments:**
  > **username_0**: Yes, it does meet the criteria which is why I link to that same position in my post which appears to me to prove my point.  In my question I also pre-empt your response in the paragraph which begins with the words "If we try to change the picture and state...". In that paragraph I express why i believe that such a method as you propose leads directly to suboptimal strategy because the self-same undecidable choices (and opposition-strength statistically hard to decide choices) do not take into account the probable response from the opponent.  
  > **username_0**: I illustrate an alternative "hard to decide" choice to shed light on a "perfect" chess strategy which fails to take into account the strategy quality of an imperfect opponent in a paragraph following the sentence "What choice to you make when you have plausible corner cases?...". What I mean with that is applying a brute approach by somewhat arbitrarily deleting options in an undecidable case and leaving only one doesn't lead to optimal strategy because it fails to account for variances in how likely a suboptimal opponent is to be able to reliably defend against different "equal" strategies.  
  > **username_5**: "arbitrarily deleting options in an undecidable case and leaving only one doesn't lead to optimal strategy". If optimal strategy is getting the best outcome, and you have a tablebase, then arbitrarily deleting options when needed is optimal strategy. It could never result in a worse outcome.  
  > **username_0**: I disagree, which is why I wrote what I did. Optimal strategy is always being able to find the best strategy. I also argue that chess is only deterministic if the best strategy can always be determined at every move.   The reason arbitrarily deleting alternatives will not lead to optimal strategy is such a strategy for designing a chess engine ignores the permutations, and weighted probability, of the opponents reply and in ignoring those probabilities it will not find the best strategy against all players. I even provide an example of this in my question where I state my case (continued)  
  > **username_0**: I will provide an example again: The idea it's totally ambivalent choice brings with it the assumption that the chess engine will be playing against an oracle. Other answers make the same assumption. The truth is the optimal strategy will fold-in the reality that the chess engine will not be playing itself all the time. Sometimes it will play humans. That's a very different scenario in which positional and defence complexities play a role which they do not when playing an oracle. A chess engine which assumes it is playing an oracle will be less effective against a human because (continued)  
  > **username_0**: An example is this:   A move may exist which, when playing an oracle, the game ends in a draw. In fact, this may be true of all chess games right from the start when playing an oracle but chess engines do not always play against oracles, sometimes they play against humans or other chess engines with suboptimal strategy. This means, for example usually, Alpha Zero may always draw against itself but it will always win against any known human player and most other chess engines.  
  > **username_0**: Let's devise a theoretical position for illustration: At any point in the game (even from the first move) there may be a position in which the perfect opponent can always pull the game into a draw but a human player usually will not achieve the same thing. A human player against an oracle will lose. That's an important difference and it has strategic implications: The Perfect chess engine Can win when playing Imperfect opponents.  In my statement following my question I write a sentence which says "What if you have a move you can make and..." (continued)  
  > **username_0**: The purpose of that statement is to illustrate the fact that a chess engine given choices against an oracle may always be pulled into a draw but they won't against a suboptimal player which the chess engine is more likely to beat. What makes decisions complicated in that scenario is probabilistic factors come into play based on how likely the opponent is to be able to defeat the strategy. These probabilities will change depending on the strength of the opponent so arbitrarily culling choices because they make no difference when playing an oracle won't work as well when playing human opponents.  
  > **username_5**: @username_0 Yep, playing certain moves can force mistakes better than others. However in chess "the output is determined solely by the input and initial conditions" so chess is deterministic in it's mathematical definition. If this is a philosophy question you might want to try a philosophy stack exchange or forum.  
  > **username_0**: OK, I can take that but my contention is, that's easy enough to say, but ignores how to determine which output /should/ be produced by the input which, I claim, in at least some cases, is indeterminable. i.e. there is no single determinable output for any input meaning there is no "pure" cause and effect response from every given legal position. From some positions there is circuit-noise in terms of the objectively unavailable prediction of the opponents response, which can never be fully accounted for.  
  
  ---
  
  ### Answer by username_6 on 2024-05-07. Score: 0
  
  Proof is impossible, but nobody believes that chess is a win for Black, and almost nobody believes that it is a win for White. With almost complete certainty it is a draw and very far from uniquely so. According to your definition it is therefore not deterministic. The fact that not all games between experts end in a draw is due to the fact that one or both of the players tries to win (otherwise why play?) and will create or acceed to imbalances that are not necessary.
  
  > **Comments:**
  > **username_0**: Yes, I expect even the best human players, however they play, will at some stage make a move which may work against a very strong human opponent but lose against an ideal chess oracle. The point here though is even if both players are perfect chess oracles the game still is not deterministic because there will still arise positions from which an ideal next move is undecidable and therefore the game is not deterministic. My post includes reference to positions where the next move can be shown to be undecidable.  
  
  ---
  
  