c++ - 一个简单的国际象棋

我自己的国际象棋引擎使用minimax算法搜索象棋移动时遇到问题，我使用5层深度搜索并且仅进行了 Material /奖金/移动性评估，但是即使我赋予它们无限性，它也会使笨拙的移动并牺牲有值(value)的棋子(这肯定是搜索问题)，我没有使用任何类型的修剪，而是在几秒钟内给出了5深度的搜索结果。

我在这个问题上停留了一周，我确定问题出在回溯而不是国际象棋逻辑上(所以任何没有国际象棋背景的人都可以解决这个问题:))，我搜索了很多东西，这是我在堆栈溢出中的第一个问题我希望你们不会让我失望的:)

这是简单的搜索代码

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;
}

最佳答案

您不是在做quiescence search，所以愚蠢的举动很可能是由于众所周知的horizon effect容易受到固定深度minimax搜索的影响。至少，您应该扩大搜索范围，以寻找任何被强制移动，检查或捕获的 object ，其中一块 object 可捕获相等或更大的值(value)。