A Simple Chess Minimax

Question

Tengo un problema con mi propio Chess Engine usando el algoritmo minimax para buscar movimientos de ajedrez Uso una búsqueda de profundidad de 5 capas y solo material/bonus/evaluación de movilidad, pero también hace mudos movimientos y sacrifica piezas valiosas incluso cuando les doy infinito (que es un problema de búsqueda), no estoy usando ningún tipo de poda y obtengo un resultado de búsqueda de profundidad de 5 segundos.

Estoy atascado en este problema durante una semana, estoy seguro de que el problema está en el retroceso no en la lógica del ajedrez (por lo que cualquier persona sin experiencia ajedrecística lo resolvería :)) y busqué mucho esta es mi primera pregunta en desbordamiento de pila y espero que ustedes no me :) decepcionaré

Aquí es el simple código de búsqueda

int GameControl::Evaluate(ChessBoard _B) 
{ 

    int material=0,bonus=0,mobility=0; 
    for(int i=0;i<8;i++) 
     for(int j=0;j<8;j++) 
     { 

      if(_B.Board[i][j]!=EMPTY) 
      { 
       if(_B.Board[i][j]->pieceColor==WHITE){ 
        material+=-_B.Board[i][j]->Weight; 
        bonus+=-_B.Board[i][j]->bonusPosition[i][j]; 
        mobility+=-_B.Board[i][j]->getPossibleMovesList(i,j,B).size(); 
       } 
       else { 
        material+=_B.Board[i][j]->Weight; 
        bonus+=_B.Board[i][j]->bonusPosition[i][j];    
       mobility+=_B.Board[i][j]->getPossibleMovesList(i,j,B).size(); 
       } 
      } 
     } 
     return material+bonus/10+mobility/20; 
} 


pair<pair<int,int>,pair<int,int>> GameControl::minimax(int depth , ChessBoard _B) 
{ 
    short int i,j; 

    int bestValue = -INFINITY; 

    pair<pair<int,int>,pair<int,int>> bestMove; 

    vector< pair<int,int> > ::iterator it; 

    vector< pair<int,int> > Z; 

    for(i = 0; i < 8; i++) 

     for(j = 0; j < 8; j++) 
     { 
      if(_B.Board[i][j]!=EMPTY && _B.Board[i][j]->pieceColor==BLACK) 
      { 
       Z=_B.Board[i][j]->getPossibleMovesList(i,j,_B); 
       for(it=Z.begin();it!=Z.end();it++) 
       { 
        pair<int,int> temp; 
        temp.first=i,temp.second=j; 
        ChessPieces* DestinationPiece; 
        DestinationPiece=_B.Board[(*it).first][(*it).second]; 
        //Moving 
        _B.Board[(*it).first][(*it).second]=_B.Board[i][j]; 
        _B.Board[i][j]=EMPTY; 
        // 
        int value = minSearch(depth-1 , _B); 
        if(value > bestValue) 
        { 
         bestValue = value; 
         bestMove.first.first = i; 
         bestMove.first.second = j; 
         bestMove.second.first = (*it).first; 
         bestMove.second.second = (*it).second; 

        } 
        //Undo Move 
        _B.Board[i][j]=_B.Board[((*it).first)][(*it).second]; 
        _B.Board[(*it).first][(*it).second]=DestinationPiece; 
       } 

      } 
     } 

     return bestMove; 
} 


int GameControl::minSearch(int depth , ChessBoard _B) 
{ 

    short int i; 
    short int j; 
    if(depth==0) 
     return Evaluate(_B); 

    int bestValue = INFINITY; 
    for(i = 0; i < 8; i++) 
     for(j = 0; j < 8; j++) 
     { 
      vector< pair<int,int> > ::iterator it; 
      vector< pair<int,int> > Z; 
      if(_B.Board[i][j]!=EMPTY && _B.Board[i][j]->pieceColor==WHITE && !_B.Board[i][j]->V.empty()) 
      { 

       Z=_B.Board[i][j]->getPossibleMovesList(i,j,_B); 
       for(it=Z.begin();it!=Z.end();it++) 
       { 

        pair<int,int> temp; 
        temp.first=i; 
        temp.second=j; 
        ChessPieces* DestinationPiece; 
        DestinationPiece=_B.Board[(*it).first][(*it).second]; 
        // Moving 
        _B.Board[(*it).first][(*it).second]=_B.Board[i][j]; 
        _B.Board[i][j]=EMPTY; 
        // 
        int value = maxSearch(depth-1 , _B); 
        if(value < bestValue) 
         bestValue = value; 
        //Undo Move 
        _B.Board[i][j]=_B.Board[(*it).first][(*it).second];  
        _B.Board[(*it).first][(*it).second]=DestinationPiece; 
        // 
       } 

      } 
     } 
     return bestValue; 
} 


int GameControl::maxSearch(int depth , ChessBoard _B) 
{ 


    short int i; 
    short int j; 
    if(depth==0) 
     return Evaluate(_B); 
    vector< pair<int,int> > ::iterator it; 
    vector< pair<int,int> > Z; 
    int bestValue = -INFINITY; 
    for(i = 0; i < 8; i++) 
     for(j = 0; j < 8; j++) 
     { 

      if(_B.Board[i][j]!=EMPTY && _B.Board[i][j]->pieceColor==BLACK) 
      { 
       Z=_B.Board[i][j]->getPossibleMovesList(i,j,_B); 
       for(it=Z.begin();it!=Z.end();it++) 
       { 
        pair<int,int> temp; 

        temp.first=i,temp.second=j; 
        ChessPieces* DestinationPiece; 
        DestinationPiece=_B.Board[(*it).first][(*it).second]; 
        //Moving 
        _B.Board[(*it).first][(*it).second]=_B.Board[i][j]; 
        _B.Board[i][j]=EMPTY; 
        // 
        int value = minSearch(depth-1 , _B); 
        if(value > bestValue)  
         bestValue = value; 

        //Undo Move 
        _B.Board[i][j]=_B.Board[((*it).first)][(*it).second]; 
        _B.Board[(*it).first][(*it).second]=DestinationPiece; 
       } 

      } 
     } 
     return bestValue; 
} 

Answer 1

Usted no está haciendo quiescence search, por lo que los movimientos mudos son probablemente debido al pozo -conocido horizon effect que las búsquedas de minimax de profundidad fija son susceptibles de. Como mínimo, debe ampliar la búsqueda de movimientos forzados, verificaciones o capturas donde una pieza captura un valor igual o mayor.

Answer 2

hay varias cosas que se pueden mejorar con su código:

1. utilizar la formulación negamax. Esto eliminará la duplicación de código de su minsearch y maxsearch.
2. Utilice alpha-beta poda. Esto duplicará la profundidad de búsqueda para una determinada cantidad de tiempo de búsqueda.
3. Use iterative deepening en combinación con un hash table. La profundización iterativa refinará gradualmente el resultado de búsqueda (para que pueda detener la búsqueda y realizar un movimiento en cualquier momento), y la tabla hash le permitirá evitar el trabajo duplicado si encuentra transposiciones en el árbol de juego.

Answer 3

¿No debería la función de búsqueda en la función minimax inicial maximizar y no minimizar?