Loading ...
Sorry, an error occurred while loading the content.

RE: Re: My Wish-list for the O'Reilly Open Source Co nvention

Expand Messages
  • Shlomi Fish
    ... Freecell Solver s development deviated a bit from the Bazaar model, mainly because I did not read CatB when I started programming it. See my essay The
    Message 1 of 3 , Nov 19, 2002
    • 0 Attachment
      On Tue, 19 Nov 2002, Chen Shapira wrote:

      >
      > > > > * Give any of the following presentations:
      > > > > "Rindolf - Purpose and Objectives"
      > > > > "Freecell Solver - Evolution of a C program" (already prepared)
      > > > > "Freecell Solver - The Next Presentation"
      >
      > > No, I'm going to submit those presentations to the
      > > organization commitee
      > > for them to decide if I can give them. If they reject all of them -
      > > whatever, but I'd still like to give them. You never succeed
      > > unless you
      > > try.
      >
      > What is the value of the second presentation?
      > The Bazaar model already exists, and is well know to the Open Source
      > community.

      Freecell Solver's development deviated a bit from the Bazaar model, mainly
      because I did not read CatB when I started programming it.

      See my essay "The Well and the Wall" for details:

      http://groups.yahoo.com/group/hackers-il/message/2809

      > The Freecell Solver doesn't feature any C breakthroughs, nor does it use any
      > novel software engineering methods.
      >

      I indeed re-invented the wheel times and again. However, many people are
      not aware of all the C tricks out there, and could use a bag-full of them
      to learn from. I initially thought some things would definitely not work
      and then discovered that they did work and better than I expected.

      For instance, I believed storing cards as chars would be slower than
      storing them as ints. However, after I implemented COMPACT_STATES I
      discovered that they were much faster than FAST_STATES. (thus changing
      FAST to DEBUG). And now the indirect stack states has become slightly
      faster than compact states after I implemented Copy-On-Write and other
      tricks of not excessively mallocing everything.

      > I find that the main value of the Freecell Solver is in its use of graph
      > theory algorithms, to solve an interesting game.
      > A lecture that will focus on those algorithms and the way they can be used
      > to solve other types of games, will be much more interesting IMO.
      > Such lecture should probably be given at a different kind of conference,
      > though. Open Source conventions are not usualy the place to discuss graph
      > theory.
      >

      There are some things involved in graphs, but I think they are common
      game AI knowledge. I believe I covered the scans in the lecture, and it is
      mentioned there.

      > BTW. I've been looking at "SameGnome" lately.
      > The idea of the game is that you have an NxM board with 3 different kinds of
      > dots on it.
      > If there is a cluster of two or more adjustant identical dots, clicking on a
      > dot will cause the cluster to disappear, giving you a score of #dots*value.
      > The interesting part is that "value" is exponential in the number of dots.
      > So deleting a cluster of 8, is much more profitable than 4 clusters of 2.
      > Also, after deleting a cluster, the dots around it will move around in some
      > way I didn't fully figure out yet, causing new clusters to be created.
      >
      > Given the formula to calculate the values, and the algorithm that shifts the
      > dots around, it should be possible to write a program that given a board
      > will output a series of steps that maximize profit.
      >
      > Automated game solving is very interesting to me, but its main interest is
      > not the language, evolution or licsense. Its the algorithms and methods.
      >

      I disagree with you here. Sometimes I had two identical algorithms
      implemented in C that run at drastically different speeds. Like Omer said,
      the devil is in the details. The pseudo-code of Freecell Solver is one
      thing. It can have so many C implementation that it hurts. And the
      difference of speed between each one can be several factors apart.

      <<<
      "Computer Science is no more about computers than Astronomy is about
      Telescopes."

      Edsgar W. Dijkstra

      "C Programming is no more about computers than Astronomy is about stars."

      Shlomi Fish
      >>>

      ;-)

      Shlomi Fish

      > Thanks,
      > Chen
      >
      >
      >
      > To unsubscribe from this group, send an email to:
      > hackers-il-unsubscribe@egroups.com
      >
      >
      >
      > Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
      >
      >



      ----------------------------------------------------------------------
      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/
      Home E-mail: shlomif@...

      "Let's suppose you have a table with 2^n cups..."
      "Wait a second - is n a natural number?"
    Your message has been successfully submitted and would be delivered to recipients shortly.