Note: If you came to this post looking for Flood-It strategies, welcome! Some links can be found in the comments section below the original post. (Ram)An innocuous little message showed up on my iGoogle page a few weeks ago. A colorful icon with the accompanying message that said, "Recommended for you." It was a game. (Wonder why it was recommended since I didn't have anything to do with games on my page.)
Being curious, I checked it out. The goal is to "fill" the board with one color by clicking on different colors to flood the board in 25 moves or less. After you have played a few games, you start to develop neat little strategies.
Like many of my "consuming interests," I expected to grow out of it within the week. Meanwhile, I felt it was good mental training and kept playing.
But my interest didn't fade. Instead, myself (and a couple of like-minded friends) have been spending unhealthy gobs of time trying to 'solve' the game with optimal strategies. (That is, trying to finish each board with the theoretical minimum possible clicks.) If you too end up spending lots of time devising algorithms, send me a note or leave a comment and we can discuss offline.
Meanwhile, check out the game. (If you use iGoogle, you can add it to your page.)
Ram
Posts
30 comments:
Sorry for commenting on such an old post, but I too just found this game and the same thing has happened to me (and a few of my like minded friends as well).
I am wondering if you devised an "optimal strategy" that you found to be successful.
A long story short: I wrote a little program that plays the game by itself (on the igoogle page no less, so I can keep track of stats) But my strategy is to click the color with the most boxes touching "the group". It has a win percentage of about 10%. Playing manually I win about 40% of the time, so I'm wondering where the disconnect is.
Anyway, let me know if you want to discuss this. If not, I won't be offended :)
Thanks,
Edward
@Edward:
(sorry for non-programmers...)
I wrote a program which wins the game (within 25 steps) more than 95% of the time. It completes in about 22 steps on average.
However it currently has no graphical input/output. It runs in CMD.exe window, and uses the numbers 0-5 to represent 6 different colors. The code is a combination of C++ and Python. The program thinks 4 steps in advance, rather than simply picking the most advantageous color at the current step. Please do contact me at zengmao00@yahoo.com.cn.
The "optimal" strategy would be to search the game space for the shortest path to a solution, but this means searching a tree with about 95 trillion leaves. This would probably be a bit time consuming, even with little tweaks to eliminate obviously poor moves.
The next approach is to choose a metric to evaluate moves and evaluate the available moves based on it. Choosing the color with the most boxes touching the group is, empirically, not a very good one. Closer to the mark would be to choose the color which results in the largest group. After that, brute force searches two, three, or more moves ahead and applying this metric to the final result would give substantially better results. I expect it would be possible to search ten moves ahead and still solve the game very quickly.
You can find out more in the Algorithms and Artificial Intelligence courses at the computer science department of any good university...
Manually I am getting about 52% win rate. I cannot say if this is good or bad. I have never reset the board so leaning curve is included.
The approach I use is to play for penetration. I aim for the opposite corner. Rarely the obstacles have too much repetition. I would allow for this by requiring a wedge shape having a favorable ratio of base size to length.
The problem you have is that you do not know what algorithm is used to create game. Is it random? If you know the actual distribution you can better determine when you reach an optimized solution.
I found this post when I exhasperatedly Googled "Can't win Flood-It." I've literally never won. I'm usually good at strategy games, but this one has me stumped. I've tried the "wedge shape having a favorable ratio of base size to length" approach, with no success (though friends have used it successfully). It wounds my pride to ask for help winning a strategy game, but--help!
Hey Lori:
A couple of my friends (Krishna and Goutham) and myself worked on this a fair bit. I can get you to win with a decent frequency, but the "optimal solution" has eluded us thus far.
Do send me an email and we can send you some of what we tried...
Ram
Thank you! I'd be glad to. I can't seem to find your email address on the blog, though, so here's mine: lorifagerholm {-at-} gmail {-dot-} com.
hi guys... i am playing this game on iphone.. and it limits a game to 22 moves.. till now out of 12 games i have managed to clear the board only once... and cant figure out any *optimal* way of doing this.. i am ready to admit that the only win was probably fluke.. please share any ways to win this... if there are any really..
i am impressed by peter who says that on an average one can win in 22 moves using his program... would like to know what was the logic used in the program...
right now. while searching through the internet for this.. i found a good strategy.. suddently it has started working for me... have 100% success rate so far... (2 games)
go for the far corner instead of furthest corner...
It was posted on slashdot not too long ago that this game was proven NP-Hard.
http://arxiv.org/abs/1001.4420
You guys should be playing my version of floodit:
http://floodit.cjb.net/
It has a hall of fame and everyting.
You are all invited to try-
lol.. This is a fun game. I have beat Small in 21 moves, Medium in 31 moves and Large in 42 moves. I have found a strategy that wins 95% of the time on Small, and about 90% on Medium and maybe 85% on large. Here's what I do.
I picture the whole board as a snake waiting to eat apples starting in the corner. I picture the shortest path to make my snake the longest, if that makes sense. In other words scan the board for the longest grouped colors and aim to drive through them all with the fewest moves and the rest of the board pretty much clears itself.
To finish off though,, It is important to recognize which color still has one of it's own buried and try to avoid choosing that color until it is unburied. Therefore, thinking of it like Chess in the last 8 moves or so is crucial to beating it with extra moves left over. Which color is has the least buried and what would unburrie it. If the one that would unburrie it is also burried by another color then keep working backwards until you figure the best combination to finish off with.
However, if you just want to beat it most times, but don't care about having a ton of extra moves left then just do the first part and skip the rest. You will almost always win, unless your bad at picking pathways through the long groups.
I have a win rate of 48% on the small board and my best game so far is 20 moves. I try to “bore” a pathway, usually diagonally through the game. This maximizes the surface area of the flood. The previous poster made the very good point that I will add to; when you have maybe 6 or 8 moves left, starts looking for colors that are not blocked by other colors and eliminate them. I can’t tell you how many times I lost a game with one pixel left of the board that could have been easily eliminated by being more careful!
We can't figure this game out either
I thought it was an impossible scam, but then someone said they beat it.
I think we're really in a pickle!
Hey, I'm currently taking a course in game analysis and as my final thesis I need to analyze and solve Flood-It. If anyone can give me links that would be amazing. Also it would be helpful if anyone can send me a program on python that simulates the game. credit will be given.
THANKS
HIKE
I have a 90% win rate on large. My strategy is a combination of going diagonally, choosing the route with the largest patches (fewest moves), but also being dynamic: knowing when to change direction to tackle a built up area such as a busy corner. It's also preferable to use all colours frequently rather than repeating the same colours within only a few moves, ie red, white, black, yellow, .... is better than red, white, red, black, red etc
Always go on the direction of the thickest crowd.
Divide and conquer!
Best iPhone game ever.
My win rate is 73% right now. Look for long chains of color, especially early in the game. Look for places to burst through checkerboard patterns. Concentrate more on paths than on clearing an area. Be careful toward the end of the game as it is easy to miss a path to buried corner pieces. Also it is critical toward the end to look for colors that can be completely cleared in a single stroke. Can anyone out there tell me why sometimes the board just clears itself and starts over. So frustrating when the game is going great and it goes "poof".
My BF has a near 100% rate. I kid you not. I told him to download the app for fun. He has a busy mind. Within two days he had mopped the floor with my 22% average. I googled ” Flood-It strategies” tonight to find a way to take him out. :)
I had no idea so many people loved the game. I'll see if I can get Mr. Flood-It himself to stop by and give us some tips!!!
Jenny
Sorry i understand this is a old post but i also wrote a program in java to solve flood it boards but i am having problems my program manages to nearly compleat the board most times so i thought i should try add some stragie rather than just going for the option that gets rid of the most squares but i am having trouble thinkink of effective ones that arnt time consuming i have some ideas for example giving each square a score based on how large the group its in is ( if its in a group ) and if its blocking access to other large areas of blocks.
After wasting a bit of time trying to solve EVERY Flood-it layout presented to me at the Easy level, I decided to be proactive and pre-select those "New Game" choices according to my own, logical but rudimentary criteria.
This approach has saved me much frustration, and has given me a solution rate of about 65-80%.
It is obvious that the power lies in the hands of the puzzle constructor, which could easily make it quite impossible to solve ALL puzzles by simply never having more than a single block of one color (i.e. NO multiple blocks of the same color). What would be the point of playing against that worst case? None!
Therefore, I now look at a "New Game" before I play. First thing I look at is whether the 3 opposing corners each have any connected blocks along the board's edge ... if not, I do not play that game EXCEPT if the next matter is greatly in my favor - but at least 2 of the 3 opposing corners need that criteria, in any case. The next criteria is that the starting corner has a VERY favorable setup, such as 2 large blocks side by side, etc. And finally, I look at the entire puzzle to see if it contains a "fair" amount of multi-square blocks, which is needed to have any reasonable chance to solve.
If those criteria are met, then I play that game ... if not, I simply hit "New Game" and look again. It seems to me that I usually reject, on average, maybe 5-8 puzzles before selecting one worth playing.
My feeling is that the "New Game" button is there for a reason, and I have chosen that reason to be one which gives me at least a 50% chance of success each time out.
Of course, during the play of the game it is important to use some of the basic logic already mentioned here, and especially when the End Game is in sight ... don't hit a given color twice unless it appears to be absolutely necessary. I try looking at those colors which are ready to be totaly eliminated by a single stroke, and get rid of them first,
Sorry to be so lengthy ... but it's 2AM++ and I'm taking a break from the game! retired, of course!
I finished my program to solve a flood-it board in lowest amount of moves and i have got to complete my testing board in 20 moves
Whatever color you start with do not touch until almost the end!
I have won the game in 16 moves multiple times, which I believe to be the fewest possible moves. 17 is easy -- however, 16 takes a special board.
I usually hit "new game" until I find a board that I am comfortable with. My strategy is to find boards that have large color blocks trailing from top left to bottom right.
Recently, since I feel that the 16 barrier cannot be broken, I have tried finding the worst possible board and seeing how many moves it takes. I have never not finished in less than 22, leading me to believe that if played correctly, the range is 16-22 for the board.
I wrote a perl-Tk version of the game some years ago and a solver to go with it. My solver results on random standard games (14x14 grid, 25 moves to win) is only 56 unsolvable boards in 263410 attempted. 99.98% win rate. Fastest win rate in those test was 14 moves on two different boards, and 15 moves on nine others.
My original algorithm involved scoring the board by +1 for each square converted to the current flood, 0 for squares neighboring the current flood, and -1 for squares that do not neighbor the current flood. With that, it searches 1 or more steps ahead for the path to the highest score. It can solve >99% of boards with a lookahead of three steps.
I recently revisited this game when I found it was available for android. I still use the same perl-Tk player/solver, but worked out a new scoring mechanism. For each board, work out the minimum number of colors required to reach each square: already flooded squares are 0. Immediate neighbors are 1. And so on. Score the board as +1 for each already-flooded square and subtract the square of the step distance for each unflooded square. This new scoring mechanism is about 2x the time to calculate for each board, but the resulting solver gets about 97-98% wins on a single step of look-ahead.
Hello from Athens,
I beat the Large in less that 40 steps, with a success rate of >90%. But, it seems impossible to beat it in less than 36 steps.
Tips welcome
Thanks
Anna
I have a win rate of 60% on a 25-move board. Like Ron Hinchley I attempt to penetrate to the very opposite end withing 17 moves or less. At least, the aim would be to cut the board into two halves, reaching at least one box short on either side of the opposite end within 17 moves or less.
The balance moves are used to clear the board. I also try to carefully select the 3 final penetrating moves, the ones where you end up 'touching the opposite end'
My record stands at 19 moves.
i got 15, cant seem to beat that... or get it again
thats manually though using my own technique similar to alot of other users here
I think its great that others have the same problems as I do, I've been stuck on baby pixie so long i was begining to think I was stupid. So, go diagonal, big color groups, long strings, got it.
I'm new to this game and already addicted. I've read a lot of posts online about how hard it is to win, which has me confused. I'm no genius but since yesterday I'm at a win rate of 83% over 49 games and have solved in 18 moves three times. I'm playing the "small" version of Flood-It 2 on my iPhone. Did they make the game easier with version #2? Or maybe I am a genius after all....?
Based on the discussion, I would suggest a strategy of minimizing the maximum buried depth. Mark the flood as depth zero. Mark any unmarked color group adjacent to the flood as depth 1. After marking depth 'i', mark any unmarked color group adjacent to depth 'i' as depth 'i+1'.
If the maximum depth is 1, we can always solve the board in at most 6 moves.
If a color has a maximum depth of 1, we can always choose that color as a best possible move.
When multiple colors are at depth 1, we can consider removing each color and prefer colors which produce a board with a lower maximum depth. When there are multiple good choices, we can sub-select on a choice that removes the most area. Or perhaps subselect to reduce the amount of area marked with the maximum depth, or the number of colors marked with the maximum depth.
For most moves of the game, there are 5 colors to choose from. During the endgame, the last 6 moves, there is typically one path to take. The first move has typically 2 or 3 moves. So in a game that can be won in 24 moves, there are 17 moves where we have 5 choices and one move where we have 2 or 3 choices. So the size of the tree is 3 * 5^17. That's 2,288,818,359,375. So only a couple of trillion nodes.
We may have a relatively good estimate on a lower bound to solve the puzzle (the number of colors at the maximum depth, plus the maximum depth, minus 1). If so, we should be able to prune large parts of the search space.
Post a Comment