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:

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

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