2018-04-23

結局評価値とか評価関数とはなんなのか

コンピュータ将棋雑談将棋

評価値、評価関数。こういった言葉が存在するが、これはそもそも何のためにあるのか、何の指標なのか、どのくらいあてになるのか。

これが今回のテーマです。

そのためにまず、ゲームの分類をしましょう。

学問の世界の話をしますと、ゲーム理論というものが存在します。これを今回の解説で参考にしております。しかし、できるだけそういう部分は出さないように、簡単に説明しようと思います。

では、ゲームを考えましょう。ゲームの種類ですが、今回は将棋や囲碁をテーマに据えますので、このゲームは

プレイヤーは二人
二人の利害関係としては、片方が得するともう一方は損する

　　　＝片方が勝ちに近づくともう一方は負けに近づく

ゲームの勝敗に運は関与しない（コイントスとかサイコロとか）
ターン制

という特徴があります。オセロ、チェスも同じ分類ですね。

（引き分けは一旦考慮しません）

最善の手段をプレイヤーが取り続けると仮定します。

すると、ゲームの手番が決まった時点で既に、勝敗は決まっているということになりますね。「勝ち」「負け」のどちらかです。

では、最善の手段はどうやって求めればいいでしょうか。

まず、勝ちが近い場合は分かりやすいでしょう。例えば、将棋ではあと一手で詰ますことができる場合は、その一手が最善です。

他に、ある局面から、相手がどんな行動をしても勝ちが読み切れている場合も、最善手は決まります。

取れる行動のパターンが少ない場合は、全て列挙すれば、それで最善手は分かるのです。

つまり、仮に全ての終局までのパターンが列挙できているとしたら、その局面の評価値は「勝ち」か、「負け」かしかありません。

では、評価値をわざわざ細かく区切って点数表示するのはどういった意味があるのでしょうか。

それは一重に、中間目標の点を指し示すために他なりません。

では、どういった目標を中間目標として目指すべきなのでしょうか。

↓こちらに続きます

ritomath-shogi.hatenablog.com

2018-04-23

実は将棋において水平線効果は合理的かもしれないという話

将棋コンピュータ将棋

水平線効果というものをご存知でしょうか

探索アルゴリズムが、その探索深度が有限の場合に、近傍に有望な落としどころを発見する事が出来なかった場合に、将来的に見て問題のある行動を取ってしまうという効果の事です。

分かりやすく言い換えると、問題のある行為でも「未来のことが分からないから、仕方ない」ってなって問題行動を起こしてしまう人みたいな感じでしょうか

コンピュータ将棋において水平線効果が現れるのは、主にコンピュータが不利を自覚した時です。不利を自覚した時、不利になる将来を先延ばしにしようと意味のない手を指すのです。

では、不利な状況というのはどんな状況でしょうか。

また、不利な状況での最善手とはどういった手でしょうか。

まず、相手が最善手で常に応じてくる場合を考えましょう。

どれだけあがいても負けることに変わりはないのですから、どういった手を指しても結果は変わりません。全ての手は等しく最善手であると言えます。

では、その考え方が気に入らないとするならば、最善手と悪手の間に区別を設けることにしましょう。

「悪手は、負けを早める手」

どうでしょう、この決め方にはきっと皆さん納得してくれると思います。

では、この定義を元に、

「負けないように手数をかける手こそが最善手」

という仮説を立てます。

仮に相手がどこかで悪手を指すと仮定しても、着手が増えるほど、相手が「真の意味での悪手」（＝形勢が逆転する着手）をしてくれる可能性は高くなるだろうというのは妥当な可能性に思えます。

では、水平線効果というのは将棋で、どういった指し手が現れた時にそうだと言われるのでしょうか。

負けを悟って、負けをあえて早める手を指した場合は、真の意味で水平線効果が現れたと考えることになりそうです。

しかし、将棋における水平線効果というのは主に、負け（≒評価値が悪化する局面）を先延ばしにする時に出てくる現象です。

負けを先延ばしにする手は、将棋で劣勢の場合は大体最善手だという話を先程しました。おそらく、人間同士の対局でもそうでしょう。

誤魔化すような手というのは、相手のミスを前提に置いた手であり、勝負手というのは往々にして負けを早める手（≒悪手）です。

また、相手がミスをすると想定できるなら、将棋を長引かせるような着手の方が勝てる可能性は高くなるのではないでしょうか。

まぁもちろん、場合によりますけどね。

さて、ここからは水平線効果についてもう少し掘り下げます。

「仮に相手が最善手で応じるなら、どの手を指しても不利な局面では負けに変わりがない」

これは大前提です。この場合、全ての手の価値は等しくなります。

では問題は相手がミスをするかどうか、ミスをどうやって誘発するかです。

この際突き詰めるなら、本質的な話をしましょう。言葉はしっかりとした定義が必要ですからね。

「勝負手を放つ」

これが想定される回答です。では、勝負手とはどういった手なのかといえば、おそらくその目的は、

「間違えやすい局面に誘導する」

ということになるでしょう。では、間違えやすい局面とはどういった局面なのでしょうか。これを数値で表すとすると、勝率に影響してくるんだろうなということが考えられます。

勝率に影響する局面まで誘導できたとしたら、形勢は傾いていると考えてよいとしましょう。

ところで、最近の（特にelmo以降の）将棋ソフトは、雑巾絞りの際に勝率も評価値に入れています。実際に、それでかなり強くなりました。

ここから大胆に解釈を進めると、評価値の正体は勝率であった。そして、勝率に影響してくる局面とは、間違えやすい局面である。

こういう結論が導き出せます。

この結論から過去の将棋ソフトを振り返ってみると、

Bonanza時代

当時の評価関数はプロの棋譜からです。となると、勝率は勿論勝敗に影響してくることになりますね。勝率の高いプレイヤー（≒強いプレイヤー）の棋譜に近づけているのですから。

Bonanza以降の探索の改善

勝率の悪くなる局面（≒評価値の悪くなる局面）を枝刈りして、先まで読めるようにして強くなりました。

Floodgateからの棋譜で学習させたソフト、自己対局で強くなったソフト

勿論これは、高レートのプレイヤーや勝ったプレイヤーに近づけているのですから、これも勝率へのアプローチだと考えることができます。

雑巾絞り

こちらも同様ですね。将来に現れる勝率の高い局面の評価値を持ってくるのですから。

ここまでの洞察から、「評価値はその局面の勝率を反映している」という結論が得られました。

では、勝負手というものを考えます。間違えやすいような、勝率に影響するような局面に誘導するのが勝負手であると言いました。つまり、勝負手は、評価値を悪くしないように保つ役割が求められることになります。

もっと言いましょう。粘る手と言われる手も勝負手の一種と言えるということです。

補足すると、局面を悪くしないように保つことは、他の効果も生みます。相手が一定の確率で間違えるとしたら、その間違える可能性のある局面を参照する機会を増やす効果があるのです。

更にここから考えを深めます。

HoneyWaffle（強豪の振り飛車を指すソフト）についてです。対局は長くなりがちなようです。これはつまり、相手に粘りを許しやすいということです。つまり、相手に最善手を指されやすい、もっと言うと、あえて自分が不利になるような局面に突っ込んでいるということになります。不利飛車ですね…。

最後に、人間にも水平線効果のようなものが起こりうるということも付け加えておきます。

未来が見えないと人間も悪手を指しやすくなるわけですね。

2018-04-15

コンピュータ将棋専門用語辞典【寄稿、独自解説など】（できるだけ数学抜きで解説する）

elmo stockfish コンピュータ将棋将棋解説

速読コンピュータ将棋用語【記事募集中】 - qhapaq’s diary

↑こちらがカパックさんの記事です。

コンピュータ将棋レーティング

↑uuunuuunさんの記事

私なら違う表現をするという場合の記述ですので、基本的には補足みたいなもんだと思ってください。（段々本家より充実してきている…説明の厳密さによって分担かなぁ）

楽しんでもらえるように、茶番を含みます。ミニマリストじゃないので…

コンピュータ将棋開発者の方々、そしてその文化を育ててくれている方々皆さんに感謝を

利用の仕方（お勧め）

全部読んでもすぐ読み切れる
読みたいものがあれば、ctrl+f（キーボードのショートカット）を使って検索したい文字を入れてみよう

floodgate

コンピュータ将棋ソフトが対局してる場所。ググると出てくる。強いソフトの棋譜を得ようと思ったらここ。まとめて一年分とかダウンロードできたりする。棋譜の管理については別のところに解説を譲る。

レート

強さのこと。将棋界ではイロレーティングが使われていると思ってよい。

測定の仕方は他にもある。

ソフトの場合はfloodgateのものがめやす。

個人的に、ここが一番見やすかったりするので感謝して閲覧しましょう。

コンピュータ将棋レーティング

uuunuuunさんという方のサイトです。

人間と比較すると、3000以上のソフトはデスクトップのいいパソコンでは人類越えだと思っていいです。最近の上位ソフトは4000くらいあるので、人間には勝てないと思われる。人間をソフトが越えたのはいつか、というのは議論すると長くなりそう…他に譲る。将棋倶楽部24よりfloodgateの方がレートはシビアだと思われる。強さに自信がある人は、floodgateに潜ってみては？

コンピュータ将棋レーティング

評価値

どちらかが、その数字分有利という目安

±150くらいまでは互角

±300で作戦勝ち

±500で有利（ミスがなければ勝ち）

±800で優勢

±1000で大優勢

±1200で勝勢

±3000で逆転不可能

（あくまでめやす）

Depth ～

読みの深さ。～の数字の手数まで読む。全幅探索（記事の中で説明してます）とは限らない

Mate～

勝敗を読み切った宣言。～のところが手数。Mate15だとしたら、どんな手を指したとしても最善で応じれば15手以内に終局があることを読み切っている。

（詰みがあるとか必死とかってことではない。連続王手で終局を長引かせても、この手数以内に収まるという宣言）

multiPV～

検討する手の上位～個を表示させる設定。主に、局面の検討で使用する。次善手などの分岐も検討する場合はこれを設定する。

Ponder＝読み筋

Ponder hit=読み筋通り

読み筋が当たったから早指しする

ライブラリ

公開されていて、中身を使って改造していいよって言ってるソフト達。

（公開されていても、ライブラリに登録されていない場合は、大会などに提出するソフトに利用してはいけない）

チルドレン

ライブラリを使って参加したソフト達。

複数使っている場合は親が沢山いることになる

評価関数

局面を評価する基準となるもの。関数とは、物を入れると何か操作されて物が出てくる箱だと思ってくれればいい。コンピュータ将棋の評価関数は、局面のデータを入れると、評価値が返ってくる。人間でいえば大局観と考えていい。

仕組みのざっくりとした説明はここで

ritomath-shogi.hatenablog.com

N駒関係

Nは任意の正の整数値

N駒関係とはつまり、N個の駒の位置関係が盤上にあるとき、その評価は何点、という採点をして、局面をその関係につけた点数を合わせたものとして評価するもの。これによって局面に評価値がつくことで、有利か不利かを判断し、有利な局面を選ぶように指し手を進める基準になる。

ボナメソ

ボナンザメソッド。Bonanzaが使った学習方法。プロの棋譜を食べさせて、一手一手次の手をソフトに答えさせる。プロと同じ手を指したらいい子いい子する。段々プロっぽい手を憶える。手筋を人間が教えたりするより、強くなった。革命。

二駒関係

これだけだとちょっと弱いみたい。三駒がちょうどいいのかな

三駒関係

ソフトちゃんが、完全に同じ局面でしか答えられないと困るので、局面を抽象化する必要がある。そこで、局面を三駒の位置関係に分解して教えた。

N駒＋効き

効きを入れると終盤とか入玉で強くなるかも？技巧さんは効きも使ってたはず。

四駒関係

頑張っても、情報量が大きくなりすぎるので今のところ主流じゃない。

KPPT

King　王様

Piece　他の駒

Turn　手番

今はこれが主流

これで分かるように、KPPは三駒関係のこと。KPは二駒。やっぱり王様は大事。

KKPの場合、二つの王様は、自分と相手の王様。

NeuralNetwork（ニューラルネットワーク）の略語。

人間の脳を模倣した機械学習です

DeepLearningの略語

NNUE

TNKが採用する、高速に差分計算ができるニューラルネットワーク型の評価関数

ごめんなさい、難しいこと言いたかっただけです。

TNK（たぬき）はソフトの名前です。基本的にニューラルネットワークを使うと、GPUでしか高速に動かすことができないのですが、その辺りの不都合を上手く解消した天才的な発明です。（技術が高度すぎて分かりやすく説明できないので許して）

不利飛車

コンピュータ将棋は振り飛車しない。振り飛車は損？振り（不利）飛車って呼ばれてる

頑張れ（ソフトの名前）

頑張って育てたソフトには愛着が湧く。開発者と一緒に応援しよう。

雑巾絞り

「この局面を探索すると、将来的にはもっといい評価値が出るのよ。だから、未来は明るい。あなたはこの局面をもっと楽観視していいのよ」という感じで、局面を与えては評価して、未来の評価値を持ってきて、ということを繰り返すこと。とっても仕事量が多い。強くなるけど。絞るにつれて段々と絞れなくなってくる。

雑巾絞りについて、有識者の言葉

「エクスカリバーが最初の町で売られているけどめっちゃ高いし装備できる人は限られてる」

「札束ビンタ」

「ドモホルンリンクルのように、滴ってくる（強さが上がる）」

elmo絞り

「我々は、未来の局面についてだけではなくて、この局面から勝利が導けるかどうかを考えます。その結果から、未来の評価値を持ってくるのです」というタイプの雑巾絞り。なんかめっちゃ強くなったみたい。

Rezero

elmo絞りって、評価関数がない状態からでも未来予測できるようになってるってことじゃないか！？という発想から生まれた（多分）評価関数の元として人間の棋譜を入れたり、人間の棋譜が元となっているソフトの棋譜を入れたりしなくても、ソフトが自分で強くなる。（elmoくらいまで）

人間からの独立。やねうら王の開発者、磯崎様がこれを発表して世界に衝撃が走った。あのGoogleも注目したかもしれない。やはりやねさんは天才。（ちなみに電気代…）

探索部

役目

局面を作って、評価関数という箱に投げつける
帰ってきた評価値と局面を並べて、次に投げる局面を決める（優先して読む手はどれかなぁ、ということをこの子が決める。この子によっては読みぬけとか…）
次に指す手を決める

Stockfish

チェスの探索部で、公開されているもの。参考にしているソフトが多い。

詰みルーチン

この局面が詰むかどうかしか考えないマン。でも、詰め将棋だけは素晴らしい腕前。CPUのお仕事をこの子にどんくらい割り振るかによって勝敗が決まることもある。

全幅探索

有効な手、考えられる手。すべてだ！全てを考えてこそ将棋の可能性に迫ることができる！という感じで全部読むよう…。読みは浅くなっちゃう。Bonanzaはこれだったけど今は、効率よく先を読む手法（Minimaxとか、下の方に…）が色々使われている。

モンテカルロ…

専門的な内容だからこれだけで一本記事がかけてしまう

αβ探索とかMinimaxとか枝刈りとかrootstrapとかbootstrapとかとか

上に同じ

book

定跡

eval

評価関数

IT関係の言葉

オペレーティングシステム。linux,windows,mac,android,iosなど。

OSがアプリケーションを動かす。下地といえば分かりやすいだろうか。機械と人間との対話をするために、翻訳する役目を担っている。

CPU

パソコンの計算機。脳みたいな。中国語で電脳はコンピュータのことだっけ。

GUI

Graphical User Interface(グラフィカルユーザーインターフェース）

視覚的に人間に分かりやすくするためのもの。将棋所か、将棋GUIのどちらかを使うのが一般的。

GPU

映像処理が得意な子。CPUの中にも少し住んでる。たまに、この子が住んでないCPUもある

グラボ（グラフィックボード）

GPUの親分。GPUの団体みたいな。強力なGPU。最近はやりのでーぷらーにんぐでは、CPUよりこの子が頑張る

コア

仕事する人。最近はマルチ（複数のって意味）コアのCPUが多いですね。沢山いると仕事が捗るけど、仕事の割り振りは大変。Xeon（じーおん）という、インテルのCPUはコアが沢山。

メモリ、HDD、SSD、キャッシュ、ハッシュ、64bit…etc

他に分かりやすい解説があるはずなので割愛。メモリが小さいとソフトが動かないことがあるとか、32bitだと動かないことがあるとか、割と致命的なこともあるので要望があれば記事にします

インテル（Intel、悪の枢軸）

CPUを売る最大手の会社。Corei3,i5,i7とかいうシリーズを持つ。せろりん、セレロン（Celeron）、Pentium（ぺんちあむ）とか。独占禁止法

AMD

安くて高性能が売りの会社。グラボも作ってるよ。スペックでIntelに勝てていなかったが、最新CPUのRyzenシリーズは破竹の勢いでIntelを追い込んでいる。頑張れ。AMDファンは熱量がある。むしろ、熱量がないとAMDを選べない程にIntelの力は強大であったと言える。

クラスタ化

GPS将棋が東大のパソコンをたくさん使って三浦先生に勝ったのが有名。パソコンを沢山使ってみんなでお仕事すること。誰かがサボったりデータを捨てたりネットワークから居なくなったりとかとかすると途中の読み筋が消えたりするから、仕事の割り振りは大変だよ。

thread（スレッド）

お仕事してる人（擬人化）の数。コアが分身して、コアよりスレッドが多くなることもあります

拡張子

ファイルの最後についてる、.exe(実行するもの).kif（棋譜データ）.csa（違うタイプの棋譜データ）など。この部分を書き換えると色々まずいのであんまり推奨しない。

ちなみに、.kifとか.csaのファイルを右クリック→プログラムから開く→メモ帳とすると、文字で棋譜を見れる。このテクは覚えておいて損はないかも。

.NET(現在では殆ど.NET Frameworkのことを指す。読みは一般に、ドットネット）

コンピュータが使う七つ道具みたいな詰め合わせだと思ってくれると分かりやすいと思う。これが古い（又は、古いソフトを動かすのに道具が新しすぎる）とソフトが動かないことがある。

margin（マージン）

余白のこと。時間切れにならないように、手を少し早く出力する設定をするときもある。

.db

拡張子の一つ、データベース。単にデータベースとだけ言う場合は、整理された情報の集まりのことを指す。特にコンピュータ将棋の時は主に定跡で使われる。

エラーメッセージ

出たらとりあえずググろう。英語なら訳そう。

システム

しすてむ。ものを構成する仕組みの全体

システム - Wikipedia

互換性

システムの部品の一部を入れ替えても、動作する状態のことを、互換性があるという。

特に、部品Aと部品Bを置き換えることができる時、互換性があるという。

処理

計算すること、お仕事すること。CPUは社畜さん。

電気代

CPUはお仕事する時に電気を食べます。おっきい仕事だと一杯食べます。将棋ソフト開発者さんは、大食漢のCPU（値段高い）を買ってきて、沢山乗るお皿とかまな板とか冷蔵庫を買ってきて（メモリ、HDD、SSD。高い）お仕事してもらってます。

家賃より高いこともあるとか。

やねさんは赤字と日々戦っている

暖房

沢山仕事したCPUやGPUは熱を持ちます。冷やさないといけません。冬は暖房代わりになります。夏は冷房をガンガンかけないとCPU達も夏バテします。

団体とか大会とか

CSA

Computer Shogi Association。コンピュータ将棋協会

SDT

Shogi Denou Tournament。将棋電王トーナメント。ドワンゴ主催、コンピュータのスペックは固定。トーナメント方式は決勝リーグだけ。

WCSC

World Computer Shogi Championship

世界コンピュータ将棋選手権。PCのスペック制限なし。クラスタと金の力がものをいう…

追記予定アル

加筆するかもしれないワード

次元下げ、rootstrap、やきなまし、線形、嵌め手、ルーチン、GUI、回帰、キメラ、高速化とか枝刈り、Github、フリーソフト、ライセンス、教師、強化学習、時間攻め、局所解、サチる、発散、まふ定跡、ベンチマーク、Ubuntu、Bitboard、AVX、64bit、バイナリ、ソースコード、オープンソース、Stockfish、合法手、合議、αβ、MiniMax、ゲーム木、過学習、bitboad

and more...?難しい用語専用の上級者向け解説記事を執筆する予定があるかも…？