Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl: the Markov chain saw
 
PerlMonks  

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

by Limbic~Region (Chancellor)
on Sep 10, 2013 at 19:33 UTC ( #1053345=note: print w/ replies, xml ) Need Help??


in reply to Re^2: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
in thread Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty

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.

#include <stdio.h> #include <stdlib.h> #include <time.h> int won_game(int *copy); void hit(int *copy, int pos); int n_neighbor(int *copy, int pos); int s_neighbor(int *copy, int pos); int e_neighbor(int *copy, int pos); int w_neighbor(int *copy, int pos); int main (void) { static const char filename[] = "games.dat"; FILE *file = fopen (filename, "r"); if (file != NULL) { char line[32]; srand(time(NULL)); while (fgets(line, sizeof line, file) != NULL) { int i; // looping variable int j; // looping variable int hits; // index where the current n +umber of hits is stored int curr; // index of current item bei +ng worked on int last; // index of last item in our + work queue int games_played; // keep track of how many ga +mes we have played int stat[10]; // Keeps track of number of +hits to win a game int work[1000][31]; // Work queue (DFS will neve +r need more than 1000) games_played = 0; hits = 30; // Populate stats to all be 0 for (i = 0; i < 10; i++) { stat[i] = 0; } // Populate first item on work queue for (i = 0; i < 30; i++) { work[0][i] = ((int) line[i]) - 48; } work[0][hits] = 9; // number of hits allowed t +o play a board last = 1; while (last > 0) { int possible[30]; // maximum number of possibl +e hits int last_idx; // index of last possible hi +t for "this" board int temp; // used for Fisher-Yates shu +ffle /* Takes too long to play games exhaustively, even in +C */ if (games_played > 500000) { break; } --last; curr = last; --work[curr][hits]; // drop the number of hits // populate possible hits for "this board" last_idx = -1; for (i = 0; i < 30; i++) { if (work[curr][i] > 0) { ++last_idx; possible[last_idx] = i; } } // Fisher-Yates shuffle them so that games played are +all distinct but random for (i = last_idx; i > 0; i--) { j = rand() % (i + 1); // yes, I know this isn't pe +rfect temp = possible[i]; possible[i] = possible[j]; possible[j] = temp; } // Loop over all possible hits on the board, hitting e +ach one for (i = 0; i <= last_idx; i++) { // copy of the board to manipulate int copy[31]; for (j = 0; j < 31; j++) { copy[j] = work[curr][j]; } hit(copy, possible[i]); // Game won if (won_game(copy) == 1) { ++games_played; ++stat[work[curr][hits]]; } // Game lost else if (work[curr][hits] == 0) { ++games_played; ++stat[9]; } // Still playing so put it back on the work queue else { ++last; for (j = 0; j < 31; j++) { work[last][j] = copy[j]; } } } } for (i = 0; i < 30; i++) { printf("%c", line[i]); } for (i = 0; i < 10; i++) { printf(",%i", stat[i]); } printf("\n"); } fclose (file); } else { perror(filename); } return 0; } int won_game(int *copy) { int i; for (i = 0; i < 30; i++) { if (copy[i] > 0) { return 0; } } return 1; } void hit(int *copy, int pos) { if (pos < 0 || copy[pos] == 0) { return; } --copy[pos]; // If we exploded, we have to hit our neighbors if (copy[pos] == 0) { hit(copy, n_neighbor(copy, pos)); hit(copy, s_neighbor(copy, pos)); hit(copy, e_neighbor(copy, pos)); hit(copy, w_neighbor(copy, pos)); } return; } int n_neighbor(int *copy, int pos) { while (1) { pos = pos - 5; if (pos < 0) { return -1; } if (copy[pos] > 0) { return pos; } } } int s_neighbor(int *copy, int pos) { while (1) { pos = pos + 5; if (pos > 29) { return -1; } if (copy[pos] > 0) { return pos; } } } int e_neighbor(int *copy, int pos) { int min_val; min_val = (pos / 5) * 5; while (1) { --pos; if (pos < min_val) { return -1; } if (copy[pos] > 0) { return pos; } } } int w_neighbor(int *copy, int pos) { int max_val; max_val = ((pos / 5) * 5) + 4; while (1) { ++pos; if (pos > max_val) { return -1; } if (copy[pos] > 0) { return pos; } } }

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.

Cheers - L~R


Comment on Re^3: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
Download Code
Re^4: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
by MidLifeXis (Prior) on Sep 11, 2013 at 12:42 UTC

    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?

    --MidLifeXis

      MidLifeXis,
      The main function is a bit long for my tastes

      I agree. It grew over time. I am also more verbose than I need to be. I am using -O3 for gcc which I believe inlines whatever it can. I am potentially considering a new direction entirely so if I touch it again, I will certainly make more use of functions.

      Some of the repeated board manipulations or constants should probably be put into macros

      Macros are incredibly powerful but if you don't code enough in C to make them second nature they can have the opposite effect as intended (making code harder to understand rather than easier). I prefer to explicitly say what I am doing when working in a language I am not comfortable in so that I understand the code when I come back to it later. As far as magic numbers - yeah. I started to make variables to give them meaning but wasn't consistent as I tried to finish the code. In a re-write I would probably have some global static variables defined outside of main.

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

      No. I was expecting someone to look at the way I copy one array to another and say a far more efficent way of doing that was memcopy with a working example but alas, no such luck.

      Cheers - L~R

        Some of the repeated board manipulations or constants should probably be put into macros

        Macros are incredibly powerful but if you don't code enough in C to make them second nature they can have the opposite effect as intended

        Don't use macros, use functions marked inline instead:

        inline int func( int arg ) { // stuff return 1; }

        All the benefits of macros with none of the nasty side-effects or opacity.


        With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
        Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
        "Science is about questioning the status quo. Questioning authority".
        In the absence of evidence, opinion is indistinguishable from prejudice.
Re^4: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
by Limbic~Region (Chancellor) on Sep 14, 2013 at 01:57 UTC
    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:

    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.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://1053345]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (8)
As of 2014-12-27 18:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (177 votes), past polls