8
\$\begingroup\$

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 <Foundation/Foundation.h>
#import <UIKit/UIKit.h>

@interface DMMatch : NSObject

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

@property CGPoint firstPosition;
@property CGPoint secondPosition;

@end

DMMatch.m

#import "DMMatch.h"

@implementation DMMatch

+(DMMatch *) matchWithFirstPosition:(CGPoint)firstPos secondPosition:(CGPoint)secondPos {
    DMMatch *match = [[DMMatch alloc]initWithFirstPosition:firstPos secondPosition:secondPos];
    return match;
}

-(instancetype) initWithFirstPosition:(CGPoint)firstPos secondPosition:(CGPoint)secondPos {
    self = [super init];
    if (self) {
        _firstPosition = firstPos;
        _secondPosition = secondPos;
    }
    return self;
}

@end

DMMatchBoardEvalPair.h

#import <Foundation/Foundation.h>
#import "DMMatch.h"
#import "DMBoardEval.h"

@interface DMMatchBoardEvalPair : NSObject

+(DMMatchBoardEvalPair *) pairWithMatch:(DMMatch *)match boardEval:(DMBoardEval *)boardEval;

@property DMMatch *match;
@property DMBoardEval *boardEval;
@property int score;

@end

DMMatchBoardEvalPair.m

#import "DMMatchBoardEvalPair.h"
#import "DMMoveScore.h"

@implementation DMMatchBoardEvalPair

+(DMMatchBoardEvalPair *) pairWithMatch:(DMMatch *)match boardEval:(DMBoardEval *)boardEval {
    return [[DMMatchBoardEvalPair alloc]initWithMatch:(DMMatch *)match boardEval:(DMBoardEval *)boardEval];
}
-(DMMatchBoardEvalPair *) initWithMatch:(DMMatch *)match boardEval:(DMBoardEval *)boardEval {
    self = [super init];
    if (self) {
        _match = match;
        _boardEval = boardEval;
        _score = 0;
        for (DMMoveScore *score in _boardEval.scores) {
            _score += score.points;
        }
    }
    return self;
}

@end

DMMatchFinder.h

#import <Foundation/Foundation.h>
#import "DMGameBoard.h"
#import "DMMatch.h"

@interface DMMatchFinder : NSObject

+(DMMatchFinder *) finderWithBoard:(DMGameBoard *)board;

-(DMMatch *) bruteForceRandomMatch;

//this takes about one full second on the iPod
-(DMMatch *) bestMatch;

//analyze the best boards and then the best boards of those best boards etc
//does not work very well because the actual fill-in results of the swap are random and not known ahead of time
-(DMMatch *) bestMatchTwoForwardFast;
-(DMMatch *) bestMatchThreeForwardFast;

@end

DMMatchFinder.m

#import <UIKit/UIKit.h>
#import "DMBoardEval.h"
#import "DMMatchFinder.h"
#import "DMMatch.h"
#import "DMMatchBoardEvalPair.h"
#import "DMMoveScore.h"
#import "DMOrb.h"
#import "DMRow.h"

#import "BZGridTools.h"

static const int kNumOrbsPerRow = 9;

@implementation DMMatchFinder {
    DMGameBoard *_board;
    NSMutableArray *_allPossibleMatches;
}

#pragma mark - Initialization
+(DMMatchFinder *) finderWithBoard:(DMGameBoard *)board {
    DMMatchFinder *finder = [[DMMatchFinder alloc]initWithBoard:board];
    return finder;
}
-(id) initWithBoard:(DMGameBoard *)board {
    self = [super init];
    if (self) {
        _board = [DMGameBoard boardWithBoard:board];
        _allPossibleMatches = [self allPotentialMatches];
    }
    return self;
}

#pragma mark - Best Match Levels
-(DMMatch *) bruteForceRandomMatch {
    DMMatch *bruteForceRandomMatch = nil;

    //without the shuffle it will favor the bottom lefthand side of the board for matches
    [self shuffleArray:_allPossibleMatches];

    for (DMMatch *match in _allPossibleMatches) {
        DMBoardEval *boardEval = [[DMBoardEval alloc]initWithOrbCalculator:nil];
        boardEval.board = _board;

        if ([boardEval swapHasMatchesForPosition:match.firstPosition secondPosition:match.secondPosition]) {
            bruteForceRandomMatch = match;
            break;
        }

    }
    return bruteForceRandomMatch;
}
-(DMMatch *) bestMatch {
    DMMatchBoardEvalPair *bestMatchBoardEvalPair = [self bestMatchBoardEvalPairForPairs:[self allMatchBoardEvalPairsForBoard:_board]];
    return bestMatchBoardEvalPair.match;
}
-(DMMatch *) bestMatchTwoForwardFast {

    DMMatch *bestMatch = nil;
    int highestScore = 0;

    NSArray *bestMatchBoardEvalPairs = [self bestMatchBoardEvalPairs:2 ForPairs:[self allMatchBoardEvalPairsForBoard:_board]];

    for (DMMatchBoardEvalPair *pair in bestMatchBoardEvalPairs) {

        int fullMatchScore = pair.score;

        DMMatchBoardEvalPair *bestPair = [self bestMatchBoardEvalPairForPairs:[self allMatchBoardEvalPairsForBoard:pair.boardEval.board]];
        fullMatchScore += bestPair.score;

        if (fullMatchScore > highestScore) {
            highestScore = fullMatchScore;
            bestMatch = pair.match;
        }
    }

    return bestMatch;
}
//if you increase the number inside here to 3, runs out of memory
-(DMMatch *) bestMatchThreeForwardFast {

    DMMatch *bestMatch = nil;
    int highestScore = 0;

    NSArray *bestMatchBoardEvalPairs = [self bestMatchBoardEvalPairs:2 ForPairs:[self allMatchBoardEvalPairsForBoard:_board]];

    for (DMMatchBoardEvalPair *pair in bestMatchBoardEvalPairs) {

        int fullMatchScore = pair.score;

        NSArray *bestMatchBoardEvalPairsLevel2 = [self bestMatchBoardEvalPairs:2 ForPairs:[self allMatchBoardEvalPairsForBoard:pair.boardEval.board]];

        for (DMMatchBoardEvalPair *pairLevel2 in bestMatchBoardEvalPairsLevel2) {

            fullMatchScore += pairLevel2.score;

            DMMatchBoardEvalPair *bestPairLevel3 = [self bestMatchBoardEvalPairForPairs:[self allMatchBoardEvalPairsForBoard:pairLevel2.boardEval.board]];
            fullMatchScore += bestPairLevel3.score;
        }

        if (fullMatchScore > highestScore) {
            highestScore = fullMatchScore;
            bestMatch = pair.match;
        }
    }

    return bestMatch;
}

#pragma mark - Algorithm
-(NSMutableArray *) allPotentialMatches {

    //get all positions on the board
    NSMutableArray *allPositions = [[NSMutableArray alloc]init];
    for (int i = 0; i < kNumOrbsPerRow; i++) {
        for (int j = 0; j < kNumOrbsPerRow; j++) {
            CGPoint point = CGPointMake(i, j);
            [allPositions addObject:[NSValue valueWithCGPoint:point]];
        }
    }

    //get all combinations of adjacent positions
    NSMutableArray *allPotentialMatches = [[NSMutableArray alloc]init];
    for (NSValue *pointValue in allPositions) {
        for (NSValue *secondValue in allPositions) {
            if ([BZGridTools isPoint:pointValue.CGPointValue adjacentTo:secondValue.CGPointValue]) {
                DMMatch *match = [DMMatch matchWithFirstPosition:pointValue.CGPointValue secondPosition:secondValue.CGPointValue];
                [allPotentialMatches addObject:match];
            }
        }
    }

    return allPotentialMatches;
}
-(NSMutableArray *) allMatchBoardEvalPairsForBoard:(DMGameBoard *)board {
    NSMutableArray *allBoardEvalsWithMatches = [[NSMutableArray alloc]init];

    for (DMMatch *match in _allPossibleMatches) {

        //create a new BoardEval for each potential match
        DMBoardEval *boardEval = [[DMBoardEval alloc]initWithOrbCalculator:[[DMOrbCalculator alloc]init]];
        boardEval.board = board;

        //if there are any possible matches, save the scored result
        if ([boardEval swapHasMatchesForPosition:match.firstPosition secondPosition:match.secondPosition]) {

            //using this is not showing a significant speed increase in testing
            //[boardEval resolveSwapForMatchFinderBetweenPosition:firstOrb.boardPosition position:secondOrb.boardPosition direction:[self directionForFirstOrb:firstOrb secondOrb:secondOrb]];

            //this one is necessary for the deeper level searches because otherwise it does not have the actually resolved board to keep searching
            //unfortunately, it may guess wrong because the results of the match on the game board are random
            [boardEval resolveSwapBetweenPosition:match.firstPosition position:match.secondPosition direction:[self directionForFirstPosition:match.firstPosition secondPosition:match.secondPosition]];

            [allBoardEvalsWithMatches addObject:[DMMatchBoardEvalPair pairWithMatch:match boardEval:boardEval]];
        }
    }

    return allBoardEvalsWithMatches;
}
-(NSArray *) bestMatchBoardEvalPairs:(int)count ForPairs:(NSMutableArray *)pairs {
    NSArray *sortedMatchPairs = [self sortedMatchBoardEvalPairs:pairs];
    NSMutableArray *bestBoardEvalMatchPairs = [[NSMutableArray alloc]init];
    for (int i = 0; i < count; i++) {
        if (sortedMatchPairs.count > i) {
            [bestBoardEvalMatchPairs addObject:sortedMatchPairs[i]];
        }
    }
    return bestBoardEvalMatchPairs;
}
-(NSArray *) sortedMatchBoardEvalPairs:(NSArray *)pairs {
    NSSortDescriptor *sortDescriptor = [[NSSortDescriptor alloc]initWithKey:@"score" ascending:NO];
    NSArray *sortDescriptors = [NSArray arrayWithObject:sortDescriptor];
    NSArray *sortedArray = [pairs sortedArrayUsingDescriptors:sortDescriptors];
    return sortedArray;
}
-(DMMatchBoardEvalPair *) bestMatchBoardEvalPairForPairs:(NSMutableArray *)pairs {
    NSSortDescriptor *sortDescriptor = [[NSSortDescriptor alloc]initWithKey:@"score" ascending:NO];
    NSArray *sortDescriptors = [NSArray arrayWithObject:sortDescriptor];
    NSArray *sortedArray = [pairs sortedArrayUsingDescriptors:sortDescriptors];
    return [sortedArray firstObject];
}

#pragma mark - Utility Methods
-(void) shuffleArray:(NSMutableArray *)array {
    NSUInteger count = array.count;
    for (NSUInteger i = 0; i < count; ++i) {
        NSInteger remainingCount = count - i;
        NSInteger exchangeIndex = i + arc4random_uniform((u_int32_t )remainingCount);
        [array exchangeObjectAtIndex:i withObjectAtIndex:exchangeIndex];
    }
}
-(BZDirection) directionForFirstPosition:(CGPoint )firstPosition secondPosition:(CGPoint)secondPosition {
    if (firstPosition.x > secondPosition.x) {
        return BZDirectionRight;
    } else if (firstPosition.x < secondPosition.x) {
        return BZDirectionLeft;
    } else if (firstPosition.y > secondPosition.y) {
        return BZDirectionDown;
    } else if (firstPosition.y < secondPosition.y) {
        return BZDirectionUp;
    }
    return BZDirectionNotAdjacent;
}

@end

Test Results

//Brute Force
2015-02-02 12:12:42.439 Match3[14988:598894] score = 5050, matches = 155
2015-02-02 12:12:42.623 Match3[14988:598894] score = 5000, matches = 154
2015-02-02 12:12:42.834 Match3[14988:598894] score = 5040, matches = 156
Executed 1 test, with 0 failures (0 unexpected) in 0.709 (0.710) seconds

//simple best match
2015-02-02 12:13:31.536 Match3[15010:599663] score = 5090, matches = 133
2015-02-02 12:13:34.622 Match3[15010:599663] score = 5170, matches = 129
2015-02-02 12:13:37.965 Match3[15010:599663] score = 5070, matches = 123
Executed 1 test, with 0 failures (0 unexpected) in 12.290 (12.291) seconds

//fast depth 2 search
2015-02-02 12:15:15.750 Match3[15037:600906] final score = 5120, final matches = 140
2015-02-02 12:15:28.438 Match3[15037:600906] final score = 5030, final matches = 113
2015-02-02 12:15:45.862 Match3[15037:600906] final score = 5040, final matches = 126
Executed 1 test, with 0 failures (0 unexpected) in 53.432 (53.432) seconds

//fast depth 3 search
2015-02-02 12:17:30.721 Match3[15053:602012] final score = 5010, final matches = 131
2015-02-02 12:18:26.876 Match3[15053:602012] final score = 5100, final matches = 134
2015-02-02 12:19:35.797 Match3[15053:602012] final score = 5150, final matches = 137
Executed 1 test, with 0 failures (0 unexpected) in 206.196 (206.197) seconds

In these tests, the computer plays until they reach 5000 and then stops. Lower total matches means more efficient choices over the course of the game. As you can see, the deeper searches do not necessarily guarantee a better result. I believe there are a few reasons for this. The computer will choose the two best boards based on the current board in order to try further matching, but the results are random, therefore 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. I don't really know how to deal with these problems, but again, it doesn't really matter, because anything deeper than a top level search is really slow anyway.

\$\endgroup\$
  • \$\begingroup\$ Are you familiar with Xcode instruments? I'd be interested in seeing your NSDictionary approach and figuring out where the performance issue in that was. \$\endgroup\$ – nhgrif Feb 2 '15 at 22:31
2
\$\begingroup\$

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 < kNumOrbsPerRow; ++i) {
        for (int j = 0; j < kNumOrbsPerRow; ++j) {
            if (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.

\$\endgroup\$

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.