/* Gridlock
Copyright (c) 2002-2003 by Brian Nenninger. All rights reserved.

Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#import "GenericAI.h"

#define DEBUG 0

static int LOSE_UTILITY = -(1<<30); // for losing positions
static int WIN_UTILITY  = 1<<30;

@interface ArrayConsumerEnumerator : NSEnumerator {
  NSLock *lock;
  NSMutableArray *sourceArray;
}
+(ArrayConsumerEnumerator *)enumeratorWithSourceArray:(NSMutableArray *)array lock:(NSLock *)theLock;
@end

@implementation ArrayConsumerEnumerator
+(ArrayConsumerEnumerator *)enumeratorWithSourceArray:(NSMutableArray *)array lock:(NSLock *)theLock {
  ArrayConsumerEnumerator *enumerator = [[[self alloc] init] autorelease];
  enumerator->sourceArray = array;
  enumerator->lock = theLock;
  return enumerator;
}

-(id)nextObject {
  id obj = nil;
  [lock lock];
  if ([sourceArray count]>0) {
    obj = [sourceArray lastObject];
    [sourceArray removeLastObject];
  }
  [lock unlock];
  return obj;
}
@end

@implementation GenericAI

-(id)init {
  if (self=[super init]) {
    //NSLog(@"Creating AI:%@", NSStringFromClass([self class]));
    threadLock = [[NSLock alloc] init];
    bestThreadMoves = [[NSMutableArray alloc] init];
  }
  return self;
}

-(void)dealloc {
  [threadLock release];
  [bestThreadMoves release];
  [super dealloc];
}

idAccessor(name, setName)
idAccessor(threadLock, setThreadLock)
idAccessor(bestThreadMoves, setBestThreadMoves)
intAccessor(depth, setDepth)
intAccessor(useThreads, setUseThreads)

// alpha-beta algorithm adapted from http://www.seanet.com/~brucemo/topics/alphabeta.htm
-(NSArray *)alphaBetaMoveForGame:(Game *)game
                           depth:(int)d
                           alpha:(int)alpha
                            beta:(int)beta
                  candidateMoves:(NSEnumerator *)moveenum
               positionsEvaluated:(int *)numEvaluated
                         utility:(int *)utility {
  int nextUtility;
  if (!moveenum) moveenum = [self enumeratorForMovesToConsiderForGame:game];
  
  NSArray *move, *nextMove, *bestMove=nil;
  Game *gameCopy = nil;
  int movenum=0;
  NSAssert2(alpha<beta, @"alpha(%d)>=beta(%d)", alpha, beta);

  while ((alpha<beta) && (move=[moveenum nextObject])) {
    id pool = [[NSAutoreleasePool alloc] init];

    if (!gameCopy) gameCopy = [game copy];
    else [game copyValuesToGame:gameCopy];

    // make and evaluate move
    movenum++;
    [gameCopy makeMoveSequence:move];
    // stop recursion if game is over or we're at depth 1
    if ([gameCopy isGameOver]) {
      int wpnum = [gameCopy winningPlayer];
      if (wpnum==[game currentPlayerNumber]) {
        nextUtility = WIN_UTILITY+d;
      }
      else if (wpnum!=0) {
        nextUtility = LOSE_UTILITY-d;
      }
      else {
        // tie; should handle this better
        nextUtility = -[self relativeUtilityForGame:gameCopy player:[gameCopy currentPlayerNumber]];
      }
    }
    else if (d<=1) {
      nextUtility = -[self relativeUtilityForGame:gameCopy player:[gameCopy currentPlayerNumber]];
    }
    else {
      // continue down the tree, swapping alpha and beta and negating utility since players are switched
      nextMove = [self alphaBetaMoveForGame:gameCopy
                                      depth:d-1
                                      alpha:-beta
                                        beta:-alpha
                              candidateMoves:nil
                          positionsEvaluated:numEvaluated
                                    utility:&nextUtility];
      nextUtility = -nextUtility; // negate since we just calculated from opponent's persepctive
      
    }
    
    if (nextUtility>=beta) {
      nextUtility = beta;
    }
    if (bestMove==nil || nextUtility>alpha) {
      bestMove = move;
    }
    if (nextUtility>alpha) alpha=nextUtility;

    if (numEvaluated) ++(*numEvaluated);
    [pool release];
  }
  [gameCopy release];
  *utility = alpha;
  if (alpha>=beta) {
    //NSLog(@"Exceeded beta at depth %d", d);
  }
  return bestMove;
}
  

-(int)searchDepthForGame:(Game *)game {
  return depth;
}

-(int)relativeUtilityForGame:(Game *)game player:(int)pnum {
  return ([game scoreForPlayer:pnum] -
          [game scoreForPlayer:[game nextPlayerNumber]]);
}

-(NSArray *)movesToConsiderForGame:(Game *)game {
  return [game allValidMoveSequences];
}

-(NSEnumerator *)enumeratorForMovesToConsiderForGame:(Game *)game {
  return [[[self movesToConsiderForGame:game] arrayWithObjectsInRandomOrder_] objectEnumerator];
}

+(double)normalizedRatioOf:(double)u1 to:(double)u2 maxRatio:(double)maxr {
  // Look at the ratio of my vs. opponent's utility. This will encourage exchanges when we're ahead and
  // avoid them when we're behind.
  double logratio = 0.0;
  if (u1<=0) return -1;
  if (u2<=0) return +1;
  else {
    logratio = log(u1/u2);
    if (logratio<-maxr) return -1;
    if (logratio>maxr) return +1;
  }
  return logratio/maxr;
}

////////////////////////////////// thread support //////////////////////////////

-(int)threadsToUse {
  if ([self useThreads]) {
    int nthreads = [[NSUserDefaults standardUserDefaults] integerForKey:@"CPUPlayerThreads"];
    if (nthreads<1) {
      // use MPProcessors() on Mac OS X, default to 1 on GNUstep until I find a portable way
#ifdef GNUSTEP
      nthreads = 1;
#else
      nthreads = MPProcessors();
#endif
    }
    return nthreads;
  }
  else return 1;
}

-(NSDictionary *)_bestMoveInfoForGame:(Game *)game
                       candidateMoves:(NSArray *)moves
                      spawningThreads:(int)nthreads {
  NSTimeInterval t1 = [NSDate timeIntervalSinceReferenceDate];
  NSTimeInterval t2;
  // each worker thread gets a lock whose condition it sets to 1 when it finishes
  NSMutableArray *locks = [NSMutableArray array];
  NSMutableArray *randomMoves = [[[moves arrayWithObjectsInRandomOrder_] mutableCopy] autorelease];
  int nmoves = [moves count];
  int i;
  if (nthreads>nmoves) nthreads = nmoves;
  for(i=0; i<nthreads; i++) {
    [locks addObject:[[[NSConditionLock alloc] initWithCondition:0] autorelease]];
  }
  // dispatch to threads, they'll pull moves from the randomMoves array using ArrayConsumerEnumerator
  [[self bestThreadMoves] removeAllObjects];
  for(i=0; i<nthreads; i++) {
    // each thread gets the game, the moves to evaluate, and the lock to update when it's finished
    NSArray *args = [NSArray arrayWithObjects:game, randomMoves, [locks objectAtIndex:i], nil];
    [NSThread detachNewThreadSelector:@selector(_bestMoveThreadEntry:)
                             toTarget:self
                           withObject:args];
  }
  // wait until all threads are done and have set their condition locks
  for(i=0; i<nthreads; i++) {
    [[locks objectAtIndex:i] lockWhenCondition:1];
    //NSLog(@"Got lock for thread %d", i);
  }
  // now find the best move in bestThreadMoves and assemble return info
  {
    NSDictionary *bestThreadMove = nil;
    NSMutableDictionary *bestMoveInfo;
    int totalEvaluated = 0;
    int bestUtility = 0;
    for(i=0; i<[[self bestThreadMoves] count]; i++) {
      NSDictionary *threadMove = [[self bestThreadMoves] objectAtIndex:i];
      totalEvaluated += [[threadMove objectForKey:@"positionsEvaluated"] intValue];
      if (bestThreadMove==nil || bestUtility<[[threadMove objectForKey:@"utility"] intValue]) {
        bestThreadMove = threadMove;
        bestUtility = [[threadMove objectForKey:@"utility"] intValue];
      }
    }
    bestMoveInfo = [[bestThreadMove mutableCopy] autorelease];
    [bestMoveInfo setObject:[NSNumber numberWithInt:totalEvaluated] forKey:@"positionsEvaluated"];
    t2 = [NSDate timeIntervalSinceReferenceDate];
    [bestMoveInfo setObject:[NSNumber numberWithDouble:t2-t1] forKey:@"time"];
    
    return bestMoveInfo;
  }
}


// these two methods execute in spawned threads
-(void)_recordBestMoveFoundInThread:(id)moveInfo {
  [[self threadLock] lock];
  [[self bestThreadMoves] addObject:moveInfo];
  [[self threadLock] unlock];
}

-(void)_bestMoveThreadEntry:(NSArray *)args {
  NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];
  
  Game *game = [args objectAtIndex:0];
  NSMutableArray *moves = [args objectAtIndex:1];
  NSConditionLock *lock = [args objectAtIndex:2];
  NSMutableDictionary *moveInfo = [NSMutableDictionary dictionary];
  NSArray *bestMove = nil;
  int positionsEvaluated=0, utility;
  int d = [self searchDepthForGame:game];

  if (DEBUG) {
    NSLog(@"Starting computation in thread:%@", [NSThread currentThread]);
  }
  // the ArrayConsumerEnumerator will pull moves off the array, in cooperation with other threads
  bestMove = [self alphaBetaMoveForGame:game
                                  depth:d
                                  alpha:LOSE_UTILITY-d
                                   beta:WIN_UTILITY+d
                         candidateMoves:[ArrayConsumerEnumerator enumeratorWithSourceArray:moves lock:[self threadLock]]
                     positionsEvaluated:&positionsEvaluated
                                utility:&utility];
  
  if (positionsEvaluated>0) {
    if (bestMove==nil) bestMove = [NSArray array];
    
    [moveInfo setObject:bestMove forKey:@"move"];
    [moveInfo setObject:[NSNumber numberWithInt:positionsEvaluated] forKey:@"positionsEvaluated"];
    [moveInfo setObject:[NSNumber numberWithInt:utility] forKey:@"utility"];
    
    [self _recordBestMoveFoundInThread:moveInfo];
    if (DEBUG) {
      NSLog(@"Finished processing in thread:%@", [NSThread currentThread]);
    }
  }
  else {
    if (DEBUG) NSLog(@"No moves available to process in thread:%@", [NSThread currentThread]);
  }
  [lock unlockWithCondition:1];
  [pool release];
}

//////////////////////////////// end thread support /////////////////////////////

-(NSDictionary *)bestMoveInfoForGame:(Game *)game {
  int nthreads = [self threadsToUse];
  NSDictionary *moveInfo;

  if (nthreads<=1) {
    NSTimeInterval t1 = [NSDate timeIntervalSinceReferenceDate];
    NSTimeInterval t2;
    int positionsEvaluated=0;
    NSMutableDictionary *detailInfo = [NSMutableDictionary dictionary];
    NSArray *bestMove = nil;
    int d = [self searchDepthForGame:game];
    int utility;

    bestMove = [self alphaBetaMoveForGame:game
                                    depth:d
                                    alpha:LOSE_UTILITY-d
                                     beta:WIN_UTILITY+d
                           candidateMoves:nil
                       positionsEvaluated:&positionsEvaluated
                                  utility:&utility];
    
    if (bestMove==nil) bestMove = [NSArray array];
    [detailInfo setObject:bestMove forKey:@"move"];
    [detailInfo setObject:[NSNumber numberWithInt:positionsEvaluated] forKey:@"positionsEvaluated"];
    [detailInfo setObject:[NSNumber numberWithInt:utility] forKey:@"utility"];
    t2 = [NSDate timeIntervalSinceReferenceDate];
    [detailInfo setObject:[NSNumber numberWithDouble:t2-t1] forKey:@"time"];
    moveInfo = detailInfo;
  }
  else {
    NSArray *candidateMoves = [self movesToConsiderForGame:game];
    moveInfo = [self _bestMoveInfoForGame:game
                           candidateMoves:candidateMoves
                          spawningThreads:nthreads];
  }
  
  if (DEBUG) {
    NSLog(@"AI done, time=%@ sec, utility=%@", [moveInfo objectForKey:@"time"], [moveInfo objectForKey:@"utility"]);
  }
  return moveInfo;
}

-(void)computeBestMoveForGame:(Game *)game {
  Game *gamecopy = [[game copy] autorelease];
  NSMutableDictionary *moveInfo = [[self bestMoveInfoForGame:gamecopy] mutableCopy];
  [moveInfo setObject:game forKey:@"game"];
  //NSLog(@"Computed best move:%@ in thread:%@", move, [NSThread currentThread]);
  [[NSNotificationCenter defaultCenter] postNotificationName:@"AIComputedBestMoveNotification"
                                                      object:self
                                                    userInfo:moveInfo];
}

@end