From campbell@beloit.edu Wed Oct 28 11:11:09 1998 Received: from beloit.edu (beloit.edu [144.89.40.1]) by clinch.math.niu.edu (8.9.1a/8.9.1) with ESMTP id LAA28744 for ; Wed, 28 Oct 1998 11:11:09 -0600 (CST) Received: from [144.89.40.223] ([144.89.40.223]) by beloit.edu (8.9.0/8.9.0) with ESMTP id LAA25308; Wed, 28 Oct 1998 11:05:11 -0600 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 28 Oct 1998 10:44:26 -0600 To: dber@tiac.net, kgodfrey@BBN.COM, andyl@harlequin.com, rusin@math.niu.edu, esr@netcom.com, brein@aero.org, fsgrb@aurora.alaska.edu, Wgreview@aol.com, zingmast@vax.sbu.ac.uk, unwin@math.uni-augsburg.de, chavey@beloit.edu, mikeyg@beloit.edu From: "Paul J. Campbell" Subject: bad random number generator in MS Windows Status: RO I have not yet finished my paper on Klondike. I just learned that Persi Diaconis of Stanford is also writing a paper on it, and we will compare notes when we are both done. Meanwhile, here is a body blow to folks who like to play the game on the computer: Ronald D. Fricker, Jr., (Ron_Fricker@rand.org) in "A Look at Randomness in Microsoft Windows Solitaire, Or, Using Electronic Games of Chance for Statistics Projects," Teaching Statistics 20 (2) (Summer 1998) 43-45 finds "that 'shuffles' in sequential games (using 'deal' from the pull-down menu) do not randomise the elctronic deck of cards in this version of Windows solitaire. In comparison, there is no evidence here that the initial shuffle when the program is first booted is not random." In fact, after a 'deal', a card tend to appear much more often than chance would allow in exactly the same position in the deck. The consequence for the player (which is what made Fricker suspicious) is streakiness (with extreme scores) of both wins and losses. He has not tried to decompile the code to find out what shuffling algorithm was used nor apparently has he written to Microsoft to inquire. Paul J. Campbell Mathematics and Computer Science Beloit College 700 College St. Beloit, WI 53511 (608) 363-2007 (ofc) 362-2805 (res) 363-2718 (fax) campbell@beloit.edu (email) http://cs.beloit.edu/campbell/ (www pages) From campbell@beloit.edu Wed Oct 28 15:52:53 1998 Received: from beloit.edu (beloit.edu [144.89.40.1]) by clinch.math.niu.edu (8.9.1a/8.9.1) with ESMTP id PAA01357 for ; Wed, 28 Oct 1998 15:52:53 -0600 (CST) Received: from [144.89.40.223] ([144.89.40.223]) by beloit.edu (8.9.0/8.9.0) with ESMTP id PAA16590; Wed, 28 Oct 1998 15:51:27 -0600 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 28 Oct 1998 15:42:31 -0600 To: dber@tiac.net, kgodfrey@BBN.COM, andyl@harlequin.com, rusin@math.niu.edu, esr@netcom.com, brein@aero.org, fsgrb@aurora.alaska.edu, Wgreview@aol.com, zingmast@vax.sbu.ac.uk, unwin@math.uni-augsburg.de, chavey@beloit.edu, mikeyg@beloit.edu, Ron_Fricker@rand.org From: "Paul J. Campbell" Subject: Re: bad random number generator in MS Windows Status: RO In reply to my note to you about Ron Fricker's article in Teaching Statistics, I got this reply today: >Date: Wed, 28 Oct 1998 10:00:29 -0800 (PST) >From: Eric S Rosenthal >To: campbell@beloit.edu >Subject: Re: bad random number generator in MS Windows > >Bad shuffles could be due to either the shuffling algorithm or the >random number generator. > >It might be easier to replace the random number generator than to >reverse engineer the shuffling algorithm. I don't have Solitaire >installed on my Windows 95 PC, but using Windows Explorer's Quick >View to examine another Windows 95 Accessory, Paint, shows a >reference to the function rand at ordinal 0415 in the dynamic link >library (DLL) MSVCRT20.dll. This information is probably sufficient >to allow intercepting calls to the random number generator and >to help locate the shuffling code (assuming the distributed Paint >and Solitaire executables were built in the same way). > Paul J. Campbell Mathematics and Computer Science Beloit College 700 College St. Beloit, WI 53511 (608) 363-2007 (ofc) 362-2805 (res) 363-2718 (fax) campbell@beloit.edu (email) http://cs.beloit.edu/campbell/ (www pages) From campbell@beloit.edu Wed Oct 28 16:00:26 1998 Received: from beloit.edu (beloit.edu [144.89.40.1]) by clinch.math.niu.edu (8.9.1a/8.9.1) with ESMTP id QAA01407 for ; Wed, 28 Oct 1998 16:00:26 -0600 (CST) Received: from [144.89.40.223] ([144.89.40.223]) by beloit.edu (8.9.0/8.9.0) with ESMTP id PAA20726; Wed, 28 Oct 1998 15:58:57 -0600 Message-Id: Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Date: Wed, 28 Oct 1998 15:56:13 -0600 To: dber@tiac.net, kgodfrey@BBN.COM, andyl@harlequin.com, rusin@math.niu.edu, esr@netcom.com, brein@aero.org, fsgrb@aurora.alaska.edu, Wgreview@aol.com, zingmast@vax.sbu.ac.uk, unwin@math.uni-augsburg.de, chavey@beloit.edu, mikeyg@beloit.edu, Ron_Fricker@rand.org From: "Paul J. Campbell" Subject: Re: bad random number generator in MS Windows Status: RO In response to my original note to you about Fricker's article: >From: "David S. Bernazzani" >To: "Paul J. Campbell" >Subject: Re: bad random number generator in MS Windows >Date: Wed, 28 Oct 1998 14:14:40 -0500 >MIME-Version: 1.0 >X-Priority: 3 >X-MSMail-Priority: Normal >X-MimeOLE: Produced By Microsoft MimeOLE V4.72.2106.4 > >Interesting... except that the random number generator is not supplied by MS >Windows. It's a feature of the compiler to generate the numbers used in a >"shuffle" algorithm. The last piece of technical documentation I read on >the subject claimed that the Visual C++ 4.2 and above libraries passed the >Knuth tests for randomness. I'm sure Borland will claim the same for their >libraries. If the programmer of MS Windows Solitaire (aka Klondike) used a >poor shuffle algorithm (and I can't say if that's true or not) then it would >hardly preclude that the many other (potentially better) versions of >Klondike have similar problems (assuming a problem exists to begin with). >Having played thousands of shuffles of my own games, I certainly couldn't >tell if there was a bias in the shuffle algorithm. I also have a dice >roller which seems to be quite properly distributed using the same random >number libraries. Instead of concentrating on one game which may or may not >have a good algorithm, it might be better to actually write a piece of >simple code to generate a few million pseudo-random numbers, save them to a >file and then use Excel or some other package to determine how random they >are (I know there are various tests - CHI^2, etc although the details are >outside of my area of interest). Each time you run this, you will get a >different sequence since the random number generator is seeded with the >current clock time (I think it uses the number of seconds from a fixed date >in history - each "shuffle" will be different unless you shuffle twice in >the same second - hardly a problem). Otherwise you are just determining if >one program (in this case MS Solitaire) has a weakness. > >Regards, > >Dave Bernazzani >dber@tiac.net >http://www.tiac.net/users/dber Paul J. Campbell Mathematics and Computer Science Beloit College 700 College St. Beloit, WI 53511 (608) 363-2007 (ofc) 362-2805 (res) 363-2718 (fax) campbell@beloit.edu (email) http://cs.beloit.edu/campbell/ (www pages) From fricker@rand.org Wed Oct 28 22:32:00 1998 Received: from mail-lax-2.pilot.net (mail-lax-2.pilot.net [205.139.40.16]) by clinch.math.niu.edu (8.9.1a/8.9.1) with ESMTP id WAA03220 for ; Wed, 28 Oct 1998 22:31:59 -0600 (CST) Received: from mail.rand.org (unknown-6-173.rand.org [130.154.6.173] (may be forged)) by mail-lax-2.pilot.net (Pilot/) with ESMTP id OAA27306; Wed, 28 Oct 1998 14:17:15 -0800 (PST) Received: from smmail.rand.org (smmail.rand.org [130.154.6.31]) by mail.rand.org (8.9.1a/8.9.1) with ESMTP id OAA20873; Wed, 28 Oct 1998 14:17:14 -0800 (PST) Received: from rand.org (fricker2-r.rand.org [130.154.3.83]) by smmail.rand.org (8.9.1a/8.9.1) with ESMTP id OAA03309; Wed, 28 Oct 1998 14:17:13 -0800 (PST) Message-ID: <36379766.F2611B0F@rand.org> Date: Wed, 28 Oct 1998 14:15:02 -0800 From: Ron Fricker Organization: RAND X-Mailer: Mozilla 4.05 [en] (Win95; I) MIME-Version: 1.0 To: "Paul J. Campbell" CC: dber@tiac.net, kgodfrey@BBN.COM, andyl@harlequin.com, rusin@math.niu.edu, esr@netcom.com, brein@aero.org, fsgrb@aurora.alaska.edu, Wgreview@aol.com, zingmast@vax.sbu.ac.uk, unwin@math.uni-augsburg.de, chavey@beloit.edu, mikeyg@beloit.edu Subject: Re: bad random number generator in MS Windows References: Content-Type: text/plain; charset=us-ascii Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Content-Transfer-Encoding: 7bit Status: RO Hello all: It looks like you guys are looking into the technical programming details of MS Solitaire as a result of my paper. That's great (and well outside of my computer skills and capabilities)! From the recent e-mail it looks to me as though you are concentrating on the random number generator which, as Eric points out below, certainly could be the culprit. However, there is one piece of evidence in my paper which casts some doubt on this hypothesis. That is, I only found evidence of non-randomness when I used the pull-down deal option between games. When I did the same statistical tests for randomness after re-booting the program each time I did not find evidence of non-randomness. If the random number generator was at fault I would expect to find problems in both cases, not just one. My hypothesis was that a good random number generator was used when the program was booted to generate the first (random) tableau of cards; thereafter, when the pull-down "deal" option was invoked the program somehow shuffled the cards, and it was in this shuffle that the program failed. Of course this is only a guess.... Good luck in your investigations! Ron Paul J. Campbell wrote: > > In reply to my note to you about Ron Fricker's article in Teaching > Statistics, I got this reply today: > > >Date: Wed, 28 Oct 1998 10:00:29 -0800 (PST) > >From: Eric S Rosenthal > >To: campbell@beloit.edu > >Subject: Re: bad random number generator in MS Windows > > > >Bad shuffles could be due to either the shuffling algorithm or the > >random number generator. > > > >It might be easier to replace the random number generator than to > >reverse engineer the shuffling algorithm. I don't have Solitaire > >installed on my Windows 95 PC, but using Windows Explorer's Quick > >View to examine another Windows 95 Accessory, Paint, shows a > >reference to the function rand at ordinal 0415 in the dynamic link > >library (DLL) MSVCRT20.dll. This information is probably sufficient > >to allow intercepting calls to the random number generator and > >to help locate the shuffling code (assuming the distributed Paint > >and Solitaire executables were built in the same way). > > > > Paul J. Campbell > Mathematics and Computer Science > Beloit College > 700 College St. > Beloit, WI 53511 > (608) 363-2007 (ofc) > 362-2805 (res) > 363-2718 (fax) > campbell@beloit.edu (email) > http://cs.beloit.edu/campbell/ (www pages)