eye_catching

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

第16回のテーマは「ナルムーブ・リダクション」です。

解説 & 漫才


「今回のテーマは「ナルムーブ・リダクション」だよ!」

Sayuri
「これは「名作『なる麻雀』のブームが去ってガッカリ (気持ちがリダクション) した」っていう 「iMac revision B」 ユーザーの悲しみを表した言葉どすな。」


「えーと、それはいろいろ詳しく説明しないと分からないボケだな。」

Sayuri
「説明しろどす。」


「先ず「なる麻雀」ってのは麻雀のビデオゲームだ。」

Sayuri
どんな麻雀ゲームどすか?」


「で、「iMac revision B」ってのは 2代目の iMac だ。」

Sayuri
「なる麻雀」はどんなゲームどすか?」


「昔、インターネット回線がまだ「ADSL」だった時代、僕は父に Mac を使いこなす修行をさせられていて、iMac の revision B を買ってもらい、Photoshop や Illustrator をいじくり回していた。」

Sayuri
「なる麻雀」の内容を知りたいどす。」


「しかし、僕には不満があった……それは、「Mac にはゲームがほとんどない」ということだった。」

Sayuri
「なる麻雀」の話をするどす。」


「そこで僕は大阪のゲームショップの「地下」に行き、Mac で動くゲームを探していた。
そこで見つけたのが「なる麻雀」だ。」

Sayuri
「ようやくゲームの内容が分かるどすな!」


「そして暇を見つけてはそのゲームにのめり込んだんだが、時代の移り変わりとは残酷なもの……。
「Mac OS」が「OS X」になり、「revision B」では「OS X」は重すぎて動かせず、泣く泣く「なる麻雀」とともに「revision B」を廃棄処分した。
つまり、冒頭のボケは「僕の中の『なる麻雀ブーム』が去ってしまってガッカリした」……ってやつだ。」

Sayuri
「もういいどす。 うちが「なる麻雀」の説明をするどす。
「なる麻雀」とは…………」


ゲフン! ゲフン!

Sayuri
「麻雀で負けた女の子が勝った女の子にセクシーなイタズラをされて…………」


ゲフン! ゲフン! ゲフン!

Sayuri
「最終的には部屋の中で女の子がオシッコするっていう…………」


ゲフン! ゲフン! ゲフン! ゲフン!

Sayuri
マニアックなセクシー麻雀ゲームどす。」


もーーーーーーーーーーーー!
「ゲフン! ゲフン!」って言ったらそこで説明止めろよな!

Sayuri
「「なる麻雀」のセクシーシーンのスクリーンショットを撮って、Photoshop で加工して壁紙を作っていたことは父親には内緒どす。」


もーーーーーーーーーーーー!
Photoshop のレッスン本の成果がさっそく活かされちゃったよーーーー!」

Sayuri
「つかみ」が長すぎたどす。
本題に早く入るどす。」


「了解。
「ナルムーブ・リダクション」ってのは「探索中に試しに 1手パスしてみて、それでもベータ値を超えるなら探索する深さを下げる」ってやつだ。」

Sayuri
「よく分からないどす。
詳しく説明しろどす。」

ナルムーブ・リダクション

header_1


「繰り返しになるけど、「ナルムーブ・リダクション」ってのは「探索中に試しに 1手パスしてみて、それでもベータ値を超えるなら探索する深さを下げる」ってやつだ。」

<null_move_reduction

Sayuri
「言ってる意味がよく分からないどす。」


「じゃあ、ちょっと聞くけど、チェスで 1手パスしたらどうなる?」

Sayuri
失格どす。


(ズコッ!)
じ、じゃあ、1手パスできる変則チェスで 1手パスしたらどうなる?」

Sayuri
「「終盤」でなければ、たぶんメチャクチャ不利になることが多いと思うどす。」


「その通り!
「終盤」の場合は「パスしたら負けない」って場合がよくあるけど、たいていはパスした方がメチャクチャ不利になる。
言い換えると、たいていの場合「パスは最悪手」だ。」

Sayuri
「それがどうしたどす?」


「じゃあ、とあるノードで試しに「1手パス」して探索続行してみたとする。」

step_1


「その結果、「ベータ値」を超える高い評価値が返ってきたとする。」

step_2


「最悪手」の結果がベータ値を超えるなら、他のどんな手を指してもベータ値を超える……そうは思わない?」

Sayuri
「まあ、「最悪手」より低い評価値はないはずどすな。」


「だから「この先はあんまり探索しなくてもベータ値超えるっしょ♪」ってな感じで探索する深さを浅くするんだ。」

step_3

Sayuri
「屁理屈は分かるどすが、そんなことあり得るどす?」


「あるよ。
それは、親ノードが「すっごい悪手」を探索し始めた時だ。
想像してみてほしい。
対戦相手が直前で「すっごい悪手」を指したら、1手パスしても勝てる気しない?」

Sayuri
「あー、オンラインチェスでごくたまにそういうことあるどすな。
この手で何をやっても次の手でメイトできる時とかあるどす。」


「そういう「すっごい悪手」が探索中はよく出てくるんだよ。
で、そういう時は真面目に探索せずに深さを浅くして探索効率を上げる……それが「ナルムーブ・リダクション」ってやつだ。」

Sayuri
「うーん……でも「二度手間」感がハンパないどす。
本当に探索効率が上がるどすか?」


「えーっとね、毎回やると探索効率は下がっちゃう。
だから制限をかける。」

Sayuri
「どんな制限どす?」


「制限は……

  • 「ナルムーブ・リダクション」の探索中にはやらない。
  • 「ゼロウィンドウ探索」中のみ行う。

……ってな感じ。」

Sayuri
「どういうことどす?」


「先ず 1つ目の説明。
「ナルムーブ・リダクション」中に「ナルムーブ・リダクション」をしちゃうと「アホみたいなこと」が起こる。
ほら、オセロで自分が「パス」したあと相手が「パス」すると「何も変わらない」という不毛の時間を過ごすことになるだろ?
そういう「アホみたいなこと」にならないように「ナルムーブ・リダクション」中は「ナルムーブ・リダクション」しないように工夫することが大事なんだよ。」

aho_1
aho_2
aho_3
aho_1


「2つ目の説明。
なんだかんだ言って「ナルムーブ・リダクション」は二度手間だ。
「評価値を知るための探索」で使うと逆に効率が下がってしまう。
なので「ゼロウィンドウ探索」という元々高速な探索をより高速化するために「ナルムーブ・リダクション」を使用するんだ。」

Sayuri
「なるほどどす。
ということは、子ノードに「今、ナルムーブ・リダクション中ですよー!」とか「今、ゼロウィンドウ探索中ですよー!」とか伝える工夫が必要どすな。」


「一番簡単な方法は「探索関数の再起コールの際にそういうフラグを引数として渡す」ってやつだね。」

flag

Sayuri
「昔はうちのコード、テンプレートを使って変なことをしていたどすな。」


「あー、あれは当時の Stockfish のコードのモノマネだな。
テンプレートを使って「普通の探索用の探索関数」「ゼロウィンドウ探索用の探索関数」の 2つの探索関数を作って、普通の探索でしか使わないアルゴリズムは「普通の探索用の探索関数」に書いて、ゼロウィンドウ探索でしか使わないアルゴリズムは「ゼロウィンドウ探索用の探索関数」に書いて少しでもフラグの判定の節約をしようとしていたな。」

Sayuri
「なんでやめたどす?」


「全然高速化しなかったからだ。
それどころか、似たコードを重複して書くというクソ面倒くさいコードになった。
だからやめた。
結局チェスエンジンって「評価関数の呼び出しをどれだけ減らせるか」以外の最適化はあんまり意味がないんだよな。」

Sayuri
「その割には「メタプログラミング」で悪あがきしているどすな。」


「あれはハッカーみたいでカッコイイからいいの!」

Sayuri
だみだこりゃ……どす。」

アルゴリズム

header_2


「いつものように疑似コードでアルゴリズムのお時間です。」

if ゼロウィンドウ探索フラグ and (not ナルムーブ・リダクションフラグ):
    ナルムーブ・リダクションフラグ = True

    MakeNullMove()

    # depth - 4 の部分は調整してね。
    score = -Search(depth - 4, ゼロウィンドウ探索フラグ,
                    ナルムーブ・リダクションフラグ, -beta, -beta + 1)

    UnmakeNullMove()

    if score >= beta:
        depth -= 3  # 調整してね。

Sayuri
「疑問が 2つあるどす。
先ず、MakeNullMove()UnmakeNullMove()ってなんどす?」


「「パスの手を指す」と「パスの手を戻す」って関数だ。
「パス」だから指し手はないけど、手番の変更とかアンパッサン関連の変数とか、いろいろやらなきゃいけないことがあるんだよ。

Sayuri
「次、探索する時に「depth - 4」と大幅に探索する深さを減らしているどす。」


「うん。
「最悪手の探索」だから浅くても結果はそんなに変わらないだろうし、しょせん「前向き枝刈り」だから「多少の間違いは想定内」なんだよ。」

Sayuri
「なるほどどす。」

最後に

Sayuri
「今回のテーマは「Mac ユーザーでもセクシーゲームがしたい!」どす。」


「Mac ユーザーだからといって、皆が皆「意識高い系」というわけではない。
中には昔の僕みたいに Mac のハードディスクのほとんどが「セクシーデータ」で埋め尽くされている人もいる。」

Sayuri
「しかもあんさん、それだけでは飽き足らず、「Virtual PC」と「Windows 98」を入れて Windows のセクシーゲームもやっていたどすな。 父親に内緒で。


「その通り。
しかもそのために勝手に CPU を取り替えて倍のクロックにし、メモリの増設までした。
全て父に内緒でな。

Sayuri
「そんなに Windows のゲームが大好きなのに何で今は Linux 使っているどす?」


「それはな、Mac のヘビーユーザーだった父に「Windows は悪」と刷り込まれたからだ。
Mac Fan って雑誌を何度も読まされ、いかにビル・ゲイツがズルい奴かを勉強させられた。
しかし Mac は高い。 そう何度も買い換えられる代物じゃない。
で、結局 Mac でもなく Windows でもない Linux に漂着したってわけだ。」

Sayuri
「で、Linux を使っているうちにプログラミングに目覚めたってわけどすか。」


「Linux を使っていると嫌でもプログラマーになる。
絶対にシェルスクリプトは組まなきゃいけないし、絶対に Python は使うハメになる。
どっかのスクリプトがバグってたら、コードを読んだり、いじくったりしなきゃいけない。
で、コンピュータが自分の思い通りに動く面白さに気付いたら、いつの間にかいろんなプログラミング言語に手を出してそこそこのプログラマーになっちまうんだ。」

Sayuri
「まぁ、最近はプログラミングよりイラスト制作の方にハマっているみたいどすが。」


「そりゃあ、いくらプログラミングしても「セクシーな美少女」は作れな……コホン! 失礼。
芸術の素晴らしさに目覚めたんだよ。」

Sayuri
「なるほど、あんさんの「人生の原動力」が「セクシー」ということだけはハッキリと分かったどす。」

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