日時：2006年 7月 6日(木) 18:30 から
場所：東京大学 本郷キャンパス 工学部14号館 5階 501
話者：
美添 一樹 (東京大学大学院情報理工学系研究科コンピュータ科学専攻)
話題：
DFPN Driven Lambda Search Algorithm の囲碁捕獲問題への適用
概要：
Lambda Search AlgorithmとDFPN Search Algorithmは、異なる特徴を持つ
探索アルゴリズムである。この二つのアルゴリズムの相互の欠点を補う
性質のある探索アルゴリズムとしてDFPN Driven Lambda Search Algorithmを
提案する。
Lambda Search AlgorithmはLambda Orderに着目した探索アルゴリズム
である。Lambda Order とは、囲碁では手数、将棋では速度と呼ばれる
もので、目的を達するために必要な自分の着手数と相手の着手数の差で
ある。Lambda Searchは他の何らかの探索アルゴリズムと組み合わせて
実装されるが、過去にはαβ法との組み合わせのみが研究されている。
DFPN Search Algorithmは証明数/反証数を用いたゲーム木探索アルゴリズム
である。世界最強の詰将棋ソルバー及び詰碁ソルバーが、DFPNを用いて
作成されるなど、大きな成功を収めている。
DFPN は自動的に証明/反証が簡単そうな手から探索する「頭の良い」
アルゴリズムであるが、その反面、人間がヒューリスティックを足して
性能向上を図ることが、αβ法と比較して難しい。
我々は、DFPN Driven Lambda Search Algorithmを実装し、囲碁の捕獲
探索に適用し性能を測定した。
出席者：27名
伊知地宏（ラムダ数教研）、長慎也（一橋大）、駒澤忠良（CGF）、石畑清（明治大）、 和田英一（IIJ）、馬淵茂（コア・インタラクティブ）、清水智弘（富士通研）、 清愼一（富士通ソーシアルサイエンスラボラトリ）、繁富利恵（産総研）、 山口文彦（東京理科大）、加藤英樹、副田俊介、笹田耕一、金子知適、横山大作、 筧一彦、田中哲朗、三輪誠、今福健太郎（東京大）、滝沢洋平、新沢剛、多田好克、 李俊、卜部昌平、寺田実、三好晴樹、丸山一貴（電気通信大）
Q1, \lambda^n_a 等は局面に対して定義されるものなのか？
また，それらの値は二値に定まるのか？
A1, そのとおり。正確には探索の結果として定まる。
Q2, 1手、あたりをやってから「シチョウ・ゲタ」をやるような場合はどうなるのか。
A2, lambda^1 探索の中では、シチョウしか探索しないのでゲタの可能性はは無視する。
Q3, オセロの1カ所しか打てないのはZugZwangに入るのか。
A3, 入ることもある。
Q4, DFPNはDepth FirstというよりはBreadth Firstのように見えるが。
A4, ある時点での閾値内ではdepth-firstである、ただし多重反復深化をしている。
Q5, transposition tableで全部覚えるのとメモリ使用量は違うのか。
A5, 重要なnodeを優先して覚えるテクニックが有効なので、だいぶ違う。
Q6, (無限大 - 1) は気持ち悪い…。
A6, 実装としては MAX_INT の半分か1/4を使用している、表記上の問題なので
ご容赦いただきたい。
Q7, lambda moveの定義を緩和しているとは何か。
A7, 低いlambda orderでの証明/反証の結果が不明なうちは、lambda moveとみなす
ようにしている
Q8, lambda^nの証明・反証を待たずにlambda^{n+1}を探索できる、とは本当に長所か。
A8, 問題にもよるのだが、反証に非常に時間がかかるケースは特に詰め将棋などで多い。
Q9, 各問の \lambda order について記録しているか？
また，\lambda-move の定義を緩和すると，しない場合と比べて出力される答えの
\lambda order が変わる可能性があると思うが，
実際にそのようなケースは存在したか？
A9, lambda orderは記録している。
定義を緩和したことで、可能な最小のlambda orderでない解が得られることは
実際にあった。
Q10, \lambda order の lower bound がわかる場合に利用して...とあったが，
具体的にはどのような場合にそれがわかるのか？
A10, 囲碁の捕獲探索ではダメの数によって明らかに分かる。
Q11, コウがあると大変じゃない？
A11, コウに対処する方法はいくつか研究があり、それほど大変ではない。
ちなみに発表時点ではコウは無視している。
（補足: 局所的なコウダテを打ち合った結果の勝敗を求める）
Q12, 正解率のところ：subsetというわけではないよね。
A12, 候補手の範囲を広げると、正しく解けるようになる問題もあるが、時間切れで
解けなくなる問題もある。なのでsubsetではない。
Q13, lambda DNPN search：pseudo nodeでlambda_1の中にlambda_0が含まれるのでは。
別々に計算しているのか。
A13, hash tableを利用しているので、低いlambda orderでの探索の情報は自動的に
高いorderでも利用される。なので別々ではない。
Q14, 詰め将棋にDFPNを利用するときに、合流するノードのせいで証明数を
2重にカウントしてしまうことがあるが、どう対処しているか。
A14, ルートからの手数を見て、最短手数が小さい子ノードの証明数は加算しない
方法を使っている。
Q15, (Q14に便乗)将棋でやるような，DAG による二重カウントはやっているか？
A15, 行っていない。
Q16, 知識で探索する枝を減らす、というのがいいのでは
（実質的には同等の手が複数ある場合、順序を1通りにするとか）
A16, できれば良いのはもちろんそのとおり。しかし判定するのは難しいかもしれない。
Q17, df-pn+ で言うところの cost 関数に相当するものは使っているか？
A17, Hとcostの併用も実験したが、Hのみの場合の性能が良かったので
本発表ではcostには触れていない。
Q18, 攻め合いのときのダメの種類を分類しているか？
A18, まったく分類していない。分類するプログラムの研究もあるが、
探索の中で使うには遅い。
Q19, 1手で終わるところは探索ではなく知識の方がよいのでは
A19, 探索を行わずに攻め合いの勝敗判定をするプログラムはあるが、
どこでその知識を使うかが問題。探索の中で使うには遅すぎる。
Q20, 最後の実験で pn/dn の初期値をいじることで，
小さい order から探索をするような実験をしているようだが，
そのような実験方法では副作用が大きいのでは？
A20, 大きいかも知れないが、今回の実験の範囲では不明。