GA将?開発日記~王理のその先へ~

ネタ勢最強を目指して絶賛開発中。

アイデアメモ

「反省会モード(仮称)」のアルゴリズムについて

昨夜思い付いたアイデアで、ひょっとしたら使えるかも? という感じのがあるので、メモがてら書いてみます。 まず、前提として「自己対局での強化学習を行う」事とします。 学習開始直後は、初期局面から自己対局&パラメータ修正を繰り返しつつ、「優勢だと…

カルマンフィルタを用いた強化学習

Kalman Temporal Differencesという、TD法とカルマンフィルタを組み合わせた手法は存在する様なのですが、方策勾配法でも同様の事が出来ないかと検討中。カルマンフィルタの基礎作者: 足立修一,丸田一郎出版社/メーカー: 東京電機大学出版局発売日: 2012/10/…

個々の駒の位置評価に対するQ学習の適用

前にもブログに書いたか実装したかした覚えは有るんですが、見つからなかったので再度書いてみる。 んで、やる事。例えば駒の位置評価*1を考える。 この時、「先手2四歩の価値」は「max(先手2三歩の価値,先手2三と金の価値)」に近い(はず)。 なので、パ…

囲いの駒の評価をリトライ

第25回選手権バージョンのGA将!!!!!!!!の弱点の一つは「ちゃんと囲えない」事なので、そこをなんとかしようかと。 んで、まず囲いの駒の認識方法は以前書いたものでそこそこの精度が出そうなので、それを流用。 次に、認識した「囲い」の評価方法。以前は駒…

上の続き

SR-PGLeafでは予測報酬(≒特定局面から先の勝率)が計算出来るから、それを利用する前提ならもうちょっとアルゴリズムを簡略化出来るかも。 評価関数パラメータを初期化する。 以下を無限に繰り返す。 自己対局で1局指す。 棋譜の各局面の予測勝率を計算する…

局面の予測勝率を基準とする、学習対象局面の選別

現在のGA将!!!!!!!!では、自己対局で生成した全ての局面を学習対象としています。 ただ、これは結構非効率的なやり方で、無駄な学習対象局面が存在する為に、深い探索と組み合わせた学習が困難です。 という訳で、初期局面から終局直前までの各局面を対象に…

囲いの認識及びその評価方法

以前どっかで書いた覚えがあるんですが、探しても見つからなかったので再度書きます。 まず、「囲いの駒」の認識アルゴリズム。先手の囲いを対象としますので、後手の時は適当に先後反転してやればOKです。 先手玉が利いている先手の駒は、囲いの駒である。 …

GA将!!!!!!!! エレガント詰めルーチン

「Labyrinthus辱め詰め」に触発されて、面白い詰将棋ルーチンを作れないかと検討中。 んで、風呂の中でザックリと構想だけねってみました。 可能な限り長手数での勝ちを選ぶ。 自分の駒(盤上・駒台とも)が少ないほど加点。 自玉と敵玉が近いほど加点。 ス…

評価値計算にシグモイド関数を用いる、非線形評価関数の実装

えー、上で書いた「もう一つの課題局面」から…なんですが、どの対局だったか忘れちゃったんで局面図無しです。 言い訳すると、一次・二次合わせて16戦してるんで、ログが埋もれても仕方ない…訳は無いんですが。あと、ひょっとしたら練習対局だった可能性もあ…

駒割の価値の分解

今のGA将のロジックだと、駒割は下記の様になっています。 歩〜飛車はその駒の価値単独のパラメータがある。 と歩〜成銀は「金とと金(OR 成香 OR 成桂 OR 成銀)の差分」をパラメータとして持ち、これに金の価値を足したのが成駒の価値。 馬・龍は「角(飛…

評価値の展開による局面評価の高速化

だれでもやってる当然の事かもしれませんが、軽くググってみても出て来なかったんで書いてみます。 まず、現在のGA将!!!!!!の駒割・絶対位置評価関連の評価項目は下記の通りです。 駒割(盤上の駒) 駒割(持ち駒) 筋・段個別の絶対位置評価 絶対位置評価 …

前提条件付きの探索って出来ないかなぁ

えー、まずは自分の指した将棋から、課題になっている局面図の一部を抜粋。"v"付きが後手の駒です。 9 8 7 6 5 v玉 一 v金 二 v角 v金 三 飛 四 角 五 先手の持駒は香車が一枚、後手は持ち駒無しです。手番は先手。 んで、ここでまず浮かんだのが8四香です…

SVRを使用したFutility Pruningのマージン決定

動的なマージンを用いるFutility Pruningという論文があるんですが、選手権後にこれを実装しようかと検討中。 んで、問題はマージン決定のフェーズと、決定したマージンを使用して探索するフェーズに分けなきゃいけないって所ですね。 今のGA将の学習方式だ…

進行度を利用した評価関数のパラメータ学習に関する、新しいアイデア

芝浦将棋Jr.の五十嵐先生と相談中で、ひょっとしたら論文ネタになるかもしれないので、ザクっと書いてみます。 まず、自己対戦の結果から強化学習(TDLeaf(λ)やPGLeaf)で学習する際に一番問題になるのは、序盤〜中盤の学習が上手く行かない事です。 これは…

昨夜の続き

http://d.hatena.ne.jp/Gasyou/20121030/1351612797 酔いが覚めてみると一つ見落としていたのに気付きました。合議クライアントの多様性が失われる危険性があります。 まず、合議で強くする為に必要なのは、「各クライアントの正解率を高める」事では無く「…

合議における内部局面の最善手共有によるReduction抑制

酔った勢いで書いてるんで色々読み抜けとか考慮漏れとかありそうですが、思い付いたんでとりあえず書いてみます。 まず、現在のGA将の思考ルーチンは全幅探索*1+LMRの部分と、全幅末端での2段階静止探索になっています。 で、LMRで重要な手を短縮してしまう…

面白そうな論文見つけた

http://aiwww.main.ist.hokudai.ac.jp/contents/research/activities/thesis/M_23_kimura.pdf 強化学習において、いきなりゴール(将棋の場合だと勝敗)に辿り着くのは難しいので、途中にサブゴールを設定し、そこに到達すると報酬を与えるという事は結構さ…

持ち駒の種類による評価項目

アイデアって程ではないんですが、「持ち駒の種類を評価すれば、ちょっとは強くならないかな」と思ったもので。 アルゴリズムとしては2つ考えていて、1つは「持ち駒が1種類だけならx点、2種類ならy点…」って感じの評価。要するに、色々持っていればそれだけ…

相手の残り思考時間を基準とした、終盤の思考時間制御

選手権時に参加者の人と話してて出たアイデアなんですが、終盤の「1秒将棋モード」を相手の思考時間を考慮する事で改善出来るのではないかと。 まず大前提として、選手権は25分切れ負けで、一手当たり最低1秒は消費します。 で、例えば自分の残り時間が90秒…

SVMを用いたヘテロジニアス合議

今構想中の多数決合議ではヘテロな(それぞれ異なる評価項目・パラメータを持つ)複数の評価関数を用いて、多数決で指し手を決めるって方式で検討中です。 ただ、合議サーバは多数決型だけではなく楽観型もありますので、もう少し違った方式も出来るのではな…

合議の票数を基準とした思考時間制御

アイデアとして書くほどのものじゃないんですが、とりあえず思い付いたので書いてみます。 今のGA将!!!!!は、合議の最多得票数の手に応じて以下の様に思考時間制御をしています。 まず、進行度と経過手数を元に基本思考時間を設定。ただし、基本思考時間は最…

自己対戦学習でも合議を有効活用出来ないか

ゲーム情報学研究発表会*1の「合議アルゴリズムプレイヤの棋譜を用いた将棋の評価関数の学習」を読んでたらふと思ったんですが、自己対戦学習で合議を使って手を選択するってのはどうかなぁ、と。 まず、現状の評価項目は下記の通り。 駒割の評価 筋・段個別…

駒同士の連携の評価

カーネル法の本を読んでいると「カーネル法を使えば、通常のベクトルとグラフや木構造をシームレスに扱える」ってな感じの事が書いてあります。 で、それなら駒同士の連携(「何番の駒が何番に利いている」という情報)を有向グラフにして、それを評価項目に…

方策勾配法とカーネル法を組み合わせれないかと検討中

以前に自然方策勾配法の実装を検討した時は、パラメータ数が多すぎて無理(メモリに載らない)という理由で断念しました。ですが、STRさんの手法を真似てカーネル法を使えば、パラメータ数を減らせれるので自然方策勾配法が使用可能ではないかと。 低次元の…

最善局面判別に必要最小限の特徴のみを用いた多数決合議用評価関数の実装

今のGA将!!!!!の実装では、評価項目*1ごとに有効・無効を切り替えて複数の評価関数を生成しています。 で、この有効・無効の切り替えの粒度をもっと細かく出来ないかと考えたのが今回の発想の原点。 やり方は単純で、適当な数の棋譜データを準備し、そこから…

駒の価値を移動させるのってどうだろうか

GA将!!!!!では駒の絶対位置の評価をしているんですが、これを移動後の位置のパラメータから移動前の位置のパラメータに移動させる(移動前の値を移動後の値に近付ける)ってのは上手く行かないかな。TD法の超限定条件下での動作って感じで。 例えば3九の銀…

ソフトマックス戦略を用いた多数決合議

今までは各弱エンジンが一票全てを最善手に投じていましたが、別に一票全部を一つの手に集める必要は無いんじゃないかと思って。 んで、強化学習で使うソフトマックス戦略を用いて、ルートノードでの各手に対して、その選択確率に応じた票を投じるってのを考…

反復深化合議

名前の通り、反復進化しながらその結果で合議する方式。 つまり、深さ1での最善手・深さ2での最善手・深さ3での…と順に一票ずつ投票していき、最終的に一番得票数の多かった手を指すやり方。 浅い探索では悪い手しか見つからなかった場合に、その結果に引っ…

密結合合議って出来ないもんだろうか

合議は基本的には疎結合なものですが、一部の情報は共有出来ると思うんですよ。 例えば“詰み”の情報は複数のエンジンで共有しても問題ないはず。これは、評価関数や乱数の違いに依存せず、単純に局面だけに依存する情報なので。 なので、あるエンジンが詰み…

強化学習将棋へのプランニングの導入を検討中

森北出版の「強化学習」によると、環境のモデル*1を用いない手法を「学習」、用いる手法を「プランニング」と呼ぶそうです。 で、今までの私のプログラムは前者だったんですが、他のソフト相手での対局から学習するならプランニングの方が相性いいかもと思っ…