6

チェスゲームの AI を作っています。

これまでのところ、Alpha-Beta Pruning Minimax アルゴリズムの実装に成功しました。これは次のようになります (ウィキペディアから)。

(* Initial call *)
alphabeta(origin, depth, -∞, +∞, TRUE)

function alphabeta(node, depth, α, β, maximizingPlayer)
    if depth = 0 or node is a terminal node
        return the heuristic value of node
    if maximizingPlayer
        for each child of node
            α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
            if β ≤ α
                break (* β cut-off *)
        return α
    else
        for each child of node
            β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
            if β ≤ α
                break (* α cut-off *)
        return β

これには時間がかかりすぎるため (すべてのツリーを 1 つずつ調べていく)、「履歴ヒューリスティック」と呼ばれるものに出会いました。

元の論文のアルゴリズム:

int AlphaBeta(pos, d, alpha, beta) 
{ 
    if (d=0 || game is over) 
        return Eval (pos);  // evaluate leaf position from current player’s standpoint 

    score = - INFINITY;     // preset return value 
    moves = Generate(pos);  // generate successor moves 

    for i=1 to sizeof(moves) do                // rating all moves 
        rating[i] = HistoryTable[ moves[i] ]; 
    Sort( moves, rating );                     // sorting moves according to their history scores 

    for i =1 to sizeof(moves) do { // look over all moves 
        Make(moves[i]); // execute current move 
        cur = - AlphaBeta(pos, d-1, -beta, -alpha); //call other player

        if (cur > score) {
            score = cur; 
            bestMove = moves[i];      // update best move if necessary 
        } 

        if (score > alpha) alpha = score;    //adjust the search window 
            Undo(moves[i]);                  // retract current move 

        if (alpha >= beta) goto done;        // cut off 
     } 

     done: 
     // update history score 
     HistoryTable[bestMove] = HistoryTable[bestMove] + Weight(d); 

     return score; 
}

したがって、基本的には、以前の「移動」のハッシュテーブルまたは辞書を追跡するという考え方です。

ここで、この「移動」が何を意味するのか混乱しています。それが文字通り単一の動きを指しているのか、それとも各動きの後の全体的な状態を指しているのかはわかりません.

たとえば、チェスでは、このハッシュテーブルの「鍵」は何であるべきでしょうか?

  1. 個々の動きは (Queen to position (0,1)) or (Knight to position (5,5))?

  2. それとも、個々の動きの後のチェス盤の全体的な状態ですか?

1 の場合、履歴テーブルに「移動」を記録するときに、他のピースの位置が考慮されていないと思いますか?

4

4 に答える 4

0

転置テーブルを使用すると、同じボードを複数回評価することを避けることができます。転置とは、異なる順序で移動を実行することで、同じボードの状態に到達できることを意味します。単純な例:

1. e4 e5 2. Nf3 Nc6
1. e4 Nc6 2. Nf3 e5

これらのプレイの結果は同じですが、異なる方法で到達しました。

http://en.wikipedia.org/wiki/Transposition_table

一般的な方法は、チェスの位置をハッシュする Zobrist ハッシングと呼ばれます。

http://en.wikipedia.org/wiki/Zobist_hashing

于 2013-11-13T03:16:12.840 に答える
0

私の経験から、履歴ヒューリスティックは、他の手法と比較してごくわずかな利点を生み出し、基本的な検索ルーチンには価値がありません。転置表を使うのと同じではありません。後者を実装したい場合でも、私はそれをお勧めしません。はるかに少ない労力で良い結果を生み出すテクニックは他にもたくさんあります。実際、効率的で正確な転置テーブルは、チェス エンジンでコーディングするのが最も難しい部分の 1 つです。

最初にプルーニングと順序付けヒューリスティックを試してみてください。そのほとんどは 1 行から数行のコードです。この記事では、そのような手法について詳しく説明しました。また、期待できるパフォーマンスの向上の見積もりも示しています。

于 2013-11-25T15:54:31.687 に答える