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

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

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: