computerplayer.java

ParallelConnectFour是一个java小游戏

package edu.rit.cs.mlr5773.connectfour;

import java.util.*;

/**
 * A Computer Player that operates on 1 CPU and requires no thinker processes.
 *
 * @author Mark Roth
 */
public class ComputerPlayer extends Player {

  /** Random number generator to use when choosing between equal score moves */
  private Random random;

  /** A local copy of the board used for planning */
  private Board thinkBoard;

  /** The current maximum search depth */
  private int curMaxDepth = 1;

  /** Maximum possible search depth overall */
  private final int MAX_DEPTH = 12;

  /** Constants for Win, Tie, and Lose score values */
  private final int TIE = Integer.MIN_VALUE+2;
  private final int LOSE = Integer.MIN_VALUE+1;
  private final int WIN = Integer.MAX_VALUE-1;

  /** Reserved for tree pruning */
  private int alpha;
  private int beta;

  /**
   * Creates a new Computer Player
   *
   * @param game The actual game board to make moves on
   * @param player The player number
   * @param maxDepth The number of moves to think ahead
   */
  public ComputerPlayer( ConnectFourGame game, int player, int maxDepth ) {
    super( game, player );
    random = new Random();
    curMaxDepth = maxDepth;
  }

  /**
   * Analyze the board, and determine how many 2-in-a-rows there are, with
   * the possible expansion to 4-in-a-rows.
   */
  private int checkDoubles() {
    int score = 0;
    int x, y, i;
    int him = (player==1) ? 2 : 1;
    int nhim, nme, nblank;

    // Check horizontals:
    for( y = 0; y < 6; y++ ) {
      nhim = 0;  nme = 0;  nblank = 0;
	for( x = 0; x < 7; x++ ) {
  	  int piece = thinkBoard.getAt( x, y );
	  if( piece == 0 ) nblank++;
	  else if( piece == player ) nme++;
	  else nhim++;

	  if( x >= 3 ) {
	    if( nblank == 2 ) {
	      if( nme == 2 ) score++;
	      else if( nhim == 2 ) score--;
            }

	    piece = thinkBoard.getAt( x - 3, y );
  	    if( piece == 0 ) nblank--;
	    else if( piece == player ) nme--;
	    else if( piece == him ) nhim--;
	  }
	}
      }

      // Check verticals:
      for( x = 0; x < 7; x++ ) {
	for( y = 0; y < 6; y++ ) {
	  if( thinkBoard.getAt( x, y ) == 0 ) break;
	}
        if( (y>1) && (y<=4) ) {
	  int piece1 = thinkBoard.getAt( x, y+1 );
	  int piece2 = thinkBoard.getAt( x, y+2 );
	  if( piece1 == piece2 ) {
	    if( piece1 == player ) score++; else score--;
	  }
	}
      }
	
      // Check diag1 (/):
      for( x = 0; x < 4; x++ ) {
	for( y = 0; y < 3; y++ ) {
	  nhim = 0;  nme = 0;  nblank = 0;
	  for( i = 0; i < 4; i++ ) {
	    int piece = thinkBoard.getAt( x+i, y+i );
	    if( piece == player ) nme++;
	    else if( piece == him ) nhim++;
	    else nblank++;
	  }

	  if( nblank==2 ) {
	    if( nme == 2 ) score++;
	    else if( nhim == 2 ) score--;
	  }
	}
      }

      // Check diag2 (\):
      for( x = 3; x < 7; x++ ) {
	for( y = 0; y < 3; y++ ) {
	  nhim = 0;  nme = 0;  nblank = 0;
	  for( i = 0; i < 4; i++ ) {
	    int piece = thinkBoard.getAt( x-i, y+i );
	    if( piece == player ) nme++;
	    else if( piece == him ) nhim++;
	    else nblank++;
	  }

	  if( nblank==2 ) {
	    if( nme == 2 ) score++;
	    else if( nhim == 2 ) score--;
	  }
	}
      }

      return score;
    }

  /**
   * Overridden implementation of move().  Thinks about the move, and then
   * does it.
   */
  public void move() {
    boolean invalid = true;
    int move = 0;

    move = think();

    game.move( move );
  }

  /**
   * Looks for at least 'inarow' pieces in a row.
   */
  private boolean potential( int x, int y, int player, int inarow ) {
    boolean result = false;
    int i, j;
    int count;

    // check horizontal
    count = 0;
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x+i, y ) == player ) count++; else break;
    }
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x-i, y ) == player ) count++; else break;
    }
    if( count >= (inarow-1) ) return true;
    
    // check vertical
    count = 0;
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x, y+i ) == player ) count++; else break;
    }
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x, y-i ) == player ) count++; else break;
    }
    if( count >= (inarow-1) ) return true;
    
    // check diag1
    count = 0;
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x+i, y+i ) == player ) count++; else break;
    }
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x-i, y-i ) == player ) count++; else break;
    }
    if( count >= (inarow-1) ) return true;
    
    // check diag2
    count = 0;
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x+i, y-i ) == player ) count++; else break;
    }
    for( i = 1; i < 4; i++ ) {
      if( thinkBoard.getAt( x-i, y+i ) == player ) count++; else break;
    }
    if( count >= (inarow-1) ) return true;
    
    return false;
  }

  /**
   * Sets the think 'scratch' board from the outside.
   * Package scope intent is so that other AIs can use this algorithm,
   * such as ThinkPlayer.
   */
  void setThinkBoard( Board board ) {
    thinkBoard = board;
  }

  /**
   * Looks at all available moves, and chooses the best one.
   * If more than one move is of equal value, use a random number as a tie
   * breaker.
   */
  public int think() {
    int i, move = -1;
    int count = 0;
    int max = Integer.MIN_VALUE;
    int him = (player==1) ? 2 : 1;
    int val[] = new int[7];
    thinkBoard = game.getCurrentBoard().copy();

    alpha = LOSE;
    beta = WIN;
    
    for( i = 0; i < 7; i++ ) {
      game.writeMessage( "" + i + "/6" );
      if( game.isValidMove( i ) ) {
        val[i] = value( i, 0 );
        System.out.print( val[i] + " " );
        if( val[i] > max ) { 
          max = val[i]; move = i; count = 1; 
        }
        else if( val[i] == max ) { 
          count++;
        }
      }
      else {
        System.out.print( "x " );
      }
    }
    System.out.println();

    if( max == WIN ) {
      game.writeMessage( game.name[player] + " will win!" );
    }
    else if( max == LOSE ) {
      game.writeMessage( game.name[him] + " can win!" );
    }
    else if( max == TIE ) {
      game.writeMessage( "We will tie!" );
    }
    else {
      game.writeMessage( game.name[player] + " score: " + max );
    }

    if( count > 1 ) {
      int r = (Math.abs( random.nextInt() ) % count) + 1 ;
      for( i = 0; i < 7; i++ ) {
        if( game.isValidMove( i ) ) {
          if( val[i] == max ) {
	    r--;
	    if( r == 0 ) { move = i; break; }
          }
        }
      }
    }

    return move;
  }

  /**
   * Values the current board if a player were to move in the indicated
   * position.  The package-scope intent is so that other player 
   * implementations can use this, such as ThinkerPlayer.
   */
  int value( int move, int depth ) {
    int result = -1, i;

    if( (depth%2) == 0 ) {
      // my move
      thinkBoard.move( move, player );
    }
    else {
      // his move
      int him = (player == 1) ? 2 : 1;
      thinkBoard.move( move, him );
    }
    
    int winner = thinkBoard.getWinner();
    if( winner == -1 ) {
      // nobody wins
      result = 0;
    }
    else if( winner == 0 ) {
      // tie
      result = TIE;
    }
    else if( winner == player ) {
      // i win
      result = WIN;
    }
    else {
      // he wins
      result = LOSE;
    }

    if( (winner == -1) && (depth == curMaxDepth) ) {
      result = valueBoard();
    }
    if( (winner == -1) && (depth != curMaxDepth) ) {
      if( (depth%2) == 0 ) {
        // my move
        // look for move with lowest value
        int min = Integer.MAX_VALUE;
        for( i = 0; i < 7; i++ ) {
          if( thinkBoard.isValidMove( i ) ) {
            int val = value( i, depth + 1 );
	    if( val < min ) { min = val; }
  	    if( min == LOSE ) break;
          }
        }
        result = min;
      }
      else {
        // his move
        // look for move with highest value
        int max = Integer.MIN_VALUE;
	for( i = 0; i < 7; i++ ) {
	  if( thinkBoard.isValidMove( i ) ) {
	    int val = value( i, depth + 1 );
	    if( val > max ) { max = val; }
	    if( max == WIN ) break;
	  }
        }
        result = max;
      }
    }
    
    thinkBoard.undo( move );
    
    return result;
  }

  /**
   * Values the board in its current position.  This is used when the
   * computer does not see an unconditional win or loss in the near future
   * and decides to pick the best of the remaining moves (used in most
   * cases).
   */
  private int valueBoard() {
    int x, y;
    int him = (player == 1) ? 2 : 1;
    int score = 0;
    int maxheight = Math.min( 5, thinkBoard.getMaxHeight() + 1 );
    boolean pplayer[][] = new boolean[7][6];
    boolean phim[][] = new boolean[7][6];

    for( x = 0; x < 7; x++ ) {
      for( y = 0; y <= maxheight; y++ ) {
        if( (thinkBoard.getAt( x-1, y-1 ) <= 0) && 
	    (thinkBoard.getAt( x, y-1 ) == 0) && 
	    (thinkBoard.getAt( x+1, y-1 ) <= 0) ) 
        {
          break;
        }

        int piece = thinkBoard.getAt( x, y );
	    
        if( piece == 0 ) {
          pplayer[x][y] = potential( x, y, player, 4 );
	  phim[x][y] = potential( x, y, him, 4 );
	  if( pplayer[x][y] ) score+=10000; 
	  if( phim[x][y] ) score-=10000; 
	}
	else if( (x>=2) && (x<=4) ) {
	  if( piece == player ) score++;
	  if( piece == him ) score--;
	}
      }
    }

    score += checkDoubles() * 100;

    for( x = 0; x < 7; x++ ) {
      for( y = 1; y < 6; y++ ) {
        if( phim[x][y] && !pplayer[x][y] && phim[x][y-1] && 
	    !pplayer[x][y-1] ) 
	{ 
	  score -= 1000000; 
	  break; 
	}

	if( !phim[x][y] && pplayer[x][y] && !phim[x][y-1] && 
	    pplayer[x][y-1] ) 
	{ 
	  score += 1000000; 
	  break; 
	}
      }
    }

    return score;
  }

}