Re: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty

[QM]

Does it make sense to do this in reverse? That is, generate boards at random, then "play" the boards. Board play is along 2 lines -- mean number of random touches to clear, and minimum number of touches in best play.

Easy boards will have less variation between random and best play, compared to hard boards. As the board difficulty rises, then given number of touches gets closer to best play. (It's up to you whether you use the "infallible" level, where allowed touches == best play.)

Thanks for the diversion today!

[Limbic~Region]

QM,
So, here is the problem:
Read more... (3 kB)

It takes too long to figure out all the ways to play a game. I am thinking I need to lower the number of possible moves and limit how much time can be spent playing a single game. What do you think?

Update: I can complete approximately 40,000 games every 5 seconds. What I have done is impose a 6 hit limit along with randomly shuffling the return of possible_hits() and limited each board to 40,0000 games. I have manually tested this against a handful of boards and it appears to give a pretty good approximation of the results if all of them had been played. I would prefer a C based version of this which could likely do far more per second but my C is rusty (was never very good) and I can't remember how to manage a dynamic array.

Update 2: I turned the problem upside down and it became much easier. Instead of scoring how difficult the game was, I instead scored how easy the game was. I used a combined score of things like win to loss ratio, number of initial 1-hit moves to 1-hit wins, etc. The ones with the lowest score were the most difficult. Now I just need to code the actual game.

[Limbic~Region]

All,
I have ported the code to C (figured out how to avoid a dynamically managed array) and am making it available here for your critique/suggestions. I have never been a C programmer so there are probably a number of ways to write this more elegantly and efficiently.
Read more... (7 kB)

Even in my neophyte C, I have realized an enormous performance increase. Even in C, it still takes too long to exhaustively play all possible games for a board when you allow the player to use up to 9 hits. For this reason, I duplicated the same changes I did to the original Perl (play a limited number of distinct but random games). The difference is that I am now able to use up to 9 hits and play 500K games in less time then it was taking me to play 6 hits for 40K games.

[Limbic~Region]

All,
Simply generating C code to play games faster hasn't lead to a solution to my real problem. I want to be able to rank the difficulty of a board so that a human will perceive game play as increasingly difficult. The problem is that if there are 19 1-hit bubbles that all lead to winning the game, it doesn't matter how many ways there are to win after 7-hits or how many ways to lose. Not only does it not matter, but the magnitude of those numbers obscure how easy a game actually is. To that end, I have revised my code as shown below:
Read more... (7 kB)

It has a number of distinctions from the previous version.

It no longer chooses to play distinct random games. It arranges the places to hit by choosing all 1 hits before 2 hits before 3 hits before 4 hits. The idea being you can't finish a board without hitting a 1-hit bubble and they can lead to cascading bursts.

The game no longer has a fixed number of hits before deeming a game lost. It keeps track of the fewest number of hits it takes to win the game. As the game progresses, it will abandon a game if it has taken more than 2 more hits than the current minimum. This reduces the noise of having a large number of games played that require a large number of hits when a human will have already solved the board.

It keeps track of more statistics. In addition to how many ways it won with 1-9 hits and the number of games lost, it also keeps track of the following fields for 1 - 9 hits:

1. Total number of games played at this hit level
2. Total number of 1-hit bubbles
3. Total number of 2-hit bubbles
4. Total number of 3-hit bubbles
5. Total number of 4-hit bubbles

I am going to let it run for a while and see if it produces more usable data.

[MidLifeXis]

It has been a number of years since I have done anything of significance in C, so some best practices may have changed, but from a quick glance, I see a couple of things:

• If you are looping through a list of items for, say, a 0-based copy, you may get better results from something like: for (j=maxval; j; j--) {...}
• The main function is a bit long for my tastes, although I understand that you are trying to do this for performance, so removing the function calls might make sense.
• Some of the repeated board manipulations or constants should probably be put into macros. The loop for copying the board is used at least twice and could be macro-ized, and many of the constants are just magic numbers as I read through.

Other than that, do you have a profiler that shows any hotspots?

[SuicideJunkie]

If you are going to build a number of random games and score them for difficulty, you could have an auto-challenge balancing routine.

1. Save 11 random boards and sort them by difficulty rating.
2. Have the user play the (easymode=3rd, medium=6th, hardmode=9th) ranked one.
3. If the user wins, delete the games easier than the one just beaten, if they lost, delete the harder games.
4. Generate replacement boards and sort them by difficulty again.
5. Goto 2 until bored

[Limbic~Region]

QM,
I considered this. Every game I have ever played, my starting move has always been where I can get the biggest chain reaction or set a chain reaction. In other words, it may make sense to create algorithms that mimic real strategies to play the games rather than exhaustively brute forcing all possible ways to play the board.

I just can't find anything I am happy with and I knew that the amazing monks at the Monastery would point out something obvious (probably having to do with recursion) that I completely missed.