コンピュータ囲碁の世界では、長きに亘り良い評価関数を設計できずに苦心していました。評価関数というのは、人間で言うと大局観に当たる部分です。この部分をうまく設計するのが強い囲碁ソフトを作る上で必要不可欠なのですが、それは職人のような作業だと言われていました。
そのあとAlphaZeroが現れたことにより、評価関数は人間が設計したものより、ニューラルネットワーク(以下NNと記す)のほうがうまく表現できることが証明されました。このことは、コンピュータ囲碁プログラマの敗北であると同時に新たな時代の幕開けでした。
一方、コンピュータ将棋の世界は少し様相が異なりました。コンピュータ将棋では、2005年にBonanza6が取り入れた、王様とそれ以外の任意2駒といういわゆる三駒関係(KPP)を10年以上使ってきました。途中でNDF[2014]が手番を入れてKPPT(Tは手番ではなくTurnのT)型に進化しましたが、いずれにせよ、三駒関係という枠組みからは抜け出せずにいました。
三駒関係は、その局面の評価値(形勢判断の指標)をKPPの線形和で計算します。線形和と言うのは、KPPのそれぞれの値を単純に足し合わせるという意味です。数式で書くとkppという三次元配列があるとして、以下のようになります。
eval = Σ kpp[k][p1][p2] : それぞれのk,p1,p2に関して
しかしよく考えてみるとこの線形和で表されるというのは何の理論的な根拠もありません。例えば、「と」を敵陣に作り、この「と」が敵の駒に近づいた時に、この「と」は高い確率でその駒と交換できるはずなので王様 – 「と」 – 敵陣の駒 という三駒関係には高い値がつきます。
ところが交換できるのはそのなかの一つだけです。(普通は、敵陣の駒を取ったときにその駒に敵の駒の利きがあり、「と」を取り返されるため) それなのに線形和でここをどんどん加算していくのは良い近似とは言えません。
このように三駒関係の線形和というのは綻びがありながらも、差分計算が容易なのでそこそこnps(1秒間に読める局面数)が稼げるので、そこまで悪い評価関数でもなく、将棋ソフトはKPPTのままレーティング(棋力)はR4000を超えました。(トッププロがR3200前後)
コンピュータ将棋界ではそこでNNUEという評価関数が発明されます。tanuki-チームが今年の大会(WCSC28)で使用したものです。
※ 高速に差分計算可能なニューラルネットワーク型将棋評価関数 : https://www.apply.computer-shogi.org/wcsc28/appeal/the_end_of_genesis_T.N.K.evolution_turbo_type_D/nnue.pdf
評価関数にソフトウェア実装によるNNを用いたものです。こう言うと、NNによる多駒関係を実現したので三駒関係より表現力が高いんだなと理解する人がほとんどかと思うのですが、実際はその説明は正確ではありません。
と言うのも、tanuki-がWCSC28で用いていたNNUEは、NNの入力がKP(王様とそれ以外の1駒)で、隠れ層の一層目のUnit数(列数)が512しかないからです。NNより構造が単純化されたパーセプトロンですら、論理回路のandやorを表現できることは知られていますが、そうは言っても、512しかないのでは、入力として与えられたKPから任意のKPP(これは任意の２つのKPの論理andです)を作り出すことはできません。
※ KPPの組み合わせは81升×1500通り×1500通り/2 程度あるので、512では到底表現できないからです。まあ、Kは同時に複数の場所には出現しないので、それを差し引いたとしても1500×1500/2 程度はUnit数がないと任意のKPPを表現することすら出来ません。
つまり、NNUEに「三駒関係より高い(N駒関係の)表現力がある」という説明は正確ではないと言えるでしょう。私が思うにこれはただの「非線形なKP(二駒関係)」です。本来、評価関数職人がうまく設計するべきであった評価関数をNNがうまく表現してくれていると言ったところでしょうか。
※ 非線形な評価関数を用いていた将棋ソフトとしては過去に『習甦』[2008-]があります。しかし『習甦』は駒割・玉の安全度などを線形和で計算したあとに最終的な出力の前にだけNNのようなものを経由させているだけでした。
いずれにせよ、NNUEの登場により、三駒関係の時代が終わりを告げたことは間違いありません。これを以て、囲碁ソフトに引き続き、コンピュータ将棋プログラマも敗北宣言をしなければなりません。
2018年に同様のムーブメントはコンピュータチェスの世界にも到来しました。
最強チェスソフトの一つとして挙げられるStockfishも評価関数は二駒関係＋αを採用していました。
チェスは駒の価値が高いので、二駒関係＋αで十分良い精度の評価関数になっているのでは？というのがコンピュータ将棋開発者も含めた開発者たちの見立てでした。まあ、コンピュータ将棋開発者のなかには、「チェスも三駒関係(KPPT)を導入すれば強くなるのに」と考えた人たちはいました。私もKPPTを導入すれば強くなるだろうと思っています。
しかし、チェスのほうはKPP/KPPTを導入されることもなく(その過程をすっ飛ばして)、AlphaZero方式のMCTS + NNを採用したソフトが出てきました。その代表格がLeela Chess Zeroです。Leela Chess Zeroは、TCEC(Top Chess Engine Championship)という大会でも好成績を収めています。
実際のところ、StockfishとLeela Chess Zeroとどちらが強いのかを公平に判断することは難しいです。後者はGPUを使うので同じマシンパワーとは言い難い意味があるからです。ただ、GPUで計算しやすい形の評価関数になっているとは言えるでしょうし、二駒関係＋αで十分だと思われていたコンピュータチェスの世界に激震が走ったこともまた事実です。
まあ、将棋ソフトがKPPTからNNUEのようなNNを用いた評価関数に推移して行ったことから、Stockfish陣営から白旗が上がるのも時間の問題だと思います。
そうは言っても、NNを用いれば自動的に評価関数が作られるわけではなく、その入力に何を入れるか(KPなのか、KとPなのか、KP+αなのか等)と、そのNNをどういう構成にするか(Unit数、Layer数など)が、将棋やチェスのソフトでは工夫の余地が大いにあり、従来のように評価関数をKPPT型に固定しておいて延々と雑巾絞り(強化学習を繰り返すこと)をするだけで良かった時代は終わってしまったと言えるでしょう。
このため、KPPT型の雑巾絞りよりはるかに潤沢な計算資源がないとろくに実験すら出来ない状況となりつつあります。
さて、来年の世界コンピュータ将棋選手権(WCSC29)では、どのようなソフトがその活躍を見せてくれるのでしょうか。興味が尽きません。私(やねうら王)も気が向いたら出場します。
こんにちはコンピュータ将棋は観る将です。
3駒関係を勘違いしてました。電王戦で駒が団子になったのをマイナス評価せず人間に負けた将棋があったと記憶してますが、それなら玉を除く3駒の関係も入れて学習すればいいのではと思いました。そうなると計算が大変なのでしょうか
KPPの組み合わせは2×38×37/2=1406ですが、任意3駒PPPの組み合わせは40×39×38/6で約6倍。現状、評価関数が全体の計算時間の4割ぐらいを締めていますが、それが6倍(実際はメモリアクセスがボトルネックになるので10倍ぐらいに..) そうするとnpsがいまの1/4程度になってしまい、これによりR400程度のダウン。評価関数の精度アップでこのR400を回収できるかと言うと、到底できないというのが私の考えです。
大変勉強になりました。ありがとうございます。
暗記して人に言いふらします。
なんとかちゃんねるの議論？
詳しい解説ありがとうございます。
3駒関係も正則化に工夫を入れればもうちょっとだけ強くなりそうな気がしないでもないけどどうなんでしょう？
例えば3駒の三角形の面積で評価値を割れば、玉から離れる程評価値が小さくなるので電王トーナメントの時にも発生した、玉から離れた位置にと金を無駄につくるようなものも無くなるような気がします。飛車・角にとってははそれだとまずいのかもしれないけど。
> 3駒の三角形の面積で評価値を割れば
面白いアイデアですが、現状、大規模学習(大量の教師棋譜を生成してそこからの学習)においては、正則化項、一切導入していないですね。KPPT型に対して正則化項をつけると害になるというのが私の考えで、例えば、99玉-98香(穴熊)のときの48金とか、明らかな離れ駒で、大きな減点をされるべきですが、これが0に寄ってしまう正則化はおかしいと私は考えます。
関係ないけど、最強のハードウェアを持ち込めた奴が優勝みたいなeスポーツは良くないスポーツだと思ってる。
BM98でいくら練習をしても、アーケード筐体の方で結果をコミットできなきゃ意味が無いみたいなｗ
実力だけで決まるようにした大会は、結果が見えていて観戦しているほうは興ざめかも知れませんけど。
そのあたりは羽生9段とか藤井7段くらいとか、そういう肩書きが付いていることで、ある程度は下克上ｷﾀｰとか差があるから仕方ないとかそもそも直接の対戦機会さえ用意されないとか調整されていると思う。
NNを用いたAIは一般的なPC（非GPU搭載）では動作が（ほぼ）不可能に近いですから、これからは競技用と家庭用で開発の棲み分けが進むのでしょうか…？
現状コンシューマ向けソフトはCPUのみでの動作が前提ですから、従来型の（線形モデルを用いた）AIのさらなる洗練に期待します！！
CPU onlyでもOpenBlasなどを使うとSIMD命令で並列化してくれるのでそこそこ動きますよ。(GPUで処理するより速いとは言っていない)
やねうら王の将棋ソフトを買おうか迷ってるのですが、もし買ったとして強さなど今後も更新されていくのでしょうか？それとも買った時点で完結されているのでしょうか。
強さ(エンジン)の更新は、しない予定ですが、近日中のアップデートで外部エンジンを使えるようにはするので、半永久的に有志によって無償公開されている最新の野良エンジンが使えることには違いないです。(｀･ω･´)ｂ
なお、本記事に関係ないコメントは手動的に消滅するです..
評価関数を組み合わせ最適化問題に落とし込んで
各種アニーリングマシンで解けるように出来たりする
可能性は無いものですかね？
NNの学習がアニーリングマシンで解けるようになれば…。(´ω｀)
いつも、大変知的な記事誠にありがとうございます。
ねーちゃんには興味があるが、ネイチャーには興味がない とレスを頂いたものです。
大変素朴な質問で恐縮ですが、
本稿ご執筆時点で AlphaZero の Science 誌での査読論文も通っていることはご承知と思いますが、
チェスの Leela に言及されて、 AlphaZero それ自体についてはほとんど触れられていないのはなぜなのでしょうか？
AlphaZeroの論文、時間なくてそこまで読みこんでないからです..(´ω｀)
アルファゼロのディープラーニングであれば、ソフトが苦手な大きな駒落ち、6枚落ちといったあたりの人間とかなり差がある分野も大きな進歩があるかなと思ったのですがその辺のアプローチはなくて残念でした。
現状、6枚落ちは並のプロで初段、名手なら3段ぐらいでソフトは全然行ってないですからね
ディープラーニングを使って駒落ちを強くするとする場合適当なところに公開して人間に一杯指してもらってそれをもとにって地道な方法しかないのでしょうか
他には複雑な曲面とか3手先にはよく見えるけど5手進むと酷い局面に誘導しやすくするとか？自動学習からどんどんはなれてるような
6枚落ちは何らか誤魔化さないと(相手はこの指し手は指さないだろうという仮定がないと)勝てないと思うのですが、それは探索の問題で、ディープラーニングは関係ないのでは…。そもそもNNUEもディープラーニングなわけでAlphaZeroと手法が大きく異なるわけでもなく。
この指しては指さないだろうという手の指しにくさみたいなものをディープラーニングで数値化できあにだろうかと思ったんです
ディープラーニングを使わずともある棋力帯の人間が指す指し手を予測すること自体はできると思いますが(e.g.GPS将棋の実現確率)、それを探索に活かすためには探索部をいまのと全く違う形で書き直す必要があって、私はやりたくないなぁという感じでございます。(2012年ごろの論文にあるOM-Searchという手法がそれです) まあ、どうせソフト自体が強くなれば駒落ち時も強くなるので、わざわざ駒落ちのために何かをしなくとも…と私は思っています。
f(board)=boardの評価値
F(f,n,board)=boardに対して評価関数fによる深さnのminimaxを行った結果の評価値
としたとき、神の（最強の）評価関数は、
F(f,n,board)=f(board)
を満たしますよね。
なんか、固有関数を求める問題におとしこめそう。
強化学習って、要するにそういうことをやっています…が、モデルの表現能力は有限なので、その限度までしか強くできないという…。