Something I was thinking about doing in the shower.

Okay. I enjoy Computer Science problems. A lot. A few days ago i thought about making a game of chess in Java. This idea sort of trailed off and I didn't really care anymore. I was in the shower today and a question popped up in my mind. How many possible unique games of chess can be played? Now there is one problem with this, I'm not sure if I can brute force the problem. I was thinking of creating a data structure to store every possible outcome (every possible board would take up roughly 113 bytes each).This would involve taking the default board, assessing every possible move, creating separate board saves for each, and using those board saves to repeat the process until a certain number of pieces are left or a king is in checkmate. I figure if two kings and one specialized piece are left, the game should be considered complete. However, I haven't take the time to calculate how many possible boards there are (I'm assuming quite a few) and I have no idea if this problem can be brute forced (due to the process never completing). I know NAMKCOR probably knows how to determine how long a process like this would take and I'll be thinking about it in more detail later on. Anyways, just putting this out there. Tell me what you think.

the problem is how very many possible combinations of piece positions that can be accomplished in a single game of chess, much less over every game in existence.  Not to mention when pieces get taken away, or when Queens are added to the board.

I have no idea how long it'd take, however I do know that brute forcing that would take an absolutely monumental amount of time and computing power, and that's with even the most efficient code.

Let's take an example, you have a fully set board.
First turn, you have 8 pawns that can move either 1 or 2 spaces, and 2 knights, that can each hit 2 positions, making the total number of outcomes 20.  So you now have 20 boards.  Now each of those 20 boards would have an additional 20 boards, from the same initial setup of Black, which makes the 2nd turn give you 20*20, or 400 unique combinations.  It only gets worse from there as you get to the pieces that can move multiple spaces, and you have to add one scenario for each and every space they could move.  A single queen alone could spawn 20 board configurations.

TL;DR - don't try to program this with Brute Force, I have no idea of any way to do it off the top of my head, and I'll probably be thinking about it for weeks now, but unless you don't want your computer to Crash due to running out of RAM, you'd better leave this one be.

Yeah I've been thinking about it and haven't been able to come up with much.  I have a bit of an idea but I can't put it into actual workable words/pseudocode yet.

Building the next Deep Blue are we?

That would be much more reasonable and easy, considering it'd only have to think ahead up to 5 or 6 moves, rather than entire games.

A quick Google leads to the Wolfram page with estimates: http://mathworld.wolfram.com/Chess.html .

4th Paragraph

Hardy (1999, p. 17) estimated the number of possible games of chess as 10^(10^(50)). The number of possible games of 40 moves or less P(40) is approximately 10^(40) (Beeler et al. 1972), a number arrived at by estimating the number of pawn positions (in the no-captures situation, this is 15^8), multiplying by the possible positions for all pieces, then dividing by two for each of the (rook, knight) pairs that are interchangeable, and dividing by two for each pair of bishops (since half the positions will have the bishops on the same color squares). (However, note that there are more positions with one or two captures, since the pawns can then switch columns; Schroeppel 1996.) Shannon (1950) gave the estimate

Perhaps Google gave us this answer, but where's the adventure?

This question of the number of games a single board can spawn seems daunting, and would require countless man hours and processing power... Perhaps you can do it "Brute Force" one or two steps at a time... (or a few hundred should you be pressed for time)... Rather than putting all the data in at once, work in pieces, figuring out each part in turn, and then combining it all together (god, I sound like a damn dumbass... This is probably obvious...)

Well, enough wasting time from me...

I would suggest taking a course in Discrete Mathematics. Discrete deals heavily with combinatorial problems much like the original question. This question is interesting however because their can be infinite games in which a winner is never declared. I assume that's why Hardy found it necessary to limit the amount of moves to 40.

The link also raises another interesting question:

1. How many pieces of a given type can be placed on a chessboard without any two attacking?

Google gives an estimate, Zombie wanted the exact answer.  Given that Chess has a limited number of Pieces, and places they can move, I'd think that there -would- be a definite answer (given that ties also counted as the end of a game) though it'd be a rather high number.

This is an extreme problem. There alot of possible layouts on the board. Also, given any particular board layout, there could be many different games that could have led to that setup. So by asking "how many different chess games are there?" you are gonna have to make a choice:

1) Accept that there are an infinite number of ways to play a game of chess.
This is a fact. After the opening moves and before either player has lost all of his pieces, the players could get into one of any vast number of move cycles. Accepting the infinity solution is not very interesting, though, so you could alter your problem slightly to try and make it countable. Which brings on the next choice.

2) Ask how many games can be played where, in each game, every board setup is unique.
This essentially means eliminating move cycles and backtracking moves from the problem. Now you have a problem that can be solved with some (probably complex) recursive algorithm. Go with something like your original idea, but put in checks to make sure that each new configuration hasn't already been seen during this game. So essentially making sure that no board layout appears more than once on any branch of the solution tree. This algorithm must exist, but I don't know if it is practical. Might be that this problem is just too big for your home computer.

1) Accept that there are an infinite number of ways to play a game of chess.
This is a fact.

This is untrue and would only be true if pieces weren't limited by specific movement types and board size.  Each peace has, in fact, a finite number of states.

2) Ask how many games can be played where, in each game, every board setup is unique.
This essentially means eliminating move cycles and backtracking moves from the problem. Now you have a problem that can be solved with some (probably complex) recursive algorithm. Go with something like your original idea, but put in checks to make sure that each new configuration hasn't already been seen during this game. So essentially making sure that no board layout appears more than once on any branch of the solution tree. This algorithm must exist, but I don't know if it is practical. Might be that this problem is just too big for your home computer.

The question is how many unique -games- of chess could be played, not how many unique board configurations there are.  This means that the only thing that needs to change to make it a unique game is a single move.  Eliminating previously used boards isn't an option because of there being many options to change the game from that point.

1) Accept that there are an infinite number of ways to play a game of chess.
This is a fact.

This is untrue and would only be true if pieces weren't limited by specific movement types and board size.  Each peace has, in fact, a finite number of states.

There are a finite number of board configurations, that is true. But there are an infinite number of games. It is perfectly legal in a Chess game for the board to have some configuration, and then for the game to return to that configuration after a few rounds of moves without achieving a stalemate. Perhaps I wasn't clear.

2) Ask how many games can be played where, in each game, every board setup is unique.
This essentially means eliminating move cycles and backtracking moves from the problem. Now you have a problem that can be solved with some (probably complex) recursive algorithm. Go with something like your original idea, but put in checks to make sure that each new configuration hasn't already been seen during this game. So essentially making sure that no board layout appears more than once on any branch of the solution tree. This algorithm must exist, but I don't know if it is practical. Might be that this problem is just too big for your home computer.

The question is how many unique -games- of chess could be played, not how many unique board configurations there are.  This means that the only thing that needs to change to make it a unique game is a single move.  Eliminating previously used boards isn't an option because of there being many options to change the game from that point.

You don't need to eliminate every non-unique board configuration, just every non-unique board configuration appearing in the same branch of the solution tree. As the most basic example I can think of, consider the initial configuration of the board. Now say white moves out a knight, black also moves out a knight, white puts his knight back where it started, black puts his knight back where it started... then our board is back to the initial setup and we have effectively achieved nothing in the context of the game. Any algorithm that considers all possible cases will run through this scenario and many others like it, i.e. the program will not terminate.

So the algorithm should ignore cases where the board has returned to a state previously seen in that same game. It doesn't mean that the algorithm should ignore states that have been seen before altogether. In this particular example the algorithm should ignore the case of the 4th move, black returning his knight, because we have already seen this state within this game. While this does modify the initial question slightly, I'm not convinced that any algorithm exists for the question posed by the OP.

In my earlier post, any branch of solution tree == any particular game of chess.

well... After reading Zombie's original question, it seems that he indeed might want to make his equation to calculate the possible outcomes, rather than the possible games...

Not only does this make the problem much easier to solve, but it eliminates the whole "but the state is the same" arguement that just took place. However, the wording is a bit... Difficult, so I may be mistaken.

But, in the long run, I assume that all that needs to be done is find all the theorhetically possible end-game configurations, as well as finding which of those configurations is actually possible to do.

However, because you can choose whether or not you capture an endangered piece, this problem would take much longer than, say, calculating the most possible outcomes in a game of "give away" (a variation of checkers where the point is to lose all of your checkers to your opponent)

possible outcomes: white wins, black wins, draw
3.

on a more serious note, if that's what he was thinking, it'd likely be a lot smaller, though still a large number, I took it to mean how many possible unique games overall.

I'm guessing we also have to count when the king wants to castle, queen-side castling, etc. Actually, I also think that it would be possible to have an infinite amount of playable. One could move his king back and forth, while the other person was moving his back and forth, making infinite moves. A different game can just mean one move different correct? Then there should be an infinite amount of games. But whether the player is actually dumb enough to keep on repeating moves, that's a different story.

I'm guessing we also have to count when the king wants to castle, queen-side castling, etc. Actually, I also think that it would be possible to have an infinite amount of playable. One could move his king back and forth, while the other person was moving his back and forth, making infinite moves. A different game can just mean one move different correct? Then there should be an infinite amount of games. But whether the player is actually dumb enough to keep on repeating moves, that's a different story.

the question would define a move in a game of chess as a move that pushes the game forward, to remove that possibility.

I wonder why no one has looked at the rules for when a draw occurs.
If you had you would have realized that a chess of games is guaranteed to be finite due to the 3-fold repetition rule and the 50-moves rules.
Refer to World Chess Federation's article 5 on the completion of the game. Look also at article 9 which elaborates on draws.

On a unrelated note I did not know about the Anti Doping Regulations in chess XD

I dunno how many possible unique games there are. It seems like a very hard combinatorial problem to solve.
There obviously are many more unique games than there are unique board configurations. In fact I believe there are many many more, like millions or billions times more.
You can store the possible board configurations with transitions between them marking possible moves. Yes, I am talking about a directed graph structure where states are board configurations and transitions are possible moves. You can perfectly fine code all possible moves in such a structure which definitely will be much smaller than a game tree describing all the possible moves. It will not be entirely trivial to roll out paths since you have to take care that the rules are fulfilled. You can for example only take a cycle x amount of times.

You can say that you use less space at the price of speed.


More on the practical side I can tell you that no top Chess AI use pattern recognition.
I dunno why the minimax game tree based approaches worked better.
That said Alpha-Beta pruning is a search algorithm which improves on minimax so I bet that's what's used in practice.
I have also heard about using the null-move heuristic is often used though I don't know what it entails.

I hope I have given you some more to think about with my limited knowledge on computer chess ^^
*hugs*

yeah I was actually going to mention that about draws.

9.3
   

The game is drawn, upon a correct claim by the player having the move, if:
     

a.
   

he writes his move on his scoresheet and declares to the arbiter his intention to make this move, which shall result in thelast50 moves having been made by each player without the movement of any pawn and without any capture, or
     

b.
   

the last 50 consecutive moves have been made by each playerwithout the movement of any pawn and without any capture.

that removes the possibility for an infinite number of chess games.
Sure it's still a large amount, but we're anticipating that to begin with.