On Saturday 03 September 2005 23:53, Gary Campbell wrote:
> 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.
OK.
> (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.
I see. Was this department part of a larger department? Or was it autonomous?
[1]
>
> (INT 021)
> In my assembler, a hex number is simply written with a leading zero.
>
Hmmmm... the problem is that C/C++, Java, Perl, C# etc. (which from what I
know are the languages with the largest communities of programmers), have a
convention of starting _octal_ number with a leading zeros, and hex numbers
with the prefix "0x". While you are free to deviate from this convention in
your own invented syntaxes, you should use the syntax that most of the people
here or elsewhere would understand. In Rome, act like a Roman.
> (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.
Cool.
>
> (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.
Wow, that's really fast.
>
> (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.
I see. Sounds very interesting.
>
> (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).
Hmmm... I remember asking people for directions regarding eliminating older
states from a game AI graph on Usenet, when I wanted to implement something
similar for FCS:
http://xrl.us/he27
> 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.
Hmmm... that reminds me of what Don Woods implemented in his solver, at least
from what I understood from the comments there. You can find this solver
here:
http://vipe.technion.ac.il/~shlomif/freecell-solver/don_woods.html
I have a problem using this technique in FCS, at least directly, because FCS
is general enough to solve solitaire variants with different ideas of what a
sequence mean. I may be able to get away with two bits instead of an entire
byte for a card, but I did not get to it, or even thoroughly considered it.
> 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!
Yes. Writing Freecell Solver involved quite a lot of trial and error as well.
Or just plain hard thought and then implementations. One thing I
retrospectively regret now is that I did not build an adequate automated test
suite for it, and did some test-driven programming. Generally, bugs and other
strange behaviours tended to appear, get fixed, disappear, re-appear, etc.
This can be prevented and the long-term correctness of the code maintained
for a long while using automated tests.
Regards,
Shlomi Fish
[1] - I think the Computer Science and the Electrical Engineering departments
should be combined into one department. In the Technion, where both
departments are separate, there are tons of duplicate courses in both, and a
lot of penis envy. Computer Science courses have a vast and deep network of
dependencies, which is constantly enforced, and that may be the case for EE
too, even though I did not notice because I'm an EE students and already had
to take most of these dependency courses anyway.
It is generally known that Computer Science courses that are given by the EE
faculty are easier than the equivalent ones given by the CS faculty, and that
the CS faculty's Electronics courses are easier than the EE ones.
In MIT they have or at least had one department for both topics. So for
example, Structure and Interpretation of Computer Programs, one of the
classic texts on CS, was published by "The Department of Electrical
Engineering and Computer Science, MIT".
[ Deleting Original Message Text ]
---------------------------------------------------------------------
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 - 23:06:53 IDT