A Simple Chess Minimax

Question

I have problem with my own Chess Engine using minimax algorithm to search for chess moves I use a 5 plies depth search and with only material/bonus/mobility evaluation , but it also make dumb moves and sacrifices valuable pieces even when I give to them infinity (which is sure a search problem), I'm not using any types of pruning and gives a 5 depth search result in few seconds.

I'm stuck in this problem for a week, I am sure the Problem is with the Backtracking not the Chess Logic (so anyone with no chess background would solve this :)) and I searched a lot this is my first Question in Stack Overflow and I hope you guys won't Disappoint me :)

Here is the simple search code

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

Solution 1

You're not doing quiescence search, so the dumb moves are likely due to the well-known horizon effect that fixed depth minimax searches are susceptible to. At a minimum you should extend search for any forced moves, checks or captures where a piece captures one of equal or greater value.

Solution 2

There are several things that could be improved with your code:

1. Use the negamax formulation. This will eliminate the code duplication of your minsearch and maxsearch.
2. Use alpha-beta pruning. This will double your search depth for a given amount of search time.
3. Use iterative deepening in combination with a hash table. The iterative deepening will gradually refine your search result (so that you can stop searching and make a move at any time), and the hash table will let you avoid duplicate work if you encounter transpositions in the game tree.

Comments

[Bo Persson]

If you do a 5 ply search, the program will "fix" any problems by pushing the loss 6 plies forward. Programs are "smart"! You cannot let it stop the search when some pieces are about to be captured.

[Osama]

Actually when I said dumb moves I meant really dumb moves like sacrificing Valuable Pieces for less one that should be avoided even in a 2 ply search

[Osama]

It really doesn't matter it depends on which player is the maximizer and which player is the minimizer.