eye_catching

「Sayuri で徹底解説! チェスエンジン・テクノロジー!」は、僕の自作チェスエンジン「Sayuri」に使われているチェスエンジンの技術を漫才形式で紹介するコーナーです。

第11回のテーマは「枝刈りの基礎 - ゼロウィンドウ探索」です。

解説 & 漫才


「今回は「ゼロウィンドウ探索」の解説だよ。」

Sayuri
「名前から察するに、「ゼロウィンド」は「風属性の即死魔法」どすな。 全てを無に帰す「ゼロの風」に違いないどす。
問題は残りの「ウ探索」が一体何を表しているか、どすが・・・・・・「ウ」を探索・・・「ウ」・・・「ウ」・・・「ウ」「ウ」「ウ」・・・。
ヤバイどす! ゲシュタルト崩壊して「ウ」が「毛の生えたワ」に見えてきたどす!


「変なところで言葉を切るお前が悪い! 反省しろ!
ちなみに、「ゼロウィンドウ探索」ってのは探索結果の評価値が「ある得点以上(以下)かどうか」を超高速で調べる探索のことだ。」

zero_window

Sayuri
超高速でそんなもの調べてどうするどすか?」


「今後紹介する「前向き枝刈り」ってやつで使う。
多くの「前向き枝刈り」では「アルファ値以下かどうか」とか「ベータ値以上かどうか」みたいなのを調べてから「枝刈り」するかどうかを決めるんだ。」

Sayuri
「ちょっと待つどす。 「前向き枝刈り」ってなんどすか?」


「枝刈り」ってのは探索するゲームの木を小さくすること。 探索するノードの数を減らすことだな。
で、「枝刈り」には「前向き」「後ろ向き」がある。
「前向き」は「たぶんだけどー、このノード、探索しなくてもいいんじゃね?」って感じで「間違った評価値を返す可能性のある枝刈り」のこと。
「後ろ向き」は「このノードの探索は本当に無駄だから探索しません!」って感じで「効率的に正しい評価値を返すための枝刈り」のこと。」

種類 長所 短所
前向き枝刈り 探索するノード数を大量に減らせる。 得られる評価値が間違っている可能性ある。
後ろ向き枝刈り 正しい評価値を得られる。 そんなにノード数を減らせない。


「ちなみに「アルファ・ベータ法」「後ろ向き枝刈り」だ。」

Sayuri
「何が「前」で何が「後ろ」どすか?」


「根拠もないのに突っ走る奴」ってなんだか「バカだけど前向き」って感じがするし、「根拠がないと前に進めない奴」ってなんとなく「賢いけど後ろ向き」な気がする・・・・・・っていう?」

Sayuri
「さては知らないどすな。」


ごめんちゃい。

ゼロウィンドウ探索

header_1


「結論から言うと、「ゼロウィンドウ探索」とは、「アルファ値とベータ値の差を 1 にしたアルファ・ベータ法」だ。
アルファ・ベータ法で「アルファ値」から「ベータ値」の間のことを「ウィンドウ」って言う。」

window

Sayuri
「ゼロ」ウィンドウなのに「1」どすか。」


「「評価値」が「整数」だからね。
差を 1 にすると、アルファ値より大きく、ベータ値より小さい数がなくなる。

window_size

Sayuri
「で、これをどう使うどすか?」


「「ゼロウィンドウ探索」の目的は、そのノードの探索結果の評価値が「ある値以下かどうか」又は「ある値以上かどうか」を調べることだ。」

Sayuri
「具体的にはどうするどす?」


「で、「ある値以下かどうか」を調べたいなら、「ある値」を「アルファ値」に、「ある値 + 1」を「ベータ値」にセットしてアルファ・ベータ法で探索する。
探索結果が「ある値以下」なら、実際の探索結果も「ある値以下」だ。
逆に、「ある値以上かどうか」を調べたいなら、「ある値 - 1」を「アルファ値」に、「ある値」を「ベータ値」にセットしてアルファ・ベータ法で探索する。
探索結果が「ある値以上」なら、実際の探索結果も「ある値以上」だ。

何を調べたい? アルファ値 ベータ値 結果
ある値以下 ある値 ある値 + 1 ある値以下なら真
ある値以上 ある値 - 1 ある値 ある値以上なら真


「ゼロウィンドウ探索の結果の評価値そのものは正しくないけど、探索途中で「ベータカット」が大量に発生するから、超高速に判定できるってわけ。
多くの枝刈りアルゴリズムは、これを使って評価値を見積もって、なんやかんやするって感じ。」

Sayuri
「なるほど、ベテランの刑事さんが家宅捜査で見つけた白い粉を小指につけて舐めるアレみたいなもんどすな。」


「それ、昭和の刑事ドラマだろ!
インターネットのなかった時代はテレビの演出が嘘か本当か調べられないから、みんな信じちゃうんだよ。
昭和のテレビで言ってた「ワカメを食べると毛が生える」って迷信が、薄毛の人々にどれだけの勇気と希望を与えたことか。

Sayuri
「インターネット全盛期の今でも「美顔ローラー」なるものが、大きな顔の人々に勇気と希望を与えているみたいどすが?」


「夢」って大切だよね。

ゼロウィンドウ探索の注意点

header_2


「ゼロウィンドウ探索は、アルゴリズム的には普通の探索と同じだから、普段使っている探索関数を使うんだけど、その際にちょこっと注意点がある。
それは、ゼロウィンドウ探索する時は、探索中に訪れる各ノードに「現在ゼロウィンドウ探索中ですよー!」ってお知らせしないといけない。

notify

Sayuri
「なんでどす?」


「チェスエンジンの探索関数は単純なアルファ・ベータ法じゃなく、いろんな工夫や枝刈りアルゴリズムをたくさん含んでいる。
で、そういった工夫や枝刈りの中には、ゼロウィンドウ探索中に機能すると効率が下がるものがあるんだ。」

Sayuri
「例えば何どすか?」


「一番分かり易いのが、「ゼロウィンドウ探索を使った工夫や枝刈り」だ。
ゼロウィンドウ探索中にさらにゼロウィンドウ探索してしまうからね。
各ノードは「現在ゼロウィンドウ探索中ですよー!」ってお知らせをもらったら、そういう工夫や枝刈りをスキップして飛ばしてやる必要があるんだ。」

Sayuri
「言われてみればそんな気がするどす。」


「逆にゼロウィンドウ探索中でこそ効果を発揮する枝刈りもある。
そいつらは「現在ゼロウィンドウ探索中ですよー!」ってお知らせをもらった時に実行するようにする。」

Sayuri
「どうやってお知らせしたらいいどすか?」


「それは簡単。
探索関数の引数に「アルファ値」「ベータ値」の他に「ゼロウィンドウ探索中かどうかフラグ」を入れればいい。
その引数を見てどのアルゴリズムを実行するかを選択するんだ。
考え方としては・・・

  • 引数のフラグが「ゼロウィンドウ探索ではない」時・・・
    • 普通の探索を「ゼロウィンドウ探索ではない」フラグで実行。
    • ゼロウィンドウ探索を「ゼロウィンドウ探索である」フラグで実行。
  • 引数のフラグが「ゼロウィンドウ探索である」時・・・
    • 普通の探索を「ゼロウィンドウ探索である」フラグで実行。
    • ゼロウィンドウ探索をスキップする。

・・・ってな感じ。」

そのノードのフラグ 普通の探索でセットするフラグ ゼロウィンドウ探索でセットするフラグ
普通の探索 普通の探索 ゼロウィンドウ探索
ゼロウィンドウ探索 ゼロウィンドウ探索 探索しない

Sayuri
フラグが立ったり折れたり、忙しいどすな。」


「「フラグが立ったり折れたり」・・・恋愛シミュレーションゲーム・・・ととのいました!
「ゼロウィンドウ探索」とかけまして! 「恋愛シミュレーションゲーム」と解きます!」

Sayuri
「・・・・・・まぁいいどす・・・そのココロは何どす?」


「どっちも「爆(バグ)弾回避」が大変でしょう!
・・・おあとがよろしいようで。」

Sayuri
「爆弾」システムのある恋愛シミュレーションは「ときめきメモリアル」だけどす。
オッサン世代にしか分からないどす。」


「シュン・・・・・・(涙)。」

最後に

Sayuri
「今回のテーマは「ワカメで髪を増やし、美顔ローラーで小顔になって幸せになろう!」どす。」


「美顔ローラーを流行らせた「テレビショッピング」は人類の夢の宝庫。
食べると痩せる夢の食品や、付けるだけで筋力アップする夢の腹巻き、8万円を越える夢の Celeron マシンなど、人類に夢と希望と愛をお届けしている。

Sayuri
「あんさんの母親も昔 16万円で Celeron マシンを購入していたどすな。」


ハイエンドのゲーミング PC が買える値段の夢の Celeron マシンのことか?
残念だがあれはテレビショッピングじゃなく家電屋さん。
テレビショッピングはなんと・・・その半額だ!

Sayuri
「つまり「ハイエンドのゲーミング PC が買える値段の夢の Celeron マシン」が「ローエンドのゲーミング PC が買える値段」で買えるってことどすか!
それはお得どす!」


「だろ?
話を戻すと、「ゼロウィンドウ探索」枝刈りアルゴリズム必須の予備知識なのでぜひ覚えておいてほしい。」

Sayuri
「話を戻すどすが、「夢」といえばあんさんも 2018年 7月 18日の夜、なかなか不思議な夢を見たどすな。」


ギクッ!

Sayuri
「夢の中で木を素手で叩いて壊して、キューブ状の木材を作ったどすな。」


「やめろ・・・・・・。」

Sayuri
「その木材を頭の中でイメージした四角い枠に並べて「作業台」を作ったどすな。」


「たのむ、それ以上は・・・・・・。」

Sayuri
「いやぁ、不思議な夢どすなぁ。
あっ、そういえば 2018年 7月 18日は「Minecraft Java Edition」のメジャーアップデートの日だったどすな。
まさかとは思うどすが、いい年した中年オヤジが、ゲームが楽しみすぎてゲームの主人公になった夢を見たとか・・・そんな今時子供でもありえない恥ずかしい体験をしたんじゃないどすな?」


そそそそ、そんなわけ、なななな、ないじゃないかっ!
ぼ、僕はもう立派なジェントルマンだぞっっっ!
た、たかがゲーム一つでドキドキワクワクするわけないじゃないかっっっ!」

Sayuri
「そりゃそうどすな。
18日の夜に 5分おきに Minecraft の公式ホームページを見てアップデートを待ち焦がれたり、スウェーデンの時刻を Google で調べて「おい! Mojang! お前の国、もう午後 5時過ぎてるじゃねぇか! なんでまだアップデートしねぇんだよ! こっちはもう 19日だぞ!」ってな感じでイライラしてふて寝したら自分が Minecraft の主人公になった夢を見たとか・・・・・・まさかそんなわけないどすな。」


いやぁああああ! もう言わないでぇええええ!
ゲームの夢を見たこと認めるから! この件はもう忘れてぇええええ!

Sayuri
「あっさり落ちたどすか。 もうちょっとイタブリたかったどす。」

一同
「ってなわけで、次回も乞うご期待!」「どす。」