Problem mit Minimax Algorithmus

[Ishildur]

Hallo zusammen
Ich muss für ein Schulprojekt ein komplette Mühlespiel inklusive der KI - Programmieren und bin eigentlich fertig damit. Leider spinnt aber die KI, welche auf einem Minimax Algorithmus mit Alphabeta - Pruning und variabler sowie dynamischer Tiefensuche basiert total! Um das Problem zu lösen, habe ich mich zunächst auf den reinen Minimax Algorithmus beschränkt, aber auch da passieren immer wieder Fehler, die ich einfach nicht lokalisieren kann! Ich habe mir dazu folgende Überlegungen gemacht!

- Ist es korrekt, dass man darauf achten sollte, dass man nur "komplette" Züge bewertet, also keine Halbzüge?

- Bei Mühle kann es ja vorkommen, dass derselbe Spieler zweimal zieht, wesshalb ich die dynamische Tiefensuche eingebaut habe, welche dafür sorgt, dass immer derselbe Spieler im Leaf ist. Ich frage mich jedoch, ob dies wirklich nötig ist.

- Ich habe bemerkt, dass die KI richtig funktioniert, wenn die Suchtiefe gering ist, sobald ich diese jedoch erhöhe, fängt sie an Fehler zu machen! Ich habe beispielsweise 2 Steine nebeneinander und kann eine Mühle machen, die KI greift jedoch nicht ein, sondern setzt seinen Stein munter an einem anderen Ort!

Hier ist mal der Code, vielleicht findet jemand einen offensichtlichen Fehler:

// #################################### define the package ####################################
package mill.player;
// ############################################################################################

// ################################ import all needed libraries ###############################
import mill.game.*; // the game library
// ############################################################################################

// ###################################### class AIPlayer ######################################
// --------------------------------------------------------------------------------------------
/** This class implements the Player interface and chooses the best move using the 
    minimax and alphabeta pruning algorithm */
// --------------------------------------------------------------------------------------------
public final class AIPlayer implements Player{
 // ********************************** inner class Situation **********************************
 public final class Situation{
 // ------------------------------------- dynamic members -------------------------------------
 public Game vrtGam; // a virtual game
 public Move vrtMov; // a virtual move
 // -------------------------------------------------------------------------------------------

 // ---------------------------------- default - constructor ----------------------------------
 public Situation(Game gam){
  // init all members by the parametric values
  this.vrtGam = gam.createVirtualInstance();
  this.vrtMov = null;
 }
 // -------------------------------------------------------------------------------------------

 // ------------------------------------- method "setMove" ------------------------------------
 public final void setMove(Move mov){
  // execute the move on the virtual game and save its source and destination
  this.vrtGam.move(this.vrtMov = mov);
 }
 // -------------------------------------------------------------------------------------------
 }
 // *******************************************************************************************

 // ---------------------------------------- constants ----------------------------------------
 private static final byte INF          = 100;  // infinite
 public  static final byte LVL_EASY     = 0x00; // easy difficulty
 public  static final byte LVL_MODERATE = 0x02; // moderate difficulty
 public  static final byte LVL_HARD     = 0x04; // hard difficulty
 private static final byte RAT_WIN      = 0x5a; // winner rating
 private static final byte RAT_NUM      = 0x05; // rating per existing stone on the field
 private static final byte RAT_MIL      = 0x01; // rating per stone inside a mill
 // -------------------------------------------------------------------------------------------

 // ------------------------------------- dynamic members -------------------------------------
 private byte lvl; // the difficulty level
 // -------------------------------------------------------------------------------------------

 // ------------------------------------ custom constructor -----------------------------------
 public AIPlayer(byte lvl){
  // assign the player color and the difficulty level
  this.lvl = lvl;
 }
 // -------------------------------------------------------------------------------------------

 // ----------------------- private recursive helper method "alphabeta" -----------------------
 private final int alphabeta(Situation sit,int depth,int max,int alpha,int beta){
  // determine the current virtual game
  Game       vrtGam = sit.vrtGam;
  PlayerInfo plyAct = vrtGam.getActivePlayer();

  // dynamically increase the search depth, if the current player is in drop mode
  if(plyAct.isInDropMode()) max++;

  // check if the maximal search depth hasn't reached yet
  if(depth < max){
   // determine if the current player is the max player
   boolean bMax = plyAct.getColor() == PlayerColor.WHITE;

   // return if the game ended with the last move
   if(vrtGam.getWinner() != null) return bMax ? AIPlayer.RAT_WIN : -AIPlayer.RAT_WIN;

   // start a loop for walking each possible move
   for(Move mov: vrtGam.getValidMoves()){
    // create a new situation for the current move and execute it
    Situation sitCur = new Situation(vrtGam);
    sitCur.setMove(mov);

    // determine the rating of the current situation
    int rat = this.alphabeta(sitCur,depth+1,max,alpha,beta);

    // check if the current player is the max - player
    if(bMax){
     // return beta if the current rating is bigger than beta or adjust alpha if the rating
     // of the current situation is highter than the alpha
     if(rat >= beta) return beta;
     if(rat > alpha) alpha = rat;
    }
    // otherwise the current player is the min - player
    else{
     // return alpha if the current rating is smaller than alpha or adjust beta if the rating
     // of the current situation is highter than the beta
     if(rat <= alpha) return alpha;
     if(rat < beta)  beta = rat;
    }
   }

   // return the alpha or beta value depending on the currently active player
   return bMax ? alpha : beta;
  }
  // otherwise return the evaluation rating of the current situation
  else{
   // calculate and return the number of stones on board
   int rating = vrtGam.getWhitePlayer().getNumberOfStonesOnBoard();
   return rating - vrtGam.getBlackPlayer().getNumberOfStonesOnBoard();
  }
 }
 // -------------------------------------------------------------------------------------------

 // ---------------------------------- abstract method "move" ---------------------------------
 /** This method will be called by application whenever the next computer move must
     be determined
 @param  game The current game
 @return The determined move
 @author Samuel Lörtscher */
 // -------------------------------------------------------------------------------------------
 public final Move move(Game game){
  // declare and init local variables
  int max = this.lvl + (game.getActivePlayer().isInDropMode() ? 1 : 0);

  // create a switch statement for the variable depth search
  // SET:   The AI must detect simple mills and traps
  // SHIFT: The AI can deepen the search as lesser moves are available
  // JMP:   The AI must decrease the search depth as may more destination fields are available
  switch(game.getActivePlayer().getStatus()){
   case SET:   max += 2; break;
   case SHIFT: max += 8; break;
   case JUMP:  max += 4; break;
  }

  // declare and init local variables
  Situation sitOpt = null;
  int       topRat = AIPlayer.INF;

  // start a loop for walking each possible move
  for(Move mov: game.getValidMoves()){
   // create a new situation for the current move and execute it
   Situation sitCur = new Situation(game);
   sitCur.setMove(mov);

   // determine the rating for the current move
   int rat = this.alphabeta(sitCur,0,max,-AIPlayer.INF,AIPlayer.INF);

   // check if a current situation was already determined
   if(sitOpt == null || rat < topRat){
    // adjust the optimal situation and the rating
    sitOpt = sitCur;
    topRat = rat;
   } 
  }

  // finally returnt the move which lead to the optimal situation
  return sitOpt.vrtMov;
 }
 // -------------------------------------------------------------------------------------------

 // -------------------------------- abstract method "getName" --------------------------------
 /** This method will be called by the application whenever the name of the player is needed
 @return The name of the player
 @author Samuel Lörtscher */
 // -------------------------------------------------------------------------------------------
 public final String getName(){
  // create a switch statement for separating all possible names
  switch(this.lvl){
   case AIPlayer.LVL_EASY:     return "Easy AI";
   case AIPlayer.LVL_MODERATE: return "Moderate AI";
   default:                    return "Hard AI";
  }
 }
 // -------------------------------------------------------------------------------------------
}
// ############################################################################################