An effective two-level proof-number search algorithm Mark H.M. Winands, Jos W.H.M. Uiterwijk, H. Jaap van den Herik はじめに 研究の背景と目的 探索方法 既存の探索アルゴリズム 提案する探索アルゴリズム 評価 まとめ 研究の背景と目的 二人零和有限確定完全情報ゲーム ・ 二人で対戦するゲーム 自分の有利 相手の不利 ・ いつかは必ず終わり，偶然の要素が入り込まない 理論的には完全な先読みを行うことで必ず勝つ事が可能 全ての可能性を探索する事は不可能 探索木を構築し可能な範囲で何手か先まで読み その中から最善手を選択する 研究の背景と目的 ゲーム木 自分・相手・自分・相手・自分・‥ といった順に可能な指し手を 枝別れするよう広げて構築 それぞれの局面を数値化 ・ 値が大きいほど自分が有利 ・ 値が小さいほど自分が不利 構築したゲーム木の探索方法が重要 目的 効率の良い新しい探索手法 PDS-PNの提案 探索方法 ブラインド探索 （単純な探索 ） 予備知識を使わずに探索を行う － 深さ優先探索 － 幅優先探索 ヒューリスティック探索 何らかの予備知識を使い効率よく探索を行う － 最良優先探索 幅優先探索のような振る舞いをする 深さ優先探索 枝を進めるかぎり掘り進めて行き詰ったら次の枝を調べる方法 利点 Ｓ Ａ Ｃ 探索が終了した部分の木を メモリに記憶する必要がなく メモリを節約できる Ｂ Ｄ Ｅ Ｆ ＧＯＡＬ Ｇ Ｈ 欠点 全ての枝を末端まで調べる ので解を見つけるのが遅い 深さ優先探索 枝を進めるかぎり掘り進めて行き詰ったら次の枝を調べる方法 利点 Ｓ Ａ 探索が終了した部分の木を メモリに記憶する必要がなく メモリを節約できる Ｂ Ｅ Ｆ ＧＯＡＬ 欠点 全ての枝を末端まで調べる ので解を見つけるのが遅い 幅優先探索 同じ深さの節点を調べ終わってから次の深さに進む方法 利点 Ｓ Ａ Ｃ Ｂ Ｄ Ｇ 効率よく見つける事が 出来る 欠点 探索木全体をメモリに記憶 Ｆ させる必要があり、メモリの ＧＯＡＬ 使用量が大きい Ｅ Ｈ 既存の探索アルゴリズム 最良優先探索 • Proof-number Search (PN探索) • PN2探索 深さ優先探索 • PN＊探索 • Proof-number and Disproof-number Search (PDS) 証明数・反証数 ヒューリスティックな評価関数を用いるよりも さらに探索を効率的に行うことができる概念 例） 詰め将棋の場合 証明数 局面を詰むために必要な先端 局面の個数 値が小さいほど詰みやすい 反証数 局面が不詰めである事を示す ために必要な先端局面の個数 値が小さいほど不詰めを示し やすい 攻め手側は証明数が最小の手を選ぶことが重要であり、 相手側は反証数が最小の手を選ぶことが重要である PN探索 既存の探索アルゴリズム 特徴 • 最良優先探索 • 証明数・反証数を用いて評価 • 全ての木をメモリに記憶させる 必要がある • メモリ不足になると探索終了 探索を進めるにしたがって 記憶するデータの量が 大きく増加していく PN2探索 既存の探索アルゴリズム 特徴 • PN探索を2段階に分けて行う • 最良優先探索 • PN探索よりメモリ使用が少ない • メモリ不足になると探索終了 木の根からある深さまで 1st PN探索を行う 1st PN探索 PN2探索 既存の探索アルゴリズム 特徴 • PN探索を2段階に分けて行う • 最良優先探索 • PN探索よりメモリ使用が少ない • メモリ不足になると探索終了 1st PN探索 木の根からある深さまで 1st PN探索を行う 木の葉を親とした 2nd PN探索を行う 2nd PN探索 PN2探索 既存の探索アルゴリズム 特徴 • PN探索を2段階に分けて行う • 最良優先探索 • PN探索よりメモリ使用が少ない • メモリ不足になると探索終了 1st PN探索 木の根からある深さまで 1st PN探索を行う 木の葉を親とした 2nd PN探索を行う 探索済みの2nd PN探索の データはメモリに記憶しない 2nd PN探索 PN*探索 既存の探索アルゴリズム 特徴 ・深さ優先探索 ・最良優先探索のような振る舞い ・全ての木をメモリに記憶させる必要がない ・PN探索よりも解を見つけるのが遅い ・証明数・反証数を対等に扱っていない 特徴 ・深さ優先探索 ・証明数・反証数を対等に扱っている ・全ての木をメモリに記憶させる必要がない ・PN探索よりも解を見つけるのが遅い PDS 既存の探索アルゴリズム 特徴 ・深さ優先探索 ・最良優先探索のような振る舞い ・全ての木をメモリに記憶させる必要がない ・PN探索よりも解を見つけるのが遅い ・証明数・反証数を対等に扱っていない 特徴 ・深さ優先探索 ・証明数・反証数を対等に扱っている ・全ての木をメモリに記憶させる必要がない ・PN探索よりも解を見つけるのが遅い 提案する探索アルゴリズム PN2探索のような 2レベルの探索 1stレベル‥‥‥PDS 2ndレベル‥‥‥PN探索 PDS－PN 探索 PN PDS ・深さ優先探索 効率的なメモリの利用 ・最良優先探索 解を速く見つけることが可能 PDS よりも速く解を見つけることが出来て PN探索のようなメモリ不足による探索終了に陥らない探索 PDS-PN 1st PDS 木のルートからある深さまで PDSを行い，それ以降の深さは PN探索を行う PDSで末端の葉がPN探索の ルートとなる 2nd PN 探索 アルゴリズムの比較 探索方法 PN2 最良優先 PDS 深さ優先 PDS-PN 深さ優先 最良優先 速さ メモリ使用 1stレベル探索： PDS 証明数・反証数を閾値として用いて，閾値の値を 1ずつ増やして探索の範囲を広げる 閾値 探索する深さの目安 A B C 1stレベル探索： PDS 証明数・反証数を閾値として用いて，閾値の値を 1ずつ増やして探索の範囲を広げる 閾値 探索する深さの目安 A B D E C F G 1stレベル探索： PDS 証明数・反証数を閾値として用いて，閾値の値を 1ずつ増やして探索の範囲を広げる 閾値 探索する深さの目安 解を見つける 可能性が低い A B 一つ上の親へ D E C F G H I J 2ndレベル探索 ：PN • 最良優先探索アルゴリズム － 有望なノードから優先的に選択する － 葉の選択，拡張を繰り返して行う • 有望なノード選択に証明数・反証数を用いる 通常の PN探索 • 1stレベル探索木の大きさで木の大きさが決まる • 探索するノードの数を関数によって制限 • 探索済みのノードは削除される PN探索と 異なる点 2ndレベル探索 ：PN • 1stレベル探索木の大きさで木の大きさが決まる • 探索するノードの数を関数によって制限 • 探索済みのノードは削除される 効率的にメモリを利用できる PN探索と 異なる点 PDS-PN PDS PN 探索 PN 探索 探索済みの部分の木は削除!! PDS-PN 効率的なメモリ利用 PDS PN 探索 PN 探索 PDS-PN 探索方法 PN2 最良優先 PDS 深さ優先 PDS-PN 深さ優先 最良優先 速さ メモリ使用 評価 Lines Of Action (LOA) 二人零和ゲームであり，同列にある駒数によって移動できる マスの数が決まり，味方の駒をすべて連結すると勝ち いくつかの勝ちパターンがセットされ たLOAを以下のアルゴリズムで解き その比較を行う • PN2 • PDS • PDS-PN 評価結果Ⅰ: 時間 457の解を探索した場合 (探索ノードの限界：50,000,000) Total time(ms) Total Time ｘ10 3 ms ・ PDSより速く解を見つける ことが出来た ・ PN2 を上回る事は 40,000 出来なかった 35,000 30,000 PN2 25,000 20,000 15,000 PDS 10,000 5,000 0 PN22 PN PDS PDS PDS-PN PDS-PN PDS-PN 評価結果Ⅱ: メモリ セットされた勝ちパターン：286 (メモリ使用が多い場合) 探索ノードの限界：500,000,000 Algorithm No.of positions solved (286) PN2 265 PDS-PN 276 PN2 よりも多くの解を 見つける事が出来た メモリ使用が多い場合 PDS－PN の方が効果的 PN2 PDS-PN まとめ 目的 効率の良い新しい探索手法 PDS-PNの提案 PDS－PN PDS (深さ優先探索) メモリ限界による探索終了がない PN (最良優先探索) PDSよりも解を見つけるのが速い 結論 ・ PDSよりも速く解を見つける事ができた ・ メモリ限界による探索終了はなかった ・ メモリ使用が多い場合、 PN2よりも効果的である 評価結果Ⅰ: 時間 457の解を探索した場合 (探索ノードの限界：50,000,000) TotalTotal No. of nodes No. of nodes ｘ10 6 2,000 Total time(ms) Total Time 3 ｘ10 ms 40,000 1,800 35,000 1,600 30,000 1,400 25,000 1,200 1,000 20,000 800 15,000 600 10,000 400 5,000 200 0 0 PN PN2 2 PDS PDS PDS-PN PDS-PN PN22 PN PDS PDS ・ PDSよりも速く解を見つけることが出来た ・ PN2 を上回る事が出来なかった PDS-PN PDS-PN 評価結果Ⅰ セットされた勝ちパターン：488 探索ノードの限界：50,000,000 Algorithm No.of positions solved (488) 371 positions Total No. of nodes Total time(ms) αβ 382 2,645,022,391 33,878,642 PN2 470 505,109,692 3,642,511 PDS 473 239,896,147 16,960,325 PDS-PN 467 924,924,336 5,860,908 評価結果Ⅱ セットされた勝ちパターン：488 探索ノードの限界：500,000,000 Algorithm No.of positions solved (488) 471 positions Total No. of nodes Total time(ms) PN2 479 2,261,482,395 13,295,688 PDS-PN 483 4,362,282,235 23,398,899 評価結果Ⅲ セットされた勝ちパターン：457 探索ノードの限界：50,000,000 Algorithm Total No. of nodes Total time(ms) PN2 1,275,155,583 9,357,663 PDS 498,540,408 36,802,350 1,845,371,831 11,952,086 PDS-PN ・ PDSよりも速く解を見つけることが出来た ・ PN2 を上回る事が出来なかった 評価結果Ⅳ セットされた勝ちパターン：286 探索ノードの限界：500,000,000 ※勝ちパターンが少なく解を見つけるのが難しい場合 Algorithm No.of positions solved (286) 255 positions Total No. of nodes Total time(ms) PN2 265 10,061,461,685 57,343,198 PDS-PN 276 16,685,733,992 84,303,478 探索ノード・時間は費やしているがPDS－PNは PN2 よりも多くの解を見つける事が出来た 問題が難解な場合 PDS－PN ＞ PN2 PDS ：1stレベル探索 証明数・反証数に閾値を設定 以下の条件を満たすまで深く掘り続ける • 証明数，反証数の値が閾値以上になった場合 • 解を見つけた場合 証明数の閾値(pnt) 反証数の閾値(dnt) 証明数（pn） 反証数(dn) 閾値が増加する条件 pn dn pn dn pnt dnt Proof-likely disProof-likely pnt dnt PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt 証明数・反証数の閾値を設定する pnt dnt Proof-likely disProof-likely 1 1 1 A 1 PDS ：1stレベル探索 閾値が増加する条件 pnt dnt pn dn pn dn disProof-likely 1 ノードの拡張 1 証明数・反証数の計算法 (自分の盤の場合) 1 1 1 子の反証数 2 の合計 1 1 1 1 A 2 証明数・反証数の閾値を設定する 子の証明数 の最小値 pnt dnt Proof-likely B 1 1 C 1 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt disProof-likely 1 証明数・反証数の値が 閾値以上なので探索終了 1 1 A 2 証明数・反証数の閾値を設定する ノードの拡張 pnt dnt Proof-likely 1 B 1 1 C 1 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt disProof-likely 1 証明数・反証数の値が 閾値以上なので探索終了 1 1 A 2 証明数・反証数の閾値を設定する ノードの拡張 pnt dnt Proof-likely 1 B 1 1 C 1 証明数・反証数の値をハッ シュ表に格納し木は削除さ れる PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt ハッシュ表に格納されてある証明数・ 反証数の値を閾値に設定 Proof-likely disProof-likely 1 2 1 A 1 pnt dnt PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt ハッシュ表に格納されてある証明数・ 反証数の値を閾値に設定 証明数・反証数の比較を行い閾値 を増加させる Proof-likely disProof-likely 2 1 2 1 A 1 pnt dnt PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt Proof-likely disProof-likely 2 2 1 A 2 ハッシュ表に格納されてある証明数・ 反証数の値を閾値に設定 証明数・反証数の比較を行い閾値 を増加させる ノードの拡張 pnt dnt 1 B 1 1 C 1 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt Proof-likely disProof-likely 2 2 1 A 2 ハッシュ表に格納されてある証明数・ 反証数の値を閾値に設定 証明数・反証数の比較を行い閾値 を増加させる ノードの拡張 pnt dnt 1 B 1 1 C 1 証明数・反証数の値が閾値以上で ないので探索続行 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt 子の閾値を証明数・反証数に等しく設定 Proof-likely disProof-likely pnt dnt 2 2 1 A 2 1 1 B 1 1 1 C 1 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt Proof-likely disProof-likely 2 2 1 A 2 子の閾値を証明数・反証数に等しく設定 2 Proof-likely， disProof-likelyのチェック pnt dnt 1 1 B 1 1 1 C 1 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt disProof-likely 2 2 1 A 2 子の閾値を証明数・反証数に等しく設定 2 1 B 2 1 Proof-likely， disProof-likelyのチェック ノードの拡張 pnt dnt Proof-likely 1 D 11 E 1 C 1 1 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt disProof-likely 2 2 1 A 2 子の閾値を証明数・反証数に等しく設定 2 1 B 2 1 Proof-likely， disProof-likelyのチェック ノードの拡張 証明数・反証数の値が 閾値以上なので探索終了 pnt dnt Proof-likely 1 D 11 E 1 C 1 1 PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt disProof-likely 2 2 1 A 2 子の閾値を証明数・反証数に等しく設定 2 1 B 2 1 Proof-likely， disProof-likelyのチェック ノードの拡張 証明数・反証数の値が 閾値以上なので探索終了 pnt dnt Proof-likely 1 D 11 E 1 C 1 1 証明数・反証数の値をハッ シュ表に格納し木は削除さ れる PDS ：1stレベル探索 閾値が増加する条件 pn dn pn dn pnt dnt Proof-likely disProof-likely 子の閾値を証明数・反証数に等しく設定 Proof-likely， disProof-likelyのチェック pnt dnt 2 2 1 A 2 2 1 B 2 1 1 C 1 ノードの拡張 証明数・反証数の値が 閾値以上なので探索終了 証明数・反証数の値が閾値以上では ないので、探索を続行 PDS ：1stレベル探索 証明数・反証数を閾値に設定 以下の条件を満たすまで深く掘り続ける • 証明数，反証数の値が閾値以上になった場合 • 解を見つけた場合 A B C PDS ：1stレベル探索 証明数・反証数を閾値に設定 以下の条件を満たすまで深く掘り続ける • 証明数，反証数の値が閾値以上になった場合 • 解を見つけた場合 閾値よりも小さい場合 探索続行 A B D E C F G PDS ：1stレベル探索 証明数・反証数に閾値を設定 以下の条件を満たすまで深く掘り続ける • 証明数，反証数の値が閾値以上になった場合 • 解を見つけた場合 閾値以上の場合 探索終了 A B 一つ上の親へ D E 閾値よりも小さい場合 探索続行 C F G H I J ルートまで返って解が求まらない場合 閾値を設定し直して再探索
© Copyright 2024 ExpyDoc
