From WKRfresno@aol.com Mon Nov 24 11:02:05 2003 Return-Path: X-Sender: WKRfresno@aol.com X-Apparently-To: fc-solve-discuss@yahoogroups.com Received: (qmail 15257 invoked from network); 24 Nov 2003 19:02:03 -0000 Received: from unknown (66.218.66.167) by m14.grp.scd.yahoo.com with QMQP; 24 Nov 2003 19:02:03 -0000 Received: from unknown (HELO imo-m01.mx.aol.com) (64.12.136.4) by mta6.grp.scd.yahoo.com with SMTP; 24 Nov 2003 19:02:03 -0000 Received: from WKRfresno@aol.com by imo-m01.mx.aol.com (mail_out_v36_r1.1.) id r.c5.3b46afd6 (1320) for ; Mon, 24 Nov 2003 14:01:50 -0500 (EST) Message-ID: Date: Mon, 24 Nov 2003 14:01:49 EST Subject: Re: Best solving method To: fc-solve-discuss@yahoogroups.com MIME-Version: 1.0 Content-Type: text/plain; charset="US-ASCII" Content-Transfer-Encoding: 7bit X-Mailer: AOL 5.0 for Windows sub 138 From: WKRfresno@aol.com X-Originating-IP: 64.12.136.4 X-Yahoo-Group-Post: member; u=3348659 Hi everybody. I was mostly inactive for a couple of years because a health problem put me on the sideline. But I'm ok now and I got a second computer in May so I'm fired up again. You've started the most interesting conversation yet. I thrive on these little details. My solver is fast (~10000000 deals per hour @733mHz) not because of any sophisticated algorithm but because I've experimented endlessly with every tiny variation and the best order to apply them. There is a very good and simple reason to move a card from a freecell (FC) to an empty column (EC). Many games cannot be solved without it. Just CAN'T be solved without it. To play with 3 freecells instead of four makes about 1% of the deals unsolvable. To play without FC->EC is a similar handicap, although I don't know what percentage of games it renders unsolvable. Of all the possible variations and permutations of all the possible moves - and I've identified hundreds of them - only one can be permanently discarded; Shlomi mentioned it in his first letter today: there is no reason for FC->EC unless you intend to put other cards on it. Regarding BrFS: it's guaranteed to find the shortest possible solution (fewest moves) but requires enormous amounts of memory. My solver keeps everything in RAM (768 mBs) because I'm too impatient to wait for pageing. Of the MS32K I've solved only a dozen or so with BrFS. One of the easiest deals to solve this way is 1941 because its tree has far fewer branches, or shorter ones, than nearly all others. My solver is quick only when solving a long range of deals using DFS. BrFS takes forever looking for shortest solutions because all moves must be available and RAM fills up for almost every deal before failing. A* is not possible for freecell because the solver must know in advance how many moves will be in the shortest solution. One can approximate A* with Iterative Deepening, where one makes a lowball guess, runs until failure, then increases the guess by one and tries again. Repeat until the shortest solution is found. When I was searching for short freecell deals I didn't use ID but set the depth at 20 and just let it run over the MS32K. Averaged 11 deals per hour with 1gH Intel and 2gB RAM. My children grew up, moved out, married and had children of their own during the time that needed. I know a couple of reasons to sort the columns while running, but never had to do that. Now I suspect that some deals are unmanageable for me because some (or many, or all) of the positions are repeated but with columns permuted. So sorting columns is on my to-do list. Bill Raymond