3

Android 用のリバーシ ゲームを実装する必要があります。私はすべてのゲームを実装することに成功し、機能していますが、問題は私が AI を持っていないことです。実際、すべての動きで、コンピューターは彼に最高のピース数を達成する位置に移動します。

alpha-beta pruning アルゴリズムを実装することにしました。インターネットでいろいろ調べたのですが、どうすればよいのか、最終的な結論には至りませんでした。いくつかの機能を実装しようとしましたが、目的の動作を実現できませんでした。

私のボードはクラス Board に保存されます (このクラス内では、各プレイヤーが占有するピースは 2 次元の int 配列に保存されます)。小さな図を添付しました（見栄えが悪くてすみません）。

図: https://docs.google.com/file/d/0Bzv8B0L32Z8lSUhKNjdXaWsza0E/edit

私の実装で minimax アルゴリズムを使用する方法を理解するのに助けが必要です。

ここまででわかったことは、ボードの価値に関する評価関数を作成する必要があるということです。

ボードの価値を計算するには、次の要素を考慮する必要があります: -フリー コーナー (私の質問は、フリー コーナー、または現在の動きで取ることができるコーナーだけに注意する必要があるということです!ここでジレンマ) . - ボードの可動性: 現在の移動後に、移動できるピースの数を確認します。・ボードの安定性…ボード上で裏返せないピースの数を意味することは知っています。-移動が私に提供するピースの数

Boardオブジェクトと部門を引数として取る新しいクラスBoardAIを実装する予定です。

この AI をどのように実装する必要があるかについて、アイデアの論理的な流れを教えてください。dept で計算しているときに再帰について助けが必要ですが、最良の選択をどのように計算するのかわかりません。

ありがとうございました！

4

1 に答える 1

5

まず、私が何年も前に書いたチェッカーAIのこのコードをチェックできます。興味深い部分は最後の関数（alphabeta）です。（Pythonですが、擬似コードのように見ることができると思います）。

明らかに、私はあなたにすべてのアルファ/ベータ理論を教えることはできません。それは少しトリッキーかもしれないからですが、多分私はあなたにいくつかの実用的なヒントを与えることができます。

評価関数

これは、優れた最小/最大アルファ/ベータアルゴリズム（およびその他の情報に基づく検索アルゴリズム）の重要なポイントの1つです。優れたヒューリスティック関数を作成することは、AI開発の芸術的な部分です。あなたはゲームをよく知っている必要があり、質問に答えるためにどのボード機能が重要であるかを理解するために専門家のゲームプレーヤーと話をする必要があります：プレーヤーXにとってこの位置はどれくらい良いですか？

機動性、安定性、フリーコーナーなどの優れた機能についてはすでに説明しました。ただし、評価関数は何度も呼び出されるため、高速である必要があることに注意してください。

基本的な評価関数は

H = f1 * w1 + f2 * w2 + ... + fn * wn

ここfで、は特徴スコア（たとえば、空きコーナーの数）であり、は特徴fが合計スコアでどれだけ重要であるかwを示す対応する重みです。

重みの値を見つける唯一の方法は、経験と実験です。;）

基本的なアルゴリズム

これで、アルゴリズムから始めることができます。最初のステップは、ゲームツリーのナビゲーションを理解することです。私のAIでは、AIが動きを試すことができる黒板のようなプリンシパルボードを使用しました。

たとえば、特定の構成B1のボードから始めます。

ステップ1：利用可能なすべての動きを取得します。特定のプレーヤーに適用可能なすべてのB1への移動を見つける必要があります。私のコードでは、これはによって行われself.board.all_move(player)ます。動きのリストを返します。

ステップ2：移動を適用し、再帰を開始します。関数が3つの動き（ M1、M2、M3 ）を返したと仮定します。

  1. 最初の動きM1を取り、それを適用して新しいボード構成B11を取得します。
  2. 新しい構成にアルゴリズムを再帰的に適用します（B11で適用可能なすべての移動を見つけて適用し、結果に再帰を適用します...）
  3. 移動を元に戻して、B1構成を復元します。
  4. 次の動きM2を取り、それを適用して新しいボード構成B12を取得します。
  5. 等々。

注：ステップ3は、すべての移動が可逆的である場合にのみ実行できます。それ以外の場合は、移動ごとに新しいボードを割り当てるなど、別の解決策を見つける必要があります。

コード内：

for mov in moves :
    self.board.apply_action(mov)
    v = max(v, self.alphabeta(alpha, beta, level - 1, self._switch_player(player), weights))
    self.board.undo_last()

ステップ3：再帰を停止します。この3つは非常に深いため、アルゴリズムに検索制限を設定する必要があります。n簡単な方法は、レベルの後で反復を停止することです。たとえば、B1、max_level=2およびで始めcurrent_level=max_levelます。

  1. B1（current_level 2）から、たとえば、M1移動を適用してB11を取得します。
  2. B11（current_level 1）から、たとえば、M2はB112を取得するために移動します。
  3. B122は「current_level0」ボード構成なので、再帰を停止します。B122に適用された評価関数の値を返し、レベル1に戻ります。

コード内：

if level == 0 :
    value = self.board.board_score(weights)
    return value

さて...標準アルゴリズムの擬似コードは、最良の葉の値の値を返します。Buどの動きが私を最高の葉に連れて行くのか知りたいです！これを行うには、葉の値を動きにマッピングする方法を見つける必要があります。たとえば、移動シーケンスを保存できます。B1から開始して、シーケンス（M1 M2 M3）は、値-1でボードB123にプレーヤーを連れてきます。シーケンス（M1 M2 M2）は、値2のボードB122にプレーヤーを連れてきます。など...次に、AIを最適な位置に移動する動きを選択するだけです。

これがお役に立てば幸いです。

編集：アルファベータに関するいくつかのメモ。アルファベータアルゴリズムは、グラフィカルな例なしでは説明が困難です。このため、これまでに見つけた中で最も詳細なアルファベータ法の説明の1つであるこれをリンクしたいと思います。それ以上のことはできないと思います。:)

重要なポイントは次のとおりです。アルファベータ法は、ノードに2つの境界をMIN-MAXに追加します。この境界を使用して、サブツリーを展開するかどうかを決定できます。

この境界は次のとおりです。

  • アルファ：可能な解の最大下限。
  • ベータ：可能なソリューションの最小上限。

Beta < Alpha計算中に、そのサブツリーの計算を停止できる状況が見つかった場合。

明らかに、それがどのように機能するかを理解するために前のリンクをチェックしてください。;）

于 2013-01-17T11:18:18.123 に答える