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 > > >
