Beefy Boxes and Bandwidth Generously Provided by pair Networks
No such thing as a small change
 
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

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 wandering the Monastery: (7)
As of 2014-08-01 23:50 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Who would be the most fun to work for?















    Results (52 votes), past polls