基本アルゴリズム
Minimax
まず、本論文では、簡単な例を通して、Minimaxアルゴリズムのアイデアと意思決定を説明します。
質問
Aには1、20、50、Bには5、10、100、Cには1、5、20の紙幣が入っています。プレーヤーはAとBの2人で、2人とも3枚の皿とその上に置かれた紙幣にアクセスできます。ゲームは3つのステップで行われます：
Aは3枚の皿から1枚を選びます。
BはAが選んだ皿から2つの音符を取り出し、Aに渡します。
AはBからもらった2つの音符のうち1つを選んで持ち去ります。
ここで、Aの目標は可能な限り大きな額面の紙幣を手にすることであり、Bの目標はAが可能な限り小さな額面の紙幣を手にすることです。
この問題を解くには、次のようなミニマックス・アルゴリズムが用いられます。
基本的な考え方
Minimaxもこのルールの例外ではなく、現在のパターンを根とするパターンの木を探索することで、次のステップの選択を決定します。すべてのパターン木探索アルゴリズムの中核は、各パターンの値の評価です。Minimax アルゴリズムは、次の単純な考えに基づいてパターンの値を決定します：
Minimaxは悲観的なアルゴリズムです。つまり、対戦相手の一挙手一投足が、現在の視点から見て理論的に最も価値の低いパターンの方向に我々を導く、つまり対戦相手が完璧な意思決定をする能力を持っていると仮定しています。したがって、私たちの戦略は、相手が私たちに対して達成できる最悪のシナリオの中で最良のもの、つまり、相手が完璧な意思決定で私に与える損害を最小にするものを選ぶべきです。
ミニマックスでは、理論的な最適解は求めません。理論的な最適解は、相手が愚かかどうかに左右されることが多いからです。 ミニマックスでは、こちらが完全にコントロールし、相手がすべてのステップで完璧な決断をすれば、予想される最小の損失パターンを達成できますし、相手が完璧な決断をしなければ、予想される悲観的なシナリオよりも良い結果を達成できます。つまり、こちら側は最悪の中から最善のものを選ぼうとしているのです。
上記の文章はやや抽象的です。
問題の解決
次の図は、上記の例題のグリッドツリーを示しています：
例題のグリッド数は非常に少ないので、完全なグリッドツリーを与えることができることに注意してください。この場合、私はミニマックスアルゴリズムの大域的最適解を求めることができます。実際のケースでは、グリッド木は非常に大きく、コンピュータでさえ完全な木を与えることができないので、ある深さまでしか探索しない傾向があり、その場合は局所最適解しか見つけることができません。
Aの視点で考えてみましょう。四角いノードがこちらの手番、三角形が相手の手番を示します。ゲームを3ラウンド行った後、終盤戦を行います。黄色の葉のノードはすべての可能な結末を示しています。Aから見ると、最終的な利益はノートの額面で評価できるので、エンディングでAが得るノートの額面で終盤戦の価値を表すのが自然です。
各ノードがその子の最大値で評価されるように、選択肢の最大値グリッドが導入されるべきです：
順番が回ってくるこれらのノードはmaxノードと呼ばれ、maxノードの値はその子の最大値です。
そのため、これらのノードの値は子ノードの最小値に依存します。このような相手のターンのノードをminノードと呼びます。
最後に、ルート・ノードは MAX ノードなので、値はリーフ・ノードの最大値に依存します。値の完全な割り当てのための最終的なグリッドツリーは次のようになります：
ミニマックス・アルゴリズムのステップを要約します：
最大探索深度Dが最初に決定され、Dは終盤に到達することもあれば、中間パターンであることもあります。
リーフノードの値は、最大深さDを持つグリッドツリーのリーフノード上で事前に定義された値評価関数を使用して評価されます。
ボトムアップは非リーフノードに値を割り当てます。max ノードは子ノードの最大値を、min ノードは子ノードの最小値をとります。
私たちの番が回ってくるたびに、この最大ノードの値と等しい値を持つ子ノードのパスを選択します。
上記の例では、ルートノードの値は20です。これは、相手がすべてのステップで完璧な決定を下した場合、上記のアルゴリズムに従って20ドルで終わることができることを意味し、これはミニマックスアルゴリズムの下での最善の決定です。グリッド変換パスは下の赤いパスに示されています：
実際の問題におけるミニマックスについては、いくつかの点を再確認しておきます：
現実の問題では一般に完全なグリッドツリーを構築することができないため、最大深度Dを決定し、現在のグリッドから下に向かって一度に最大D層を計算する必要があります。
上記の理由から、ミニマックスは一般的に大域的な最適解ではなく局所的な最適解を探索します。探索の深さが深ければ深いほど、より良い解が見つかる可能性は高くなりますが、消費される計算時間は指数関数的に膨れ上がります。
また、一度に完全なグリッドツリーを構築することは不可能であるため、実際の問題におけるMinimaxは、一般的に一度だけでなく、ゲームをプレイしながらローカルグリッドツリーを計算しますが、計算された中間結果はキャッシュすることができます。
#p#
Alpha-beta
単純なMinimaxアルゴリズムの1つの大きな問題は、計算の複雑さです。探索されるノードの数は最大深度とともに指数関数的に増大し、アルゴリズムの有効性はしばしば深度に依存するため、これはアルゴリズムの有効性を大きく制限します。
アルファ・ベータ・プルーニングはミニマックスを補完し、改善します。アルファ・ベータ・プルーニングでは、最大深度D内のすべてのノードを構築して探索することなく、最大深度D内のすべてのノードを構築して探索することが可能です。構築プロセス中に、現在のグリッドのさらに下方に良い解が見つからないことが判明した場合、このグリッド以下の探索を停止する、つまりプルーニングを行います。
アルファ・ベータは、現在わかっている最良の選択肢を常に記憶しておき、現在のグリッドから下に検索しても既知の最適解よりも良い解が見つからない場合は、このグリッドブランチでの検索を停止し、親ノードに戻り検索を続けるというシンプルな考えに基づいています。
アルファベータアルゴリズムはミニマックスの変形と見なすことができ、基本的なアプローチはルートノードから深さ優先でグリッドツリーを構築することであり、各ノードではグリッドツリーを構築する際にこのノードのアルファ値とベータ値が読み込まれます。エンディングの上限。敵対者が状況を最悪の結末のいずれかに導くことを想定しているため、βがαより小さい場合、最終的な結末にかかわらず、上限値がここから先の既知の最適解より低い、つまり、ここから下はもはやより良い解を見つけることができないので刈り込まれることを意味します。
アルファベータ・プルーニング・アルゴリズムがどのように機能するか、再び上記の例を用いて紹介します。ルートノードから始めて、Alpha-betaを使う各ステップを詳しく説明します：
ルート・ノードのアルファとベータは、それぞれ, と初期化されます。
リーフノードではなく、最初の子を深さ優先で検索するため、alphaとbetaはそれぞれ親ノードから継承されます。
3段目の最初の子も同様に探します。
第4階層を検索してリーフノードに到達すると、評価関数を使用してこのノードの評価値を1とします。
このリーフノードの親はmaxノードなので、アルファ値を1に更新することは、このノードが1の下界を取ることを示します。
もう一つの子ノードを見ると、値は20で、現在のアルファ値より大きいので、アルファ値を20に更新します。
この時点で、第3レベルの左端のノードのすべてのサブツリーが検索され、maxノードとして、その真の値が現在のアルファ値：20に更新されます。
親ノードはminノードなので、親ノードのベータ値を20に更新すると、このノードは最大20の値を取ることになります。
50は20より大きいので、minノードのベータ値は更新しません。
第 2 階層の左端のノードの第 3 子を検索します。最初のリーフ・ノードを見ると、3 番目の子は alpha=beta であることがわかります。
B枝の最初の子を検索した結果、この時点でB枝のαは20、βは10であることがわかります。つまり、B枝のノードの最大値は10を超えることはなく、A枝ではすでに20になっています。この10はこのノードの実数値とは限りませんが、線上にあるだけで、Bノードの実数値は5かもしれないし、1かもしれないし、10より小さい値かもしれません。しかし、そんなことはもうどうでもいいのです。どうせこのブランチはAブランチより良くならないことがわかっているのですから、あきらめてもいいのです。
ブランチCの検索でも、ブランチBと同じ状況に遭遇します。そこで、C枝刈りの話をします。
この時点で、探索はほぼ完了し、このステップの戦略も決まりました。
通常のMinimaxでは18個のリーフノードが検索されるのに対し、ここでは9個のリーフノードしか検索されていないことがわかります。Alpha-βプルーニングを使うことで、Minimaxの探索深さを同時に増やすことができ、より良い結果を得ることができます。また、Alpha-βの解は通常のMinimaxの解と一致します。
#p#
2048ゲームの実装について
ov3yが2048用に実装したAIを紹介します。プログラムのgithubはここでは、主なプログラムはai.jsあります。
モデリング
MinimaxとAlpha-betaは、どちらも対称的な情報で順番を取る問題を扱っていると前述しました：
我々：ゲームプレーヤー。毎回、上下左右の4つの戦略から1つを選択します。移動後、マスは決められたロジックに従って移動・合体し、パターンが変化します。
対戦相手：コンピュータ現在のマスのいずれかにマスを1つ配置します（マスの値は2か4）。
勝利条件：「2048」と書かれたマスが出現。
失敗条件：グリッドが満杯で、4方向のいずれにも移動できない場合。
このようにして、2048ゲームは対称的な情報を持つ2人用の問題としてモデル化されます。
グリッドの評価
アルゴリズムの中核として、現在のパターンの価値をどのように評価するかが最優先事項です。2048では、終盤を除き、中間パターンにはあまり明確な価値指標がないため、パターンを評価するためにはいくつかの発見的指標が必要になります。点数の高い良いパターンは勝利につながるパターンであり、点数の低い悪いパターンは失敗につながるパターンです。
単調性。
単調とは、正方形が左から右へ、上から下へ、増加または減少のパターンをたどることを意味します。一般的に、パターンは単調であればあるほど良いとされています。以下は、単調性の良いパターンの例です：
[]
滑らかさ。
滑らかさとは、各マスと、そのマスに隣接するマスの値の差のことで、差が小さいほど滑らかです。例えば、4の隣の2は128の隣の2より滑らかです。一般的に、グリッドは滑らかであればあるほど良いとされています。極端に滑らかな例を示します：
スペースの数
これはよく理解できることで、一般的にスペースの数が少ないほどプレーヤーにとって不利だからです。つまり、スペースが多ければ多いほど良いグリッドとみなされるのです。
孤立空間の数
この指標は、スペースがどの程度離れているかを評価するもので、スペースが広がれば広がるほど、パターンは悪くなります。
具体的には、2048-AI はパターンを評価する際に、これらのヒューリスティックの重み付け戦略を使用します。具体的なコードを以下に示します：
// static evaluation function
AI.prototype.eval = function() {
var emptyCells = this.grid.availableCells().length;
var smoothWeight = 0.1,
//monoWeight = 0.0,
//islandWeight = 0.0,
mono2Weight = 1.0,
emptyWeight = 2.7,
maxWeight = 1.0;
return this.grid.smoothness() * smoothWeight
//+ this.grid.monotonicity() * monoWeight
//- this.grid.islands() * islandWeight
+ this.grid.monotonicity2() * mono2Weight
+ Math.log(emptyCells) * emptyWeight
+ this.grid.maxValue() * maxWeight;
};
興味のある生徒は、重さを調節してその効果を確かめることができます。
互いの選択を剪定
この手順では、α-β刈り込みに加えて、minノードでもう一つの刈り込み、すなわち、相手の可能な手をすべて探索するのではなく、パターンを悪化させる相手の最悪の手だけを考慮します。これは、相手の可能な選択肢はすべて「スペース数×2」であり、それらをすべて探索すると探索の深さが著しく制限されるためです。
関連する剪定コードは以下の通り：
// try a 2 and 4 in each cell and measure how annoying it is
// with metrics from eval
var candidates = [];
var cells = this.grid.availableCells();
var scores = { 2: [], 4: [] };
for (var value in scores) {
for (var i in cells) {
scores[value].push(null);
var cell = cells[i];
var tile = new Tile(cell, parseInt(value, 10));
this.grid.insertTile(tile);
scores[value][i] = -this.grid.smoothness() + this.grid.islands();
this.grid.removeTile(cell);
}
}
// now just pick out the most annoying moves
var maxScore = Math.max(Math.max.apply(null, scores[2]), Math.max.apply(null, scores[4]));
for (var value in scores) { // 2 and 4
for (var i=0; i<scores[value].length; i++) {
if (scores[value][i] == maxScore) {
candidates.push( { position: cells[i], value: parseInt(value, 10) } );
}
}
}
検索の深さ
2048-AIの実装では、探索の最大深度に制限はなく、むしろ「考える」のにかかる時間に制限があります。ここではタイムアウトを設定します。デフォルトは100msで、この時間内に1から開始し、到達できる深さまで検索します。関連コード
// performs iterative deepening over the alpha-beta search
AI.prototype.iterativeDeep = function() {
var start = (new Date()).getTime();
var depth = 0;
var best;
do {
var newBest = this.search(depth, -10000, 10000, 0 ,0);
if (newBest.move == -1) {
//console.log('BREAKING EARLY');
break;
} else {
best = newBest;
}
depth++;
} while ( (new Date()).getTime() - start < minSearchTime);
//console.log('depth', --depth);
//console.log(this.translate(best.move));
//console.log(best);
return best
}
つまり、このアルゴリズムで得られる結果は、実際にはjavascriptエンジンを実行するマシンの性能に依存します。もちろん、タイムアウトを長くすることでより良い結果を得ることは可能ですが、それに応じて各ステップが遅くなります。
アルゴリズムの改善
現在、この実装の作者は、2048の合成に成功する確率は90%以上だが、4096や8192の合成に成功する確率はあまり高くないと主張しています。作者は同時にいくつかの最適化の提案をしています：
- 結果のキャッシュ現在のところ、この実装は検索されたツリーのキャッシュを行いません。
- マルチスレッド検索。これはjavascriptエンジンがシングルスレッドであるため困難ですが、他のプラットフォームであれば並列技術も考慮できるかもしれません。
- より良いヒューリスティック関数グリッド値を評価するためのより良いヒューリスティック関数をいくつかまとめることができるかもしれません。
