eye_catching

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

第15回のテーマは「アスピレーション・ウィンドウズ」です。

解説 & 漫才


「今回のテーマは「アスピレーション・ウィンドウズ」だよ。」

Sayuri
「「アスピレーション・ウィンドウズ」・・・「熱望のウィンドウズ」どすか。
きっと「熱血のマック」「情熱のウブントゥ」がそれに続き、「白熱のデビアン」「熱愛のミント」が後を追い、ラストは「熱意のカーリー」「熱狂のテイルズ」がついてくるどすな。」


「ラスト 2つはヤバいので良い子は忘れて下さい。
「アスピレーション・ウィンドウズ」というのは探索の一番初めのノード、「ルートノード」で行う枝刈りだよ。」

root_node

Sayuri
「何か昔「イテレーティブ・ティープニング」を説明する時にチラッと話が出たどすな。」


「そう。
「イテレーティブ・ディープニング」があるからこそできる枝刈りだ。」

アスピレーション・ウィンドウズ

header_1


「アスピレーション・ウィンドウズ」の具体的説明を始めるよ。」

Sayuri
「しろどす。」


「アルファ・ベータ法」ではルートノードで一番最初に探索する指し手の「アルファ値」は「マイナス無限」で、「ベータ値」は「プラス無限」だ。」

root_alpha_beta

Sayuri
「当たり前どす。
「まだ探索していない」ってことは「探索後の評価値が見当もつかない」・・・つまり「探索後の評価値の範囲」は「プラスマイナス無限の範囲」ってことになるどす。」


「その通り。
でもね、もし「いやー、なんだかんだゆーても、だいたいこの範囲内に評価値あるんじゃね?」って思えるとしたらどうする?」

Sayuri
その範囲を「アルファ値」と「ベータ値」にセットして探索してみるどす。
そして、評価値が「アルファ値以下」なら「アフファ値」をもっと下げて再探索「ベータ値以上」なら「ベータ値」をもっと上げて再探索すると効率が良さそうどす。」

out_of_window_1
out_of_window_2
out_of_window_3

Sayuri
「でも「だいたいこの範囲」ってのが全く見当つかないからそんなことは無理どす。」


「と・こ・ろ・が、「イテレーティブ・ディープニング」をしていれば「だいたいこの範囲」ってのが分かるんだな。」

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


「「イテレーティブ・ディープニング」は探索する深さを一つずつ増やしながら何度も探索し直す探索方法だ。」

iterative_deepening


「ってことは、2サイクル目の探索以降は前のサイクルの探索結果を参考にできるってことだ。」

next_cycle


「だから前のサイクルの探索結果の評価値付近にこれから探索する評価値があるんじゃないかって予想できるってことだ。」

Sayuri
「うーん・・・うさんくさいどす。」


「もちろん評価値が全く見当違いになることもよくあるよ。
でも、だいたい合っていることが多いし、全く見当違いになるってこともあるってことを考慮すれば、ルートノードで「アルファ値」「ベータ値」を狭めた状態で探索開始できるんだよ。」

Sayuri
「分かったような分からないような・・・つまるところ「アスピレーション・ウィンドウズ」って何どすか?


「「アスピレーション・ウィンドウズ」ってのは・・・

  1. 「前のサイクルの評価値 - マージン」を「アルファ値」に、「前のサイクルの評価値 + マージン」を「ベータ値」にして探索開始する。
  2. そのサイクルの最初の候補手を探索する時・・・
    • 結果が「アルファ値 < 評価値 < ベータ値」なら成功。
    • 結果が「アルファ値以下」なら「アルファ値」を「評価値 - マージン」に引き下げて再探索。
    • 結果が「ベータ値以上」なら「ベータ値」を「評価値 + マージン」に引き上げて再探索。
  3. そのサイクルの 2つ目以降の候補手を探索する時・・・
    • 結果が「アルファ値 < 評価値 < ベータ値」なら成功。
    • 結果が「ベータ値以上」なら「ベータ値」を「評価値 + マージン」に引き上げて再探索。

・・・ってなことをする枝刈りだ。」

Sayuri
「ん?
「最初の候補手を探索する時」「2つ目以降の候補手を探索する時」とに分かれているどすな。」


「うん。
それは、「最初の候補手を探索する時」は「アルファ値」は「現在の最高得点」じゃないから「アルファ値」もアスピレーション・ウィンドウズで探さなきゃいけない。
でも「2つ目以降の候補手を探索する時」は「アルファ値」は「現在の最高得点」を表すので勝手に変えちゃいけないんだよ。」

Sayuri
「分かったような分からないような・・・・・・どす。」


疑似コード見たら手っ取り早いから、次いってみよう!」

アルゴリズム

header_2


「疑似コードでアルゴリズムの紹介だよ。」

alpha = -無限
beta = 無限
best_move = None
depth = 1

while 探索終了条件が満たされるまで:
    delta = 15

    if 5サイクル目以降?:
        beta = alpha + delta
        alpha -= delta
    else
        alpha = -無限
        beta = 無限

    for 候補手 in 候補手リスト:
        MakeMove(候補手)

        while 無限ループ:
            score = -Search(depth, alpha, beta)

            if 最初の候補手?:
                if score <= alpha:  # 探索失敗! Fail Low!
                    delta *= 2
                    alpha = score - delta
                    continue  # やりなおし。

            if score >= beta:  # 探索失敗! Fail High!
                delta *= 2
                beta = score + delta
                continue  # やりなおし。

            if score > alpha:
                alpha = score
                best_move = 候補手
            break  # 終了。

        UnmakeMove(候補手)

    depth += 1

Sayuri
「先ず疑問があるどす。
さっき「2サイクル目以降」にアスピレーション・ウィンドウズをするって言ってたどすが、このコードは「5サイクル目以降」になっているどす。
書き間違いどすか?」


「いや。 これが Sayuri の設定だ。
深さ 5レベルの探索なんてアッという間だから余計なことしないようにしてるだけ。」

Sayuri
「じゃあ次どす。
「delta」ってのはマージンのことどすな。
「15」ってなっているどすが根拠はあるどすか?」


「これは Sayuri の場合はこれより多くても少なくても効率が悪くなるってだけ。
他のエンジンの場合は「25」とか「50」くらいが普通らしい。」

Sayuri
「なるほど。
で、探索失敗する度に「delta」が 2倍に増えているどすな。」


「アスピレーション・ウィンドウズが全く見当違いだったら逆に効率が下がっちゃうので「倍々」で急激に増やしているんだ。」

Sayuri
「いろいろ工夫しているんどすな。」


「そういう工夫がエンジンの個性になるからな。」

Sayuri
「素人目には「強さ」以外にエンジンの個性なんて分からないどすが。」


「それはたいていの人は「強いエンジン」としか戦ったことないからだと思う。
チェスエンジンは「どんな駒の配置を目指そうとするか」とか「どのタイミングで強くなるか」とかで個性がいろいろ出るんだ。
ただ、強いエンジンであればあるほど個性が分からなくなってくる。
だからスマホやテレビゲーム機のチェスゲーム、方向性の違う「変なチェスエンジン」なんかと戦うと個性が分かりやすいと思う。」

Sayuri
「変なチェスエンジン」ってどんなのどす。」


「例えば Lisp インタープリタを搭載したチェスエンジンとか、メタプログラミングのやりすぎでコードがスパゲッティ・モンスターになっているチェスエンジンとか、スケベな作者が女性の名前を付けたチェスエンジンとか。」

Sayuri
全部うちどすな! 「変」とは失礼どす! しばくどす!

最後に

Sayuri
「今回のテーマは「空飛ぶスパゲッティ・モンスター教のプログラマーは地雷」どす。」


「僕みたいに「スパゲッティ・モンスターなコード」を書く人は間違いなく「ぼっちプログラマー」だろうな。
一人でしかプログラミングしないから「人に読んでもらうコード」が書けない。
だから僕が開発チームとかに入ると間違いなく「お茶くみ係」になる・・・・・・(涙)

Sayuri
「ならその悲しい気持ちをぶつけるどす!」


「分かったぜ!」

pic

Sayuri
一生お茶くみ係でいればいいどす。


「しゅん・・・・・・。」

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