Since I haven't mastered getting OutlookExpress to insert the old Unix style > characters into the original email, I'll respond by putting a (subject) in front of each response, and try to get my reply to stand by itself. If you get confused, refer to the Original Message.
(links)
When I get back to surfing the web in a few weeks, maybe I'll see some links coming my way. My solver can be downloaded from the web page
http://numin8r.us/programs (click the "little man" if you're interested in the rest of my website).
(age & degree)
In fact, I was born in 1944. I got my M.S. in Computer Science at the University of Colorado. I joined the department the second year of its existence.
(INT 021)
In my assembler, a hex number is simply written with a leading zero.
(lib.c)
I realize that C makes things a lot more portable. I'm stuck in a DOS window and on an Intel processor. I've been "stuck" there since about 1976. OK, 1980 if you want to get technical, however the port from the 8080 was trivial, and it gave me my first opportunity to write my assembler in itself. I suspended my third or fourth effort at rewriting it when I took up this Freecell project. I really need to get back to it, and implement a 32 bit version.
(assembler)
I've seen confirmed quite a few times that writing a code in assembler gets you about a 3-to-1 speed improvement, and about the same ratio of object code improvement. When I brought FCELL over to my new laptop, it ran at the rate of 218 games per second over the first 5 million games. That would be about 2.5 minutes for the first 32,000 games.
(atomic, super, and meta moves)
I never considered using atomic moves. It took me awhile to realize that moving the maximum number of cards to an empty column would never prevent a solution from being found. I also force certain "auto" moves beginning with the basic auto move implemented by Horne. Then, the Raymond extension to that. Finally, there are certain kinds of moves that empty columns or freecells and target fully sequenced columns that can be considered automatic. These latter two types of moves, however, can lengthen a solution, but they never prevent one. As for meta moves, there are certain kinds of move sequences that narrow search and, if carefully done, also don't prevent solutions, but this is a tricky area.
(freecell architecture)
State Representation: I only keep the current card layout for most purposes. I also keep the current move list along with untried alternative moves. When I run into a dead end, both the layout and the list are backed up. It is a depth first search with as much pruning as I can justify. It was not until about my third redesign that I implemented a lookup storage of layouts that I had encountered. I compress a layout into an average of about 16 byte entries (I forget what it is exactly). Also, I only store the most recent 24,000 or so entries (due to my memory constraints). However, it seems to work. The compression I do on a card layout considers how many cards in each column match the original deal, and how many have been played onto what ever remain. It only takes one bit per card to represent a sequence on top of n original cards, and it only takes one byte to represent a head card played into an empty column, plus one bit per card on top of that. Those are my basic tricks. Of course, you want to eliminate ordering cards in the freecells and head cards played into empty columns. I've tinkered with variations, and I'm not sure why the design I use is better than some I've tried. The design of this program has involved more trial and error than I've ever seen in a program!
----- Original Message -----
From: Shlomi Fish
To: Gary Campbell
Cc: fc-solve-discuss_at_yahoogroups.com
Sent: Saturday, September 03, 2005 1:24 PM
Subject: Re: Freecell solver program
Hi Mr. Campbell and all!
Mr. Campbell has replied to me in person, but gave me his permission to reply
to the list.
On Friday 02 September 2005 22:33, Gary Campbell wrote:
> > I'll link to it from my other solvers' list:
> >
> > Thanks for mentioning it.
> >
> > Looking at it, I see it is a .COM program, which from what I recall is a
> > DOS program that is actually the raw image of an x86 memory sector. Since
> > it's only 12331 bytes long, I guess it is written in Assembler. That's
> > quite an accomplishment.
> Yes, it's written in assembly language (of a sort). And, it uses
> limited memory, but I'm from the "old school" (got my M.S. in
> Computer Science in 1972).
1972... five years before I was born. I am humbled. Where did you get your CS
M.Sc. from? I wasn't aware that Computer Science was an established science
in the Academic sense back then. Or was it a sub-field you specialized in?
(Like "Immunology" is to "Biology").
I've chatted with an American Girl on the IRC that just turned 15. A quick
calculation indicated that I had a computer and did some programming in it
before she was born... :-) Her first operating system was Windows 95.
Of course, Adrian here humbles us both in this regard. He graduated from
Purdue University in 1944 in Electrical Engineering, and did some programming
for some really ancient systems. See:
http://www.shlomifish.org/open-source/interviews/adrian-ettlinger.html
For an interview I conducted with him.
> >
> > Note that at the moment, I am Linux-based which means I'll have to run it
> > under dosbox, dosemu or whatever. This will involve a large performance
> > penalty.
> >
> I don't know what environments are available to you, but any
> recent Intel compatible processor that can supply INT 021
> Bios entry points (I just use standard input and output) can
> run my program.
Actually the Int $21 (isn't it its Hexadecimal number?) are provided by DOS or
a similar system, not by the processor. Linux and other x86-based UNIXes
don't provide this interrupt, and work in very different ways than DOS or
Windows. There's a standard called the Intel Binary Compatability Standard
(or iBCs for short):
http://www.purplet.demon.co.uk/linux/ibcs/
It specifies how a UNIX should behave and implemented on Intel. Linux follows
it and so do other i386-based UNIXes. Most C programs request a service from
the operating system kernel by calling functions out of the Standard C
Library (a.k.a libc). This is similar to the fact that Win32 programs use the
KRNL32, USER32 and GDI32 DLLs.
What libc does is embed in the code calls to interrupt $80 (or 128 in
decimal), with appropriate values fetched in and out of registers.
So I can't run a DOS program as is on Linux, but should rather use an
emulation or virtualization of some sort.
> It does need 32-bit instructions to handle
> the random number generator used for standard deal numbers.
I see.
> I think it would be trivial to couple it into windows program that
> could spawn a child process.
That is doable.
> Given its 640K, it remains pretty
> much CPU bound during execution. In fact, I just ran it over
> lunch on games 1-1000000 (and broke it off at 627827), and it
> solved games at the rate of 218 games / second. This was the
> first time I've run it on my new laptop. It's been running 77g/s
> on my 2001 Dell laptop during the past two months that I've
> been working on it.
>
It sounds pretty fast. Freecell Solver in a certain meta-scan configuration
could solve the MS 32,000 in about 40 minutes or 75 minutes or so (don't
remember exactly) on a P3-600 MHz computer. I haven't timed it on my new
P4-2.4GHz (which replaced the P3 due to the latter's hardware failure) yet.
Using Assembler can often make a dramatic influence on the speed, size and
memory consumption of the program. I recall that my partner and I in the
Technion once had to re-write a a floating-point routine in inline Assembler.
(on a Pentium) We both wrote different codes, but they both performed 4 to 5
times faster than the C-version. I'm not sure if the C version was compiled
with optimizations, though.
> >
> > A couple of times, I contemplated hand-optimizing some time-consuming
> > routines in FCS by implementing them in Assembler, and giving the build
> > system a choice to use it instead on an i386 system. But then I thought
> > that it would be "cheating". I still must make sure Freecell Solver is
> > available as a pure C program, because I cannot guarantee it would run on
> > an i386 VM. One anecdote about it is that it is distributed as part of the
> > KDE desktop environment's kdegames package, which aims to be built on any
> > UNIX flavour and architecture. (I actually received a few bug reports
about
> > incompatabilities with such systems.)
> >
> > I suppose you have used atomic moves? (I.e: moves that move one card at a
> > time.) How did you implement the state collection? How are your states
> > represented?
> No, I use the maximum legal supermove that might be available,
> and basically treat it as "atomic."
I see. Well, Freecell Solver has an option to use some meta-moves, which are
groups of atomic moves or supermoves that aim to achieve a certain end that
may be desirable. Moving the cards themselves and generating the next state
is relatively inexpensive, but finding such a legal move for some of the more
complex meta moves is a bitch. What I have now is a lot of nested loops and
conditionals, all in one function. Maybe there's a better way to do it, but I
haven't looked into it.
Atomic ("one-card-at-a-time") moves are adequate for solving Freecell and
similar games to some success, but from what I tried are almost completely
unsuitable for solving Simple Simon:
http://en.wikipedia.org/wiki/Simple_Simon_(solitaire)
> Otherwise, various pruning
> options and shortcuts wouldn't be as easy. Just because it's
> written in assembly language doesn't mean it isn't sophisticated!
:-)
> In fact, the assembler I use is my own creation, and it is as easy
> (for me) to use as any language I've programmed in. I developed
> it in graduate school as an exercise in human factors applied to
> programming languages.
I see. Is your assembler program now written (and compiles) itself? I don't
suppose the 8086/8088 existed back in 1972. Did you eventually port your
assembler to the x86? Or was it modular enough to start with?
> >
> > Being a DOS program - does your solver has a limit of 640 KB memory?
> >
> Yes, it only uses the standard memory amount, and no intermediate
> file storage. It only reads and writes Standard In and Standard Out.
>
I see. What measures did you take to reduce the amount of memory the states
occupy? There are quite a few techniques I used in Freecell Solver, and I
heard or was suggested others.
> > An advice for you is to have the link say "Download the Executable" or
> > something along these lines. Possibly including the filename. In any case,
> > your link says "Freecell Solver" with a capital "S". I don't see a reason
> > for the "S" to be capitalized. "Freecell" is a name, but "solver" is not.
> > Generally, "Freecell Solver" with a capital "S", refers to my solver, and
> > not to any other Freecell solver. It's a bit confusing, but I'm to blame
> > for my lack of imagination in better naming my solver. (and for not
> > entirely being aware of the rest of the Freecell and Freecell solvers
> > culture that existed before its writing).
> I'll change my link to "Download the Executable" as you suggest.
Thanks.
Regards,
Shlomi Fish
---------------------------------------------------------------------
Shlomi Fish shlomif_at_iglu.org.il
Homepage:
http://www.shlomifish.org/
95% of the programmers consider 95% of the code they did not write, in the
bottom 5%.
Yahoo! Groups Links
Received on Sat Sep 03 2005 - 13:54:03 IDT