staticeval.java

Wrox.Professional.Eclipse.3.for.Java.Developers

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

/******** STATIC EVAL ********
   static evaluator function - produces an integer value for
   any given board position for either side
*/   
public final class StaticEval {
   static final int WIN_VALUE=100000,
                    SW=1, SE=2, E=3, NE=4, NW=5, W=6, 
                    SW_B=7, S_B=8, SE_B=9, NE_B=10, N_B=11, NW_B=12 ;
   // board areas
   static final int[][] WhiteAreas = { {3,4,4,4,4,4,3},
                                       {3,2,2,2,2,2,3},
                                       {3,2,1,1,1,2,3},
                                       {3,2,1,0,1,2,3},
                                       {3,2,1,1,1,2,3},
                                       {3,2,2,2,2,2,3},
                                       {3,4,4,4,4,4,3} },
                        BlackAreas = { {3,3,3,3,3,3,3},
                                       {4,2,2,2,2,2,4},
                                       {4,2,1,1,1,2,4},
                                       {4,2,1,0,1,2,4},
                                       {4,2,1,1,1,2,4},
                                       {4,2,2,2,2,2,4},
                                       {3,3,3,3,3,3,3} } ;
   private boolean isFullChainWhite, isFullChainBlack ;
   private int stack[]=new int[25], stackPtr=0 ;
   // weights 
   private int A0x, A1x, A2x, A3x, A4x, B1x, B2x, L0x, L1x, E1x, E2x, C1x, C2x, C4x, C5x, 
               chainBaseX, chainPctX ;
   // parametric function values
   private int wA0, wA1, wA2, wA3, wA4, bA0, bA1, bA2, bA3, bA4,
               w2Bridge, b2Bridge, w1Bridge, b1Bridge, w1Link, b1Link, w0Link, b0Link,
               w2Edge, w1Edge, b2Edge, b1Edge,
               wChainLink, wChainBridge, wLinkPct, bChainLink, bChainBridge, bLinkPct,
               w5Chain, w4Chain, w2Chain, w1Chain, b5Chain, b4Chain, b2Chain, b1Chain,
               wVal, bVal ;
   private Board bd ;
   private Game game ;

   // constructor
   public StaticEval(Board bd,Game game) { 
      this.bd = bd; 
      this.game = game ;
   }
   // initializes weights and function values
   private void initValues() {
      A0x = 8 ; A1x = 4 ; A2x = 2 ; A3x = 1 ; A4x = 0 ;
      B2x = 8 ; B1x = 4 ; L1x = 3 ; L0x = 0 ; E2x = 4 ; E1x = 2 ;
      C5x = 500 ; C4x = 240 ; C2x = 175 ; C1x = 110 ;

      chainBaseX = 1000 ; chainPctX = 90 ;
      isFullChainWhite = isFullChainBlack = false ;
      wLinkPct = bLinkPct = 0 ;

      wA0 = wA1 = wA2 = wA3 = wA4 = 0 ; 
      bA0 = bA1 = bA2 = bA3 = bA4 = 0 ; 
      w2Bridge = b2Bridge = w1Bridge = b1Bridge = 0 ;
      w1Link = b1Link = w0Link = b0Link = 0 ;
      w2Edge = b2Edge = w1Edge = b1Edge = 0 ;
      wChainLink = wChainBridge = 0 ;
      bChainLink = bChainBridge = 0 ;
      w5Chain = w4Chain = w2Chain = w1Chain = 0 ;
      b5Chain = b4Chain = b2Chain = b1Chain = 0 ;
   }
   // main evaluation method
   int eval(int evalColor) { 

      // first see if it's all over
      if (bd.isWin(evalColor)) return WIN_VALUE ;
      else if (bd.isWin(game.getOtherColor(evalColor))) return -WIN_VALUE ;
      // no win, start eval
      initValues() ;
      // calculate value of chains
      calcChains() ;
      // calculate value for each hex
      calcHex() ;
      // now add everything up
      wVal = (A0x*wA0)+(A1x*wA1)+(A2x*wA2)+(A3x*wA3)+(A4x*wA4) ;
      wVal += (B2x*w2Bridge)+(B1x*w1Bridge)+(L1x*w1Link)+(L0x*w0Link)+
              (E2x*w2Edge)+(E1x*w1Edge) ;
      wVal += (C5x*w5Chain)+(C4x*w4Chain)+(C2x*w2Chain)+(C1x*w1Chain) ;
      if (isFullChainWhite) wVal += chainBaseX + (chainPctX * wLinkPct) ; 

      bVal = (A0x*bA0)+(A1x*bA1)+(A2x*bA2)+(A3x*bA3)+(A4x*bA4) ;
      bVal += (B2x*b2Bridge)+(B1x*b1Bridge)+(L1x*b1Link)+(L0x*b0Link)+
              (E2x*b2Edge)+(E1x*b1Edge) ;
      bVal += (C5x*b5Chain)+(C4x*b4Chain)+(C2x*b2Chain)+(C1x*b1Chain) ;
      if (isFullChainBlack) bVal += chainBaseX + (chainPctX * bLinkPct) ; 
      // and send it back, negamax-style
      return (evalColor==Game.WHITE)? 
         (int)(wVal - bVal) : (int)(bVal - wVal) ;
   }
   // look for chains
   private void calcChains() {

      bd.clearVisited() ;
      // White
      for (int j=0; j<4; j++) {
         for (int i=0; i<Game.SIZE; i++) {
         
            if ((bd.isWhite(i,j))&&(!bd.isVisited(i,j))) {
               stackPtr = wChainLink = wChainBridge = 0 ;
               // first check for valid start
               if (isOpen(i,j,NE)) {
                  bd.setVisited(i,j,true) ;
                  switch (searchChainWhite(i,j)) {
                     // full chain
                     case 8: if (j==0) wChainLink++ ;
                             else wChainBridge++ ;
                             wLinkPct = (int)( 100*(((float)wChainLink/(wChainLink + wChainBridge))) ) ;
                             isFullChainWhite = true ;
                             return ;
                     case 5: w5Chain++ ; break ;
                     case 4: w4Chain++ ; break ;
                     case 2: w2Chain++ ; break ;
                     case 1: if ( ((i==4)||(i==5))&&(j==3)&&(bd.isWhite(4,4)) ) 
                                w1Chain++ ;
                             else if ( (i==2)&&(j==2)&&((bd.isWhite(2,3))||(bd.isWhite(1,3))) ) 
                                w1Chain++ ;
                  }
               }
            }
         }
      }
      // Black
      for (int i=0; i<4; i++) {
         for (int j=0; j<Game.SIZE; j++) {
         
            if ((bd.isBlack(i,j))&&(!bd.isVisited(i,j))) {
               stackPtr = bChainLink = bChainBridge = 0 ;
               // first check for valid start
               if (isOpen(i,j,W)) {
                  bd.setVisited(i,j,true) ;
                  switch (searchChainBlack(i,j)) {
                     // full chain
                     case 8: if (i==0) bChainLink++ ;
                             else bChainBridge++ ;
                             bLinkPct = (int)( 100*(((float)bChainLink/(bChainLink + bChainBridge))) ) ;
                             isFullChainBlack = true ;
                             return ;
                     case 5: b5Chain++ ; break ;
                     case 4: b4Chain++ ; break ;
                     case 2: b2Chain++ ; break ;
                     case 1: if ( ((j==4)||(j==5))&&(i==3)&&(bd.isBlack(4,4)) ) 
                                b1Chain++ ;
                             else if ( (i==2)&&(j==2)&&((bd.isBlack(3,2))||(bd.isBlack(3,1))) ) 
                                b1Chain++ ;
                  }
               }
            }
         }
      }
   }
   // DFS for chains - returns "absolute" length of chain 
   //    (number of rows or columns it spans including edges)
   private int searchChainWhite(int x,int y) {
      int direction=0, currLength=0, maxLength=0, saveLength=0, localMaxLength=0 ;

      // initialize length counters
      if (y==0) currLength = maxLength = 1 ;
      else if (y==1) currLength = maxLength = 2 ;

      while (true) {
         // look for a link
         direction = bd.scanLinks(x,y,Game.WHITE) ;
         // nope, look for a bridge
         if (direction==0) direction = bd.scanBridges(x,y,Game.WHITE) ;
         if (direction!=0) {
            // found something - bump the counter
            if (direction>6) wChainBridge++ ;
            else wChainLink++ ;
            // make hex current
            stack[stackPtr++] = direction ;
            switch (direction) {
               case SW: y++ ; currLength++ ; break ;
               case SE: x++ ; y++ ; currLength++ ; break ;
               case E : x++ ; break ;
               case NE: y-- ; currLength-- ; break ;
               case NW: x-- ; y-- ; currLength-- ; break ;
               case W : x-- ; break ;
               case SW_B: x--  ; y++  ; currLength++ ; break ;
               case S_B : x++  ; y+=2 ; currLength+=2 ; break ;
               case SE_B: x+=2 ; y++  ; currLength++ ; break ;
               case NE_B: x++  ; y--  ; currLength-- ; break ;
               case N_B : x--  ; y-=2 ; currLength-=2 ; break ;
               case NW_B: x-=2 ; y--  ; currLength-- ; break ;
            }
            // check overall length
            if (currLength>maxLength) maxLength = currLength ;
            // check for local max if we're not moving forward
            else if (localMaxLength<maxLength)
               if ( (y>=3)&&(maxLength>0)&&(isOpen(x,y,SW)) ) localMaxLength = maxLength ;
            // check if we've reached the bottom
            if (y==(Game.SIZE-1)) { wChainLink++ ; return maxLength+1 ; }
            if (y==(Game.SIZE-2)) if (isOpen(x,y,SW)) { wChainBridge++ ; return maxLength+2 ; }
            // nope, look for next link/bridge
            bd.setVisited(x,y,true) ;
         }
         else {
            if (stackPtr==0)
               // all chains visited, return the longest we've found
               return (saveLength>localMaxLength)? saveLength : localMaxLength ;
            // at end of path, check chain and back up
            if (saveLength<currLength)
               if ( (y>=3)&&(currLength>0)&&(isOpen(x,y,SW)) ) saveLength = currLength ;
            direction = stack[--stackPtr] ;
            // decrement the counter
            if (direction>6) wChainBridge-- ;
            else wChainLink-- ;

            switch (direction) {
               case SW: y-- ; currLength-- ; maxLength-- ; break ;
               case SE: x-- ; y-- ; currLength-- ; maxLength-- ; break ;
               case E : x-- ; break ;
               case NE: y++ ; currLength++ ; break ;
               case NW: x++ ; y++ ; currLength++ ; break ;
               case W : x++ ; break ;
               case SW_B: x++  ; y--  ; currLength-- ; maxLength-- ; break ;
               case S_B : x--  ; y-=2 ; currLength-=2 ; maxLength-=2 ; break ;
               case SE_B: x-=2 ; y--  ; currLength-- ; maxLength-- ; break ;
               case NE_B: x--  ; y++  ; currLength++ ; break ;
               case N_B : x++  ; y+=2 ; currLength+=2 ; break ;
               case NW_B: x+=2 ; y++  ; currLength++ ; break ;
            }
         }
      }
   }
   private int searchChainBlack(int x,int y) {
      int direction=0, currLength=0, maxLength=0, saveLength=0, localMaxLength=0 ;

      // initialize length counters
      if (x==0) currLength = maxLength = 1 ;
      else if (x==1) currLength = maxLength = 2 ;

      while (true) {
         // look for a link
         direction = bd.scanLinks(x,y,Game.BLACK) ;
         // nope, look for a bridge
         if (direction==0) direction = bd.scanBridges(x,y,Game.BLACK) ;
         if (direction!=0) {
            // found something - bump the counter
            if (direction>6) bChainBridge++ ;
            else bChainLink++ ;
            // make hex current
            stack[stackPtr++] = direction ;
            switch (direction) {
               case SW: y++ ; break ;
               case SE: x++ ; y++ ; currLength++ ; break ;
               case E : x++ ; currLength++ ; break ;
               case NE: y-- ; break ;
               case NW: x-- ; y-- ; currLength-- ; break ;
               case W : x-- ; currLength-- ; break ;
               case SW_B: x--  ; y++  ; currLength-- ; break ;
               case S_B : x++  ; y+=2 ; currLength++ ; break ;
               case SE_B: x+=2 ; y++  ; currLength+=2 ; break ;
               case NE_B: x++  ; y--  ; currLength++ ; break ;
               case N_B : x--  ; y-=2 ; currLength-- ; break ;
               case NW_B: x-=2 ; y--  ; currLength-=2 ; break ;
            }
            // check overall length
            if (currLength>maxLength) maxLength = currLength ;
            // check for local max if we're not moving forward
            else if (localMaxLength<maxLength)
               if ( (x>=3)&&(maxLength>0)&&(isOpen(x,y,E)) ) localMaxLength = maxLength ;
            // check if we've reached the bottom
            if (x==(Game.SIZE-1)) { bChainLink++ ; return maxLength+1 ; }
            if (x==(Game.SIZE-2)) if (isOpen(x,y,E)) { bChainBridge++ ; return maxLength+2 ; }
            // nope, look for next link/bridge
            bd.setVisited(x,y,true) ;
         }
         else {
            if (stackPtr==0)
               // all chains visited, return the longest we've found
               return (saveLength>localMaxLength)? saveLength : localMaxLength ;
            // at end of path, check chain and back up
            if (saveLength<currLength)
               if ( (x>=3)&&(currLength>0)&&(isOpen(x,y,E)) ) saveLength = currLength ;
            direction = stack[--stackPtr] ;
            // decrement the counter
            if (direction>6) bChainBridge-- ;
            else bChainLink-- ;

            switch (direction) {
               case SW: y-- ; break ;
               case SE: x-- ; y-- ; currLength-- ; maxLength-- ; break ;
               case E : x-- ; currLength-- ; maxLength-- ; break ;
               case NE: y++ ; break ;
               case NW: x++ ; y++ ; currLength++ ; break ;
               case W : x++ ; currLength++ ; break ;