Simple chess minimax

Question

I have a problem with my own chess engine, using a minimax algorithm to search for chess movements. I use a 5-layer depth search and only with the evaluation of material / bonus / mobility, but it also makes silent movements and sacrifices valuable objects, even when I give them infinity (which is undoubtedly a search problem), I do not use any types of cropping and gives a 5x search result in a few seconds.

I’ve been stuck with this problem for a week, I’m sure that the problem is with Backtracking and not with Chess Logic (so anyone who does not have a chess background will solve this :)) and I searched a lot, this is my first question on Stack Overflow, and I hope you guys won’t be disappointed :)

Here is a 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; } 

Answer 1

You do not search for peace , so dumb moves are probably related to the well - known horizon effect , which can be perceived with a minimal minimum search. At a minimum, you should expand your search for any forced moves, checks, or grabs when a piece captures one or more values.

Answer 2

There are several things you can improve with your code:

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

Answer 3

Should the search function in the initial minimax function be maximized and not minimized?