「Sayuri で徹底解説! チェスエンジン・テクノロジー!」は、僕の自作チェスエンジン「Sayuri」に使われているチェスエンジンの技術を漫才形式で紹介するコーナーです。
第6回のテーマは「イテレーティブ・ディープニング」です。
解説 & 漫才
僕
「今回のテーマは「イテレーティブ・ティープニング」だよ。」
Sayuri
「「イテレーティブ」は「繰り返して」で「ディープニング」は「深めること」どす。
つまり日本語に訳すと、「お前、また深き闇に落ちたの? www」どす。」
僕
「大学に入って中二病を再発した人の悪口はやめろ。
「イテレーティブ・ディープニング」ってのは「探索関数」を「探索深さ」を増やしながら繰り返す方法のこと。」
Sayuri
「何を言っているのか全然分からんどす。」
僕
「分からないのは仕方がない。 これはチェスエンジンのちょっと「常識外れ」な部分だから、言っている意味が頭に入ってこないと思う。」
Sayuri
「分かるように言えどす。」
僕
「そうだな。
前回紹介した「アルファ・ベータ法」で「深さ優先探索」ってのを思い出してほしい。
きっと皆はあれを見て、「えっ? どうやって『時間制限』で探索を終了させるの?」という疑問を持ったと思う。」
Sayuri
「別に疑問に思わなかったどすが。」
僕
「思ったことにしてくれた方が話が早かったんだけどな。 察しろ。 クソが。
じゃあ、疑問に思わなかった人のために話すよ。
「深さ優先探索」ってのはその性質上、予め決めておいた探索の「深さ」の「ゲームの木」を全て探索し終えないと「最善手」は見つからないんだ。
だから「時間制限」を設定し、その設定された時間で探索を中断してしまうと「最善手」が分からないんだ。
そうなると「何秒間思考する」みたいなことができなくなって、持ち時間を上手く使えなくなってしまう。」
Sayuri
「どうしようもないどすな。」
僕
「うん。 その深さ優先探索の「性質」はどうしようもない。
でも、それを「無理矢理」なんとかしたのが「イテレーティブ・ディープニング」なんだ。」
イテレーティブ・ディープニング
僕
「じゃあ、具体的にどんな風に「無理矢理」か説明するよ。」
Sayuri
「しろどす。」
僕
「「イテレーティブ・ディープニング」ってのは・・・
- 先ず「1 プライ」の深さの「ゲームの木」を探索して最善手を出す。
- 次に「2 プライ」の深さの「ゲームの木」を探索して最善手を出す。
- 次に「3 プライ」の深さの「ゲームの木」を探索して最善手を出す。
- 「4 プライ」「5 プライ」と制限時間が来るまで「ゲームの木」を巨大化させながら何度も探索して何度も最善手を出す。
・・・ってな感じ。 (「プライ」ってのはチェスの「半手」のことで将棋での「1手」に相当する。)」
僕
「これだと、例えば「10 プライ」の「ゲームの木」を探索中に制限時間が来ても、「9 プライ」の「ゲームの木」の最善手を使えば OK ってことになる。」
Sayuri
「理屈は分かったどす。 でもそれだと「二度手間」どころか「十度手間」どすな。
しかも「1 プライ」から「8 プライ」までの探索は「無駄」ってことになるどす。」
僕
「そう思うかもしれないけど、実はそうでもないんだ。
先ずは「そうでもない理由・その 1」、「探索時間の大部分は『一番大きなゲームの木』の探索に使われている」ってこと。」
Sayuri
「どういうことか説明しろどす。」
僕
「「探索時間」のほとんどは「葉ノードの評価」に使われている。
だからそれぞれの大きさの「ゲームの木」の「葉ノード」の数を探索時間ってことにして注目してみる。
簡単にするため、各局面の候補手を「30 手」として見積もるよ。
「4 プライ」まで計算すると下図みたいな感じになる。」
僕
「で、例えば「2 プライ」のゲームの木を探索したとすると、「2 プライ」の大きさの「ゲームの木」の「葉ノード」は「900」で、それまでに評価した全ての「葉ノード」は「1 プライ」のやつと足して「930」だ。
つまり「2 プライのゲームの木」の「葉ノード」は全体の「96.8 %」を占めているってことだ。
こんな感じで「最後のゲームの木の葉ノードの数 ÷ 評価した葉ノードの累計」で計算していくと、下図みたいな感じになる。」
Sayuri
「単純計算どすが、ロスはわずか数パーセント程度ってことどすか。
「指数的爆発」恐るべしどす。
ついでに「リア充」も「爆発」するといいどす。」
僕
「アホか。 「リア充」が「指数的爆発」したら、数の力で僕らオタクが爆死するだろ。
とにかくそんな感じで大きな無駄にはならないってこと。
次に「そうでもない理由・その 2」、「それまでの探索内容を利用して探索効率を上げられる」だ。」
Sayuri
「それはつまり「4 プライ」のゲームの木の探索に「1 プライ」「2 プライ」「3 プライ」のゲームの木を探索した内容が利用できるってことどすか?
というか、そもそも「内容」ってなんどすか?」
僕
「「内容」ってのは「トランスポジションテーブル (ハッシュテーブル)」や「キラームーブ・ヒューリスティクス」みたいなやつのことなんだけど、この辺りの詳しい説明はいつかやるのでここでは簡単にしか説明しない。
「トランスポジションテーブル」ってのは、「ある局面」における「最善手」を覚えておく「記憶領域」のこと。
「キラームーブ・ヒューリスティクス」は、「ある深さ」で「ベータカット」した指し手を覚えておくやり方のこと。
これらを使って探索する指し手の順番を変えることで探索するべきノードを大幅に減らすことができる。」
Sayuri
「「順番」を変えるだけでそんなに変わるどすか。」
僕
「メチャクチャ変わる。 その辺りはいつか「ムーブオーダリング」の回でやる。」
Sayuri
「「そうでもない理由」を聞いていてふと思ったんどすが、もしかすると「1回で深く探索」するよりも「イテレーティブ・ディープニング」の方が探索効率が良くなるんじゃないどすか?」
僕
「たぶんね。 計測したことないから分からないけど。
それに「イテレーティブ・ディープニング」は「アスピレーション・ウィンドウズ」という「前向き枝刈り」でさらに効率を上げることができる。」
Sayuri
「なるほど・・・
- トランスポジションテーブル
- キラームーブ・ヒューリスティクス
- ムーブオーダリング
- アスピレーション・ウィンドウズ
・・・と専門用語を連発して読者の頭をグチャグチャに引っ掻き回す作戦どすか。」
僕
「何の意味があるんだよ、その作戦。
っちゅーか、仕方ないんだよ。 チェスエンジンはいろんな技術が同時に使われているから、ステップ・バイ・ステップで説明できないんだよ。
それにそれらの専門用語はいつか解説するつもりだし。」
Sayuri
「「いつか解説する」どすか・・・なるほど、専門用語を連発した理由は「書くことを増やしてブログを延命させること」だったどすか。」
僕
「チッ! バレちまった!」
最後に
Sayuri
「今回のテーマは「専門用語を連発するとなんだか偉くなった気分になる」どすな。」
僕
「そうだな、意外と気持ちよかったな。
とにかくこの「イテレーティブ・ディープニング」を使えば「深さ優先探索」で「何秒間思考する」ってことができるって寸法だ。」
Sayuri
「あんさんも「イテレーティブ・ディープニング」を身に付けて繰り返し試行錯誤できるようにするといいどす。」
僕
「なんか僕がいつも感覚や直感だけで動いているバカみたいな言い方だな。
僕だってちゃんと試行錯誤くらいする。
はっきり言って「ミスター・イテレーティブ・ディープニング」と言っても過言ではない。」
Sayuri
「ほう、「過言ではない」どすか。
じゃあ、普段は何を試行錯誤しているどすか?」
僕
「例えば本屋に IT 関連の技術書を買いに行ったとする。
そして自分が前々から知りたかった技術が書かれている本を見つけたとする。
しかしその本の表紙には「可愛い女の子のイラスト」が描かれてあった。
そしてレジの方をふと見ると「キュートな女子大生」の店員さんがレジを担当している。
お前ならどうする?」
Sayuri
「は? 普通に買うどすが・・・・・・?」
僕
「そうだな、普通はそうするな。 しかし「ミスター・イテレーティブ・ディープニング」である僕は違う。
僕は・・・
- 「この本欲しいけど、表紙がちょっと恥ずかしいなぁ・・・・・・。」
- 「あのキュートなレジの店員さんに『何なのこのオヤジ。 いい年こいてこんな本を買うつもりなの?』とか思われたくないなぁ・・・・・・。」
- 「いやいや、表紙はアレだけど中身は硬派な IT の技術書だ! もしかするとあの店員さんも『このオジ様とても勉強熱心でいらっしゃるわ❤ 素敵❤』となるかもしれない!」
- 「よし! ここは勇気をだしてこの本を買おう!」
- 「でも表紙がちょっと恥ずかしいなぁ・・・・・・。」
- 「2」に戻る。
・・・ってな感じで、延々と「繰り返し、深く深く」考える。
これこそまさに「イテレーティブ・ディープニング」だ!」
Sayuri
「それは「ミスター・若い女の子に好かれたいスケベ思考の中年オヤジ」どす。」
一同
「ってなわけで、次回も乞うご期待!」「どす。」
