シンプルチェスミニマックス

Question

ミニマックスアルゴリズムを使って自分のチェスエンジンに問題があり、チェスの動きを検索することができます。私は5プライ深度の検索とマテリアル/ボーナス/モビリティ評価のみを使用しますが、ダムの動きをして貴重なものを犠牲にします無限に無限大（検索の問題があると確信しています）しても、何らかのタイプのプルーニングを使用しておらず、数秒で5つの深さの検索結果が得られます。

私はこの問題で1週間立ち往生していますが、問題はチェスロジックではないバックトラックにあると確信しています（チェスのバックグラウンドを持たない誰でもこれを解決できます:)）スタックオーバーフローでの質問と私はあなたたちが私を失望させないだろう:)

をここに願っていますが、単純な検索コード

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

であるあなたはquiescence searchをやっていないので、ダムの移動が原因十分に可能性があります固定深さのミニマックス検索では、影響を受けやすいと知られているhorizon effectです。ピースが等しいかそれ以上の値をキャプチャする場合は、少なくとも強制的な移動、チェックまたはキャプチャを検索する必要があります。

Answer 2

あなたのコードを改善することができ、いくつかのものがあります。

1. negamax製剤を使用しますが。これにより、minsearchとmaxsearchのコードの重複がなくなります。
2. alpha-betaプルーニングを使用してください。これにより、指定した検索時間分の検索深度が2倍になります。
3. iterative deepeningをhash tableと組み合わせて使用​​してください。反復深化は徐々に検索結果を絞り込みます（検索を停止していつでも移動できます）。ハッシュテーブルでは、ゲームツリーで転置が発生した場合、重複した作業を避けることができます。

Answer 3

初期minimax関数の検索関数は最大化していて、最小化してはいけませんか？