Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/85-964ebcc7

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

「艦これ」における遠征最適化問題の定式化

概要

 タイトルの通りです。
 『艦これ』を含めた海戦シミュレーションゲームにとって、艦隊を回すための資材運営(兵站)は重要な要素です。しかし、『どの遠征を回せば良いか』という問題は自明ではありません。そこで、整数計画問題への定式化を模索してみることにします。
注意:今回対象とするのは、『艦これ』やそれに類似したゲーム(『戦艦少女』など)における遠征最適化です。他の海戦ゲーに以下の議論は当てはまらない場合があります。


遠征システムのおさらい

 艦これにおける遠征の仕組みはざっと以下の通りです。

  1. 遠征用の艦隊を編成し、それを指定した遠征に出撃させる
  2. 遠征が成功すると、各種資材が備蓄に追加される
  3. 別の艦隊が同一の遠征に出撃することはできない
  4. 遠征の度に、艦隊の燃料・弾薬が消費されることがある
  5. 時間経過とともに、資材が自然回復することがある
  6. 獲得資材量を増やす手段として、キラ付けによる大成功・大発動艇の装備などがある(『戦艦少女』には存在しない要素)

 ルール1・ルール2は自明ですね。
 ルール3により、例えば『3艦隊全てを海上護衛に回す』といったことができなくなります。
 ルール4における消費量は、遠征毎に異なります(『戦艦少女』だと消費無し)。
 ルール5については、「最大備蓄可能各資材量」というパラメータが存在し、その量に達するまでは「燃料・弾薬・鋼材について+3/3分、ボーキについて+1/3分」のペースでじわじわと上がっていきます。一日にそれぞれ1440 or 480だけ回復するわけですね。
 ルール6についてですが、ざっくり纏めると「大成功すると1.5倍」「大発をn個載せると更に(1.0+n*0.05)倍」「改修したりすると更に増加(ややこしい式になる)」となります。主に、大量に資材が手に入る長時間遠征相手に用いられることが多いです。

 ちなみに『戦艦少女』の場合、ルール4・ルール6が存在しません。なので、誰を出撃させるか、何を持たせるかについては考慮する必要がありません……と言いたいところですが、遠征が大成功する確率が艦隊練度に依存する他、スキルによって大成功率が増やせたりするのでそちらの配慮が必要でしょうね。


定式化について

 まず、遠征のリストを用意します。遠征名を種類とし、資材の種類を種類とすると、『遠征を実行すると資材だけ手に入った』と表現できます。その際、『遠征を1回実行する時に掛かる時間』をとしておきます。
 次に、制約条件を考えます。遠征回実行するとすると、獲得できる資材となります。各資材がそれぞれ必要だったとすると、が全ての資材について成り立つ必要があります。
 さらに、最適化する目標を定めます。全体の遠征時間はとなります。もちろん複数艦隊(個)で同時に出撃すれば、全体の遠征時間をおよそ分の1まで縮めることができますが……。入れ子となる組み合わせ最適化問題はわざわざ解いてられませんので、ここではと近似します。

 ……実は、ここまでを整数計画問題として解かせると、例えば『短時間遠征1つだけを延々と周回する』といった不適切な解が出てきてしまいます。これは、艦隊を個フルに使うことが上記では考慮されないからです。もちろん、『が1以上かどうかを判定してその個数を数える』と言うのは不可能ではないかもしれませんがナーンセーンス!
 同一の遠征を複数艦隊が同時に行えない以上、総遠征時間の下界は『各遠征毎の総遠征時間の最大値』となります。つまり、とすると、が最小になればよいのです。除算を考慮するのは面倒ですから、現実的にはを最小化させた方が楽でしょう。これを定式化するには、『とを制約条件に加える』といったテクニックを用います。


まとめと宣伝


 結果的に、遠征の最適化問題を整数計画問題としてうまく落とし込むことができました。
 これを利用した自作ソフトウェアをGitHubで公開しています。

 →ExpeditionOptimizerへのリンク
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/85-964ebcc7

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

06 ≪│2017/07│≫ 08
- - - - - - 1
2 3 4 5 6 7 8
9 10 11 12 13 14 15
16 17 18 19 20 21 22
23 24 25 26 27 28 29
30 31 - - - - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数:
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。