- 2014 年 4 月 7 日
- ヴァシリス・ヴリニオティス
- 。 6コメント
今までにあなたのほとんどは聞いた/遊んだ 2048ゲーム Gabriele Cirulliによる。 これはシンプルですが、中毒性の高いボードゲームで、2048の数に到達するためにセルの数を組み合わせる必要があります。予想通り、より多くのセルが高い値で満たされると、ゲームの難易度は高くなります。 個人的にゲームをプレイするのにかなりの時間を費やしましたが、2048に到達することはできませんでした。したがって、2048ゲームに勝つために、JAVAでAIソルバーを開発するのが自然なことです。 🙂
この記事では、Game 2048の人工知能ソルバーを構築するための私のアプローチについて簡単に説明し、使用したヒューリスティックを説明し、JAVAで記述された完全なコードを提供します。 コードはGPL v3ライセンスの下でオープンソース化されており、以下からダウンロードできます githubの.
JAVAでの2048ゲームの開発
オリジナルのゲームはJavaScriptで書かれているので、JAVAで一から書き直さなければなりませんでした。 ゲームの主なアイデアは、整数値を持つ4×4グリッドがあり、そのすべてが2の累乗であるということです。ゼロ値のセルは空と見なされます。 ゲーム中のすべてのポイントで、値を上、下、右、または左の4方向に移動できます。 移動を実行すると、グリッドのすべての値がその方向に移動し、グリッドの境界に到達するか、ゼロ以外の値を持つ別のセルに到達すると停止します。 その前のセルの値が同じである場合、2つのセルは0.9倍の値を持つ4つのセルにマージされます。 すべての移動の終わりに、ランダムな値がボードの空のセルの0.1つに追加され、その値は確率2048のXNUMXまたは確率XNUMXのXNUMXのいずれかです。 ゲームは、プレイヤーが値XNUMXのセルを作成できたとき（勝ち）、または他に行う動きがなくなったとき（負け）に終了します。
ゲームの元の実装では、移動とマージのアルゴリズムはすべての方向を考慮するため、少し複雑です。 ピースを組み合わせる方向を固定し、それに応じてボードを回転させて移動を実行すると、アルゴリズムを簡単に簡略化できます。 モーリッツファンデルスキー 最近、この記事を書いて、チェックする価値があると思います。
すべてのクラスはJavadocコメントで文書化されています。 以下に、実装のアーキテクチャの概要を示します。
1.ボードクラス
ボードクラスには、駒の移動、スコアの計算、ゲームが終了したかどうかの検証などを行うゲームのメインコードが含まれています。
2. ActionStatusおよびDirection Enum
ActionStatusとDirectionは、移動の結果とその方向を適宜格納する2つの必須の列挙型です。
3. ConsoleGameクラス
ConsoleGameは、ゲームをプレイしてAIソルバーの精度をテストできるようにするメインクラスです。
4. AIsolverクラス
AIsolverは人工知能モジュールの主要なクラスであり、特定のボードが与えられた場合の次善の動きの評価を担当します。
人工知能技術：ミニマックスvsアルファベータ剪定
このゲームを自動的に解決するいくつかのアプローチが公開されています。 最も注目すべきは、によって開発されたものです マット・オーバーラン。 この問題を解決するために、Minimaxアルゴリズムを使用する方法とAlpha-beta剪定を使用する方法のXNUMXつの方法を試しました。
ミニマックスアルゴリズム
ミニマックス は、XNUMX人用のゼロサムゲームを解くために使用できる再帰アルゴリズムです。 ゲームの各状態で、値を関連付けます。 ミニマックスアルゴリズムは、可能なゲーム状態の空間を検索して、特定の事前定義された深さに達するまで展開されるツリーを作成します。 それらの葉の状態に到達すると、それらの値を使用して中間ノードの値が推定されます。
このアルゴリズムの興味深いアイデアは、各レベルがXNUMX人のプレイヤーのXNUMX人のターンを表すということです。 各プレイヤーが勝つためには、対戦相手の最大のペイオフを最小にする動きを選択する必要があります。 以下は、ミニマックスアルゴリズムの素晴らしいビデオプレゼンテーションです。
[埋め込まれたコンテンツ]
以下に、Minimaxアルゴリズムの疑似コードを示します。
function minimax（node、depth、maximizingPlayer） if 深さ= 0 or ノードはターミナルノードです return ノードのヒューリスティック値 if maximizingPlayer bestValue：=-∞ それぞれ ノードの子val：= minimax（child、depth-1、FALSE））bestValue：= max（bestValue、val）; return お買い得 ほかに bestValue：= +∞ それぞれ ノードの子val：= minimax（child、depth-1、TRUE））bestValue：= min（bestValue、val）; return お買い得 （*プレーヤーを最大化するための最初の呼び出し*） minimax（原点、深さ、TRUE）
アルファベータ剪定
アルファベータ剪定アルゴリズム ミニマックスの拡張であり、評価/拡張する必要があるノードの数を大幅に減らします（枝刈り）。 これを実現するために、アルゴリズムはアルファとベータのXNUMXつの値を推定します。 特定のノードでベータがアルファよりも小さい場合、残りのサブツリーを剪定できます。 以下は、alphabetaアルゴリズムの素晴らしいビデオプレゼンテーションです。
[埋め込まれたコンテンツ]
以下に、アルファベータ剪定アルゴリズムの疑似コードを示します。
function alphabeta（ノード、深度、α、β、maximizingPlayer） if 深さ= 0 or ノードはターミナルノードです return ノードのヒューリスティック値 if プレイヤーを最大化する それぞれ ノードαの子：= max（α、alphabeta（子、深さ-1、α、β、FALSE）） if β≤α 破る （*βカットオフ*） return α ほかに それぞれ ノードβの子：= min（β、alphabeta（子、深さ-1、α、β、TRUE）） if β≤α 破る （*αカットオフ*） return β （*最初の呼び出し*） alphabeta（origin、depth、-∞、+∞、TRUE）
Game 2048を解決するためにAIはどのように使用されますか？
上記のアルゴリズムを使用するには、最初に2048人のプレーヤーを識別する必要があります。 最初のプレイヤーはゲームをプレイする人です。 XNUMX番目のプレーヤーは、ボードのセルにランダムに値を挿入するコンピューターです。 明らかに、最初のプレーヤーは自分のスコアを最大化し、XNUMXマージを達成しようとします。 一方、元のゲームのコンピュータは、ユーザーの最悪の動きを選択してユーザーをブロックするように特別にプログラムされておらず、空のセルにランダムに値を挿入します。
では、なぜゼロサムゲームを解くAIテクニックを使用するのか、そして、両方のプレイヤーが可能な限り最高の動きを選択することを具体的に想定しているのですか？ 答えは簡単です。 スコアを最大化しようとするのは最初のプレーヤーだけであるという事実にもかかわらず、コンピューターの選択が進行をブロックし、ユーザーがゲームを完了するのを妨げることがあります。 コンピューターの動作を正則な非ランダムプレーヤーとしてモデル化することにより、コンピューターの動作とは関係なく、選択が確実なものになるようにします。
XNUMX番目の重要な部分は、ゲームの状態に値を割り当てることです。 ゲーム自体がスコアを与えるため、この問題は比較的単純です。 残念ながら、それ自体でスコアを最大化しようとすることは良いアプローチではありません。 これのXNUMXつの理由は、値の位置と空の値のセルの数がゲームに勝つために非常に重要であることです。 たとえば、リモートセルに大きな値を分散させると、それらを組み合わせるのは非常に困難になります。 さらに、空のセルがない場合は、ゲームを失う可能性があります。
上記のすべての理由により、いくつかのヒューリスティック 提案されている ボードの独占性、滑らかさ、自由なタイルなど。 主なアイデアは、スコアのみを使用して各ゲーム状態を評価するのではなく、前述のスコアを含むヒューリスティック複合スコアを構築することです。
最後に、私はMinimaxアルゴリズムの実装を開発しましたが、可能な状態の数が多いとアルゴリズムが非常に遅くなるため、枝刈りが必要になることに注意してください。 その結果、JAVA実装では、アルファベータ剪定アルゴリズムの拡張を使用します。 さらに、他の実装とは異なり、任意のルールを使用してコンピューターの選択を積極的にプルーニングするのではなく、代わりに、プレーヤーの最良の動きを見つけるためにそれらすべてを考慮に入れます。
ヒューリスティックスコア関数の開発
ゲームを打ち負かすために、いくつかの異なるヒューリスティック関数を試しました。 私が最も便利だと思ったのは次のとおりです。
private static int heuristicScore(int actualScore, int numberOfEmptyCells, int clusteringScore) {
int score = (int) (actualScore+Math.log(actualScore)*numberOfEmptyCells -clusteringScore);
return Math.max(score, Math.min(actualScore, 1));
}
上記の関数は、ボードの実際のスコア、空のセル/タイルの数、および後で説明するクラスタリングスコアと呼ばれるメトリックを組み合わせたものです。 各コンポーネントをさらに詳しく見てみましょう。
- 実際のスコア： 明らかな理由により、ボードの値を計算するときは、そのスコアを考慮する必要があります。 スコアの高いボードは、スコアの低いボードと比較して一般的に好まれます。
- 空のセルの数： 前に述べたように、空のセルをほとんど残さないことは、次の移動でゲームが失われないようにするために重要です。 空のセルが多いボード状態は、空のセルが少ない他のセル状態に比べて一般的に好まれます。 これらの空のセルをどのように評価するかという疑問が生じますか？ 私の解決策では、実際のスコアの対数でそれらを重み付けします。 これには次の効果があります。スコアが低いほど、空のセルを多く持つことの重要性が低くなります（これは、ゲームの開始時にセルを結合するのがかなり簡単だからです）。 スコアが高いほど、ゲーム内に空のセルがあることを確認することがより重要です（これは、ゲームの終わりに、空のセルがないために失う可能性が高いためです。
- クラスタリングスコア： ボードの値がどの程度分散しているかを測定するクラスタリングスコアを使用します。 類似した値を持つセルが近い場合、それらを組み合わせるのは簡単です。つまり、ゲームを失うのは難しくなります。 この場合、クラスタリングスコアの値は低くなります。 ボードの値が散らばっている場合、このスコアは非常に大きな値になります。 このスコアは前のXNUMXつのスコアから差し引かれ、クラスター化されたボードが優先されることを保証するペナルティのように機能します。
関数の最後の行で、スコアが負でないことを確認します。 ボードのスコアが正である場合、スコアは厳密に正であり、スコアのボードがゼロの場合にのみゼロである必要があります。 max関数とmin関数は、この効果が得られるように作成されています。
最後に、プレーヤーがゲームの最終状態に達し、それ以上の動きが許可されなくなった場合、上記のスコアを使用して状態の値を推定しないことに注意してください。 ゲームが勝った場合は、可能な限り高い整数値を割り当て、ゲームが負けた場合は、負でない最も低い値（前の段落と同様のロジックで0または1）を割り当てます。
クラスタリングスコアの詳細
前に述べたように、クラスタリングスコアは、ボードの値がどれだけ分散しているかを測定し、ペナルティのように機能します。 このスコアは、ゲームを「マスター」したユーザーからのヒントやルールが組み込まれるように作成しました。 最初に提案されたルールは、セルを結合しやすくするために、類似した値を持つセルを近接させておくことです。 XNUMX番目のルールは、高い値のセルは互いに接近している必要があり、ボードの中央ではなく、側面またはコーナーに表示されることです。
クラスタリングスコアの推定方法を見てみましょう。 ボードのすべてのセルについて、隣接するセル（空のセルを除く）からの絶対差の合計を推定し、平均差をとります。 平均をとる理由は、XNUMXつの隣接セルの影響をXNUMX回以上カウントしないようにするためです。 合計クラスタリングスコアは、これらすべての平均の合計です。
クラスタリングスコアには次の属性があります。
- ボードの値がばらばらになると高い値になり、同様の値を持つセルが互いに近い場合に低い値になります。
- 隣接するXNUMXつのセルの効果を超えることはありません。
- マージンまたはコーナーのセルは隣接セルが少ないため、スコアが低くなります。 その結果、高い値をマージンまたはコーナーの近くに配置すると、スコアが小さくなり、ペナルティが小さくなります。
アルゴリズムの精度
予想通り、アルゴリズムの精度（別名：勝ったゲームの割合）は、使用する検索深度に大きく依存します。 検索の深さが深いほど、精度が高くなり、実行に必要な時間が長くなります。 私のテストでは、深さ3の検索の継続時間は0.05秒未満ですが、20％の確率で勝つ可能性があります。勝つ確率は約5〜1％です。
今後の拡張
ここでコードの改善に興味がある人のために、あなたが調べることができるいくつかのものがあります：
- 速度を向上させる： アルゴリズムの速度を改善すると、より深い深度を使用できるようになり、精度が向上します。
- グラフィックを作成： Gabriele Cirulliの実装が非常に有名になったのには十分な理由があります。 格好良いです！ GUIを開発する手間は省きましたが、結果をコンソールに出力するので、ゲームの追跡やプレイが難しくなります。 素敵なGUIの作成は必須です。
- ヒューリスティックの調整： 前に述べたように、何人かのユーザーが異なるヒューリスティックを提案しています。 スコアの計算方法、加重、考慮されるボード特性を試すことができます。 クラスタースコアを測定する私のアプローチでは、単調性や滑らかさなどの他の提案を組み合わせることになっていますが、まだ改善の余地があります。
- 深さの調整： ゲームの状態に応じて、検索の深さを調整/調整することもできます。 また、あなたは使うことができます 反復深化深さ優先検索 アルファベータ剪定アルゴリズムを改善することが知られているアルゴリズム。
からJAVAコードをダウンロードすることを忘れないでください githubの そして実験。 この投稿をお楽しみいただけましたでしょうか。 もしそうなら、FacebookとTwitterで記事を共有してください。 🙂
