Back

Explore Courses Blog Tutorials Interview Questions
0 votes
1 view
in AI and Deep Learning by (50.2k points)

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

1 Answer

0 votes
by (108k points)

You have to perform the quiescence search as it decreases the effect of the horizon problem faced by AIengines for various games like chess. At a minimum, you should extend the search for any forced moves, checks or captures where a piece captures one of equal or greater value. 

Minimax is a decision rule used in Artificial Intelligence so if you wish to learn more about Minimax Decision Rule then visit this Artificial Intelligence Course.

Welcome to Intellipaat Community. Get your technical queries answered by top developers!

28.4k questions

29.7k answers

500 comments

94.1k users

Browse Categories

...