0

定義されたポリシールールに従ってボードの状態を評価する必要がある単純なAIを作成しています。ゲームはテトリスに非常に似ています。ボードの状態と次のN個のピース​​のシーケンス（Nは変数）を考慮して、現在の最適な動きを決定する必要があります。

つまり、ピースキューの最初のピースを使用する必要があります（複数の「次の」レベルを持つテトリスのように）。

1つ先に進むと、これは非常に簡単です。

bestMove = function(Board board, piece piece)
{
     possibleMoves = getPossibleMoves(board, piece)
     bestMove = null
     bestScore = -INFINITY
     boardCp = clone(board)     

     for (move in possibleMoves)
     {
         tempBoard = applyMove(boardCp, move)
         if (tempBoard.score > bestScore)
         {
             bestMove = move
             bestScore = tempBoard.score
         }
         boardCp = undoMove(tempBoard, move)
     }

    return move
}

さて、どうすればこのアルゴリズムをNに一般化できますか？私は再帰の専門家ではないので、助けてくれてありがとう！

PS：私はJavaを使用していますが、どの言語や擬似コードでも大歓迎です。

4

4 に答える 4

4

これは、N 手先を考慮に入れるように簡単に変更できます。再帰的または反復的な方法で。

bestMove = function(Board board, piece piece, int lookAhead)
{
 possibleMoves = getPossibleMoves(board, piece)
 bestMove = null
 bestScore = -INFINITY
 boardCp = clone(board)     

 for (move in possibleMoves)
 {
    /* just the original code */
     if(lookAhead <= 1) {
         tempBoard = applyMove(boardCp, move)
         if (tempBoard.score > bestScore)
         {
             bestMove = move
             bestScore = tempBoard.score
          }
         boardCp = undoMove(tempBoard, move)
     }

     /* recursion, can be changed to a loop */
     else {
        tempBoard = applyMove(boardCp, move)                // apply
        move2 = bestMove(tempBoard, piece, lookAhead-1)     // dive and get best 
        boardCp = undoMove(tempBoard, move)                 // (1) check how good it actually is
        tempBoard = applyMove(boardCp, move2)
        if (tempBoard.score > bestScore)
         {
             bestMove = move2
             bestScore = tempBoard.score
          }
        boardCp = undoMove(tempBoard, move2)                // generaly I'd refactor both if-else paths and reuse some code
     }
  }

return bestMove
}

関数から 2 つの値を返すことができる場合は、(1)その必要はありません。移動が必要であり、スコアです。

ところで。最小-最大、アルファ-ベータ (プルーニングあり) アルゴリズムについて読んだことがありますか?

于 2013-02-19T18:57:41.307 に答える
1

純粋な再帰アルゴリズム。ただし、次のピースがどのように編成されているかはわかりません。そのため、ここではキューを使用して想定しました。ただし、クローン作成は最も効率的ではないため、データ構造に依存します。 

 function getBestPossibleScore(Board board, Queue<piece>nextPieces){
         if (nextPieces.isEmpty())
             return board.score;
         piece = piece.pop();
         possibleMoves = getPossibleMoves(board, piece)   

         bestScore = -INFINITY
         boardCp = clone(board)     

         for (move in possibleMoves)
         {
             tempBoard = applyMove(boardCp, move)
             curentScore = getBestPossibleScore(tempBoard,nextPieces.clone());
             if (currentScore > bestScore)
             {            
                 bestScore = currentScore
              }
             boardCp = undoMove(tempBoard, move)
          }

        return board.score+bestScore;
    }
     function getBestMove(Board board, Queue<piece> nextPieces)
        {

         piece = piece.pop();
         possibleMoves = getPossibleMoves(board, piece)   
         bestMove=null;
         bestScore = -INFINITY
         boardCp = clone(board)     

         for (move in possibleMoves)
         {
             tempBoard = applyMove(boardCp, move)
             currentScore = getBestPossibleScore(tempBoard,nextPieces.clone());
             if (currentScore > bestScore)
             {            
                 bestScore = currentScore
                 bestMove=move;
              }
             boardCp = undoMove(tempBoard, move)
          }

        return bestMove
        }
于 2013-02-19T19:17:23.897 に答える
0

これに擬似コードアプローチを採用します。私の最初の選択は、アルファベータ法を使用したミニマックス法です。これは、あなたと同様の問題を解決するための一般的で実績のある方法だからです。

しかし、あなたが何か違うことをしたい場合。

List moves = new list()
Best board = current board    

While (queue is not empty){
    grab the next item in the queue.
    Implement your algorithm.
    add the move to the move list.
    update the best board
}

最高ではありませんが、キューに基づいた移動のリストを提供する非常に単純なアプローチです。ボードの状態を前の最良のボードからアルゴリズムボード要素に転送し、次のピースをキューからアルゴリズムのピース引数に転送するだけです。

于 2013-02-19T19:38:00.703 に答える
0

i can't help you, but i can suggest to you this MinMax algorithm this is what i have used in my AI university course.

Pseudocode, if can be useful:

function integer minimax(node, depth)
  if node is a terminal node or depth <= 0:
    return the heuristic value of node
  α = -∞
  for child in node:       # evaluation is identical for both players 
    α = max(α, -minimax(child, depth-1))
  return α

this algorithm assets that the opponents do his best moves (based on an evaluation function)

于 2013-02-19T19:09:50.470 に答える