I
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";
}
}
// -------------------------------------------------------------------------------------------
}
// ############################################################################################
