"be consistent" 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??

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

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

Create A New User
Node Status?
node history
Node Type: note [id://1054042]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (3)
As of 2017-08-22 00:09 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Who is your favorite scientist and why?

Results (326 votes). Check out past polls.

Notices?