if so, this thread is for you!

how many different ways can a 68-team NCAA tournament play out?

3/18/2011 9:23:33 PM

eleventy billion

3/18/2011 9:25:40 PM

1

3/18/2011 9:26:09 PM

2^67

3/18/2011 9:26:27 PM

about tree fiddy

3/18/2011 9:32:38 PM

how many rubik's cube permutations are there?

how many possible games of chess are there?

(i know the answers)

(ibtwhatsasport)

3/18/2011 9:33:02 PM

Quote :

"how many rubik's cube permutations are there?"

There are exactly 43,252,003,274,489,856,000 permutations for the rubik's cube.

Quote :

"how many possible games of chess are there?"

Chess programs like Fritz are now routinely used by chess players. Their increasing strength has led to speculation that the game of chess might one day be solved - solved in the sense that we will be able to say that the initial position is a win for White in say 200 moves. Or a draw. Or a win for Black - after all, the shortest possible game ending in mate is a win for Black.

This question of the solvability of chess is intimately connected to the question of the number of possible different chess games. The Laws of Chess have as a consequence the fact that chess is a finite game provided that the three-fold repetition and fifty-move laws are always invoked: there is a distinct and finite number of different chess games. The numbers involved are very large by ordinary standards and we need a way of writing them so that they don’t take up too much space. We write:

10^10

to mean ten to the power 10, or one followed by ten zeroes – a biggish number. Bigger still is:

10^10^10

which is one followed by 10^10 zeroes, a seriously large number. It is numbers of this order which we must consider when looking at the number of possible chess games.

Could a computer of sufficient speed and storage capacity calculate and store them all so that the question of the solvability of chess could be answered? A "game" must here be defined as a legal sequence of moves ending in mate, stalemate or a draw by obligatory imposition of the three-fold repetition and fifty-move laws so that the result is beyond dispute. How many such games are there? Three different methods have been used to produce an answer.

The British mathematician J.E.Littlewood (not to be confused with the chess player of the same name)published "A Mathematician's Miscellany" (1953, later revised as "Littlewood's Miscellany,1986). Littlewood used the sledge-hammer approach. He calculated the number of possible arrangements, legal or not, of the pieces and the number of sequences of such arrangements to produce an upper bound of 10^10^70.5: However many games of chess there are, the number cannot be bigger than this. As part of his derivation Littlewood wrongly used 28 rather than 27 as the maximum number of moves for a queen but this has little effect on his estimate.

A second method uses the fact that chess is a finite game of no more than about 6000 moves and with no more than about 500 moves available in any position. Consider a simpler chess-like game where in every position there are just 10 moves available. Then after White has moved Black can reply to each of White’s 10 moves in 10 ways leading to 100 (10^2) possible games. After 2 moves (4 half-moves) there will be 10^4 games. More generally, for games of L moves and with M moves available in any position, the number of games will be 10^2LlogM. (For those who have forgotten their high school maths, this is 10 raised to the power 2 times L times the logarithm of M.) With L=6000 and M=500 this gives the maximum number of games as about10^10^5. This seems to have been the method used by G.H.Hardy. In his book "Ramanujan" (1940), speaking of large numbers he says "The number of protons in the universe is about 10^80. The number of possible games of chess is much larger, perhaps 10^10^50 (in any case a second-order exponential." This is a casual comment by Hardy and the 50 is presumably a misprint for 5. It is odd that Littlewood makes no reference to this earlier statement from his long-term friend and collaborator.

These large numbers do not belong to the world of practical chess.It is rare for the 50-move rule to be invoked once let alone twice or more so games of 100 moves are rare and games of anything like 1000 moves nonexistent in real life.

A third estimate was made by Claude Shannon in his ground-breaking paper "Programming a computer for playing chess" (1950). Shannon calculated the number of "typical games". He took L to be 40 and M 30 to obtain 10^118 or in his round figures 10^120. The critical weakness in this argument is the assumption that in any position there do exist 30 moves which will branch to to produce 40-move games. Shannon assumed this to be true. Littlewood had commented: "The problem of a not too hopelessly inadequate lower bound (even a moral certainty without full proof) seems not at all easy." Littlewood, one of the greatest mathematicians of the twentieth century, must have considered and rejected this crude argument as not even "morally certain" (whatever that means). I think chessplayers may be a little more accepting. They are well aware that during the course of a game most positions have many possible moves. If Fritz is set to analyse a game it seems to show about 30 possible moves in most positions from opening to endgame. The principal exception occurs when a king is in check when replies are often fewer than 10.

My moral certainty may not be as highly developed as Littlewood's so I am prepared to accept 10^100 as an indication of the number of games. Such a number is far in excess of the number of particles in our galaxy. If each game could be written on an atom there would be far too few atoms for completeness. If all the atoms in the other 10,000,000,000 galaxies were added there would still not be enough. With a number like 10^100 the extra atoms of a few billion more galaxies are neither here nor there.


Who wins a game of perfect chess?

"Perfect chess" is chess in which both players, foreseeing all possibilities, play only moves to produce a win or if that is not possible a draw or if even that is not possible, a loss after the most possible moves.

Shannon amusingly describes a game between two mental giants: "They sit down at the chessboard, draw the colours, and then survey the pieces for a moment. Then either

(1) Mr. A says, "I resign" or

(2) Mr. B says, "I resign" or

(3) Mr. A says, "I offer a draw," and Mr. B replies, "I accept."

This must be so.

Suppose White wins a particular game which began with say a3. Consider Black’s last unforced move. All other moves at that branch point must also lead to mate in as many moves or fewer or Black would have chosen one of them in preference. This argument applies at every branch point so all games starting with a3 must then be wins for White. Games starting with the other 19 possible moves are of little consequence. They could all be wins for the unfortunate Black, who would never get to play them.

Black’s prospects are therefore rather gloomier: to win any game it is necessary that every game be a win for Black.

And if all perfect games are drawn then our mortal wins and losses are mere aberrations caused by bad play.


Who wins in a game of chess between two perfect players? We may never know. Chess appears to be effectively an infinite game with no solution. The nature of the universe and not our limited intellect may be the ultimate determinant of our knowledge of chess. Vladimir Nabokov, novelist and chess-writer, touches on this idea in "The Defence":

[Edited on March 18, 2011 at 10:48 PM. Reason : .]

3/18/2011 10:46:33 PM

might have found a new outdoor sales

3/18/2011 11:57:01 PM

JC morri

3/18/2011 11:59:16 PM

i posted this in the espn challenge thread in sports talk:

Quote :

"if you filled out 1 bracket per second for every possible outcome, it would take 63.5 earth lifetimes to fill them all out"

and that's not even counting play-in games

3/19/2011 12:25:04 AM

Play in games are lame anyway

3/19/2011 12:29:13 AM

play-in games are great

i really enjoyed the 10th round matchups today

3/19/2011 12:32:31 AM

I mean...darkone's answer is correct.

3/19/2011 2:27:45 AM

let's see...this is quite doable.
Let C_n be the number of ways a 2^n team tournament can play out. If we have a 2^n+1 team tournament, then, there are 2^n+1 ways the first round can pan out, and after the first round we are left with a 2^n team tournament, which by hypothesis can happen in C_n ways. Therefore
C_n+1 = (2^n+1)*C_n.

We have C_0=1, so it looks like in general C_n= 2^(sum i=1...n)=2^n(n+1)/2

So a 64-team tournament can, it appears, happen in 2^(32*65) ways. (I have ignored the 4 extra teams, since they mess up the symmetry of the calculation.

I have probably screwed this up somewhere, though.

3/19/2011 3:49:43 PM

I mean if you go round by round it's:
2^32 * 2^16 * 2^8 * 2^4 * 2^2 * 2^1 = 2^63, discounting play-in games.

3/19/2011 5:36:31 PM

dammit, I took my sum over values 2^i rather than just i. you're absolutely right.

3/19/2011 5:43:33 PM

2⁶³ is how i got the earth lifetimes number a bunch of posts up

3/19/2011 6:01:10 PM

3/19/2011 6:19:20 PM

2^63 = 9,223,372,036,854,775,808

If every person in America filled one out (300 million people),
the probability of someone winning is:

300,000,000
----------- = .00000000003253
2^63

3/19/2011 7:42:29 PM

Don't neglect the play-in games.

3/24/2011 7:28:45 PM

dont forget that this thread sucks

3/25/2011 7:53:05 AM

Quote :

"outdoor sales"

3/25/2011 9:03:08 AM