Is chess infinite?

I thought he said something once like chess was a waste of mental effort?

Edit: found this - http://www.chess.com/forum/view/chess-players/who-is-more-clever-kasparov-or-einstein

Okay, with two assumptions, I can show that the number of Chess games is uncountably infinite (obviously without the 50 move rule and 3 fold repitition). Assumption one: the number of Chess games is at least countably infinite. Assumption two: there are Chess games of infinite length with no forced moves. I think the second one is obvious: two kings on a board with another piece.

Anyway, get any countably infinite list of Chess games: g1, g2, g3, ...

Start with a game g', where the position after the first ply is different than the position after the first ply of g1, the position after the second ply of g' is different than the position after the second ply of g2, the position after the third ply of g' is different than the position after the third ply of g3, and so on. As long as g' has no forced moves, this is always possible. Since g' is different on at least one ply from every game on your countably infinite list, the set of all games is uncountably infinite.

Something else is interesting.

there are computers for the game of bridge and the game of duplicate bridge while very hard to play at world class level--is far less complicated than chess and the computers for bridge only play at the equivalent of what we call class A level in chess!

I disagree that there are games of infinite length; sure they could potentially go through a large number of moves but its a fixed matrix with limited maneuvers and limited piece types.  Infinity is boundless.  Although we could be here till the universe dies a heat death or whatever its called, trying to count them, it still must be a finite number of games.

The problem with your proof is that the 50 move rule and 3-fold repetition are parts of the laws of chess. Playing without those rules is playing a variant of chess that is remarkably similar, but is not chess as in the game of chess many of those games would end prior to being able to deviate from the previous g'.

Chess programmers are more proficient than bridge programmers?

I am certain there's only a finite number of interesting games (but still lots of 'em).

No. Chess is not infinite.
http://home.telfort.nl/jaheruddin/f/Chess_will_be_solved.pdf

But it is still solvable. And given the past we have every right to assume that Moore's law will hold.

Don't you need to show that such a g' can be constructed from the countably infinite list of all possible games? The list of g1, g2, ... contains many games with positions that are forced, so g' wouldn't be able to differ from those games at those particular moves that are forced, which means that you haven't shown that g' differs from every other game in at least one position.

You can make an infinity of numbers with just 10 digits, Chess is far less restricted than that. And it isn't really ignoring the 50 move or 3 fold repetition rules. Those have to be claimed. It's just assumed that the players don't claim them.

In Cantor's diagonalization argument, you can change any digit of the list of real numbers and you still end up with another real number. That isn't the case here, because some of the numbers (games) have digits (positions) that can't be changed to anything else, because the next move is forced. Thus the diagonalization argument doesn't work (at least not in the current formulation).

That's an overly restrictive view of Cantor's diagonalization argument, sapientdust. You can view it as changing a digit in the number on the list, or adding a new digit to the number not on the list (that doesn't match the corresponding digit on the list). I'm doing the second one.

The first one doesn't even make sense in the Chess situation. You would have to change a move in the game on the list that reached a legal position in both the game on the list and the game not on the list.

I'm adding a move to the game not on the list. That game (g') is specified not to have any forced moves. So you always have a choice of positions on ply n, so that it doesn't match the position of ply n of game gn. That way you only need to have one game that has no forced moves, not an infinite number of them.

On the other hand I think you could have an infinite number of them. Say you have a position P. Come up with 10 different cycles of moves that return to position P. Those ten cycles correspond to the ten numeric digits 0-9. You can then combine those cycles to map games to different numbers: the eighth cycle followed by the tenth cycle followed by the first cycle would map to 801. Come to think of it, you can then map a unique chess game to every real number, and you've got an uncountably infinte set. And since all of those games start from a single position, the set of legal Chess games has a cardinality greater than that of the real numbers.

You are assuming part of what is to be proved by specifying that g' doesn't contain any forced moves. That requires justification, because it's not clear that it's possible to formulate such a g' containing no forced moves. I grant though that if you could show that, then the proof would work.

I don't see any problems with your new argument though that maps the 10 cycles to the base-10 digits.

I find this discussion more interesting than most on chess.com, so that's value enough for me.

We're close (see Stockfish, for example). Sooner or later some programmers will actually team up to get it done.

Hmm... but it seems intuitive that when you ignore repetition that the number of unique games is infinite.

However I like the argument showing it exceeds the number of real numbers... and not having gone far in math I'd never heard of Cantor's argument which I looked up and found interesting, thanks.

Do you know who was the mathematician or did it just say "a mathematician"?

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.

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.