∫ii Legal games

How many legal games of Chess are there?

Certainly there is a set consisting of all legal games and a possible position is one that can be reached one way or the other in a legal game.

The rules

We say two games are the same or equivalent, if when played separately as two distinct games the standard notation sheets are identical. Each move and all successions must be matched. It means that the notation of these two games are duplicate. Of course according to this definition if two differ in any one move at all they are considered different games.

Let us give more formal definitions for these positions and games: A "legal game" is one played by the rules of Chess and correctly annotated. A "possible position" is one that can be reached by the allowed moves, therefore in a legal game. A "feasable position" is any arrangement of the chessmen and empty squares on the board.

In principle the number of feasable positions can be counted as an exact number, although not evaluated as a digital decimal number. And, each possible position is a feasable one, so that the possible ones are contained in the set of feasable ones and therefore there has also to be finitely many possible positions. The set of legal games is also finite by similar reasoning:

The games are distinct. Also remember there are no infinitely long games because there is no game of chess with an infinite number of moves because repetition in a game is not allowed by the rules and ends in a draw. Indeed one could find an upper bound for these positive integers as a game of length of eventually a maximum number of moves.

As such we know there must be a maximum so there also has to be an end as a single fixed number of moves, as the longest chess game there can be. The actual numbers concerned are unthinkably enormous in fact to the point of meaningless, and counting will take forever after forever and ever.

I was suprised to realise that there are as many legal games as possible positions. In fact they are of exactly the same number even though we don't know what it is! To prove it in the end seems elementary I will give a proof in a seperate essay.

A challenge? It's not quite trivial.

Very big numbers

It would hardly be possible to devise some way of a succesfully counting all legal Chess games, meaning then an exact number. Of course the exercise will certainly be fruitless. However in such kinds of combinatorics problems it is often possible to find upper bounds.

Probably the only way to count the games exactly is to in effect physically go and write it out and count them with some basic branching kind of algorithm. Certainly one could invent a procedure.  

Theoretically we can ennumerate thus in some way or another all legal games. Of course this will most certainly be totally impractical and even when we have devised a method it would still be futile. It gets incredibly complicated terribly fast as the games progress and moves and the various allowed replies are made on the board. To actually go and try to count and exhaust these all will be not only stupid it is totally impractical indeed it is impossible.

The theory of counting sheep

In principle then it would be possible to calculate in some or another way the number of legal games, but indeed it is equal to the number of possible positions and at least we know it is also finite. A method might be straightforward but would still be impossible to implement. The feasable games on the other hand can be calculated exactly though and it's not terribly complicated but the number is much larger than anything here.

Further, of importance, one must realise that a given possible position can be visited in different games for example different routes could land again at the same position, and at the same time of course a legal game consists of many positions.

Such a problem in combinatorics is called non-polynomial. Even if there is a method it would be of little use. I find the idea of a foolproof procedure perplexing and not only for the immensity of all the imaginable possible positions. You would definitely need some kind of infinite computer, by the way I read they are now talking of experimental quantum computers.

Yes, suitable counting algorithms do exist and theoretically can be programmed on a computer, as you can think the show becomes extremely complicated and the machine cannot cope. The counting is impossible. The number remains unknown.