Hatena::ブログ(Diary)

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

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

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

 | 

2014-04-06 電王戦 第四局 ツツカナ戦について思うこと

[] 電王戦 第四局 ツツカナ戦について思うこと  電王戦 第四局 ツツカナ戦について思うことを含むブックマーク  電王戦 第四局 ツツカナ戦について思うことのブックマークコメント


第四局は、将棋の内容的にも非常に素晴らしい戦いだった。両者の力が存分に発揮された白熱した戦いだった。矢倉の達人、森下卓先生矢倉で勝つ。棋譜だけ見ればツツカナ側が森下先生ではないかと思ってしまうほどだ。


森下先生は事前対局はそれほどされていなかったようなのだが、ツツカナ比較的事前研究されると弱点が見つかりやすいのではないかと私は思う。ちょっと、私の考えの道筋だけ書いておく。


今回のような貸し出しアリのルール場合ファミコンゲーム攻略のようにしてプロ棋士側が勝率を最大化しようと思ったときに、コンピューター同士対戦させるという方策がまず考えられる。どうせなら、本番と同じ持ち時間で対戦相手のソフトを一番強いソフトと対戦させておくほうがなお良い。これを最初に言い出したのはプロ棋士西尾明六段だと思うので、ここではこれを西尾戦略と呼ぶことにする。


f:id:yaneurao:20140406221605p:image

https://twitter.com/nishio1979/status/447558853253529600


f:id:yaneurao:20140406221606p:image

https://twitter.com/nishio1979/status/447561125853290496


f:id:yaneurao:20140406221607p:image

https://twitter.com/nishio1979/status/447573579261943808


ところが、よく考えると、序盤でコンピューター側の指し手がバラけると研究対象局面が増えて損である。そこで、西尾戦略の前に、まずコンピューター側の定跡がどこまで入力されているのがその樹形図(初手からの定跡木)を作成したほうが効率が良い。


ソフトによってはある局面での定跡の指し手は1手しか入っていないことも多々あるし、今回のような貸し出しルールのもとでは、不利と結論の出ている局面まで進んでしまうことを開発者としては恐れるので、定跡を早めに打ち切っていることがある。だとすれば、先手側が人間であれば、樹形図を使えばソフト側の定跡を抜けた局面を数局面限定することは十分可能である


それらの局面研究対象として研究するほうがはるか効率が良い。そこで、それらの局面から強いソフトと本番の持ち時間で対戦させてみるという西尾戦略を採ることを考える。実際には西尾戦略樹形図作成を交互に繰り返しながら、研究対象局面の深さ(初手からの手数)をどんどん深くしていくと良い。


そうしたときに、ソフト側の指し手がバラけるソフトとバラけないソフトとがある。指し手がバラけるように調整しようと思うと、きつく乱数を入れないといけないので弱体化してしまう。ソフト人間よりはるかに棋力的に上回っているなら、R50〜R100ぐらい弱くなっても誤差かも知れないが、まだそういう状況でもない。局後学習は、弱体化させずにランダム性を入れるという意味では面白いアプローチだが、本当にこれで事前研究回避できるかは定かではないし、比較的実装が面倒なので私以外の開発者が進んでこれを導入するとはあまり思えない。


また、乱数調整をしていない場合、長い思考時間において指し手がどの程度バラけるのかという部分はあまり知られていない。一般的に言って思考時間が長いと、指し手は特定の指し手に収束する傾向がある。(例えば、終盤で羽生先生激指の指し手一致率が90%を超えることがある) これは、思考時間が長いと棋力が高い人の指し手に近づき、そして、棋力が高い人にとってはそんなに指し手の自由度がないということなのだろう。


やねうら王の場合、同じ思考時間(例えば1手1分ぐらいの長さ)であれば、5〜10手に1手ぐらいしか指し手が変化しない。たぶん他のソフトも似た状況だろう。それでもこのときの指し手のバラけかたはソフトによって個体差がある。それが評価関数の差なのか探索手法の差なのかはよくわからないが、さまざまな要因で個体差がある。もしかするとツツカナ比較的指し手がバラけにくい部類に属するのではないかと私は思う。


と言うのもやねうら王のほうは序盤で自ら局後学習で定跡を作っているので、他のソフトと対戦されると意図せず相手ソフトにとって定跡外しのような進行になる。そのときに相手の指し手がどの程度バラけるかという尺度で見たときに、ツツカナはどうも同じパターンにハマりやすい気がする。今年の2月下旬にやねうら王をfloodgateに流していたときツツカナと5回当たったのだがいずれも似た進行となり、5回とも勝たせてもらった。(だからこういう進行ばかりになるならfloodgateのレーティングを見てどっちが強いとか言ってもあまり意味のないことである。このへん、他の開発者にもいい加減わかってもらいたい。)


ツツカナが今回の電王戦版でどんな乱数調整がされているのか詳しくは知らないが、あまりきつい乱数を入れていないなら、もしかしたらまずいのではないかと私は思っていた。もちろん、西尾先生がおっしゃっているように人間側は「(そこまでやって)作戦勝ち或いは少し優勢な局面を作れるかなという程度」だと思うので、プロ側が事前に時間を大量に費やして、こういうのを狙ってやるほどの価値はないのかも知れない。


また、私が考える究極のアンチ将棋ソフト戦略は、

1. 研究対象局面限定する(初手から樹形図を書いて、研究対象局面を絞っていく)

2. 入玉狙いにする(まだソフト入玉は大変弱いので)

3. ソフトの評価値おかし局面に誘導する(棋譜から学習は実戦例が少ない局面が苦手)

という3つだが、これらを同時に満たすのが故米長邦雄先生が対ボンクラーズ戦で見せた後手6二玉なのである。あれこそがアンチ将棋ソフト戦略極北だった。米長先生戦略は、2年前にしていまよりさらに3年ぐらい先を行っていた。トータルで5年ぐらい先を行っていたことになる。


それと言うのも、米長邦雄先生将棋倶楽部24でのレーティングはおそらく(いまの将棋倶楽部24換算で)R2800前後米長先生引退されてから長かったのでトッププロ比較するとR300〜400程度の差はあったと思われる。一方、ボンクラーズのRは(米長先生と対局時のPC構成において)R3200前後だと思うので、10回やって2回勝てるかどうかぐらいの差があったのだろう。それくらいの差において勝率を最大化しようと思うと、もはやアンチ将棋ソフト戦略以外に他ないと米長先生は判断されたのだろう。


今回の電王戦では出場ソフトプロ棋士の棋力はそこまで大きく乖離していないので、プロ側も米長先生のような戦い方をすることもないのだろうが、もっと大差になってくるとそういう戦いが現れるのかも知れない。


さて、少し話を戻して、初手から樹形図についてもう少し考えてみる。


連珠では、初手は天元(中央の星)に打ち、2手目は天元から1目離れた場所、3手目は天元から2目以内の離れた場所に置かなければならない。このため、3手目までが対称形を除くと26通りあり、これらを珠型(しゅけい)と呼ぶ。


将棋でも、今回の電王戦のような貸し出しルールのもとで序盤に対して樹形図が得られている場合人間側は好きな(自分の得意な)珠型(開始局面)を選択することが出来る。


そこで、樹形図自動生成するソフトなんてのも作ろうと思えば作れるわけだ。対戦相手のソフトと、一番強いソフトとを自動対戦させて樹形図作成する。「この3つの局面のいずれかに進行する確率(80%,10%,10%)、この4つの局面のいずれかに進行する確率(60%,20%,10%,10%)で、前者と後者とどちらを選択するか」なんてのを人間が選び、一番自信のある進行で戦う。


まあ、「自信のある進行」とは言っても局面的にはほとんどの場合ソフト側によほどの穴がない限りは形勢的にはほぼ互角であるだろうから、そこから勝ちきるのは実力である。また、ソフト開発側としては、こういう形の事前研究で欠陥が露呈しないように対策しないといけない。お互いに苦労が絶えない。誰得な感じもする。

り 2014/04/06 22:38 対コンピュータ戦の人間側が取るべき戦略は
攻撃7/防御3くらいの攻撃に特化した差し回しでしょうね。

redboltzredboltz 2014/04/06 23:00 > 連珠では、初手が天元(中央の星)に打ち、
> 2手目は天元から1目離れた場所、
> 3手目は天元から2目離れた場所に置かなければならない。

連珠の3手目に関してですが、花月、雨月、松月、丘月、雲月、浦月、銀月、斜月は天元から1目離れたところかと思います。
http://ja.wikipedia.org/wiki/%E9%80%A3%E7%8F%A0

kanokekanoke 2014/04/06 23:17 電王戦では「一時の勝利よりも普遍的な棋力アップを考える開発者」と「長い伝統とプロスポーツとしての矜持をもつ棋士」が主役ですので、このように「ルール内で勝率の最大化を狙う」という方向にはなかなか進まない気がしますね。
開発者にとっても棋士にとっても、ルール攻略で電王戦に勝っても得るものが少なすぎますから。
どちらかというと、Ponanzaに勝てたら100万円企画の方がそれに近くなりそうな気がします。
100万円企画の方をもっと整備して、各自宅で再現性がとれるルールとより高い賞金提供があれば(プログラマ的には)盛り上がる気がするなー。(興行的には)いまいち盛り上がらないでしょうけど。

aa 2014/04/06 23:20 確かに今回の電王戦を観戦していても、事前研究はただ漫然とやればよいというものではないことが良く分かりますね。本番と同じ設定だと時間と体力が必要なので序・中盤だけとか、時間をより短く設定してとか…前者では終盤のソフトの粘りに対応不足だし、後者ではそもそも指し手の質が違うことになる…数千局を分析するのも容易ではない。

YSSは序・中盤に時間をかけなかったことと、おっしゃる指してのバラツキが少ないことにより、研究がしやすかった面があるかもしれないですね。

米長先生は先見性がありましたね。電王戦の興行も…

yaneuraoyaneurao 2014/04/06 23:39 ↑*3 「2目“以内”の離れた場所」と書こうとして“以内”が脱字してました。本文、修正しました。ご指摘感謝します。
↑*2 100万円企画は、ソフトが強すぎて電王戦が成立しないぐらいの時代が来たら、詰将棋解答選手権のようにプロも参加可能にしたものを見てみたいですね。
↑*1 米長先生の先見性はもっともっと評価されていいように思うんですけどね。

観戦者n号観戦者n号 2014/04/06 23:42 貢献の割に見返りが少ないみたいですね。棋士にとっても開発者にとっても。
個別の対局勝利賞金と、チーム戦勝利賞金を設ければ、少しは緩和されるのかな…。

abcabc 2014/04/06 23:47 局後学習有りのやねうら王と無しのやねうら王を延々と自己対戦させると勝率はどの程度開いていくと思われますか?

yaneuraoyaneurao 2014/04/06 23:58 ↑*1
20手目ぐらいまで局後学習させただけで短い持ち時間(1局5分設定)では自己対戦勝率は55〜60%ぐらいになりますね。40手目ぐらいまでやれば(変化も膨大なのですべての変化を網羅するのに何年もかかるかも知れませんが…)80%ぐらいいくのではないでしょうか。

abcabc 2014/04/07 01:50 なるほど、20手まででも結構変わるんですね。80%というと柔道や相撲で組み手、体勢が十分な状態から試合開始、というようなイメージですね。
一般的にバージョンアップなどで自己対戦させる場合、先手勝率、後手勝率は同じように上がるものなんでしょうか?
持ち時間が長い場合やソフトの棋力が上がっていくほど、先手勝率は上がるけど、後手勝率は頭打ち、みたいな傾向はないのかな?と。

yaneuraoyaneurao 2014/04/07 02:01
> なるほど、20手まででも結構変わるんですね。

定跡のない側は初手から定跡外れるので、短時間で10手分自分で考えて悪手なしに指さないといけないですが、局後学習定跡のある側はすごく時間を使って考えた最強の1手をノータイム(計測上1秒)で指せるので20手目の局面で+200ぐらいの差が出てるときがあります。ただ、持ち時間の長い将棋ですと、定跡のない側もそこまで悪い手を指さないでしょうし、ほぼ互角(勝率で言うと数%下がる程度)なのだと思います。

> 一般的にバージョンアップなどで自己対戦させる場合、先手勝率、後手勝率は同じように上がるものなんでしょうか?

これは私は提示できるデータを持ちあわせてないです。戦型選択によってもずいぶん変わってきますし、仮に思考時間を増やしたときに後手のほうは1%か2%ぐらい勝率が下がるとしても、それを統計的に示すには1000局ぐらいはやらないといけないかと思うのですが、長い持ち時間でそれだけこなすのはなかなか大変で…。

匿名匿名 2014/04/07 12:37 >もっと大差になってくると

純粋にソフトが進化して、もっと大差になってくることってあるんでしょうか?まだ見えていない何かのブレークスルーが無ければ、結構、頭打ちなんですよね?

やまやま 2014/04/07 13:34 誰得ってのが全てを表していますね。

そして対comと対人の違いを埋めようとすればするほど(ルールを平等にしようとすればするほど)興行としての魅力が薄れていくような気がしますね。

kawanomizugokugokukawanomizugokugoku 2014/04/07 15:11 やねうら王はアンチソフトソフトとして最強になるわけですねわかります。

yaneuraoyaneurao 2014/04/07 15:20 ↑*3 それが…既存の技術の組み合わせだけでまだまだ伸びそうなんです…。
↑*1 「アンチコンピューター将棋戦略」にも対策した「アンチアンチコンピューター将棋ソフト」になりたいですね。

aa 2014/04/07 21:36 初歩的な質問ですみません
COM相手に囲わせないことによって
評価関数上有利に進行するなんてことはできるのでしょうか

mnmmnm 2014/04/08 00:14 誰かプロさんが狂った様に研究して、入玉定石なるものを完成させられたら、一旦ソフトの脅威から解放されるのに。無理か。。無理なのか。。

亜亜亜亜亜亜 2014/04/08 02:16 やねうらさんは「事前貸し出しのルールは、プロ棋士側に負担をかける悪いルール」と述べているにも関わらず、アンチ将棋ソフト戦略を詳細に考えているところが面白いですね。
ただ、そういうルールになってしまった以上は、プロ棋士と開発者の双方の視点に立って、考察しているところが、やねうらさんらしくて素晴らしいです。

将棋連盟は次回の電王戦対策のために、電気代を軽く支払えるくらいのギャラを支払って、やねうらさんを雇うべきだと思いますw
ただ、次回の電王戦トーナメントでは、やねうら王が優勝して、出場者になると予想されますから、それは無理かもしれません。(と発破をかけておく)

樹形図を自動生成するソフトは、実際に作って、仮にやねうら王が市販化されたのなら、セットで売り出せば、バカ売れするかも?
樹形図作成機能は、プロ棋士の人間同士の対局でも役立つのではないでしょうか。
あるいは、自分のネット将棋の棋譜を全部取り込んで、樹形図にしてくれれば、アマにとっても序盤研究の武器になりそうです。

>指し手がバラけるように調整しようと思うと、きつく乱数を入れないといけないので弱体化してしまう。

現在のソフトの評価関数の実力ですと、序盤はプラマイ200点ぐらいは誤差の範囲に思えます。
その範囲内での乱数による指し手の選択なら、そんな弱体化はしないのではないでしょうか?
ただ、中終盤だとそれではいけないので、どこで切り替えるかという問題はあるのかもしれませんが。

あと、乱数による弱体化は理論上の話なのか、実際に乱数をきつくしていった時に、棋力が落ちていく対戦データがあるのかを知りたいです。

かーかー 2014/04/08 09:27 やねうらさんの局後学習凄いですよね。
試合を中断する前に、プロセスキルしちゃうとか、対局前にコピーして元のと差し替えられてしまうと成長しないのですか?
貸出期間の研究の際にそうされたら振りだなって。

yaneuraoyaneurao 2014/04/08 09:33 ↑*4 狙って相手を穴熊に組ませない的なことですかね。今回電王戦に出場したやねうら王2013の場合、電王戦第二局のような進行になると居飛車穴熊相手に美濃囲いにしてしまう癖のようなものがありますね。ソフトによってはああいう形で序盤で作戦勝ちすることは十分に可能でしょうね。

↑*2 序盤だけ乱数性を入れるというのはいいアイデアですね。あと、R200も落としてよければ相当に指し手にランダム性を持たせることは出来ると思いますが(今回のPonanzaでR50程度のダウンらしい)、まだ将棋ソフトはその200が問題にならないほど突き抜けた強さではないので…どうなんでしょう。

> あと、乱数による弱体化は理論上の話なのか、実際に乱数をきつくしていった時に、棋力が落ちていく対戦データがあるのかを知りたいです。

評価関数のパラメーターにこれくらいの乱数を加えれば、これくらい自己対戦の勝率が落ちるというデータであれば以前調べたことがあります。勝率が落ちるので棋力が落ちているのは間違いなのですが、指し手がどれくらいバラけているのかの統計は取ってないので(その統計をとるのが手作業になるのは辛いので、何らかのアシストツールが必要だと感じます)、よくわかりませんが。このへんは今後も必要そうであれば開発します。

↑*1 対局中に遭遇した局面をsfen形式で書きだしているのでプロセスのkillに対しては安全です。もちろん、別のPCにコピーしておいてそちらで練習対局するだとかされるとどうしようもありませんが、そのへんは運用上の問題なので…。

り 2014/04/08 22:32 乱数乱数言ってますけど、例えば評価関数のパラメータを正規分布ぽくばらけさしたり、評価関数のパラメータを1/2の確立で「1割増/1割減」させたりとか、局面の評価値を計算した所でその評価値を1/2の確立で「1割増/1割減」したりとか、方法はいろいろあると思います。どういう方法が一番いいと思いますでしょうか。

yaneuraoyaneurao 2014/04/09 17:00 ↑それは論文級の話になってしまうのでは…。どういう乱数の加え方があまり弱体化させずに指し手をばらけさせることが出来るかというのは、合議でも重要になってくるのでそこそこ意味のある議論であると思いますし。

名無し名無し 2014/04/10 21:34 電王戦はプロ棋士側orコンピュータ側のどちらかに勝って欲しいと思って見ているわけではなく、ただ単純に熱戦が見たいと思って観戦しています。
電王戦には異種格闘技戦のような面があり、そういった戦いにおけるルールというのは、ある意味では対戦者の実力以上に勝敗に大きく影響すると思うのですが、
前回と比べてプロ棋士側に有利な条件でもコンピュータ側が勝ち越したことで、今後の電王戦のルールはどうなるのか(熱戦になるのか)不安に思っています。

第4局の対局後の会見や下記の動画で、森下先生が「人間側が盤駒を使用したらどうか?」ということを仰っていますが、これについてやねうらおさんはどう思われますか?

  【棋士・森下卓九段】が対コンピュータ戦について語っていた ‐ ニコニコ動画:GINZA
  http://www.nicovideo.jp/watch/sm23229879

また、動画の中で「3日に1手を指す、1年かけての将棋」という話をされており、電王戦のスピンオフ企画としては面白いのではないかと思ったのですが、
ルール以外の点でも、こうしたら面白いんじゃないか?というような考えなどあったらお聞かせください。

yaneuraoyaneurao 2014/04/10 21:58 ↑ > 森下先生が「人間側が盤駒を使用したらどうか?」

長時間なら人間側は盤駒+メモ用紙があれば、さらに強くなると思いますよ。どれくらい強くなるのかはわかりませんが、私は盤駒+メモ用紙ありで戦う森下先生も見てみたいです!

> ルール以外の点でも、こうしたら面白いんじゃないか?

プロ相手にソフト側が駒落ちできるほどいまのソフトは強くないでしょうから、チェスのハンディみたく、初期局面での後手2手待ち(王をとる手は不可)とかあってもいいとは思うのですが。そうすると76歩〜33角成〜88馬のあと同角成、同銀までが定跡化されるのかな…。後手3手待ちで、かつ、その3手は先手は駒を1〜5段目には運べないとかそういうハンディでもいいと思いますし。このへんは駒落ちにせずとも、いろいろハンディのつけかたがあると思いますよ。

亜亜亜亜亜亜 2014/04/11 04:17 >>現在のソフトの評価関数の実力ですと、序盤はプラマイ200点ぐらいは誤差の範囲に思えます。
>あと、R200も落としてよければ相当に指し手にランダム性を持たせることは出来ると思いますが

今、読み返してみると、間違って伝わっている気がw
評価値+200〜−200の間という意味だったのですが、R200と伝わってしまったような・・・。

単純に候補手の選択に乱数を使えばいいと思ったのですが、評価関数のパラメーターに乱数を加えているのですね。
その方法ですと、確かに指し手がどれくらいバラけるのかが不明ですが、序盤に限定すれば、前者の方法でダメなんでしょうか?
中盤でも、例えば最前手+300、次善手+280の場合、前者を選ぶ必然性はなく、最善手の評価値の90%程度の値までに複数の候補手があれば、ランダムでいい気がします。

yaneuraoyaneurao 2014/04/11 09:06 ↑ > その方法ですと、確かに指し手がどれくらいバラけるのかが不明ですが、序盤に限定すれば、前者の方法でダメなんでしょうか?

通常のαβ探索では、その局面のベストな指し手(最善手)は求まるのですが2番目にベストな指し手(次善手)は求まらないのです。(ベストな指し手のスコアを超えないとわかった時点で枝刈りして帰ってくることによって探索効率を高めるのがαβ探索の特徴なので..)

ゆえに、評価値のスコア差がこれくらいの範囲に収まる他の指し手を選ぶということは、通常のαβ探索では出来ないのです。

接待ひよこ将棋では、探索開始局面でそれぞれの指し手で1手進めてからαβ探索することによって、探索開始局面でのそれぞれの指し手のスコアを求めているのですが、それだと探索効率はすこぶる悪くなります。(枝刈り性能が悪くなるので、たぶん数倍余計に時間がかかります)

やねうら王の局後学習で複数の候補手を挙げるときに用いているMultiPVという機能も基本的には、これと同じ考え方です。探索効率はかなり悪くなります。

そんなわけでして、互角のプレイヤー相手にその局面の次善手を求めることは、良くないアイデアなのです。次善手を求めても良いのは、もっと実力差があるときの手加減目的であるだとか、局後など時間がかかっても良い時に限られます。

亜亜亜亜亜亜 2014/04/11 16:57 なるほど、αカットの段階で、その候補手は同じ階層の仮の最善手の評価値を超えられないので、相手の指し手が枝刈りされて、その候補手の評価値がどこまで下がるのか分からないわけですね。
だから、最善手以外の評価値が分からず、次善手を求めることができないわけですね。

てっきり、市販の激指や東大将棋の検討モードで、候補手が表示されるので、求まると勘違いしていました。
あれは、候補手の数を限定して、探索効率を犠牲にすることで可能となるんですね。
勉強になりました。

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

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