Strategy

[GoogleCodeExporter]

Ok guys its time to pick a strategy.
Post any ideas you come up with. We will be implementing each of these 
strategies and timing them along with counting moves (the two things tested).

Ideas so far:
-Pre-calculate every possible game, then pick the one with the least moves
-Predict game one move ahead, then pick best opportunity
-Predict game two moves ahead, then pick best opportunity
-Predict game a number of moves ahead based on how many squares are touching 
the current color

Original issue reported on code.google.com by drdaniel...@gmail.com on 14 Mar 2011 at 11:44

[GoogleCodeExporter]

-Find the largest blobs in the grid, and compute the shortest path to connect 
them

Original comment by smd7...@gmail.com on 15 Mar 2011 at 12:53

[GoogleCodeExporter]

change color to the color which will provide the best immediate results at each 
iteration?

Original comment by sreservoir on 15 Mar 2011 at 1:00

• Added labels: Component-Logic, Milestone-Release1.0, Priority-Critical

[GoogleCodeExporter]

-Compute shortest path from top-left to bottom-right, and then take it from 
there with another strategy

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:07

[GoogleCodeExporter]

who is this smd?

Original comment by sreservoir on 15 Mar 2011 at 1:09

[GoogleCodeExporter]

To elaborate on my last comment, having a path going from top-left to 
bottom-right will give us a large amount of surface area.  I think that surface 
area is a key with this problem among other factors, because the more surface 
area we have, the more blocks we can take with each successive turn.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:10

[GoogleCodeExporter]

This is Scott DellaTorre.  I'm a Junior who took AP CS last year.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:11

[GoogleCodeExporter]

let us define criteria for which squares are advantageous:

1. borders unconverted squares.
2. closer to center.

def. 1 is tactical: it allows us to immediately work on more.
def. 2 is strategic: it allows us to work on more in the long run.

the question is how much to weigh them, and how to determine them. also, what 
other criteria we can use.

Original comment by sreservoir on 15 Mar 2011 at 1:15

[GoogleCodeExporter]

Through testing with a 5x5 pixelated board, I've discovered that moves which 
remove a color from the board are more beneficial than moves that result in a 
color remaining on the board, even if the latter move captures more blocks.  
This is probably only relevant to end-game scenarios but is still notable.

On another note, divide and conquer solutions are typically faster than brute 
force solutions and I usually like to see if it's possible to take that route.  
Does anybody see a way in which we could divide this problem into smaller 
sub-problems?

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:23

[GoogleCodeExporter]

the trouble with that is that this is a fundamentally monolithic problem, 
because you have only one changeable blob.

Original comment by sreservoir on 15 Mar 2011 at 1:25

[GoogleCodeExporter]

We could implement the line from top left to bottom right and then change the 
color based on the block color with the most number of that specific color 
blocks around it?
In essence, changing the color based on the color that is mostly surrounding 
the current blob. This will help to attain a bigger surface area to start. I 
think this in a latter stage though would be ineffective due to the number of 
blocks that would be around the giant blob.

Original comment by mikedibu...@optonline.net on 15 Mar 2011 at 1:33

[GoogleCodeExporter]

Yes, though it probably isn't impossible to break this problem into 
subproblems, it might not be a feasible solution.  Still something to consider 
for the future perhaps.

A new idea: Look at each color individually and determine how many moves it 
would take to connect all of that color's blocks together (and thus eliminate 
it from the problem).  Choose the color that takes the least amount of moves to 
accomplish this.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:35

[GoogleCodeExporter]

that's what I said initially. see comment 2.

Original comment by sreservoir on 15 Mar 2011 at 1:35

[GoogleCodeExporter]

I think we need to get as many blocks on the perimeter of the blob as possible, 
giving us more options and a bigger surface area. I think that should be our 
number one priority.

Original comment by mikedibu...@optonline.net on 15 Mar 2011 at 1:38

[GoogleCodeExporter]

yes. care to help determine how to do that?

Original comment by sreservoir on 15 Mar 2011 at 1:38

[GoogleCodeExporter]

incidentally, how can we determine the /current/ perimeters of the blob?

Original comment by sreservoir on 15 Mar 2011 at 1:39

[GoogleCodeExporter]

@sreservoir (comment 12): was that in reference to my comment or mike d's?

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:40

[GoogleCodeExporter]

to mike's (10).

Original comment by sreservoir on 15 Mar 2011 at 1:41

[GoogleCodeExporter]

incidentally, 11 isn't a bad idea *if* we can make it time-efficient.

Original comment by sreservoir on 15 Mar 2011 at 1:42

[GoogleCodeExporter]

Doing a little testing I have discovered two things that may be of help. One, 
doing the idea in comment 11 takes time in the beginning but makes the end 
quite quick. Also, from watching the AI I noticed that it tries to get as many 
of one color isolated inside the blob and then changes to that color. That may 
help us in some way.

Original comment by mikedibu...@optonline.net on 15 Mar 2011 at 1:45

[GoogleCodeExporter]

For the perimeter problem, we can determine the exposed perimeter, or surface 
area, by scanning each row until reaching a different color than the one in the 
top-left, and then repeating that process for each column.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:48

[GoogleCodeExporter]

Ok, I take back my last comment.  It's a bit more complicated than that.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:49

[GoogleCodeExporter]

Given a list of the blocks in the blob, we can iterate that list and for each 
block, count the amount of exposed sides.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:50

[GoogleCodeExporter]

That would be a sequential search though, I think something similar to a binary 
search, where we cut it in half until we find the changed spot, would be the 
best, but the only problem with both  of our ideas is that what if the blob is 
exposed on two sides, then it will stop at the first sighting and we might not 
get an accurate perimeter

Original comment by mikedibu...@optonline.net on 15 Mar 2011 at 1:51

[GoogleCodeExporter]

@19: that's an interesting observation, considering an observation I've made: 
if we just try to press toward the lower-right, that happens a lot, and then it 
gets consumed by the next few changes.

Original comment by sreservoir on 15 Mar 2011 at 1:51

[GoogleCodeExporter]

you make a good point mike, by moving outward, usually the inner blocks are 
absorbed just by trying to move out farther

Original comment by mikedibu...@optonline.net on 15 Mar 2011 at 1:53

[GoogleCodeExporter]

@23 I think the revised idea solves that problem.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 1:54

[GoogleCodeExporter]

where do you intend to get a list of all the blocks in the blob?

Original comment by sreservoir on 15 Mar 2011 at 2:09

[GoogleCodeExporter]

I believe that this recursive function will correctly compute the surface area, 
provided that we have access to the grid of pixels.

private int getSurfaceArea(int[] grid, int x, int y) {

    int surfaceArea = 0;

    if (x+1 < grid.length) {
        if (grid[x+1][y].color.equals(grid[0][0].color) {
            surfaceArea+=getSurfaceArea(grid, x+1, y);
        } else {
            surfaceArea++;
        }
    }

    if (y+1 < grid[0].length) {
        if (grid[x][y+1].color.equals(grid[0][0].color) {
            surfaceArea+=getSurfaceArea(grid, x, y+1);
        } else {
            surfaceArea++;
        }
    }

    return surfaceArea;

}

Original comment by smd7...@gmail.com on 15 Mar 2011 at 2:25

[GoogleCodeExporter]

Initialized with x=0 and y=0.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 2:28

[GoogleCodeExporter]

I think that fails on both of the following:

xxx
xxx
xxx

and

xxx
 x 
xx

the first gets overlapped, and the second doesn't have its hook accounted for.

Original comment by sreservoir on 15 Mar 2011 at 2:29

[GoogleCodeExporter]

I propose a recursive solution whereby we flag each appropriate grid and 
applicable neighbors, then recurse on those neighbors; and finally, at the end, 
we count them.

better yet, we do that and count the number of neighbors each has. then we'll 
know which ones are perimeter blocks.

Original comment by sreservoir on 15 Mar 2011 at 2:31

[GoogleCodeExporter]

Indeed it does.  Good catch.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 2:31

[GoogleCodeExporter]

Code can definitely be shortened.  Requires a copy of the board array to be 
made.

private int getSurfaceArea(Block[][] grid, int x, int y) {

    grid[x][y] = null;

    int surfaceArea = 0;

    if (x-1 >= 0) {
        if (grid[x-1][y] != null && grid[x-1][y].getNumColor() == grid[0][0].getNumColor()) {
            surfaceArea+=getSurfaceArea(grid, x-1, y);
        } else {
            surfaceArea++;
        }
    }

    if (x+1 < grid.length) {
        if (grid[x+1][y] != null && grid[x+1][y].getNumColor() == grid[0][0].getNumColor()) {
            surfaceArea+=getSurfaceArea(grid, x+1, y);
        } else {
            surfaceArea++;
        }
    }

    if (y+1 < grid[0].length) {
        if (grid[x][y+1] != null && grid[x][y+1].getNumColor() == grid[0][0].getNumColor()) {
            surfaceArea+=getSurfaceArea(grid, x, y+1);
        } else {
            surfaceArea++;
        }
    }

    if (y-1 >= 0) {
        if (grid[x][y-1] != null && grid[x][y-1].getNumColor() == grid[0][0].getNumColor()) {
            surfaceArea+=getSurfaceArea(grid, x, y-1);
        } else {
            surfaceArea++;
        }
    }

    return surfaceArea;

}

Original comment by smd7...@gmail.com on 15 Mar 2011 at 2:48

[GoogleCodeExporter]

The (!= null) checks should be moved from the inner if statements to the outer 
if statements.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 2:51

[GoogleCodeExporter]

Interesting Note: The optimal solution for "Pixelated" or "Flood-It" has been 
shown to be NP-hard.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 3:02

[GoogleCodeExporter]

Going back to the idea from comment 11, this can be achieved using heuristics 
(and from what I've read, that is the most efficient way of solving this type 
of problem).  Check out the A* search algorithm: 
http://en.wikipedia.org/wiki/A*_search_algorithm.

Original comment by smd7...@gmail.com on 15 Mar 2011 at 4:40

[GoogleCodeExporter]

The code in 33 gives us the exposed perimeter but, as Mike Z proposed, a better 
metric would be the amount of neighboring blocks, since having four edges 
exposed to a block is not any more beneficial than having one edge exposed.

The following code should correctly count the number of neighboring blocks 
(hopefully I'm correct this time).  I think using a new boolean array for 
flagging blocks will be more efficient that cloning the block array.

    private int getNeighborCount(Block[][] grid)
    {
        return getNeighborCount(grid, new boolean[grid.length][grid[0].length], 0, 0);
    }

    private int getNeighborCount(Block[][] grid, boolean[][] flagged, int x, int y)
    {

        flagged[x][y] = true;
        int count = 0;

        int[][] coordArray = new int[][] {{x-1, y}, {x+1, y}, {x, y-1}, {x, y+1}};
        for (int[] coords : coordArray) {
           int currX = coords[0], currY=coords[1];
            if (currX >=0 && currX<grid.length 
                    && currY>=0 && currY<grid.length
                    && !flagged[currX][currY]) {
         if(grid[currX][currY].getNumColor() == grid[0][0].getNumColor()) {
                     count+=getNeighborCount(grid, flagged, currX, currY);
                 } else {
             flagged[currX][currY] = true;
             count++;
            }
        }     

        return count;

    }  

Original comment by smd7...@gmail.com on 15 Mar 2011 at 7:24

[GoogleCodeExporter]

Hey guys, can we set up a meeting maybe sometime next week, say Wednesday, to 
go over what's been done so far and to come up with a plan for what to do next?

Original comment by mikedibu...@optonline.net on 16 Mar 2011 at 11:45

[GoogleCodeExporter]

where should we meet?

Original comment by smd7...@gmail.com on 17 Mar 2011 at 12:10

[GoogleCodeExporter]

We could talk to Mr. Barretta and see if we can use the Math Resource room. or 
we could just go to the woodbridge library?

Original comment by mikedibu...@optonline.net on 17 Mar 2011 at 12:27

[GoogleCodeExporter]

idk if it's possible but ask him if we can get a room with a whiteboard so we 
can write stuff down.

Original comment by smd7...@gmail.com on 17 Mar 2011 at 12:33

[GoogleCodeExporter]

We could always ask him if he wouldn't mind coming down to the room we go to 
for class every day. That might be a good spot to work on the project

Original comment by mikedibu...@optonline.net on 17 Mar 2011 at 12:36

[GoogleCodeExporter]

yea that would be good because we would also have computers to work with.

Original comment by smd7...@gmail.com on 17 Mar 2011 at 12:40

[GoogleCodeExporter]

Original comment by drdaniel...@gmail.com on 20 Mar 2011 at 2:19

• Changed state: Started

[GoogleCodeExporter]

All new strategies should get their own thread. The current ideas are basically 
created.

Original comment by drdaniel...@gmail.com on 22 Mar 2011 at 12:41

• Changed state: Done