So-net無料ブログ作成
検索選択

矢倉4三銀3七桂型激減の理由 [将棋]

まとめサイトあたりで「居飛車党の先手番で指す戦法がない」という話を見かけて気になっていたところ、矢倉の4六銀3七桂型については渡辺二冠が解説してくれたのでメモ。

http://www.nicovideo.jp/watch/sm26305132
真ん中あたり~

・4六銀3七桂の4六銀を指す前の局面
 http://kyokumen.jp/positions/11604
・▲4六銀に対して△5三銀、そして▲3七桂で先手がやれるというのがそれまでの常識だった
 http://kyokumen.jp/positions/18268
・△5三銀に代えて△4五歩が1つ目の新手
 2年前ぐらいに塚田泰明九段がやりはじめた、コンピュータにやられて咎めるのが難しかったらしい

・▲3七銀と引いてからは、△5三銀
  http://kyokumen.jp/positions/30497
・▲4六歩か▲4八飛
・▲4八飛に△4四銀右だと後手はあまり良くないというのが去年までの常識だった
 http://kyokumen.jp/positions/30498
 http://kyokumen.jp/positions/290543
・ここで、2014年秋ごろの電王戦タッグマッチで菅井習甦が△5五歩とつく(居飛車党にとって)超斬新な手順で勝った
 http://www.nicovideo.jp/watch/sm24542406
 1:48~

 http://www.nicovideo.jp/watch/sm24540765
 12:00~ 5五歩がコンピュータにとって常識的なのかどうか聞いている渡辺二冠

・渡辺二冠は△5五歩が成立するなら、△9四歩も成立するとみて順位戦に採用
 行方尚史 vs 渡辺明二冠 2015-01-08 第73期順位戦A級7回戦
 http://kifdatabase.no-ip.org/shogi/index.php?cmd=kif&cmds=display2&kid=82432

 http://kyokumen.jp/positions/4793505

・さらにJT杯で羽生相手にも指したところ快勝した
 http://live.shogi.or.jp/jt/kifu/35/jt201411160101.html

 △9四歩のコメント
 △9四歩に羽生の手がしばし止まっている。
「研究が深すぎて解説がついていかないですね」(藤井九段)

 △7三桂のコメント
△7三桂に羽生が時間を使っている。
「じゃあ羽生名人に次の手を封じてもらいましょうかね」と藤井九段。
17時18分、羽生が封じ手の意志を示したようだ。対局はしばしの休憩に入る。両対局者がステージから降りてきた。
ここまでの消費時間は▲羽生9分、△渡辺3分。
藤井九段の候補手は▲6四角や▲6八角を、矢内女流五段は▲5五歩を挙げている。他にも▲9六歩などが考えられるようだ。
対局は17時35分に再開予定。
35分、渡辺、羽生の順にステージへ向かった。

 正解者無しで話題となった封じ手クイズだったが、今までの話があったとすると、藤井九段は研究通りの展開になって一方的にならないようにしようとしていたのかもしれない。

・▲46歩、△同歩、▲同角のときに、「△7三桂と跳ねて問題がない」のが△4五歩からの後手の主張
 http://kyokumen.jp/positions/5968266
 先手から▲6四角と角交換してきたときに、△同銀で取る(http://kyokumen.jp/positions/11556489)と、▲7一角打、△7二飛、▲3六馬と馬がタダで作られて後手は面白く無いとされていた。ところが、△8五歩が入っていないので、△8五桂から後手が攻めることが出来る。(一手損角換わりと同じ理由?)

後手番一手損角換わり
https://ja.wikipedia.org/wiki/%E5%BE%8C%E6%89%8B%E7%95%AA%E4%B8%80%E6%89%8B%E6%90%8D%E8%A7%92%E6%8F%9B%E3%82%8F%E3%82%8A

 そこで、羽生4冠はJT杯のときに、先に8五桂への銀当たりを緩和する▲6八銀を封じ手にした。

・このJT杯の快勝のイメージが強いので、今のところ後手番のほうがよい変化が多いとされている

 投了時のコメント
△5九角からの詰めろ。先手玉は受けが難しい。
△3九成桂に羽生が投了。渡辺が日本シリーズ初優勝を決めた。
局後、「作戦的にこちらが用意してきた手(42手目・△7三桂)が出る展開でアドバンテージがあったと思います」と渡辺。
「封じ手の▲6八銀(43手目)がどうだったか。あまりよくなかったかもしれません」と羽生。
感想戦は▲6八銀に代えて▲6四角と取る手が検討された。手順は43手目コメントに追記しました。
表彰式後、渡辺は「ようやく初優勝することができて良かったです」とファンの前で語った。

 矢倉の4三銀、3七桂型については4五歩以下の望ましくない手順が多いので、違う形(脇システム?など)が模索されている模様

■局面ペディア
 局面ペディアの存在を思い出したので見てみたところ、Floodgateでは定跡DBの影響が大きく、▲4六銀に対して△5三銀とするソフトが大半であるため、あまり参考にならない。特にTitanda_Lは1秒で5三銀としている場合が大半のようなので、この定跡は外してみても良いのではないかと思う。
 GPSFishだと△4五歩はかなり「迷う」手のようではっきりしない。
 Aperyは明確に△4五歩一択になっている。Aperyは4五歩以下の展開が後手有利と判断しているため、その前の△2二玉ではなく△9四歩で後手が若干やれると判断している。そのため、2二玉で入城して4六銀3七桂の形にはならないようである。
 http://kyokumen.jp/positions/7817

 あと、2014年ponanzaも5三銀は決めてしまっているようにも見えるので、もし矢倉に誘導できるのであれば、4五歩あたりから活路を見いだせたかもしれない。Aperyの場合、この局面がちょうど30手過ぎたところなので、「30手までは定跡手順」とすると5三銀が定跡手順に入らないので、コンピュータ同士だとここに来る前に変化をする事が多い模様。

■反響
 
△45歩も(62飛では)簡単ではないと思うのだが、「先手を持って覆すのは面倒だし、他の形にしよう」という流れかなぁ。 もしくは摸索中か。


 先手で主導権があるはずなのに好ましい変化が少なくなってしまったのでよほどの矢倉スキーでないと積極的に選ぶ理由がない、というところだと思う。
 先手矢倉のテーマとして、脇システムや早囲いに活路を見出しているのが現状のようだ。

■参考書


プロの定跡最前線 矢倉△4五歩作戦の研究(将棋世界2015年09月号付録)

プロの定跡最前線 矢倉△4五歩作戦の研究(将棋世界2015年09月号付録)

  • 出版社/メーカー: マイナビ(日本将棋連盟発行)
  • 発売日: 2015/08/05
  • メディア: Kindle版



ちょうど将棋世界の別冊付録にこの変化を軽くまとめたものが出た。ただ、上記の変化の前の段階(7五歩からの変化)の説明が多い。5五歩、9五歩についてはかなり驚いている様子が伺える。

2八角の棋譜 [将棋]

自分の記憶が曖昧な気がしたので、動画から棋譜を起こしてみた

手合割:平手
先手:山口さん(24でR3000)
後手:AWAKE_電王戦FINAL
手数----指手---------消費時間--
1 7六歩(77) ( 0:00/00:00:00)
2 3四歩(33) ( 0:00/00:00:00)
3 6八飛(28) ( 0:00/00:00:00)
4 6二銀(71) ( 0:00/00:00:00)
5 4八玉(59) ( 0:00/00:00:00)
6 8四歩(83) ( 0:00/00:00:00)
7 1六歩(17) ( 0:00/00:00:00)
8 4二玉(51) ( 0:00/00:00:00)
9 1五歩(16) ( 0:00/00:00:00)
10 3二玉(42) ( 0:00/00:00:00)
11 2二角成(88) ( 0:00/00:00:00)
12 同 玉(32) ( 0:00/00:00:00)
13 8八銀(79) ( 0:00/00:00:00)
14 1二香(11) ( 0:00/00:00:00)
15 7七銀(88) ( 0:00/00:00:00)
16 1一玉(22) ( 0:00/00:00:00)
17 2八銀(39) ( 0:00/00:00:00)
18 2二銀(31) ( 0:00/00:00:00)
19 2六歩(27) ( 0:00/00:00:00)
20 3一金(41) ( 0:00/00:00:00)
21 2七銀(28) ( 0:00/00:00:00)
22 2八角打 ( 0:00/00:00:00)
23 1六香(19) ( 0:00/00:00:00)
24 1九角成(28) ( 0:00/00:00:00)
25 3八玉(48) ( 0:00/00:00:00)
26 8五歩(84) ( 0:00/00:00:00)
27 4八金(49) ( 0:00/00:00:00)
28 3五歩(34) ( 0:00/00:00:00)
29 5八金(69) ( 0:00/00:00:00)
30 3六歩(35) ( 0:00/00:00:00)
31 同 銀(27) ( 0:00/00:00:00)
32 5一銀(62) ( 0:00/00:00:00)
33 2七銀(36) ( 0:00/00:00:00)
34 2九馬(19) ( 0:00/00:00:00)
35 同 玉(38) ( 0:00/00:00:00)
36 4二銀(51) ( 0:00/00:00:00)
37 3八玉(29) ( 0:00/00:00:00)
38 3三銀(42) ( 0:00/00:00:00)
39 6六歩(67) ( 0:00/00:00:00)
40 4四歩(43) ( 0:00/00:00:00)
41 4三角打 ( 0:00/00:00:00)
42 5二金(61) ( 0:00/00:00:00)
43 6五角成(43) ( 0:00/00:00:00)
44 4二銀(33) ( 0:00/00:00:00)
45 5六馬(65) ( 0:00/00:00:00)
46 4三金(52) ( 0:00/00:00:00)
47 8八飛(68) ( 0:00/00:00:00)
48 3三銀(42) ( 0:00/00:00:00)
49 8六歩(87) ( 0:00/00:00:00)
50 同 歩(85) ( 0:00/00:00:00)
51 8三歩打 ( 0:00/00:00:00)
52 3二飛(82) ( 0:00/00:00:00)
53 8六飛(88) ( 0:00/00:00:00)
54 3四銀(33) ( 0:00/00:00:00)
55 8二歩成(83) ( 0:00/00:00:00)
56 4五銀(34) ( 0:00/00:00:00)
57 7八馬(56) ( 0:00/00:00:00)
58 3六歩打 ( 0:00/00:00:00)
59 同 歩(37) ( 0:00/00:00:00)
60 同 銀(45) ( 0:00/00:00:00)
61 3七歩打 ( 0:00/00:00:00)
62 2七銀(36) ( 0:00/00:00:00)
63 同 玉(38) ( 0:00/00:00:00)
64 4五歩(44) ( 0:00/00:00:00)
65 9一と(82) ( 0:00/00:00:00)
66 4六歩(45) ( 0:00/00:00:00)
67 同 歩(47) ( 0:00/00:00:00)
68 3五桂打 ( 0:00/00:00:00)
69 3八玉(27) ( 0:00/00:00:00)
70 4七歩打 ( 0:00/00:00:00)
71 同 金(48) ( 0:00/00:00:00)
72 2七銀打 ( 0:00/00:00:00)
73 4八玉(38) ( 0:00/00:00:00)
74 4七桂成(35) ( 0:00/00:00:00)
75 同 金(58) ( 0:00/00:00:00)
76 3八金打 ( 0:00/00:00:00)
77 5八玉(48) ( 0:00/00:00:00)
78 3七金(38) ( 0:00/00:00:00)
79 5六金(47) ( 0:00/00:00:00)
80 4七金(37) ( 0:00/00:00:00)
81 6七玉(58) ( 0:00/00:00:00)
82 1六銀成(27) ( 0:00/00:00:00)
83 8一飛成(86) ( 0:00/00:00:00)
84 5四香打 ( 0:00/00:00:00)
85 7五歩(76) ( 0:00/00:00:00)
86 3八飛成(32) ( 0:00/00:00:00)
87 8七馬(78) ( 0:00/00:00:00)
88 8八歩打 ( 0:00/00:00:00)
89 同 銀(77) ( 0:00/00:00:00)
90 6四歩(63) ( 0:00/00:00:00)
91 7六玉(67) ( 0:00/00:00:00)
92 5六香(54) ( 0:00/00:00:00)
93 同 歩(57) ( 0:00/00:00:00)
94 4六金(47) ( 0:00/00:00:00)
95 9六香打 ( 0:00/00:00:00)
96 5六金(46) ( 0:00/00:00:00)
97 8五玉(76) ( 0:00/00:00:00)
98 8三歩打 ( 0:00/00:00:00)
99 同 龍(81) ( 0:00/00:00:00)
100 8六歩打 ( 0:00/00:00:00)
101 4三馬(87) ( 0:00/00:00:00)
102 8八龍(38) ( 0:00/00:00:00)
103 8四玉(85) ( 0:00/00:00:00)
104 8九龍(88) ( 0:00/00:00:00)
105 9三玉(84) ( 0:00/00:00:00)
106 4九龍(89) ( 0:00/00:00:00)
107 5三馬(43) ( 0:00/00:00:00)
108 4一桂打 ( 0:00/00:00:00)
109 7一馬(53) ( 0:00/00:00:00)
110 9九龍(49) ( 0:00/00:00:00)
111 9二玉(93) ( 0:00/00:00:00)
112 1四歩(13) ( 0:00/00:00:00)
113 9三香成(96) ( 0:00/00:00:00)
114 1五歩(14) ( 0:00/00:00:00)
115 5二歩打 ( 0:00/00:00:00)
116 9七龍(99) ( 0:00/00:00:00)
117 9四歩打 ( 0:00/00:00:00)
118 6五歩(64) ( 0:00/00:00:00)
119 5一歩成(52) ( 0:00/00:00:00)
120 3七龍(97) ( 0:00/00:00:00)
121 5二金打 ( 0:00/00:00:00)
122 3三桂(41) ( 0:00/00:00:00)
123 4三歩打 ( 0:00/00:00:00)
124 4五桂(33) ( 0:00/00:00:00)
125 4二歩成(43) ( 0:00/00:00:00)
126 同 金(31) ( 0:00/00:00:00)
127 同 金(52) ( 0:00/00:00:00)
128 3一歩打 ( 0:00/00:00:00)
129 4四歩打 ( 0:00/00:00:00)
130 3三銀打 ( 0:00/00:00:00)
131 4三歩成(44) ( 0:00/00:00:00)
132 4二銀(33) ( 0:00/00:00:00)
133 同 と(43) ( 0:00/00:00:00)
134 4八歩打 ( 0:00/00:00:00)
135 4一と(51) ( 0:00/00:00:00)
136 9五歩打 ( 0:00/00:00:00)
137 4四歩打 ( 0:00/00:00:00)
138 3二金打 ( 0:00/00:00:00)
139 4三歩成(44) ( 0:00/00:00:00)
140 同 金(32) ( 0:00/00:00:00)
141 同 と(42) ( 0:00/00:00:00)
142 3四龍(37) ( 0:00/00:00:00)
143 4四金打 ( 0:00/00:00:00)
144 3五龍(34) ( 0:00/00:00:00)
145 3四桂打 ( 0:00/00:00:00)
146 同 龍(35) ( 0:00/00:00:00)
147 同 金(44) ( 0:00/00:00:00)
148 3三香打 ( 0:00/00:00:00)
149 4四馬(71) ( 0:00/00:00:00)
150 8七歩成(86) ( 0:00/00:00:00)
151 8二飛打 ( 0:00/00:00:00)
152 投了 ( 0:00/00:00:00)
まで151手で先手の勝ち

・打って香があがってから、取るまで。
 金が下段にいて、取るための手数がかかるほうが2八角率が高いらしい

・この棋譜でも3五歩~3六歩は突かれていた
 3六歩、同銀のときに、5一銀だが、家のPC+Awakeだと1八馬となり、さっさと馬は諦めて銀と交換しようとする。

通常のアマの場合、銀角交換ぐらいだと玉型の悪さから食いつかれて崩壊していたと思う。

この棋譜の場合、入玉狙いのための手が、ことごとくうまく行っていた。

歩で飛車をまらわせる。
右から負わせるために駒を使わせる
玉の逃げ道をあける。
香車で逃げ道を舗装する。

などなど。
5一銀が出ないとこういう展開になりにくいので、角銀交換+長時間だったらどうなったのかは、興味がある。
やねうらおさんのいう「ハンデを与えるのはどうやったらいいか」というのがまさにこの条件ではなかっただろうか。

手合割:平手
先手:阿久津主税
後手:AWAKE
手数----指手---------消費時間--
1 7六歩(77) ( 0:00/00:00:00)
2 3四歩(33) ( 0:00/00:00:00)
3 6八飛(28) ( 0:00/00:00:00)
4 8四歩(83) ( 0:00/00:00:00)
5 4八玉(59) ( 0:00/00:00:00)
6 6二銀(71) ( 0:00/00:00:00)
7 1六歩(17) ( 0:00/00:00:00)
8 8八角成(22) ( 0:00/00:00:00)
9 同 銀(79) ( 0:00/00:00:00)
10 4二玉(51) ( 0:00/00:00:00)
11 1五歩(16) ( 0:00/00:00:00)
12 3二玉(42) ( 0:00/00:00:00)
13 2八銀(39) ( 0:00/00:00:00)
14 2二玉(32) ( 0:00/00:00:00)
15 2六歩(27) ( 0:00/00:00:00)
16 5四歩(53) ( 0:00/00:00:00)
17 2七銀(28) ( 0:00/00:00:00)
18 5三銀(62) ( 0:00/00:00:00)
19 9六歩(97) ( 0:00/00:00:00)
20 2八角打 ( 0:00/00:00:00)
21 1六香(19) ( 0:00/00:00:00)
22 投了 ( 0:00/00:00:00)
まで21手で先手の勝ち

なんて思ったが、こっちだと穴熊に組む前に打たされたのでよりひどい状況かもしれない。
Aperyだと、

・途中で気がついて角銀交換で抑えようとする
・意地でも穴熊に組んでしまう

という方針のようで、先手玉が薄いのもあってか、穴熊のハッチ閉めた状態では、先手+316点という割といい勝負。コンピュータ相手にここから勝ちきれるのかはやってみないとわからないところだとは思うので、最後までやってみてほしかったかなぁとは思った。

オンライン機械学習の本 [将棋]


オンライン機械学習 (機械学習プロフェッショナルシリーズ)

オンライン機械学習 (機械学習プロフェッショナルシリーズ)

  • 作者: 海野 裕也
  • 出版社/メーカー: 講談社
  • 発売日: 2015/04/08
  • メディア: 単行本(ソフトカバー)



まだ軽く目を通しただけだが、簡潔によくまとまってて久々にいい本に出会ったなと思う。
なんでも筆者いわく、自分が理解する上でまとめたようなことを書かれていたが、概念や思想的な面での筋道がたっていてわかりやすい。
オンライン機械学習というタイトルだが、バッチ学習のための基礎的な参考書としても十分使える。

例の黄色いクソ高い本は、基礎的な部分の説明が長く、じゃあそれで応用したらどうなるのという部分が皆無なので、素人にはわかりづらい。全部読めばある程度あたまにはいってくるのだろうが、読みやすさは断然こっちが上。

価格が安いのもよい。その代わりページ数が少ないがよくまとまってるので問題ない。この本をベースに足りないところなどは別途別の本を参考にするのが良いと思われる。

全然関係ないがとある論文を読んでいたら、例の糞高い黄色い本の表現をそのまま書かれていたりした。論文を書くような人でも、まとめるのに苦労している場合があり、機械学習を正しく勉強する難しさがあると思う。

そもそもは、コンピュータ関係の話は機械学習に限らず、数学的にはコンピュータがろくになかった時代の人達によって理論的には完成されていたりすることが多いので、そういう理論的なバックグラウンドを把握していないと何をしているかわからなくなることが多い、と自分は思っているので、この本は自分のニーズを見事に満たしてくれたので、久々にいい買い物をしたと思う。

Kindleでなかったのだけが残念。

例の糞高い本


パターン認識と機械学習 上

パターン認識と機械学習 上

  • 作者: C.M. ビショップ
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/04/05
  • メディア: 単行本(ソフトカバー)




パターン認識と機械学習 下 (ベイズ理論による統計的予測)

パターン認識と機械学習 下 (ベイズ理論による統計的予測)

  • 作者: C.M. ビショップ
  • 出版社/メーカー: 丸善出版
  • 発売日: 2012/02/29
  • メディア: 単行本



Stockfishの指し手生成とBonanzaの指し手生成の違い [将棋]

やねうら王Blogの指し手生成のところを見た時に面白いことをしているなぁって思ったが、今日起きた問題は割りとそれに近いのだろうか

http://yaneuraou.yaneu.com/2015/01/06/stockfish-dd-notation-%E6%8C%87%E3%81%97%E6%89%8B%E6%96%87%E5%AD%97%E5%88%97%E3%81%AB%E5%A4%89%E6%8F%9B/


gpsfishのmove.cpp

合法手を生成して、それと一致する文字列と一致したらOKというようにして、合法手かどうかを担保している

// move_from_uci() takes a position and a string representing a move in
/// simple coordinate notation and returns an equivalent Move if any.
/// Moves are guaranteed to be legal.

Move move_from_uci(const Position& pos, const string& str) {

#ifdef GPSFISH
  return osl::record::usi::strToMove(str,pos.osl_state);
#else
  MoveStack mlist[MAX_MOVES];
  MoveStack* last = generate(pos, mlist);

  for (MoveStack* cur = mlist; cur != last; cur++)
      if (str == move_to_uci(cur->move, pos.is_chess960()))
          return cur->move;

  return MOVE_NONE;
#endif
}



movegen.cpp

非合法手を含む手を生成してから合法手なものだけを返すようになっている

template<>
MoveStack* generate(const Position& pos, MoveStack* mlist) {

#ifdef GPSFISH
  return generate(pos, mlist);
#else
  assert(pos.is_ok());

  MoveStack *last, *cur = mlist;
  Bitboard pinned = pos.pinned_pieces(pos.side_to_move());

  last = generate(pos, mlist);

  // Remove illegal moves from the list
  while (cur != last)
      if (!pos.pl_move_is_legal(cur->move, pinned))
          cur->move = (--last)->move;
      else
          cur++;

  return last;
#endif
}


非合法手の生成は、王手がかかっているかどうかで違う。王手がかかってたら逃げる一手

/// generate computes a complete list of legal
/// or pseudo-legal moves in the current position.
template<>
MoveStack* generate(const Position& pos, MoveStack* mlist) {

  assert(pos.is_ok());

  return pos.in_check() ? generate(pos, mlist)
                        : generate(pos, mlist);
}


gpsfishの場合は、その後はOSLのライブラリで、手を生成している関係で、
Stockfish的な処理はばっさりカットしている

Bonafishの場合だと、ここがBonanza風になると思うが、
よく言われる探索時に不成りは生成していないというのは、次のあたりだろうか

root.c

int
make_root_move_list( tree_t * restrict ptree )
{
    unsigned int * restrict pmove;
	int asort[MAX_LEGAL_MOVES] = { 0 };
    unsigned int move;
    int i, j, k, h, value, num_root_move, iret, value_pre_pv;
    int value_best;

    // 1. 指し手生成
    pmove = ptree->move_last[0];
    ptree->move_last[1] = GenCaptures( root_turn, pmove );
    ptree->move_last[1] = GenNoCaptures( root_turn, ptree->move_last[1] );
    ptree->move_last[1] = GenDrop( root_turn, ptree->move_last[1] );
    num_root_move = (int)( ptree->move_last[1] - pmove );


next.c

   static int CONV
gen_next_quies( tree_t * restrict ptree, int alpha, int turn, int ply,
        int qui_ply )
{
    switch ( ptree->anext_move[ply].next_phase )
    {
        case next_quies_gencap:
            { 
                unsigned int * restrict pmove;
                int * restrict psortv;
                int i, j, n, nqmove, value, min_score, diff;
                unsigned int move;

                ptree->move_last[ply] = GenCaptures( turn, ptree->move_last[ply-1] );


使われていない合法手生成ルーチン自体は以下のようになっている

int CONV gen_legal_moves( tree_t * restrict ptree, unsigned int *p0, int flag )
{
    unsigned int *p1;
    int i, j, n;

    p1 = GenCaptures( root_turn, p0 );
    p1 = GenNoCaptures( root_turn, p1 );
    if ( flag )
    {
        p1 = GenCapNoProEx2( root_turn, p1 );
        p1 = GenNoCapNoProEx2( root_turn, p1 );
    }
    p1 = GenDrop( root_turn, p1 );


flagによって生成したりしなかったりするが、ponderの場合は出力して、
outmoveというコマンドの場合は出力しないようになっている

また、学習時には、全部生成するようになっている

learn1.c

    //すべての合法手生成
    pmove = GenCaptures     ( pdata->root_turn, pdata->amove_legal );
    pmove = GenNoCaptures   ( pdata->root_turn, pmove );
    pmove = GenDrop         ( pdata->root_turn, pmove );
    pmove = GenCapNoProEx2  ( pdata->root_turn, pmove );
    pmove = GenNoCapNoProEx2( pdata->root_turn, pmove );


というのを総合すると

Stockfishは

全部の合法手=偽合法手ー非合法手

Bonanzaは

合法手=全部の合法手ー不成り以外の手

となっていて、StockfishとBonanzaでは指し手生成の思想が違うのでgenerateの中をいれかえるような単純移植だと噛み合わない。
最初からちゃんとした合法手ができてる場合は、Stockfishのように変に判定を入れる必要はないような気がするがどうなんだろうか。

gpsfishが文字列を指し手に変換するだけの漢仕様なのは、クラスタの末端なので、上位がバグってなければ問題無いという信用で成り立っているようだが、将棋倶楽部24なんかだと王手放置が飛んでくるので、非合法手の場合の処理をいけなかったらしい

AperyだとPinされているても動かして開き王手も生成しているようなので、Stockfishポリシーと同じようです。(探索の方見てないので、確証はないですが)

	// 部分特殊化
	// Evasion のときに歩、飛、角と、香の2段目の不成も生成する。
	template  struct GenerateMoves {
		FORCE_INLINE MoveStack* operator () (MoveStack* moveStackList, const Position& pos) {
			MoveStack* curr = moveStackList;
			const Bitboard pinned = pos.pinnedBB();

			moveStackList = pos.inCheck() ?
				GenerateMoves()(moveStackList, pos) : GenerateMoves()(moveStackList, pos);

			// 玉の移動による自殺手と、pinされている駒の移動による自殺手を削除
			while (curr != moveStackList) {
				if (!pos.pseudoLegalMoveIsLegal(curr->move, pinned)) {
					curr->move = (--moveStackList)->move;
				}
				else {
					++curr;
				}
			}

			return moveStackList;
		}


不成りも生成するっていうのが、詰みが関わる場面では速度よりも信頼性ってことでしょうか。
2015年以降はApery参考にしておけば間違いないでしょう。

おまけ

http://emptywords.hatenadiary.jp/entry/2014/04/09/193055

<追記>
http://yaneuraou.yaneu.com/2015/03/22/selene%E3%81%8C%E5%8F%8D%E5%89%87%E8%B2%A0%E3%81%91%E3%81%97%E3%81%9F%E3%82%88%E3%81%86%E3%81%A7%E3%81%99%E3%81%8C/

同じことを考えていたようで安心した
確かに学習時に気がつくはずというのはあるので、学習は別で動かしてたとか、バグを発見できなかった理由はいろいろありそう

まあ、時代はAperyいじってれば間違いない。
Stockfishの最新版(今は6のRC3)は定跡ルーチンが消えているので、アップデートする気が激減した。しかもバグ含みで弱いし。


Aperyのメモ [将棋]

去年ぐらいにツイートで謎のリークがあったが、まさかぁと思っていたところ、本当に公開された。
しかもgithubなので、開発もやりやすい。(といいつつ最近はコンピュータ将棋そのものは忘れている)

全然動かしてないので、確認用のメモ程度で大したことは書いてない。
<平岡さんにRTされて閲覧数が増えたので少し直しました>

■準備
 https://github.com/HiraokaTakuya/apery_binaries

 落としてきたZipを展開するとBinフォルダが出来ると思うが、リネームしてはいけない
 フォルダ構成を変えると、評価値が間違ったまま動作するという罠モードに移行する
 (10手目ぐらいで評価値が5000とか出てくる)

 2chではXmlいじってどうこうという話が出ていたが、将棋所でもShogiGUIでも普通にエンジン登録できる

・主要な設定

 USI_Hash:2048 とか適当に決めたが、ZobristHashの仕様で次の大きさは4096になる
 USI_Ponder:False CPU同士対局のときはこうする。

 Threads:デフォルトはコア数になっているが、Core i7などでHT使ってて8コアになっていたら、4にする

 電王戦FINALバージョンなので対人用設定になっている
 Max_Random_Score_Diff 30 評価値がトップとの差30まで
 Max_Random_Score_Diff_Ply 40 40手目まで

 と思ってるがソースコード確認していない

 多分提出したら設定変えられないというルールのためにそうなってるんだろうが、個人が検討用に使うにはここらへんは両方0にしたほうがよいはず。
 Diff_Plyのほうの最小値が-32768なのはなんでだろうか。不安になってきた。
 対局用では逆に30を500にしたら調度良くなったというような話もあった

 序盤はMultiPV3になっているが、これはソースを変えないとだめそう?

 Use Sleeping Threadは対局時にはOffのほうが良さそうな印象があったが、デフォルトONだった。

・設定その他
 将棋所の「空白は認めないルール」に対応するため、Stoskfishと同等の設定値に「_」がついているので、設定項目が大量に出ている。
 いくつかの値は変更されているようだ。SplitDepthが1手深くなっている。

・動作
 速度はBMI2使ったものでCore i7 3.4GHzで
 序盤1コア80万程度、4コアで320万ぐらい
 中盤1コア60万程度 4コアで240万ぐらい

・安定性
 GPSFISHと違って落ちない。素晴らしい。

・強さ
 自分では3秒10戦しかやっていないが、6-4だった。
 Tweetや2ch情報をみてもgpsfishと比べて6:4ぐらいっぽい人もいれば圧勝の人もいる
 5960XだとNPSは2倍ぐらいになり、それがR3200のXeonをぼこっていたことを考えると、短時間より長時間のほうがより差がでるかもしれない(平岡さんも短時間はあまり強くないかもとは仰られていた)

 評価値を見てみると、中盤においては

 Bonanza:点がついていない
 gpsfish:矢倉とかで妙に強気なことがある
 Apery:gpsfishと似ているが、gpsが評価しない局面で良くなることが多い

 みたいな印象。序盤は速さを活かして深く読むので先に優勢になる事が多い。

<追記>
 あと、序盤の定跡生成っぽいコードはちゃんと見ていないが、GPSの定跡のように抜けたらいきなり300点悪くなってるというようなことはなさそうだ。
 これは、「人間の定跡を再評価して、ある程度よいものを自分の定跡にするようにする」という習甦の方法らしい。(要検証)
<追記終わり>

・ソースコード
 https://github.com/HiraokaTakuya/apery

 Readme.txtにも書かれているように、StockfishとBonanzaを読んでいると大体わかるようになっているっぽい。

 個人的にBonanzaの課題であるところは、速度を出すために黒番と白番でコードが書かれていて、ビット定数がハードコーディングされているところだと思っている。ボナンザ解析Blogでも見ないと意味がわからない。

 Stockfishのコードは妙にシンプルだと思ったが、チェスの場合Knightですら後ろにいけるので移動方向に区別があるのは、Pawnだけ。
 一方で将棋の場合は先手と後手で非対称なため、コードの同一性が難しい。(ハードコーディングされている数値が先手と後手で違う)
 この問題は、各ソフトでは以下のようになっている

 Bonanza:先手用ルーチンと後手用ルーチンを書く。数値もハードコーディング。
 旧やねうら王:YaneLispを作成し、先手用や後手用のルーチンを自動生成(それだけじゃないが)
 Apery:C++11以降のテンプレート機能を使用

 Colorが手番を表していてBlackのほうが先手、Whiteのほうが後手のはずだが
 (GPSFISHが公開されたときも少し話題になっていたが、チェスだと白が先手だが、将棋では黒が先手で表現されるかららしい)、テンプレート関数でColorがある場合は、先手と後手で違うコードを生成していると思って良い。最近のC++はテンプレートからさらに定数がコンパイル時に決定されるようになっているので、より意味がわかりやすいコードが書けるようになっている。

 inFrontMaskなんかはいい例で、Bonanzaではマジックナンバーだったが、それをコンパイラに自動生成させている。templateの部分を引数にすれば普通のコードとしても成り立っている。

 VisualStudio 2013の段階ではC++のテンプレートに使える引数に制約が多いため、ビルドが通らない。StockfishではC++11とそうでないコードを用意しているぐらいだが、将来的にVisualStudioがC++11に対応しなかったらどうするんだろうか。

 また、学習においてBonanzaではfuncなのが、sigmoidになってたりとか、よりわかりやすい。ただ、個人的にはsigmoidではなくて、Tに相当する何かにしてその中にインラインでsigmoidとかのほうが、より学術的ではないかなと思ったりもする。そうすると元々のfunc自体も別に悪くないのかとか思ったりもする。

 学習は多分NDFっぽいことはやってるはずだが、見ていない。Bonanza Methodと同等の構造になってることは確認した。
<追記>
 本格的に学習ルーチンを使うのは2015年以降のようだ。
 チーム開発する上で、Bonanza改造したほうが手軽なので、それをApery型にしていたようだ。
<追記終わり>

・最終的なパラメータ更新は向きしか考慮しないのがBonanza Methodなので、定数項をかけないようにして、学習の効率化を図ろうとしたようだが、やめている。(理由は不明)
・並列化するべきところとそうでないところについてのコメントが書いてあった。
・FV_WINDOWの数字が変えてあった。

 Bonanza Method以外の方法としてgps将棋やBlunderが採用した関数(ロジスティック回帰の対数をとったもの?)にしていたりとかはやっていないようだ。
 ロジスティック回帰の関数の性質を考えると、BlunderやGPSや(なのはも?)この方法のほうが良い成果がえられるのかもしれない。

 あと、Aperyのソースコード本体よりも、棋譜からBook作るRubyスクリプトのほうも興味深い。(WSCS常連はやってて当然かもしれないが)新規とかの人はかなり参考になりそう。特にAperyはやねうら定跡の富岡流?にはまった過去があるので、このスクリプトには思い入れがあるのではなかろうか。

  また、ついでにやってるかどうかはわからないが、Bookの評価値や勝率などを設定している点も興味深い。gpsfishでは、自分が300点悪いと思ってるほうに突っ込むというアホな序盤力があるが、定跡であっても評価値を入れることで自分の好きな形成に入るようになっている。逆にこのことによって、戦型が絞られすぎてしまうので、電王戦FINALでは振り飛車を解禁したのだろう。が、裏目に出てしまったようだ。(というと四間飛車=悪いみたいな話になってしまうが)
 序盤は今でも課題だと思われる。PonanzaはUCTで序盤生成を半年ぐらい前にやって、秘策3二金を編み出した(が、Floodgateでその秘策が出ていたようで、Awakeの巨瀬さんはその一局を見逃さず、対策を入れていた)

・終盤
 終盤にgpsfishにひっくり返されるという話が2chにあった。十数手の詰みを読みきれなかったとか。終盤力だけでいうと、Bonanza>gpsfish>Aperyのような気がしている。特にBonanzaは詰みっぽいほうに突っ込む傾向が強い。勝率という点だけで見ると、中盤でNPSが出たほうが良いのでAperyのほうが強いのだが、Stockfishに普通にKPP型の評価関数を乗せるとどうしても終盤弱くなるので、工夫の余地はあると思うが、それは素人考えか。
 gpsfishでは一定局面ごとにdfpnを呼び出すようになっている。これは、クラスタのセカンダリ以降で使われることを考慮しているためで、対局用としてはチューニングする余地はありそうな気はしている。
 アイデアとして、終盤の詰み発見が遅いのがbonafish型の弱点なので、相矢倉などの居飛車系にして入玉を含みにして、DFPNが動くようにすると大会などでは逆転模様になりやすいのではないだろうか。


<追記>
 電王戦FINAL,第2局の終盤について、Ponanzaの山本さんがTweetしてたが、三手ぐらい前の局面で1六角が危険だと察知するようだ。何をやったらそうなるのかは大変興味ある。こういうのは評価関数の精度をあげるしかないようなことは前に言ってたがどうなんだろうか。

84手目の局面で34秒考えると、▲13角成に△16角打でまずいと気がつくようです。 そこで方針を転換して、▲18香と戦おうとしますが・・

 ※13角成は13歩成の間違いだと思われる

 例えば5960Xで探索しているとして、34秒*2で68秒のときに、どうなるかというのは、これからWSCS出る人にはテストパターンとしてはいいかもしれない。
 程度の差はあれ、最初に13歩成を読んで、ある程度たってから1八香でその時点は100~300程度の点数というのが、どのソフトでもあるような傾向のようである。

Bonanza 6.0に追加学習のようなものの備忘録 [将棋]

前回から間が空いてしまって記憶が完全にぼやけている罠。

・論文読んでるうちに、何やってるかすっかり忘れてしまって思い出すのに苦労
 CP+とか行ってるから余計
・論文読んでる途中で別のこと試したくなったが、うかつにも学習結果を吹き飛ばしていたことが判明
 Bonanzaは学習を実行した時に容赦なく上書きされるため
 ログによれば30時間分ぐらい吹き飛ばしたことになる。もったいない。


■前提となる文献

Large-Scale Optimization for Evaluation Functions with Minimax Search

・Bonanzaメソッド(MMTO)

 目的関数:Jp(w) = J(P,w) + Jc(w) + Jr(w)

 J(P,w) = ΣΣ(T(s(p,w) - s(p,w))   ・・・(A)
  T:シグモイド関数
  準備はphase1のmake_pv。計算そのものはcalc_deriv。
  左右対称は考慮されているので、KPPは本来の状態数の2倍近い数になっている。
  また、この結果は符号の向きだけしか使われない。
  
 Jc(w):Σa(w') - 6500  ・・・(B)
  駒割りに関する拘束条件
  renovate_paramのrmt関数があるあたり
  駒の価値を変動させるときにトータルが一定になるようにすることで、数学的には収束して最小値が求められることが数学的に保証されている。(適当に調べたところ、ラグランジュ未定乗数法ではそうなるという理解)

 Jr(w):λ|w''|  ・・・(C)
  λ=0.2/32 = 1/160
  この項目自体はcalc_penaltyの全部足してFV_PENALTYをかけているところだが、更新量はrenovate_paramのrparam。
  これはL1正則化のように、あまり重要ではない要素を0に収束させることにより、重要な特徴の量を減らす機械学習の常套手段だが、正則化による変動量を目的関数に入れることによって収束の度合を指標としている
  ベクトルの更新と目的関数中のCは符号が逆なのは、そういう理由があるんだと思うがどうだろうか。加算しているが、|w|を加算したものを最小化するというのは、全部の値0になってほしいという圧力がかかっている。

というのが、現状というかしばらく前の自分の認識で、今はすっかり忘れて読みながら「なるほど」とか思ってるぐらい忘れている。

昔から変化量=微分だと思って最初からソースを見ていたが、|w|のあたりなんかは、実装としては割りと適当というか、コードとして書きやすいようになってるので、数学的には厳密ではないような気もするが、微分して定数になるので、sign関数になるというようなことでいいんだろうか。


■少数の棋譜から指し手を変化させる

これは、去年のGPWの論文がもろにあった。

「将棋での少数の棋譜からの評価関数の学習における拘束条件の研究」

この論文では1848あまりの羽生四冠の棋譜から変化させるという目的のために、新たに次の項目を追加している。(引用元のGPW2009の論文にもある)

 Jr=C/2 ||w-w0||^2 ・・・(D)

 オリジナルボナンザでは目的関数はA+B+Cであったが、この論文ではA+B+C+Dとしている。
 (以下、(D)の係数がCなので混在しているかもしれない)
 2で割って、2乗するというのは、変化量がC|w-w0|になるので便利だから。またこの形はL2正則化というらしい?。自分が少し前に書いたコードもこの形。

 この論文では、まず(C)の係数であるλについて調査している。すごい大雑把なイメージだと、

・(A)は値の絶対値を増やす
・(C)は値の絶対値を減らす

 という作用があるため、(C)の係数であるλの値によって、

・λがでかすぎると値がつかないし、
・λが小さすぎると過学習になる

 というのは、まあ当たり前といえば当たり前の話。
 そこに更に(D)という項目を付け加えると、

・(A)のために値の絶対値を増やす
・(C)のために値の絶対値を減らす
・(D)は値がついてるところはそのままにして、値がついていないところは、(C)とともに絶対値を減らす

 というような、複雑な学習になってしまって、効果が出るかいまいちわかりにくい。
 さらに、この論文では、駒の価値の変化について検討しているが、そもそも48000局の棋譜で学習してつけた値をわずか1800余りの棋譜で更新するというのはやりすぎに思える。

 ということから、論文を読む前で完全に後付ではあるが、前にやった方式もそんなに間違ってなかったと勝手に理解した。前にやった方法を、論文に書かれているように書き直すと

 ・使っている棋譜が1万程度なのでBonanzaの学習に対する影響力は5分の1程度であると見積もる
 ・(B)は一切変化させない
  実際は5分の1変化させたいが、整数だと0になってしまうので変化しない
 ・(C)は用いずに(D)だけを用いる。
  よって変化量はC|w-w0| となるが、CはFV_PENARTYそのものとした
  
 これで学習を進めていると、目的関数がA+B+Cであっても、3時間で0.001~0.003ぐらい改善されているように見える。
 今回データが吹き飛んだので、A+B+C+D形式の目的関数を作成して表示してみると、A+B+Dになる。
 今回吹き飛んだついでに目的関数を表示させてみると、

 Aが下がる
 Cが上がる
 Dが上がる

 となり、ベースとなる評価関数から乖離し始めつつも、新しい値が付いているように観測される。(過学習な気もするが)

 前は結果が出そうなのが一週間後だったので途中でやめた上に、別のことやろうとしたら吹き飛ばしてしまったので現在再学習中だが、棋譜の量から見積もれる変化量などによる推察はあっていいのではと思う。
 また、オンライン学習では、L1正則化をある程度まとまってから行うようにすると聞くので、正則化のようなことすらしないような方向もあるのではないかとも思ったのだが、こういうのを考察できるような文献が今のところ見つかっていない。

その他

・そもそもが左右対称のみを考慮した、Bonanzaオリジナルのまま学習を実行しているが、まずは完全相対化されたもので学習したほうが、より人間の感覚に近づくのではないか

・シグモイドではなく、ロジスティック関数による学習を行うことの是非
 相対化やる気力がわいたらその後にやってみたい

・全然関係ないが保護PDFなのでコピペできないので大変めんどくさい。Adobeは研究目的の保護機能を入れるべきである。

・ゲーム理論的なものへのリンクがまとめられたページが出きた

 http://www.ai-gakkai.or.jp/my-bookmark_vol30-no2/

 今コンピュータ将棋を調べようとすると結構デッドリンクだったり、話が古かったりするので(それはそれで有用なものもあると思うが)こういうリンクはよい。ただ、これが学会の一特集であるというのが残念で、もしAI学会が本気でやるのであれば、ChessProgrammingWikiのようなものはあっても良いと思うのだが・・・

Bonanzaの疑問点の調査 その2 [将棋]

調査と言いつつ、単に英語読んでるだけなのでタイトルとやってることがイマイチあってない。
本当は軽くまとめようと思ったが、結構量があったので分けたエントリのその2


■4章 Experiments

 Bonanzaについて書かれている
 Bonanzaのソースのバージョンが論文中は2013とか書かれているが、公開されている6.0は2011更新となっている謎。
 評価関数の重みは4000万(このカウント方法は後述)
 あと、ほとんどのグラフとかはGPWのどっかにはあると思われる。
 (どれも見た記憶はあるが、内容を覚えていない)

●4.1 Setup: Evaluation Functions, Features, and Game Records

・Bonanzaに取り入れられているテクニック
 PVS
 quience search
 static exchange evaluation
 killer and history heuristics
 null move pruning
 futility pruning
 late mode reduction

 全幅探索という言葉がひとり歩きしていたが、最初から枝刈りのテクニックを使っていた。(当然といえば当然なきもするが)。

 枝刈りだけ抜き出して書いてある特集
 「コンピュータ将棋における全幅探索とfutility pruningの応用」

 Blunderも似たような感じ。
 http://www.computer-shogi.org/wcsc21/appeal/Blunder/Blunder.pdf

 余談だが、今はなきBlunder公式Blogでは、Blunderに実装した探索は
 Stockfish探索よりも成果が良かったという結果を出していた。

・定跡ファイル
 自己対戦の結果らしい

・学習に使った棋譜
 48566、そのうちプロの棋譜は3万弱
 具体的にどの棋譜を使ったかが、書かれている。

・評価関数の次元
 A:駒割りのみ 13次元(駒の種類、成り駒が13種類)
 B:KP 6万ちょっと
 C:KKP 242万
 D:KPP 4422万

 ソースコード上は、左右対称であっても、高速化を考慮して、KPPテーブルは2倍の80Mになっている。

・対称性
 先手と後手を入れ替えると評価値がマイナスになる
 左右入れ替えた評価値はおなじになる

・Pの取りうる値
 状態数は1476であるとしている(shogi.hでenum定義されている値、これは非合法手を消してあるので、81*13*2より少ない)

・目的関数の値
 ノーマライズのために、すべての合法手数で割った値を使う
 (ただ、この値そのものは何かに使うわけではなくて学習効率を測る指標だと思われる)

・駒割りの制約
 ラグランジュ未定乗数法として追加してある定数項は駒割りを一定の数にしている
 fill_init_paramの中で初期値を決定している。
 他の論文によると初期値はALL500でも収束してくれるらしいが、最初から近い値のほうがよい(当たり前にも思えるが)

・sigmoidの係数
 0.0274 = 7/256 でソースに直打ちされている値
 100点差があったときに大きく動くように調整したらしい

・正則化項
 Jrの係数 0.00625は FV_PENALTY の値
 calc_penaltyで計算した値は全く使っていないが、学習がうまくいってるかどうかの指標に使っているのだろう。
 この正則化項によって、最大値が決定する。値が大きくなるほどペナルティが大きくなる。
 1/160=0.00625

・FV_SCALE
 Σ計算は32bitだが、wは16bitなので、2^5 = 32で割った値が格納されている

・更新量
 整数の最小値である1に設定している

●4.2 Learning the Piece Values

 駒の点数を計算するが、ここで、Tesauro(2001)のChessの論文の方法との対比になっている。
 Chessの論文では、伝統的な勾配降下法(conventional gradient descent method?)を使っているが、それを将棋に適用したときに2つ問題がある
 1.収束が遅い(100回回しても収束しない)
 2.定数倍で増えていってしまう
 1と2は関係しているように思えるが、学習モデルに拘束条件が入っていないので収束しない
 一方でボナメソ(の拘束条件)を使うと40回で収束する

 Figure 5は別の論文の図にあったはずなので、そっち見たほうが(日本語なので)わかりやすい

 Figure 6
 拘束条件が無いと、MMTOよりも収束が遅くなる
 2006論文などでは、収束させるには入れて当然、みたいにさらっと書いてあるが、裏付けとしてデータを載せている。

 Figure 7
 高次元ベクトルを評価関数に使う場合、オーバーフィッティングが発生している
 正則化なしでは一致率が急激に上昇するので一見ようように見えるが、そのときの0になっている値は0.2%しかなく、正則化後では96.3%になっていることが、オーバーフィッティングであるとする理由。

●4.4 強さの改善

 棋譜との一致率と強さの関係
 ここでいきなり GPS将棋の紹介
 まったく違う評価関数とのELOレーティングでの比較

 Figure 8
 GPS将棋と、KP、KKP、KPPの比較
 これを見るとKKPはあまりレーティングに寄与していないように見える(R50ぐらい)
 なのはminiはKP+PPだったが、ここはKPPのみもしくはKPP+PPPなんてやってみるとよいのではないか

 あとKPPがまだ伸びしろがあるように思える。
 NDFのように相対学習などを取り入れることによりR3000超えたりしているので、KPPはまだ点の付け方に工夫ができる余地があるということが、ここ最近の進展だろう。

●4.5 Numerical Stability and Convergence

 数値的安定性と収束
 早い話がちゃんと正しそうな値に収束するかどうかってことだと思うが、この章では駒の価値だけの評価関数を元に、連続性や、極小値に落ち込まないかどうかを検証している。

・4.5.1 Surface of the objective function

 Figure 9
 このグラフもGPWのどっかに書いてあった記憶。
 極小値があって学習が難しいよという話

・4.5.2  Empirical Convergence and Local-Minima Properties

 駒割りだけの学習だが、極小値に陥ってないかの検討
 これも別の論文があったような

 X5690で200回回すのに一週間
 200回も回せば強さにはあまり影響がないらしい

 初期値をランダムにして収束が違うか
 ある程度まではよいが、40回ぐらい回すと極小値に落ち込んでいる場合が多い

 Bonanzaがクラスタ合議をやった際に、それで強くなるのか疑問だったが強くなったというようなことがあった気がする。クラスタ合議する際に、ランダムな初期値を与えて合議させていたので、極小値回避をしていたのだと思われる。

 Figure 11
 自分が回した時はサーチデプスが2だったのもあるが、目的関数が0.1程度だったが
 0.165付近で止まってるので、これは調査用の学習だろう。

■4.6 Performance of MMTO under Tournament Conditions

 世界コンピュータ将棋選手権でボナメソ使ってるソフトが活躍してるぜという紹介
 ここにBonanzaの初期バージョンはL2正則化をしていると書いてある
 2006論文ではL1だったような記憶が若干あるのだが。
 あとNDFが古いタイプの学習になってるのだが、Bona6ベースだからAdvanced MMTOといってもいいのではないか。

 もう一つ、Bonanzaのソースに入っているランダム性についてここに書かれている。
 このランダム性をいれることことで評価関数の品質が上がるかどうかは不明であるとしている。(ちょ
 だったら、自分みたいなニワカマンの場合、下手にランダム無い方が計算速くていいのではないか。
 (実際は評価関数のほうが時間の比率は大きいから誤差みたいなもんだとは思うが)

■4.7 Preliminary Experiments on Chess

 チェスのプログラムにMMTOを適用
 チェスは凝ったプログラムが多いので比較が難しい的な話

■4.8 Data Quality Dependence

 Table 5
 強い棋譜を使うと強くなる的な話
 これを推し進めると、コンピュータ同士の強い棋譜で学習したらつよくならんの?
 と思ってちょっと走らせてみたが前々回ぐらいのエントリ
 時間がかかりすぎたのでやめたが。
 そもそも相対学習からの絶対学習で強くなるのがわかってるのだが、棋譜を用意がFloodgateのほうが100倍楽なので、何か思いついたらまた試してみたい。

■5 Coclusion

 まとめ
 二人ゲームにおいてMMTOは有効

■Appendix

 数式だらけなのでパス


■雑感

・KKPいらんのではないか
 R50減ったとしても、その分速く読めればとんとんだったりしないのだろうか。

・棋譜
 かなり正確に書かれていたので、同等の棋譜が用意できれば、同じぐらいの強さの評価関数は再現できるだろう

・実はもっとがっつり変化させられないか

 この論文の主張では数値的に安定的にするために少しずつ学習する方法をとっているが、GPS優勝後のPPTによると、評価関数や学習方法を変えた時に、不連続性があってもうまく行ったようなのが書いてあった。ただ、GPW2008のものではイマイチっぽいかかれ方をしててよくわからず。

・GPSの学習方法との比較がなかった

 GPSはGPSで式を変えていたが、どっちがよいかというような比較が無かった。
 せっかく共著なのでそういうのも期待したかった。


Bonanzaについて一つにまとまっている論文を全部ひと通り読んでみたが、ソースコードだけから読み取ろうとした数字などについて解説があり、納得できた面もあるが、謎な部分もある。

まとめてたら、エントリも長すぎて途中で気力がつきかけたので、間違っている部分もあるかもしれない。

論文読んでたら、「Bonanzaよりは強くなるのではないか」という方法が4つぐらい思いついた気がするが、メモらなかったので忘れてしまった。

1個はKPP無しかな

思いついたら追記するかも。


そもそも、なんで読もうと思ったのかを忘れていたが、少し前にやった部分学習的なことの方針が合っているのかどうかを確認したかっただけだったが、論文のボリュームがあったのと英語の読解力不足で時間がかかった。

部分学習するときにいくつかの固定パラメータをうまく調整する必要があるはずで、カンで調整したところが、本当に調査どおりなのか確認してみたが、概ねあっていたように思う。

Bonanzaの疑問点の調査 その1 [将棋]

ソースだけ見ててもコメントが入ってないので、
その数値はどうやって決めたのかというのがよくわからなかったが
そもそもほとんど解説してる論文の存在を忘れていた

Kunihito Hoki and Tomoyuki Kaneko, Large-Scale Optimization for Evaluation Functions with Minmax Search, Journal of Artificial Intelligence Research, 49, 527-568, 2014.

電子書籍の悪いところとして、タブレットに突っ込んでおいて忘れるという、未だ生活スタイルに馴染んでいないのだが、これもまさにそのパターンでつい最近まで完璧に忘れていた。

この論文は、将棋を知らない外国人が読んでもわかるように書いてあるため、いまさらBonanza 6.0のソース読んでる自分が完全に欲しかったものであり、疑問点はほぼすべて書いてあった。

2006年のGPWの発表論文などでは、Bonanza 1あたりについて書かれているため、パラメータが1万とか書いてあって、今と同じなのかという疑問があったが、この論文でも学習方法の大筋は変わっていないようであった。なので、英語はチョットと言う人は、日本語の発表論文のほうを読んでからのほうがわかりやすいと思う。

■1章 序章

 Chessにおける機械学習の歴史と、この論文のポジション。
 世界的にはChessのほうが研究が盛んなので、それらの成果との対比という書き方になる。
 この論文ではBonanzaメソッドはMinmax Tree Optimization(MMTO)と書かれている。

 余談だが、小保方問題のときに、序章は先人の積み上げた歴史なかでこの論文でどういう発見があったかを書くものなのでコピペはありえないと、どこぞの研究者がキレていたのを思い出した。

■2章 関連事項

 他の方法の紹介とその方法ではダメでMMTOならいけるというような話

2.1 チェスにおける学習の枠組み
2.2 他の評価関数学習方法
2.3 学習とnumerical optimization
 numerical optimizationの訳語がわからない。数値最適化だろうか

■3章 Minmax Tree Optimization

 ボナメソの説明

3.1 目的関数の最小化

 これは2006の論文などにも書かれている内容をより正確に書いてある(と思う)
 英語で分からない人は先に2006のほうを見ておくとすんなりわかる(はず)
 疑問点:sigmoidのaの符号が-になっていない理由
 微分するからどうでもいいっちゃーどうでもいいような?

 Figure 2の説明と、該当ソースコード
  1. Phase 1のmake_pvあたり
  2. Phase 2の前半、calc_derivあたり
  3. Phase 2の後半、renovate_paramあたり

 チェスの学習方式との違い
 Heaviside関数 => sigmoid関数
 評価値の差 => 探索結果の評価値の差
 目的関数に拘束条件が入っているのが重要
 最後のセンテンスは不明(学習を進めるとPVノードが固定化されるような意味合いだろうか)

3.2 定数項と一般項

 目的関数にあった拘束条件?の部分の説明
 チェスでは一般的にSinged 16bit Integerが使われる。(KKP/KPPとかもShort)
  置換表に格納するのに丁度よいためらしい
 チェスにスケール合わせる
 拘束条件とかL1正則化について書かれているがよくわからん

3.3 偏導関数近似?

 3.2の考えに沿って導関数を偏微分して拘束条件などを考える
 探索結果は微分可能であるとは限らないため、近似を行う
 近似によってエラーは出るが影響は小さい(らしい、別の論文がある)

3.4 格子隣接アップデート

 評価関数のアップデートのこと
 今のBonanzaのように符号の向きだけを使うようにすることで、目的関数を最小化させて、近似によるエラーも無視できる

 がっつり移動しない理由

Although MMTO focuses on optimization of weight vectors represented by integers, it should be noted that the gradient descent update is not suitable even when one uses oatingpoint feature weights


 (超訳)本来であれば微分であるので浮動小数点を使って調整するべきであるが、最終的な結果は整数で扱うので調整方法を十分に小さい整数にする。

3.5 実践的な事項やテクニックの組み合わせ

 実装されているパラメータなどの説明

3.5.1 ラグランジュ乗数

 ラグランジュ未定乗数項をどう設定するかという話だろうがよくわからん。
 話としては、駒割りの総計を一定数(変化量を0)にすることで、望ましい結果を得ようという拘束条件について書かれているはず。具体例は4章。

3.5.2 探索深さ

 make_pvで探索を行うため、MMTOで一番時間がかかる処理である
 静止探索を使うとよい=より深く探索するほどよい
 現実的な問題として一手探索+一手静止探索
 学習が進んで探索の幅?が狭くなっても深く探索するのは効果がある(4.4)

3.5.3 効果的な学習のためのPVの再使用

 イテレーション32は経験的に決めた。多くのPVが変わらないように十分小さい値にするべき。
 個人的には32は固定小数点の数と一致させたのかなと思っている

3.5.4 枝刈り

 枝刈りによって学習に必要な探索が劇的に削減される
 αβ探索では枝刈りによって不連続になることはないが、Futility Pruningでは不連続性が発生しうる
 Futility Pruningを使った時にも評価関数が強靭であるか評価するべきである
 経験的には問題がない

3.5.5 収束の判定

 収束の判定は難しいのでレーティングで判断する?

3.5.6 重複する局面と代替手?

 同じ局面が何回も出てきても1回にカウントする(実装にはZobristHashを使う)?
 同じ局面で複数の手が指された場合には、互いの学習が打ち消し合ってしまう。
 経験的にはそれでもうまく動いているが、他の種類のゲームではうまくいかないかもしれない。
 (MMTOは将棋だけでないという主張なのでこういう書き方になっていると思われる)

4. Experiments(やったこと?)

 ソースや学習などを実際にやる人はここからが本題
 細かいパラメータや評価関数の形式など、ソースにある不明な点はここからが本題なのだが、その2の予定。


元々Bonanzaのソースは個別の話題があったときに流し見してた程度だったので、一般的に言われているようなことしか知らなかったが、今回学習とか高速化を少しやった上で、疑問点がいつくかあった状態で読んだのでかなり理解できた(気がする)。

 GPSの金子さんとの共著になっているので、元の論文があるのではないかと思ったが、GPW2008で方法論の整理だったりとか、GPW2010でチェスとの比較だったりとか、理論的な体系を確立するのに必要そうな論文を複数だしていて、そういうのを全部まとめたのが今回の論文だったようだ。

■現状のまとめ

 シグモイド関数の正負が逆なのだけは理解できない。

 文章中に「in our experiments」みたいなことが結構多いが、過去のGPWの論文では、そのへんを考察しているようだ。

 「がっつり変化させる」ということに対しては、この論文からは否定的な結論になっている。GPSのソースのコメントにも、ボナメソのほうが結果が良い的なことが書かれていた。


Bonanzaの一部学習 [将棋]

いろいろ修正しながらBlogのエントリを書いていると、タイムアウトで消えるのだが、見事に消えたので、部分的にだけ。

大して手間を掛けずに、ちょっとだけなんとかならんかというのが趣旨。

・FloodgateのR3000超(と思われる)の棋譜を抜き出す
 akiさんのBlunder.Converterを改造して作成。
 当初、強そうなプレイヤーだけ全部集めてrecords.csaを作ろうと思ったが、めんどくさくなってgpsfish_Xeonにマッチした棋譜だけ抜き出した。
 また、学習では複数の棋譜を1つにまとめたrecords.csaが必要なのでそれを作れるようにもした。
 大体1万局ぐらいがヒット。
 両方強いプレイヤーのほうがいいんじゃね?という意見には、floodagateがレーティング調整してくれているから、自分はやらなくてよいという考え。あと機械学習には枯れ木も山の賑わいという面がある(はず)

・それを学習に使用するが、本来の学習の棋譜(4万8千)に比べて5分1程度なので、未知局面が多いと思われるので、元々ついていた値は正しいだろうという前提で学習させる

・2,3日学習させた
 akiさんのFVAnalyerによると、非ゼロ率が16%=>36%ぐらいになったので、ある程度効果があったように思われる。
 また、絶対最大値が360に対して1回1点程度の変動しかないので、指し手に影響がでるぐらい学習するとなると、300回ぐらい回す必要があり、1回3時間なので、40日ぐらい必要となる。(ので途中でやめた)

・オリジナルBonanzaとの対局
 中盤の評価値が思ったより差が出ている。
 一応56-1-43ではあったが、上記のように指し手に影響が出ているわけではないと思うので、ただの誤差だろう。
 ただ、中盤の点数がついてるような感じなので、boNanohaと組み合わせるとより効果が出てるかもしれない。


Bonanza6.0の棋譜からの学習 ~左右対称はありまぁす~ [将棋]

去年レーティングがすごい伸びたのは
以下がきっかけだったのかなと予想している。

http://www.computer-shogi.org/wcsc24/appeal/NineDayFever/NDF.txt

相対化を学習に取り込んだところ良かったらしい
(複数の変更があるのでどの程度良くなったかどうかは不明)
では、Bonanzaはまったく相対を考慮していないのかというとそんなことはなかった。

Phase1
・棋譜を今の評価関数で評価する
・指し手の中である程度有望そうな手を更新予定として保存する
 (ここはあまり自信がない)

・Phase2
 Phase1の結果から、評価関数の更新量を計算する
 ここがちょっと特殊

・終了処理
 左右対称の更新量を合算する
 駒割りが発散しないように調整する
 L1正則化っぽいことを行う
 学習元のfvテーブルを更新する
 評価関数に使う駒割りの差分を更新する

となっている。

ここでの合算というのが、計算をし終わった上で合算しているので
本当にそれでいいのかは理解できていない。
数をこなしているうちに収束するから大丈夫だろうということだろうか。
また、Bonanzaの更新量はシグモイド関数とみせかけて違うのは
合算しても問題ないようにしたのかもしれない
(あと仮定として学習によって更新しても指し手が変わらないので
 あんまり急激な変更は入れたく無いというのがある気はする)
<下記に追記しました>

それはともかく、最終的な結果として左右対称の場合は値が同じになるように調整されている。

これをさらに一般化して完全に縦方向も相対化したというのがNDFのアピール文章で
相対化の後絶対学習をさせ、そのときに相対化された項目の値が残るように
目的関数を設計しているようである。

また、少ない棋譜での学習については以下の様な書き込みが2chにあった。

508 名前:名無し名人[sage] 投稿日:2015/01/12(月) 07:22:18.60 ID:xPf01yZ4 [1/2]
棋譜はとにかく数が多くないとダメっぽいね
2000局位(羽生さん多め)を追加学習させてノーマルbonanzaと100局対戦させてみたら勝率4割程度しかなかった


自分も追加で学習を繰り返していけば強くなるのではないかと思ったが
それこそ素人の浅はかさで、すべての学習に使った棋譜+問題の棋譜のようにしないとうまくいかないし
部分的に追加された項目が指し手に現れるかというとまず現れない。

これは、今のBonanzaの学習ルーチンの設計がそうなっているからで
具体的にはPhase2が終わって最後の計算をする前に
ペナルティ(ノイズを消す)がかかっていて、そこで消されているからであると思われる。
(具体的にはrparam)

大雑把に書くと

・数万局の棋譜で指し手の頻度を調べる
・指し手の頻度に応じてパラメータを更新する
・ノイズを消す(ペナルティ=少し減衰させる)

となっているので、今の関数に部分的に学習したいと思っても
最後のノイズを消す作業によって、微妙についていた値が全部消されてしまって
のっぺりした評価関数になっていると思われる。

やねうら王Blogでペナルティを何とかしたいようなエントリがあった。

http://yaneuraou.yaneu.com/2015/01/08/%E3%81%9D%E3%82%8C%E6%9C%AC%E5%BD%93%E3%81%AB%E9%81%8E%E5%AD%A6%E7%BF%92%EF%BC%9F/

ボナメソでは出現しなかった特徴因子の値はゼロに収束するようにしてあります。ところが、iterationをある程度回すと、それぞれの棋譜のそれぞれの局面のPVは固定化してきてしまい、いままで出現していて、きちんと値がついていた特徴因子も出現しなくなるので、これらがすべてゼロに収束していく現象が起きます。


少ない棋譜から学習したり、効率をあげるには何かしらのアルゴリズム的な変更が求められる。
=>もしかして:オンライン学習

<追記>
妙にRTされたので少し補足

局面評価の学習を目指した 探索結果の最適制御
http://www.geocities.jp/bonanza_shogi/gpw2006.pdf

変化量はsign関数なので一定量しか動かないようになっている
http://ja.wikipedia.org/wiki/%E7%AC%A6%E5%8F%B7%E9%96%A2%E6%95%B0

将棋の棋譜を利用した,大規模な評価関数の調整
http://www.graco.c.u-tokyo.ac.jp/~kaneko/papers/gpw08.pdf

軽くBonanzaの学習方法について触れられているが、考え方は概ねあっているようだ。

ただ、基本的な考え方は同じではあるが、
この当時のBonanzaは1.0ぐらいだと思われるので、いまのとは当然形が違う。

PPTによれば変化量は一定のように書かれているが、
Bonanza 6.0の最終的に値を更新していると思われるrparam場所では
乱数を利用して学習している。(RはRandomの略だろうか)

これは合議などを行う際に、全く同じ結果で合議しても意味が無いことから入っている乱雑さだと思われる。
更新量は変化の度合いに関わらず、正負だけで

0 : 25%
1 : 50%
2 : 25%

の範囲で更新するようになっている。後手番だと負の値になる。
なので、この部分を合議するつもりがなかったり、さっさと収束させたい場合は

*pv += dv;


のようにしてしまえば、あっという間に過学習気味に終息すると思う。
元々のdvがシグモイド関数の微分値から求められているので、
これでも案外いい線いくのではないかと予想している。
(GPSの学習も微分不可能なのに微分可能であるとして
大胆に学習させてそこそこうまくいったような論文があった)

そして、このような学習方法であることと、先日やねうら王Blogが書いてあったコードを見ると、やねうら王の学習パラメータの一部を勝手に推測できる。

http://yaneuraou.yaneu.com/2014/12/30/stockfish-dd-bitcount-h/

私は棋譜からの学習のときに評価因子に正規分布っぽい乱数を加算するのに、popcount(rand() & 7) とかやってますが(二項分布≒正規分布なので)…まあ、こんなところはたいした問題ではないですね。


この表現こそまさに今のrparamの中でやっていることだと思われる。

& 7となっているので、0~255の値で中央値は128ぐらい。 FV_SCALEをそのままだとすると4点ぐらい一気に動かすようにしていたりするのだろうか。
<追記の追記>
ビット数えてるので、0~3でした、Bonanzaよりも1点だけ多く変動するだけでした。orz
<追記の追記終わり>
<追記終わり>