FreeCell puzzles solver API

This is a little pet project I did a while ago. It’s a FreeCell puzzle‘s solver API.

The idea is to provide a basic validation engine and board management (pretty much like my old chess validation), so people can write FreeCell solvers on top of it. It has basic board setup (of multiple sizes), movement legalisation, and a basic Solver class, which you must derive to create your own solvers.

There’s even a BruteFroceSolver that can solve a few small boards, and that gives you an idea on how to create your own solvers. However, the API is not clear enough yet that children could start playing with it, and that’s the real goal of this project: to get kids interested in solving complex optimisation problems in an easy way.

Freecell is a perfect game for it. Most boards can be solved (only a handful of them were proven – by exhaustion – not solvable), some movements can be rolled back and you can freely re-use cards that have already been placed into the foundations (their final destination) back in the game again.

It’s out of the scope of this project to produce a full-featured graphic interface for kids, but making the API easy enough so they understand the concepts without dragging themselves into idiosyncrasies of C++ is important.

Compiler optimisations

The reason why I did this was to make some of the optimisations compiler engineers have to do more appealing to non-compiler engineers or children with a taste for complex problems. But what does this have to do with compilers? The analogy is a bit far-fetching and somewhat reverse, but it’s interesting nevertheless and it was worth the shot.

Programming languages are transformed into graphs inside the compiler, which should represent the intentions of the original programmer. This graphs are often optimised multiple times until you end up with a stream of instructions representing the source code in the machine language.

Ignore for now the optimisations on those graphs, and focus on the final part: selecting machine instructions that can represent that final graph in the machine language (assembly). This selection can pick any assembly instruction at will, but it has to put them into a very specific order to represent the same semantics (not just syntactic) of the original program. Since many instructions have side effects, pipeline interactions, special flags set or cleaned up, it’s not trivial to produce correct code if you don’t check and re-check all conditions every time. This is a known complex optimisation problem and can be responsible for changes in speed or code size in orders of magnitude.

What does it have to do with the Freecell puzzle? Well, in Freecell, you have a number of cards and you have to put them in a specific order, just like assembly instructions. But in this case, the analogy is reverse: the “sequence” is trivial, but the “instructions” are hard to get.

There are other similarities. For example, you have four free cells, and they can only hold one value at a time. They are similar to registers, and manipulating them, gives you a good taste of how hard it is to do register scheduling when building the assembly result. But in this case, it’s much harder to spill (move the data back to memory, or in this case, card back to cascades), since there are strict rules on how to move cards around.

Reusing cards from the foundations is similar to expanding single instructions into a sequence of them in order to circumvent pipeline stalls. In real compilers you could expand a multiply+add (very useful for digital signal processing) into two instructions: multiply and add, if that gives you some advantage on special cases on special chips. In Freecell, you can use a 9 on top of a 10, to move an 8 from another cascade and free up a card that you need to clean up your freecells (registers).

I’m sure you can find many more similarities, even if you have to skew the rules a bit (or completely reverse them), but that’s not the point. The point is to interest people into complex optimisation techniques without the hassle of learning a whole new section of computer science, especially if that section puts fear in most people in the first place.

Humble Bundle

I’m not the one to normally do reviews or ads, but this is one well worth doing. Humble bundle is an initiative hosted by Wolfire studio, in which five other studios (2D Boy, Bit Blot, Cryptic Sea, Frictional Games and the recently joined Amanita Design) joined their award-winning indie games into a bundle with two charities (EFF and Child’s Play) that you can pay whatever you want, to be shared amongst them.

All games work on Linux and Mac (as well as Windows), are of excellent quality (I loved them) and separately would cost around 80 bucks. The average buy price for the bundle is around $8.50, but some people have paid $1000 already. Funny, though, that now they’re separating the average per platform, and Linux users pay, on average, $14 while Windows users pay $7, with Mac in between. A clear message to professional game studios out there, isn’t it?

About the games, they’re the type that are always fun to play and don’t try to be more than they should. There are no state-of-the-art 3D graphics, blood, bullets and zillions of details, but they’re solid, consistent and plain fun. I already had World of Goo (from 2D Boy) and loved it. All the rest I discovered with the bundle and I have to say that I was not expecting them to be that good. The only bad news is that you have only one more day to buy them, so hurry, get your bundle now while it’s still available.

The games

World of Goo: Maybe the most famous of all, it’s even available for Wii. It’s addictive and family friendly, has many tricks and very clever levels to play. It’s a very simple concept, balls stick to other balls and you have to reach the pipe to save them. But what they’ve done with that simple concept was a powerful and very clever combination of physical properties that give the game an extra challenge. What most impressed me was the way physics was embedded in the game. Things have weight and momentum, sticks break if the momentum is too great, some balls weight less than air and float, while others burn in contact with fire. A masterpiece.

Aquaria: I thought this would be the least interesting of all, but I was wrong. Very wrong. The graphics and music are very nice and the physics of the game is well built, but the way the game builds up is the best. It’s a mix of Ecco with Loom, where you’re a sea creature (mermaid?) and have to sing songs to get powers or to interact with the game. The more you play, the more you discover new things and the more powerful you become. Really clever and a bit more addictive than I was waiting for… 😉

Gish: You are a tar ball (not the Unix tar, though) and have to go through tunnels with dangers to find your tar girl (?). The story is stupid, but the game is fun. You can be slippery or sticky to interact with the maze and some elements that have simple physics, which add some fun. There are also some enemies to make it more difficult. Sometimes it’s a bit annoying, when it depends more on luck (if you get the timing of many things right in a row) than actually logic or skill. The save style is also not the best, I was on the fourth level and asked for a reset (to restart the fourth level again), but it reset the whole thing and sent me to the first level, which I’m not playing again. The music is great, though.

Lugaru HD: A 3D Lara Croft bloody kung-fu bunny style. The background story is more for necessity of having one than actually relevant. The idea is to go on skirmishing, cutting jugulars, sneaking and knocking down characters in the game as you go along. The 3D graphics are not particularly impressive and the camera is not innovative, but the game has some charm for those that like a fight for the sake of fights. Funny.

Penumbra: If you like being scared, this is your game. It’s rated 16+ and you can see very little while playing. But you can hear things growling, your own heart beating and the best part is when you see something that scares the hell out of you and you despair and give away your hide out. The graphics are good, simple but well cared for. The effects (blurs, fades, night vision, fear) are very well done and in sync with the game and story. The interface is pretty simple and impressively easy, making the game much more fun than the traditional FPS I’ve played so far. The best part is, you don’t fight, you hide and run. It remembers me Thief, where fighting is the last thing you want to do, but with the difference is that in Thief, you could, in this one, you’re a puss. If you fight, you’ll most likely die.

Samorost 2: It’s a flash game, that’s all I know. Flash is not particularly stable on any platform and Linux is especially unstable, so I couldn’t make it run in the first attempt. For me, and most gamers I know, a game has to work. This is why it’s so hard to play early open source games, because you’re looking for a few minutes of fun and not actually fiddling with your system. I have spent more time writing this paragraph than trying to play Samorost and I will only try it again if I upgrade my Linux (in hoping the Flash problem will go away by itself). Pity.

Well, that’s it. Go and get your humble bundle that it’s well worth, plus you help some other people in the process. Helping indie studios is very important for me. First, it levels the play-field and help them grow. Second, they tend to be much more platform independent, and decent games for Linux are scarce. Last, they tend to have the best ideas. Most game studios license one or two game engines and create dozens of similar games with that, in hope to get more value for their money. Also, they tend to stick with the current ideas that sell, instead of innovating.

By buying the bundle you are, at the very least, helping to have better games in the future.

Happy 1234567890!!

It has just passed the Unix time 1234567890! (or, if you prefer, 0x499602D2, which is not funny at all).

Friday, February 13, 2009 at exactly 23:31:30 (UTC, which I happen to be), is a nice Friday 13th (already spooky).


$ perl -e 'print scalar localtime(1234567890),"\n";'
Fri Feb 13 23:31:30 2009

I suppose you have a Unix at home, of course. Well, you probably do anyway…

Other fancy Unix dates to come:


$ perl -e 'print scalar localtime(2000000000),"\n";'
Wed May 18 04:33:20 2033
Next billionth second…


$ perl -e 'print scalar localtime(0x7FFFFFFF),"\n";'
Tue Jan 19 03:14:07 2038
As far as it can go, with 32bit signed integers…

And some other that passed already:


$ perl -e 'print scalar localtime(1000000000),"\n";'
Sun Sep 9 02:46:40 2001
The first billionth second:

And finally some before the Unix era:


$ perl -e 'print scalar localtime(0xDEADBEEF),"\n";'
Mon Apr 14 15:27:43 1952
Well, 0xD has the sign bit set, doesn’t it? It’s in the past too…


$ perl -e 'print scalar localtime(0x80000000),"\n";'
Fri Dec 13 20:45:52 1901
As far as it can go in the past…

But don’t worry, 64-bit systems can already (and do already) manage times up to 9223372036854775807 seconds back and forth 1st January, 1970. It’s plus and minus 292 million years. It’ll be good to tag even dinosaurs with Unix-time, as well as the Enterprise next-generation.

The only problem is that the two final catastrophes we can’t get rid of: sun becoming a red giant (thus engulfing all planets, or the Milky Way colliding with Andromeda, will happen in no less than 5 billion years from now, which means that we’ll need to change to 128-bit time-stamp eventually.

Happy unix-time 1234567890!!

Silly game of the week: Grep Pipes

After writing my last post I couldn’t stop thinking about pipes and remembered a nice game called Pipe Dream (aka Pipe Mania) and than it came to me the geeky version of this game:

You have a starting point (some lines of text) and some ending points (stripped versions of the original text) and a few grep blocks with regular expressions. The objective is to place the grep blocks from start to finish before the data floods out.

grep pipes

After a few minutes with OODraw and Gimp I could come to this (horrible and ill drawn) interface for the game. Nothing really exciting, just to give you an idea on what should happen… 😉

I’ve also did a sample code on what the underlying library should look like available here.

The idea is to have more commands, such as awk, sed and perl to make it harder (because each one has its own regular expression syntax). A tee should also be required to split paths and other programs such as cat, diff and comm re-unite them.

Harder levels of the game should have bigger boards, tricky regular expressions and even more than one board with netcat or ssh bridges to send data across the network. Also, to increase the level of reality, some programs such as cat and grep should let the data flow faster than others like perl.

Another option is to let the user define the regular expression by hand or number of lines to crop. This would be like having some of the blocks as wild cards, in case there isn’t any suitable block available.

Anyway, the options are endless and I’m sure there will be lots of people that would love it (me included) but I’m a complete failure to design user interfaces. So this is an open invitation, if you’d like to see this game out and could give me a hand with the interface, just let me know… 😉

Just bear in mind the following fundamental pre-condition: the game must allow (better still, encourage) keyboard-only playing, even if high-end OpenGL graphics interface is used.

True wisdom from randomness

You can live a whole life and remain stupid but a stupid program using a pseudo-random number generator and a clever algorithm (Markov’s chain) can excel us quite easily:

  • Input: The GNU GPL license
  • Output:

    “GNU General Public License along with you add to sue for details.”

  • Input: man perl
  • Output:

    “PERL (higher numbers usually being affected by wraparound).”

  • Input: My own wiki
  • Output:

    “Bioinformatics is a physicist (definitions of enforcing standards but it puts wrong things can build complex information systems and nothing is totally unacceptable for every new piece of giving generic answers.”

Recursive patents

IBM once had great innovators working for them, many holding Nobel prizes etc but for a while they haven’t had a great idea… until NOW!

It’s a genius idea that will revolutionize the whole patent scheme: They’re filling a patent on Getting money out of patents.

Quoting The Register: If Big Blue gets its way, Microsoft’s promises to Novell and Xandros not to sue over alleged infringements of its Windows patent portfolio ought to mean Redmond pays a kickback to IBM.

If that doesn’t change the completely stupid and out-of-this-world patent system in US, I don’t know what will…

Geeks United! It’s time to recycle!

It’s time to recycle using your hand craft abilities!

Computer Chip Trivet

Don’t you know what to do with those old computer chips laying around? What do you think about a stylish trivet? Instructions are simple to follow: all you need are some computer chips , grout, adhesive, and a tile square.

Once you’re all finished, you’ll have a nicely geekified trivet for all your hot stuff.

You’ll really impress your geeky friends with this genuinely useful kitchen tool that you can make: a trivet built out of old computer chips.

Follow this link for full instructions.

Hard Drive Wind Chimes

The drive platters themselves are also quite remarkable: precisely made aluminium patters with a surface not unlike recording tape. The disks make a lovely clear note if you strike them, so it was only natural to make them into a set of wind chimes.

An interesting side effect is that the shiny shiny platters reflected little spots of light into the house. Naturally, if you have cats, they’ll love it too.


Follow this link for full instructions.


Hard Drive Picture Frames

So, you’ve disassembled hard drives, taken the magnets out, made wind chimes out of the platters, and so on. One thing that you might have left over is a set of printed circuit boards. Funny shaped printed circuit boards, with holes in them.

Here’s how to turn those leftover PCBs into fabulous geek-chic picture frames.

It’s done! Hang it on something ferromagnetic!

Here’s a completed picture frame, hanging on a wire bookshelf.

Follow this link for full instructions.

Build your own Flower Robot!

Finally!

Now you can build your own robot! Carnegie Mellon University’s Robotics Institute, USA, has released its recipes to build robots as home.

Using TeRK (Telepresence Robot Kit), you can find all pieces you need and even adapt others parts to do your own robot.

Right now, they have 4 recipes:

Qwerkbot Classic (The Qwerkbot Classic is the simplest mobile robot that you can build using a Qwerk processor. Utilizing the holes in the Qwerk enclosure as mount points for two motors and a caster the Qwerkbot recipe literally turns your Qwerk into a robot.)

Qwerkbot+ (The Qwerkbot+ adds a pan-tilt head to allow independent motion of the camera and robot base. This version is somewhat more challenging to build than the Qwerkbot Classic.)

AC Power (The AC power Adapter allows you to power a QweRK from an ordinary AC wall outlet.)

Flower (The Flower is a stationary robot with seven degrees of freedom. Once you have built the Flower, you can use TeRK’s Robot Universal Remote and Flower Power software to program its movements. You can program your Flower to rise or wilt and program the motions of its petals. Because the Flower is equipped with IR sensors on three of its petals, it can track objects moving in front of it. It can even catch a lightweight ball.)

While all others bots are for beginners, the Flowers is quite more complex and you can spend 10 hours building it.

But, how cute is that!

Flower Robot

They also have softwares for controlling your TeRK robot, like this Flower Plower to program your Flower Robot.

Flower Power Software

Actually, the robot’s secret is the internal electronic controller Qwerk, a microcomputer using Linux to control all cameras, USB devices, engines and sensors. The robot’s sftware is Open Source and you can use virtually any computer language.

Oh, yes! There are bad news… Now, they are selling the kit just in US. By the way, the Flower Robot Total cost of parts is $725,00.