用maximax算法幫助連接四個Javascript

Question

我想在我的連接四個遊戲中使用minimax算法創建AI，但我無法正常工作。我相信我非常接近，但我仍然無法弄清楚。任何人都可以幫助我解決任何錯誤嗎？我意識到我的代碼並不好，因爲我對Javascript的效率不高，這就是爲什麼我想試試這個。如果我完全偏離軌道，有人能告訴我更好的方法嗎？提前致謝。

編輯：我用我更新後的代碼替換了我的代碼。它現在「工作」，只要給我AI動作，但問題是他們不是「聰明」的動作。我已經看過許多極小極小定義，我覺得我已經正確實現了它。即使當我跑到7尺的深度時，一個5歲的人也可以擊敗它。任何幫助，將不勝感激。

function getBestMove(currBoard,depth,who) { 
     var opp; 
     //Get opponent for next piece 
     if(who == 'a') { 
      opp = 'p'; 
     } else { 
      opp = 'a'; 
     } 

     var tBoard = new Array(rows); 
     for(var i=0; i<tBoard.length; i++) { 
      tBoard[i] = new Array(cols); 
     } 

     var moves = new Array(aiOpenCols.length); 
     //Drop each piece and use minimax function until depth == 0 
     for(var i=0; i<aiOpenCols.length; i++) { 
      for(var j=0; j<rows; j++) { 
       for(var k=0; k<cols; k++) { 
        tBoard[j][k] = currBoard[j][k]; 
       } 
      } 
      tBoard = dropPiece(aiOpenCols[i],who,tBoard); 
      moves[i] = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]); 
     } 

     var bestAlpha = -100000; //Large negative 
     //Use random column if no moves are "good" 
     var bestMove = Math.floor(Math.random() * aiOpenCols.length); 
     bestMove = +aiOpenCols[bestMove]; 
     //Get largest value from moves for best move 
     for(var i=0; i<aiOpenCols.length; i++) { 
      if(+moves[i] > bestAlpha) { 
       bestAlpha = moves[i]; 
       bestMove = aiOpenCols[i]; 
      } 
     } 

     bestMove++; //Offset by 1 due to actual drop function 
     return bestMove; 
    } 
    function minimax(currBoard,depth,who,col) { 
     //Drop current piece, called from getBestMove function 
     currBoard = dropPiece(col,who,currBoard); 

     //When depth == 0 return heuristic/eval of board 
     if(+depth == 0) { 
      var ev = evalMove(currBoard); 
      return ev; 
     } 
     var alpha = -100000; //Large negative 
     var opp; 
     //Get opponent for next piece 
     if(who == 'a') { 
      opp = 'p'; 
     } else { 
      opp = 'a'; 
     } 

     //Loop through all available moves 
     for(var i=0; i<aiOpenCols.length; i++) { 
      var tBoard = new Array(rows); 
      for(var i=0; i<tBoard.length; i++) { 
       tBoard[i] = new Array(cols); 
      } 
      for(var j=0; j<rows; j++) { 
       for(var k=0; k<cols; k++) { 
        tBoard[j][k] = currBoard[j][k]; 
       } 
      } 
      //Continue recursive minimax until depth == 0 
      var next = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]); 
      //Alpha = max(alpha, -minimax()) for negamax 
      alpha = Math.max(alpha, (0 - +next)); 
     } 
     return alpha; 
    } 
    function evalMove(currBoard) { 
     //heuristic function 
     //AI = # of 4 streaks + # of 3 streaks + # of 2 streaks - # of 3 streaks opp - # of 2 streaks opp   
     var fours = checkFours(currBoard,'b') * 1000; 
     var threes = checkThrees(currBoard,'b') * 100; 
     var twos = checkTwos(currBoard,'b') * 10; 
     var oppThrees = checkThrees(currBoard,'r') * 100; 
     var oppTwos = checkTwos(currBoard,'r') * 10; 

     var scores = fours + threes + twos - oppThrees - oppTwos; 

     //If opponent wins, return large negative 
     var oppFours = checkFours(currBoard,'r'); 
     if(+oppFours > 0) { 
      return -100000; 
     } else { 
      return scores; 
     } 
    } 
    function dropPiece(col,who,currBoard) { 
     for(var i=0; i<currBoard.length; i++) { 
      if(currBoard[i][col] != 'w') { 
       //Make sure column isn't full 
       if(i != 0) { 
        if(who == 'p') { 
         currBoard[i-1][col] = 'r'; 
        } else { 
         currBoard[i-1][col] = 'b'; 
        } 
        break; 
       } 
      } 
      //If column is empty, place in first row 
      if(i == (currBoard.length - 1)) { 
       if(who == 'p') { 
        currBoard[i][col] = 'r'; 
       } else { 
        currBoard[i][col] = 'b'; 
       } 
      } 
     } 
     return currBoard; 
    } 

Answer 1

您的評估函數將值分配給沒有值的位置要素。連續有兩個連續的單元格沒有價值。如果第四個單元格可以被對手佔用而不允許在其他地方獲勝，那麼連續三個也沒有價值。

簡化。對於Connect Four，您只需要關心該位置是贏或輸，或者在下一步移動中該位置可以贏或輸。如果這是一場勝利，則返回一個很大的正面價值。如果它是一個損失，返回一個很大的負值。如果在下一步移動中可以贏得或失去位置，則爲該分支擴展搜索深度一層，然後再次調用minimax（），返回結果。後者將避免所有固定深度極小極大搜索易受影響的horizon effect。否則返回零。