I Who would win a perfect game of chess?

[jbriggs444]

To justify it you need to know all the possible moves.

To justify it, you need to have analyzed the game tree for all possible continuations of all the possible moves.

 

[MathematicalPhysicist]

You're missing the whole point. Simply moving first is an advantage. If you don't believe it, just look at the statistics of high level chess games. Most wins are by white. The question is whether the advantage of moving first is enough to win a game where both players follow the optimum strategy. We don't know.

I saw the statistics of mfb and it seems there are more draws than wins for the white.
The question is when if ever will we exhaust all the number of moves possible in chess?
How could one prove what are the optimal strategies without covering all the possible moves?

OK, I'll edit my previous post, though I am quite sure of a draw, mark my words! :-D
And another question how can one prove optimality of a game without knowing all the possible outcomes?

 

[MathematicalPhysicist]

72 of the 100 games between Alpha Zero and Stockfish were a draw and interestingly, the win/draw ratio was 25/25 when Alpha Zero played white but only 3/47 when it played black (Alpha Zero won every game). I have not seen any statistics released on the 44 million training games played regarding an advantage for white vs. black.https://arxiv.org/pdf/1712.01815.pdf

Did Alpha zero played its equal?
I.e itself?

 

[TeethWhitener]

And another question how can one prove optimality of a game without knowing all the possible outcomes?

If, for example, you can show that it's always possible for white (or black) to reach a position with a forced mate, you only have to evaluate the possible moves leading to that position.

 

[phyzguy]

And another question how can one prove optimality of a game without knowing all the possible outcomes?

This is like asking how we can know that there are an infinite number of prime numbers without having examined all possible integers. There are mathematical methods which allow you to prove things about very large (or even infinte) sets without having to examine every case. Game theory has used mathematical methods to prove that every game of perfect information has at least one optimal strategy, meaning a strategy which cannot be improved upon.

 

[cosmik debris]

Did Alpha zero played its equal?
I.e itself?

Yes, roughly 20 million I believe. It trained for four hours.

Cheers

 

[MathematicalPhysicist]

This is like asking how we can know that there are an infinite number of prime numbers without having examined all possible integers. There are mathematical methods which allow you to prove things about very large (or even infinte) sets without having to examine every case. Game theory has used mathematical methods to prove that every game of perfect information has at least one optimal strategy, meaning a strategy which cannot be improved upon.

OK, then how would you try finding this optimal strategy?
I know how to prove that there are infinite prime numbers.
I mean without some trial and error I don't see how can you find an optimal strategy?

 

[PeroK]

To justify it you need to know all the possible moves.

You are the only one who claims to have a solution. Everyone else is saying that we do not know. That chess is too complicated to decide between a white win and a draw, with perfect play on both sides.

The evidence from chess theory is that white has a small advantage by moving first, but that it less than the minimum needed to guarantee a win. A proof of this cannot be furnished simply by considerations of symmetry.

 

[MathematicalPhysicist]

You are the only one who claims to have a solution. Everyone else is saying that we do not know. That chess is too complicated to decide between a white win and a draw, with perfect play on both sides.

The evidence from chess theory is that white has a small advantage by moving first, but that it less than the minimum needed to guarantee a win. A proof of this cannot be furnished simply by considerations of symmetry.

I didn't claim to have a solution, it's just my strong belief which I see is unjustified.
So why in checkers for example the advantage in starting isn't sufficient to enforce a win?
What mathematical argument was given for this?

 

[TeethWhitener]

So why in checkers for example the advantage in starting isn't sufficient to enforce a win?
What mathematical argument was given for this?

http://science.sciencemag.org/content/317/5844/1518

 

[phyzguy]

OK, then how would you try finding this optimal strategy?
I know how to prove that there are infinite prime numbers.
I mean without some trial and error I don't see how can you find an optimal strategy?

I didn't say you can find it, only that we know it exists. The fact that there are a huge number of moves and finding the optimal strategy is so difficult is why we don't know the answer to the OP's question. You can say, "I think it will be a draw," but there is no reason for the rest of us to believe you.

 

[PeroK]

I didn't claim to have a solution, it's just my strong belief which I see is unjustified.
So why in checkers for example the advantage in starting isn't sufficient to enforce a win?
What mathematical argument was given for this?

Checkers is a simpler game and has been crunched by a computer.

There's no reason that the solution for chess is the same. It might turn out that white can win.

 

[jbriggs444]

If, for example, you can show that it's always possible for white (or black) to reach a position with a forced mate, you only have to evaluate the possible moves leading to that position.

That sounds like the essence of alpha-beta pruning. If you are trying to decide between a forced win for white and a forced draw for black then black can prune away all moves other than to a known forced draw. White can prune away all moves other than to a known forced win.

 

[dRic2]

Spoiler

Although it might be intellectually/mathematically pleasing to think about it, what an horrible game would be a "perfect" game ?

I'm not criticizing the OP for the question (very legit), but I noticed that this kind of discussions seem to reduce chess to just "maths" (logic). A non-player (an outsider) might get the wrong idea! Chess is about art and phycology and culture and a lot of other stuff!

Now hate me for this useless comment

 

[MathematicalPhysicist]

Now when I think of it, white will always win, it's not the same as in checkers.

Try to play against the computer in level 10 with the hints with white in chess.com. I know it's not a proof, but it seems plausible that in this game the one who starts will win, if he played perfectly.
It took 109 moves, if I were to repeat these game will the moves of the black changed?

I have exams on Condensed Matter Physics and Particles theory 2 so no more time chatting here.
I stand corrected.

 

[MathematicalPhysicist]

Spoiler

Although it might be intellectually/mathematically pleasing to think about it, what an horrible game would be a "perfect" game ?

I'm not criticizing the OP for the question (very legit), but I noticed that this kind of discussions seem to reduce chess to just "maths" (logic). A non-player (an outsider) might get the wrong idea! Chess is about art and phycology and culture and a lot of other stuff!

Now hate me for this useless comment

You are in the wrong website.
:-D

 

[bahamagreen]

Last time I did programming was mainframe Fortran IV...

Given 64 squares and 32 pieces
Let all states of the board (including improper ones) be represented by a base 31 number of up to 64 places.
Assign the values 0-31 to the pieces, even white, odd black, as "digits" of this number.
Example of the initial board state at the beginning of a game might be something like:

1 3 5 7 9 11 13 15 17 19 21 23 25 27 29 31 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30

Treating these states as either numbers or strings, exclude states that represent:
- no pieces
- one piece
- two pieces where at least one of them is not a king
- more than one king of either color
- bishops on incorrect color square
- pawns on their back row
- too many of same color piece (due to pawn promotion... this would calculate how many duplicates of a piece are possible and allowed based on comparing the possible number of pawns promoted vs pawns not yet promoted and available to reach the back row)
- addition impossibilities in a game

Distinguish states that represent proper moves.
Set the initial starting game state as move number zero

For each set of all proper final move states* (see below) where the set's move number is one less than the present move number but not negative
For each piece
Test all states that re-position the piece to every square and eliminate states from the list that:
- re-position an incorrect color piece for that move sequence in the game
- re-position a piece to the square it is already occupying
- move a piece through an occupied square, inclusive (expect knights, and proper captures, castles)
- move a piece improperly per game rules of piece movement (including second same color castle)
(above piece movement tests done algebraically)
Mark or associate all proper final move states* for this move number with an indication of the move number and the moved piece number
Increment the move number
Repeat
This provides a disordered list of all proper piece position move states (including capture, castle, and promotion) for all move numbers of all proper games

Relate these proper move states into strings of all proper games
Using the proper final move states with their indication of the move number and the moved piece number

Set move number to one

For all proper states of the move number
Test all proper states where move number is one greater
If greater move number state is a proper move from the previous move state number, mark or associate the two
(include test for third of same move, move number greater than 50 if desired)
Increment move number
Repeat

Use the proper move associations to produce all possible proper games state number lists
Filter this list for however you define a "perfect game"

 

[PAllen]

The 50-move rule limits the maximum number of moves to just under 6000. There's a thread about it here:

https://www.physicsforums.com/threads/exact-number-of-possible-chess-games.730486

The 50 move rule is often removed for theoretical purposes. For example, tablebase analysis includes forced mates with hundreds of moves without capture or pawn move.

 

[PAllen]

Chess is unsolvable with traditional computers

Claude Shannon noted that a true chess solution would require storing 10^120 moves. This gets into age of the universe type computational times and impossible storage requirements with any conceivable computer technology other than maybe a huge quantum computer

No, that number would have to be analyzed but not stored. The result of analysis so far could use one of the compact tablebase representations. I once worked out this would only require a number of bits similar to atoms in the moon to play any position perfectly.

 

[PAllen]

Chess is kind of weakly solved when 7 pieces (including the two kings) remain on the board (discarding the castling moves and en passant). I don't know if they're working on 8 pieces, etc. An idea to have another indication that chess may be a draw (or a win/loss) with perfect play is to set symmetrical starting positions with the few pieces on the board and see the outcome of perfect moves.

I also guess that it leads to a draw, but it's just a pure guess.
Some chess variants are easier to deal with than chess (giveaway or suicide chess), whilst others are more complicated (crazyhouse).

Another very interesting question is whether all starting position of chess 960 (Fischer random chess) lead to the same outcome than regular chess, with perfect play.

I would say it is strongly solved for 7 or fewer pieces. The winner as well as best play for both sides, for any such position, can be generated ( even though the sequence itself is not stored).

 

[phyzguy]

Now when I think of it, white will always win, it's not the same as in checkers.

Try to play against the computer in level 10 with the hints with white in chess.com. I know it's not a proof, but it seems plausible that in this game the one who starts will win, if he played perfectly.
It took 109 moves, if I were to repeat these game will the moves of the black changed?

I have exams on Condensed Matter Physics and Particles theory 2 so no more time chatting here.
I stand corrected.

So you've replaced your guess that it would be a draw with the guess that white would win. Well, it's one of those two. If we knew which, we could answer the OPs question.

 

[PAllen]

Chess is kind of weakly solved when 7 pieces (including the two kings) remain on the board (discarding the castling moves and en passant). I don't know if they're working on 8 pieces, etc. An idea to have another indication that chess may be a draw (or a win/loss) with perfect play is to set symmetrical starting positions with the few pieces on the board and see the outcome of perfect moves.

I also guess that it leads to a draw, but it's just a pure guess.
Some chess variants are easier to deal with than chess (giveaway or suicide chess), whilst others are more complicated (crazyhouse).

Another very interesting question is whether all starting position of chess 960 (Fischer random chess) lead to the same outcome than regular chess, with perfect play.

Some of the starting positions in chess 960 are considered extremely favorable to one side, based on computer plus human analysis. Nothing is proven, but I would guess some are forced wins for one side.

 

[jbriggs444]

So you've replaced your guess that it would be a draw with the guess that white would win. Well, it's one of those two.

Is it proven that black cannot win against best play?

 

[Buzz Bloom]

The 50-move rule limits the maximum number of moves to just under 6000. There's a thread about it here:

Hi PeroK:

The 50 move rule was changed for a while but restored in 1992. It may well be modified again sometime in the future.

https://en.wikipedia.org/wiki/Fifty-move_rule
All of the basic checkmates can be accomplished in well under 50 moves. However, in the 20th century it was discovered that certain endgame positions are winnable but require more than 50 moves (without a capture or a pawn move). The rule was therefore changed to allow certain exceptions in which 100 moves were allowed with particular material combinations. However, winnable positions that required even more moves were later discovered, and in 1992, FIDE abolished all such exceptions and reinstated the strict 50-move rule.​

Regards,
Buzz

 

[PAllen]

I think it is important to note that Alphazero is a major breakthrough in machine learning, but says almost nothing about solving chess or perfect play in chess. The breakthrough is learning to play chess with no strategy input or example expert games, and reaching a level well beyond human experts. Perfect play, or even best computer was never a goal of the research. A few random observations on the theme that alphazero is very strong, but still far from an oracle of perfection:

- Alphazero mainly played stockfish 8. Stockfish 10 wins against stockfish 8 by at least as much as Alphazero did. Alphazero has not played against stockfish 10 because winning computer chess tournaments or even research in chess is not a priority at all for the deep mind team.

- In the Carlsen-Caruana world chess championship match, there was a game where stockfish 10 running on a supercomputer found a forced mate in 43 moves. Alphazero analyzing these games was unable to find this line.

- There are Alphazero losses indicating that its highly selective search plus deep position understanding (self developed), has weaknesses of the expected kind. There is a game where Stockfish 8 crushed Alphazero in 22 moves in a position with extremely deep tactics. This was exceedingly rare, and only uncovered when a thousand games were played, but it is sufficient to prevent making assumptions about solving chess based on Alphazero.

My opinion is that chess is likely drawn with best play, but this is purely an opinion.

 

[PAllen]

To answer the titular question of this thread: a perfect chess player

 

[PAllen]

Previous link titled: Solving chess - Wikipedia. More generally, Game complexity - Wikipedia, Solved game - Wikipedia

Solutions can be

• ultraweak - the outcome of the game if both players play perfectly. In some cases, one can do the solution non-constructively, like with strategy-stealing.
• weak - an algorithm that gives one player the best outcome, no matter what the other player does, when starting from the initial position.
• strong - like the above, but starting from any position.

Tic-tac-toe is strongly solved, and it is easy to solve it with brute force. Connect Four is more difficult, but it has been solved in its classic configuration, 7 wide and 6 high, and other small sizes. Likewise, Go has been solved for 7*7 and smaller sizes, though Go is typically played on a 19*19 board.

The most difficult board-game solution so far is for checkers, and is required an enormous amount of computing power. Computers Solve Checkers—It's a Draw - Scientific American, Chinook - World Man-Machine Checkers Champion, Checkers Is Solved | Science The abstract:

Note that checkers is weakly solved.

 

[PeroK]

Hi PeroK:

The 50 move rule was changed for a while but restored in 1992. It may well be modified again sometime in the future.

https://en.wikipedia.org/wiki/Fifty-move_rule
All of the basic checkmates can be accomplished in well under 50 moves. However, in the 20th century it was discovered that certain endgame positions are winnable but require more than 50 moves (without a capture or a pawn move). The rule was therefore changed to allow certain exceptions in which 100 moves were allowed with particular material combinations. However, winnable positions that required even more moves were later discovered, and in 1992, FIDE abolished all such exceptions and reinstated the strict 50-move rule.​

Regards,
Buzz

I know.

 

[mfb]

Chess is unsolvable with traditional computers

Claude Shannon noted that a true chess solution would require storing 10^120 moves. This gets into age of the universe type computational times and impossible storage requirements with any conceivable computer technology other than maybe a huge quantum computer

No, that number would have to be analyzed but not stored. The result of analysis so far could use one of the compact tablebase representations. I once worked out this would only require a number of bits similar to atoms in the moon to play any position perfectly.

You don't have to analyze 10¹²⁰ games. As an example: If both players move their knights out and back in again before starting a "normal" game this is a separate option in the game tree complexity of 10¹²⁰, but you go through the same state as other games. No need to analyze them separately once you reach a common state again. You only need to know the value of each position and you have to consider each move from this position, you don't need to analyze all games (=all possible combinations of moves in the whole game).

We had this topic on page 1 already.

 

[fluidistic]

I would say it is strongly solved for 7 or fewer pieces. The winner as well as best play for both sides, for any such position, can be generated ( even though the sequence itself is not stored).

I'm wondering why you say strongly solved when en passant and castling (which are allowed in some positions with 7 pieces or less) are ignored from the current tablebases. Could you please explain what you have in mind?

 

[PAllen]

I'm wondering why you say strongly solved when en passant and castling (which are allowed in some positions with 7 pieces or less) are ignored from the current tablebases. Could you please explain what you have in mind?

en passant is considered in current tablebases. It is true that castling is not considered because it is so rarely relevant for endgames and because the program using the tablebase can account for this with minimal extra compute time (it already knows if castling is allowed, and just needs to generate trees of when to do castling, with all other evaluation based on tablebase probes). It is also true that the method used for en passant would trivially handle castling, it has just been found to be uninteresting to do so.

So a more precise statement would be that current top engines using 7 piece tablebases can play any 7 piece position perfectly. And that existing tablebases technology could readily be extended to include castling directly. Or that existing tablebases directly strongly solve any 7 piece position in which castling is no longer possible.

 

[fluidistic]

Thank you PAllen for the information.

 

[BeedS]

White has the advantage of choosing the first offensive move, black has the advantage of choosing the first defensive move.
Seems quite balanced, am i missing something?

 

[mfb]

White has the advantage of choosing the first offensive move, black has the advantage of choosing the first defensive move.
Seems quite balanced, am i missing something?

Where do you see any balance in that?

 

[rcgldr]

Somewhat off topic - I don't know if AlphaZero's learning method affected the results of white versus black.

Alpha Zero and Stockfish
https://arxiv.org/pdf/1712.01815.pdf

The pdf file linked to still mentions AlphaZero versus Stockfish 8, at at time when Stockfish 9 was already released. Stockfish version 10 is now released. In addition, Stockfish opening and end game tables were removed in the earlier matches, and Stockfish was force to make moves at fixed rate, rather than allowing it to manage it's average number of moves per unit time. AlphaZero "trained" on a large number of processors and played on relatively expensive hardware. More on the earlier matches are mentioned in this article.

https://en.chessbase.com/post/alpha-zero-comparing-orang-utans-and-apples

StockFish's and other newer chess programs main improvement is move tree pruning allowing them to look 25 to 27 moves or more ahead, which is why they've exceeded the best human players some years ago.

SIde note - I have an old version of Deep Junior 8, but its interface is StockFish compatible, so I'm able to run StockFish, but I'm using the opening and endgame tables from whatever was available at the time of Deep Junior 8. Considering StockFish is free, it's a nice way to upgrade an existing chess program if it has a compatible interface.

 

[PAllen]

Somewhat off topic - I don't know if AlphaZero's learning method affected the results of white versus black.

The pdf file linked to still mentions AlphaZero versus Stockfish 8, at at time when Stockfish 9 was already released. Stockfish version 10 is now released. In addition, Stockfish opening and end game tables were removed in the earlier matches, and Stockfish was force to make moves at fixed rate, rather than allowing it to manage it's average number of moves per unit time. AlphaZero "trained" on a large number of processors and played on relatively expensive hardware. More on the earlier matches are mentioned in this article.

https://en.chessbase.com/post/alpha-zero-comparing-orang-utans-and-apples

StockFish's and other newer chess programs main improvement is move tree pruning allowing them to look 25 to 27 moves or more ahead, which is why they've exceeded the best human players some years ago.

Stockfish 8 was the latest version available when most of the research was done.

They did a shorter test on stockfish 9 towards the end of the work, wither results similar to stockfish 8.

In the earliest work they used default stockfish settings except for time control, and a poor choice of hash size. This does not mean no opening book, it means the default one rather than a designated tournament opening book

In the more recent matches,all of these weaknesses were rectified. They used tournament time controls, good program settings, as similar hardware as was possible, and endgame tablebases. They had runs with default opening behavior and also using best tournament book recommended by stockfish experts. Alphazero still won all scenarios.

The rating difference between stockfish 10 and 9 is rather small. It would be very interesting to chess players to a match with stockfish 10, but no interest really to deep mind. The research goal was never specifically to produce and maintain a strong computer chess program. Instead, it was to demonstrate achieving beyond human playing performance on multiple games, with no starting knowledge except the rules, by self play.

See my post #75 for additional info.

 

[PeroK]

White has the advantage of choosing the first offensive move, black has the advantage of choosing the first defensive move.
Seems quite balanced, am i missing something?

You're missing everything to do with the game of chess.

 

[phyzguy]

White has the advantage of choosing the first offensive move, black has the advantage of choosing the first defensive move.
Seems quite balanced, am i missing something?

How about we have a duel. We stand 10 feet apart. I shoot first, then you shoot. Completely balanced, right?

 

[BeedS]

How about we have a duel. We stand 10 feet apart. I shoot first, then you shoot. Completely balanced, right?

You can't win a game of chess in 1 move.

 

[PAllen]

You can't win a game of chess in 1 move.

Are you familiar with the chess term zugzwang? At present is simply unknown whether or not the starting position is a deep zugzwang for whoever moves first. Essentially no one thinks this is likely, but there is no evidence beyond experience from imperfect play that it is false. Your argument simply has no logical force whatsoever.

 

[BWV]

This is the latest 1000 games between AZ and SF8. There is no apparent advantage for the second move in Shogi or Go. but a clear difference between AZ's results playing as white vs black. I don't think it has been released, but the results of AZ's training games would be interesting in this regard.

It does seem reasonable to view these games as an approaching perfect play, much like if we trained AZ to play checkers it would get close to the solved game results

https://deepmind.com/blog/alphazero-shedding-new-light-grand-games-chess-shogi-and-go/

 

[PeroK]

You can't win a game of chess in 1 move.

Yes you can.

Fischer-Panno, Palma 1970:

1. c4

And black resigned.

 

[PAllen]

View attachment 238143

This is the latest 1000 games between AZ and SF8. There is no apparent advantage for the second move in Shogi or Go. but a clear difference between AZ's results playing as white vs black. I don't think it has been released, but the results of AZ's training games would be interesting in this regard.

It does seem reasonable to view these games as an approaching perfect play, much like if we trained AZ to play checkers it would get close to the solved game results

https://deepmind.com/blog/alphazero-shedding-new-light-grand-games-chess-shogi-and-go/

I agree this is evidence, but I don't take it as strongly as you do.

1) As I argue in my post #75, there is clear evidence AZ's play is not perfect, so you can't draw any firm conclusions about perfect play from it.
2) I actually think it is very unlikely that AZ training on checkers would replicate the solved play. Of course, unless someone does this, it is anybody's guess.

 

[BeedS]

Yes you can.

Fischer-Panno, Palma 1970:

1. c4

And black resigned.

A resignation is not a played win.

 

[PeroK]

A resignation is not a played win.

How many top level games end in checkmate? Almost none. Almost all wins are resignations, or a loss on time.

 

[BeedS]

Almost all wins are resignations, or a loss on time.

Resignations because they know they are going to lose, you don't know you are going to lose after white makes the first move.

 

[PAllen]

Resignations because they know they are going to lose, you don't know you are going to lose after white makes the first move.

You might if you are Panno playing Fischer in 1970,

 

[BeedS]

Resignations because they know they are going to lose, you don't know you are going to lose after white makes the first move.

With equally skilled players

 

[PeroK]

Resignations because they know they are going to lose, you don't know you are going to lose after white makes the first move.

That's immaterial. You can win a game of chess in one move. Fischer did. It's in the record books. A win is a win.

If you'd said you can't checkmate an opponent in one move, that would be different.

 

[Klystron]

How about we have a duel. We stand 10 feet apart. I shoot first, then you shoot. Completely balanced, right?

In fairness, this duel analogy does not include any defensive moves or strategy. Actual duels of this form supposedly proved "honor" of both duelists; a weird form of trust that the opponents deliberately miss their shots while standing upright and still as targets. Sheer idiocy IMO particularly if the duel was caused by one person calling the opponent untrustworthy. (See A. Hamilton vs. A. Burr.)

Dueling with swords, staffs, knives, or bare-handed allows defensive moves, tactics and defensive strategies. Physical strength, training, speed and stamina determine outcomes to a large extent, particularly expertise in fencing with swords and knives. According to some sources, this expert advantage led to the stupidity of pistol dueling as described. Little skill required to miss or stand still; just steady nerves.