500 billion what?

[tahnan]

This New York Times article, discussing how checkers has been computationally solved, says that

Even with the advances in computers over the past two decades, it is still impossible, in practical terms, to compute moves for all 500 billion billion board positions.

Right, so, limit search, yadda yadda. But what I want to know is: with 32 squares, each of which can have a black piece, a red piece, a black king, a red king, or nothing, there ought to be 5³² board possibilities (a huge chunk of them, of course, unreachable: kings on the board with the back row still unoccupied; more than 12 pieces per side; etc.), and that's 23,283,064,365,386,962,890,625. I think that's 23 billion billion--would it kill the times to just use the word "sextillions"?

Anyway, does anyone know where that "500 billion billion" number comes from?

Comments

[530nm330hz.livejournal.com]

Well, you start off with only 12 pieces of each type, so you can't have 32 squares that are, for example, all red kings. So, ignoring limitations on kinging, I think you'd have

∑ over i from 1 to 12  // how many red pieces are there?
  32Ci                   // where can those red pieces be?
  * 2i                   // which of them are kings?
  *
  sum over j from 1 to 12 // how many black pieces are there?
    32-iCj                 // where can those black pieces be?
    * 2j                  // which of them of kings?

[530nm330hz.livejournal.com]

Just ran that through Excel and I get 2,308,487,698,984,340,000,000 which is one order of magnitude less than 5²³, and only a factor of 4 above the number cited in the Times.

[tahnan.livejournal.com]

The problem was my inability to tell a billion billion from a trillion billion (or a billion trillion? a milliard milliard? a billiard table?), as Cnoocy noted below. I thought that the upper limit on the positions, 5³², was smaller, not larger, than the 500 billion billion they cited.

Also: 2,308,487,698,984,342,680,192. Don't use programs that round. :-)

[530nm330hz.livejournal.com]

Don't use programs that round. :-)

Caught! [[hangs head in shame]]

[thedan.livejournal.com]

Also note that any red checker in the back row (and vice versa) has to be a king, which should eliminate a decent chunk of your positions.

I think there's also things that are impossible to achieve such as all the reds passing all the blacks without a capture, but that seems much more complicated.

[530nm330hz.livejournal.com]

Well, I did say ignoring limitations on kinging.

[cnoocy]

Your number is 23 trillion billion, so it might be that some of the limiting factors take it down by a factor of 46. (Though that seems wrong to me.)

[tahnan.livejournal.com]

Aha. And this is why I hate the Times for its "billion billion".

[leighjen.livejournal.com]

Ha! You have fallen into my trap. And now I will stomp Brain Weasels!

You are the best and brightest thing in my life. I love you more than the number of moves on a checkers board. You are smart and funny and talented. I will tell you one of more than a sextillion ways that I love you:

You look totally sexy with a hippo on your head! ;-)

[lilisonna.livejournal.com]

Now I have the Laurie Beakner children's song stuck in my head.

tahnan's got a hippo on his head,
tahnan's got a hippo on his head,
tahnan's got a hippo on his head, and he keeps it there all day.

[incontango.livejournal.com]

Heheheh, "sextillions"

[flynngrrl.livejournal.com]

And that's why they don't use that word.

[incontango.livejournal.com]

Hehehehe.

[tahnan.livejournal.com]

Thank you so much. You have personally ruined my enjoyment of the New York Times, which can no longer use the word "sextillions", nor run articles on sperm whales, cockfighting, Lake Titicaca, or Jennifer Aniston.

[incontango.livejournal.com]

ROFL

[jordanwillow.livejournal.com]

wait, why not jennifer aniston?

[tahnan.livejournal.com]

oh god you don't even want to know.

[jordanwillow.livejournal.com]

i'll take your word on that one.

[kirbyk.livejournal.com]

My theory is that it's not tracking just possible board positions, but tracking them through time, so that there's 500 billion billion possible _games_ of checkers. It's doing the 'what are all the possible moves he could make, and where could those lead' thing.

I don't want to do that math. It seems plausible, given the board position math already here.

[mildmannered.livejournal.com]

Perhaps it's like the Chinese "Ten thousand things" = "Everything" or Borges' "14" = "infinite" - a random number standing in for "some really big number"?