Jump to content

Talk:Shannon number

Page contents not supported in other languages.
From Wikipedia, the free encyclopedia

Number of Board Positions

[edit]

Hmmm... well, it occured to me that the total number of posible board positions couldn't be more than 64!/32!... that is, the total number of ways of arranging 32 distinguishable pieces on a board of 64 spaces. But I didn't consider the affect of promoting pawns, and all the various choices that might be available in that case, and the extra board positions that this would create... still though, if promoting pawns was disallowed, it would limit the positions to 64!/32! (as well as noticably changing the dynamics of the game)... just a curious thought. (The Swami 08:36, 17 August 2005 (UTC))[reply]

64! / 32! = 482219923991114978843459072919892677776312893440000000, but that's not what Shannon's number is. Soo 16:01, 26 September 2005 (UTC)[reply]
I know it's not, I was just posting some musings on the derivation of said number... but here's a few more while I'm thinking of it... I think the total number of board positions could not excede 64!/32! ^ 6^32; this would be the total thirty two pieces maximum on the board, each of which can be one of six types. The game-tree complexity may be larger than this, I'm just saying that the total number of board positions could not (I believe) excede this. (The Swami 02:53, 28 September 2005 (UTC))[reply]

Shannon Number

[edit]

There are several possible problems with this page. First, "One novemtriginillion is known as the Shannon number." It seems like the Shannon Number is actually 90040, which is 1.478...×10118, for which 10120 is a poor approximation. If 90040 is indeed the Shannon Number, then that doesn't really belong in this article. Also, for the number of atoms in the universe: can that figure really be estimated with so much precision? Ardric47 05:18, 6 April 2006 (UTC)[reply]

  • I've changed where it claimed that it was the Shannon number. While it might not be the Shannon number, it's pretty close in size to it. 152.163.100.10 00:55, 7 April 2006 (UTC)[reply]
    • It only seems pretty close because the exponents are pretty close, but really it is larger than the Shannon Number by a factor of about 67...saying that this is pretty close would be like saying that pi is pretty close to 200 (3.14...×100 vs. 2×102). Ardric47 02:05, 8 April 2006 (UTC)[reply]
      • Approximating 118 with 120 is hardly the same as approximating 0 with 2. A better picture is pi to 10 (100.5 vs 101) More importantly; when dealing with that large numbers approximating the exponent is usual, and frequently necesarry.

I restored the number 10^120, with a quote from the paper. Sure, it's an approximation, but it's Shannon's number so we should use Shannon's approximation, not Ardric47's approximation! Gdr 19:55, 13 May 2007 (UTC)[reply]

I think that Shannon knew that some games might last 41 moves, which gives 90041=1.3x10121 so he just rounded it off to 10120. However it is true that for him to say that 90040 "will be 10120 variations" is pretty sloppy mathematics. Was he using a slide rule at the time? 199.125.109.62 14:42, 6 June 2007 (UTC)[reply]

Move?

[edit]

This article is about the Shannon number. Now that it has been decided that the Shannon number is not 10^120, shouldn't the article be moved back to Shannon number? Melchoir 01:49, 8 April 2006 (UTC)[reply]

  • In the googol article, it says "The Shannon number is a rough estimate of the number of possible chess games, and is more than a googol: 10120". Is it wrong? 64.194.43.49 13:02, 8 April 2006 (UTC)[reply]
    • Yes, it's wrong, and I'll change it. While it is unclear exactly what the Shannon number is, whether it's 900^40 or some more accurate estimate, this article does not state that 10^120 is the Shannon number, so its title is misplaced. In general, you should trust the more specialized Wikipedia article above other articles mentioning it. Melchoir 19:23, 8 April 2006 (UTC)[reply]

Confusing redirects

[edit]

Due to confusing redirects, this page has been mirrored (and then added to by me...) at Talk:10^120 (number). Ardric47 21:14, 8 April 2006 (UTC)[reply]

Actually, as I type this, the page history is at 10^120. The redirect at 10^120 should be reverted and then moved on top of Shannon number. Melchoir 21:41, 8 April 2006 (UTC)[reply]
Do you know offhand if there was ever anything about 10120 (and not the Shannon number) that might need to be moved to its own article? 10^120 (number) is now (as of 21:46, 8 April 2006 (UTC)) a redirect to Large numbers. Ardric47 21:46, 8 April 2006 (UTC)[reply]
Not really. I'm actually now inclined to leave the redirect and this page as they are. As long as 10^120 (number) isn't deleted, it will retain a record of this page's early history, which includes so many moves that it might be best forgotten anyway. Melchoir 21:53, 8 April 2006 (UTC)[reply]
The root of the problem is the first version, in which 10120 is equated with the so-called "Shannon number". Let me add though, that I'm sure the creator meant well. Ardric47 21:52, 8 April 2006 (UTC)[reply]
Right. Melchoir 21:53, 8 April 2006 (UTC)[reply]

Calculation error in refered page

[edit]

This article refers to this site when mentioning the lower bound of an estimate of all the atoms in the universe. However, the following calculation on that page is incorrect: . The correct answer is , not . This, in turn, affects the subsequent calculation and results in a different estimate of atoms in the universe.

Cut restatement

[edit]

I cut this text from the article:

Page 70 in “The Immortal Game” by David Shenk estimates that there are 10120 unique games of chess possible.

because it appears (considered very charitably) merely to be a restatement of Shannon's estimate from the first sentence of the article, adding nothing to the article, which is not a general article on combinatorial estimates relating to chess. (Considered uncharitably, with "unique games" taken literally, the claim is of course quite false.) Gdr 10:31, 25 September 2008 (UTC)[reply]

Other uses?

[edit]

How in the world can a large number about chess variants be an analog to a joking reference about how close you are to a mathematician? I don't understand. Practicality (talk) 15:27, 2 February 2010 (UTC)[reply]

If this other Shannon number were important it should have its own article. The reference doesn't belong here. Lubrom (talk) 18:10, 26 July 2010 (UTC)[reply]

Upper bound

[edit]

In a 2006 posting to newsgroup rec.games.chess.computer Will Entriken proved an upper bound of 23937533792747905898433845980097921846050276105440 on the number of chess diagrams (roughly 2^164). The following Haskell program, if correct, improves this to just under 2^155 for the number of positions, which includes side-to-move, castling, and en-passant info.

import Control.Monad
import System(getArgs)
import Array

armies np ir = do -- max number of pawns and initial rooks
  q <- [0..1+np]
  let prom1 =         max (q-1) 0
  r <- [0..ir+np-prom1]
  let prom2 = prom1 + max (r-ir) 0
  b <- [0..2+np-prom2]
  let prom3 = prom2 + max (b-2) 0
  n <- [0..2+np-prom3]
  let proms = prom3 + max (n-2) 0
  guard $ proms <= np
  p <- [0..np-proms]
  return (q+r+b+n, p, proms, fac q*fac r*fac b*fac n*fac p)

fac :: Int -> Integer
fac n = fac64!n where fac64 = listArray (0,64) (scanl (*) 1 [1..64])

count fixp pspace fixwr fixbr = sum $ do
  let np = 8-fixp
  (wpcs,wp,wproms,wprod) <- armies np (2-fixwr)
  let wpx = np-wp-wproms                 -- white p captured
  (bpcs,bp,bproms,bprod) <- armies np (2-fixbr)
  let bpx = np-bp-bproms                 -- black p captured
  let caps = 30-2*fixp-fixwr-fixbr-wp-bp-wpcs-bpcs
  guard $ wproms <= bpx + caps
  guard $ bproms <= wpx + caps
  let space = 62-4*fixp-fixwr-fixbr-wp-bp
  return $ (fac pspace `div` fac (pspace-wp-bp)) *
           (fac space `div` fac (space-wpcs-bpcs)) `div` (wprod * bprod)

count0 (mul,ek) = mul * count 0 (46+ek) 0 0

-- Diagrams
main0 = print . sum $ map count0 [(212,2),(1448,1),(1952,0)]
-- 22124621884617108585387385940828998876019391612

-- multiplier, edge kings, fixed white rooks, fixed black rooks
countep (mul,ek,fwr,fbr) = mul *
  (count 0 (46+ek) fwr fbr + 14 * count 1 (42+ek) fwr fbr)

-- Positions
main = print . (* 2) . sum $ map countep
  [(1,2,2,2),(4,2,1,2),(4,2,1,1),
   (2*9,2,0,2),(2*43,1,0,2),(4*11,2,0,1),(4*44,1,0,1),
   (212,2,0,0),(1448,1,0,0),(1952,0,0,0)]
-- 45193640626062205213735739171550309047984050718

--Tromp (talk) 17:32, 5 May 2010 (UTC)[reply]


Just in case it's not clear, the program above (allegedly) computes an upper bound on the number of chess positions, whereas Shannon was estimating a simple lower bound on the number of variations needed to calculate the game-theoretic value of the initial position. Gdr 00:24, 4 August 2010 (UTC)[reply]