Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

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

by Limbic~Region (Chancellor)
on Sep 14, 2013 at 01:57 UTC ( #1054042=note: print w/ replies, xml ) Need Help??


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

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:

#include <stdio.h> #include <stdlib.h> #include <time.h> // Constants to remove magic numbers #define HIT 30 // index where the # of hits are stored #define MAXQUEUE 1000 // DFS will never need more than this #define BOARDLEN 31 // board = 30, 1 for remaining hits #define STATLEN 55 // statistics for determining difficulty #define MAXGAMES 500000 // Takes too long to play games exhaustivel +y - even in C #define MAXHITS 9 // Games taking more hits are probably too +hard #define LOST 9 // index where # of lost games are stored #define ASCII 48 // ASCII value of 0 is 48 so to convert to +integer - 48 #define BUBBLES 30 // # of bubbles on a board // Prototypes inline void update_stats(int *item, int *stat, int hits_remaining); inline int possible_hits (int *item, int *possible); inline void output_results(char *line, int *stat); inline void initialize_work_queue(int *item, char *line); inline void initialize_stats(int *stat); inline void copy_array(int *src, int *dst); inline int won_game(int *copy); inline void hit(int *copy, int pos); inline int n_neighbor(int *copy, int pos); inline int s_neighbor(int *copy, int pos); inline int e_neighbor(int *copy, int pos); inline int w_neighbor(int *copy, int pos); int main (void) { static const char filename[] = "games.txt"; FILE *file = fopen (filename, "r"); if (file != NULL) { char line[32]; srand(time(NULL)); while (fgets(line, sizeof line, file) != NULL) { int i, curr; int last = 1; int best = 100; int games_played = 0; int stat[STATLEN]; int work[MAXQUEUE][BOARDLEN]; initialize_stats(stat); initialize_work_queue(work[0], line); while (last > 0 && games_played <= MAXGAMES) { curr = --last; --work[curr][HIT]; update_stats(work[curr], stat, work[curr][HIT]); int possible[BUBBLES]; int last_idx = possible_hits(work[curr], possible); for (i = 0; i <= last_idx; i++) { int copy[BOARDLEN]; copy_array(work[curr], copy); hit(copy, possible[i]); if (won_game(copy) == 1) { if (work[curr][HIT] < best) best = work[curr][ +HIT]; ++games_played; ++stat[work[curr][HIT]]; } else if (work[curr][HIT] == 0) { ++games_played; ++stat[LOST]; } else if (work[curr][HIT] > (best + 2)) { ++games_played; } else { copy_array(copy, work[++last]); } } } output_results(line, stat); } fclose (file); } else { perror(filename); } return 0; } inline void update_stats(int *item, int *stat, int hits_remaining) { int i; int offset = (((MAXHITS - hits_remaining) - 1) * 5) + 10; ++stat[offset]; for (i = 0; i < BUBBLES; i++) { switch(item[i]) { case 1: ++stat[offset + 1]; break; case 2: ++stat[offset + 2]; break; case 3: ++stat[offset + 3]; break; case 4: ++stat[offset + 4]; break; } } } // populate 1s before 2s before 3s before 4s inline int possible_hits (int *item, int *possible) { int i, j; int last_idx = -1; for (i = 1; i < 5; i++) { for (j = 0; j < BUBBLES; j++) { if (item[j] == i) possible[++last_idx] = j; } } return last_idx; } inline void output_results(char *line, int *stat) { int i; for (i = 0; i < BUBBLES; i++) { printf("%c", line[i]); } for (i = 0; i < STATLEN; i++) { printf(",%i", stat[i]); } printf("\n"); } inline void initialize_work_queue(int *item, char *line) { int i; for (i = 0; i < BUBBLES; i++) { item[i] = line[i] - ASCII; } item[HIT] = MAXHITS; } inline void initialize_stats(int *stat) { int i; for (i = 0; i < STATLEN; i++) { stat[i] = 0; } } inline void copy_array(int *src, int *dst) { int i; for (i = 0; i < BOARDLEN; i++) { dst[i] = src[i]; } } inline int won_game(int *copy) { int i; for (i = 0; i < BUBBLES; i++) { if (copy[i] > 0) { return 0; } } return 1; } inline 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)); } } inline int n_neighbor(int *copy, int pos) { while (1) { pos = pos - 5; if (pos < 0) return -1; if (copy[pos] > 0) return pos; } } inline int s_neighbor(int *copy, int pos) { while (1) { pos = pos + 5; if (pos >= BUBBLES) return -1; if (copy[pos] > 0) return pos; } } inline 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; } } inline 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; } }

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


Comment on Re^4: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
Download Code
Replies are listed 'Best First'.
Re^5: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
by Anonymous Monk on May 25, 2015 at 17:37 UTC
    What did you write in the games.txt file?
      Anonymous Monk,
      It was nearly 2 years ago but I seem to recall it was 1 character representing the number of moves and then 30 characters representing the game board (in C, strings are null terminated so 1 + 30 + null = 32). These game boards were generated randomly using Perl.

      Cheers - L~R

Log In?
Username:
Password:

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

How do I use this? | Other CB clients
Other Users?
Others scrutinizing the Monastery: (13)
As of 2015-07-30 08:51 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (270 votes), past polls