1. ホーム
  2. java

[解決済み] アルファ・ベータ・プルーニングを用いた反復深化の実装方法

2022-02-17 11:16:49

質問

Dots and Boxesをプレイするプログラムを書いているのですが、αBetaで考えた手を反復深化方式でヒューリスティック値に基づいて並べることで、時間効率を上げたいと考えています。基本的には、探索木に入り、反復するごとに深さを増していき、各ノードをalphaBetaで評価したいのです。各反復において、私がノードを考慮する順序は、前の反復からのノードのヒューリスティック値によって決定されます。しかし、これがどのように実装されるのか理解するのに苦労しています。どなたか、標準的なalphaBetaプログラムをどのように反復深化を用いた検索に適応させるか、疑似コードを提供していただけませんか?ありがとうございます。

どのように解決するのですか?

さて。 反復的な深化 を実装することはそれほど難しくありません。すでに検索を行う関数がある場合、それを alphaBetaAtRoot を一定の距離で検索するもので、距離1から順に繰り返し呼び出すだけです。

for(int distance = 1; distance < MAX_DISTANCE && !outOfTime(); distance++) {
  bestmove = alphaBetaAtRoot(position, distance);
}
play(bestmove);

しかし、重要なのは、このように 転置表 . そうでなければ、各検索がゼロの知識から始まるだけで、より良い手の順序の恩恵を受けることはできません。