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: [email protected] > 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 [email protected], 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-programmers 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 > > >
