rewritemath's blog

将棋ソフト開発の歴史

BONANZA以前

将棋のルールを記述して、そのルールどおりに動くソフトの発明

手筋、定跡をを記述して学習する手法が主流

探索部は、深く、選択した局面を探索。選択する局面ももちろん手入力が元となっている


BONANZA

機械学習の導入(プロの棋譜を評価する形で教師とする)

三駒関係の発明

全幅探索

三手詰めルーチン

マチュア三段から四段程の棋力と称されるが、プロ棋士も、一手十秒程度の早指しでは勝てなかったようだ。(ソースは、cakesにてmtmtさんの語るところによる)

 

ボンクラーズ

探索をクラスタ化(ボナンザクラスターズ)

探索局面が増えるごとに(指数関数的な増加に比例して)レートが伸びることの検証を行う。プロ棋士並みの実力から、名人の実力に到達した(数値上の話)

 

後にクラスタ化は、GPS将棋が引き継いで、当時A級棋士(上位十名)だった三浦九段を破る。(現在三浦九段がソフト指し騒ぎに揺れていますが、どうなるのでしょうね)

これをきっかけとして、電王戦のレギュレーションがソフトに制限を年々厳しく変更する方向に傾くこととなる。

探索局面が少なくても強いソフトとして、枝刈りが利用されるようになる。興味があるなら、αβ探索とか、ミニマックス法とかで検索したまえ。

過度な枝刈りは、悲劇を生むこととなるだろう。

AWAKEの28角による投了のような問題は、後に、BishopDangerを生み出す改良へと繋がったりする。

 


ツツカナ、やねうら王、PONANZA等々の登場

これは、将棋ソフトの裾野を広げた。プロ棋士にも勝ち越す様になっている。


現在トップソフトの推定棋力はレートにして3800は出そうだ。

 

三駒関係の進化

四駒関係、三駒+手番、二駒+効き+手番等々の、独自評価関数が生まれてくる。

 

教師データも、最近では後半の学習には、プロ棋士棋譜を用いない方が現状では強くなる。

 

三駒関係ではパラメータが多すぎて、正確な評価値の値を確定するには局面数が少なすぎる。そこで、教師データの生成と、少ない教師データでの学習、等々多彩な技術が利用されてきた。


教師データの作成をするために自己対戦を続けたソフトもあった。

 


完全にプロの棋譜を用いないで学習させる試みもある(やねうら王の磯崎さんのサイトで実験的な試みが多数行われている。)

 

現状、序盤、中盤、終盤のどれをとってもソフトの力は人間より高いだろう(終盤の一部の局面で人間が上回る場合がある)

 

左右対称問題

評価関数の学習には、左右対称にするかどうか問題というものがある。

左右対称にしないとその分、居飛車を高く評価しやすくなる。また、居飛車である評価が左美濃にも乗ることになる。

理論上は左右対称の方が正確な評価値が確定しやすいはずだが、(手番が左右で変動するという議論は、完全解明が間近に迫るまでしなくてよいだろう)実用上は左右対称にしないほうが良いと言う見解を、Apery平岡さんとPONANZA山本さんは持っている様だ。(ツイッタがソース)私も同意する。

 

次元下げ

評価関数の次元を下げることで教師データの不足を補おうということを、AWAKEが行っていて、ブームになった時代がある。しかし、根本的な問題は解決しなかっただけでなく、あまり強くならないし、もっといい方法あるし、なによりコードは複雑になりすぎて大変なので、ブームは去っていった。

 

現状、seleneの学習手法が、完全解明、完全な真の値の評価関数に一番近づける可能性を持っている。詳細は割愛する。複雑すぎてここに書くのはちょっと無理だ。

 

NDFの評価関数設計

現在の主流だ。ある局面を学習させて、その先の評価値を手前に引っ張ってくるだけ。

 

近年の強豪ソフトや、開発者に大きい影響を与えたと思われるもの

(というか、単なる将棋ソフトの説明になっている気もしなくはない…)

Apery

オープンソース時代の到来を告げたソフト。開発者の平岡さんは結婚できない独身さん。素晴らしい人だから、是非幸せになって欲しい。ネガティブ。平岡組とは独身の人達の組のこと

 

技巧

PONANZAと二強なのに(現在はそうでもないけど)電王トーナメントでは大活躍…できない不遇ソフト。定跡でよく死んでしまっている。定跡を切ったら今度は序盤が弱い。二駒+利き+手番で評価関数を組んでいる弊害か。ただし、その評価関数のお陰で、入玉の将棋にめっぽう強い。玉の安全度を図る終盤力には定評あり。PONANZAは玉の正確な安全度を読み切るのが得意なのに対し、技巧は玉の生存圏を確保するのが得意なイメージ。

このソフトの公開はオープンソース世界に新風を巻き起こした。

Aperyと技巧はオープンソース界の二大巨頭

 

やねうら王

強い。互換性好き。定跡とか時間の使い方で勝っていた、電王トーナメントから一転。第二回叡王戦では実力派になっていた。天才プログラマの磯崎さんの作品。オープンソースに転身した。

 

大合神くじらちゃん

えびちゃんさんの作品。ニコ生ユーザーによるクラスタ化、stokfish7をいち早く導入、単騎のSilentMajorityも強かったので話題に。フリーソフトの中でやっぱりかなり強い位置を占めている。序盤が苦手な技巧を使うのをやめて序盤研究はこっちに移していた人も。