「海戦」におけるゲームのアルゴリズム：敵の砲撃

こんにちは、愛しい人！ ゲーム「海戦」に多かれ少なかれ適切なAIをプログラミングするという質問は、2004年後半にどこかで困惑しました。 たぶん私は、適切な指導なしで自転車を発明しましたが、その後、私は彼らの誠実さに驚くべき素晴らしいアルゴリズムに出くわしました。ランダムに撃ち、時々バランスをとるために船の位置を覗きます。 その後、アルゴリズムを数回改善しました。 Habréの最新の記事によると、このトピックが関連していると判断できます。また、他のユーザーが書いたものに追加するものがあります。

だから、私のメモの目標は、 敵の船を攻撃するための戦略の最適なものの実装であり 、最初のヒットだけでなく、その後の「底までの追跡」でもあります。 私の実装での船は、ほぼ（以下でさらに）任意の形状であることに注意してください。

はじめに

序文部分を短くすることを許可します-写真の完全性のために、以前の記事を参照することをお勧めします。

• 海戦をプレイするための最適なアルゴリズム （ GORKOFF ）
• ゲーム「海戦」の理論と実践- 正直に （ born2fly ）

「デッキ」の代わりに「船の船体に属するケージ」など、大きなターンで物語を複雑にしたくないという願望に起因するいくつかの専門用語についてすぐに謝罪します（私の子供時代、私たちは船を「4デッキ」、「シングルデッキ」などと呼びました-理由はわかっています）。

船は任意の形状をとることができますが、船体（「デッキ」）に属する各セルは、他のセルと水平および/または垂直および/または斜めに接続する必要があります。

座標グリッド（競技場を視覚化した図）：左から右-数字、上から下-文字。

ご注意

この記事では、コードレベルでの最適化を考慮していませんが、アルゴリズムは最も詳細な（詳細な）形式で提示されています。

説明図に加えて、記事には私のプログラム/ゲームのスクリーンショットが含まれています。

モード

戦闘戦略では、2つのステージ（2つのモード）を明確に区別できます。

• 「 戦闘中の偵察 」 敵の地図には、「傷ついた」船は1つもありません。 AIは、「完全に健全な」船を攻撃するポイントを選択します。
• 「 仕上げ 」。 マップ上には、「傷ついた」とマークされたセルがあります。 AIは、船を沈めるために船の船体と方向を決定しようとしています。

ほとんどの人は、敵の船を「傷つけ」て、それを殺そうとします。 logical死により、沈没した船の周囲に追加の（バッファ）ゾーンが発砲にとって無意味になり、敵のフィールドに関する情報量が増加し、発砲する確率が低下するため、これは論理的です。 さらに、船が占有する次のポイントが計算され、最悪の場合、4ターン（対角船-8ターン）で計算されることが保証されますが、新しい船をノックアウトしようとすると生産性が大幅に低下します。

したがって、AIは「インテリジェント」モードで動作を開始し、重大でない損傷（「負傷」）が発生した場合、敵船は「仕上げ」モードになります。 2番目のモードでは、AIは船が破壊されるまで機能し、その後、最初のモードが再び選択されます。

「古典的な」飛行隊（ベンドのない船）のアルゴリズムを最適化する場合、3番目のモードを選択すると便利な場合があります（これについては後で詳しく説明します）。 1番目と2番目のモードは、確率行列の形成の特徴（以下で詳しく説明します）、およびレジーム変更のロジックが異なります。

知能

任意の形状の任意の数の船から形成された飛行隊を攻撃できる抽象化レベルを達成するために（それでも、ルールによれば、敵に関するこの情報は事前に知られています）、壊れていない船の破片（この競技場の「デッキ」）の確率の概念を導入します"）。 攻撃ポイントを選択するための基準は、上記の確率に比例する値になります。つまり、敵の船（浮いている船）があらゆる方法でフィールドに配置しようとした場合に、このセルに落下する正規化されたデッキの数です。

説明してみましょう。マトリックス（以降、「Pマトリックス」と呼びます）を取ります。このディメンションは、相手のフィールドのディメンションに対応します。 ゼロで埋めます。 敵の船のリストから最初に利用可能な（つまりまだ沈んでいない）敵船を取得し、（規則に従って、砲撃中に取得した情報に基づいて）座標A1に配置しようとします。 配置できた場合は、Pマトリックスで、船体で覆われているすべての要素（競技場のセルに対応）をインクリメントします。 すべての座標に対して手順を繰り返します。 次に、船を90度回転させ、すべての座標について通過を繰り返します。 180度と270度についても同じことを繰り返します。

その結果、便宜上P行列に最大値に正規化された値を入力します。 得られた特性は、船の最も可能性の高いポイントで単一の値を取り、不可能でゼロになります。 たとえば、発射されていないマップでは、中心点（ 古典的な戦隊の場合）に最大値があります。

誤解を避けるために、「 確率 」という用語を定義する価値があります。 このアルゴリズムは、現場での船舶の均一な配置を想定しています。 血管をフィールドの端に沿って押す試みは、個別に検出する必要があります。 たとえば、トレーニング中に何らかの形で形成されるウェイトマトリックスを入力できます（この対戦相手との以前のゲーム）：その前に敵が船をフィールドの中央に配置しない場合、ウェイトマトリックスの対応するセルには最小係数があります。 いずれにせよ、これはチェスではありません-常に未知の情報があり、状況が成功すれば、「ディフェンダー」に利点を与えることができます。

左の図は、 古典的な戦隊を使用したゲームでの最初のAI移動中のPマトリックスの視覚化を示しています。 カラー[RGB（0; 0; 0）; RGB（255; 0; 0）]は、セルの値を示します。 白い十字は最大値を示します。 ご覧のとおり、通常はいくつかの高値があります。 ゲームを多様化し、AIによって選択された攻撃ポイントを予測する可能性を排除する（およびそれに応じて船を配置する）ために、最大値から任意のポイントを選択します（図では-黄色の枠があります）。

相手の回答が「過去」または「殺された」の場合、AIの動作モードは変更されません（2番目の場合、いくつかのアクションが必要です）。 回答は、敵の力のバランスに関する知識を蓄積する特別なマトリックスに保存されます。 Pマトリックスの計算で船舶を配置する試みは「 このマトリックス上 」で行われます。

古典的な飛行隊のみを使用する場合、行列の計算を最適化することができます（これについては以下で詳しく説明します）。

仕上げ

相手から「負傷」した応答の後、AIは第2の動作モードに切り替わります。

このモードでは、Pマトリックスを計算するときに、テストされた船の「デッキ」の数が「傷ついた」セルの数よりも多くなければなりません。 船は、その配置が「傷」としてマークされたすべてのセルをカバーする場合にのみ、Pマトリックスの要素の値を増分します。 すべての船を列挙した後、「傷ついた」セルをさらに強調します。 そのようなセルを撃つことは無意味なので（ただし、「by」セルとは異なり、船の一部であり、Pマトリックスにゼロ以外の値があります）、Pマトリックスの対応する要素の値はリセットされます。 「傷ついた」セルのいずれにも隣接していないセルも無効になります。 後者の状況は、非古典的な戦隊船のエキゾチックな形状によって強化された状況下で、別の船に対応するPマトリックスの最大値を選択できるという事実によるものです（攻撃されたセルが「傷ついた」ものから分離されている場合にのみ可能です）。 この状況は、AIが両方のセルを満たす船を拾おうとするという事実につながり、遅かれ早かれ失敗します。 これは、Pマトリックスのすべての要素がゼロの値をとるという事実につながります。したがって、すでに発火したポイントは適切な攻撃オプションになります。 したがって、近くのポイントを攻撃するのが妥当です。

左の図は、2つのマトリックス（より正確には、それらの値の視覚化）を示しています。 アッパー-灰色の船が白いフィールドにあります。 前の動きでは、AIはZh4に成功した攻撃を実行しました（最初の動きが成功したという事実は偶然です）。「傷ついた」セルは黄色でマークされています。 以下はPマトリックスです。 実際の船のセットのジオメトリを考えると、AIには4つの同等の可能性のある攻撃オプション（十字のマークが付いたセル）があり、そこからZh3（黄色の枠のセル）を選択しました。 移動はミスで終了しました（上のマトリックスの青いセル）。

エキゾチックなジオメトリを備えた船のセットを使用すると、マトリックスはさらに神秘的になります。 私は古典的な戦隊でプレイすることに慣れていますが、 ほぼ任意の形状の船を使用することで非難されることは見当たりません。 このようなモデルは、たとえば高速双胴船 、 RV FLIP 、 重空母巡洋艦 、 「コンクリート戦艦」を模倣できます。 動きのない（ゲームの論理による）オブジェクトは、世界大戦中に陸上の低機動性（または静止した）戦略的オブジェクトとして解釈できるという事実は言うまでもありません。 私の意見では、ゲームプレイの位置から、そのような複雑さはゲームに興奮を加えるだけです。

右側の写真は状況を示しています。何度かサルボを成功させた後、AIは間違った方向を選択し、E13でミスします。 意味のある移動オプションが10個あり、そのうち2個が最も可能性が高いことに注意してください。

「仕上げ」モードは、対戦相手が「殺された」と答えた後にのみ「知能」に切り替わります。 最初のモードと同様に、砲撃中に得られた情報は、次の動きでPマトリックスを形成するときに考慮されます。

クラシック

古典的な戦隊、つまり「1次元」船を使用すると、アプローチを指定して、操作の数を減らすことができます。 一方で、以下で説明するアルゴリズムは柔軟性が低く、パフォーマンスのクラムを節約します（現在の技術レベルとジャンルによる1移動あたりの長い時間を考慮すると）が、一方で、これらのアルゴリズムはゲームの人間の知覚により近く、プロセスの理解を容易にしますAI機能。

古典的な船のジオメトリの詳細（つまり、1次元性）によって、船体を180度回転させて（回転点に応じて-対応する座標を修正して）船体をゼロ回転角で配置する確率と等しくすることができます。 言い換えれば、すべての船について判断することは不可能です：上から下、または下から上、左から右、または右から左にあります（左の図を参照してください：灰色の船体の4つの回転角度と古典的な茶色の2つの回転角度）。 この状況により、計算の数を減らすことができ、すべての船に0度と90度の角度での配置テストのみを残します。

一次元性により、船の長さと障害物までの距離のみに依存して、ケージに落ちる「デッキ」の数を決定できます。 右側の図では、障害物のセル（他の船の緩衝地帯など）が赤でマークされ、特性が計算されるセルは緑の円で示されています。 3セルの長さの船を配置しようとします。 結果（上から下）は0、0、1、1になると推測するのは簡単です。明らかに、最初の2つのケースでは、障害物間の距離は基本的に必要な長さの体に対して十分ではありません。 4番目のケースでは、船の可能な位置の数を増やすために、反対側の境界線のみをプッシュできることが明らかになります。

左に障害物を移動し始め、1、2、3、3の特性を取得します。結果から、特性は船の長さによって上から制限されていることがわかります。

要約すると：

• 距離の合計+ 1（テストセル）が船の長さより小さい場合、結果は0です。
• 距離の合計+ 1が船の長さに等しい場合、結果は1です。
• その他の場合、特性は次のとおりです。
  
  
  • 1以上
  • 船の長さを超えない
  • 障害物までの最小距離に制限

上記に基づいて、特性を計算する関数のコードの形式は次のとおりです。

inline unsigned minimum(unsigned A,unsigned B){ return A<B?A:B; } unsigned Bf(unsigned A,unsigned B,unsigned K){ if(A+B+1<K) return 0; if(A+B+1==K) return 1; return minimum(minimum(A,B)+1,K); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

敵の戦隊に同じ長さの船が複数ある場合、セルへの影響の合計を考慮するには、一度Bfを計算し、結果に装備の数を掛ければ十分です。 敵の船のすべてのユニークな長さ（ クラシック -4オプションの場合）を調べて、この船体の長さが浮いている船の数を考慮すると、特定の特性Gfが得られます。 この特性は、すべての船舶の固定された方向（座標ではない）でケージに落ちる「デッキ」の数を示します（たとえば、上の図では水平）。 最終的な特性G2dfは、水平および垂直方向のGfの合計です。 競技場のすべてのセルのG2df値のマトリックスは、上記のPマトリックスの類似物です。 マトリックスの最大値に基づいて、攻撃ポイントを選択します。 成功した場合は、フィニッシングモードに進み、最も自由な（ただし、破壊されていない敵船の中で最大の船体長内にある）方向に対応するセルを選択します。 複数の方向が同じ確率である場合-ランダムに選択します。 攻撃の方向を選択した後、次のいずれかの結果に向けて発砲し続けます。

• 1.船が破壊されます。 新しい被害者の検索モードに切り替えます。
• 2.ミス 。 したがって、攻撃は極端なポイントから開始されませんでした。 火の方向を反転し、最初の「傷」のポイントから攻撃を続ける
  
  
  • 2.1。 仕上げモードでの最初のショットのミス 。 これは、方向が誤って選択されたことを意味します。 受信した情報を考慮に入れて、ルートの確率を再計算する必要があります。
• 3.選択した方向への射撃は意味がなく （たとえば、競技場の端に到達した）、 船はまだ浮いています。 解決策はパラグラフ2に似ています。

おわりに

これで、敵を攻撃する方法と、船を最適に配備する方法がわかりました（記事の冒頭のリンクを参照）。

私自身は、船舶の最適でない（均一な）配置に関するコミュニティの考えを知りたいと思います。 古典的なバージョンであっても、既に設定されている船舶を動かさないと、デッドロックが発生する可能性があります。 任意の形状の船の場合、配置するフィールドの最小サイズの基準を正当化することがおそらく可能です。

記事を最後まで読んでくださった皆さんに感謝します。 私はあなたの質問に答えようとします。

リクエスト：議論を薄めないように、エラーに関する指示と編集に関するその他の提案をPMに書いてください。

批評

興味深く建設的なコメントをありがとう！



mayorovpは、考慮されたアルゴリズムが特定の近似でのみ最適に機能することを明確にします。 実際、提案された状況を考慮してください。

ラインに5つのセルがあり、2つの1x2船がフィールドに残っている場合、最適なアルゴリズムはそれらを4ショットでミスなく破壊します。 アルゴリズムは、中心にある船を見つける「確率」が最大であると判断し、そこに射撃しようとする場合があります（3つのうち1つ）。

確かに：



人にとって明らかな最適な戦術とは異なり、33％の確率のAIは、N番目の動きでA3を攻撃することにより、アプリオリに誤った決定を下します。 （N + 1）番目の移動（N番目の移動で成功した場合）では、誤った攻撃を50％の確率で実装できます（図では、2番目のスライドのA3への攻撃）。

mayorovpのメモとして、

最適なアルゴリズムは

1）近隣の制限を考慮に入れて、フィールドに1隻ではなく敵戦隊全体を配置する確率を計算する場合。

訓練中の競技場での船の不均等な分布への適応の弱さも注目されます。

2）敵が特定の対戦相手のために訓練するのではなく、最低確率の位置（たとえば、端）に敵が故意に配置し、最初のゲームで既に報復アクションを行うことができることを考慮します。

MichaelBorisov は、彼の研究「海戦をするためのボット：歴史、理論、実践」へのリンクを提供しています 。

残念ながら、私の「包括的な」アプローチは、現代のコンピューターでもすべての組み合わせを計算することは不可能であるという計算上の困難に陥りましたが、モンテカルロ法を使用して近似値を探すことしかできませんが、これはリアルタイムで困難であることが判明しました

zorge_van_daar は興味深い質問を提起します。敵の装備をすべて検出することがゲームの主な目標であり、検出後に破壊することができるため、終了する代わりに、新しい船の検索に切り替えることができますか？



limon_spbおよび他のユーザーの 十分に根拠のある アドバイスに よると、過度に 誇張された「最適な」特性が削除されました。 そのような声明は客観的な証拠を必要とするので、それは記事では与えられておらず、上記のおかげで与えることができません。