762alpha(旧President_X)アピール文書 2018年1月21日 V0.1 2018年2月11日 V0.2 天野史斎 ■ まえがき 762alphaは前回までPresident_Xと名乗っていたソフトの後継ソフトです。 というより、やろうとしていることと実現方針は全く同じで変わっていません。 過去2回はプログラムの完成度の問題でたいした成績を残せていませんが、今年はどうなりますやら なお過去のアピール文書はわざと実現方針をわかりにくくわかりにくくぼかして書いてみましたスミマセン;; 当ソフトの目的: 学習を自動化し、コンピュータ将棋プログラム開発への人間の介在を不用にする ひた隠しにしてきたキーワード:局面の場合分け ■ 問題提起 [既存のコンピュータ将棋] (特徴) 1. 優れたプレイヤー同士の棋譜を学習サンプルとする。 2. 学習サンプルで評価関数を調整する。 3. そのまま対戦時の局面評価にも使う。 (問題点) 1. 「優れたプレイヤー同士の棋譜」が必須である割に、「優れたプレイヤー同士の棋譜」とは何であるかがシステムの中で十分には規定されていない。 このため学習サンプル集めに人間(システムの外の存在)の関与が必要 2. ボナンザメソッドの結果を見てパラメータ数をスケールさせるのも人間(PPT、KKP + KPP、KPPP、KPPT、KKPT...人間がこれらを進化させている。 3. 異なる棋風(最善手(必勝手)が複数ある局面での選択の好み)のn駒間の関係ベースでのグローバルな合算が現実の調整手段で常に最良の結果をもたらすのか、確定的な結論は出ていなさげ ■ 提案する方法 [762alpha(および旧President_X)] (特徴) 1. 全力で戦って負けたケースの棋譜を学習サンプルとする。 2. 学習サンプルから局面の場合分けを学習し、評価関数の調整は場合毎に行う。 3. 対戦時の局面評価には軽量な評価関数を使う(1つの場合の中の形勢だけ説明できれば良い (既存手法の問題点を解決する手段) 1. 「全力で戦って負けたことを学習サンプルの条件とする」という明確な基準がシステム内にあることから、 学習サンプル集めが真に全自動化される。(「優れたプレイヤー同士の棋譜」が何であるかについて悩む必要が無い 2. 学習サンプルの数が増えるにつれ局面の場合分けが勝手に細分化することで、パラメータ数のスケール相当の作業も全自動で進行 3. 対戦時の評価関数は1つの場合の中の形勢だけ説明すれば良いので、個々の場合の中で異なる棋風の交絡は起き難い。 なお、学習サンプル集めは特徴1さえ満たせばオンライン学習でもバッチでも可能 ■ 局面の自然な場合分け 終盤の局面から場合分けを学ぶ。次の通り、終盤の局面は考えやすい。 1) 終盤の局面は、玉に睨みを利かせている駒(必要な駒)と、そうでない駒(不要な駒)からなる。 必要な駒の集合をキーにして分類すればまず間違い無い分類になる - 必要な駒は取られては困るので高い得点とし、不要な駒は捕られてもかまわないので低い得点とすれば、 勝利という目的に局面評価を自然に整合させられる。 2) 終盤より前の局面においては駒の要/不要がはっきりせず、うまい分類キーを見出せそうにない。 これは当方の終盤力が継続的に上昇し、「終盤の局面」の範囲が拡大し続ける ・・・(仮定1) という仮定の下で、考えないこととする。 ■ 終盤局面内の「必要な駒」の抽出 局面をbag of KPPsとみなしてベイジアンフィルタを適用する。 このときの勝利/敗北の教授信号(局面に対する勝利/敗北のラベル付け)は、 「局面別の勝敗推定」で述べる手段で推定して与える。 勝利にとって必要なn駒間の関係は、勝利時に頻出するため、対戦を重ねるにつれ勝利条件として認識されるようになる。 そうでないn駒間の関係は、勝利時と敗北時の両方に現れるため打ち消しあって無視されるようになる。 (言うまでも無く前者が「玉に睨みを利かせている」n駒間の関係である。 勝利と敗北の出現頻度が違っても、両方が1回以上現れたなら、ベイジアンフィルタは打ち消すべきものを打ち消してくれる。 あとは、n駒間の関係を駒の要不用判断に落とし込む。 すなわち、ベイジアンフィルタによる得点(log(P(当方の勝利|n駒間の関係(i,j,k))/P(当方の敗北|n駒間の関係(i,j,k)))を (駒の種類, 手番)毎に合計すれば、その値の大きさで(駒の種類, 手番)が「玉に睨みを利かせている」駒か否かワカル ※ 個人的にはベイジアンフィルタの上記性質は終盤局面の良し悪しを盤面の正規表現で表すという捨てたアイデアがリバイバルした感じでたいへん喜ばしい なお、特徴1の通り、当方法では当方の負けた対局からしか学習しないので、勝利の学習サンプルを得るために次の仮定をおく。 当方が全力で戦って負けたのであれば、相手の指し回しから学習すれば(同じ負け方が回避されることにより)強くなれる ・・・(仮定2) この仮定の下では、相手の指し回しは勝利の学習サンプルとみなせる。 ■ 局面の場合分け 局面ごとの勝利/敗北の教授信号が与えられる前提で(その手段は「局面別の勝敗推定」で述べる 局面(盤面)を適当な固定長ベクトルに変換 すれば、いかような手段でも教授信号に従い局面を分類できる。 分類器はここでは線形分離×決定木を使う。 盤面の適当な固定長ベクトルへの変換については… 前回は 玉に睨みを利かせている駒を知りたいのだから駒の座標に注目すべきである → 任意の座標変換を表現し得るベクトル表現にしよう(座標の差や平均が勝手に特徴になるハズだ と考えて変に複雑化してた; (置駒・持駒・上手/下手毎の駒の個数が変動するから、  盤全体の駒の座標は形勢判断にとって意味のある形ではたいへん固定長ベクトルにし難い ■■■■{■■■■}■{■■}■■■■■xx■■■■■■■■■ ■■■■■■■(■■■■, ■■)■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■■ ■ 局面別の勝敗推定 当方が全力で戦って負けたとして、投了付近では 1. +の評価値の期間が連続 2. -の評価値の期間が連続 3. 投了 という経過を辿るはずである。(頓死等、2の期間の長さが0手のケースもある。) 1の期間の当方手番局面は、当方が形勢判断を誤った局面と考えられる。 ただし、相手が優勢だったとする確証は乏しい。 (∵当方の形勢判断能力不足で相手が助かった可能性がある。 2の期間は、当方が全力で戦って評価値を覆せなかったのだから、相手が優勢だったのだとかなり確信を持って言える。 少なくとも仮定2の下では、相手手番を勝利の学習サンプルとみなして問題無い。 よって、2に属する局面の当方手番を「敗北」、相手手番を「勝利」とラベル付けして学習サンプルとする。 ■ 評価関数の調整 上記1の期間に属する当方手番局面を分類器で場合分けし、その場合に対応する評価関数の評価値を下げる調整を行う。 (ボナンザメソッド風にパラメータを振って探索し、評価値が下がるポイントを探す ■ その他 Futility purningやnull move purningのしきい値を自動調整するしくみを備えています。 (一定回数ごとにpurnせずに探索し、結果を蓄積→ヒストグラムの上側x %点をしきい値にする。 ■ F.A.Q. Q1. 最適化の行き届いた探索部を有するソフトに勝てますか(・∀・)? A1. 機械が全自動で行う局面の場合分けのたゆまぬ細分化とpurningしきい値の自動調整によりそのうち勝てる日も来るのではないでしょうか。   (対戦相手が開発に飽きるまで続ければ。) Q2. 評価関数はどういうものですか。 A2. 駒の移動の可能性は探索でもって確かめるとして、評価関数では 駒がそこに居る価値 駒の攻撃可能性 だけを評価します。 具体的には次の通り。 /// - 相手玉への利き /// - 相手玉の退路への利き (退路=相手玉の利きの中の空白マス) /// - 相手玉の守りへの利き (守り=相手玉の利きの中にいる相手の駒) /// - 相手玉の突破口への利き(突破口=相手玉の利きの中にいる当方の駒) /// - 相手玉に近い段への利き /// - 相手駒への利き /// - 自駒への利き /// - 相手からの利きに対する反撃可能性 /// - 相手からの利きに対する当方利きの優越 Q3. 最適化の行き届いた探索部を有するソフトにいつ勝てますか(・∀・)?? A3. わかりません。 Q4. Bag of KPPsとおっしゃいますがどのKPPを使うんですか(・∀・)??? A4. 普通のKPPです。すなわち、局面を - 当方の王K に対する当方の王以外の2駒PPの位置関係 - 相手の王K'に対する相手の王以外の2駒PPの位置関係 のbagとみなします。(駒台も位置に含める。また、PPはP=Pのケースも含む。) Q5. 普通のKPPでKPPTやKPP_KKPTに勝てるんですか(・∀・)???? A5. KPPベースのボナンザメソッドとBag of KPPsのベイジアンフィルタを比較すると、 パラメータの自由度が(前者)<<(後者)であるため、 ボナンザメソッドのKPPが、よりパラメータ数の多いKPP亜種に変更されたとしても、 後者で対抗できる余地があると考えています。 ボナンザメソッドは - 学習結果が探索結果として妥当となること という制約条件を含むことから、同じKPPが、 - ある親局面の子に現れるときは兄弟局面に対して評価値を最大化することに寄与 - 別の親局面の子に現れるときは兄弟局面に対して評価値を最大化「しない」ことに寄与 という2役を兼ねる必要があります。つまり、ボナンザメソッドにおいては、 任意のKPPは、兄弟局面として現れ得る大量の他のKPPとの関係において、 とれる値の範囲が(おそらくかなり厳しく)制限されます。 ということは、ボナンザメソッドのKPPおよびその亜種は、 独立パラメータ換算にすると見かけほど複雑なモデル表現ではない (特徴空間の次元<<1局面に現れるKPPの数)である可能性がある。 一方、ベイジアンフィルタは「勝った」「負けた」の事実の積み重ねを記録するだけで 機能するので、そのような制約はありません。 つまり、特徴空間の次元≒1局面に現れるKPPの数、と看做し得ます。 (去年のアピール文書で力説したことの言い換え。 ※ 実際には扱いやすく、意味のある固定長ベクトル化をする目的で制限した次元数にします Q6. いいことづくめに聞こえるBag of KPPsのベイジアンフィルタですが 流行っていないのはなぜか考えたことはありますか(・∀・)????? A6. ありません。 モデルに対して学習データがスパースなのはボナンザメソッドのKPPも ベイジアンフィルタも同じなので、挫折した先駆者が居たとしたら 平滑化に難儀されたんじゃないですかね(適当 Q7. Bag of KPPsのベイジアンフィルタと評価関数の関係が相変わらずよくわかりませんが(・∀・)?????? A7. Bag of KPPsのベイジアンフィルタの結果でもって f: {学習データ内の局面} → { 特徴ベクトル } という写像を改訂して特徴空間内での局面の場合分け能力をグレードアップしていき、 グレードアップされた場合分け能力でもって分けられた場合毎に 局面の評価と評価値の調整をやるということです。 Q8. ありがとうございます。たいへんよくわかりました。お薬を増しておきますね。 A8. いいえ。 以上