Brute Force (and not) Bejeweled AI

My approach to solving the problem of selecting the best match on a bejeweled board is a fully object oriented approach. Some of the other relevant code can be found in my previous questions regarding bejeweled, but this question will only be about the DMMatchFinder class and associated classes.

I should note that I originally attempted to use an NSDictionary for holding the DMMatches and their corresponding DMBoardEval objects, but I had to give up this approach. It is possible to use custom objects such as DMMatch as keys for a dictionary, but I could not seem to count on isEqual to consistently return YES when iterating over the dictionary objects and trying to get the key related to an object. I did override the isEqual method in order to force it to work, but this was a performance drain. Simply placing the DMMatch and DMBoardEval in the DMMatchBoardEvalPair class together greatly improved the readability of the code, and provided the added benefit of having a score property to use to sort arrays of these objects.

I tried to figure out a way to input the desired depth for searching rather than having separate methods for two and three depth searching, however I could not really get it working. In reality, it seems that it doesn't matter because any searches deeper than the top level (or current) board are very computationally expensive anyway. Because of this, the algorithms here will only search deeper starting with the two best boards created by matches at the top level. Any more than this and the program runs out of memory. I will provide the results of some unit tests at the bottom of this question to give you an idea of the time it takes to make matches. However, even just the simple bestMatch search takes about a second on an iPod touch 5th generation.

DMMatch.h

```
#import
#import

@interface DMMatch : NSObject

+(DMMatch *) matchWithFirstPosition:(CGPoint)firstPos secondPosition:(CGPoint)secondPos;

@property CGPo

each attempt will have different orbs filling in the board than each other, and this will also be different from the orbs filling in the board in the live game

The way to solve this problem is: when you fill in the board, fill it in with a special kind of cell, UNKNOWN, and have your AI treat UNKNOWN specially (for example, treat it as never matching any of its neighbors).

Your allPotentialMatches function is ridiculously inefficient. Try replacing it with something like

-(NSMutableArray *) allPotentialMatches
{
    NSMutableArray *result = [NSMutableArray array];

    // for each position on the board, swap it either left or up
    // (swapping it "down" is equivalent to swapping its lower neighbor "up")
    for (int i = 0; i  0) {
                [result addObject:
                    [DMMatch matchWithFirstPosition: CGPointMake(i,j)
                             secondPosition: CGPointMake(i-1,j)]];
            }
            if (j > 0) {
                [result addObject:
                    [DMMatch matchWithFirstPosition: CGPointMake(i,j)
                             secondPosition: CGPointMake(i,j-1)]];
            }
        }
    }

    return result;
}

This reduces the size of the array by half, and reduces the amount of work actually being done from O(N^4) to O(N^2). Benchmark again; is it fast enough now that looking ahead several moves is feasible? If so, the next step is to implement the UNKNOWN cell type.

StackExchange Code Review Q#79376, answer score: 2