コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習

Slides:



Advertisements
Similar presentations
コンピュータ囲碁における Root 並列化について 発表者 副島 佑介. 目次 研究背景 – 囲碁の難しさ – モンテカルロ木探索について – 並列化手法の先行研究 提案手法 – Root 並列化における合議制 実験結果 まとめ.
Advertisements

 C 川船 美帆.  強い人工知能の作成 o 「遺伝的アルゴリズム」  「どうぶつしょうぎ」のアプリケーショ ン作成 o スマートフォン向けアプリケーション.
白井ゼミ 豊田秀樹(2008)『データマイニング入門』 (東京図書)。4章
3次元nクイーン問題の 解に関する研究 論理工学研究室 伊藤精一
Building text features for object image classification
「わかりやすいパターン認識」 第1章:パターン認識とは
ML 演習 第 8 回 2007/07/17 飯塚 大輔, 後藤 哲志, 前田 俊行
コンピュータ囲碁の仕組み ~ 将棋との違い ~
圧縮類似度を用いた方言の自動分類 ~ライス符号を用いた前処理~ ~連結クラスタリング法~ ~余弦類似度を用いた方言分類木の評価~
将棋プログラム「激指」  鶴岡 慶雅.
芦田尚美*,髙田雅美*,木目沢司†,城和貴* *奈良女子大学大学院 †国立国会図書館
上坂吉則 尾関和彦 文一総合出版 宮崎大輔2003年6月28日(土)
ゲームプレイング (Game Playing)
ゲームプレイング (Game Playing)
モンテカルロ法によるミニ囲碁 増井拓視 情報理論工学研究所.
ゲームプレイング (Game Playing)
クロスワードゲームの 作り方を学ぼう/やってみよう ‐ボードゲームの動作機構‐
モンテカルロ法と囲碁・将棋ソフトの人知超え
生命情報学入門 機械学習を用いたタンパク質の分類法 2011年6月7日
情報教育論 第9回 仮定文の仕組み 政策・メディア研究科 岡田 健.
単位 おねだり ☆オセロ おねだり隊☆D班.
ガウス過程による回帰 Gaussian Process Regression GPR
第6章 カーネル法 修士2年 藤井 敬士.
サポートベクターマシン によるパターン認識
計算機実験の計画 References 研究目的 囲碁・将棋での強化学習 高信頼性人工知能システムへの展望 大規模な強化学習技術の実証と応用
情報論理工学 研究室 第5回: 局面・駒石・手の表現.
Bottom-UpとTop-Down アプローチの統合による 単眼画像からの人体3次元姿勢推定
グラフアルゴリズムの可視化 数理科学コース 福永研究室 高橋 優子 2018/12/29.
人工知能特論 9.パーセプトロン 北陸先端科学技術大学院大学 鶴岡 慶雅.
音高による音色変化に着目した音源同定に関する研究
第14章 モデルの結合 修士2年 山川佳洋.
音響伝達特性を用いた単一マイクロホンによる話者の頭部方向の推定
4人版リバーシYoninの解析 情報論理研究室 藤本 侑花
第7章 疎な解を持つカーネルマシン 修士2年 山川佳洋.
Data Clustering: A Review
数独の解生成と 解に対する番号付け 理学部 情報科学科 渡辺研究室 戸神星也.
近畿大学理工学部情報学科 情報論理工学研究室 赤井 隆純
逆算法に基づく 詰将棋の列挙 堀山貴史 中塚裕之 岩間一雄 (京都大学) 持駒なし 9手詰め.
1-Q-9 SVMとCARTの組み合わせによる AdaBoostを用いた音声区間検出
部分的最小二乗回帰 Partial Least Squares Regression PLS
サポートベクターマシンを用いた タンパク質スレッディングの ためのスコア関数の学習 情報科学科4年 81025G 蓬来祐一郎.
Nightmare at Test Time: Robust Learning by Feature Deletion
顔特徴点移動量・点間距離変化量の組み合わせに基づく顔表情認識
適応的近傍を持つ シミュレーテッドアニーリングの性能
モンテカルロ法を用いた 立体四目並べの対戦プログラム
情報論理工学 研究室 第7回: 強い手の選択.
理工学部情報学科 情報論理研究室 野中章宏 2016年2月5日
研究背景と目的 局面対による学習の高速化 学習器の説明 今後 大規模な強化学習技術の実証と応用 一方で、 強化学習手法の台頭
「データ学習アルゴリズム」 第3章 複雑な学習モデル 報告者 佐々木 稔 2003年6月25日 3.1 関数近似モデル
わかりやすいパターン認識 第7章:部分空間法  7.1 部分空間法の基本  7.2 CLAFIC法                  6月13日(金)                  大城 亜里沙.
第3章 線形回帰モデル 修士1年 山田 孝太郎.
サポートベクターマシン Support Vector Machine SVM
「ICAによる顔画像特徴量抽出とSVMを用いた表情認識」
京都大学 化学研究所 バイオインフォマティクスセンター
第9章 学習アルゴリズムとベイズ決定側 〔3〕最小2乗法とベイズ決定側 発表:2003年7月4日 時田 陽一
モデル作成にクラスタリングを用いた視線認識
``Exponentiated Gradient Algorithms for Log-Linear Structured Prediction’’ A.Globerson, T.Y.Koo, X.Carreras, M.Collins を読んで 渡辺一帆(東大・新領域)
囲碁プログラム 彩の仕組み 山下 宏 2008年9月4日 FIT2008.
近畿大学理工学部情報学科 情報論理工学研究室 段野健太
第28回世界コンピュータ将棋選手権アピール文章 作成:井本 康宏 作成日:2018/3/吉日
ICML読む会資料 (鹿島担当) 教師ナシ の 構造→構造 マッピング 読んだ論文: Discriminative Unsupervised Learning of Structured Predictors Linli Xu (U. Waterloo) , … , Dale Schuurmans.
モデルの微分による非線形モデルの解釈 明治大学 理工学部 応用化学科 データ化学工学研究室 金子 弘昌.
音響伝達特性を用いた単一チャネル 音源位置推定における特徴量選択の検討
戦術的観点からの  変形碁盤間の   類似度評価 佐藤 真史(早稲田大学).
パターン認識特論 カーネル主成分分析 和田俊和.
わかりやすいパターン認識 第6章 特徴空間の変換 6.5 KL展開の適用法 〔1〕 KL展開と線形判別法 〔2〕 KL展開と学習パターン数
Webページタイプによるクラスタ リングを用いた検索支援システム
情報論理工学 研究室 第8回: ミニマックス法.
CSP係数の識別に基づく話者の 頭部方向の推定
グラフ-ベクトル変換を用いたグラフ構造表現による一般物体認識
Presentation transcript:

コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習 九州大学大学院システム情報科学府修士1年  末廣 大貴 コンピュータ将棋におけるカーネル法を用いた静的評価関数の学習

目次 自己紹介 研究背景 関連研究 提案手法 実験 今後の課題

自己紹介 九州は福岡から来ました 研究室では主に機械学習について学んでます 学部時代は将棋部で、機械学習がコンピュータ将棋界で流行っていると聞き、研究を始める 研究室は違うが、瀧本先生と共同研究してます そしてこの研究会を紹介されました でもまさか一人で行くことになるとは・・・

将棋は「解ける」か? ゲームのパターン数 オセロ 10の60乗 チェス 10の120乗 将棋 10の220乗 囲碁 10の360乗 オセロ 10の60乗 チェス    10の120乗 将棋 10の220乗 囲碁     10の360乗 将棋をしらみつぶしに解くことはほぼ不可能 強い将棋コンピュータを作ろう

「強い」コンピュータ将棋を作るために 局面評価(形勢判断)の正確さ 正確な静的評価関数 先読み(探索)の速さ     枝刈り,並列化など

静的評価関数 入力:局面を表現するベクトル 駒の有無(駒割) 駒の位置関係 玉の危険度 出力:実数(評価値) を重みベクトルとしたとき,

静的評価関数 例:駒の有無だけを考えた静的評価関数 例:駒の重み(手番で符号を入れ替える) 飛 角 金 銀 桂 香 歩 龍 馬 と 成銀 成桂 成香 と 170 140 100 80 60 50 20 185 160 91 82 78 65

静的評価関数                  先手は後手より                  馬1枚得(+160)                  角1枚得(+140)                  で300点優勢                 

静的評価関数の作りかた 従来・・・人間の手作業による調整 ボナンザメソッド(保木,2006) 機械学習による、特徴ベクトルの重みの自動調整 大変な労力 作成者の棋力,感覚に依存 ボナンザメソッド(保木,2006) 機械学習による、特徴ベクトルの重みの自動調整

問題提起 特徴ベクトルの要素は作成者が用意しなければならない →やはり作成者の感覚、棋力に依存   →やはり作成者の感覚、棋力に依存 実際、現在の強豪プログラムの多くは、将棋の高度な知識が必要とされるような特徴ベクトルを多く用い、学習を行っている

問題提起 局面の単純な情報のみから、必要な特徴を自動的に作成し、学習できないか

提案手法 サポートベクターマシンとカーネル法に注目 サポートベクターマシン カーネル法と相性の良い優秀な学習器 カーネル法   カーネル法と相性の良い優秀な学習器 カーネル法 特徴ベクトルの要素同士の組み合わせから成る新しい特徴を構成する(今回の手法の骨子)

SVM(サポートベクトルマシン) ? 超平面 座標上に学習サンプルが与えられる マージン(超平面と一番近い例との距離) が最大となるような超平面を作成 ? 未知の例が与えられる 超平面に応じて分類

SVM(サポートベクトルマシン) これは二次計画問題なので,効率よく 解くことが出来る 線形分離不可能なデータには性能が不十分

カーネル法 データを高次元の特徴空間上へ写像し、   SVMを線形分離不可能な問題にも対応させる 超平面

カーネル法 カーネル関数 先ほどの式の を        に置き換え るだけで,特徴空間上でのマージン最大化超平面 を求めることが出来る

多項式カーネル 次元の点を 次元の特徴空間に写像 例:  が2次元ベクトル、

ガウシアンカーネル 無限次元の特徴空間に写像 カーネルを使えば,元の特徴のn項関係を特徴とする特徴空間上で超平面を学習できる

提案手法 プロ棋士の棋譜を用意 棋譜の全ての局面に対し プロが指した手の後の局面(棋譜の次局面)を正例 その他の合法手後の局面を負例   とする 全ての局面を単純な特徴ベクトルで表したものを学習サンプルとして、SVMとカーネル法を用いた学習を行う

提案手法 単純な特徴ベクトル(値は 0 or 1)の例 など 要素の数は,トータルで6000弱 盤上の駒kの数m B[k][m] 持ち駒kの枚数m H[k][m] 盤上の位置pに駒kがある P[p][k] 盤上の位置pに駒kが利いている E[p][k]    など 要素の数は,トータルで6000弱

提案手法 特徴ベクトルファイルの具体例 (SVMlight,LIBSVM形式) ラベル B[歩][] B[香][] ・・・ H[歩][] P[11][] -1 8:1 28:1 541:1 560:1 815:1 9:1 542:1 +1 561:1

対局方法 学習で得たSVMの超平面を用意 局面の全ての合法手後の局面の単純な特徴ベクトルを書き出す 超平面と局面のベクトル表現との内積をその局面の評価値とする 最も評価値の高い局面を選択する minimax法は用いない

学習から対局までの概略図 プロの指した +1 9:0 28:0・・・ 後の局面 -1 9:0 28:0・・・ その他の合法手後の局面 ・ 超平面 学習! +1 9:0 28:0・・・ プロの指した 後の局面 その他の合法手後の局面 -1 9:0 28:0・・・ ・ SVMとカーネル 棋譜のある局面

学習から対局までの概略図 9:0 28:0・・・ すべての合法手後の局面 ・ 超平面との内積計算 ! SVMとカーネル 対局中のある局面 1.05499 - 0.43635 0.53457 ・

実験 以下のプログラム同士を対戦させた SVMlightを使用(http://svmlight.joachims.org/) ランダムに指すプログラム 10局学習したプログラム(カーネル法有る無し) 20局学習したプログラム(カーネル法有る無し) Passive Aggressive(オンラインアルゴリズム)の カーネルなしで2000局学習 SVMlightを使用(http://svmlight.joachims.org/) カーネルは多項式カーネル(     )を用いた 特徴ベクトルは先ほどあげた6000弱のもの 全てに詰め将棋ルーチン(7手詰)を搭載

実験 相手 lin10 lin20 ker10 ker20 PA 2000 rand 勝敗 手番 先 後 linear10 ○ × × × ○ × × × × × × ○ ○ ○ 4 - 0 linear20 ○ ×  kernel10 10 - 0 kernel20 ○ ○ ○ ○  8 - 0 random 0 - 10

重要な問題 なぜ最高で20局しか学習していないのか? →学習サンプルがメモリに乗らない (100局で約1.5G) →サンプル数を増やすと,計算時間が急速に増大 現在棋譜を50000局用意しているが・・・

課題 学習に時間がかかりすぎる(→並列化?) メモリに乗らない(→オンライン?) 基本特徴ベクトルの追加(相対位置、王手など) SVMのパラメータの最適化 やたら駒を切りたがるので,カーネルに期待しつつ,静的評価関数の正確さを測るため探索も入れた方が良いかも ランキング問題として考えてみる