Subject: RE: [hackers-il] Re: My Wish-list for the O'Reilly Open Source Co nvention

From: Chen Shapira <[email-masked]>
Date: Tue, 19 Nov 2002 10:11:34 +0200

> > > * 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.
The Freecell Solver doesn't feature any C breakthroughs, nor does it use any
novel software engineering methods.

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.

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.

Thanks,
Chen

---

From: Shlomi Fish <[email-masked]>
Date: Tue, 19 Nov 2002 13:51:19 +0200 (IST)

> The Bazaar model already exists, and is well know to the Open Source

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

> 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.

> though. Open Source conventions are not usualy the place to discuss graph

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.

> 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:
> [email-masked]
>
>
>
> Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/
>
>

----------------------------------------------------------------------
Shlomi Fish        [email-masked]
Home Page:         http://t2.technion.ac.il/~shlomif/
Home E-mail:       [email-masked]

"Let's suppose you have a table with 2^n cups..."
"Wait a second - is n a natural number?"