risk game ai agent
1.0.0
リスクは、2〜6人のプレーヤーの外交、紛争、征服の戦略ボードゲームです。ターンは、他のプレイヤーからの領土を捕らえようとするピースを演奏する軍隊を制御するプレーヤーの間で回転し、結果はサイコロロールによって決定されます。ゲームの目標は、ボード上のすべての領域を占有し、そうすることで他のプレイヤーを排除することです。各ターンは2つのアクションで構成されています。
このプロジェクトの目的は、ルールにいくつかの変更が加えられたリスクゲームを実装し、ゲームを適切にプレイできる人工的にインテリジェントなエージェントを設計することでした。プレイヤーまたは他のエージェントプレイヤー。
ゲームは、Javaプログラミング言語を使用して実装されています。ターンを制御し、プレーヤーを要求したアクションを要求し、ゲームマップを更新し、ルールに従ってすべてが起こっているかどうかを確認することは、コードのこの部分が行うことです。ゲームUIは、マップを描画する.FXMLファイルを介して設計されており、プレーヤーをゲームのロジックに接続するプラットフォームです。
このセクションでは、ゲームリスクの強力なAIにつながるヒューリスティックの実装と評価に焦点を当てています。
実装は、Minimax Alpha-Beta Pruningアルゴリズムに基づいています。プレーヤーは、DFSアルゴリズムに基づいて予測ツリーを構築します。
エージェントのプレイの番であるときはいつでも、木が作られます。ツリーノードはゲームの状態（その状態のゲームのマップ）であり、各エッジは、マップの攻撃状態から現在の状態から作られた攻撃の可能性です。攻撃アクションは、開始およびターゲットの領土の座標と、攻撃軍にいるように選択されたユニットの数で構成されています。ルートノードは、プレーヤーが移動するマップの現在の状態です。ただし、ツリーは、メモリと時間の制限が許可しない各状態でプレイヤーが持つことができる多数の可能性のある動きのために、ゲームの終了状態まで予測することはできません。したがって、プレイヤーは、コードで定義した特定の深さまでツリーを構築できます。また、エージェントのゲーム戦略の特定の部分にいくつかの単純化が適用されていますが、これは次のセクションで説明します。可能な限り最良の決定を下すために、ヒューリスティックは、その状態に到達する量がプレーヤーにとって有益であることを評価する可能性のある最も深いノード（木の葉）に対して定義されます。このヒューリスティックについては、レポートでさらに説明する予定です。葉の値が決定されると、ツリーはMinimax Alpha-Beta Pruningに渡され、このよく知られているアルゴリズムは、プレイヤーが持つことができる最高のアクションのシリーズを見つけます。
領土にユニットを供給することは難しい作業です。攻撃力を改善したいだけでなく、攻撃の危険にさらされている領土に十分な防御力があることを確認します。敵の領土に隣接する国にユニットを展開することは、これら2つの目標のバランスを保つための賢明な方法である可能性があります。
ドラフト単純化：
予測ツリーに可能なすべてのドラフトシナリオを予測し、含めることは、前述の問題に直面する複雑なツリーにつながります。したがって、単純化の1つは、常に可能な限り最良の結果をもたらすことが証明されている起草ヒューリスティックを使用し、敵がこのアプローチをドラフトすることでも予測することです。言い換えれば、予測ツリーを形成する可能性として起草の結果を削除し、それらを決定的なドラフトシナリオに変更します。
そうするために、次の手順を実行します。
ドラフトヒューリスティック：
ステップ1：
国Xに隣接する敵国のすべてのユニットの合計を採用すると、Xで国境警備脅威（BST）と呼ばれる措置が与えられます。
ステップ2：
このBSTをXに位置するユニットで除算すると、すべての国境国で比較できる国境セキュリティ比（BSR）が得られます。
BSRが高い国は、隣接する敵国の敵ユニットの数は、国自体のユニットの数よりも比較的高いため、敵のプレイヤーによって征服される可能性が高くなります。供給するために高いBSRを持つ国を選択すると、BSRを下げることで防御力が高まります。 BSRが低い国にユニットを供給することは、すでにより良い防御的な姿勢を持っていることを意味し、攻撃力を高め、これらの国からの攻撃を成功させる可能性を高めます。
ステップ3：
BSRを所有するすべてのBSRの合計で除算することでBSRを正規化すると、誰かがユニットを配置できる直接的な測定値が得られます。正規化された国境セキュリティ比（NBSR）は、次のように計算されます。
これは、ユニットを国にどのように分配できるかの直接的な比率を示しています。この時点で、一部のデータは無関係であり、すべての領土にユニットを追加したくないため、この比率に問題があることがわかります。降順の順序（防衛力の強化に重点を置いています）、データを中央から分割し、下半分の数値をゼロに設定します。
ステップ4：
ステップ4は、利用可能なユニットが追加されなくなるまで継続されます。
ツリーを複雑にしないようにするために、攻撃段階にいくつかの単純化が適用されているため、より深いレベルを予測できます。これは、どの攻撃シナリオが戦闘に勝つ可能性が高く、ツリーにのみ含めるチャンスが高いかを確認することで実行できます。
その特定のプレーヤーにとって、木の葉がどれほど有益であるかを評価するため。後で説明するヒューリスティックの学習中に可能な限り最高の重みが見られる4つのヒューリスティックな特徴を定義しました。すべての機能は、ゼロから1の間の結果を返します。これは、機能が互いに密接な比率で評価されると、学習と割り当ての重量がより正確になるためです。
機能は次のとおりです。
前のパートの各ヒューリスティックに重みを与えることは、エージェントがゲームに勝つためにそれぞれがどれほど重要かつ影響力があるかを評価するのに役立ちます。これらの重みを見つけるプロセスは、遺伝的で学習することです。各遺伝子は、これらの4つの機能の4つの重みのセットです。まず、範囲で100セットのランダムウェイトを生成することから始めます[0,10]。その後、10トーナメントが発生します。トーナメントごとに、プライマリ集団の10個の遺伝子がランダムに選択されます。遺伝子のすべての可能なペアが互いに対戦し、各トーナメントの各ゲームの結果を文書化します。フィットネス関数は、各遺伝子の（勝利数 /ゲーム数）として定義されます。各トーナメントの3つのトップ遺伝子（フィットネス関数に基づく）が選択されるため、30のトップ選択された遺伝子があります。これらの中で、12のランダムペアを選択し、各ペアに対して、遺伝子のペアの平均重量を計算することにより新しい遺伝子を作成しているクロスオーバーを実行します。したがって、このクロスオーバーから12個の新しい遺伝子があります。一方、3つの遺伝子は、私たちが持っていた30の遺伝子内でランダムに選択され、それぞれの1つのランダムな重みを別のランダムな重量に変更することにより変異します[0,10]。結局のところ、私たちは現在、一次集団に入れられる15の真新しい遺伝子を持っています。この時点で、第2世代の遺伝子が生成されます。このプロセスは、遺伝子の生成4が生成されるまで繰り返し続けます。その集団の上位遺伝子は、エージェントがプレイするために使用するヒューリスティックの特徴のための最高の重みとして選択されます。
