Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

GT-Rの買取ならここですわ。どこよりも高く買取ってもらえるはず。お勧め!GT-R 買取
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 | 

2014-04-10 電王戦 第五局 Ponanzaの意外な弱点

[] 電王戦 第五局 Ponanzaの意外な弱点  電王戦 第五局 Ponanzaの意外な弱点を含むブックマーク  電王戦 第五局 Ponanzaの意外な弱点のブックマークコメント


※ この記事は電王戦 第五局が始まる3日前に書いている。


Ponanzaが他のどのソフトより一回り強いソフトであることには誰も異存はないだろう。

ノーパソ人間の強豪相手に166連勝とか凄すぎて言葉も出ない。


そんなPonanzaだが、開発者山本君自身が「銀ばさみ」を弱点として挙げている。


f:id:yaneurao:20140410022728p:image

https://twitter.com/kagami_tomo/status/452827971808534528


初めてこの話題を聞く将棋ファンにとっては「これだけ化け物級の将棋ソフトが銀ばさみなどと言う初歩的な手筋を食らうはずがない」と考えるだろうが、銀ばさみを食らいやすいというのは本当のことなのだ


ライト将棋ファンのために説明しておくが、銀はさみというのは次図のような形で銀が死んでいることを言う。


f:id:yaneurao:20140410022729p:image


歩がタダ取りできると思って銀で歩を取りに行ったときに、銀の前に歩を打たれて上図のような形となり、あえなく銀がご臨終となる。


実は、従来から将棋ソフトは銀ばさみを食らいやすかった。理由はいくつかあると思う。


・理由1 銀ばさみされた形は部分的はいい形である


例えば、Bonanza型の評価関数では3駒関係の評価をしているが、このなかで、銀ばさみの形はどう評価されるか。(いま2駒関係は問題ではないのでそれについては考えない)


Bonanzaの3駒関係」というとき、1枚は玉であり、残り2枚がここでは銀と歩なのだが、銀ばさみの形は部分的には、たいていはいい形として評価してしまう。


f:id:yaneurao:20140410022732p:image


例えば、歩の裏から香を打つような形は(香を打つ側にとって)いい形である。これは歩が合い駒できないからだ。


f:id:yaneurao:20140410022730p:image


同様に、銀ばさみの形も、次に歩の裏から歩を打てたりして(次図)部分的はいい形なのだろう。


f:id:yaneurao:20140410032713p:image


そもそも銀が出て銀ばさみに遭って銀が無条件でタダ取りされるような形での銀の進出はプロの実戦棋譜には出てこない。本当に無条件でタダ取りされるなら、プロはそんな進行は避けるからだ。銀が出るからにはそれ以上の代償があるときのみである。だからプロ棋譜から評価関数パラメーターを学習させたときに銀ばさみになっている形に対してなかなかマイナスの値がつかない。


同様に、棒銀などで攻めに行って敵陣の形を乱す代償に銀をタダ取りされてしまう指し手がソフトに多いのも実戦(プロ棋譜)には成功事例しかないからなのかなという気が少しする。


・理由2 銀ばさみした銀をとった形はすこぶる悪形である


次に、銀ばさみした銀を歩で取りきった形。これが銀を取った側から見てすこぶる悪形だということ。将棋には「位(くらい)を取ったら位の確保」という格言があるが、浮いている歩がいくつも並んでいるのはよくない形なのである。銀を取った側が瞬間的にすこぶる悪形なのでこれが形勢評価を誤らせる一因となる。


従来のソフトが銀ばさみに弱いのは、おそらく上記の2つの理由が大きいのではないかと思う。


しかし、Ponanzaが銀ばさみに遭いやすいのは、もう2つぐらい理由があると私は考えている。それというのも、いま開発中の新やねうら王も銀ばさみにやたらと遭うのだ。やねうら王の開発中のもの将棋倶楽部24に放流しているのだが、まだ200局すらしていないのにすでに3回も銀ばさみを食らっている。最初バグか何かだと思ったのだが違うようだ。そして、どうもその原因はPonanzaと根が同じものだと思う。それについて簡単に説明する。



・理由3 銀ばさみしたあと歩を打って銀を殺す手の形が悪すぎる


おそらく統計的に見て、歩を自陣に打つ手が好手である確率というのはあまり高くない。歩は本来ならば敵陣に使いたい。それを自陣に使うのは、他の指し手では悪くなるので辛抱をするときがほとんどである。そこで、自陣の歩は形としてそれほどプラスにはなっておらず、また、指し手のオーダリング(探索する順番を決めるための順序付け)をするときにも打ち歩は低い順序になりやすい。そのため、探索部で激しく枝刈りをしているタイプの将棋ソフト(※注1)では、これが枝刈りの対象になりやすい。このため、思考時間が短い設定だと、たかだか7手ぐらい先であっても見落としてしまうのだ。


※注1 「Ponanzaは(他のソフトに比べて前向き枝刈りで)刈りすぎ」というPonanza山本君の発言が2年ぐらい前にあったと思う。Ponanzaの枝刈りがかなりきつめに調整されているのは特徴的で、それゆえこういう指し手が枝刈り対象になっているのかと思う。(やねうら王も実は他のソフトよりは少しきつめに調整してあるつもりだが、あまりきつくすると読み抜けて弱くなるので、私にはこの調整が難しい。Ponanzaはこのへんを実にうまくやっているのだろうと思う。)


・理由4 銀ばさみにしたあと銀を殺すために歩を打つ地点に他の駒を運ぶ手は悪手である


やや専門的な話となる。理解できない人は読み飛ばしい欲しい。


ある局面で指し手のオーダリング(探索する順番を決めるための順序付け)をするときに「この升に駒を移動する指し手はいい指し手である可能性が高い」というように移動先の升ごとに点数をつけた表を用いる。それをhistoryテーブルと言う。激指が実現確率探索で指し手の実現確率を求めるためにやっていたようなことを、より小さい労力で行なうためのアイデアである


これは、探索中にいい指し手であったときにこのhistoryテーブルのその(指し手の移動先の)升に加点し、いい指し手でなかったときには減点する。そして指し手のオーダリングにこのhistoryテーブルに記載されているスコアを使うわけであるが、銀ばさみにした形は、歩を打って銀を殺す升に移動できる駒として、銀を殺す側から見て、普通は金のような支えとなる駒が背後にあるはずである


ところが、金をこの升に運ぶと金銀交換になるため、historyテーブル上は、この升へ駒を運ぶ(打つ)指し手は減点されているはずである。だから、この升に駒を打つ指し手の探索順序がかなり後回しになり、指し手オーダリングで後ろのほうの順番になっている指し手は枝刈りしてしまうので(前向き枝刈り)、ざくざく枝刈りしているタイプの探索ではどうしても読み抜けるのである


Bonanzaのhistoryテーブルは、駒の移動元の升(=81)と駒の移動先の升(=81)のペア(組み合わせ)なので、81×81のサイズ配列(≒表)が必要となる。(実際にはさらに移動させる駒の種類とか駒打ちであるかとかも考慮されてたと思うが話がややこしくなるのでここではそれは考えないものとする)


Bonanzaではこのように移動元を考慮に入れたhistoryテーブルなので上述の問題は起きないのだが、Stockfish型の探索など現代風の探索部では、historyテーブルは移動先の升しか考慮に入れないのが主流であるから(historyテーブルを小さく抑えてメモリ効率を良くするため)、移動先の升が同じである複数の指し手があり、そのなかの1つだけが良しでそれ以外はすべて悪いというような時にこの1つだけ良しの指し手を見落とす傾向がある。(ちょうど銀バサミからの打ち歩がこの条件に該当する)


また、駒打ちと駒打ちでないかでhistoryテーブルの使う場所別にすればこの問題は回避できるかも知れないが、たいていは駒打ちでも駒打ちでなくとも急所の升に駒を移動させる(駒を打つ)指し手は良い手であるから、そういうことをしてもhistoryテーブルのサイズが大きくなるわりには探索効率が落ちかねない。そもそも自陣に駒を打つ手はほとんどの場合、悪手であるから、historyテーブルをそういう風にわけても、打つことに関するhistoryテーブルのスコアはほとんどがマイナスになりかねない。結局はそういう指し手は枝刈り対象になりやすい。


から現代風の探索部においてはhistoryテーブルでは指し手の移動元や、指し手が駒打ちであるかなどは考慮しないのが普通だと思うのだが(※注2)、そうするとこのような問題があって、ちょうど銀ばさみに関してこの問題が露呈しやすい。


※注2 ちなみにコンピューター将棋開発者の用語で、指し手に関して駒の移動元をfrom、駒の移動先をtoと呼ぶ。Ponanza山本君と数年前に話したときに、「(Ponanzaでの)history?ああ、toしか見てません。Bonaはfromとかも見てますよね。」という言葉があった。このことから、4)はBonanzaには当てはまらず、Ponanzaには当てはまる特徴だと言えると思う。(最新のPonanzaがどうなってるのかまでは知らないが、ここをいまさら複雑化しているとは思いがたい) ちなみに、やねうら王もtoしか見てない。


・とは言うものの…


将棋の探索部はいろんな要因が複雑に絡みあっているので、本当に銀ばさみに遭いやすい理由が、上記の4つなのかどうか私は正直自信がないし、きちんと調べたわけでもない。「このへんが原因なのかな?」という私の推測にすぎない。以上の話は、開発者の間での議論のための叩き台にでもしてもらえればと思う。


あと、電王戦本番でPonanzaが銀ばさみに遭うかというと、思考時間が長ければさすがに5手か7手先ぐらいはほとんど枝刈りせずにきちんと調べるだろうから普通に回避できると思う。つまり、「将棋ソフトが銀ばさみに遭いやすい」というのは、「思考時間が短いときに」という但し書きがつく。


以上、電王戦本番でも他者を寄せ付けない圧倒的な強さを見せつけるであろうPonanzaにも意外な弱点があるんだよねという程度の記事でした。

電王戦本番でPonanzaが銀ばさみされるところが見れるのかと思った人、すみません


■ 関連記事


やねうらおさん、コンピュータ将棋の銀ばさみについて解説 「電王戦 第五局 Ponanzaの意外な弱点」(2ch名人)

http://i2chmeijin.blog.fc2.com/blog-entry-524.html

→ やねうら王が銀ばさみに遭った局面図とか、本記事に関するtwitterでの言及などがまとめられていて凄くわかりやすい。


Ponanza現在課題 (3) 銀ばさみの理解(ぶたろうノート)

http://emptywords.hatenadiary.jp/entry/2014/04/11/004046

→ 「電王ponanzaに勝てたらノートパソコンプレゼント挑戦者求む![ドスパラ大阪なんば店]」のときニコ生の放送の文字起こしPonanza山本君自身が、Ponanzaが銀ばさみされやすいということについて将棋ファン向けにわかりやすく語っている。

aa 2014/04/10 05:14 :%s/Bonanzaではさらに/Ponanzaではさらに/c

yaneuraoyaneurao 2014/04/10 05:28 ↑本文、その部分、わかりにくかったですね。読みやすいように少し本文を修正しました。

Ta(ryTa(ry 2014/04/10 09:16 そなんだ。

takashitakashi 2014/04/10 11:02 将棋ソフトは、このような明らかに不利になる局面の評価を特別に調整して悪手を避けるようにプログラムしないのかな?
歩と歩の間に銀が入る手は-500を加えるとか。

nanasinanasi 2014/04/10 12:43 伊藤電王も『私もだいぶ昔には、たとえば「銀ばさみの形をマイナス」などというのをいちいちプログラムしていたこともありますが、だいたいそういうのは非常に限られた局面しか効果がなく、勝率でいうとほとんど変わらないものです。』と語ってたけど、弱点狙ってくる人間相手の一発勝負とかだとやっぱりこういう個々の地道な調整が必要なのかも

がーすーがーすー 2014/04/10 19:28 今日の記事も非常に面白く興味深かったです。理由4がとくに。
from無視history利用による検索効率化の弱点が、駒打ちの無いチェスでは顕在しなかったが、駒打ちのある将棋では顕在化したとも言えるのでしょうね。実際に銀バサミにあわずとも、探索した先で局面評価に失敗しているケースも多々あるのでしょう。
探索の弱点と考えて探索面で対策するのか、評価関数の弱点と考えて評価関数面で対策するのか?
銀バサミだけについて対策するのか、(質的に共通点のある)他の弱点も含めて解消できるような対策を目指すのか?
いろいろなアプローチが考えられそうで、今後プログラマーの方々がどう対応されるのか、も楽しみです。
銀バサミを喰らいやすい理由に関する仮説の実証は困難だと思いますが、例えば、N4という4駒関係のソフトがあると聞きましたが、N4に「読みは浅いのに銀バサミを喰らいにくい」という特徴があれば、一つの傍証になるかもしれないと思いました。
それと、銀バサミを喰らいやすいということは、裏を返せば、銀を呼び込んで銀バサミを喰らわせる手筋を使うのも苦手ということなんでしょうか?

yaneuraoyaneurao 2014/04/10 21:44 ↑ > それと、銀バサミを喰らいやすいということは、裏を返せば、銀を呼び込んで銀バサミを喰らわせる手筋を使うのも苦手ということなんでしょうか?

そうなりますね。ただ、そっちは銀ばさみにする局面自体を回避することになるだけなので大きな損害にはなりにくいのでそこが銀ばさみされる側とは非対称なんですよね…。

yaneuraoyaneurao 2014/04/10 22:10 何故か本記事がGIGAZINEで取り上げられていたのでメモ。

2014年4月10日のヘッドラインニュース(GIGAZINE)
http://gigazine.net/news/20140410-headline/

yaneuraoyaneurao 2014/04/11 00:33 ここのコメントで指摘があったので、3),4)はBonanzaに該当せず、Ponanzaには該当する根拠について、本文中に注記しときました。

なおこのコメントは24時間後に手動的に消滅する..

はっほーはっほー 2014/04/11 18:53 投稿とは関係ない質問ですいませんが、やねうら王を公開する予定はありますか?

yaneuraoyaneurao 2014/04/11 20:14 ↑無償公開するか、スマフォ版にするか、ブラウザで遊べるものを作るか、二回りぐらい強くしてから商品化するか…など考え中なんです。

やれやれやれやれ 2014/04/12 01:37 ニコ生の書き起こしがあって良かったですね。33,4の根拠について、2年前の発言に基づいているのでツッコもうかと思ってましたがwww

観戦者n号観戦者n号 2014/04/12 18:58 非常に興味深いエントリでした。
極論を言えば、今のCOMは「ミスをしない人間以上にはなれない」もしくは「開発者の意図した以上にはなれない」のですね。

123123 2014/04/13 00:22 電王戦お疲れ様でした。記者会見もお疲れ様でした。
爆裂トーク面白かったです。竹内さんの苦笑い込みで(笑)
MVP磯崎さんに投票しましたが、、、まあ、あの結果はしょうがないですね。
また以前の様な笑顔の磯崎さん見られる日を楽しみにしております。
もちろん来年も出られますよね?
やねうら王の商品化、アルパカのように首を長くしてお待ちしております。

aa 2014/04/13 00:26 銀ばさみの弱点は現代風の評価関数と枝刈りチューニングにある原理的問題が浮き彫りになったものなんですね。

エントリと多少内容は変わりますが、やね裏学習メソッドIIでは思考時間を増やして得たより良い結果を記録していますよね?人間の学習過程と比較してみると、感想戦等で局面を検討してより良い指し手を発見しそれがゆくゆくは定跡につながっていくことと対応しているのだと思います。

一方で、人間の場合、特に成長段階では定跡や検討結果の記憶だけではなく同時に大局観(≒評価関数)も洗練されていきます。現在、評価関数のパラメータは棋士の棋譜から学習していますが、ソフトの質が棋士に近づいた現在、ソフトの棋譜もその対象に出来ると思いますがいかがですか?(色々工夫の余地がありそうですが、例えば評価値が大きく変動した前後n手の局後検討結果抽出など。)

そうすれば自動対戦(24でもfloodgateでも)で継続的に進化させられますし、ソフト個別の弱点にも対応できるかもしれません。

もちろん、現状の評価関数のパラメータ規模では学習が飽和してしまう恐れが強いですし、重量化はnps低下による棋力低下のジレンマを抱えていますから簡単ではないですが、人を模倣するならば自然な方向性に思えます。

cscs 2014/04/13 02:19 記者会見お疲れ様です。
磯崎さんの話していた内容の結論は「今のルールだと良い勝負にならないので、棋士側によりハンデをあげるべき」ということなんでしょうか?
まあ、そうしないと勝負にならない時代にすぐにでもなりそうですが、正直見ていてヒヤヒヤしましたw

トラックバック - http://d.hatena.ne.jp/yaneurao/20140410
 | 

1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06