플레이어가 연속적으로 두 번 움직일 수있을 때 Negamax-search 구현이 작동하지 않습니다.

Question

Java에서 Nine Men's Morris 게임에 대한 Negamax 검색을 구현하려고합니다.

플레이어가 연속으로 3 개의 피스 (밀이라고도 함)를 사용하면 플레이어는 턴을 바꾸기 전에 상대방의 피스 ('추가'이동)를 ​​제거합니다. 모든 초기 부분이 배치 된 후에

또한, 세트 피스 상 및 이동 편 위상이있다.

내 구현은 다음과 같습니다

public int[] negamaxSet(int depth, int alpha, int beta, int color) { 
    if (depth == 0 || board.isGameOver()) { 
     return new int[] { color * evaluateBoard(color}; 
    } 

    int stonesSet = color == -1 ? board.blackStonesSet : board.whiteStonesSet; 
    // set piece phase 
    if (stonesSet < Game.initialPieces) { 
     List<Piece> moves = board.getEmpty(); 

     int bestValue = Integer.MIN_VALUE; 
     int bestMoveX = -1; 
     int bestMoveY = -1; 

     for (Piece piece : moves) { 
      Piece move = new Piece(color, piece.x, piece.y); 
      board.setPiece(move); 

      int value[] = null; 

      //Player made Mill, move again 
      if(board.checkMill(move)){ 
       value = negamaxRemove(depth - 1, alpha, beta, color);    
      } 
      //normal move, switch turn 
      else { 
       value = negamaxSet(depth - 1, -beta, -alpha, -color); 
       value[0] = -value[0]; 
      } 
      if (value[0] > bestValue) { 
       bestValue = value[0]; 
       bestMoveX = move.x; 
       bestMoveY = move.y; 
      } 
      if (value[0] > alpha) { 
       alpha = value[0]; 
      } 

      board.revertLastMove(); 

    //  if (alpha >= beta) 
    //   break; 
     } 
     return new int[] { bestValue, bestMoveX, bestMoveY }; 
    } else { 

     //move phase 

     List<Piece> moves = board.getPiecesByColor(color); 

     int bestValue = Integer.MIN_VALUE; 
     int bestMoveX = -1; 
     int bestMoveY = -1; 
     int bestMoveX2 = -1; 
     int bestMoveY2 = -1; 

     for (Piece piece : moves) { 

      List<Piece> adjPieces = board.getAdjacentEmtpy(piece); 
      for(Piece adjPiece : adjPieces){ 

       Piece newFrom = new Piece(color, piece.x, piece.y); 
       Piece newTo = new Piece(color, adjPiece.x, adjPiece.y); 

       board.movePiece(newFrom, newTo); 

       int[] value = null; 

       //Player made Mill, move again 

       if(board.checkMill(newTo, false)){ 
        value = negamaxRemove(depth - 1, alpha, beta, color); 

       } else { 
        value = negamaxSet(depth - 1, -beta, -alpha, -color); 
        value[0] = -value[0]; 
       } 

       if (value[0] > bestValue) { 
        bestValue = value[0]; 
        bestMoveX = newFrom.x; 
        bestMoveY = newFrom.y; 
        bestMoveX2 = newTo.x; 
        bestMoveY2 = newTo.y; 
       } 
       if (value[0] > alpha) { 
        alpha = value[0]; 
       } 

       board.revertLastMove(); 

    //   if (alpha >= beta) 
    //    break; 

      } 


     } 
     return new int[] { bestValue, bestMoveX, bestMoveY, bestMoveX2, bestMoveY2 };  
    } 
} 

기본 Negamax 알고리즘을 변경하고 돌을 설정하고 알고리즘 자체가 둘 사이를 구별하지 않는 하나 개의 작업에 돌을 이동 캡슐화하지 아마 것이 좋습니다 ,하지만 내 이해에서 그것은 여전히 이런 식으로해야합니다.

negamaxRemove 함수는 기본적으로 negamaxSet과 동일하지만 밀링 (불가능)을 확인하고 제거 할 부분을 찾지 않습니다.

호출 함수와 동일한 매개 변수로 negamaxRemove를 호출하고 부호를 바꾸지 않으므로 (다시 최대화 함) 올바른지 여부

어쨌든 AI 플레이어는 상대방이 제재소를 형성하는 것을 막지 않습니다 (가능한 경우 자신을 형성합니다).

알고리즘이 이와 같이 정확합니까? 코드의 다른 부분에서 오류를 찾아야합니까? 또는 Negamax가 어떻게 작동해야하는지 오인 했습니까? (alpha-beta pruning을 주석 처리하여 알파 또는 베타를 잘못 설정하면 잘못되지는 않습니다.)

일부 포인터는 정말 고맙게 생각합니다.

Answer 1

I've implemented this game. "행동 수행, 다른 행동 수여"에서 "여러 행동 수행"으로 이동 정의를 변경하십시오. 그런 다음 2 개의 "움직임"을하는 대신에, from: 3, to: 0, remove: 17, from: 3, to: 0, remove 19 등과 같은 움직임으로 끝납니다. 조각을 제거하지 않는 움직임의 경우 단순히 제거를 -1으로 설정하십시오.