僕はチェスエンジン「Sayuri」の開発者です。
今回は、チェスエンジンがどのように考えて次の1手を決めているかを紹介したい思います。
目次
「チェス」と「ゲームの木」
「チェス」というゲームは「ある局面」で「ある指し手」を指すと「別の局面」に変化します。
「局面」をノード、「指し手」をエッジとすると「木構造の有向グラフ」で一つのゲームを表現することができます。
このグラフを「ゲームの木」と呼びます。
チェスエンジンはこの「ゲームの木」の中を探索し、どの候補手が最善手なのかを計算します。
余談ですが、実は、「Repetition は引き分け」「50手ルールは引き分け」という条件を入れることで理論上「ゲームの木」は完全に展開することができます。
これは言い換えると、理論上「全ての局面において、真の最善手を解くことができる」ということです。
しかし、現実的にはあまりにも「ゲームの木」が大きすぎて、『スーパーアルティメットデラックスコンピュータ ZX』があったとしても計算不可能でしょう。
基本の考え方「ミニマックス法」
「ミニマックス法」はチェスエンジンの思考法の基本的な考え方になっているアルゴリズムです。
「ミニマックス法」の考え方は、先ず以下の手順で小さな「計算用ゲームの木」を作成することです。
- ある一定の深さ(未来の局面)までの「ゲームの木」を作成する。
- 一番深いところの局面での形勢判断をして得点をつける。
- 0点は五分五分。 有利ならプラス、不利ならマイナス。
次に、上記で付けた得点に対して以下のように考えます。
- 「先手」にとって「後手」の得点はプラスマイナス逆。
- 「後手」にとって「先手」の得点はプラスマイナス逆。
要するに、『「先手」にとって有利な局面は「後手」にとって不利な局面だ』・・・みたいなことをいいたいわけです。
次に、「プレイヤーは自分にとって最も得点が高くなりそうな指し手を選ぶ」という考え方を肝に銘じます。
すると、最も深い局面につけた得点を上へ上へと遡らせることができます。
それを「1手先の局面」のところまで遡らせます。
で、それぞれの初手の先に付いている局面のプラスマイナス逆にした得点を「初手の得点」とし、その中で最も高い得点の初手が「最善手」となるわけです。
チェスエンジンの命「評価関数」
「評価関数」・・・それは「命」・・・。
(元ネタはアニメ映画「イノセンス」のCMです。)
「評価関数」というのは「ある局面を形勢判断し、得点をつける関数」のことです。
ちなみに、「関数」というのは簡単に言うと「何かを入力し、何かを出力するカラクリ」みたいな感じのやつです。
「評価関数」は局面を入力し、得点を出力します。
評価関数のベース「マテリアル」
「マテリアル」というのは将棋で言う「駒得」のことです。
簡単に言うと、「相手よりどれだけ強い駒が、どれだけ多く残っているか」を表す得点です。
チェスでは各コマに「強さ」を表す得点が付けられています。
チェスエンジン業界では「ポーン1つを100点」として計算する「センチポーン(cp)」という単位が一般的です。
僕のチェスエンジン Sayuri では各コマとその得点は以下の表のようになっています。
駒の種類 | 得点 |
---|---|
ポーン | 100 |
ナイト | 400 |
ビショップ | 400 |
ルーク | 600 |
クイーン | 1200 |
キング | 1000000 |
チェスは将棋と違ってルール上「キングが取られることは絶対にありえない」ので、キングに得点を割り当てることに全く意味がありませんが・・・付けちゃっています。
「マテリアル」は
『マテリアル = 自分の駒の得点の合計 − 相手の駒の得点の合計』
で計算します。
「評価関数」では、この「マテリアル」を「基本の得点」とし、その他の点数上乗せしてその局面の評価をします。
余談ですが、実はこの「マテリアル」は「評価関数」で計算する必要はありません。
思考前に現在の局面の「マテリアル」を計算しておいて、探索中に「相手の駒を取る」という指し手があった場合に得点をその駒の分だけ変化させればいいのです。
こうすることで「マテリアル」を応用した高度な枝刈りアルゴリズムを使用することができるようになります。
その他の点数「ポジショナルアドバンテージ」
「ポジショナルアドバンテージ」というのは「駒の配置」による有利不利のことです。
将棋とちがってチェスは「戦略理論」がハッキリしていて、人間の感覚による「局面の有利不利」を簡単にプログラムで表現することが可能です。
(将棋の場合は、局面の評価はとても難しく、「2駒関係」などかなり人間の感覚とは違った計算方法を使わなければ評価ができません。)
Sayuri の「ポジショナルアドバンテージ」は
『得点 = (ウェイト1 × 特徴1) + (ウェイト2 × 特徴2) + ・・・』
で計算します。
(線形代数をご存知なら「ウェイトベクトル」と「特徴ベクトル」の内積と考えてください。)
「特徴」というのはその局面の中の「ある特徴」の「自分と相手の差」を表す数です。
例えば、自分の「パスポーン」が2つ、相手の「パスポーン」が1つあった場合、『2 − 1』で「1」が「パスポーンの特徴」です。
さらに、チェスでは「駒のボード上での位置」で駒の価値が変わります。
例えば、「中央6段目にいるナイトは隅っこに居るナイトよりも価値が高い」などです。
このような特徴は以下のような「ピーススクエアテーブル」という点数表を使って計算します。
『駒 A が位置 X に居る時、価値は Y』みたいな感じで価値を出し、『自分の価値 − 相手の価値』が「特徴」となります。
さらにもう一つ、「ある」「ない」を表す場合「1」「0」を使います。
例えば、自分は「キャスリング」していなくて、相手はしている場合、『0 − 1』で「キャスリングの特徴」は「-1」となります。
「ウェイト」というのはその「特徴」を得点化するための係数です。
例えば、上記の「パスポーン」の場合、「パスポーン」1つが「50 cp」の価値があれば「パスポーンのウェイト」は「50」になります。
もしその「特徴」が「悪い特徴」なら「ウェイト」はマイナスの数になります。
例えば、「ダブルポーン」1つあたり「-20 cp」のペナルティを与えたいとすると、「ダブルポーンのウェイト」は「-20」となります。
実は Sayuri の「ウェイト」はかなり複雑になっています。
「Sayulisp Editor」という付属のツールを見ていただけると分かりますが、「ウェイト」は「駒の数」を変数とした「折れ線グラフ」で定義されています。
理由はチェスというゲームは駒の数に合わせて戦略が大きく変化するからです。
今のところ、「駒の数が 14個以下ならエンディングのウェイト」とし、「32個から 15個まで一次関数的に変化するオープニングのウェイト」としています。
これらは「Sayulisp」という「独自 Lisp インタープリタ」で設定可能です。
とはいえ、「評価関数」でいちいち折れ線グラフを計算したりはしません。
チェスのマスの数は 64個と十分に少ないので、探索直前に「ウェイト」を予め計算し、64個の配列に結果を格納しておいて、それを「評価関数」で使用します。
なので、どんなに複雑なグラフでも思考速度に影響を与えません。
探索アルゴリズム「アルファ・ベータ法」
先ほど「ミニマックス法」という探索アルゴリズムを紹介しました。
しかし実際このアルゴリズムをそのまま使うと、実用的なくらいの深さで計算するには、1手につき数日はかかります。
実は「ミニマックス法」は、よく見ると「これ以上は探索しなくていいよね」的なポイントがあります。
そのポイントを知ることによって「計算用ゲームの木」がアホみたいに小さくなります。
注目する点は、実際の探索アルゴリズムが「深さ優先探索」であること、「自分は最も得点が高くなりそうな指し手を選ぶ」ということ、「探索中のある局面の得点が、一つ前の局面に上がるときにプラスマイナス逆転する」ことです。
順を追って図で説明します・・・の前に、ちょっと注意事項。
- 「5」と「10」を比べると、「10」の方が大きいです。
- 「-5」と「-10」を比べると、「-5」の方が大きいです。
いや、皆さんを馬鹿にしているのではなくて、僕自身がよく勘違いするので書きました。
では、順を追って図で説明します。
ある局面「A」があります。 「A」には指し手が 2つあり、それらを指すと「B」「C」という局面になります。
「B」を探索した結果が「-10 cp」だったとします。
となると、「Bへの指し手」の得点はプラスマイナス逆になり「10 cp」となります。
ってことは、もし次に計算する「Cへの指し手」の得点が「10 cp 以下」なら「C」の探索は意味がないと言えます。 なぜなら「Cへの指し手」が「10 cp 以下」なら「Cへの指し手」は「最善手」ではないからです。
でも、それは所詮「結果論」です。 実際探索してみなくてはそんなこと分かりません。
なので「C」の探索を開始します。 「C」の指し手は 4つあり、「D」「E」「F」「G」へとつながります。
「Dへの指し手」が「-20 cp」、「Eへの指し手」が「-15 cp」だったとします。
これは特に問題ありません。
ところが、「Fへの指し手」を計算すると「-5 cp」だったとします。
すると、ここが先ほど言っていた「これ以上は探索しなくていいよね的なポイント」になります。
どういうことかというと、先ず、「C」の探索におけるここからの目的は「-5 cp」 よりも大きな得点が得られる指し手を探すことだからです。
ところがそのような指し手を見つけたところで「A」での「Cへの指し手」の得点は「10 cp 以下」になるだけです。
つまり、「C」で「-5 cp」という指し手を見つけた時点で「A」における「Cへの指し手」の得点は「5 cp 以下」になることが確定してしまうのです。
「A」にとって大事なのは「10 cp より大」の指し手を見つけることなので、「G」を探索する必要はもうないというわけです。
このように探索を途中で打ち切ることを「ベータカット」といいます。
なぜそんな変な名前かというと、上記の場合「C」における上限値「-10 cp」のことを「ベータ値」と呼ぶからです。
この「ベータ値」以上の指し手を見つけた時点で「ベータカット」が起こり、探索が打ち切られます。
で、結果的に「A」の局面では「Bへの指し手」が採用され、「10 cp」という得点が決定します。
以上が「アルファ・ベータ法」の概要です。
・・・えっ? 「ベータはいいが、アルファはどうした?」ですって?
なるほど、あなたはなかなか鋭い・・・「アルファ」がただの「中二病的修飾子」ではないことに気付くなんて・・・。
それでは説明します。
各局面を探索する際には「ベータ値」とともに「アルファ値」という値が設定されます。
この値は「その局面における下限値」で、「アルファ値以下の指し手を見つけても意味ねーよ」的な値のことです。
上記の例だと「C」での「ベータ値」は「-10 cp」でした。 つまり「C」にとっては「10 cp」以下の得点を「D」「E」「F」「G」で見つけても、それぞれの指し手が「-10 cp 以上」になるので意味ないのです。
なので、「D」「E」「F」「G」を探索する際、それぞれの「アルファ値」を「10 cp」に設定して探索開始します。
先ず、「D」を探索します。 「D」では「H」「I」「J」への 3つの指し手がありました。
「D」では「10 cp 以下の指し手は意味ねー」という設定です。
逆に言うと、「H」「I」「J」が「-10 cp 以上」だと指し手は「10 cp」以下になるので「意味ねー」です。
なので、先ず「H」を探索する際その局面の「ベータ値」を「-10 cp」にして探索します。
結果は「-15 cp」だったとします。
ってことは「H」への指し手は「15 cp」なので「意味あり」です。 そして、この時点で「D」の「アルファ値」が更新され、「15 cp」となります。
つまり「D」において「15 cp」以下は「意味ねー」になります。
なぜなら最善手が「15 cp」だからです。
で、「I」を探索する際はそのノードの「ベータ値」を「-15 cp」に設定します。
なぜなら、「I」の得点が「-15 cp」以上だと指し手は「15 cp」以下になるので「意味ねー」だからです。
ってな感じで、「アルファ値」を更新し、次の局面の「ベータ値」に「アルファ値のプラスマイナス逆」を設定しながら探索を続けていきます。
まとめると・・・
- 各局面には「アルファ値」と「ベータ値」が設定されている。
- 「アルファ値」は「これ以下の得点は意味ねー値」。
- 「ベータ値」は「これ以上の得点の指し手」を見つけたら「ベータカット」で終了。
- 「アルファ値」はその局面での現在の最高得点で上書きできる。
(補足すると、最終的な「アルファ値」がその局面の得点となります。) - 「次の局面」の「アルファ値」は「ベータ値のプラスマイナス逆」。
- 「次の局面」の「ベータ値」は「アルファ値のプラスマイナス逆」。
・・・ってな感じです。
以上が「アルファ・ベータ法」の概要です。
・・・えっ? 「アルファはいいが、キャベツはどうした?」ですって?
それは「キテレツ」に聞いてください。
Google検索 : 「キテレツ キャベツはどうした」
前向き枝刈り
「枝刈り」というのは「計算用ゲームの木」を縮小するアルゴリズムです。
実は先ほど話した「アルファ・ベータ法」は「後ろ向き枝刈り」という手法の一つだったりします。
「後ろ向き枝刈り」は「確実に無意味な局面」を探索しないアルゴリズムです。
では「前向き枝刈り」とは何かというと、「多分この局面、探索しなくて良くなくなくなくね?」という局面を探索しないアルゴリズムです。
何が「前向き」なのかは僕は知りませんが、もしかするとそのアルゴリズムの「見捨てる勇気」がとても前向きという意味なのかもしれません。
代表的な「前向き枝刈り」
「前向き枝刈り」には、「よく知られているもの」と「そのエンジン固有のもの」があります。
「よく知られているもの」でもそのエンジンの作者が改造している場合もあります。
「前向き枝刈り」の詳しい説明は難しいのでしませんが、Google で検索しやすいように代表的なものの名前を紹介させていただきます。
- 「Futility Pruning」 : ほぼ全てのチェスエンジンに搭載されています。
- 「Late Move Reduction」 : 超強力枝刈りです。
- 「Null Move Pruning / Reduction」 : 割と上記2つと共存できます。
- 「ProbCut」 : 「Null Move Pruning」との相性は最悪です。
- 「Aspiration Windows」 : 「枝刈り」というより、ルートノードで行うちょっとした工夫です。
- 「指し手のオーダリング」用。 (「前向き枝刈り」ではないけれど紹介。)
- 「SEE」 : 駒の取り合いにおける有力な手を予測します。
- 「Internal Iterative Deepening」 : PVノードにて、ハッシュテーブルに最善手がない場合に使用します。
- 「History Heuristics」 : ベータカットできそうな指し手を予測します。
- 「Killer Move Heuristics」 : これもベータカットできそうな指し手を予測します。 「History Heuristics」よりも強力です。
後半に「指し手のオーダリング」というのがありましたが、どの指し手から計算するかの順番を決めるアルゴリズムです。
実は「良さ気な手」から順番に計算をすると「ベータカット」が早くに発生しやすいので、上手く行けば大幅に「計算用ゲームの木」を縮小することができます。
チェスエンジンには必須の技術です。
最後に・・・
実はまだまだ紹介していない重要な技術がたくさんあります。
「Iterative Deepening」や「ビットボード」や「マジックビットボード」などです。
これらは「超必須技術」で、これらのないチェスエンジンはこの世に存在しないくらいです。
ただ、これらを説明しようとすると、とてつもなく長くなり、僕のような未熟なブロガーが説明できるシロモノでもないのでやめておきます。
決して「疲れた」とか「お腹が空いたので食事休憩したら書く気がなくなった」とか「撮り溜めしているプリキュアの続きが見たくなった」とかではなく、僕の未熟さが理由なのです。
チェスエンジンって思ったより複雑にできていますネ♪