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

Locate

Added tag C++. This is C++ right? – Gillan

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. – Eatton

Answer 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.

Hoecake

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 – Locate

Answer 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.

Anastice

Last two links are broken. – Drud

@Kowalski fixed, tnx for reporting. – Anastice

Answer 3

Shouldn't the search function in the initial minimax function be maximizing and not minimizing?

Lannylanolin

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