Я пытаюсь создать «ИИ» для Девяти Мужчин Морриса, но меня сильно задел алгоритм minMax. Подводя итог, я пытался найти проблему более 10 часов, но не смог. (отладка этой рекурсии отвратительна или я делаю это плохо или оба)
Поскольку я начал сомневаться во всем, что я написал, я решил опубликовать свою проблему, чтобы кто-то мог найти что-то не так в моей версии minMax. Я понимаю, что это действительно сложная задача без всего приложения, поэтому любые предложения, в которых я должен трижды проверить свой код, также приветствуются.
Вот ссылка на видео, объясняющая minMax, на которой я основывал свою реализацию: https://www.youtube.com/watch?v=l-hh51ncgDI (Первое видео, которое появляется после yt после поиска minmax - на тот случай, если вы хотите посмотреть видео и не не хочу нажимать на ссылку)
Мой minMax без обрезки альфа-бета:
//turn - tells which player is going to move
//gameStage - what action can be done in this move, where possible actions are: put pawn, move pawn, take opponent's pawn
//depth - tells how far down the game tree should minMax go
//spots - game board
private int minMax(int depth, Turn turn, GameStage gameStage, Spot[] spots){
if(depth==0){
return evaluateBoard(spots);
}
//in my scenario I am playing as WHITE and "AI" is playing as BLACK
//since heuristic (evaluateBoard) returns number equal to black pawns - white pawns
//I have decided that in my minMax algorithm every white turn will try to minimize and black turn will try to maximize
//I dont know if this is correct approach but It seems logical to me so let me know if this is wrong
boolean isMaximizing = turn.equals(Turn.BLACK);
//get all possible (legal) actions based on circumstances
ArrayList<Action> children = gameManager.getAllPossibleActions(spots,turn,gameStage);
//this object will hold information about game circumstances after applying child move
//and this information will be passed in recursive call
ActionResult result;
//placeholder for value returned by minMax()
int eval;
//scenario for maximizing player
if(isMaximizing){
int maxEval = NEGATIVE_INF;
for (Action child : children){
//aplying possible action (child) and passing its result to recursive call
result = gameManager.applyMove(child,turn,spots);
//evaluate child move
eval = minMax(depth-1,result.getTurn(),result.getGameStage(),result.getSpots());
//resets board (which is array of Spots) so that board is not changed after minMax algorithm
//because I am working on the original board to avoid time consuming copies
gameManager.unapplyMove(child,turn,spots,result);
if(maxEval<eval){
maxEval = eval;
//assign child with the biggest value to global static reference
Instances.theBestAction = child;
}
}
return maxEval;
}
//scenario for minimizing player - the same logic as for maximizing player but for minimizing
else{
int minEval = POSITIVE_INF;
for (Action child : children){
result = engine.getGameManager().applyMove(child,turn,spots);
eval = minMax(depth-1,result.getTurn(),result.getGameStage(),result.getSpots());
engine.getGameManager().unapplyMove(child,turn,spots,result);
if(minEval>eval){
minEval=eval;
Instances.theBestAction = child;
}
}
return minEval;
}
}
Простая эвристика для оценки:
//calculates the difference between black pawns on board
//and white pawns on board
public int evaluateBoard(Spot[] spots) {
int value = 0;
for (Spot spot : spots) {
if (spot.getTurn().equals(Turn.BLACK)) {
value++;
}else if(spot.getTurn().equals(Turn.WHITE)){
value--;
}
}
return value;
}
Мой номер:
//the same parameters as in minMax() function
public void checkMove(GameStage gameStage, Turn turn, Spot[] spots) {
//one of these must be returned by minMax() function
//because these are the only legal actions that can be done in this turn
ArrayList<Action> possibleActions = gameManager.getAllPossibleActions(spots,turn,gameStage);
//I ignore int returned by minMax() because,
//after execution of this function, action choosed by minMax() is assigned
//to global static reference
minMax(1,turn,gameStage,spots);
//getting action choosed by minMax() from global
//static reference
Action aiAction = Instances.theBestAction;
//flag to check if aiAction is in possibleActions
boolean wasFound = false;
//find the same action returned by minMax() in possibleActions
//change the flag upon finding one
for(Action possibleAction : possibleActions){
if(possibleAction.getStartSpotId() == aiAction.getStartSpotId() &&
possibleAction.getEndSpotId() == aiAction.getEndSpotId() &&
possibleAction.getActionType().equals(aiAction.getActionType())){
wasFound = true;
break;
}
}
//when depth is equal to 1 it always is true
//because there is no other choice, but
//when depth>1 it really soon is false
//so direct child of root is not chosen
System.out.println("wasFound?: "+wasFound);
}
Верна ли идея моей реализации алгоритма minMax?