Zax and all--
All I can say i8s that, even with my approaching-infinity game
experience, I can't remember any; but then my memory ain't what it used to be.
Stu Goldman
----- Original Message -----
From: [email protected]
To: [email protected]
Sent: Thursday, March 05, 2009 9:32 AM
Subject: Re: [quackle] Re: Scrabble Complexity
Or the even more interesting thought, what are the odds of two complete
games ever being exactly the same?
--- On Thu, 3/5/09, [email protected]
<[email protected]> wrote:
From: [email protected] <[email protected]>
Subject: Re: [quackle] Re: Scrabble Complexity
To: [email protected]
Date: Thursday, March 5, 2009, 12:28 PM
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: zax_...@yahoo. com
To: quac...@yahoogroups .com
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 <tc...@yahoo. com> wrote:
From: Russell Honeybun <tc...@yahoo. com>
Subject: Re: [quackle] Re: Scrabble Complexity
To: quac...@yahoogroups .com
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
>
>
>
