ニューラルネットワークはDotaを演じます

みなさんこんにちは！ 実際、ニューラルネットワークはおなじみのDota 2ではなく、RussianAICup 2016 CodeWizardsでプレイします。 RussianAICupは、人工知能プログラミングの年次オープン競争です。 このコンテストへの参加は非常に興味深いです。 今年、テーマはDotaに似たゲームでした。 私はしばらくの間強化でトレーニングしてきたので、これをRussianAICupで適用したいと思いました。 主な目標は、ニューラルネットワークにこのゲームをプレイすることを教えることでしたが、もちろん賞品を獲得することは素晴らしいことです。 その結果、ニューラルネットワークは約700箇所になります。 競争の制限のため、これは悪くないと思います。 この記事では、競争そのものよりも強化学習とDDPGおよびDQNアルゴリズムに焦点を当てます。



この記事では、ニューラルネットワークに関する基本的な情報については説明しませんが、インターネット上にはニューラルネットワークに関する情報が大量にあるため、この出版物を膨らませたくはありません。 ニューラルネットワークを使用した強化学習、つまり、試行錯誤によって目的の動作を実証するために人工ニューラルネットワークをトレーニングする方法に焦点を当てたいと思います。 2つのアルゴリズムの説明を簡略化します。2つのアルゴリズムには1つのベースがあり、適用分野はわずかに異なります。

マルコフ状態

入力では、アルゴリズムはエージェントSの現在の状態を使用します。ここでは、状態にマルコフプロパティがあること、つまり、可能であればシステムの次の状態を予測するために必要なすべての情報を含めることが重要です。 たとえば、地平線に対して斜めに投げられた石があります。 石の座標を状態としてとると、これ以上の挙動を予測することはできませんが、石の速度ベクトルを座標に追加すると、この状態により、石のさらなる軌道全体、つまりマルコフが予測できます。 状態に基づいて、アルゴリズムはアクションAに関する情報を提供します。これは、最適な動作、つまり報酬の量を最大化するような動作を保証するために実行する必要があります。 R賞は、アルゴリズムのトレーニングに使用する実数です。 報酬は、エージェントが状態Sにあり、アクションAを実行し、状態S 'に入った瞬間に発行されます。 トレーニングのために、これらのアルゴリズムは、過去に何をしたか、結果は何であったかについての情報を使用します。 経験のこれらの要素は、4つのコンポーネント（S、A、R、S '）で構成されています。 このような4つを一連の経験に入れ、それらをトレーニングに使用します。 記事では、リプレイバッファという名前が付いています。

Dqn

または、Deep Q-Networksは、 Atariがゲームをプレイするように教えられたまさにそのアルゴリズムです。 このアルゴリズムは、制御コマンドの数が厳密に制限されている場合、およびAtariの場合はジョイスティックボタンの数に等しい場合（18）に設計されています。 したがって、アルゴリズムの出力は、Qのすべての可能なアクションの推定値のベクトルです。ベクトルのインデックスは特定のアクションを示し、値はこのアクションがどれだけ良いかを示します。 つまり、最大評価のアクションを見つける必要があります。 このアルゴリズムは1つのニューラルネットワークを使用し、その入力にSをフィードします。アクションインデックスはargmax（Q）として定義されます。 ベルマン方程式を使用してニューラルネットワークをトレーニングします。これにより、ニューラルネットワークの出力が、将来の報酬の量を最大化する動作を実装する値に収束することが保証されます。 この場合、形式は次のとおりです。





これが解読されると、次のことがわかります。

1. N個の経験要素（S、A、R、S '）のパケット（ミニバッチ）を取得します（例：128要素）
   
   
2. 各要素について、考慮します
   
   
   
   y = R +γ* _{すべてのA 'の}最大（Q ^過去 （S'、A '））
   
   
   
   γは割引係数で、間隔[0、1]の数値であり、将来の賞の重要性を決定します。 通常、一般的な値は0.9〜0.99の範囲で選択されます。
   
   
   
   Q ^過去はニューラルネットワークのコピーですが、後方学習の反復（たとえば100または1000）がいくつかあります。このニューラルネットワークの重みを定期的に更新するだけで、トレーニングは行いません。
   
   
   
   Q ^past =（1-α）* Q ^past +α* Q
   
   
   
   α-更新レートQ ^過去 、標準値0.01
   
   
   
   このトリックにより、アルゴリズムの収束が改善されます。
   
   
   
   
3. 次に、ミニバッチの損失関数を考えます
   
   
   
   L = _{ミニバッチの要素}上のΣ（y-Q（S、A）） ² / N
   
   
   
   二乗平均平方根誤差を使用する
   
   
4. Lを使用してお気に入りの最適化アルゴリズムを適用する
   
   
5. ニューラルネットワークが十分に学習するまで繰り返します
   
   

ベルマンの方程式をよく見ると、現在のアクションが実行された後に可能なすべての後続アクションからの報酬の加重合計によって現在のアクションを再帰的に推定することがわかります。

DDPG

またはDeep Deterministic Policy Gradientは、制御コマンドが連続アクションスペースからの値である場合に作成されるアルゴリズムです。 たとえば、車を運転するときは、ハンドルを特定の角度だけ回すか、アクセルペダルを特定の深さまで押します。 ハンドルの回転とアクセルペダルの位置には、理論的には無限に多くの値があります。そのため、現在の状況に適用する必要がある非常に具体的な値をアルゴリズムに提供してほしいです。 したがって、このアプローチでは、2つのニューラルネットワークが使用されます。μ（S）は、コンポーネントが対応する制御信号の値であるベクトルAを返すアクターです。 たとえば、マシンのオートパイロットの3つの要素（ステアリング角度、ガスペダル位置、ブレーキペダル位置）のベクトルです。 2番目のニューラルネットワークQ（S、A）は、状態SでのAのアクションの推定値であるqを返す批評家です。批評家は、俳優を教育するために使用され、ベルマン方程式を使用してトレーニングされます。









評論家は評論家Q（S、μ（S））の勾配から俳優の重みで学習します







この復号化が取得された場合：

1. N個の経験要素（S、A、R、S '）のミニバッチを取得します
   
   
   
   
2. y = R +γ* Q ^過去 （S '、μ ^過去 （S'））
   
   
   
   Q ^過去 、μ ^過去はDQNの場合と同じトリックであり、現在はこれらは2つのネットワークのコピーです
   
   
   
   
3. 損失関数を考慮します
   
   
   
   L = _{ミニバッチごとの} Σ（y-Q（S、A）） ²
   
   
   
   
4. Lを使用して批判を訓練します
   
   
5. アクターの重み勾配∇Q（S、μ（S））をお気に入りの最適化アルゴリズムで取得し、それを使用してアクターを変更します
   
   
6. 目的に達するまで繰り返します
   
   

ロシア語

今、私は競争のために訓練したエージェントについてお話します。 興味があれば、 ここで詳細なルールを読むことができます。 メインページでビデオと説明を見ることもできます 。 競技会には2種類のゲームがあります。1つ目は、10のウィザードの1つを戦略でコントロールする場合です。 次に、戦略が5人のウィザードのチームを制御する場合、同時に相手は5人のウィザードの反対側のチームを制御します。 戦略に利用できる情報には、すべての友好的なウィザードの範囲内にあるすべてのオブジェクトが含まれ、残りのスペースは戦争の霧で覆われています。

• ウィザード
  
  
• 手先
  
  
• 建物（タワーと基地）
  
  
• 木々
  
  
• ボーナス
  
  
• 貝殻
  
  

ユニットには、それ自体に関する次の情報が含まれる場合があります。

• 座標
  
  
• ヒットポイントの数
  
  
• マナ量
  
  
• 次のストライクまでの時間
  
  
• 他のパラメーター、多数あり、ルールには完全な説明があります
  
  

ローカルシミュレーター（KPDV上にあります）を使用して、自分自身または2人の組み込みの対戦相手に対して戦略を追跡できます。非常に単純な戦略です。 まず、問題を真正面から解決しようとすることにしました。 DDPGを使用しました。 私は世界について利用可能なすべてのパラメーターを収集しましたが、それらは1184であり、入力のために提出されました。 私の方法は、13の数字のベクトルであり、直接および横方向の移動速度、回転、さまざまなタイプの攻撃、および発射範囲などの攻撃パラメーター、一般に存在するすべてのパラメーターを担当しました。 開始に対する報酬で、私は賢くないことも決めました、ゲームはXPの量を与えるので、XPの増加に対して肯定的な報酬を与え、ヒットポイントの減少に対して否定的な報酬を与えました。 しばらく実験を重ねた結果、この形式ではニューラルネットワークの感覚をつかむのが非常に難しいことに気付きました。 そのため、ニューラルネットワークのタスクを簡素化する必要があると判断しました。



まず、状態を再構築して、受信したすべての情報のコレクションだけでなく、制御されたウィザードからの循環レビューの形式で表示されるようにしました。 円形のレビュー全体が64のセグメントに分割され、このセグメント内の4つの最も近いオブジェクトが各セグメントに分類されます。 友軍ユニット、中立ユニット、敵ユニット、および移動する場所を示すために、このような循環レビューが3回ありました。 その結果、さらに多くのパラメーター-3144を取得しました。また、正しい方向、つまり敵基地への経路に沿って移動することに対する報酬を与え始めました。 円形ビューにはオブジェクトの相対位置に関する情報が含まれているため、畳み込みネットワークを使用してみました。 しかし、何もうまくいきませんでした。 ウィザードは、わずかな知性を垣間見ることなく、1か所で回転しました。 そして、しばらくの間、ニューラルネットワークのトレーニングに関する情報を読み、インスピレーションを得ようと試みました。



しばらくしてから、すでに刺激を受けた実験に戻り、学習速度を1e-3から1e-5に減らし、入力パラメーターの数を714に大幅に減らし、同時に情報処理のプロセスを高速化するために一部のデータを拒否しました。 また、動きと回転だけにニューラルネットワークを使用することを決定し、手動で指定された単純な戦略のために射撃を残しました。射撃できる場合は、最も弱い敵に向けて射撃します。 そのため、トレーニングには十分に難しいが、照準と射撃のタスクを簡単に処方できるように、ニューラルネットワークから削除しました。 そして、彼は前進と後退のかなり難しい形式化されたタスクを残しました。 その結果、通常の完全に接続されたネットワークのインテリジェンスが垣間見えるようになりました。 しばらくの間（実験のためにGeForce GTX 1080で数日）トレーニングし、良好な制御品質（ネットワークが組み込みの対戦相手に勝った）を達成したので、私はネットワークをサンドボックスにアップロードすることにしました。



Tensorflowからネットワークウェイトをアンロードし、hファイルとしてハードコーディングしました。 結果は数十メガバイトのアーカイブであり、サンドボックスはダウンロードの最大ファイルが1 MBであると言って、それを受け入れることを拒否しました。 ニューラルネットワークをさらに削減し、トレーニング、ハイパーパラメーターの選択、1 MBのアーカイブサイズへの適合に多くの時間（約1週間または数週間、正確には覚えていません）を費やす必要がありました。 そして、最後にもう一度ダウンロードしようとすると、解凍されたアーカイブの制限は2 MBであり、4 MBでした。 Facespalm。 嵐のような気持ちを乗り越えて、私はニューラルネットワークをさらに絞るようになりました。 その結果、次のアーキテクチャに刺されました。

394 x 192 x 128 x 128 x 128 x 128 x 6
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

394は入力層であり、reluは最後から最後から2番目を除くすべての層で使用され、最後から2番目のタンではアクティベーション関数として使用されます。後者では、通常、アクティベーション関数はありません。 このフォームでは、コントロールはあまり良くありませんでしたが、知性を垣間見ることができるので、決勝戦が始まる数時間前にこのオプションをダウンロードすることにしました。 マイナーな改善により、彼はまだランク付けで約700の場所でサンドボックスでrussianaicup.ru/profile/Parilo2をプレイしています。 一般的に、私は現時点で結果に満足しています。 以下は、1x1マッチの例のビデオです。私の戦略は、5人のウィザードのチーム全体を制御します。

競争改善の提案

競争に参加することは非常に興味深いです。 ローカルシミュレーターの形のパンがあります。 いくつかの形式の変更を提案したいと思います。 つまり、サーバー上で実行されるのはサーバー部分と評価テーブルのみで、クライアントはインターネットを介してサーバーに接続し、戦いに参加します。 したがって、サーバーから負荷を削除するだけでなく、戦略のリソース制限を削除できます。 一般に、これはStarcraft 2や同じDotaなどの多くのオンラインゲームで行われます。

コード

エージェントコードはgithubで入手できます。 管理とトレーニングの両方にC ++で使用されます。 トレーニングは、TensorFlowに依存する別のWizardTrainerプログラムとして実装されます。戦略は、ネットワークを介してトレーナーに接続し、そこで環境を破棄し、そこから実行する必要のあるアクションを受け取ります。 彼女はまた、得られたすべての経験をそこに送ります。 したがって、複数のエージェントを1つのニューラルネットワークに接続し、すべてを同時に管理できます。 組み立てるのは簡単ではありません。必要に応じて、どのように尋ねます。

資源

強化学習、これら、およびその他のアルゴリズムの詳細については、David Silverの優れたGoogle DeepMind コースをご覧ください。 スライドはこちらから入手できます 。

DDPGおよびDQNによるオリジナル記事。 私はそれらから式を取りました。



最後まで読んでくれてありがとう。 知識の道で頑張ってください！



PS数式のサイズをおforびします。小さくなりたくないので、プリントスクリーンでそれを上書きしました。