MTD(f)

MTD(f)は、アルファベータゲームツリー探索アルゴリズムで、初期探索境界として「ゼロウィンドウ」を使用し、中間探索結果を再利用するためにメモリ (通常は転置テーブル) を使用するように修正されています。MTD(f) は、MTD(n,f) の短縮形であり、ノードが「n」、値が「f」の Memory-enhanced Test Driver を表します。^[1]このパラダイムの有効性は、初期推測が適切であることと、最終的なミニマックス値が推測の周囲の狭いウィンドウ内にあるという仮定 (ルートからの検索の上限/下限になる) に依存します。メモリ構造は、他の場所で決定された初期推測を保存するために使用されます。

MTD(f) は 1994 年に導入され、チェス、チェッカー、オセロ、その他のゲームオートマトンでそれまで主流だった検索パラダイムであるNegaScout (PVS) に取って代わりました。 ^[^{引用が必要}^]

起源

MTD(f) は、Aske Plaat、Jonathan Schaeffer、Wim Pijls、Arie de Bruin が執筆したアルバータ大学の技術レポートで初めて説明され、 ^[2]後に 1994/1995 年の ICCA Novag 最優秀コンピュータチェス出版物賞を受賞しました。アルゴリズム MTD(f) は、1979 年に George Stockman が発明した最良優先探索アルゴリズムであるSSS*アルゴリズムを理解するための研究努力から作成されました。 ^[3] SSS* は、alpha-beta が転置テーブルなどのストレージを使用する場合、一連の Alpha-beta プルーニング|alpha-beta 呼び出しと同等であることがわかりました。

MTD(f) という名前は、メモリ強化テストドライバーの略で、ゼロウィンドウ検索を実行するJudea Pearlのテストアルゴリズム^{[引用が必要]}を参照しています。MTD(f) については、Aske Plaat の 1996 年の博士論文で詳しく説明されています。^{[引用が必要]}

ゼロウィンドウ検索

「ゼロウィンドウ」検索は、上限と下限が同一であるか、または 1 単位異なるアルファベータ検索であり、戻り値は境界外になることが保証されます (または、非常に幸運な場合には、境界と等しくなります)。

MTD(f) は、事前に決定された「良い」境界 (つまりベータ) で、ゼロウィンドウのアルファベータ検索のみを実行することで効率を引き出しています。MTD(f) では、AlphaBeta は上限または下限で失敗し、それぞれミニマックス値の下限または上限を返します。ゼロウィンドウ呼び出しではカットオフが多くなりますが、返される情報は少なく、ミニマックス値の境界のみになります。ミニマックス値を見つけるために、MTD(f) は AlphaBeta を何度も呼び出し、それに収束して最終的に正確な値を見つけます。転置テーブルは、以前に検索されたツリーの部分をメモリに保存して取得し、検索ツリーの部分を再探索するオーバーヘッドを削減します。^[4]

擬似コード

関数MTDF(root, f, d)は
    g := f
    上限:= +∞
    下限:= −∞

    lowerBound < upperBoundの場合
        β := max(g, 下限値 + 1)
        g := AlphaBetaWithMemory(root, β − 1, β, d)
        g < βならば
            上限:= g
        それ以外
            下限:= g

    戻るg

f: 最適な値の最初の推測。良いほど、アルゴリズムの収束が速くなります。最初の呼び出しでは 0 になる可能性があります。
d: ループする深さ。反復深化深さ優先探索は、MTDF()増分しながら複数回呼び出しd、前回の最良の結果を提供することで実行できますf。^[5]

AlphaBetaWithMemory以前の結果をキャッシュする Alpha Beta Search のバリエーションです。

説明

MTD(f)はツリーのルートからゼロウィンドウ検索を呼び出します。MTD(f)は効率的に実行するために転置テーブルに依存します。^[6]

ゼロウィンドウ検索は、ワイドウィンドウ検索よりも早くカットオフに達します。したがって、ワイドウィンドウ検索よりも効率的ですが、ある意味では、寛容性も低くなります。ただし、奇数/偶数の変動が大きく、評価関数がきめ細かいエンジンの場合、検索ウィンドウが広いほど寛容性は高くなります。このため、一部のチェスエンジンはMTD(f) に切り替えていません。

チヌーク（チェッカー）、フェニックス（チェス）、キーアノ（オセロ）などのトーナメント品質のプログラムを使用したテストでは、MTD(f)アルゴリズムは他のすべての検索アルゴリズムよりも優れたパフォーマンスを示しました。 ^[4]ベストノードサーチなどの最近のアルゴリズムは、MTD(f)よりも優れていると示唆されています。

参考文献

^ ヨハネス・フュルンクランツ、ミロスラフ・クバット（2001年）。『ゲームを学ぶ機械』。Nova Publishers。95～97ページ。ISBN 978-1-59033-021-0。
^ 「実際のゲームに対する MTD-f の適応戦略」東京農工大学柴原克己他
^ Teofilo Gonzalez、Jorge Diaz-Herrera、Allen Tucker (2014 年 5 月 7 日)。コンピューティングハンドブック、第 3 版: コンピュータサイエンスとソフトウェアエンジニアリング。CRC プレス。pp. 38– 。ISBN 978-1-4398-9853-6。
^ ab Plaat、Aske;ジョナサン・シェーファー。ヴィム・ピルス。アリー・デ・ブルーイン（1996年11月）。「ベストファースト固定深さミニマックスアルゴリズム」。人工知能。87 (1-2): 255-293。土井：10.1016/0004-3702(95)00126-3。
^ "Aske Plaat: MTD(f)、新しいチェスのアルゴリズム".
^ 奇偶効果が顕著なプログラムで MTD(f) を使用する場合、ルートのスコアは偶数の検索深度では高くなり、奇数の検索深度では低くなります。そのため、f に別の値を使用して、検索をできるだけミニマックス値に近いところから開始することをお勧めします。そうしないと、特に細粒度評価関数の場合、検索でミニマックス値に収束するまでにより多くの反復が必要になります。

外部リンク

MTD(f)アルゴリズムの説明

[FürnkranzKubat2001-1] ヨハネス・フュルンクランツ、ミロスラフ・クバット（2001年）。『ゲームを学ぶ機械』。Nova Publishers。95～97ページ。ISBN 978-1-59033-021-0。

[2] 「実際のゲームに対する MTD-f の適応戦略」東京農工大学柴原克己他

[GonzalezDiaz-Herrera2014-3] Teofilo Gonzalez、Jorge Diaz-Herrera、Allen Tucker (2014 年 5 月 7 日)。コンピューティングハンドブック、第 3 版: コンピュータサイエンスとソフトウェアエンジニアリング。CRC プレス。pp. 38– 。ISBN 978-1-4398-9853-6。

[ai-4] Plaat、Aske;ジョナサン・シェーファー。ヴィム・ピルス。アリー・デ・ブルーイン（1996年11月）。「ベストファースト固定深さミニマックスアルゴリズム」。人工知能。87 (1-2): 255-293。土井：10.1016/0004-3702(95)00126-3。

[5] "Aske Plaat: MTD(f)、新しいチェスのアルゴリズム".

[6] 奇偶効果が顕著なプログラムで MTD(f) を使用する場合、ルートのスコアは偶数の検索深度では高くなり、奇数の検索深度では低くなります。そのため、f に別の値を使用して、検索をできるだけミニマックス値に近いところから開始することをお勧めします。そうしないと、特に細粒度評価関数の場合、検索でミニマックス値に収束するまでにより多くの反復が必要になります。