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

Alert readers will have noticed that my blog-posting schedule slipped last Sunday — I had promised to discuss the Power of Collaboration,  but it turned out that one of my current  collaborators was visiting from out of town.  So instead of writing about collaboration, I actively engaged in some fun and collaborative work!

I have been mostly self-employed for the last 15 years.  Working from home has distinct advantages, among them not having to commute, and having the freedom to set my own schedule.  The biggest downside I’ve encountered is a lack of collaborators to work with. My experience is that I’m many times more productive when I’m collaborating on some project, so for the last 5 years or so I’ve been actively seeking out collaborations.  I’ve been fortunate in the last 3 years to have found a number of excellent collaborators, and have been engaged in some really exciting projects:

1.  Monorail iPhone puzzle app  — a collaboration with my son Aaron during 2011.

2.  Android version of my Target Tiling (Tetris-inspired) puzzle app  — working with one of my brother’s former students.

3.  Working on a new iPhone puzzle app — as part of a team assembled by an MIT classmate of my son’s.

4.  Researching techniques for solving very large search problems — collaborating with my brother, Wayne, who is a CS professor at Westmont College.

The last 3 of these are actively ongoing, and I plan to write more about them in future posts.

The Power of Collaboration

It seems fairly obvious and natural (as a general rule) that 2 or more people working together can accomplish more than any one person working alone.  They can share the work and thus accomplish more.  But my experience is that the productivity of collaboration is not additive, but is in fact multiplicative.  When I’m working with a collaborator, I estimate that I am at minimum 10 times more productive  and sometimes even more than that!  My intent in this note is to examine how this works, and why it is the case.  I will be focusing on 2-person collaborations since that is what I have the most experience with.

Advantages of collaboration

1.  Dividing up the work

2.  Synergy of knowledge, skills, and ideas

3.  Maintaining focus and commitment

4.  Avoiding prolonged periods of being stuck on something

Dividing up work

If there is a fixed amount of work to do for a project, then 2 collaborators might be expected to accomplish it in half the time.  This assumes that both collaborators are equally capable of doing all of the work themselves with comparable efficiency.   If the collaborators are specialized so that each works best on separate sub-tasks, then dividing the work according to these specialties yields a greater than 2-fold increase in productivity.  In the most extreme case, imagine that neither collaborator has all the skills needed to do the project / task.  Then the time for either one working alone would be infinite!   But working together, if their skills together cover what’s needed, they can accomplish the task collaboratively in finite time.  That’s quite a speedup!

Synergy of knowledge, skills, and ideas

The knowledge and skills of even a 2-person team can be much greater than that of either individual alone.  Beyond dividing tasks according to respective expertise and specialization, the collaborators can share their knowledge and skills with each other so that each becomes individually more productive as well!  This seems very similar to the power of community learning environments (such as ESG at MIT), where the shared knowledge within the community enhances the knowledge of each individual community member.  There is also synergy of ideas — collaborative brainstorming can be both fun and productive, with each collaborator contributing ideas, and feeding off of (reacting to) the ideas of the other.  When it comes to evaluating ideas, having 2 points of view can be beneficial as well.

Maintaining focus and commitment

I have a very great tendency to get distracted (I’m probably ADD or something along those lines).   When I’m actively collaborating (in realtime) with someone, I find that I’m much more able to maintain focus and “stay on track”.   Even when not in realtime, it is still helpful to have a commitment to one’s collaborator — putting off or avoiding things is letting your partner down.

Getting unstuck more quickly (avoiding staying stuck for prolonged periods).

A very specific and powerful aspect of collaboration is reducing the length of stuck times!   When working on a task alone, I often run up against obstacles which stump me (sometimes for prolonged periods).  This can occur for many reasons, including lack of a specific skill or piece of knowledge, or simply not being able to immediately solve some challenge.  Very often, one’s collaborator can offer a key insight or suggest a useful tool or mechanism that gets me quickly unstuck.  Without that outside help, I am much more likely to stay stuck for an extended period.  Similarly, my collaborators can often “rescue” me from pursuing a dead end, by helping me recognize earlier on that it’s either hopeless or unproductive.

Some slight disadvantages of collaboration

There are also a few small disadvantages of collaboration, for example:

1. Overhead in scheduling / finding time to work together

2. Having to compromise (sometimes involving lengthy discussions to resolve differences)

But overall I find that the powerful benefits of collaboration far outweigh any disadvantages!

Next week:

Collaboration “case studies” — exploring more concretely some of my experiences in working with collaborators.

Today I’ll wrap up the current discussion of Target Tiling with a look at how to achieve symmetry.  Also, I’ll describe something I call pseudo-symmetry,  which is similar to and behaves somewhat like symmetry.

Achieving Symmetry

For Target Tiling on a board of width = 5, there are a total of 32 different row patterns (5-cell patterns of filled and empty cells).  Of these, there are 8 that are left-right mirror symmetric (they are the same when order of cells is reversed).   Last week I illustrated the 6 “non-trivial” symmetric patterns (omitting both the empty pattern and the completely filled pattern).  That leaves 24 row patterns that are non-symmetric.    These non-symmetric patterns match up into groups of 4 related patterns:  each group containing the 2 mirror reflections of one non-symmetric pattern, each occurring twice — once with the center cell filled and once with the center cell empty.  So fundamentally there are 6 different asymmetric patterns (each generating a related group of 4 out of the 24 patterns).

The next image illustrates all 6 possible non-symmetric row patterns (with center-cell empty, and omitting the mirror reflections):

Canonical asymmetric rows (with center cell empty)

Canonical asymmetric rows (with center cell empty)

Each of these asymmetric patterns (and the variants with reflection and center filled) can be first transformed into a symmetric pattern, and then cleared by a symmetric wipeout using the symmetric macro-operators described in my blog post last week.

I will present an illustration  using a single 1-cell pattern, starting with just a single cell in the 2nd row (1 cell left of center).  Here is the starting board position:

Start pattern for example of achieving symmetry

Start pattern for example of achieving symmetry

This non-symmetric pattern can be transformed into a symmetric pattern with just 2 T-piece placements. The first T piece is placed to the right with its stem pointing right, which yields this position:

After first T-piece is placed at right

After first T-piece is placed at right

Now place the second T piece to the left with stem pointing up, yielding this symmetric position (before the filled row clears):

Symmetry achieved (before row clear)

Symmetry achieved (before row clear)

After the filled row clears, the pattern is still symmetric:

Symmetry achieved (after row clear)

Symmetry achieved (after row clear)

This symmetric pattern can be wiped out with the application of symmetric macro-operators as discussed last week.

The macro-level description could be:

Repeat 2 times:  DO  [ Clear-Center-Hole    +   Clear-3  ]

This takes a total of 14 moves.

Transforming Pseudo-symmetry into Symmetry

Here is a second example, of clearing a non-symmetric pattern by first transforming it into a pseudo-symmetric pattern (symmetric if rows were superimposed on one another).

To illustrate this, consider the challenge of clearing a T-shaped start pattern (where the T is off-center to begin with):

Start with off-center T at right

Start with off-center T at right

This position is non-symmetric.  There is an easy pattern I discovered for clearing it, though.  The first move is placing a T on the left with stem down, achieving a nearly symmetric position (what I call pseudo-symmetry):

Pseudo-symmetric pattern after placing T at left

Pseudo-symmetric pattern after placing T at left

The only feature that breaks symmetry here is that the single filled cells in the left and right columns are in different rows.  Ignoring this difference, the position is symmetric.  It turns out that this can be transformed into an actually symmetric position with 2 moves.  The first move is to place a T at far right with stem in so as to fill the hole at the right of the 2nd row.

After filling hole at right (but before row clear)

After filling hole at right (but before row clear)

When the row clears we arrive at this pattern:

After row clear

After row clear

Now a 2nd T piece placed at the left (with stem pointing right) yields a true symmetric position:

Symmetric position after T placed to fill left hole

Symmetric position after T placed to fill left hole

This symmetric position can be wiped out with just 1 more piece filling the T-shaped hole.

There are many more patterns to learn, but with practice, one builds up skills for clearing all the non-symmetric patterns.

My experience is that symmetric patterns are significantly easier to clear, so it is worthwhile to learn how to achieve symmetry from non-symmetric patterns.

Check out Target Tiling — it’s free, it’s fun, and it’s fantastically challenging!

Instructions on how to download and run my game are on my web page:

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

Next Week:  The Power of Collaboration

Using symmetry to solve width 5 Target Tiling puzzles using the T-piece

By symmetric positions, I mean board patterns that have left-right (reflective) symmetry, that is, they are unchanged if the order of the columns is reversed.  In a symmetric board position, every individual row will itself be symmetric.   But of course not all patterns will be symmetric, so for those non-symmetric patterns, the challenge is to achieve symmetry.

Why is symmetry useful in the first place?

It would be pointless to achieve symmetry unless there were something to be gained by it.  In fact there is a lot to be gained:

1.  There are far fewer symmetric patterns than non-symmetric ones.

2.  It is easier to recognize familiar symmetric patterns.

3.  In solving symmetric positions, it is possible to do so while maintaining symmetry!

4.  The number of “operators” that maintain symmetry is much smaller than the set of all available operators, so there are fewer choices of what to do at each point (in search terms, the branching factor is smaller).

Exploiting symmetry

Taking advantage of symmetry has two parts:  achieving symmetry,  and then maintaining symmetry while simplifying and solving.  I will discuss each of these after presenting some examples.

Examples of symmetry

Here is one example of a symmetric position with 6 partially filled rows:

Symmetric board illustrating all 6 possible symmetric rows (except filled and empty)

Symmetric board illustrating all 6 possible symmetric rows (except filled and empty)

In fact, every possible symmetric row pattern appears in this diagram.  There are 6 such symmetric row patterns.  Notice that rows 3 and 5 (counting from the bottom) are the cases I discussed last week:  Center-hole, and 3-in-the-middle, respectively.   I explained how each of these patterns could be cleared by an appropriate macro-operator:  the Clear-3 macro for the 3-in-the-middle pattern, and the Clear-Center-Hole macro for the Center-hole pattern.  It is possible to learn a “clearing macro” for each of the other 4 row patterns, as well.

Solving While Maintaining Symmetry

The key to maintaining symmetry is to only place T-pieces so that the result is still symmetric. There are 2 cases I find useful:

1.  Placing a single T-piece in a symmetric position

This can only be done in 2 ways, since there are exactly 2 rotations of the T-piece that are left-right symmetric, and the piece must be placed exactly in the center (straddling the center the column).

Symmetric placement of T-piece:  in center with stem-down

Symmetric placement of T-piece: in center with stem-down

Symmetric placement of T-piece: in center with stem up

Symmetric placement of T-piece: in center with stem up

2.  Place two T-pieces so that together they form a symmetric pattern

Again, there are only 2 ways to do this.  The pieces cannot cover any of the center column, since they would both have to cover the same cell, which is not possible. Here are the 2 placement patterns:

2 Symmetric T-pieces, stems facing in

Placing 2 T-pieces symmetrically, stems facing in

Placing 2 T-pieces symmetrically, stems facing out

Placing 2 T-pieces symmetrically, stems facing out

Either of these 2-piece macro-operators will maintain symmetry when they are applied to any symmetric position. Taken together, this set of 4 operators (2 single-piece + 2 double-piece) are sufficient to solve (i.e. Wipe Out) any symmetric starting position. Let’s give names to these operators:  T1-Stem-Down,  T1-Stem-Up, T2-Stems-In, and T2-Stems-Out, respectively. Looking back to the examples from last week, we can see how the macros Clear-3  and  Clear-Center-Hole  are actually composed from these 4 operators:

     Clear-3   =   T2-Stems-In  +  T1-Stem-Down

and

    Clear-Center-Hole  =  T1-Stem-Down  +  Clear-3

where “+” means “followed by”.  Note that any macro-operator composed from symmetric operators will itself be symmetric!

Solving the Illustrative Symmetric pattern we started out with:

Symmetric board illustrating all 6 possible symmetric rows (except filled and empty)

Symmetric board with all 6 possible symmetric rows

We start by applying T2-Stems-In to arrive at:

Result of applying  T2-stems-in operator

Result of applying T2-stems-in operator

Next it is natural to apply T1-stem-down (since there is a “T-shaped hole” in the middle of the top 2 rows):

Result after T1-stem-down

Result after T1-stem-down

Now, the top row is a “3-in-the-middle” which can be cleared by the Clear-3 macro, yielding:

After Clear-3 macro operator

After Clear-3 macro operator

Here the top row is a “Center-Hole” pattern, which can be cleared by the Clear-Center-Hole operator to leave:

AFter Clear-Center-Hole macro

AFter Clear-Center-Hole macro

Dropping a T-piece with stem up into the middle of this pattern transforms it into:

After T1-Stem-Up

After T1-Stem-Up

Filling the 2 holes with 2 T-pieces using T2-Stems-Out, reduces the pattern to 2 cells in just a single row:

After T2-Stems-Out

After T2-Stems-Out

Almost there!  A simple T1-Stem-Down fills the center hole, and yields 2 rows of “3-in-the-middle”:

After T1-Stem-Down

After T1-Stem-Down

The final two rows, each being examples of “3-in-the-middle”,  can be cleared by two successive applications of Clear-3.

That solves the puzzle!!   Notice how the positions remained symmetrical at each stage of the solution.  Typically rows were cleared one by one.

To be continued …

Next time:  Achieving Symmetry (transforming non-symmetric patterns into symmetric ones)

Last week I discussed an extremely advanced Target Tiling challenge.  This week I’d like to introduce and discuss some simpler strategies for solving basic Target Tiling wipeout challenges.  The two key ideas are:

1.  Learning Macro-patterns

2.  Achieving and exploiting symmetry

Each of these techniques helps simplify the solving of wipeout challenges.

Discovering and using macro-operators

You may recall from previous posts that a macro-operator is a fixed sequence of simpler operations that achieves a specific transformation.  I’ll illustrate this with something I call the Clear-3 macro.  It applies in the WipeOut Challenge using the T-piece on a board of width 5.   Here is the starting board state for the macro:

Start of Clear-3 Macro

Start of Clear-3 Macro

It is natural to try filling the right and left holes as follows:

Left hole filled, about to fill right hole

Left hole filled, about to fill right hole

Then, after the filled bottom row is cleared, we arrive at this position:

[Note that for today’s discussion, we are using the original (single row) version of the Row-Clear Rule]

WipeOut coming with next move!

WipeOut coming with next move!

This is just 1 move from a WipeOut  (clear board).  The last piece (the 3rd in the macro sequence) clears the remaining 2 rows:

WipeOutDone

Note that the difference between the start and the final positions is the removal of the 3 filled cells in the middle, hence the name Clear-3.

The Power of Macros

The Clear-3 macro allows us to clear any row of 3 filled cells situated in the middle of the width 5 board, using T-Pieces.  As an example, suppose we have a rectangle formed by 4 rows of “3 filled cells in the middle” of each row, as in the next diagram:

4 Rows of "3 in the Middle"

4 Rows of “3 in the Middle”

This pattern can be easily wiped out in 12 moves, simply by applying the Clear-3 macro  4 times in succession, clearing each row in turn.  Although the solution involves 12 piece placements,  conceptually it is very simple:

    Repeat 4 times:  Do Clear-3

The fundamental power of macros is that they allow planning at a more abstract level (hiding or ignoring low-level steps in the planning / problem-solving process)!

Using Clear-3 to solve a new problem

What if we are faced with this next position, where a row is filled except for a “hole in the middle”:

Row with 1 hole in middle

Row with 1 hole in middle

A single move (placing a T-piece stem-down into the center hole) yields the familiar “3 in the Middle” position:

Row of 3 in the Middle

Row of 3 in the Middle

This can be eliminated (WipedOut) with a single application of Clear-3.  Note that the sequence involves 4 Piece placements, but conceptually is just 2 steps (fill hole  +  Clear-3).

This 4-move sequence is a new macro, allowing us to clear any row filled except for a hole in the center.  Let’s call this macro Clear-Center-Hole.

Clear-Center-Hole can be applied iteratively, as well.  Suppose the board is filled 4 deep with a column of holes running down the center:

4 Rows of "Center Hole"

4 Rows of “Center Hole”

This starting position can be solved by 4 applications of Clear-Center-Hole.

The entire sequence takes 16 moves, but conceptually it is simple and elegant:

     Repeat 4 times:  Do Clear-Center-Hole

These macros, by themselves, do not suffice to solve (WipeOut) all positions – there are many other patterns, most of which are not even symmetric.  Skill and mastery involves learning patterns for transforming given positions into other simpler / known positions (such as the 3-in-middle and center-hole above).   One technique I’ve found quite useful is to transform positions so as to make them symmetric.  Once symmetry is achieved,  moves can be chosen so as to maintain symmetry, which greatly reduces the number of patterns one is faced with.

To be continued …

   Next time:  Achieving and Exploiting Symmetry in Target-Tiling positions

Continuing from last week: more on my Target Tiling puzzle game (inspired by Tetris), including a novel extension to the Tetris row-clearing rule, a seemingly impossible challenge, and a very surprising solution!

Modifying the Row-Clearing Rule

Recall that in Tetris (which inspired my Target Tiling puzzle game), there is a row clear rule:

After each piece placement, any rows that are completely filled are eliminated,  and the rows above move down to fill the vacant space.

When I had become rather expert at all the earlier variations (varying widths, piece types, piece sequences, and targets), I began thinking about new ways to challenge myself.  I thought about the row clearing rule, and asked myself:

What if it wasn’t enough to fill a single row to get a clear?  What if you had to fill 2 consecutive (adjacent) rows before they would clear? What if the threshold was 3 rows?  or 4 rows?   This seemed like an interesting challenge, and also related to the notion of Tiling (with pieces)  which conventionally involves completely filling a given space with available pieces.   So I implemented this variation of row-clearing in my simulator, generalizing the row-clear rule to an  N-row-clear rule (where N could be 1, 2, 3, or 4):

When N (or more) consecutive rows are completely filled, they are cleared as with the original row-clear rule, with any higher rows moving down to fill the emptied space.

NOTE that when N=1, this rule is exactly the original Tetris  rule for row clearing.

It turns out that the variants of row-clearing with N= 2, 3, and 4 are interesting and present some quite complex challenges.  I started playing with N=2 (Double variant), and learned new patterns for solving the various width, piece, and target patterns.   When I felt proficient with that, I advanced to N=3 (Triple), and finally N=4(Quadruple).

A Nearly Impossible Challenge

When I tried the N=4 (Quad) variant of Width=5 using T-pieces, I thought I may have reached the limit of solvability.  I was stumped for quite a long time, and was close to giving up, declaring it “too hard, and maybe impossible”.   Then, one day, I tried something desperate – a totally counter-intuitive Tetris piece placement,  and low and behold, this enabled me (with long macro-sequences) to actually solve it!

Here is an example position illustrating what was stumping me for the longest while:

This stumped me for a long time!

This stumped me for a long time!

Everything I tried seemed to lead nowhere.  I was about to give up, when I discovered this extremely counter-intuitive T-piece placement.  This discovery led eventually to a solution to this and other Width=5 T-piece Quad puzzles!

A Surprising Counter-Intuitive Discovery!

A Surprising Counter-Intuitive Discovery!

This placement is counter-intuitive because it violates the natural Tetris heuristic:

      Try not to create any covered holes!  

This piece-placement violates that heuristic by creating 2 covered holes!  On first examination, it looks like it fails to get closer to filling any rows.  The surprise was that the top row is filled except for the hole in the 2nd position, and this top row can be eliminated (by first achieving symmetry and then wiping out everything above and including this row (without modifying anything in the pattern below).

It takes 9 moves to clear the top row, and another 13 to wipeout the rest, for a total solution in 23 moves (counting the “surprise” move).  Here are some snapshots to illustrate this solution sequence:

After 5 more moves

After 5 more moves

Is this progress?  Look what happens after just 4 additional moves:

Top Row Cleared!

Top Row Cleared!

The Top row (created by the “surprise move”) is now cleared.  This is finally looking like progress!

Down to 1 Row - after 4 more moves!

Down to 1 Row – after 4 more moves!

An additional 4 moves lead to this position, just 1 move from a solved WipeOut:

1 more move to solve!

After 4 more moves – just 1 more move needed to solve!

Placing the last T-piece in the hole will clear the final 4 rows, leading to an WipeOut (empty board)!

This solution took a total of 23 piece placements starting from the original Stuck Position. 

I was incredibly excited by this discovery.  This “key (surprise) move” insight, and the patterns learned to clear from it, enabled me to solve the entire class of T-piece Width=5 Quad puzzle patterns.  What I mean by solving the entire class is being able to solve (WipeOut) any initial pattern given enough clear board space to work with at the top of the board.  I could also solve the related class of Target problems.  What seemed impossible at first, was actually quite solvable, but required a very specific (surprising and non-intuitive) insight!

Next week:  discussion of some more basic Target Tiling solving strategies (macro-patterns and symmetry)

Thinking Deeply About Logic Puzzles 

If you know anything about me, you know that I’m passionate about puzzles.  I particularly like logic puzzles, by which I mean puzzles that require logical thinking to solve.  In these notes I will try to “think deeply” about puzzles: What is a puzzle?  What makes a good puzzle?  How do I create new puzzles?

What is a puzzle?

There are many different types of puzzles, but the primary common feature is that they  have a solution!  Some puzzles explicitly define the elements of the puzzle and the valid operations or moves.  Other puzzles don’t even make clear exactly what the goal is, and part of the puzzle is to “figure out just what the puzzle is”.  Still other puzzles have hidden elements that may get revealed (e.g. MasterMind, or puzzle boxes with hidden mechanisms).  Math problems and scientific research projects can also be viewed as kinds of puzzles, some explicit, others very open-ended.  There are jigsaw puzzles where one has to use piece shapes and visual clues to assemble a target picture.  There are popular paper-and-pencil puzzles (like KenKen and Sudoku).  With the development of computers and videogame systems, there are now a wide range of interactive puzzles (and video games).

I personally am particularly interested in puzzles which are explicitly stated (goal is clearly defined, and the elements and operators are well-defined), and can be solved by logical thinking.  I don’t particularly care for puzzles with hidden goals or hidden elements.  Nevertheless, the class of explicit puzzles is quite broad .   I enjoy physical puzzles, paper-and-pencil puzzles, and interactive (computer and smartphone) puzzles, among others.

A Few of my Favorite Puzzles

1. Physical puzzles:   Rubik’s Cube,  Hi-Q Peg Solitaire, Hi-Q Dominos, Rush Hour, numerous other sliding-block-puzzles  (and many more!)

2. Paper and Pencil puzzles (newspapers, magazines, books):  KenKen,  Sudoku, RoundTrip and OneWayTrip (Monorail type path puzzles)

3. Computer and videogame puzzles:  Tetris,  Target Tiling (my Tetris-inspired puzzle game), many of the Soleau Software puzzles, plus my Grand Tour (Monorail/RoundTrip), and One-Way Trip applets.

4. SmartPhone puzzles:  here is a link to My Favorite Interactive Logic Puzzles.  I especially love Vubu, Relix, BoxedIn, Blockhouse, and Monorail, but all the puzzles listed are great (imho)!

What Do I like about these puzzles?

a.  They are challenging and fun to solve

b.  Most involve visual / geometric elements

c.  I can develop skills and expertise at solving  (a variety of reasoning strategies that can be learned!).  Best of all if there is a hierarchy of skills!

d. They are reasonably time-limited (typically solvable in hours — not days, weeks, or years)

Creating a new puzzle – case study of Target Tiling (inspired by Tetris)

I became a Tetris addict when it appeared back in the late 1980’s, playing first on the Mac SE, later on the NES (Nintendo Entertainment System).  I loved the geometry, the challenge, and even the music (Russian folk tunes)!   I was inspired to write my own Tetris simulator, so I could experiment with variations of the game.  Over time, this project grew into a rather rich and extremely challenging interactive puzzle game (my Target Tiling – available for free download from my web site)

1. Identifying the elements:

Board size (Tetris had a fixed 10-wide board),

Pieces (Tetris had 7 pieces, each covering 4 grid cells) that could be rotated and placed in position

Row-clearing rule (completely filled rows are eliminated and the cells above move down to fill the vacated space)

2. Playing with (varying) the elements

Once I had written a general-purpose Tetris simulator, I began varying and playing with the elements.   I tried different board sizes, both narrower (4, 5, 6, 7) and wider up to 20 or 30.  I introduced different piece shapes,  again, both smaller (1, 2, and 3-cell pieces), and larger (the full set of Pentomino shapes, which cover 5-cells each).  I also varied the speed at which pieces would fall on their own, but I found I much preferred slower speeds (I also included a “Pause” feature”) – in general I’m not a big fan of timed puzzle solving or games – I prefer to think in a more relaxed mode.

3.  Varying the puzzle objective

Tetris is fundamentally a game of survival — typically the pieces speed up until they fall so fast that you can’t control them, at which point the board “fills up” and you lose.   I much prefer puzzles and games that I can “win” (solve).   At some point I latched onto the challenge of “completely clearing the board”.   I thought this made a nice clear objective, and provided satisfying closure when achieved!   I first tried this (as a self-defined objective) in Tetris on the NES, but it was extremely difficult to achieve because the “Next Piece” was always chosen randomly – so one couldn’t plan ahead very far.   I’d try to achieve a board pattern with the “bottom rows” filled except for a “hole” in the shape of one of the pieces.   Even doing that is quite difficult, but once accomplished one has only a 1-in-7 chance of getting the necessary shape as the next piece.  It struck me that this “puzzle objective” (clearing the board) would be much more interesting if the next piece was chosen deterministically, as this would allow planning.

4.  Simplification  (thinking deeply about simple things)

So I experimented with various simplifications / modifications

a.  Make the board width smaller (5, 6, and 7, seemed to work well)

b.  Use just a single piece type (this was the simplest way to make the next piece choice deterministic – you always get the same piece shape!)  Through experimentation I found that the T-piece and the L-piece (or J-piece) seemed the most interesting.  The Z-piece was impossible (on a 2D board), and the 2×2 square and the 1×4 “I”-piece seemed rather boring.

5. Skill learning

Using the T and L pieces on boards of width 5, 6, and 7 turned out to be very challenging and interesting.   Over time, I was able to develop skills that let me reliably and fairly quickly solve these puzzles.   I used a random start position (formed by dropping a specified number of pieces of the given type), and would then proceed to work the pattern down (reducing the number of rows) and finally clear the final bottom rows.  I found this both challenging and immensely enjoyable.   I particularly like the set of skills I developed that made me an “expert” at these puzzles!  These skills formed a natural hierarchy, with higher-level skills building on and using lower-level skills.  At the lowest levels there are standard Tetris skills (using the controls to rotate and place pieces in desired target locations, and exposing and filling “holes” to reduce the height of the remaining cell pattern).   The final “WipeOut” skill (clearing the board exactly) involved learning to recognize specific “solvable patterns” and applying the associated move-sequences (macro moves) to solve them.  Some of these macro-moves simply transformed one recognized pattern into another (simpler) pattern that could then be solved by subsequent macros.

6. Adding incremental complexity

After I became skilled at these basic puzzles, I started thinking about adding new challenges.

a. Multiple pieces

I tried a variation using both the T and L pieces (alternating so that the piece sequence was still deterministic so as to allow planning).  Having 3 or more pieces can be extremely challenging, even when still deterministic, but experimenting with those possibilities led to a virtually endless set of rich challenges.  I even tried returning to the complete set of 7 original Tetris pieces (presented in a deterministic fixed / cylic order) – that was difficult but still a fun challenge, though I still preferred narrower boards — width 10 gets rather tedious and takes a really long time to solve.  I found that widths 5, 6, and 7 were most enjoyable.

b.  Target Pattern (generalization of WipeOut)

At some point it occurred to me that I could generalize the puzzle objective from WipeOut to achieving a specified Target pattern (a particular set of marked cells to be filled).  The WipeOut objective could be viewed as the special case of the “Empty Target pattern”.   Initially, I would specify some cells to be left filled in the bottom row.  This led to a new level of skill based on doing a “wipeout” in “mid-air”.  Let me explain.   If the target was a single cell in the bottom row, for example, then one could begin by doing a full WipeOut (clearing the board), but this would not “solve” the target puzzle, since the target cell is empty, and needs to be filled.   Next, one could place a piece so that it covered the target cell, but no other cells in the bottom row – this might involve “standing the piece on end”, for example.  This fills the target cell, but still doesn’t solve the puzzle — the objective is to match the exact target pattern by filling all the marked target cells and no other cells!).   In our example, this can be achieved by wiping out rows 2 and above, while being careful never to fill any of the empty cells in the bottom row — I call this a mid-air wipeout.  It turns out to require concave pieces (such as the T and L) which can then “hang over the side” of filled cells, so as to fill more and more of the rows to be cleared (wiped out).  This introduced an entire new level of skills and patterns!

c.  Mid-air Targets

There was an “Aha!” experience I had while playing Tetris on the NES.   I asked myself it it might be possible to “suspend a piece in mid-air”, by which I mean have piece “floating” without obvious support (either from below, or cantilevered from a filled cell to its right or left).   At first blush, it seemed like there was a kind of “gravity” at work in Tetris, so maybe this was impossible.  But Tetris-gravity is different — when each row clears, cells above that row only move down 1 cell, in particular, they do not keep falling!   So I set myself the challenge of “floating a piece”, and soon discovered that I could create a mid-air platform (2 or 3 nearly filled rows with a piece-shaped hole) cantilevered from a single support cell (that is the row below has 1 cell filled but the rest of that support row is empty).

Here’s an attempt to illustrate:

This graphic shows a platform (rows 2 and 3, not counting the red base row) with a T-shaped hole.  A T-piece is descending in columns 3-5, and will “fill the hole” in the platform:

TargetTilingPlatform

After the piece fills the platform hole, rows 2 & 3 will be filled and so will be removed, and the 4 cells resting on the platform will move down 2 spaces, ending up as “floaters” in rows 2-4.  The floating T-piece will not fall further, it is statically floating:

TargetTilingFloatingPiece

 d.  3-D Geometry

You might notice that the pieces are drawn in a “sort-of” 3D perspective.  In fact, the current version of Target Tiling supports both 3D board grids and 3D pieces.  Check out the game on my web page to try it out:   Target Tiling  (this gets you a page with instructions on how to download and install – it’s all free!)  Eventually I hope to release a version for smartphones, but the current puzzle game runs on MacOSX, Windows, and Linux.  To run it, you need to download the LispWorks PE  (which is also free) – just follow instructions on my page.  If you do try it out, please send me your reactions and thoughts. Thanks!

… more next week

Musical Notes

[Apologies for the “blogslip” this week  (missed my Sunday target)…]

Did I mention that I love music?

I love to listen to music, play music, and have tried my hand at composing/songwriting.

Listening to music

I love to listen to music.  When I’m working on my computer, I love to have iTunes playing in the background.  My favorite genre is blues, but I also enjoy classic and progressive rock, as well as newer groups such as ColdPlay and Muse.  I have a long list of “favorite blues musicians”, but one that I particularly think deserves to be better known is Sherman Robertson, so I’m giving him a special mention.

When I can afford it, I enjoy going to blues clubs, concerts, or outdoor blues festivals.  This August I enjoyed both the Gloucester Blues Festival, and the annual Blues & Brews Fest.  In June I was able to attend my first Chicago Blues Festival (in Grant Park).  The highlight for me was the pre-Festival concert at Buddy Guy’s Legends, where I heard Shemekia Copeland and Kinsey Report (both great!). Also first heard Quinn Sullivan – a young teenage guitar prodigy who is being mentored by Buddy Guy!

I also listen to music on the radio – though the ads get to be extremely annoying.  I regularly listen to Carter Alan’s Sunday Morning Blues on WZLX FM Boston.  My other regular show is Blues Breakers with Tom Marker on WXRT FM Chicago – I listen to this via the Internet.   I regularly record both these radio shows using the service of dar.fm, a free service that usually does a decent job of recording radio shows available on the internet (dar.fm also has a paid service that let’s you record more shows and use more storage to keep recordings longer).  I listen to Sunday Morning Blues “live” on Sunday mornings (9am-noon) when I wake up in time (which I haven’t done consistently of late).  I then listen a 2nd time (or 1st time if I overslept) with the dar.fm recordings after the playlist is posted (usually by Monday or Tuesday).

Playing Music

I love to play music, too!  I started piano lessons around 1st grade (thanks to my father who was my piano teacher!)  Piano / keyboards is still my favorite instrument.  I also studied trumpet from 4th to 12th grades, and even tried Jazz Band at MIT, but I never loved trumpet like I do piano — the piano is just so much more versatile!   I got my first electronic keyboard as a grad student – an RMI that I played through a Fender Reverb amp.  I had fantasies of joining a rock band, and even tried the occasional audition, but never got off the ground with that.   I tried to learn guitar, but never felt comfortable with it — too hard for me to memorize all those different chord patterns.  I also taught myself recorder, which I found quite enjoyable.  I especially enjoy the Renaissance piano/recorder duets I have, and always am pleased when I have someone to play with (I’m to do either the piano or recorder parts!).  My favorite classical music for piano are Beethoven sonatas, especially my life-long favorite, the Pathetique!  While working at GTE, I enjoyed collaborating with a flute-playing colleague to play the Bolling Suite for Jazz Flute and Piano – a wonderful piece of music.

Song Writing and Improvisation

I enjoy piano improvisation, and have also tried my hand at some song writing.  I wrote a couple songs back in high school, then some more in college.  In the aftermath of my divorce, I channeled my emotions into writing a fair number of songs.  I even audited a song-writing seminar at MIT.   In that seminar, we had to write a new song each week – at first I thought that would be impossible, but it turned out to be fine.   The deadline of “finishing” a song in a week meant that I couldn’t obsess endlessly trying to improve or perfect it.   There is a counterintuitive interplay between “quantity” and “quality”.  Surprisingly, striving for quantity (lots of songs) can also lead to better quality (compared to tinkering with a single song trying to perfect it).  I’m reminded of the writing seminar I participated in at ESG at MIT – we consciously tried to write continuously (stream of consciousness) without censorship.  This ended up being very liberating.   I also recall reading an anecdote (I forget where) about an art teacher who divided his ceramics class students into two groups:  the first to aim for quantity, the second for quality.  The surprising outcome was that those students striving for (and being judged by) quantity, also ended up producing higher quality work!  My “mini-theory” to explain this is that the quantity group is getting more experience by trying more new and different things, and thus also encounters more learning opportunities.

Open Mic nights

This Spring, I dusted off some of my old songs, and started performing them at Open Mic nights in the area.  The Open Mic at Nourish Restaurant in Lexington Center turns out to be very convenient — I only live a block away, and there is already an electronic keyboard there, so I don’t have to schlepp my own!   For better or worse (and often worse in my case), the performances there are recorded, so I now have audio available of many of the songs I’ve performed.

This Summer, I had the great pleasure of collaborating with my daughter Rachel (who is a violinist – music conservatory major).  We performed arrangements of several of my songs, plus a cover of a Bonnie Raitt song.  I really enjoyed this collaboration.  I was reminded of how much I value collaboration in all aspects of life – not just technical development work.

I finally collected the Nourish recordings to make available (in all there crudeness and roughness) on my web page.  There is now a link to my “Music page” from my “Home page”:

http://glenniba.com

The direct link is:

http://glenniba.com/Music.html

There are even two videos of me and Rachel (kindly recorded and shared by another Nourish open mic participant).

Caveat:  These are not polished performances, so don’t expect a lot.  I hope, nevertheless that you can derive some enjoyment from my sharing them.

“If music  be the food of love, play on …”  — William Shakespeare

Tag Cloud