4
\$\begingroup\$

It all started during a "fourInARow" game... A friend of mine asked: "If you drop in all 42 stones, what will the number of "four in a row"s be with the optimal configuration?"

I thought it should be something like this: (0 is player1's coins , 1 is player2's coins)

1111110
1111100
1111000
1110000
1100000
1000000

Which should be 12row+12col+12diagDownLeft=36.

After that I tried to write a program to bruteforce test all possible combinations... After my calculations the sum of all possible ways should be (42!)/((21!)*(21!))≈5,4*10^11

I first tried the code on an android phone... But after implementing a progress bar I estimated a runtime of 9 years.

The situation on desktop wasn't much better ≈300days with 1.000.000FieldsTested/sec.

I'm also interested how the situation evolves for larger fields than 7(width)*6(height)...

Details on how to count the "sum of four in a rows": If you have 7 clips of equal color in one row then this counts as 4*" fourInARow" (same is true for diagonal or rows)

I took a look on other possibilities to count the "fourInARow"s more efficiently, but most solutions are more optimized to find only one winning condition like this one:

Does anyone have a recommendation how to optimize the performance of the code or is everything lost because I need a performance speedup of at least x300.

Should I try to use parallel processing and opencl? Or is the code too inefficient?

I tried to avoid functions and so on as much as possible and sorry for bad coding style, thats because I come from the "assembler/hardware" area where you don't have to bother about names :).

My code so far:

#include <stdio.h>
int main()
{
char height = 6; //height of the field
char width = 7;  //width of the field
short length = height * width; // number of places in the field
short temp1;
short temp2;
short temp3;
short temp4;
short scoreold = 0;
short scorenew = 0;
long int b = 0;
long int a=0;
//check if field has even number of places, if not abort
if ((length % 2) != 0)
{
    printf("Error Code 1: Uneven number of fields");
    return 1;
}
char field[length];
//generate initial field (111 ... 111000 ... 000)
for (short a = 0; a < (length / 2); a++)
{
    field[a] = 1;
}
for (short a = (length / 2); a < length; a++)
{
    field[a] = 0;
}
//iterate through every possible combination
while ((b++) < (538257874440))  // (42!)/((21!)*(21!))
{
  a++;
    temp1 = 0;
    //generate the next testing setup for the field
    while (field[temp1] == 0)
    {
        temp1++;     //temp1 is number of 0 from the low end
    };
    if (temp1 == 0)  //if there are no zeros from low end move first one one space to the higher end: eg. 000....000111...000 => 000...010111...111
    {
        while (field[temp1] == 1)
        {
            temp1++;
        }
        field[temp1--] = 1;
        field[temp1] = 0;
    }
    else    
    {
        temp2 = temp1;
        while (field[temp2] == 1)
        {
            temp2++;
        }
        field[temp2] = 1;
        temp2 = temp2 - (++temp1);
        while ((temp1--) != 0)
        {
            field[((temp1) + temp2)] = 0;
        }
        while ((temp2--) != 0)
        {
            field[temp2] = 1;
        }
    }
    // end field generation

    // test for rows (temp1 used as iterator through all fields)
    for (temp1 = 0; temp1 < (width * height); temp1++)
    {
        if (temp1 % width == 0) //beginning of new row reset counters
        {
            temp2 = 0;    //used as counter for player1
            temp3 = 0;    //used as counter for player2
        }
        if (field[temp1] == 0) //coin of player 2
        {
            temp2 = 0;
            temp3++;
        }
        else  //coin of player 1
        {
            temp2++;
            temp3 = 0;
        }
        if((temp2 > 3) | (temp3 > 3)) //four in a row detecred increase score
        {
            scorenew++;
            // test1++;
        }
    }
    // test for colums
    for (temp1 = 0; temp1 < (width * height); temp1++)
    {
        if (temp1 % height == 0) //reset counter for new column
        {
            temp2 = 0;
            temp3 = 0;
        }
        if (field[((temp1 * width) % (width * height)) + (temp1 / (height))] == 0)
        {
            temp2 = 0;
            temp3++;
        }
        else
        {
            temp2++;
            temp3 = 0;
        }
        if ((temp2 > 3)|(temp3 > 3))
        {
            scorenew++;
            // test2++;
        }
    }
    // test down right
    for (temp1 = 0; temp1 < ((width + height) - 1); temp1++)
    {
        temp2 = 0;
        temp3 = 0;
        if (temp1 < width)
        {
            temp4 = temp1;
        }
        else
        {
            temp4 = (((temp1 - width) + 1) * width);
        }
        while (temp4 < (width * height))
        {
            if (field[temp4] == 0)
            {
                temp2 = 0;
                temp3++;
            }
            else
            {
                temp2++;
                temp3 = 0;
            }
            if ((temp2 > 3)|(temp3 > 3))
            {
                scorenew++;
                // test3++;
            }
            if ((temp4 + 1) % width == 0)
            {               // right border reached
                break;
            }

            temp4 += (width + 1);
        }
    }
    // test down left
    for (temp1 = 0; temp1 < ((width + height) - 1); temp1++)
    {
        temp2 = 0;
        temp3 = 0;
        if (temp1 < width)
        {
            temp4 = temp1;
        }
        else
        {
            temp4 = (((temp1 - width) + 1) * width) + (width - 1);
        }
        while (temp4 < (width * height))
        {
            if (field[temp4] == 0)
            {
                temp2 = 0;
                temp3++;
            }
            else
            {
                temp2++;
                temp3 = 0;
            }
            if ((temp2 > 3)|(temp3 > 3))
            {
                scorenew++;
                // test4++;
            }

            if (temp4 % width == 0)
            {               // left border reached
                break;
            }
            temp4 += (width - 1);
        }
    }
    if (scorenew > scoreold)
    {
        scoreold = scorenew;
        for (temp1 = 0; temp1 < 42;)
        {
            printf("%d ", field[temp1++]);
            if ((temp1) % width == 0)
            {
                printf("\n");
            }
        }
        printf("score: %d" , scoreold);
        /* printf("T1:%d\n", test1); printf("T2:%d\n", test2);
           printf("T3:%d\n", test3); printf("T4:%d\n", test4); */
        printf("\n\n");
    }
    if(a==538257){
      printf("%f\n",((float)b)/538257874440);
      a=0;
    }
    scorenew = 0;
    /* test1 = 0; test2 = 0; test3 = 0; test4 = 0; */
}
printf("Finished!---------------------\n");
}
\$\endgroup\$
5
\$\begingroup\$

Your machine-code background is certainly showing through. Let's see if we can help you transition to high-level language!

Use 'natural' data types by default.

The assembly-language programmer notes that width and height will fit in a char, and uses the narrowest types necessary. That doesn't necessarily lead to the fastest code, and in C we lean towards int or unsigned int unless we're storing many (millions of) such values.

int main()
{
    const unsigned int height = 6;
    const unsigned int width = 7;
    const unsigned int length = height * width; // number of places in the field

I also removed the "obvious" comments above; this reduces clutter, and draws attention to the comment that explains that length actually means the total size, or area, of the grid.

The other variables declared at the top of function may be confined to a narrower scope, so let's leave them for now.

Why disallow odd-sized grids?

I don't see why we couldn't work with a 7x7 grid, for instance. If this test really is necessary, then we should write the error message to the standard error stream rather than standard output:

Simplify the grid initialization

Instead of hand-writing a loop, we can use the memset() function from the standard library:

    char field[length];
    {
        unsigned int half = length / 2;
        memset(field, 1, half);
        memset(field + half, 0, length - half);
    }

Don't pre-calculate the number of iterations

This loop (which would be clearer if it were written as a for loop), doesn't automatically adapt if you change width or height; also, we run the risk that the constant is outside the range of long int (C guarantees that b can store values up to 2,147,483,647, which isn't enough):

while ((b++) < (538257874440))  // (42!)/((21!)*(21!))

One way around this is to write a function:

int advance_board(char *board, size_t length);

We can then implement this function using the same logic we already have, except that we return a true value if we successfully advance, and a false value (i.e. 0) when we try to advance past the last valid board state. Then the main loop becomes

do  {
   /* ... */
} while (advance_board(board, length));

and we can test this part of the program independently with a smaller board:

int main() {
    char board[] = { 1, 1, 1, 0, 0 };
    const size_t length = sizeof board / sizeof *board;

    do  {
        printf("%d%d%d%d%d\n", board[0], board[1], board[2], board[3], board[4]);
    } while (advance_board(board, length));
}

Reduce common code in the result count

There are four tests, one for each of the different orientations (horizontal, vertical, leading diagonal, trailing diagonal). All that differs between these are how the x and y coordinates change when going from one cell to the next. These four could be refactored into a single function which includes the x and y increments as parameters. Then the logic becomes

do {
    int score = 0;
    /* horizontal */
    for (int row = 0;  row < height;  ++row)
        score += count_wins(field, width, height, 0, row, 1, 0);
    /* vertical */
    for (int col = 0;  col < width;  ++col)
        score += count_wins(field, width, height, col, 0, 0, 1);
    /* leading diagonal */
    for (int row = 0;  row < height-4;  ++row)
        score += count_wins(field, width, height, 0, row, 1, 1);
    for (int col = 0;  col < width-4;  ++col)
        score += count_wins(field, width, height, col, 0, 1, 1);
    /* trailing diagonal */
    for (int row = 0;  row < height-4;  ++row)
        score += count_wins(field, width, height, width-1, row, 1, -1);
    for (int col = 4;  col < width;  ++col)
        score += count_wins(field, width, height, col, 0, 1, -1);

Again, separating into a function allows the logic to be tested independently with a smaller field. And we might consider extracting the constant 4 so we can play n-in-a-row instead.

Take advantage of symmetries

You'll get a big performance win by noting that the board has 4-way symmetry, so we should be able to greatly reduce the number of configurations to be tested. A simple test to skip ¾ of the possible boards is to omit any where more than half of, say, the '1' counters are on the upper or left-hand side of the board, as we know that we'll consider the reflections of those during our search.

Another observation is that swapping the ones and zeros gives the same score, so we can further reduce the search space by half.


My version

I'm sure there remain some significant optimizations, but this should be a start; I compiled with gcc -std=c11 -Wall -Wextra -O3 -march=native.

#include <stdio.h>
#include <string.h>

int advance_board(char *board, size_t length)
{
    if (length < 2) return 0;

    /* Find the last transition from 1 to 0 */
    char *p = board+length;
    while (p > board && *--p == 1)
        ;
    while (p > board && *--p == 0)
        ;
    if (*p == 0)
        /* we reached the last permutation */
        return 0;

    /* Swap the adjoining 0 and 1 */
    *p++ = 0;
    *p++ = 1;
    /* Reverse the tail of the board */
    for (char *q = board+length-1;  p < q;  ++p, --q) {
        char c = *q;
        *q = *p;
        *p = c;
    }
    return 1;
}

int weigh(const char *board, int length)
{
    int weight = 0;
    for (const char *p = board;  p < board + length;  ++p)
        weight += *p;
    return weight;
}

int is_top_heavy(const char *board, int length)
{
    return weigh(board, length / 2) > (length+1)/2;
}

int is_left_heavy(const char *board, int width, int height)
{
    int weight = 0;
    for (int row = 0;  row < height;  ++row)
        weight += weigh(board+width*row, width / 2);
    return weight > height * width / 2;
}

int count_wins(const char *board, int width, int height, int x, int y, int dx, int dy)
{
    int score = 0;
    int count[2] = { 0, 0 };
    while (0 <= x && x < width && 0 <= y && y < height) {
        int color = board[y * width + x];
        if (++count[color] >= 4) ++score;
        count[!color] = 0;
        x += dx;
        y += dy;
    }
    return score;
}

void print_field(int score, const char *field, int width, int height)
{
    for (int row = 0;  row < height;  ++row) {
        for (int col = 0;  col < width;  ++col) {
            printf("%d", *field++);
        }
        printf("\n");
    }
    printf("Score %d\n-----\n", score);
}


int main()
{
    const int height = 6;
    const int width = 7;
    const int length = height * width; // number of places in the field

    char field[length];
    {
        int half = length / 2;
        memset(field, 1, half);
        memset(field + half, 0, length - half);
    }

    char best_field[length];

    int best_score = 0;
    do {
        if (is_top_heavy(field, length)) continue;
        if (is_left_heavy(field, width, height)) continue;
        int score = 0;
        /* horizontal */
        for (int row = 0;  row < height;  ++row)
            score += count_wins(field, width, height, 0, row, 1, 0);
        /* vertical */
        for (int col = 0;  col < width;  ++col)
            score += count_wins(field, width, height, col, 0, 0, 1);
        /* leading diagonal */
        for (int row = 0;  row < height-4;  ++row)
            score += count_wins(field, width, height, 0, row, 1, 1);
        for (int col = 0;  col < width-4;  ++col)
            score += count_wins(field, width, height, col, 0, 1, 1);
        /* trailing diagonal */
        for (int row = 0;  row < height-4;  ++row)
            score += count_wins(field, width, height, width-1, row, 1, -1);
        for (int col = 4;  col < width;  ++col)
            score += count_wins(field, width, height, col, 0, 1, -1);

        if (score > best_score) {
            best_score = score;
            memcpy(best_field, field, length);
            print_field(score, field, width, height);
        }
    }  while (advance_board(field, length) && field[0]);
}

This code completed in under 20 hours on my machine, with the following final result:

1000000
1100000
1110000
1111000
1111100
1111110
Score 37
\$\endgroup\$
  • \$\begingroup\$ Hello Toby, First of all thank you for your in depth answer. The symmetry aproach was something I totally missed, thanks for pointing that out. This would like you said easily give x8 performance. Thats a good start, do you think that I can get away without parralalisation? \$\endgroup\$ – Beny Benz Aug 21 '17 at 12:56
  • 1
    \$\begingroup\$ I thought about parallelisation, but didn't pursue it. The generation of boards is the only part that needs to be serialised (well, also the update of the high score). Boards can be scored in parallel; it might make sense to devote one thread to generating positions for other threads to evaluate? I also wonder whether you only want to look at positions that are possible in a real game (where players take turns to drop their stones into the grid), or whether that constraint is waived? Boards with a single-colour row along the bottom are obviously unreachable, for example. \$\endgroup\$ – Toby Speight Aug 21 '17 at 13:20
  • \$\begingroup\$ Oh yeah I forgot to mention that. Yes the rule of the game are completely disobeyed. So 7 stones of one player in the last row is a possible solution. I also thought about parralelizing thr boards generation by giving one thread the start field (000000111111) and the next one something like (000111000111) to start with and modifing thr abort condition for each thread. For the hight score I thout that each thread could store its own highscore and compare the n thread's highscores afterwars... I initially planned to use a gpu because of the massive parralel power, but I need learn opencl then. \$\endgroup\$ – Beny Benz Aug 21 '17 at 14:10
  • \$\begingroup\$ @TobySpeight, boards with a single-colour row along the bottom are perfectly reachable. Boards with two single-colour rows along the bottom aren't. \$\endgroup\$ – Peter Taylor Aug 21 '17 at 15:40
5
\$\begingroup\$
char field[length];

For high-performance brute-force combinatorics involving binary strings, bit fiddling is the way to go. You don't want an array of bits, you want an array of rows. Consider that with

int rows[height];

you can count vertical fours-in-a-row with

int scoreVertical = 0;
for (int i = 0; i + 3 < height; i++)
{
    int fours1 = rows[i] & rows[i+1] & rows[i+2] & rows[i+3];
    int fours0 = (rows[i] | rows[i+1] | rows[i+2] | rows[i+3]) ^ ((1 << width) - 1);
    scoreVertical += hammingWeight(fours0) + hammingWeight(fours1);
}

where you may know hammingWeight as the popcnt instruction. Similar loops with shifts give diagonal and anti-diagonal fours. That just leaves horizontal fours, but I would handle them differently. Since you're going to need to generate row sets which have the right total Hamming weight I would have an initialisation phase where you generate all possible rows and store them indexed by Hamming weight, and this generation phase would be a good time to calculate and cache their four-in-a-row counts too.

The reason for storing the rows indexed by Hamming weight is that it helps a lot in symmetry reduction. Toby Speight's answer already talks about that, so I won't repeat it.

After bit-fiddling and symmetry reduction, the next obvious optimisation is early rejection. Given that you have a good idea for a plausible best board, you can pre-calculate its score. Suppose you can bound the score of the last three rows such that if you don't already have a score of S after the first three rows then you can't possibly beat the current best score. In the best case this would allow you to reduce the number of cases to consider to about its square root (i.e. from 239 to 219.5), and if you obtain that best case then the program shouldn't take more than a couple of minutes to run. (The reason for not doing this first would be that the effort required is probably on the order of hours, so the simpler optimisations might allow you to solve the problem with less elapsed thought + CPU time).

There's another useful technique for this general class of problems called meet-in-the-middle, where you generate all half boards and then try to pair them up. This would be more useful if you want to generalise to larger boards (where the overlap between the two halves in which fours can be found isn't the entire board), but you could try to apply it if the ideas of the previous paragraph turn out not to work for this particular problem. In that case maybe it's at least possible to lower-bound the number of horizontal fours there must be, and then by indexing half-boards by Hamming weight and number of horizontal fours you can quick-reject some pairs without calculating fours in the other three directions.

\$\endgroup\$
  • \$\begingroup\$ An alternative that I had in mind involves using a single uint64_t to hold the entire board, with shiftable constants for the four directions of row (you have to be careful not to overshift, as you'll wrap without warning). That simplifies my is_top_heavy() and friends with simple Hamming weight versions. \$\endgroup\$ – Toby Speight Aug 21 '17 at 16:34
  • \$\begingroup\$ An excellent point: that eliminates the loop in scoreVertical and variants. And for this size of board it's possible to have four bits of 0 padding between each row so that overshifting isn't an issue. \$\endgroup\$ – Peter Taylor Aug 21 '17 at 16:39
  • \$\begingroup\$ Tank you Peter for your answer. \$\endgroup\$ – Beny Benz Aug 21 '17 at 18:14
  • \$\begingroup\$ What do you think about first letting a row go through an and mask with n/4 ones which is shifted and afterwards xored. If the result is all zeros / ==0 then this was a 4 in a row for player1. And the same then ored with a the same mask and afterward xored for player2's score? Or is the 64bit with preconfigured shifting masks faster? \$\endgroup\$ – Beny Benz Aug 21 '17 at 19:26
  • \$\begingroup\$ @Beny, at this point the best suggestion is to try different approaches and profile them yourself. You'll learn a lot, including elements of performance on your particular system (that we can't really guess for you). \$\endgroup\$ – Toby Speight Aug 22 '17 at 7:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.