Chess and checkmate

1. Jun 5, 2012

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

2. Jun 5, 2012

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.

3. Jun 5, 2012

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.

4. Jun 5, 2012

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

5. Jun 5, 2012

zoobyshoe

Are you asking how many possible chess games there are?

6. Jun 5, 2012

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.

7. Jun 5, 2012

zoobyshoe

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

8. Jun 5, 2012

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.

9. Jun 5, 2012

uperkurk

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

10. Jun 5, 2012

Jack21222

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.

11. Jun 5, 2012

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.

12. Jun 5, 2012

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.

13. Jun 5, 2012

Jack21222

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.

14. Jun 5, 2012

ThomasT

What if the universe is infinite?

15. Jun 5, 2012

DaveC426913

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

16. Jun 5, 2012

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...

17. Jun 5, 2012

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

18. Jun 5, 2012

DaveC426913

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.

19. Jun 5, 2012

Jack21222

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.

20. Jun 6, 2012

fluidistic

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").
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.