Thoughts and experiences on various topics: puzzles, games, AI, collaboration, music, politics, and whatever else is on my mind

Software Developer (Gensym 1997-1998)

In January, 1997 I found a job as a software developer (programmer) at a small company called Gensym (not to be confused with the biotech company Genzyme!).  Gensym developed an expert system product called G2, which it sold to large corporations.   Gensym did its internal development in CommonLISP, which was great for me since that was (and still is!) my primary language.  Deployment was done in the C language, with cross-compilation for multiple platforms.  To accomplish this, Gensym used a Lisp-to-C translator (created by a different company).  I was hired to work with my boss (who was an amazing and accomplished programmer, as well as an all-around great guy!) on building Gensym’s own in-house Lisp-to-C translator.  Of course this translator was being written in Lisp, and I learned a lot of C in the process of working on the project.  This was not research by any stretch of the imagination, but it was technically challenging and interesting work, and I really enjoyed collaborating with my boss, who had designed the translator, and actively worked with me on the implementation.  I learned a lot, and enjoyed the first year immensely!

Unfortunately Gensym started to hit trying times, and after a year my boss became disillusioned with management and chose to leave.  This left me in a quite difficult position – I was not fully up to taking over the translator project on my own, so I ended up transitioning to a more “standard” developer position – doing bug fixing and feature coding directly on the G2 product.  I was not particularly good at this, and my heart was not in it, so my second year at Gensym was a downward spiral, ending in my own decision to leave later that year.

Free-lance puzzle consultant / designer (1998-2001)

I had tried teaching (Hampshire), research (GTE Labs), programming (Gensym), but now I had thoughts of pursuing my puzzle passion as a free-lance consultant and puzzle designer.

I had tried to sell a few puzzles in the past, but only in passing, and not very successfully.  My first non-trivial sale was modifying and licensing a “sliding block puzzle” search engine that I had developed for fun over the preceding years.  ThinkFun (maybe it was still named Binary Arts at that point), used my search engine to analyze and design puzzle levels for their Railroad Rush Hour puzzle (a sequel to the enormously popular Rush Hour puzzle by Nob Yoshigahara).  I ended up designing a few levels myself, and received a credit on the box of the game when it was released (though you might need a magnifying glass to find it).

In the early 1990’s I also published a few puzzles in my favorite puzzle magazine: Dell Champion Variety Puzzles  (sadly now out of print).  I started with RoundTrip path puzzles, invented and first published by a puzzle author using the name Stitch (that’s his “nom” in the National Puzzler’s League, which I later also joined – my “nom” is now Macro).  I started out simply writing (for fun!) a program to solve RoundTrip puzzles.  It then occurred to me that I could use the solver as part of a puzzle generator.  As often is the case with fun “hacking” projects, I kept adding new features and variations.  I had the idea of changing the geometry from square/rectangular to triangular/hexagonal.  You can see samples of my puzzles (under the name Grand Tour) on my web page:

http://glenniba.com/grandtourhexbranch/GrandTour.html

I wasn’t sure if I could publish Round Trip puzzles in Dell Champion Variety Puzzles (or any other magazine), since I did not originate the puzzle idea itself, not to mention possible issues with using the name “Round Trip”.   When I contacted Dell about this, they aid it was fine, and encouraged me to to send in puzzle submissions.  So I sent them a batch of both square and hex RoundTrip puzzles.   Later I sent in some “Dominoes Logic” puzzles (both square and hex variants) that I wrote a different program to generate.  These puzzles began to appear in the magazines.  The most amazing result happened once while I was on a plane trip:  I was reading the In-Flight magazine, and I saw a Round Trip puzzle!  Wow, I thought, someone else published a round trip puzzle!  Then I looked, and the name was mine!   Turns out Dell had “re-printed” my puzzle in the flight magazine.   I didn’t know they could do that, but I didn’t complain — I was pleased to have my puzzles (and name) getting “out there”.

Later I implemented a suggestion by Scott Kim to generate One-Way-Trip puzzles which feature a start and end vertex for the path.  In both types of puzzles the object is to create a path that connects all the dots (vertices) visiting each dot once and only once.  For RoundTrip puzzles the path is closed, i.e. it returns to its “starting point” (though you can start anywhere – it makes 1 big loop, or a “Grand tour”).  For OneWayTrip, the solution path starts and ends at the specified dots.  My program that generates these puzzles ensures that there is always only 1 solution.  The link to the OneWayTrip Java applet on my web site is:

http://glenniba.com/OneWayTripHexBranch/OneWayTrip.html

The JavaApplets provide puzzles of different sizes and both square and hex geometries.  They range from simple to very challenging!

Jumping ahead a bit in the story, I later wrote a book titled  Round Trip Puzzles  (published through Sterling in January 2011).  Following that, my son, Aaron, and I wrote an iphone logic puzzle app called  Monorail, which has hundreds of challenging puzzles of this type (it’s also out for Android, now, too – but be sure to look for the Monorail by IBA Puzzles  (there is another app that uses the same name, which only creates confusion).  Here is link to my Monorail puzzle page (where you can find info about both the RoundTrip puzzles book and the Monorail apps for smartphones):

http:// glenniba.com/monorail/

Making a puzzle variation of Tetris  (1989-present)

Another puzzle project I worked on, which I consider potentially my “magnum puzzle opus”, is an extremely challenging version of the game, Tetris.  When Tetris appeared in the late 1980’s (I’m thinking I first started playing it on MacSE’s around 1989),  I was instantly addicted.  I loved the music (Russian folk songs) and the video game challenge (play as fast and survive as long as you can).  At GTE Labs we actually formed a Tetris Team and I remember we had a “match” against the team from MITRE Corp.  Great fun.

I wasn’t satisfied to simply play the existing version(s) of Tetris.  I wanted to try out my own variations.  So, naturally, I started programming my own Tetris simulator, first running on Lisp Machines, and later on Macintoshes.  With my own simulator, I could vary all sorts of game parameters such as:  board width, and height, piece set (no reason to limit pieces to size 4 — I supported both smaller and larger pieces, too), speed of the game.

While playing around with this simulator, I came up with a novel challenge:  to wipe out the Tetris board, i.e. eliminate all the cells (in Tetris, if you don’t already know, filled rows are cleared and the cells eliminated – then the rows above any cleared rows will move down to take up the cleared space).  The typical objective in playing “normal” Tetris is to survive as long as possible, and score as many points as you can.   This wipeout idea provided novel puzzle challenge, and it appealed to me because it was something you could succeed at (rather than postponing inevitable failure when the board fills up).  I implemented this in my simulator, and discovered that it was great fun (for me at least) and required developing a variety of skills to become “expert” at it.   Accomplishing a wipeout is extremely difficult in original Tetris, or any variation where the next piece is chosen randomly.  This makes it nearly impossible to plan ahead more than just 1 or 2 moves.  I decided to make the moves deterministic (predictable) and this worked quite nicely.   I found that even the simplest deterministic variant (where there was only a single piece type, and you’d always get that piece, was both interesting and challenging.  My experiments led me to discover that board widths 5, 6, and 7 led to interesting and enjoyable puzzle challenge, especially combined with a choice of piece such as “T” or “L” (2 of the standard Tetris pieces).  I also introduced the idea of piece reflection, which makes solving easier or harder depending on whether or not reflection is permitted.

I came to think of this Tetris-inspired puzzle challenge as a kind of Dynamic Tiling Problem  which generalizes the static tiling problem of filling a specified area with a particular set of piece shapes (eg. fill a 4×4 square grid with 4-cell T pieces, or fill an 8×8 grid with 4-cell  L pieces).  In dynamic tiling the Tetris row-clear operation dynamically modifies the fixed cell pattern.

Later, when the Nintendo Entertainment System (NES) came out, it included Tetris, and I spent numerous hours (really should be measured in months and years) playing the game.  One day, in order to challenge myself, I posed the question (remember: – Think deeply about simple things!):  Might it be possible to fill cells on the Tetris board that are not supported by (or connected to) other cells or the base of the board area?  This amounted to what I call “floating a piece (or set of cells) in mid-air“.   It is natural to think that there is a kind of gravity operating in Tetris, especially since pieces fall (slowly at first), and you can drop pieces (in which case they keep falling until some part of the piece lands on some kind of support (another fixed cell, or the base of the board).  But deeper examination revealed that row-clearing obeys a different rule of gravity.  The row-clear rule is that all the cells above a cleared row (or rows) move down exactly a number of cells equal to the number of rows cleared below them.   So, in particular,  cells above a cleared row do not keep falling until they touch a support!   So naturally, I set about trying to prove that this was possible, and before long I had learned how to create a platform (rows that could be cleared by placing a piece in a hole in the platform), and could use the platform to support a piece – and then, after clearing the platform, have the piece placed on the platform end up “suspended in mid-air”.

I used this discovery to create a Target variation of my Tetris-inspired puzzle, and I named it Target Tiling.   Instead of an empty pattern (wipeout)  being the target, why not have certain cells  (Target cells) be marked (specified) and have a more general objective of contstructing that exact target pattern  (each of the marked target cells must be filled, and no other cells can be filled).   This provided for lots of additional challenge, including the goal (in some target patterns) of suspending cells in “mid-air”.   I considered names such as Tetris Architect  (because you are building up a target pattern according to a “blueprint”), and also Tetris Target,   I think has a nice ring to it, but finally settled on Target Tiling because the name Tetris is trade-marked.

There are many levels of skill one can acquire in mastering Target Tiling.  At the low level there is learning to use the controls to manipulate and place pieces.  Then there is the standard Tetris skill of filling and clearing rows, and uncovering covered “holes” so they can be filled.  Then there is the “working down” skill — reducing a board pattern of many rows to a simpler one with just 1 or 2 rows left.  Next comes the skill of wiping out the board,  which requires much more precise play, and often involves learning lengthy sequences of “moves” (macro-moves)   that accomplish desired transformations, simplifications.  Finally there is the target constructing skill which requires building up the target pattern row by row, and finally wiping out any excess above the top target row (carefully!  since you don’t want to mess up any of the completed target rows below!).   I think this game would be ideal for teaching meta-skills for learning and problem-solving.   I also believe it would make a great testbed for AI skill learning research, and I hope to work on this sometime soon!  If  this sound interesting to you, please contact me (giba@alum.mit.edu) — I’m always looking for collaborators!

You can actually try out my game!  I have posted a free version of Target Tiling on my website, and you are welcome (actually encouraged!) to play it and let me know what you think.  The game has evolved, and now includes a 3D version with 3D pieces.    The latest version has piece sequences (some pre-set for you to choose among), but also lets you pick your own piece sequences.  You can use randomized Start and Target board configurations, or you can edit either or both of these patterns to try out your own specific patterns.  You can find information about the game, the CommonLisp source code, instructions on how to run it, and lots of puzzle challenges,  all at my web page:

http://glenniba.com/target-tiling.html

I made a serious effort to sell this game idea to The Tetris Company, back in the mid-to-late 90’s, but ultimately they turned me down.  Later I tried again with Microsoft, after I learned that Alexey Pajitnov (the original creator of Tetris!) worked there, but sadly, he left Microsoft before we could get a deal in place (even before I got to show him the game, which I would still love to do – does anyone know how to contact him?)

Full Circle – back to ESG at MIT, now as an instructor! (2001- 2004)

In 2001, my oldest son, Aaron, enrolled at MIT as a freshman.  I wasn’t making enough income from my puzzle work to be self-sustaining, so I contacted ESG and was able to get part-time employment there as a Lecturer (staff instructor).  This did not pay particularly well (think adjunct salary level), but the major benefit was that we got a pro-rated tuition break on my son’s MIT tuition, which was a huge financial plus!   I mostly was teaching basic math courses (calculus), but got to teach the occasional seminar on puzzles, or AI/Machine Learning research.  I even got to work with some undergrad students on UROP (Undergrad Research Opportunities Program) projects.  This was great fun, and I enjoyed being closely connected with both ESG and MIT once again.

to be continued …

Next up:  Divorce (2002) and freedom!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Tag Cloud

%d bloggers like this: