简单的国际象棋Minimax

Question

我有自己的国际象棋引擎使用minimax算法搜索国际象棋移动的问题我使用5层深度搜索并且只有材料/奖励/移动性评估,但它也会使愚蠢的动作和牺牲有价值的棋子,即使我给他们无限(这肯定是一个搜索问题),我没有使用任何类型的修剪,并在几秒钟内提供5深度搜索结果.

我坚持这个问题一个星期,我确定问题是回溯而不是国际象棋逻辑(因此任何没有国际象棋背景的人都会解决这个:))我搜索了很多这是我在Stack Overflow中的第一个问题我希望你们不要让我失望:)

这是简单的搜索代码

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

你没有进行静止搜索,所以愚蠢的移动可能是由于固定深度极小极大搜索容易受到众所周知的地平线效应.至少你应该扩展搜索任何强制移动,检查或捕获一个片段捕获相同或更大值的片段.