/***
 * Hex-7
 *  Version 2.0
 * www.mazeworks.com
 *
 *  Copyright (c) 2002 David Herzog
 *  All Rights Reserved.
 */


package com.bdaum.Hex.game;

import org.eclipse.swt.graphics.Point;

/******** AI ********
   generates computer moves
*/   
public final class AI {
   static final int PLAYER_WIN=-999999, COMPUTER_WIN=999999 ;
   static final byte hexes[][] = {
         // cols 0 and 1 hold all hexes from center outward
         // cols 2 and 3 hold 2nd-ply response move 
         // inner diamond
         {3,3,0,0},{2,2,3,4},{4,4,3,2},{3,2,3,3},{4,3,4,4},
         {2,3,2,2},{3,4,3,3},{4,2,3,3},{2,4,3,3},
         // middle ring
         {1,1,2,3},{5,5,4,3},{2,1,3,3},{5,4,5,5},{1,2,1,1},{4,5,3,3},
         {3,1,3,2},{5,3,4,2},{1,3,2,4},{3,5,3,4},{4,1,4,2},
         {5,2,3,3},{1,4,3,3},{2,5,2,4},{5,1,5,5},{1,5,1,1},
         // outer ring
         {0,0,1,2},{6,6,5,4},{1,0,3,3},{6,5,3,3},{0,1,3,3},{5,6,3,3},
         {2,0,3,3},{6,4,5,5},{0,2,1,1},{4,6,3,3},{3,0,3,3},{6,3,3,3},
         {0,3,3,3},{3,6,3,3},{4,0,3,3},{6,2,3,3},{0,4,3,3},{2,6,3,3},
         {5,0,3,3},{6,1,3,3},{0,5,3,3},{1,6,3,3},{6,0,3,3},{0,6,3,3} } ;
   private int ply, maxDepth ;
   private BestMove best ;
   private Point move ;
   private Board bd ;
   private StaticEval stat ;
   private Game game ;

   // constructor
   public AI(Board bd,StaticEval stat,Game game) {
      this.bd = bd ;
      this.stat = stat ;
      this.game = game ;
   }
   // main routine
   public void makeMove() { 
      ply = game.getPly() ; move = null ;
      if (ply<=2) move = openingMove() ;
      if (move==null) {
         // set search depth (ply)
         if (game.getLevel()==Game.LEVEL1) maxDepth = 4 ; 
         else maxDepth = 6 ;
         // search game tree
         best = abSearch(Game.COMPUTER,PLAYER_WIN,COMPUTER_WIN,0) ;
         move = best.getMove() ;
      }
      // if somehow there's still no move, make a random one
      if (move==null) move = randomMove() ;
      bd.computerMove(move,game.getColor(Game.COMPUTER)) ;
   }
   // returns random integer from 0 to n-1 inclusive
   private int randomInt(int n) { return (int)(n*Math.random()) ; }

   private Point randomMove() {
      int x, y ;

      while (true) {
         if (bd.isEmpty(x=randomInt(Game.SIZE),y=randomInt(Game.SIZE))) break ;
      }
      return new Point(x,y) ;
   }
   private Point openingMove() {
      if ((ply==2)&&(game.getLevel()==Game.LEVEL2)) {
         // search hexes array for response
         for (int i=0; i<hexes.length; i++)
            if (!bd.isEmpty(hexes[i][0],hexes[i][1]))
               return new Point(hexes[i][2],hexes[i][3]) ;         
      }
      // first move is always on inner diamond (except the center!) or 
      // the 2 hexes on main diagonal from middle ring (1-1 and 5-5)
      else if (ply==1) {
         int i = randomInt(10) + 1 ;
         return new Point(hexes[i][0],hexes[i][1]) ;
      }
      return null ;
   }
   // move generator
   private byte[] moveGen(int depth,int color) {
      // uses 3 main arrays:
      //    "list1" contains all possible moves for white & black, 
      //       with values from shallow search
      //    "list2" contains n-best moves, with values
      //    "ml" is final movelist: byte array with n-best moves only

      int temp[]=new int[3], moveListLength=0, list1ptr=0, list2ptr=0,
          list1[][]=new int[100][3], list2[][] ; 
      byte ml[] ;

      // generate list1
      for (int i=0; i<list1.length; i++ ) list1[i][2] = -999999 ;
      for (int i=0; i<hexes.length; i++) {
         // first get value of move for current color
         if (bd.setHex(hexes[i][0],hexes[i][1],color)) {
            list1[list1ptr][0] = hexes[i][0] ;
            list1[list1ptr][1] = hexes[i][1] ;
            list1[list1ptr][2] = stat.eval(color) ;
            bd.setEmpty(hexes[i][0],hexes[i][1]) ;

            if ((depth==0)&&(list1[list1ptr][2]==StaticEval.WIN_VALUE)) {
               // found winning move
               // return it alone NOW
               ml = new byte[1] ;
               ml[0] = (byte)( (list1[list1ptr][0]*10) + list1[list1ptr][1] ) ;
               return ml ;
            }
            else list1ptr++ ;
            // get value of Black move
            bd.setHex(hexes[i][0],hexes[i][1],game.getOtherColor(color)) ;
            list1[list1ptr][0] = hexes[i][0] ;
            list1[list1ptr][1] = hexes[i][1] ;
            list1[list1ptr++][2] = stat.eval(game.getOtherColor(color)) ;
            bd.setEmpty(hexes[i][0],hexes[i][1]) ;
         }
      }
      // set movelist max size
      if (game.getLevel()==Game.LEVEL1) moveListLength = 16 ;
      else {
         // at Advanced level, n-best is tapered
         if (depth<2) moveListLength = 16 ;
         else moveListLength = 14 ;
      }
      // initialize list2
      list2 = new int[moveListLength][3] ;
      // Shellsort list1 by value
      for (int h=list1.length/2; h>0; h/=2) {
         for (int i=h; i<list1.length; i++) {
            for (int k=0; k<3; k++) temp[k] = list1[i][k] ; 
            int j = i ;
            for ( ; j>=h && temp[2]>list1[j-h][2] ; j-=h)
               for (int k=0; k<3; k++) list1[j][k] = list1[j-h][k] ;

            for (int k=0; k<3; k++) list1[j][k] = temp[k] ;
         }
      }
      // copy top entries to list2
      // if duplicate move, add value of both entries
      list1ptr = list2ptr = 0 ;

      outer:
      while (list2ptr<moveListLength) {
         // quit if no more possible moves listed
         if (list1[list1ptr][2]==-999999) break ;
         for (int i=0; i<list2ptr; i++) {
            if ( (list1[list1ptr][0]==list2[i][0])&&
                 (list1[list1ptr][1]==list2[i][1]) ) {
               // duplicate found
               list2[i][2] += list1[list1ptr++][2] ;
               continue outer ;
            }
         }
         // copy entry to list2
         list2[list2ptr][0] = list1[list1ptr][0] ;
         list2[list2ptr][1] = list1[list1ptr][1] ;
         list2[list2ptr++][2] = list1[list1ptr++][2] ;
      }
      // now we know how big to make ml
      ml = new byte[list2ptr] ;
      // sort list2 by value
      for (int h=list2.length/2; h>0; h/=2) {
         for (int i=h; i<list2.length; i++) {
            for (int k=0; k<3; k++) temp[k] = list2[i][k] ; 
            int j = i ;
            for ( ; j>=h && temp[2]>list2[j-h][2] ; j-=h)
               for (int k=0; k<3; k++) list2[j][k] = list2[j-h][k] ;

            for (int k=0; k<3; k++) list2[j][k] = temp[k] ;
         }
      }
      // copy list2 to ml: 1-D byte array, and return
      for (int i=0; i<ml.length; i++) 
         ml[i] = (byte)( (list2[i][0]*10) + list2[i][1] ) ;
      return ml ;
   } 
   // negamax game tree search, with alpha-beta
   private BestMove abSearch(int side,int alpha,int beta,int depth) {
      int otherSide, baseCase, value, x, y ;
      int color = game.getColor(side) ;
      BestMove reply ;
      Point saveMove=null ;
      
      // base to end recursion
      baseCase = stat.eval(game.getColor(Game.COMPUTER)) ;
      if ((depth==maxDepth)||(baseCase==-100000)||(baseCase==100000)) 
         return new BestMove(baseCase) ;
      // cutoff for valuable computer move
      if ((depth==maxDepth-1)&&(baseCase>100)) 
         return new BestMove(baseCase) ;
      
      // set initial values
      if (side==Game.COMPUTER) { otherSide = Game.PLAYER ; value = alpha ; }
      else { otherSide = Game.COMPUTER ; value = beta ; }
      // loop through move list
      byte ml[] = moveGen(depth,color) ;
      for (int i=0; i<ml.length; i++) {
         x = (int)(ml[i]/10) ; y = ml[i] % 10 ;
         if (bd.setHex(x,y,color)) {
            reply = abSearch(otherSide,alpha,beta,depth+1) ;
            bd.setEmpty(x,y) ;
         
            if ( ((side==Game.COMPUTER)&&(reply.getValue()>value))||
                 ((side==Game.PLAYER)&&(reply.getValue()<value)) ) {
               // save better move 
               if (side==Game.COMPUTER) alpha = value = reply.getValue() ;
               else beta = value = reply.getValue() ;
               saveMove = new Point(x,y) ;
               // refutation
               if (alpha >= beta) break ;
            }
         }
      }
      return new BestMove(value,saveMove) ;
   }
}