「Sayuri で徹底解説! チェスエンジン・テクノロジー!」は、僕の自作チェスエンジン「Sayuri」に使われているチェスエンジンの技術を漫才形式で紹介するコーナーです。
第13回のテーマは「レイト・ムーブ・リダクション」です。
解説 & 漫才
僕
「今回のテーマは「レイト・ムーブ・リダクション」だよ。」
Sayuri
「「トイレ・ブーム・ぶわっくしょん!」・・・つまり「トイレが流行ると風邪が流行る」という古代ギリシャのことわざどすな。」
僕
「その通り。
Wikipedia によると、古代ギリシャではトイレがなく、町中で排泄物が垂れ流しの状態だったらしい。
その不衛生さから命に関わるレベルの伝染病がよく流行していたようだ。
つまり「風邪」のような軽い病気は病気のうちに入らなかったのだろう。
しかし、「トイレ」がブームになれば町が清潔になり、命に関わる伝染病が減少し、逆に「風邪」のような軽い病気が世間に注目され、「トイレが流行ったせいで風邪が流行っちまったじゃねぇか!」と町の人々が怒り出すんだな。
これがいわゆる「トイレ・ブーム・ぶわっくしょん!」というやつだ。」
Sayuri
「・・・・・・・・・・・・。」
僕
「・・・・・・・・・・・・。
「レイト・ムーブ・リダクション」というのは「後半の指し手は探索する深さを浅くしちゃうよ!」みたいなやつ。」
Sayuri
「「後半」って何の「後半」どすか?」
僕
「「ムーブ・オーダリング」で順序付けられた、探索すべき候補手の「後半」だ。」
Sayuri
「以前の記事によると、「ムーブ・オーダリング」はその局面で探索すべき候補手を、「高い評価値になりそうな順」にならべるアルゴリズムだったどすな。
その「後半」ってことは、あまり高い評価値にならないっぽい候補手ってことどすか。」
僕
「うん。
そういう候補手の探索の手抜きをするってわけだ。」
レイト・ムーブ・リダクションの概要
Sayuri
「「手抜き」って具体的に何をするどすか?」
僕
「要は、「探索する深さ」を 1プライほど浅くして「ゼロウィンドウ探索」をし、「アルファ値」を超えるかどうかを調べるんだ。
超えれば「リダクション失敗」として、普通の探索で再探索する。」
Sayuri
「本当に探索する深さを浅くして探索していいどすか?
浅くした深さで探索してアルファ値を下回っても、もしかするとちゃんとした深さで探索したらアルファ値を超えるかもしれないどす。
で、さらに悪いことに、その手はもしかしたらその局面の「最善手」かもしれないどす。
だとしたら、「最善手」を見逃してしまったことになるどす。」
僕
「うん、そうなったら「最善手」は見逃すね。」
Sayuri
「うん? 何か裏がありそうな言い方どすな。
何か奇妙な屁理屈で最善手を見逃さない方法があるみたいどすな。」
僕
「ないよ。 最善手はちょくちょく見逃すよ。
きっと Sayuri もレイト・ムーブ・リダクションでたくさん最善手を見逃していると思うよ。」
Sayuri
「な、なんてことどすか!
コンピュータ・プログラムは計算を間違えないのがウリどす!
「最善手を見逃す」という計算ミスなんてしてたらコンピュータの面目に関わるどす!」
僕
「いやいや、実はこれは・・・・・・」
Sayuri
「きぃいいいい! これはきっと人間の嫉妬どす!
チェスエンジンがあまりにも強いから、悔しくてコンピュータに計算ミスさせているに違いないどす!
そうやってチェスエンジンをワザと弱くして、「コンピュータなんて所詮は機械。 人間にはかなわないよ。」とか言ってコンピュータを嘲笑うつもりどす!
きぃいいいいいいいい!」
僕
「落ち着け。
まず、「レイト・ムーブ・リダクション」ってのは「前向き枝刈り」っていわれる最適化手法なんだ。
この種の枝刈りは「間違うこともある」という前提の枝刈りなんだ。
で、こういう・・・・・・」
Sayuri
「きぃいいいいいいいい!
チェスエンジンに計算ミスさせることを「前向き」とか言っているどす!
これは宣戦布告どす! 人類による人工知能に対する宣戦布告どす!」
僕
「普通は逆じゃないか? SF ってのは人工知能が人類に宣戦布告するもんじゃないのか?
まぁいいや。
で、こういう「前向き枝刈り」ってのは、以前話した「イテレーティブ・ディープニング」ってやつが関係してくるんだ。」
Sayuri
「「イテレーティブ・ディープニング」ってのは最初に 1プライ探索して最善手を出して、次に 2プライ探索して最善手出して・・・って感じで何度も最善手を出しながら探索するゲームの木を大きくしていくやつどすな。」
僕
「うん。
でな、「前向き枝刈り」ってのは、その 1回のサイクルをいい感じで早くしようってやつなんだ。」
Sayuri
「なんとなく分かるような、分からないような・・・どす。」
僕
「例えば、あるサイクルで「ある局面の候補手」がこんな感じにあったとする。」
僕
「で、「レイト・ムーブ・リダクション」は前の方の指し手はちゃんと探索し、後ろの方の指し手は少し浅く探索するので、各候補手の探索する深さはこんな感じだ。」
僕
「で、とりあえず今回のサイクルはこれで探索する。
で、次のサイクルになるとその局面の各候補手の探索する深さは、1プライ増えてこんな感じだ。」
僕
「そのまた次のサイクルになると各候補手の探索する深さは、さらに 1プライ増えてこんな感じだ。」
僕
「ってな感じで、サイクルが回れば回るほど、その局面で探索する深さはどんどん深くなる。
で、こうやって深くしていけば・・・
- 前のサイクルで見逃した最善手が後のサイクルで発見できるかもしれない。
- 1回のサイクルの探索時間が早くなるので、重要そうな候補手はより深く探索できるようになる。
・・・ってなるわけだ。」
Sayuri
「うーん・・・やはり、分かったような分からないような・・・・・・どす。」
僕
「温泉が「出そうな所」と「出なさそうな所」を想像してくれ。」
Sayuri
「したどす。」
僕
「制限時間がある時、どっちを深く掘りたい?」
Sayuri
「「出そうな所」どす。」
僕
「うん。
で、「出そうな所」を「5メートル」、「出なさそうな所」を「2メートル」掘ったとする。」
僕
「で、時計を見たら、まだ時間が余ってた。
だから「出そうな所」と「出なさそうな所」をそれぞれさらに「1メートル」掘るんだ。」
僕
「で、時計を見たら、まだ時間が余ってた。
だから「出そうな所」と「出なさそうな所」をそれぞれさらに「1メートル」掘るんだ。」
Sayuri
「コピペしたどすな。」
僕
「で、時計を見たら・・・ってな感じで掘っていく・・・ってな感じ。」
Sayuri
「分かったどす。
分かったどすが、うちはその例え話は「レイト・ムーブ・リダクション」の説明にあまり向いていないような気がするどす。」
僕
「うん。 僕も今そう思った。」
具体的なアルゴリズム
僕
「具体的にどんな感じで実装すればいいか解説するよ。」
Sayuri
「しろどす。」
僕
「先ずはざっくりと擬似コード。」
# (注) 「アルファ値」は現在の最高得点で更新されている。
MakeMove(move)
if 「レイト・ムーブ・リダクション」していい?:
score = -Search(残り深さ - 2, -(アルファ値 + 1), -アルファ値)
else:
score = アルファ値 + 1
if score > アルファ値:
PV 探索する。
UnmakeMove(move)
Sayuri
「ざっくり過ぎて色々質問しないといけないコードどすな。
先ず、「レイト・ムーブ・リダクションしていい?」ってなんどすか?」
僕
「「レイト・ムーブ・リダクション」は「前向き枝刈り」なので、それをやるべき候補手かどうかは慎重に選ばなければいけない。
Sayuri で「レイト・ムーブ・リダクションをしない条件」は・・・
- 「探索するべき残りの深さ」が 4プライ以下だった場合。
- その候補手の順番が前半 30パーセントだった場合。
- その候補手が「駒を取る手」だった場合。
- その候補手が「昇格する手」だった場合。
- その候補手が「キラー・ムーブ」だった場合。
・・・だ。
つまり「レイト・ムーブ・リダクションしていい?」ってところで上記の条件を確認するってわけだ。」
Sayuri
「ってことは・・・
「score = -Search(残り深さ - 2, -(アルファ値 + 1), -アルファ値)」
・・・の部分が「レイト・ムーブ・リダクション」ってわけどすな。
で「残り深さ - 2」の「- 2」ってのは何どす?」
僕
「えーと、「残り深さ」は現在のノードの「探索するべき残りの深さ」だ。
だから、候補手を探索するにはそこから 1プライ引いてやらなきゃいけない。
つまり「残り深さ - 1」だ。
で、「レイト・ムーブ・リダクション」は 1プライさらに浅くするので、さらに 1プライ引いてやる。
つまり「残り深さ - 2」だ。」
Sayuri
「じゃあ、「レイト・ムーブ・リダクション」しなかった時の「score = アルファ値 + 1」って何どす?」
僕
「それは「レイト・ムーブ・リダクションしなかった」ということを「レイト・ムーブ・リダクションしたけど最善手かもしれないので再探索してね」と同じ意味にするためのトリックだ。」
Sayuri
「意味が分からんどす。」
僕
「通常の探索をする条件は・・・
- 「レイト・ムーブ・リダクション」しなかった時。
- 「レイト・ムーブ・リダクション」したけどアルファ値を超えちゃった時。
・・・だ。
で、いちいち小難しい条件分岐を作るのが面倒なので、「レイト・ムーブ・リダクションしなかった時」に評価値をアルファ値を超えさせて、「アルファ値を超えちゃった」と見せかける。
すると通常の探索をするときの条件は「評価値がアルファ値を超えた時」一つでよくなる。」
Sayuri
「それが次の「if score > アルファ値」ってやつどすか。 なるほどどす。」
僕
「アルゴリズムは以上だ。」
最後に
Sayuri
「今回のテーマは「温泉を掘り当ててお金持ちになろう!」どす。」
僕
「温泉って 1000メートルくらい掘らなきゃいけないらしい。
しかも掘るのに 1億円くらいかかるし、掘ったからといって出るとは限らないから、元々大金持ちの人しか掘れないね。」
Sayuri
「でもあんさん、昔は手作業で数千メートルくらい掘っていたどす。」
僕
「フッ・・・昔の話さ・・・・・・。」
Sayuri
「(カクテルを振りながら) お兄さん、聞かせてくれないどすか?
その昔話とやらを・・・どす。」
僕
「そうだな、あれは携帯ゲーム機がまだ「ニンテンドーDSi」だった頃、オレはまだ駆け出しの冒険者だった。
天使界から地上に降りたり、イッシュ地方を駆け回ったりしていた。」
Sayuri
「(スッとお酒の入ったグラスを差し出し) 「インペリアル・フィズ (楽しい会話)」どす。
あちらのお客さんからどす。」
僕
「ありがとう。 (ニコッ)」
Stockfish先生
「気にしなくていいのじゃ。」
僕
「数々の冒険を成し遂げ、冒険者として名を上げていったある日、オレは膝に矢を受けてしまってな・・・・・・冒険者の道を断念した・・・・・・。」
Sayuri
「(カクテルを振りながら) ・・・・・・・・・・・・。」
僕
「悲嘆に暮れていたオレは、ある時「DSi ウェア」というのを知った。
そこにはピンク色の衣装を付け、ドリルを手にした少年の姿があった。
彼は自分を「ミスタードリラー」と名乗っていた。
きっと彼はドリルに誇りを持っていたのだろう。」
Sayuri
「(カクテルを振りながら) 新しい出会い・・・どすな。」
僕
「ああ・・・・・・。
彼はオレに言った、「僕を十字キーと Aボタンで動かしてほしい」と・・・・・・。
オレは彼の切なる願いを聞いてやろうと必死で動かし地面を掘ってやった。
しかし彼は・・・彼は・・・・・・。」
Sayuri
「(カクテルを振りながら) ゴクリ・・・・・・。」
僕
「上から降り注ぐ大量の岩盤に押しつぶされて死んでしまった。」
Sayuri
「(スッとお酒の入ったグラスを差し出し) 「ギムレット (長い別れ)」どす。
あちらのお客さんからどす。」
僕
「ありがとう。 (ニコッ)」
Stockfish先生
「辛かったじゃろうな。」
僕
「しかし、それからなぜかオレのもとに「ミスタードリラー」を名乗る少年たちが次々と集まってきた。
そしてオレは彼らの望むままに動かし、そして掘った。」
Sayuri
「(カクテルを振りながら) 「地面を」どすな。 「少年を」じゃなく。」
僕
「何人・・・何十人・・・何百人の少年を犠牲にし、オレはついに 5000メートル以上掘ることに成功した!」
Sayuri
「(スッとお酒の入ったグラスを差し出し) 「アプリコットクーラー (素晴らしい)」どす。
あちらのお客さんからどす。」
僕
「ありがとう。 (ニコッ)」
Stockfish先生
「お祝いじゃ。」
僕
「多くの犠牲のもと、大偉業を成し遂げたオレは空を見上げてこう思った・・・・・・。」
Sayuri
「(カクテルを振りながら) ・・・・・・・・・・・・。」
僕
「掘るの飽きた。」
Stockfish先生
「ワシは帰るのじゃ。」
Sayuri
「(カクテルを振りながら) またのご来店を・・・どす。」
僕
「ん? あの人、お金払った?」
Sayuri
「(カクテルを振りながら) は? 何を言っているどす?
全部あんさんの奢りと言っていたどすが?」
僕
「んだと! あのジジイ、オレの金で飲んでたのか!
ちゅーか、オレによこした酒もオレの金じゃねぇか!
やってられるか! 帰る!」
Sayuri
「(カクテルを振りながら) お代は 1億万円になるどす。」
僕
「なんだよその「子供が思いつくギャグ」レベルの金額は!
払えるか! そんなもん!」
Sayuri
「(カクテルを振りながら) 仕方ないどす・・・(キュピーン!)」
僕
「ぐわぁ! 体が動かない! 超能力かっ!」
Sayuri
「(カクテルを振りながら) あんさんは今から地下 5000メートルで強制労働どす。
1億万円分働くどす。」
僕
「いやだぁああああ! わぁああああああああ!」
Sayuri
「ちゃんちゃん♪ どす。」
一同
「ってなわけで、次回も乞うご期待!」「どす。」
