Zax and all--
Since I'm mentioned, I might as well chime in. The usually astute Zax
did not allow for exchanges or passes, which would seem to make the number of
possible games something that approaches infinity.
Stu Goldma
----- Original Message -----
From: [email protected]
To: [email protected]
Sent: Thursday, March 05, 2009 11:42 AM
Subject: Re: [quackle] Re: Scrabble Complexity
The correct answer is the number of games Stu Goldman has played +1 or
roughly .034^8.23.
The other thing to realize is the number of valid possible game
positions, which varies by lexicon.
What would the space be if we didn't care about the validity of the
words? How many possible ways can 100 tiles fit on a 225 square grid? That
would seem like the upper bound.
--- On Thu, 3/5/09, Russell Honeybun <[email protected]> wrote:
From: Russell Honeybun <[email protected]>
Subject: Re: [quackle] Re: Scrabble Complexity
To: [email protected]
Date: Thursday, March 5, 2009, 11:30 AM
Roger, a typical game does not have 490 moves. such a game would have
a probability of 10^(very large negative number) of ever being played, thus
it's significance is ~0. This is a dampening factor that N(number of moves)
tends to infinity, the probability of playing such a game reduces dramatically.
Your brief assay would be like summing the cumulative brightness of all stars
in the universe as if they were the distance of our own sun away.
I don't have my more detailed calcs at hand, but it's fairly simple
to
work out the approximation - but you have to cheat by assuming the
bag is endless for X moves, for the purposes of simplicity.
1. Assume all words of eight letters or more are playable on each
turn(114575) .
2. Assume the average moves per person per game is X=15.
3. N^X=114575^30= ~10^151
The true answer is significantly less than (3). 200 words or less are
playable per turn (play a few games of quackle and ask it to generate all moves
to calculate this for yourself)
200^30=10^69
I think in my original calcs i looked at my own stats of 14 plays per
game average 200^28=2*10^ 64 and you can see how the original figure is tending
to the answer Graham correctly gave you.
This in itself is a rough overestimation, as on each turn available
there are less than 50 (and in a lot of cases less than ten) "sane" options.
unfortunately, there is no mathematical function to describe "saneness" when
talking about near-infinite branching integrals. If we implement "saneness"
(<50 moves/turn) the number of total games drops to around 10^40, if we
implement "expert saneness" (average 5 moves playable) you are looking at a
figure around 10^21. Still, this is a number so large we could play a game
every hour for the age of the universe and have a never repeat. I think that
when considering games of go and chess, the saneness and expert-saneness
protocols reduce the number of games playable far more than scrabble is
restricted.
As it stands, a definite approximation is impossible to achieve, but
we are absolutely sure it is more than 10^21 and less than 10^151
Regards.
--- On Fri, 2/27/09, Roger <[email protected]> wrote:
> From: Roger <[email protected]>
> Subject: [quackle] Re: Scrabble Complexity
> To: quac...@yahoogroups .com
> Date: Friday, February 27, 2009, 1:17 AM
> I think that 10^60 is a gross underestimation of the size of
> the game
> tree of Scrabble. If we account for exchanging tiles and
> passes, then
> each player has 128 or 2^7 options of what to do a turn
> without even
> playing a tile on the board. We can alternate doing this
> for 5 turns
> each time until one player plays a tile (2 on the first
> move of the
> game) and then repeat. Because there are 100 tiles in the
> bag, there
> will be ~98 or so repetitions of this and we'll end up
> with ~490 or so
> moves. Each moves has a 2^7 (assuming all tiles are
> different, which
> is not the case, but for our purposes let's assume
> this). (2^7)^490 =
> 2^3430 ~= 10^1000 (which is considerably larger than
> 10^60). yes, we
> are making the assumption that the tiles on the racks are
> unique to
> come up with the 2^7 number, but notice that we haven't
> even taken
> into consideration the geometry of the board at all.
>
> I believe that Scrabble has a game tree complexity
> significantly
> greater than 10^60.
>
> --- In quac...@yahoogroups .com, Graham Toal
> <gt...@...> wrote:
> >
> > The *exact* number is impossible to calculate; it
> would have to be
> > enumerated - and it's so large that that isn't
> possible either!
> >
> > However an estimate would be around 10^60.
> >
> > Russell Honeybun is the expert in this area and should
> be able to
> give
> > you a derivation of the above estimate. If he's
> not on this list,
> try
> > wordgame-programmer s which is where I saw him last.
> >
> >
> > Graham
> >
> >
> > On Thu, Feb 26, 2009 at 7:14 AM, allstrugglewithin
> <pookp...@.. .>
> wrote:
> > > I just search wikipedia and it seems like
> 'Go' has the most total
> > > number of possible games that can be played.
> > >
> > > But wikipedia doesn't say anything about
> Scrabble, so if someone
> knows
> > > the exact number, please tell me.
> >
>
>
>
>
>
> ------------ --------- --------- ------
>
> Yahoo! Groups Links
>
>
>
