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%.
Received on Sat Sep 03 2005 - 12:27:30 IDT