# Is chess infinite?

• 11 months ago · Quote · #61

Okay, I'll venture into the waters...

The number of chess positions is clearly finite.  But I claim there are continuumly many chess games.  (NB: This is stronger than saying simply there are uncountably many games.  It actually says there is a 1-1 correspondence between all games and the set of all real numbers.)

First, there are at most continuumly many games.  Label the finite number of positions n_1, n_2, ..., n_k.  Since every game is a countable (finite or countably infinite) sequence of positions, we can represent every game (finite or infinite number of moves) as a countably infinite sequence from the set {n_0, n_1, n_2, ..., n_k} where n_0 is a placeholder inserted after the end of any finite-move game.  Since this map is injective (distinct games map to distinct sequences) and the number of countably infinite sequences of elements of this set is precisely (k+1)^(aleph-naught) = c (cardinality of the continuum), there are at most continuumly many games.

On the other hand, there are at least continuumly many games.  Consider all games that start with some fixed initial moves leading to the position of white Q on a1, white K on h1, and black K on h5, with white to move.  (The specific initial moves don't matter, just fix some choice of moves.)  Now, imagine the white K moving around the circle of squares h1, h2, g2, and g1.  And consider the black K moving around the circle of squares h5, h6, g6, and g5.  Both kings only move either to their immediate clockwise or counter-clockwise square.  Now consider the following map from the open unit interval into the space of all games with this initial move sequence: first, consider the number's infinite binary representation (for definiteness, if there are the 2 representations, take the one ending in all 0's).  This gives a countably infinite sequence of 0's and 1's.  Let 0 correspond to "clockwise" and 1 correspond to "counterclockwise".  For each digit, move white, and then black, in the direction corresponding to that digit.  Since distinct numbers in the open unit interval map to distinct games, this map is also injective, so there are at least continuumly many games.

Now apply Schroeder–Bernstein.

• 11 months ago · Quote · #62
piphilologist wrote:
pipinghotsos wrote:

However there is one infinite variable - the number of moves. Even taking in to account the 50 move rule, you could keep playing just by checking now and then, which resets the count. Say you were playing a game where both players were trying to keep playing forever. Can you think of ways to play that can keep going, round and round? I can, easily. Therefore the number of games is infinite.

Right solution, wrong method. Checking does not reset the count, you have to move a pawn or make a capture to reset the 50-move-rule count.

However the 50-move-rule is not automatic, it has to be claimed by one of the players so if neither claims then they can keep repeating. Therefore the number if possible games is infinite.

However the number of possible positions is finite, although of course very large.

I stand corrected. I was under the impression checking was also under the classification of resetting the 50-move count, thank you for correcting that.

• 11 months ago · Quote · #63
sapientdust wrote:

There is an argument for finite and an argument for infinite, both based on the fifty-move rule.

If players claim the fifty-move rule when possible, then chess is finite, because that ensures that there is a maximum length of game possible, which ensures a finite number of possible games.

However, the draw is not automatic. It has to be correctly claimed by a player, and it is not mandatory to claim the draw. Therefore, if the players never claimed a draw, a game could be of arbitrary length, and thus chess is infinite (even if almost all of those infinitely many games are utterly boring games that real people would almost certainly have agreed were draws).

So, while I guess it's technically infinite, the subset of games that are interesting is certainly finite, but it's still of such a magnitude that it's beyond the mental capacity of any person to thoroughly master this finite game.

This seems like the most believable answer to me.

However... if one wanted to be really pedantic, they could argue that, even if one doesn't claim a draw by 50 moves/repetition, the number of moves possible is still limited by the life of the players. It is certainly a rule in tournament chess at least that the 2 players that start a game must be the ones making the moves. So theoretically, if one of the players dies, the game is over. Thus, the game can last only as long as the players live (even if the death is by old age, this is a finite number of moves). With that in mind, I would argue that the number of unique chess games possible is still finite.

• 11 months ago · Quote · #64
-kenpo- wrote:
I'm sure it's possible to build a cyborg or "enhance" a human being so that it is able serve a tennis ball at 500 miles per hour something absurd. why should this have any bearing on tennis played between humans composed of muscles and bones? I don't understand why you are apparently concerned with it really.

Maybe just because within my memory people were better at chess than machines, period, and with that came an assumption (by some anyway) that human thought was qualitatively different than computer processing. Then computing machines got tiny and incredibly powerful and probably radically changed the way people trained for tournaments. I doubt we're too far from engineering either silicone-based "external" memory for our brains, or genetic innovations that will enhance biological CPUs.

The infinity question is sort of all balled up in metaphysics (any maybe regular physics) because my imperfect understanding is that what humans perceive as "infinite" is perhaps just very, very large. Like "space," whatever that is.

BTW you were right about the chess strength of ordinary PC chess programs. My pre-packaged Mac software was not running up to speed. I was getting "better" suspiciously fast, but tried a properly functioning program today and was humbled.

A question, my new machine actually takes time (more than milliseconds, I mean) to make its moves. Is the program really "thinking" all this time, or are the pauses for effect? It is a Mac Book Pro running with a pre-installed program called "Chess." It's pretty basic, but "powerful" relative to early machines, I'm sure.

• 11 months ago · Quote · #65

Well, even if chess is solved, even then it would be interesting as no one will be able to learn and remember about ALL the positions of the chess borad

• 11 months ago · Quote · #66

I'm going to retract my statement that there are more Chess games than real numbers. I realized last night after posting that showing a one-to-one relationship with Chess games left over is not sufficient to prove that the cardinality is greater.

• 11 months ago · Quote · #67
John_Doe18 wrote:

Well, even if chess is solved, even then it would be interesting as no one will be able to learn and remember about ALL the positions of the chess borad

Even if particular openings were shown to be losing with best play, I expect people would still play them for that very reason - to show that they can still win in a handicapped line. A bit like the King's Gambit then (allegedly)!

• 11 months ago · Quote · #68
ironic_begar wrote:

I'm going to retract my statement that there are more Chess games than real numbers. I realized last night after posting that showing a one-to-one relationship with Chess games left over is not sufficient to prove that the cardinality is greater.

lol this was a mind-bender in math class. "How can the cardinality of the integers be the same as the cardinality of the positive integers?" O.O

• 11 months ago · Quote · #69
ironic_begar wrote:

I'm going to retract my statement that there are more Chess games than real numbers. I realized last night after posting that showing a one-to-one relationship with Chess games left over is not sufficient to prove that the cardinality is greater.

I didn't notice that you said "greater cardinality" than real numbers, and I interpreted it as greater than the natural numbers or at least equal to the real numbers, which was what you were originally trying to prove. That proof still seems valid, so the number of chess games is at least uncountably infinite (cardinality equal to or greater than that of the real numbers).

• 11 months ago · Quote · #70

You could argue that it is infinite, on the grounds that the 50-move rule and the 3-fold-repetition rule do not kick in automatically, they have to be claimed by one of the players.

• 11 months ago · Quote · #71

sapientdust said: "That proof still seems valid, so the number of chess games is at least uncountably infinite (cardinality equal to or greater than that of the real numbers)."

Saying that a set is uncountable is not the same thing as saying its cardinality is equal to or greater than that of the real numbers.  The equivalence of these two properties (that there are no uncountable sets with cardinality strictly less than that of the real numbers) is precisely the continuum hypothesis.  So, saying that a set has at least continuumly many elements (cardinality at least that of the real numbers) is a stronger statement than saying it's uncountable, because every set with continuumly many elements is uncountable, regardless of whether the continuum hypothesis holds, but the converse is only true assuming the continuum hypothesis.

Also, saying there are precisely continuumly many games is stronger than saying there are at least continuumly many games.  The latter requires, as I showed above, proving you can inject the set of all games into a set of cardinality the continuum.

• 11 months ago · Quote · #72

Even if two games would be identical with regards to the moves they could still be quite different, and even have different results. One player could lose on time after having made exactly the same moves as in another game where the players agreed to draw in the same position. Not that this ever will be particularly common, maybe it has never happened.

Then there are many variations that end with more or less forced repetitions in the opening. Two players happy with a draw could blitz it out and go home, while another player that needs to win blunders into the line without knowing about it, and sits for an hour trying to find something better before accepting the draw. In one way the games would be identical, but in another way they would be slightly different.