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

QM,
So, here is the problem: 
#!/usr/bin/perl
use strict;
use warnings;

while (<DATA>) {
    chomp;
    my $level = $_;
    my @work = {board => $level, hits  => 9};
    my $avail_hits = possible_hits($level);

    my %stat;

    while (@work) {
        my $item = pop @work;
        my ($board, $hits) = @{$item}{qw/board hits/};
        $hits--;

        for my $pos (possible_hits($board)) {
            my $new_board = play_board($board, $pos);

            # No need to continue if we have won
            if (game_won($new_board)) {
                $stat{$hits}++;
                next;
            }

            # Not able to continue if we have lost
            if (! $hits) {
                $stat{lost}++;
                next;
            }

            # We need to continue
            push @work, {board => $new_board, hits => $hits};
        }
    }
    print join(',',
        $level,
        $avail_hits,
        ($stat{lost} || 0),
        map {join(':', (9 - $_), ($stat{$_} || 0))} reverse 0 .. 8
    ), "\n";
}

sub game_won {
    my ($board) = @_;
    return $board =~ /^0{30}$/;
}

sub possible_hits {
    my ($board) = @_;
    my @possible;
    for (0 .. length($board) - 1) {
        push @possible, $_ if substr($board, $_, 1) ne '0';
    }
    return wantarray ? @possible : scalar @possible;
}

sub play_board {
    my ($board, $pos) = @_;
    hit(\$board, $pos);
    return $board;
}

sub hit {
    my ($board, $pos) = @_;

    # Ran off the edge of the board
    return if $pos < 0 || substr($$board, $pos, 1) eq '0'; # not sure 
+2nd instance can ever happen

    my $val = substr($$board, $pos, 1);
    $val--;

    substr($$board, $pos, 1, $val);

    if (! $val) {
        hit($board, n_neighbor($board, $pos));
        hit($board, s_neighbor($board, $pos));
        hit($board, e_neighbor($board, $pos));
        hit($board, w_neighbor($board, $pos));
    }
}

sub n_neighbor {
    my ($board, $pos) = @_;
    while (1) {
        $pos -= 5;
        last if $pos < 0;
        return $pos if substr($$board, $pos, 1) ne '0';
    }
    return -1;
}

sub s_neighbor {
    my ($board, $pos) = @_;
    while (1) {
        $pos += 5;
        last if $pos > 29;
        return $pos if substr($$board, $pos, 1) ne '0';
    }
    return -1;
}

sub e_neighbor {
    my ($board, $pos) = @_;
    my $min_val = int($pos / 5) * 5;
    while (1) {
        $pos -= 1;
        last if $pos < $min_val;
        return $pos if substr($$board, $pos, 1) ne '0';
    }
    return -1;
}

sub w_neighbor {
    my ($board, $pos) = @_;
    my $max_val = (int($pos / 5) * 5) + 4;
    while (1) {
        $pos += 1;
        last if $pos > $max_val;
        return $pos if substr($$board, $pos, 1) ne '0';
    }
    return -1;
}

__DATA__
101010000010101000000000010101
000000000000100000000000000000
211000000000000000000000000000
432114010304403414114124232323

[download]

It takes too long to figure out all the ways to play a game. I am thinking I need to lower the number of possible moves and limit how much time can be spent playing a single game. What do you think?

Update: I can complete approximately 40,000 games every 5 seconds. What I have done is impose a 6 hit limit along with randomly shuffling the return of possible_hits() and limited each board to 40,0000 games. I have manually tested this against a handful of boards and it appears to give a pretty good approximation of the results if all of them had been played. I would prefer a C based version of this which could likely do far more per second but my C is rusty (was never very good) and I can't remember how to manage a dynamic array.

Update 2: I turned the problem upside down and it became much easier. Instead of scoring how difficult the game was, I instead scored how easy the game was. I used a combined score of things like win to loss ratio, number of initial 1-hit moves to 1-hit wins, etc. The ones with the lowest score were the most difficult. Now I just need to code the actual game.

Cheers - L~R

  • Comment on Re^2: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
  • Download Code

Replies are listed 'Best First'.
Re^3: Challenge: Algorithm To Generate Bubble Blast 2 Puzzles With Difficulty
by Limbic~Region (Chancellor) on Sep 10, 2013 at 19:33 UTC
    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.
    Read more... (7 kB)

    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

[reply]
[d/l]
      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:
      Read more... (7 kB)

      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

[reply]
[d/l]
        What did you write in the games.txt file?
[reply]

      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

[reply]
[d/l]
[select]
        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

[reply]

In Section Seekers of Perl Wisdom