How many ways are there to checkmate someone in chess?

[uperkurk]

How many possible ways, in any direction, using any number of peices are there to checkmate someone in chess?

I'd have a guess and say at least a couple of hundred thousand different ways

 

[DaveC426913]

Define "ways to checkmate". Do you mean the number of ways to lead up to a checkmate, or do you mean simply the very last static state of the board in which the king cannot make a move? Do you count pieces on the board that do not contribute directly to the checkmate?

The first is virtually uncountable. The next is lower but still very large.

 

[Jimmy Snyder]

Well, there's suddenly, and then of course decisively. Cleverly has to be my favorite.The ones I hate is when you're doing really well and then the other guy sneak attacks you with his knight. Those pieces move really funny and it's hard to defend against them.

 

[uperkurk]

I mean the build ups to checkmate. So the first checkmate is the one that can be achieved in 2 or 3 moves I think, so that's one way, etc etc the number must be absolutely huge come to think of it

 

[zoobyshoe]

I mean the build ups to checkmate. So the first checkmate is the one that can be achieved in 2 or 3 moves I think, so that's one way, etc etc the number must be absolutely huge come to think of it

Are you asking how many possible chess games there are?

 

[uperkurk]

Kind of... I guess I am actually because each game can only be won via a checkmate so yeah, how many different possible chess games are there that end in a checkmate.

 

[zoobyshoe]

Kind of... I guess I am actually because each game can only be won via a checkmate so yeah, how many different possible chess games are there that end in a checkmate.

I don't even understand this article, but it's clearly the sort of thing you're looking for:

http://en.wikipedia.org/wiki/Shannon_number

 

[DavidHume]

There are 20 initial moves (8 pawns x 2 moves/pawn + 2 knights x 2 moves/knight), and 20 responses. Assuming you have about 20 possible moves at each point and a game is 40 moves long, this gives us 20^40 = 1e52 possible games, so that's a rough starting point.

Of course you may have fewer than 20 possible moves at any given point but a game might go for more than 40 moves, so this approximation is as good as any.

 

[uperkurk]

So many numbers so which is it? lol 2 to the power 255 is an astronomical number...

 

[Jack21222]

So many numbers so which is it? lol 2 to the power 255 is an astronomical number...

There are far more possible chess games than there are elementary particles in the observable universe.

This is a far cry from "a couple hundred thousand."

And if you think that's a lot, consider how many possible ways there are to arrange a 52 card deck. Every time you shuffle a deck of cards, that particular configuration has probably never happened before in human history, and will probably never happen again.

 

[uperkurk]

Well the card deck is much less than the number of chess games... 52! = 10 to the power 66. Shannons number with the chess example says 10 to the power 76.

 

[DavidHume]

Well, taking the upper bound of 2^155 from the Shannon citation on Wikipedia, if you had a million computers calculating 2.4 billion moves per second, it would only take about an Avogadro's number of years to figure out all the games.

 

[Jack21222]

Well the card deck is much less than the number of chess games... 52! = 10 to the power 66. Shannons number with the chess example says 10 to the power 76.

I've never heard of the "Shannon's number," but I have heard of the 20^40 number. That's what I was going by.

 

[ThomasT]

There are far more possible chess games than there are elementary particles in the observable universe.

What if the universe is infinite?

 

[DaveC426913]

What if the universe is infinite?

It doesn't matter. The observable universe (as Jack referenced) is not.

 

[AlephZero]

Computer programs are slowly creeping up on this, working backwards from actual checkmate positions to see how to achieve them or avoid them. So far there are complete databases for 6 or fewer pieces on the board. Even within that limit, the longest known game needs more than 500 moves to force a win (ignoring the chess rule that more than 50 moves without a piece being captured or a pawn being moved is a draw). Google for chess tablebases.

Extending this to a full analysis of 7 pieces in a practical timescale is probably beyond the current capability of computer systems. Getting to the full starting position with 32 pieces in play may take some time...

 

[uperkurk]

Well the deeper blue chess super computer can permutate 200 million moves a second, but how many seconds are needed to calculate all the moves if the number is indeed 10 to the power 76

 

[DaveC426913]

Well the deeper blue chess super computer can permutate 200 million moves a second, but how many seconds are needed to calculate all the moves if the number is indeed 10 to the power 76

I do believe it is an outrageously long time, if not longer than the age of the universe.

For just this reason, the computers are designed to eliminate many unlikely paths without going all the way down them.

 

[Jack21222]

Well the deeper blue chess super computer can permutate 200 million moves a second, but how many seconds are needed to calculate all the moves if the number is indeed 10 to the power 76

This is an easy calculation that I'd urge you to attempt yourself. I think Dave's comment of "...longer than the age of the universe" is a gross understatement. Double check my calculation.

 

[fluidistic]

There are 20 initial moves (8 pawns x 2 moves/pawn + 2 knights x 2 moves/knight), and 20 responses. Assuming you have about 20 possible moves at each point and a game is 40 moves long, this gives us 20^40 = 1e52 possible games, so that's a rough starting point.

Of course you may have fewer than 20 possible moves at any given point but a game might go for more than 40 moves, so this approximation is as good as any.

Basically yes, though an average chess game is longer than the 40 "moves" you are considering. A chess move consist of 2 half moves (i.e. 1 move in chess is w to play and b to play and if the average length of a chess game is close to 40 chess moves, then it's 80 of the moves you seem to consider by saying that there is approximately "20 possible moves at each point").

Computer programs are slowly creeping up on this, working backwards from actual checkmate positions to see how to achieve them or avoid them. So far there are complete databases for 6 or fewer pieces on the board. Even within that limit, the longest known game needs more than 500 moves to force a win (ignoring the chess rule that more than 50 moves without a piece being captured or a pawn being moved is a draw). Google for chess tablebases.

Extending this to a full analysis of 7 pieces in a practical timescale is probably beyond the current capability of computer systems. Getting to the full starting position with 32 pieces in play may take some time...

I had read in wikipedia that the complete 7 pieces tablebases might be done for 2015. I don't remember the number of terabythes but it was huge. For the 8 pieces I don't even know if the data can realistically be stored on Earth, etc.
Also the endgame tablebases have a flaw in that they don't consider the possibility of castling. This isn't so bad when there are few pieces though.

 

[zoobyshoe]

I had read in wikipedia that the complete 7 pieces tablebases might be done for 2015. I don't remember the number of terabythes but it was huge. For the 8 pieces I don't even know if the data can realistically be stored on Earth, etc.

How can I phrase this as a mind boggling piece of trivia to post on facebook? "There are so many possible games of chess that mathematicians don't think there is room on Earth to digitally store all the permutations." ?

 

[ThomasT]

It doesn't matter. The observable universe (as Jack referenced) is not.

Thanks Dave, I overlooked that.