Shlomi Fish
Sat, 15 Apr 2000 05:42:07 -0700
This is slightly off-topic but I thought it may be of interest to the list. I wrote a program that automatically solves Freecell games. For those who are not familiar with it, Freecell is a card game, in which there are several stacks which should be moved to the decks with the aid of freecells, which are cells that can hold one card each. In any case, the program operates by keeping record of the states for which it checked whether they are solveable, so if the same state is reached twice, it will only be checked once. (and thus also, it makes sure there are no infinite loops). I wrote two versions of the program, one which uses states where the representitive integers have widthes of ints and shorts. And the second the integers are chars, and semi-chars. (I use shifts and bit masks to get the card deck and card number). I noticed that the program that uses the chars representation runs much faster than the int/short based program. For 100 given initial boards, it finished them in 11 minutes and 12 seconds. The wider program took more than 19 minutes when it was terminated in the middle of board No. 62, which is a complex board that takes 42,940 checked states to solution. The question is why the wide-integer based program is slower because obviously my Pentium 166 MHz processor takes less time for 32-bit or 16-bit integer computations and memory access than for 8-bit ones. My best guess so far is that the majority of the time is spent storing and searching for states, and because the char storage occupies less space, that it is considerably faster. What do you think? You can download Freecell Solver and take a look at the source code from the following URL: http://t2.technion.ac.il/~shlomif/fcs/ This is not going to be its permanent homepage, but I resorted to putting it there because vipe.technion.ac.il has a momentary problem of hosting the users' homepages. I discovered a few other insights while working on Freecell Solver. For instance, I realized that one should not use qsort to insert a sort margin into a sorted array, because it's quite slow. Instead, a binary-search based merging function should be used. Another curious thing is that the program runs differently on Windows NT than it does on i386 Linux and SPARC Solaris. On IRIX 64-bit it runs differnetly than both of the above. I still don't know what's the cause of this behaviour but I'm investigating it. Best regards, Shlomi Fish ---------------------------------------------------------------------- Shlomi Fish [EMAIL PROTECTED] Home Page: http://t2.technion.ac.il/~shlomif/ Home E-mail: [EMAIL PROTECTED] The prefix "God Said" has the extraordinary logical property of converting any statement that follows it into a true one. ================================================================= To unsubscribe, send mail to [EMAIL PROTECTED] with the word "unsubscribe" in the message body, e.g., run the command echo unsubscribe | mail [EMAIL PROTECTED]