30 April 2015

Flood It: One More Tweak

I found a way to improve the lower bound on the number of moves needed to solve a Flood-It board position.  Basically, we can obtain a lower bound on the earliest time when a color can be cleared.  First, we have to be able to reach all cells containing the color, which is a simple distance measurement.  But next we need to be able to make consistent progress to every furthest cell of the color.

For each of the furthest cells of a color, we can create a distance map for that cell and find the critical paths to reach that furthest cell.  We can then record the different colors at each distance on that critical path.  On each turn, we have to move to one of those colors.  So we have a list of color sets, and we need to take one color from each set on each turn.

For each furthest cell of a color, we can build the list of color sets, and then AND together corresponding sets across the different cells.  If the AND of corresponding sets is empty -- if there is a turn on which no color choice will make progress to every furthest cell -- then we have proven a lower bound for that color that is one more than the furthest distance.

Unfortunately, I didn't implement quite the algorithm described here.  I didn't think up some of the generalities until after I wrote the code.  I'll have to see if the more general code can slightly improve the lower bound in more cases.

For the 14x14 board position, I'm now at 6,136 nodes evaluated and 1,894 of those expanded, in about 30 seconds (using python).

For the 21x21 board position, I'm now at 114,975 nodes evaluated and 39,493 of those expanded, in about 24 minutes.

So about 2.5 times faster.

29 April 2015

Flood It: Current Results

I previously discussed algorithms for finding optimal solutions to flood-it.  Today, it's time to post the performance of my current algorithms.

I'm working with two board positions.

A 14x14 board:

This can be solved in 21 moves: bygrpbvypgvrypgbryvpb.  (Flood with blue, then flood with yellow, green, red, pink, blue, violet, ...)  

My algorithm evaluated 16,280 board positions and expanded 4,594 of those.



A 21x21 board:

This can be solved in 29 moves: rprbygpbvpgyprpgvbgvyrpvybrgv.

For this board, my algorithm evaluated 293,889 board positions, and expanded 91,165 of those.

Labels: , , ,

You Say "Rent Control"...

I say "Long term lease."

Seems like people should have the right to be able to live where they want to live without major changes being forced upon them.  We don't forcibly exile law abiding citizens.  In California, Proposition 13 was passed oh so long ago, partly based on the argument that steadily increasing property taxes were forcing retired people to move out of their homes.

But instead of "Rent Control" to allow people to keep their dwellings when growth is rapid, suppose we used "Long Term Leases".  Suppose we got to a situation where you could sign a long term lease -- a 25 year or 30 year or 50 year lease.  The renter and landlord would negotiate a base rent and a yearly rent increase.  There would be an agreed upon mechanism to allow the renter to terminate the lease.

In particular, one mechanism for terminating the lease would be for a 3rd party to pay the renter to have the lease terminated so that the 3rd party could acquire a new long term lease at a higher price with the landlord.   Under this approach, the landlord still makes a profit in a fast growing market, but the renter can also make a profit and be compensated for giving up their right to live in one place for a long time.


But the concept of people being able to live where and how they want has broader applicability.  Here in the Bay Area, there's a strong call to increase housing development.  But none of these calls mention the fact that we're in the middle of a drought and current residents are being asked to cut water usage by 20%.  I've never seen a call for more development discuss how to compensate existing residents for the changes that will be forced upon them.

24 April 2015

Flood-It

I've been working on algorithms that solve Flood-It.  I'm using a simple A* search.  And then I'm using basically four ideas.

First, we can represent a board position as a network of cells where a cell represents a connected set of squares of the same color.  Cell zero represents the set of squares of the same color connected to the upper-left corner.  We can then quickly measure the distance of each cell from Cell zero.  That gives us a lower bound on how many moves are needed to solve the game: we must at least clear a path to the furthest cell.

Secondly, consider the set of colors that are furthest from the origin.  We will have to remove each of these colors, and we can't clear a color until we reach it's furthest cell.  So for the lower bound we can add one move for each furthest color.  More generally, for each distance, consider the set of colors at that distance and the set of colors at a further distance.  Each color that is at a distance but not a further distance must be cleared at or after that distance.  We can consume one color making a move to reach the distance, but any other colors will need an extra move that won't make forward progress toward reaching a further distance.

This above computation on the lower bound gives us the estimate of the cost to solve a board position needed by the A* search algorithm.

The third idea that we use helps us to reduce the number of next moves that we need to examine at a board position.  Consider a cell at distance 'd' that has no neighbor at a further distance.  That cell isn't blocking the path to any other cell, and we can take that cell whenever it is exposed and we happen to take it's color for some other reason.  We can treat the cell as if it was at the furthest distance of any cell of its color.

We can work backwards through the distances adjusting the "effective distance" of each cell.  We can increase the effective distance of a cell to be the maximum possible less than the effective distance of any cell that was at a normal distance greater than the normal distance of the cell we are adjusting.  But, we also want to make sure that the "effective distance" is a distance where the color of the cell can be taken.  So, for each color, we record the normal distances on which the color can be taken, and we reduce the effective distance of a cell to be one of the distances in the cells color list.

This idea allows us to restrict the next move colors to colors that are at an effective distance of 1.

Finally, we note that if we can clear a color, clearing the color is always at least as good as any other move.  So if we can clear a color, we choose a single move that clears a color as our sole next move.  (This is, at best, a very minor optimization.)

This simple set of ideas allows us to solve 6-color 21x21 boards.  6-color 28x28 boards remain elusive.