Need to speed up pattern matching in jagged array

Question

I have a jagged array, 20 by 20. I try to match 700 different patterns that are built like smaller jagged arrays. The values that are matched (bytes OR:ed together) can be "player", "opponent", "empty" or "don't care" or a mix of these. The pattern size ranges from 4x4 to 7x7.

How can I speed this up? I am sure there is a better way to do this. Right now it takes around a second to check for all the patterns. I need to know all the matches, not just once for each pattern.

// Iterate through all patterns
for( int patNum = 0; patNum < whitePatterns.Length; patNum++)
{
    // Get current pattern
    pat = whitePatterns[patNum];

    col = pat.pattern.Length;
    row = pat.pattern[0].Length;

    for (int x = 0; x < myBoard.Size - col + 1; ++x)
    {
        for (int y = 0; y < myBoard.Size - row + 1; ++y)
        {
            for (int xx = 0; xx < col; ++xx)
                for (int yy = 0; yy < row; ++yy)
                {
                    count++;
                    if ((myBoard.board[x + xx][y + yy] & pat.pattern[xx][yy]) == 0)
                    {
                        goto loopY;
                    }
                }

            // Found a match!

            loopY: ;
        }
    }
}

Answer 1

Sometimes brute-force is the best approach. However, you're unlikely to be taking advantage of your CPU. As a very basic start, use parallelisation to take full advantage of your machines processing power.

Parallel.ForEach(whitePatterns, wp =>
{
int col = wp.pattern.Length;
int row = wp.pattern[0].Length;
for (int x = 0; x < myBoard.Size - col + 1; ++x)
{
    for (int y = 0; y < myBoard.Size - row + 1; ++y)        
    {
        for (int xx = 0; xx < col; ++xx)
            for (int yy = 0; yy < row; ++yy)
        {
            count++;
            if ((myBoard.board[x + xx][y + yy] & wp.pattern[xx][yy]) == 0)
            {
                goto loopY;

            }
        }

        // Found a match!

    loopY: ;
    }       
}
});

Answer 2

So you have a fixed set of patterns and you want to search the game board for all occurrences of those patterns.

This sounds suspiciously like having a fixed set of search strings that you want to find over a large body of text.

I'm not saying that it would be easy, but you could build a state machine from that fixed set of patterns and then run what is essentially a modified the Aho-Corasick algorithm on it.

Actually, what you'd do is each line of each pattern is considered a "string", and you build the Aho-Corasick tree structure from those patterns. You then run through the entire game board to find all of the matching strings. Your result will be a set of pattern rows with their starting addresses (row, col) and pattern numbers.

Sort those results by pattern number, row number (row number in the pattern, that is), starting column, and starting row. Then you can go sequentially through that sorted list and pick out matching patterns. A pattern matches if its first row starts at game board position (row, col), next row starts at game board position (row+1, col), etc.

It will take some (small) amount of time to generate the state machine, but you only have to do that once. After that, the searches are incredibly quick. Sorting the results and picking out the matches would be very fast.

I built an Aho-Corasick pattern matcher in C# that might help you get started. See my article, Aho-Corasick Revisited.