Counting the maximum number of four-in-a-row wins

Question

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");
}

Answer 1

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

Answer 2

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 2³⁹ to 2^19.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.