2013-12-23

モンスターハンタースキルシミュレータのアルゴリズム

mh programming

この記事はモンハン Advent Calendar 2013 23日目のエントリーです。

こんにちわ！kudzuです。よろしくっく！
MH4用のスキルシミュレータのMH4スキルシミュ（泣）*1や、お守りスナイプ用のウェブページ*2とかを作ってます。

現在HR289で、好きな武器はライトボウガンです。たまに近接で大剣や片手を使うことはありますが、大体ライトボウガンかヘビィボウガンを使うことが多いです。

MH3Gでは水冷と麻痺が速射できるイケメンのガノシュトロームが愛銃でしたが、今作は属性速射と麻痺速射が使える銃が大きく減った上に、高レベルギルクエの状態異常耐性の上昇率の高さのせいで、麻痺速射が大幅に弱体化してしまい、大変がっかりしてしまいます。
MH4では、普段は烈日やブリザードタビュラを担いでいます。後はラージャン狩りにアイルーヘルドール。あまり使いませんが、ダークデメントや鬼ヶ島も大好きです。
あまり使う人を見ないですが、ライトボウガンは速射、リミカ、サポと、プレイスタイルが幅広い上に、納刀(納銃？)も素早いので、戦闘中に罠や閃光玉なども織り交ぜやすく、機動力が高く、立ち回りがしやすく、ヘビィほどではありませんが、火力も十分高く、とても面白い武器です。
貫通しゃがみヘビィをお使いの方は、増弾リミカタビュラを是非お試しください。フルリロードからの立ち貫通弾20連発は大変爽快です。

スキルシミュレータのアルゴリズム

前置きはこのくらいにして、MH4スキルシミュ（泣）の中のアルゴリズムを少し紹介したいと思います。

MH4の防具は、各部位に300+の装備があり、それに加えて、お守りという、コンピュータで網羅するにも禿げ上がるような組み合わせの数があります*3。それにくわえて、今回開発したシミュレータは、携帯上のJavascriptで動かさなくてはいけないため、デスクトップアプリの十倍くらいのハンデがあります*4。

そんなわけで、一層高速に探索ができるアルゴリズムが必要なわけですが、速度を上げるために、false-negativeが出てしまうと、「このシミュレータはこの装備の組み合わせが出ないぞ！」という話になってしまい、信用がなくなってしまうので、ヒューリスティックを元にアグレッシブな最適化を行うことはできません。

そこで、組み合わせの数を最小限に抑え、枝刈りを保守的に最大限に行い、条件がきついものは枝刈りで素早く結果を出し、条件が緩いものは、最大結果件数で切り上げることで、ある程度実用性がある感じの時間で結果を出すようにしています。

装備の組み合わせを見つける処理はざっくり５つのステップで行われています。

フィルタリング
グルーピング
装備のスコアリング
装備の選択
装飾品の選択

フィルタリング

まず要求された条件に関係ない防具を除外します。
例えば女性であればアーク一式は装備できなく、逆に男性はフィリアが装備できないので、除外します。他にも剣士・ガンナーの装備の除外、進行度による除外、固定装備・除外装備などの設定を元に、探索対象となる装備を選びます。

グルーピング

残った防具の中から、要求されたスキルポイントの値とスロットが同じものは、組み合わせを減らすために、一つの防具としてまとめます。
例えば切れ味+1で検索した場合、クロオビメイルとアカムトウルンテは両方共匠+2、スロット1なので、同じ防具として扱っても大丈夫なわけです。
同様に、胴系統倍加の防具や空きスロット1-3の防具もまとめられています。

装備のスコアリング

ここからが重要です。
探索を枝刈りするためには、枝刈りするための指標が必要となります。
自分がとったアプローチは、装備にスコアをつけ、スコアの高いものから防具を試し、足りないスキルと、残っている防具のスコアを元に、枝刈りを行うというアプローチです。枝刈りの仕組みについては後で説明します。

スコアの付け方ですが、検索対象となるスキルが装飾品でスロット数いくつ相当か、ということになります。
先ほどの例の切れ味+1とクロオビメイルでは、クロオビメイルは匠+2で、匠+2は匠珠(3)相当なので、3スロット分の価値があり、かつ空きスロットが1あるため、合計4ポイントとなります。

匠珠(2)と匠珠(3)のように、いくつかスキルポイントの設定が異なる装飾品がある場合、スキルポイントごとのスロット数が低いものを採用します。なので、匠+1の防具は、本当は匠珠(2)相当の2スロットですが、ポイントは3 / 2の1.5となります。

装飾品がない潔癖などのスキルポイントは1ポイントあたり100という扱いにすることで、真っ先にそのスキルを持つ防具を試すように作ってあります。何故か剣士の検索してるのに、頭がガンナーばっかりという時は、大抵ガンナー頭のほうがスキルポイントが多めにあるため、優先的に試された結果、検索結果の最大件数全てガンナー頭になってしまった、ということです。

装備の選択

スコアにもとづき、一番スコアの高いものから順番に総当りで試していきます。
まずトリッキーなのは、胴系統倍加。これは胴の防具が選ばれたら順番に空いてる部位に胴系統倍加防具を試しはじめるという仕組みになっています。

そしてこのアルゴリズムで最も重要な枝刈りですが、

足りないスキルポイントのスロット数換算 > 空いている装備のスロット数 + (今選んだ防具のポイント * あと装備できる箇所の数)

となります。わかりにくいので、もう少し例を出しながら説明すると、回避性能+3のスキルをつけるべく、回避性能のスキルポイントを20集めようとした時、防具はスコアが高いものから順番に試されます。
お守りも含めて4つの防具を装備して、スキルポイント10と2スロットがあるとすると、残り２つと空きスロットでで10ポイント相当をカバーしなくてはいけません。2スロットは回避性能+3ポイント相当なので、残り2つの防具で回避性能+7を加えなくてはいけません。試している順番はポイントが高い順なため、次に選ぶ防具が回避性能+3スロット0だった場合、これより後に回避性能+3スロット0より高性能な防具がないことがわかっているため、足りない回避性能4ポイントは絶対に埋めることができない、ということがわかります。ここで枝刈りを行います。
先ほどの数式をこの例で書くと、

2 / 3 * 10 > 2 + (n * 2)
20 / 3 > 2 + (n * 2)
14 / 3 > (n * 2)
7 / 3 > n

と、次の防具が最低2と1/3ポイントの防具でないと無理だということがわかります。回避性能+3は2ポイント相当なので、無理だということがわかります。

そして、逆に

足りないスキルポイントのスロット数換算 <= 装備のスロット数

を満たした場合、装飾品を埋めることで要求スキルを満たすことができるかもしれないので、装飾品を試し始めます。

装飾品の選択

装飾品を試すのは、比較的簡単で、

胴系統倍加がある場合、胴をまず埋める
スキル系統ごとにスロット数が最も高い(コストの高い)スキルから試す
- 満たせないことが早い段階でわかりやすい
同じスキルポイントの装飾品は、スロット数が多いものから試す

という感じで、唯一トリッキーなのは、どの装飾品をどのスロットにはめるかということで、例えば空きスロットが3と2だった場合、1スロの装飾品はどこにはめるべきかでしょうか？3にはめた場合、2-2となり、3スロの装飾品を試せなくなり、２にはめた場合、3-1となり、2スロの装飾品を一つしか試せなくなります。
で、どうすればいいかというと、新しい装飾品を試すたびに、今まで選んだ装飾品を見て、新しい装飾品のスロット数のものを一番多くはめるにはどうすればいいかを計算しなおします。
計算式は1スロは超単純で、空きスロを数えればいいです。3スロはまず丁度いいサイズのスロットを全部埋めて、その後は優先的に2スロを埋めて3スロをあけるようにします。2スロが若干面倒で、同じく丁度良いサイズを全部埋めた後に、3スロに1スロの装飾品をはめて2スロに変換した上で、余った1-2スロの装飾品を*5埋める感じになります。

以上がMH4スキルシミュ（泣）の仕組みでした。

実は頑シミュさんもアルゴリズムを公開しているのですが、そんなことは知らずに自分で作り始めたので、全体的なアプローチが異なっています。もしご興味がある方はこちらも御覧ください。色々と組み合わせるともっと速くなるかもしれません。

次回はyoruakiさんの「地雷について考えます」です。おつかレイア

*1:なんでこんな名前かというと、シミュレータスレの79番だったから

*2:こっちは306番とかだった気がするけど、別に特に名前つけてない

*3:昔は20分かかる検索があったとか。参照：http://www.geocities.jp/masax_mh/logic/page3_hone.html

*4:参照：http://sealedabstract.com/rants/why-mobile-web-apps-are-slow/。シミュレータでも十倍かは不明だけど間違いなく遅い

*5:3スロの装飾品は3スロ以外でははまらないため、ちょうどいいサイズの空きが必ずあるはず

2013-10-31

モンハン4闘技大会

そういやモンハン４の話はブログには書いてなかったけど、どちらかというとこっちに書いたほうがいい気がするからこっちに書いていこう。

今日二人で闘技大会埋めてって、とりあえずイヤンクックとケチャワチャ以外はAとって*1、Sもザボアザギルで出せた。二人でやればAは全く難しくはないんだけど、いくつか楽になりそうなポイントを。

アルセルタスとゲネル・セルタスはアルセルタスは多分再生しない。
ザボアザギルのSは余裕っぽい(後述)
ティガレックスの片手は高耳に加えて、回転する攻撃が見てからガードが間に合うので楽。火力はないかも。
- Ｓは5:30で、太刀使いと二人でやって5:52だった。その後もう１回やったけど、6分越えた。
ジンオウガ亜種は笛とハンマーでやったけど、完全に失敗だった気がする
- 両方共火力低い上、麻痺ハンマーが竜やられと相性悪すぎる
イビルジョーは慣れないスラッシュアクスを持ってハンマー使いと行ったけど、9:30いけた。8:00がSだから、割と楽かも
レイア・レウス同時は分断さえできれば難しくない。
グラビモス二種は撃龍槍当てて、虫棒でぴょんぴょん飛びながら同士討ち狙えば楽。棒初めて使ったけど、それでも余裕なくらい楽だった。

で、Sランクの勲章のためにザボアザギルを何度もやった。4:30でSのところを大剣*2で最初から4:43で、あとちょっとでいけるんじゃないか、と色々武器変えたりして試したりしたけど、結局は大剣*2で3:30くらいで倒せた。工夫したのは本当に開幕だけで、後は割といつも通りにやって、一発で1:30くらい短くなった。多分乗った回数も1-2回だったと思う。

大剣二名
飯食わずに左側から入場。ザボアザギルの後ろから入場になる
ダッシュで近づけば気付かれずに溜め開始できる
耳栓あるから、溜め3→横打ち→強溜め3→強薙ぎ払いまでが叩き込める
すぐ氷がつく

それまでは氷がつくまでそこそこ時間があったけど、この開幕手順だと、最初に相当なダメージを叩き込めるから、後は抜刀→納刀で普通に立ちまわって、乗った後は溜め3→横切り→強溜め3→強薙ぎ払い、という感じでSいけると思う。

*1:相手がすでにこの２つAとってたから飛ばした

2013-08-04

新サーバー

linux

新しいサービス用にもう一つサーバー借りた。
http://d.hatena.ne.jp/kudzu/20120402/1333378708を参考にセットアップ中。

まずは普通に使うツールをインストール
- emacs
- screen
- sudo
  - adduser kudzu sudo
サーバ・サービス類
- nginx
- mysql-server
- django

python周りをインストール中。

$ sudo pip install cheetah simple-json feedparser twisted pyrss2gen PIL pngcrush

mysqldbだけはpipからインストールできん。あとimagemagickとpngcrushも駄目だった。そもそもこれって本当にpythonモジュールか？

pipでgcc走るやつで、Python.hが足りないので、libpython-devを追加
追加で必要なモジュールは幸いfabricにメモしてたので、さらに選んでみる。

$ sudo pip install uwsgi django hatta couchdbkit

aptにsupervisordないや、と思ったらsupervisorだった。
アップデートしたらcouchdbが動かず。

{"init terminating in do_boot",badmatch,{error,{{app_would_not_start,ssl}....

どうやら6月のdebianのerlangのアップデート(testingかexperimentalのどっちかしらないけど)でcouchdbが壊れているっぽいことが判明。https://issues.apache.org/jira/browse/COUCHDB-1833
しょうがないから今のうちにubuntuに変えることに決定。
couchdbがようやく動いたけど1.0系。debianは1.2だから動くか心配。
replicationをhttp://guide.couchdb.org/draft/replication.htmlにしたがって行う。

2013-06-27

女神転生４

game

真・女神転生IV (2013年5月23日発売) - 3DS

出版社/メーカー: アトラス
発売日: 2013/05/23
メディア: Video Game
クリック: 28回
この商品を含むブログ (85件) を見る

女神転生４結構進んだ。今LV50後半くらい。

最初の方は経験値の補正が厳しくて、LV上げが無茶苦茶辛かったけど、LV20くらいからは出現する敵のほうがLV上ばっかりで、超経験値入りまくる割には全然LVが追いつかないという不思議な状態に。
悪魔の交渉も、LV20辺りからは、失敗すると全滅する危険が無茶苦茶高いので、ターゲットを残して残りを掃討しなくちゃいけないんだけど、二体残ってターンが回すと、普通に全滅する。ベノンザッパーで何度カロンさんに挨拶することになったことか...。あと高HPの悪魔と低HPの悪魔が混ざると低HPの悪魔だけ残すのが至難の業。そういう時は数を減らすのを諦めて、テトラカーン張って交渉で切り抜ける。

仲魔のHPとMPが、大雑把に高HP/低MP、中HP/中MP、低HP/高MPみたいな感じで、高いのと低いのでは倍以上違う。MP低いと、スキルが全体的にコストが無茶苦茶高くて、あっという間にMP切れて木偶の坊になるし、HP低いと通常攻撃二回で沈むというジレンマ。

相手にターンを渡すと全滅するのがごく当然で、通常攻撃があんまり強くないから、雑魚相手にもスキルを中心に全力で攻撃しないといけない。だからスキルを連発するために高MPを優先してる。LV30になってLV5の雑魚に全滅させられそうになるゲームってどうなんだよ、とちょっと思うけど。

で、高MPの悪魔揃えても、スキルのコスト高いから、すぐMP切れる。必然的に全ての悪魔に吸魔かエナジードレインをつける。あとチャクラウォークも同時につけたりする。これで雑魚戦は火力全開で戦える。先制攻撃くらうと相変わらず全滅するけど。なんだこのゲームバランスは。

じゃあ１ターンで勝負がつかないボス戦はどうするのよ？というと、普通に持久戦に持ち込むと全滅する。というか、2-3ターン目辺りに結構死ぬ。最初の頃は弱点をつける構成で、捨て身のゴリ押しで切り抜けてきた。テトラカーンを手に入れた辺りからはずっと反射無双で、パーティ三名が反射魔法と吸魔・エナジードレインを持って、交代で反射し続けてる。反射は耐性無視という仕様はどうなのよ？とも思うけど、せっかくだから使うことにしてみた。まだ幸い万能系魔法を中心に攻めてくるボスがいないので、ダメージソースの7割以上を反射にしてると思う。なんか全然違うゲームである。

アバタールチューナーも反射じゃないけど、属性無効のバリア張ってターンを奪うっていうのが結構重要な要素であったし、こういうゲームもありなのかな、と思えてきた。

テトラカーン・マカラカーンは最初はコスト重すぎだろ、と思ってたけど、2人でローテーション組めるくらい吸魔でMPを吸えるので、それほど気にならない。テトラカーンはまだしも、マカラカーンは万能過ぎなので、属性ごとの反射ができるもう少し軽量な反射魔法があってもゲームが面白くなったかもなぁ、と思った。

2013-04-10

djangoで独自の認証つきadminページの追加

programming

調べても、ほとんどModelからAdminページを作る話ばかりで、完全にカスタマイズされたページで、認証だけ流用したい、という用途においては全然参考になるコードがなかったので、一応記録しておく。
http://docs.djangoproject.jp/en/latest/ref/contrib/admin/index.html
のAdding views to admin sites辺りにチラっと書いてあるんだけど、これだけじゃただurl追加しただけだった。

https://github.com/django/django/blob/master/django/contrib/admin/sites.py

のget_urlsの実装を見ればわかるけど、実際のページの処理をする関数に対して認証ページのwrapperをかけてる。

wrapする関数自体は直接触れないので、しょうがないからコピペしてみた。

class MyAdmin(admin.AdminSite):

    def get_urls(self):
        def wrap(view, cacheable=False):
            def wrapper(*args, **kwargs):
                return self.admin_view(view, cacheable)(*args, **kwargs)
            return update_wrapper(wrapper, view)

        patterns = super(MyAdmin, self).get_urls()
        patterns += urls.patterns(
            '',
            urls.url(r'^edit/$', wrap(self.editPage), name='edit'),
            )
        return patterns

urlpatternの登録は以下のとおり。

adminSite = MyAdmin()
urlpatterns = urls.patterns(
    '',
    urls.url(r'^admin/', urls.include(adminSite.urls)),
    )

これで、/admin/edit/などのページを開くと、ユーザ名を聞くようになる。

テンプレート側は、

{% extends "admin/base_site.html" %}

{% load i18n admin_static %}

{% block content %}
...
{% endblock content %}

こんな感じで見慣れたadminページのヘッダが表示される。

2012-11-29

San MateoのDMVで実技試験受けてきた

11:15にドライビングスクールのおっさんに拾ってもらって、しばらく練習して、13:00くらいに書類提出。車を実技試験の待機エリアに停車して、しばらく待って、ようやくお姉さんが出てきてテスト開始。

出発前に手信号やライトの確認などから。3つ間違えるとそこで終了。エンジンをつけるのに手間取って死ぬほどあせったけど、流してくれたっぽい。

運転に関しては、公式ビデオが結構わかりやすいので、必ず目を通したほうがいいと思う。
https://www.youtube.com/playlist?list=PL297E87DA9A1025B2

あと、色々日本語のブログを見たけど、スコアの基準が何も書いてなかったから、せっかくだから、ここに書いてみる。本当に正しいかはわからないけど、スコアシートにはそう書いてあるから、多分正しいと思う。
一発終了の項目は上のリンク先のビデオに大体載ってるので、そちらを見てもらうとして、それ以外は1ミスあたり減点１？で、合計15個ミスするとアウト

以下が減点項目。

Intersection (8個)
- Through
  - Traffic check
  - Speed
  - Yield
  - Unnecessary stop
- Stop
  - Traffic check
  - Deceleration/Braking
  - Full stop
  - Gap or Limit line
- Start
  - Traffic check
  - Yield
  - Speed
Business/Urban And Residential Rural(2個 B/R)
- Traffic check
- Speed
- Spacing
- Lane Position
Lane Change(2個 L/R)
- Traffic Check
- Signal
- Speed
- Spacing
- Steering control
Turns(LeftとRight各4個)
- Approach
  - Traffic check
  - Signal
  - Deceleration/Braking
  - Yield
  - Lane use
  - Unnecessary stop
- Stop
  - Traffic check
  - Full stop
  - Gap or Limit line
  - Wheels straight
- Turn/Complete
  - Traffic check
  - Yield
  - Steering control
  - Too wide/short
  - Correct lane
  - Speed
  - Signal

普通にこの項目をひと通り意識してやれば15個間違えられるので、1発アウトに比べると比較的ゆるい。
ただ、どれかの項目をどの場面でも失敗すると、あっという間に15になるかも。例えば、遅すぎるのは減点になる*1ので、それを知らないと、Intersectionで-8、Business/Residentialで-2、Lane Changeで-2、Turnsで-8になって-20になってしまうこともありうるかもしんない。

「試験官は君に免許をとってもらいたいと思ってるんだから、気を楽にして行くといいよ」と言っていたけど、普通にひっかけ問題*2を出してきて、このクソババァ！と思った。幸いあらかじめ教わっていたから問題なかったけど。

結果は、減点7で無事通過。減点されたのは、十字路での安全確認不足で3点、車線変更で3点、バックをまっすぐにできなくて1点。

後はまた最初の書類提出と同じ窓口にまで戻って、免許をもらう手続き。また紙の仮免をもらって、本物は後日郵送。大体全部終わったのが1:45くらいだった。

今回車の練習をお願いしたのは
http://www.yelp.com/biz/guerrero-driving-school-san-francisco
のおっさん。料金が若干安めだけど、しっかりやってくれたし、アメリカにしては珍しく、時間通りちゃんと来る。よく喋るおっさんだから、英語でしゃべるのがしんどい人にはおすすめしない。

*1:法定速度-10mph?

*2:2車線で、右車線に変更するように言われて、右車線は右折のみなんだけど、曲がれとは言われない。右折のみだから曲がるのが正解。