/* 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.
*/

/* There is no "BreakthroughGame" class because the rules can be handled by HexapawnGame */

#import "BreakthroughAI.h"
#import "DCHypergridPosition.h"

@implementation BreakthroughAI

-(int)rowIncrementForPlayer:(int)pnum {
  return (pnum==1) ? 1 : -1;
}

-(int)piecesSupportingPostion:(id)pos forPlayer:(int)pnum inGame:(Game *)game {
  // look behind left and right
  int count=0;
  int dr = [self rowIncrementForPlayer:pnum];
  int r = [pos row]-dr;
  if (r>=0 && r<[game numberOfRows]) {
    int c1= [pos column]+1;
    int c2= [pos column]-1;
    if (c1>=0 && c1<[game numberOfColumns] && [game valueAtRow:r column:c1]==pnum) count++;
    if (c2>=0 && c2<[game numberOfColumns] && [game valueAtRow:r column:c2]==pnum) count++;
  }
  return count;
}

/** Returns the number of opposing pieces in the "light cone" of the given position; that is,
pieces which fall within a 45 degree angle (column difference<=row difference). Any pieces
outside this cone cannot affect the piece at the given position.
*/
-(int)numberOfOpposingPiecesRelevantToPosition:(id)pos forPlayer:(int)pnum inGame:(Game *)game {
  int count = 0;
  int oppval = [game playerNumberMovingAfterPlayer:pnum];
  int dr = [self rowIncrementForPlayer:pnum];
  int r,c;
  int maxr = [game numberOfRows];
  int maxc = [game numberOfColumns];
  int maxoffc = 0;
  for(r=[pos row]+dr; r>=0 && r<maxr; r+=dr) {
    ++maxoffc;
    for(c=[pos column]-maxoffc; c<=[pos column]+maxoffc; c++) {
      if (c>=0 && c<maxc && oppval==[game valueAtRow:r column:c]) {
        ++count;
      }
    }
  }
  return count;
}

-(float)positionalBonusForPosition:(id)pos forPlayer:(int)pnum inGame:(Game *)game {
  //static float bonuses[] = {3, 2.75, 2.5, 2.25, 1.75, 1.5, 1.25, 1, 0.75, 0.5, 0.25};
  //static int bonuscount = 10;
  //static int sidelimit = 4;
  static float bonuses[] = {3, 2.5, 2, 1.5, 1, 0.75, 0.5, 0.25};
  static int bonuscount = 8;
  //static int sidelimit = 2;
  
  int relativeRow = (pnum==1) ? [pos row] : [game numberOfRows]-1-[pos row];
  if (relativeRow>3) {
    int oppval = [game playerNumberMovingAfterPlayer:pnum];
    int dr = [self rowIncrementForPlayer:pnum];
    int r,c;
    int maxr = [game numberOfRows];
    int maxc = [game numberOfColumns];
    int maxoffc = 0;
    
    int count = 0; // 2 points for same column, 1 for diagonal, 2 otherwise
    //int leftCount = 0;
    //int rightCount = 0;
    
    for(r=[pos row]+dr; r>=0 && r<maxr; r+=dr) {
      ++maxoffc;
      for(c=[pos column]-maxoffc; c<=[pos column]+maxoffc; c++) {
        if (c>=0 && c<maxc && oppval==[game valueAtRow:r column:c]) {
          int defvalue = 2;
          if (c==[pos column]-maxoffc || c==[pos column]+maxoffc) defvalue=1;
          count += defvalue;
          /* // counting blockers on each side appears to not help and may actually hurt
             // (65.8% vs 62.3% wins against original AI)
          if (c>=[pos column]) rightCount += defvalue;
          if (c<=[pos column]) leftCount  += defvalue;
          */
          // optimization since no side counts
          if (count>=bonuscount) return 0;
        }
      }
    }
    /*
    // penalize for not having 3 points left or right (disabled, see above)
    if (leftCount<=sidelimit  && [pos column]>0)  count-=1;
    if (rightCount<=sidelimit && [pos column]<[game numberOfColumns]-1) count-=1;
    if (count<0) count=0;
     */
    
    if (count>=bonuscount) return 0;
    else return bonuses[count];
  }
  else return 0;
}

-(int)playerControllingPosition:(id)pos inGame:(Game *)game {
  // check each of the four cells that can capture this position
  int p1threats = [self piecesSupportingPostion:pos forPlayer:1 inGame:game];
  int p2threats = [self piecesSupportingPostion:pos forPlayer:2 inGame:game];
  // if threats are equal, it's controlled by whoever has a piece there
  if (p1threats>p2threats) return 1;
  else if (p2threats>p1threats) return 2;
  else return [game valueAtPosition:pos];
}

-(float)controlFactorForPosition:(id)pos forPlayer:(int)pnum inGame:(Game *)game {
  int oppnum = [game playerNumberMovingAfterPlayer:pnum];
  float control = 0;
  int value = [game valueAtPosition:pos];
  //int relativeRow = (pnum==1) ? [pos row] : [game numberOfRows]-1-[pos row];
  
  
  if (value==pnum) control++;
  else if (value==oppnum) control--;
  control += [self piecesSupportingPostion:pos forPlayer:pnum inGame:game];
  control -= [self piecesSupportingPostion:pos forPlayer:oppnum inGame:game];

  // "tie" on an occupied cell goes to the current player
  if (value!=0 && control==0)  {
    control = ([game currentPlayerNumber]==pnum) ? 1 : -1;
  }
  if (control>1) control=1;
  if (control<-1) control = -1;

  control *= (1+[self positionalBonusForPosition:pos forPlayer:pnum inGame:game]);

  return control;
  /*
  if (control>0 && relativeRow>3) {
    int p = [self numberOfOpposingPiecesRelevantToPosition:pos forPlayer:pnum inGame:game];
    if (p==0) control*=3.0;
    else if (p==1) control*=2.0;
    else if (p==2) control*=1.5;
*/
    // assign bonus for neighboring cells
    // actually it looks like this causes gaps
    /*
    if (relativeRow>4)
    {
      int neighbors = 0;
      NSEnumerator *ne = [[[game grid] neighborsOfPosition:pos distance:1] objectEnumerator];
      id npos;
      while (npos=[ne nextObject]) {
        if ([game valueAtPosition:npos]==pnum) neighbors++;
      }
      control *= 1+(0.05*neighbors);
    }
  }

     */
}

-(NSArray *)_emptyCellsToCheckFromPosition:(id)pos forPlayer:(int)pnum inGame:(Game *)game {
  int dr = [self rowIncrementForPlayer:pnum];
  int c = [pos column];
  int r = [pos row];
  int maxc = [game numberOfColumns];
  int maxr = [game numberOfRows];
  NSMutableArray *array = [NSMutableArray array];
  // check (r+dr,c-1),(r+dr,c),(r+dr,c+1)
  if (r+dr>=0 && r+dr<maxr) {
    if (c>0) [array addObject:[DCHypergridPosition positionWithRow:r+dr column:c-1]];
    [array addObject:[DCHypergridPosition positionWithRow:r+dr column:c]];
    if (c<maxc-1) [array addObject:[DCHypergridPosition positionWithRow:r+dr column:c+1]];
  }
  return array;
}

-(int)_threatWeightForGame:(Game *)game player:(int)pnum {
  static int oppturnweights[] = {3,1,2,4,8,16, 99999,9999999};
  static int myturnweights[]  = {3,1,2,4,8,16,999999,9999999};
  //static int weights[] = {1,1,2,3,4,8,99999,999999};
  static int weights[] = {3,1,2,4,8,16,99999,999999};

  float utility = 0;
  //int *weights = ([game currentPlayerNumber]==pnum) ? myturnweights : oppturnweights;
  int cpnum = [game currentPlayerNumber];
  NSEnumerator *pe = [[game grid] enumeratorForPositionsWithValue:pnum];
  id pos;
  //NSMutableSet *emptyCellThreats = [NSMutableSet set];

  while (pos=[pe nextObject]) {
    // row numbers are inverted for player 2
    int index = (pnum==1) ? [pos row] : [game numberOfRows]-1-[pos row];
    int weight = (useAltWeights) ? index[(cpnum==pnum) ? myturnweights : oppturnweights] : weights[index];
    float control = [self controlFactorForPosition:pos forPlayer:pnum inGame:game];
    if (control>0) {
      //[emptyCellThreats addObjectsFromArray:[self _emptyCellsToCheckFromPosition:pos forPlayer:pnum inGame:game]];
      utility += weight*control;
      utility += pieceWeight;
    }
    // any credit for pieces that are outnumbered?
  }
/* // this doesn't seem to help
  if (emptyMultiplier>0) {
    pe = [emptyCellThreats objectEnumerator];
    while (pos=[pe nextObject]) {
      int index = (pnum==1) ? [pos row] : [game numberOfRows]-1-[pos row];
      int weight = index[(cpnum==pnum) ? myturnweights : oppturnweights];
      int control = [self controlFactorForPosition:pos forPlayer:pnum inGame:game];
      if (control>0) {
        utility += weight*control*emptyMultiplier;
      }
    }
  }
*/
  return (int)utility;
}

-(int)relativeUtilityForGame:(Game *)game player:(int)pnum {
  return [self _threatWeightForGame:game player:pnum] -
  [self _threatWeightForGame:game player:[game playerNumberMovingAfterPlayer:pnum]];
}

// for some reason, a depth of 2 is actually worse than 1.
// not in this class, but it takes way too long to do 3-2-1 evaluation
-(int)searchDepthForLevel:(int)d {
  if (use311) return (d%2==0) ? d-1 : d;
  else return d;
}


-(NSArray *)movesToConsiderForGame:(Game *)game {
  // if we can win, win
  // otherwise stop opponent if he's about to win
  int pnum = [game currentPlayerNumber];
  int oppnum = [game nextPlayerNumber];
  int dr = [self rowIncrementForPlayer:pnum];
  
  int lastrow = (pnum==1) ? [game numberOfRows]-1 : 0;
  int nextlastrow = lastrow - dr;

  int firstrow = (pnum==1) ? 0 : [game numberOfRows]-1;
  int secondrow = firstrow+dr;
  
  int maxc = [game numberOfColumns];
  int c;
  NSMutableArray *blockmoves = nil;
  // scan our next to last row for win
  for(c=0; c<maxc; c++) {
    if ([game valueAtRow:nextlastrow column:c]==pnum) {
      // we win, move left (or right if c=0)
      int cwin = (c==0) ? c+1 : c-1;
      id move = [NSArray arrayWithObjects:[DCHypergridPosition positionWithRow:nextlastrow column:c],
                                          [DCHypergridPosition positionWithRow:lastrow column:cwin],
                                          nil];
      return [move arrayWithSelf_];
    }
  }
  // scan our second row to prevent opponent win
  for(c=0; c<maxc; c++) {
    if ([game valueAtRow:secondrow column:c]==oppnum) {
      // look for blocking moves, left and right
      if (c>0 && [game valueAtRow:firstrow column:c-1]==pnum) {
        id move = [NSArray arrayWithObjects:[DCHypergridPosition positionWithRow:firstrow column:c-1],
                                            [DCHypergridPosition positionWithRow:secondrow column:c],
                                            nil];
        if (!blockmoves) blockmoves = [NSMutableArray array];
        [blockmoves addObject:move];
      }
      if (c<maxc-1 && [game valueAtRow:firstrow column:c+1]==pnum) {
        id move = [NSArray arrayWithObjects:[DCHypergridPosition positionWithRow:firstrow column:c+1],
                                            [DCHypergridPosition positionWithRow:secondrow column:c],
                                            nil];
        if (!blockmoves) blockmoves = [NSMutableArray array];
        [blockmoves addObject:move];
      }
    }
  }
  if (blockmoves) return blockmoves;
  else {
    // return all possible moves
    return [game allValidMoveSequences];
  }
}

@end