人気ゲーム2048 - AIプログラムアルゴリズム分析

現在人気の2048ゲームでは、誰かが高確率（90％以上）でゲームに勝つことができるAIプログラムを実装しており、その作者はstackoverflowでAIアルゴリズムのフレームワークと実装のアイデアを簡単に紹介しました。ただし、この回答は主にヒューリスティック関数の選択に焦点を当てており、AI で使用されるコアアルゴリズムの詳細な説明は提供されていません。この記事は主に 2 つの部分に分かれています。最初の部分では、使用される基本的なアルゴリズム、つまりミニマックスとアルファベータプルーニングを紹介し、2 番目の部分では著者の特定の実装を分析します。

基本アルゴリズム

2048 は、本質的には情報対称型の 2 人用ゲームモデルに抽象化できます (プレーヤーは 4 つの方向のいずれかに移動し、コンピューターが特定のスペースを 2 または 4 で埋めます)。ここで、「情報の対称性」とは、任意の瞬間に 2 人のプレイヤーが状況について完全に一貫した情報を持ち、移動戦略が次の状況についての推論のみに依存することを意味します。著者が使用するコアアルゴリズムは、チェスモデルで一般的に使用される、アルファベータプルーニングを使用したミニマックスです。このアルゴリズムは、チェスなどの情報対称ゲーム AI でもよく使用されます。

ミニマックス

次に、剪定なしのミニマックスを紹介します。まず、この記事では簡単な例を使用して、ミニマックスアルゴリズムの考え方と意思決定方法を説明します。

質問

ここで、次のようなゲームを考えてみましょう。A、B、C の 3 つのプレートがあり、それぞれに 3 枚の紙幣が入っています。 A は 1、20、50 で配置され、B は 5、10、100 で配置され、C は 1、5、20 で配置されます。単位は「元」です。 A と B という 2 人の人物がいて、どちらも 3 枚の皿とそこに置かれた紙幣を自由に見ることができます。ゲームは 3 つのステップで構成されます。

Aは3つのプレートのうち1つを選択します。
BはAが選んだ皿から紙幣を2枚取り、Aに渡します。
AはBから渡された2枚の紙幣のうち1枚を選び、持ち去ります。

A の目標は、できるだけ大きな額面の紙幣を手に入れることであり、B の目標は、できるだけ小さな額面の紙幣を手に入れることです。

次に、ミニマックスアルゴリズムを使用してこの問題を解決します。

基本的な考え方

ゲーム関連の問題を解決するための自然な考え方は、パターンをツリーに整理することです。ツリーの各ノードはパターンを表し、親子関係は、親パターンから 1 ステップ進むだけで子パターンに到達できることを示します。 Minimax も例外ではありません。現在のパターンをルートとしてパターンツリーを検索することで、次の選択肢を決定します。すべてのパターンツリー検索アルゴリズムの中核は、各パターンの値の評価です。 Minimax アルゴリズムは、次の単純な考えに基づいてパターンの値を決定します。

ミニマックスは悲観的なアルゴリズムであり、対戦相手が各ステップで理論値が最小となる方向に状況を導く、つまり対戦相手が完璧な意思決定能力を持っていると想定します。したがって、私たちの戦略は、相手が私たちのために達成できる最悪のシナリオの中から最善のものを選択すること、つまり、完璧な決定の下で相手が私に与える損失を最小限に抑えることであるべきです。
ミニマックスは理論上の最適解を探しません。理論上の最適解は、対戦相手が十分に愚かであるかどうかに左右されることが多いためです。ミニマックスでは、主導権を完全に握っています。対戦相手の決定がすべて完璧であれば、期待される最小損失パターンを達成できます。対戦相手が完璧な決定を下さなければ、予想される最悪のシナリオよりも良い結果を達成できる可能性があります。つまり、最悪の状況の中から最善のものを選択しなければならないのです。

上記の説明は少し抽象的ですので、以下の具体的な例を見てみましょう。

問題解決

以下は、上記の例の問題のランドスケープツリーです。

問題のパターン例の数は非常に少ないため、完全なパターンツリーを提供できることに注意してください。この場合、ミニマックスアルゴリズムのグローバル最適解を見つけることができます。実際には、パターンツリーは非常に大きく、コンピュータでさえ完全なツリーを提供することはできません。そのため、多くの場合、特定の深さまでしか検索できず、その後は局所的な最適解しか見つけることができません。

Aさんの視点から考えてみましょう。四角いノードは自分の番（A）であることを示し、三角形のノードは相手の番（B）であることを示します。 3 ラウンドのプレイ (こちら側 - 相手側 - こちら側) の後、最終ゲームが始まります。黄色の葉は、起こりうるすべての結果を表します。甲の立場からすると、最終的な利益は紙幣の額面金額で評価できるので、当然、甲が最終的に受け取る紙幣の額面金額を最終状況の価値として表すことができる。

次に、最後から 2 番目のノード層について考えます。これらのノードでは、選択する順番が回ってくるので、選択できる最大値パターンを導入する必要があります。これにより、各ノードの値は、その子ノードの最大値になります。

順番が回ってきたノードは最大ノードと呼ばれ、最大ノードの値は子ノードの最大値になります。

最後から 3 番目の層は、対戦相手が選択する番です。対戦相手は、私たちの価値を最小化する状況にするために全力を尽くすものと想定します。したがって、これらのノードの値は、子ノードの最小値によって決まります。順番が互いに変わるノードは、最小ノードと呼ばれます。

最後に、ルートノードは最大ノードなので、その値はリーフノードの最大値によって決まります。最終的な完全な割り当てパターンツリーは次のようになります。

ミニマックスアルゴリズムの手順を要約すると次のようになります。

まず、最終結果または中間結果となる最大検索深度 D を決定します。
最大深度 D のパターンツリーのリーフノードでは、事前定義された値評価関数を使用してリーフノードの値が評価されます。
下から上の順に非リーフノードに値を割り当てます。最大ノードは子ノードの最大値を取得し、最小ノードは子ノードの最小値を取得します。
私たちの番になるたびに (この時点ではパターンツリーの最大ノードにいる必要があります)、この最大ノードの値と等しい値を持つ子ノードパスを選択します。

上記の例では、ルートノードの値は 20 です。つまり、相手が各ステップで完璧な決定を下した場合、上記のアルゴリズムに従って最終的に 20 元を獲得できます。これは、ミニマックスアルゴリズムに基づく私たちにとって最善の決定です。パターン変換パスは、下の図の赤いパスで示されています。

実際の問題におけるミニマックスについては、いくつかの点を再度強調します。

実際の問題では、完全なパターンツリーを構築することは一般的に不可能であるため、最大深度 D を決定し、現在のパターンから下方向に最大 D 層まで計算する必要があります。
上記の理由により、ミニマックスは一般に、グローバル最適解ではなくローカル最適解を探します。検索の深さが深くなるほど、より良い解が見つかる可能性が高くなりますが、計算時間は指数関数的に増加します。
また、完全なパターンツリーを一度に構築することは不可能であるため、実際の問題では、Minimax は通常、ローカルパターンツリーを 1 回だけ計算するのではなく、ゲームをプレイしながら計算しますが、計算された中間結果はキャッシュできます。

#p#

アルファベータ剪定

単純なミニマックスアルゴリズムの大きな問題は、計算の複雑さです。検索する必要があるノードの数は最大深度とともに指数関数的に増加し、アルゴリズムの効果は深度に関係することが多いため、アルゴリズムの有効性は大きく制限されます。

アルファベータプルーニングは、ミニマックスの補足および改良です。アルファベータプルーニングを使用した後は、最大深度 D 内のすべてのノードを構築して検索する必要がなくなります。構築プロセス中に、現在のパターンでより良いソリューションが見つからない場合は、このパターンとそれ以下の検索を停止します。これがプルーニングです。

アルファベータは、現時点でわかっている最良の選択肢を常に覚えておくというシンプルなアイデアに基づいています。現在のパターンから検索しても既知の最適ソリューションよりも優れたソリューションが見つからない場合は、このパターンブランチの検索を停止 (剪定) し、親ノードに戻って検索を続行します。

アルファベータアルゴリズムは、ミニマックスのバリエーションとして考えることができます。基本的な方法は、ルートノードから始めて深さ優先方式でパターンツリーを構築することです。各ノードを構築するときに、このノードのアルファ値とベータ値が読み取られます。ここで、アルファは現在のノードを検索したときにわかっている最良の選択肢の下限を表し、ベータは、このノードから下方向に検索したときの最悪の結果の上限を表します。相手が状況を最悪の結果の 1 つに導くと想定されるため、ベータがアルファより小さい場合、ここからは最終的な結果がどうであろうと、その上限値が既知の最適解よりも低くなることを意味し、ここでより良い解を見つけることは不可能であるため、剪定が行われます。

以下でも上記の例を使用して、アルファベータプルーニングアルゴリズムの動作原理を紹介します。ルートノードから始めて、Alpha-beta を使用する各ステップを詳しく説明します。

ルートノードのアルファとベータはそれぞれ-∞と+∞に初期化されます。
最初の子に対する深さ優先探索。これはリーフノードではないため、アルファとベータは親ノードから継承され、それぞれ-∞と+∞になります。
上記と同じように、第 3 レベルの最初の子を検索します。
4番目のレイヤーを検索し、リーフノードに到達します。評価関数を使用して、このノードの評価値を1として取得します。
このリーフノードの親ノードは最大ノードなので、そのアルファ値は 1 に更新され、このノードの値の下限が 1 であることを示します。
別の子ノードを見てみると、値は 20 であり、これは現在のアルファ値より大きいため、アルファ値は 20 に更新されます。
この時点で、第 3 層の左端のノードのすべてのサブツリーが検索され、最大ノードとして、その真の値は現在のアルファ値 20 に更新されます。
親ノード (2 番目のレイヤーの左端のノード) は最小ノードであるため、親ノードのベータ値は 20 に更新され、このノードの値が最大 20 になることを示します。
第 2 層の左端のノードの 2 番目の子とそのサブツリーを検索します。上記のロジックによれば、取得される値は 50 です (第 2 層の左端のノードのベータ値を子に渡す必要があることに注意してください)。 50 は 20 より大きいため、最小ノードのベータ値は更新されません。
2 番目のレベルの左端のノードの 3 番目の子を検索します。最初のリーフノードを確認すると、3 番目の子のアルファがベータに等しいことがわかります。これは、このノードにはこれよりよいソリューションが存在しないことを意味するため、このノードは剪定されます。
ブランチ B の検索を続けます。ブランチ B の最初の子を検索すると、ブランチ B のアルファが 20 で、ベータが 10 であることがわかります。これは、B ブランチノードの最大値が 10 を超えないことを意味し、A ブランチではすでに 20 に達しています。このとき、アルファがベータ以上であるという剪定条件が満たされているため、B が剪定されます。そして、ブランチ B のノード値を 10 に設定します。この 10 は必ずしもノードの実際の値ではなく、単に上の線であることに注意してください。ノード B の実際の値は、5、1、または 10 未満の任意の値になります。しかし、それはもう問題ではありません。このブランチはブランチ A よりも優れていないことがわかっているので、諦めることができます。
ブランチ C を検索したところ、ブランチ B と同じ状況に遭遇しました。それでは、C ブランチのプルーニングについてお話ししましょう。

この時点で検索は完了し、このステップの戦略が得られました。つまり、ブランチ A を選択する必要があります。

通常のミニマックスでは 18 個のリーフノードが検索されるのに対し、ここでは 9 個のみが検索されることがわかります。アルファベータプルーニングを使用すると、同じ時間でミニマックスの検索深度を増やすことができ、より良い結果が得られます。そして、アルファベータの解は通常のミニマックスの解と一致します。

#p#

2048ゲームの実装

ov3yが2048年に実装したAIを見てみましょう。プログラムのgithubはここにあり、メインプログラムはai.jsにあります。

モデリング

上で述べたように、ミニマックスとアルファベータはどちらも情報対称性と交代ゲームに関するものです。ここで著者はゲームを次のように抽象化しています。

私たちの側：ゲームプレイヤー。毎回、上、下、左、右の 4 つのチェス移動戦略のいずれかを選択できます (一部のパターンでは、一部の方向は不可能なため、4 つより少ない戦略になる場合があります)。移動後、確立されたロジックに従ってブロックが移動および結合され、パターン変換が完了します。
相手：コンピューター。空いているマスにブロックを置きます。ブロックの値は 2 または 4 になります。新しいブロックを配置すると、レイアウト変換が完了します。
勝利条件: 値が「2048」のブロックが出現する。
失敗条件: グリッドがいっぱいで、4 つの方向のいずれにも移動できません (マージをトリガーできません)。

このように、2048 ゲームは対称情報を持つ 2 人用ゲームの問題としてモデル化されます。

パターン評価

アルゴリズムの核心として、現状の価値をどのように評価するかが最も重要です。 2048 では、最終ゲームを除いて、中間パターンに対する非常に明白な価値評価指標がないため、パターンを評価するにはいくつかのヒューリスティック指標が必要です。スコアが高い「良い」パターンは簡単に勝利につながり、スコアが低い「悪い」パターンは簡単に失敗につながります。

著者らは、以下のようにいくつかのヒューリスティック指標を採用した。

単調性

単調性とは、ブロックが左から右、上から下に増加または減少することを意味します。一般的に言えば、パターンは単調であればあるほど良いです。以下に、優れた単調なパターンの例を示します。

[[111205]]

滑らかさ

滑らかさは、各ブロックとそのすぐ隣のブロックの値の差を指し、差が小さいほど滑らかになります。たとえば、2 と 4 の隣は 2 と 128 の隣よりも滑らかです。一般的に、パターンが滑らかであればあるほど良いと考えられています。非常に滑らかな例を以下に示します。

スペース数

これは簡単に理解できます。一般的に、空きスペースが少ないほど、プレイヤーにとって不利になるからです。したがって、スペースが多ければ多いほど良いと考えます。

隔離された空間の数

この指標は、スペースが分離されている度合いを評価します。スペースが分散しているほど、パターンは悪くなります。

具体的には、2048-AI はパターンを評価する際に、これらのヒューリスティック指標に加重戦略を使用します。具体的なコードは次のとおりです。

 // 静的評価関数 
 AI.prototype.eval =関数() { 
     var emptyCells = this .grid.availableCells().length; 
   
     varスムーズウェイト = 0.1, 
         //モノウェイト = 0.0,  
         //島の重み = 0.0,  
        モノ2ウェイト = 1.0、
        空の重量 = 2.7、
        最大重量 = 1.0; 
   
    戻る この.grid.smoothness() * スムーズウェイト
         //+ this.grid.monotonicity() * monoWeight  
         //- this.grid.islands() * 島の重み 
        +この.grid.monotonicity2() * mono2Weight
        + Math.log(空のセル) * 空の重量
        +この.grid.maxValue() * maxWeight;
 };

興味のある学生は重みを調整して、どのような効果があるかを確認できます。

相手の選択を刈り込む

このプログラムでは、アルファベータ剪定に加えて、最小ノードで別のタイプの剪定が使用され、対戦相手の可能なすべての動きを検索する代わりに、最悪の状況を生み出す対戦相手の動きのみを考慮します (実際の 2048 でのコンピューターの選択はランダムです)。なぜなら、相手にとっての選択肢は「マス数×2」しかなく、すべて探索すると探索の深さが著しく制限されてしまうからです。

関連するプルーニングコードは次のとおりです。

 // 各セルに 2 と 4 を入力して、どれだけ迷惑か測定します 
 // evalからのメトリクス付き 
 var候補 = [];
 varセル = this .grid.availableCells();
 varスコア = { 2: [], 4: [] };
 for ( varスコアの値) { 
     for ( var i in cells) {
        スコア[値].push( null ); 
         varセル = cells[i]; 
         var tile = new Tile(セル、parseInt(値、10)); 
         .grid.insertTile (タイル);
        スコア[値][i] = - this .grid.smoothness() + this .grid.islands(); 
         this .grid.removeTile(セル);
    }
 } 
   
 // 最も迷惑な動きをピックアップするだけです 
 var maxScore = Math.max(Math.max.apply( null , スコア[2]), Math.max.apply( null , スコア[4]));
 for ( var value in scores) { // 2 と 4  
     ( var i=0; i<scores[value].length; i++) { 
         if (スコア[値][i] == maxScore) {
            candidates.push( { 位置: cells[i], 値: parseInt(value, 10) } );
        }
    }
 }

検索の深さ

2048-AI の実装では、検索の最大深度は制限されませんが、各「思考」の時間は制限されます。ここでタイムアウトを設定します。デフォルトは 100 ミリ秒です。この間、検索は 1 から開始され、到達可能な深さまで到達します。関連コード:

 // アルファベータ検索の反復深化を実行します 
 AI.prototype.iterativeDeep =関数() { 
     var start = (新しいDate()).getTime(); 
     var深さ = 0; 
     varベスト; 
    する{ 
         var newBest = this .search(depth, -10000, 10000, 0 ,0); 
         (newBest.move == -1)の場合{ 
             //console.log('早めに終了');  
            壊す;
        }それ以外{
            ベスト = 新しいベスト;
        }
        深さ++;
    } while ( ( new Date().getTime() - 開始 < minSearchTime); 
     //console.log('depth', --depth);  
     //console.log(this.translate(best.move));  
     //console.log(ベスト);  
    最高のリターン
}

したがって、このアルゴリズムの効果は、実際には JavaScript エンジンを実行するマシンのパフォーマンスに依存します。もちろん、タイムアウト期間を長くするとより良い結果が得られますが、各ステップの速度は遅くなります。

アルゴリズムの改善

現在、この実装の作成者は、2048 を正常に合成できる確率は 90% を超えていると主張していますが、4096 や 8192 を合成できる確率は高くありません。著者は、github プロジェクトの REAMDE で、次のような最適化の提案も行っています。

結果をキャッシュします。現在、この実装では検索されたツリーがキャッシュされないため、各ステップで検索を再開する必要があります。
マルチスレッド検索。 JavaScript エンジンはシングルスレッドであるため、これを実行するのは困難ですが、他のプラットフォームの場合は、並列テクノロジを検討できる可能性があります。
より優れたヒューリスティック。おそらく、パターンの価値を評価するために、いくつかのより優れたヒューリスティック関数を要約できるでしょう。