読者です 読者をやめる 読者になる 読者になる

愛とは、全人生をかけてアイドルにチェスを教えること。

フリルドスクエアと行く、奥深いチェスの旅。

一ノ瀬志希のブレイクタイム[ボードゲームと距離概念について]

 

 ディープ・ラーニングというのが昨今話題になってるよね!

 Googleの肝煎り、アルファ碁とか、あとはこの前行われた世界コンピュータ将棋選手権で劇的な結果を残したPonanzaとか。チェスでは個人が開発したのがもう5年以上前の話だったかなぁ。

f:id:rikkaranko:20170503034048j:plain

 でも、今日あたしが今日別に講義するのは、ディープラーニングについてじゃないよ。それは、マキノちゃんにでもやってもらおう!あたしが話すのは、マシンさんたちはどうやって駒の動きを理解してるんだろうネ?って話。これがちょっとでも体得出来たら、人のゲームにも応用できそうじゃない?少なくとも、高性能GPUを頭蓋骨の中に移植する、とかいうより実践的でしょ♪

 

 簡単に言えば、ピースの動き方を計算機的にとらえたらどうなるの?ってこと。角換わりでは、88の角と33の角で、6マス分斜めに動いてるわけだ。でも、88の飛車が33の地点に行くのには6マスじゃいけないよね?そーいうこと!

 6マス分、とかいうのはまず距離概念を考えてあげればいいよね。距離概念、とは二点間の『遠さ』に対して人間サマが与えた、定量的なパラメータのことだよ。じゃ、同じスタートから同じゴールなのに、駒の動きに依存して距離が違う場合はどうしようか?

 こういう問題を、機械の『脳内』ではどう考えてるのかにゃ~、っていうのを、ちょっと覗いてみようじゃないか♪

 

 というわけで、今日扱う数式は、じゃんじゃじゃーん!この3つ~♪

f:id:rikkaranko:20170507225943p:plain

(1)マンハッタン距離 

 マンハッタン距離の定義は、

f:id:rikkaranko:20170507232932p:plain

と、こうなってるよ。

 これは日常生活ではあまり馴染がない距離公式だよねぇ……って、日常生活であまり距離を数学的に測ったことがない?なるほど、そーゆー人もいるのか~!

 

 あたしたちが普段『直線距離』と口に出すとき、それは往々にして2点A,B間の最短距離を指しているワケだ。そして、やっぱり往々にしてそれはある定義された距離を用いている――Do you understand?ここまではいい?その『定義された距離』、というのはこれだよね。ユークリッド距離、とでも言おうかにゃ。ユークリッド空間で通用する最短距離、のことだからね。

f:id:rikkaranko:20170507234458p:plain

 要は、軸を2本取った世界、2つのVectorに張られる世界、ピタゴリアン・セオレムの斜辺、2次元ノルムの……色んな言い方があるけれど、x軸とy軸を想定した紙面の上での、2点間の距離だよ。

f:id:rikkaranko:20170508013917p:plain

 点Pと、原点Oとの距離とは、この赤い線分のコトだね!原点OのOとは、全ての始まりであるゼロであるとともに、出発点であるOUCHI『お家』のOなんじゃないかって……それはまぁ、いっか~♪

 

 そして、この節の冒頭で定義したマンハッタン距離、というのは、数式をあたしたちの言葉に翻訳すれば、マンハッタンのような縦と横の区画に区切られた町で、ある点からある点へと移動するときに動くだけの距離、ってことだよ。

 マンハッタンがわかりにくかったら、京都でもなんでも。平城京でも。平城京で、二坊三条から、五坊六条に行くためには、2,3,4,5坊の4区画と、3,4,5,6条の4区画で、計8区画移動するのが『最短』になるよね?まさか、お家を突っ切ったり空を飛んだりしちゃダメだよ~。

 つまり、こんどはこーゆーディスタンスを考えてることになる。

f:id:rikkaranko:20170508014630p:plain

  この図だと、羅城門から四条三坊かにゃ?羅城門は九条大路と朱雀大路の交点にあるからね!x軸が九条大路なら、点Pは、縦に9,8,7,6,5,4の横が0(朱雀),1,2,3で(4条,3坊)って訳だね~。ここに羅城門から寄り道せずに往く経路を今考えると、ずーっと九条大路沿いに行ってから1回左折して三坊大路を往く赤の経路と、いきなり朱雀大路から八条大路に曲がって、そのあと二坊大路に入ってずーっと行き、四条大路を通ってP納言の家に行く青の経路と、なーんの違いもござらぬ!ってこと。これが、マンハッタン距離だよ。だから、別名をシティ・ブロック・ディスタンスとも言われるんだ。ブロック区画化された市街地をタクシーキャブが行く様子、ってことでタクシーキャブ・プロブレムとか呼んだりもするね。

 これ、チェスでいうとなんだと思う??

 そうなの!ルークの動きなんだよねぇ。羅城門をRa1とすれば、さっきのP納言の家はRe3だよね。ここに到達するルークの最短移動距離は?ってことをコンピュータ・ソフトが考える時に使っているパラメータこそ、他ならぬマンハッタン距離なんだよ。

 よく、平城京のことを『碁盤の目』とかって言うじゃない。あれあたし的にはしっくりこないなぁって思うんだ。だって、囲碁は『駒が移動するボードゲーム』じゃないもん。寧ろ『将棋盤の目』だよねぇ……。あ、でも目って言い方もしないか、ケッコー難しい問題だ。

 

 マンハッタン距離、名前は仰々しいし、出て来るのはキョリクーカンとかいう数学でも特に厄介な分野だから馴染があんまりないように見えて、実はなかなか身近な概念だったでしょ?もうちょっとこの概念と仲良くなるために、こんなモノを見つけて来たよ。

f:id:rikkaranko:20170508020712p:plain

 これは、見ての通り。東大の前期入試の過去問だね。わお、マンハッタン距離そのものが問われてる。しかも、その概念を知らなくてもその場で解かせよう、ってことで丁寧につけられた誘導が(1)なんだね。ホントは(2)まであって、それがメンドクサイやつなんだけど、今日は(1)だけ!

 東大の問題だから難しそう……?ほんとかにゃ~、実際、これだけのハナシだよね!

f:id:rikkaranko:20170508144244p:plain

 求める範囲は、斜線部。境界上の点は含む。以上!

 

 ちなみに日本の国立大学受験の、記述方式の数学は教授たち曰く大体加点法で採点してるらしいから、アタシの解答だとたぶん、東大なら1問20点だから2~3点くらいカナ?科学なんてまず第一に解ければいーのいーの!解けた人と、説明する人は別だっていいんだから。

 

 ま、そんなわけで、マンハッタン距離についてでした。はーい、質問あるひと?じゃ、次行こうか。

 

(2)チェビシェフ距離

f:id:rikkaranko:20170508021159p:plain

 これが、チェビシェフ距離。チェビシェフ不等式、とかチェビシェフフィルタ、とかさ、理系の人なら聞いたことあるんじゃなーい?これは別名をチェスボード・ディスタンスとも呼ばれてるよ。

 2点間の距離を、絶対値の差の最大値と定義する、ってどういうこと?っていうと、つまりは『斜め方向の移動も、縦や横の移動と同じくカウントする』ってことだね。例としては、こんな感じ~♪

f:id:rikkaranko:20170508021659p:plain

 Kd4がKb6に行くのは、斜めに2回動けばいい、だからd4とb6の間のチェビシェフ距離は2だね。これを、(b~d=)2でも、(6-4=)2と考えるんでもいいよ。

 Kd4がKf4に行くのも、2だね。これは、(4-4=)0と、(b~d=)2の最大値(max)を取って、2、とする、とこーゆー訳だよ。

 Kd4がKc2に行くのは、(4-2=)2と(d~c=)1のうち最大値を採用して、やっぱり2だね!

 つまり、d4にいるキングはb6、f4、c2どこに動くにも最低2回で到達する、ってこと。ルークと違ってチェスでは他のピースには斜め方向の動きがあるでしょ。だから、ルーク以外のピースは、チェスソフトではマンハッタン距離ではなくこのチェビシェフ距離を採用して移動距離を演算してるんだって。

 

 ユークリッド距離、マンハッタン距離、そしてチェビシェフ距離の一番の違いを視覚化したのが次の図だね。これは、各距離概念に於いて、原点Oから等距離にある点を結んだ図なんだよ。

f:id:rikkaranko:20170508022509p:plain

 もちろん、青がユークリッド距離だよ。円とは中心から等距離にある点の軌跡だもんね。

 赤が、チェビシェフ距離だね。縦横斜めに1マス動けるキングが、1回の移動で到達し得るマスの軌跡を描いたなら、赤い正方形が得られるでしょ♪

 黒はマンハッタン距離だよ。にゃは、わかりやすいでしょー♪

 

(3)ミンコフスキー距離

 これは、補足!でも、大事な補足。

 チェスソフトで用いられている距離概念は、(1)のマンハッタン距離と(2)のチェビシェフ距離だった、っていうのは観て来たけど、これらを別々に定義してやるのは2倍手間がかかる。だから、なんとか1つの形式で書けないか……ってことを昔の偉いスーガクシャは考えたんだ。スーガクシャっていうのは、究極の楽したがりさんたちのことだからね。類似の概念を束ねることで、効率と理解の扶助とする……ウンウン、つまり楽したがり屋さんってことだよ!

 

f:id:rikkaranko:20170508023039p:plain

 ミンコフスキー距離、と呼ばれるよ。これが?マンハッタン距離とチェビシェフ距離の一般化?って思うよね。

 p=1のときが、マンハッタン距離でしょ。

 そして、p→∞のときが、チェビシェフ距離だよ。無限に飛ばすってことは、つまり一番作用の大きい成分だけを考えるってことだから、即ちマキシマムを考えるわけだね!

 ちなみに、p=2のときは、そうだよ、ユークリッド距離になるんだ。1/2乗っていうのは√をとることと一緒だもんね。

 ミンコフスキーは人の名前。彼の最大の業績は、フフン、そうだね。数学嫌いのアルバート・アインシュタインに数学を教えたことにあるのだよ!

 

 厳密には、あと2変数同士に相関がある時には統計学から借用してきたマハラビノス汎距離を使ったり、ユークリッド距離の互換概念である標準ユークリッド距離を使ったりもするんだけど、大体今回紹介したものが、チェスの距離測定では用いられているんだよー♪

 実際、ディープラーニングでも以上6距離概念が使われているんだよ。機械学習の効率化に於いて、こんな簡単なアルゴリズムが使われてるなんてちょっと意外でしょ?真実なんて、その辺に転がってるものなんだってば。ただ、ちゃんとそれと分かる人が磨いてやらないと真実には永遠に辿り着けない、それだけの話。科学者なんて、みんな自分が最初に真実を見つけたい野望と、自然の中の真実の美しさへの憧憬に囚われたドレイなんだよ~♪

 

 そういえば、チェスに於ける『テンポ』の概念って説明されたんだっけ。柚ちゃんの4回目。これも、感覚的には損とか得とかだけど、数学的には最短距離を想定しているから出て来る計算結果の話だよね。あたしにはチェス盤は、極めて精緻な数学の世界として見えているんだ。

 こーんなアプローチだって、チェス盤上の真理を追究するのには一助になるかも、でしょ?なんたって、ボドヴィニク曰く、

ーーチェスは論理の科学を表現する芸術。

っていうくらいなんだから!

 

(続く)