チャのブログ

ゲームか情報処理に関すること等を気が向いたら書きます

地下大洞窟におけるおすすめ努力値振りスポット

ポケモンBDSP

BDSP は金策が簡単なのでドーピングがメジャーな努力値の振り方だと思うが、複数ポケモンに一斉に振りたい人やレベリングを並行したい人向け。

特定のタイプの出現率アップの石像を置くことで、倒したときに特定のパラメータの努力値がもらえるポケモンのみが出やすくなるパターンの中から抜粋した。

一覧

HP

地下水脈の空洞 / でんき

草原の空洞 or 陽だまりの大空洞 / エスパー

攻撃

地下水脈の空洞 / あく

河岸の空洞 or 水鏡の大空洞 / ドラゴン

防御

広めの空洞 or 輝きの空洞 or 星影の大空洞 / ドラゴン

マグマの空洞 / いわ

吹雪の空洞 or 氷柱の空洞 or 氷河の大空洞 / いわ

岩石の空洞 or マグマの空洞 or 熱砂の空洞 or 断崖の大空洞 or バクフーの大空洞 / どく

マグマの空洞 or 熱砂の空洞 or バクフーの大空洞 / むし

岩石の空洞 / ひこう

特攻

マグマの空洞 or 熱砂の空洞 or バクフーの大空洞 / あく

輝きの空洞 or 星影の大空洞 / ほのお

輝きの洞窟 or 星影の大空洞 / いわ

特防

地下水脈の空洞 / こおり

吹雪の空洞 or 氷柱の空洞 or 氷河の大空洞 / フェアリー

素早さ

輝きの空洞 or 星影の大空洞 / でんき

輝きの空洞 or 星影の大空洞 / かくとう

輝きの空洞 or 星影の大空洞 / むし

吹雪の空洞 / あく

まとめ

あくタイプの石像を常設しておけば ACS の3カ所が振れるので、ぶっぱするならあくポケモンを倒しつつパワー系アイテムで HBD を振るのがおすすめ。

なみのりが必要なチョンチー, ランターンは効率が悪いので、BD ではできるだけパワーウエイトを活用したほうが良い。

ダイパリメイクにおける効率の良い化石の掘り方を遺伝的アルゴリズムで調べた

ポケモンBDSP アルゴリズム 遺伝的アルゴリズム

はじめに

もしあなたが実際にゲームをプレイする際の効率化を求めてこの記事にたどり着いた場合、おそらく最後まで読んでも有益な情報は手に入りません。

化石堀りとは

「ポケットモンスター ブリリアントダイヤモンド・シャイニングパール」で実装されているミニゲームで、これをすることでポケモンの化石や石像、伝説のポケモンに会うために必要なアイテムを手に入れられるという要素。

適当な攻略サイトを以下に貼るので詳細はこちらで。

【ポケモンダイパリメイク】化石の掘り方と知っておくべきこと | BDSP - 神ゲー攻略

解決したい課題

化石掘りは上記のサイトでも説明されている通り、ハンマーとピッケルを使い分けて壁を壊していき、アイテムを露出させることで手に入れることができるというルールである。

しかし壁を叩ける回数には上限があるため、少ない回数でアイテムを発見する必要がある。

手法

叩けるマスが130個、叩ける回数が最大50回あり単純な全探索は難しいので、遺伝的アルゴリズムで最適解に近い解を探す。（上手く最適化すれば全探索できるかもしれないが面倒だった。）

遺伝子構造

各遺伝子は長さ50の行動の配列で構成されていて、行動は「どこを叩くか」と「ハンマーとピッケルのどちらで叩くか」の2つの情報を持つ。

評価関数

最小のアイテムは2*2の大きさを持っている。また各マスは耐久値が6段階（0から5とする）あり、0まで破壊することでアイテムが露出するが、1でもひび割れからそのマスにアイテムがあるかを知ることができる。

よって評価値は2*2の範囲108通りのうち、最小の耐久値が1以下であるものの数とした。

結果

赤い印がハンマーで叩くべきところ、青がピッケルで叩くべきところ。

f:id:charines:20211218180645j:plain

ゲーム画面に計算結果をマーキングしたもの

遺伝子長は50だが、今回は25回叩いた時点で評価値が最大となった例を挙げる。

初期値が耐久度2の土の座標を叩いているのは2か所で、耐久度の高いマスから叩いていく方が無駄がないことが読み取れる。

しかしそれ以外の規則性を見出すのは難しかった。

実際にマーキング通りに叩くと以下のようになった。

f:id:charines:20211218181550j:plain

計算通りに壁を叩き終えたもの

任意の2*2の範囲で、耐久度が2（ひびの入っていない土）以上のマスのみの範囲が存在しないことがわかる。

この壁に埋まっているアイテムは2つだったので、中央やや上の緑のタマと中央下の箱で全て。

この後この2つのアイテムを壁が崩れる前に掘り出すことができた。

問題点

ひび割れだけではアイテムを見つけられない可能性がある

以下は最小のアイテムの一つが埋まった2*2の範囲である。

f:id:charines:20211218182024p:plain

埋まったみどりタマS

もし左上のマスの耐久度が高くても、この範囲で最小の耐久値は左下の1なので、評価関数ではプラスになるが、左下のマスのひび割れからここにアイテムが埋まっていることを判別するのはほぼ不可能と言える。これはこのアイテムが下側が細いいわゆる"逆三角形"のような形をしているからである。（どうでもいいけど、どういう角度だろうと三角形は三角形だし逆とかないだろとは思う。）

この問題を回避するには評価関数を改善する必要がある。

アイテムを掘り出せない

今回はアイテムが2つの壁だったためどちらも掘り出すことができたが、アイテムが4つの壁だと、すべてのアイテムを掘り出す前に壁が崩れそうである。

この問題を回避するには、世代数を増やすなどしてより効率の良い解を探すか、見つけたアイテムを掘り出すごとに再計算して、掘り出す過程を含めた最適解を探す必要がある。

正直どんなにうまくやっても、ある程度は運が絡むくらいのレベルデザインにはなってそう。

リポジトリ

https://github.com/hylian-flute/bdsp-fossil

複数のテキストを入力するフォームの調査

Web

入力フォームの分類

HTMLの入力フォームを

  • 値を自由記述するか選択するか
  • 値が単数か複数か

の2つの軸で分類して、4パターンのUIについて考える。

自由記述で単数

<input type="text"> や <textarea>

f:id:charines:20211107160838p:plain

input

f:id:charines:20211107160908p:plain

textarea

選択で単数

<input type="radio"> や <select>

f:id:charines:20211107161151p:plain

radio

f:id:charines:20211107161246p:plain

select

選択で複数

<input type="checkbox"> や <select multiple>

f:id:charines:20211107161407p:plain

checkbox

f:id:charines:20211107161619p:plain

select multiple

自由記述で複数

上記の3パターンは使用すべき要素が決まっており、実際にどのWebサイトでも多少デザインの差異があるとはいえ、類似したUIが使用されていると言えるだろう。

しかしこのパターンについては単体で要件を満たす要素がなく、各Webサイトで独自の実装がされているのではと考えた。そこでこのパターンについて、どのような実装が存在するかを調査する。

調査

Google検索

自由記述の項目を複数入力するフォームとして、最もなじみ深いのは検索エンジンだろう。Googleのはじめほぼ全ての検索エンジンでは、一つのinputに単語をスペース区切りで入力する方式である。

f:id:charines:20211107162256p:plain

Google検索 ( www.google.com )

ただしこれは検索クエリにおける AND の代わりにスペースを使えるというだけなので、厳密には複数の値を入力するためのフォームとは言えないかもしれない。

はてなブログ

はてなブログでは記事にタグをつける機能がある。単語を入力してEnterで確定すると、その単語がタイル化し、次の単語を入力できるようになる。入力済みの単語を削除するにはタイルの×ボタンをクリックする。

この方式は他のブログサービスでも使われているほか、メールアプリで送信先メールアドレスを指定するときなどにもよく使われている。

f:id:charines:20211107163310p:plain

はてなブログ ( blog.hatena.ne.jp )

調整さん

日程調整ツールとして有名な「調整さん」は、候補日時を一つのテキストエリアに改行区切りで入力していく。また入力の補助として、入力欄右側のカレンダーをクリックすることで自動入力が可能。入力済みの候補日を消したり、時刻を変更するには直接テキストエリアを編集する必要がある。

改行区切りのテキストエリアは、簡易的なルーレットやくじ引きのWebアプリなど、手軽さが求められるサービスでよく使われているイメージ。

f:id:charines:20211107164641p:plain

調整さん ( chouseisan.com )

Googleフォーム

Googleフォームの作成画面で、ラジオボタンやチェックボックスなど選択式の設問を設定する場面では、常に「選択肢を追加」というプレースホルダーが設定された入力欄が最下部にあり、入力を始めると新しく入力欄が追加される。既存の項目を削除するには×ボタンを押す。

はてなブログ形式と似た操作感だが、一つ一つの項目が長文でも見やすくなっている感じがする。

f:id:charines:20211107170704p:plain

Googleフォーム ( www.google.com/intl/ja_jp/forms/about/ )

ちなみにGoogleフォームでチェックボックスの設問に回答するとき、「その他」を選択つつ自由記述ができる場合があるが、なぜだか複数の「その他」を使うことはできない。

結論

調査と銘打って記事を書き始めたものの、そんなに多様なパターンは見つけられなかった。一つ一つの項目が長いか短いか、リッチなUIを作りたいか手早く実装したいかの2軸によって選択すると良さそうな感じがする。

他にもこういうUIを知ってますという方がいれば是非教えてください！

Web Workerを複数使えば行列計算は速くなるのか

Web

はじめに

JavaScriptの非同期処理はシングルスレッドで行われるため、並列処理によって計算を高速化することはできません。一方でWeb Workerを使うことで並列処理を実現できます。

developer.mozilla.org

そこでWeb Workerを複数使うことでどの程度並列処理による高速化ができるかを試しました。

計算内容

2つの正方行列の積を求めます。N行N列の正方行列同士の積を最も単純な方法で求めると計算量はO(N3)です。これを(N/M)行N列の行列とN行N列の正方行列の積を求める、計算量O(N3/M)の計算M個に分割して、Web Workerで並列処理を行います。

今回はN=103、1 <= M <= 16の条件で速度を計測します。

環境

Windows10、AMD Ryzen 7 3700X 8コア、Google Chrome 85

結果

M 実行時間(ms)
1 9107
2 5894
3 3769
4 3055
5 2650
6 2345
7 2078
8 2204
9 2165
10 2126
11 2214
12 2210
13 2078
14 2073
15 2095
16 2111

f:id:charines:20200905170946p:plain

M = 7が最も速かった

結論: Web Workerを複数使えば行列計算は速くなる

ソースコード

main.js


async function main() {
  const N = 10 ** 3;
  const [matrixA, matrixB] = [...new Array(2)].map(
    () => [...new Array(N)].map(
      () => [...new Array(N)].map(() => Math.random())
    )
  );

  for (let m = 1; m <= 16; ++m) {
    const workers = [...new Array(m)].map(() => new Worker("./worker.js"));
    const asyncWorks = workers.map(
      worker => (...args) => new Promise(
        resolve => {
          worker.onmessage = resolve;
          worker.postMessage(args);
        }
      )
    );

    const promises = asyncWorks.map(
      (asyncWork, i) => asyncWork(
        matrixA.slice(Math.floor(i * N / m), Math.floor((i + 1) * N / m)),
        matrixB
      )
    );

    const startTime = new Date().getTime();

    const resMessages = await Promise.all(promises);
    const ansMatrix = resMessages.reduce(
      (concated, message) => concated.concat(message.data),
      []
    );

    const endTime = new Date().getTime();
    console.log(`m: ${m}, Time: ${endTime - startTime}ms`);
  }

}

main();

worker.js


addEventListener("message", message => {
  const [slicedA, matrixB] = message.data;

  const ansMatrix = [];
  slicedA.map(row => {
    const ansRow = [];
    for (let columnIdx = 0; columnIdx < row.length; ++columnIdx) {
      ansRow.push(
        row.reduce(
          (sum, valueA, i) => sum + valueA * matrixB[i][columnIdx],
          0
        )
      );
    }
    ansMatrix.push(ansRow);
  });
  postMessage(ansMatrix);
});

SAWの音圧を上げてノリノリにする

DTM アルゴリズム

DTMerの多くはコンプレッサー等で波形を潰して音圧を上げることが大好きです[要出典]。そこでSAW（のこぎり波）を音色を損なわずに音圧を上げる方法を考えます。

 音圧の高さとは実効値の大きさと言えるでしょう。実効値の計算式は以下の通りです。

\textrm{RMS}=\sqrt{\frac{1}{N}\Sigma x(t)^2}

tは時刻、 x(t)は時刻 tでの信号の強度を表します。例えば振幅1の矩形波は x(t)^2が常に1なので \textrm{RMS}=1です。

ところでSAWは以下のように正弦波に分解できることが知られています。

x_\textrm{saw}(t)=\Sigma\frac{1}{k}\sin(kt)

つまりSAWは n倍音の振幅が基音の 1/nであるような正弦波の重ね合わせです。ここでヒトの聴覚は位相に鈍感であるという性質を利用して、倍音ごとに異なる位相の正弦波を重ね合わせることを考えます。こうすることによって、ほとんど音色を変えずに音圧を変えられるはずです。

アルゴリズム

[0, 2\pi)の範囲の値を持つ位相の配列 pをいくつか生成し、以下のように波形を合成します。

x_\textrm{saw}(t)=\Sigma\frac{1}{k}\sin(kt+p_k)

この波形はSAWと位相のみが異なり周波数成分は同じであるため、ほぼ同じ音色に聞こえるはずです。これを振幅が1になるように正規化してから実効値を計測し、もっとも音圧が高くなった pを求めます。 pの生成は単純なランダム生成で行います（遺伝的アルゴリズムも試したがあまり上手くいかなかった）。

結果

pの次元数を25に設定して実行したところ、最も実効値の高い波形は以下のようになりました。

f:id:charines:20190823232922p:plain

左は実際の波形、右は周波数スペクトルを表し、青い線がSAW、オレンジの線が生成した波形です。どちらも25倍音までの正弦波の重ね合わせるで生成されているため、SAWが完全な直線にはなっていないことに留意してください。実効値はSAWが0.496に対し生成した波形は0.682と音圧が高くなっています（理想的なSAWの実効値は \sqrt{3}^{-1}\simeq 0.577）。周波数スペクトルはほぼ同型ですが少しギザギザになってしまいました。

実際にこれらを880Hzで鳴らした時の音声は以下の通りです。

SAW 生成した波形

音量が上がった様に聞こえますが音色も若干変わってしまった気がします。

まとめ

今回は pがランダム生成なので最適解ではないですが、ある程度音圧を上げることには成功しました。しかしもっと綺麗な波形が生成されると予想していたのですが、ここまで歪な形になってしまったのは意外でした。DTMerの方々は今回の結果を参考に(?)是非ノリノリな音色づくりに励んでみてください。

おまけ

三角波で同様にやってみました。

f:id:charines:20190823235427p:plain

実効値は0.584（理想的には \sqrt{3}^{-1}\simeq 0.577）から0.806に増加しました。

三角波 生成した波形

SAWのときより綺麗な波形になりました。

メガリザードンXとYをベイズ推定する

ポケモンUSUM アルゴリズム

リザードンといえば初代御三家の一匹で、対戦においてもポケモンUSUMのシングルレート環境において常に使用率上位に君臨する人気ポケモンです。

リザードンは禁止伝説のミュウツーを除けば唯一2つのメガシンカを持つポケモンであり、見せ合い時点で全く性質の異なるXとY両方の対策を相手に強要することは大きな強みとなっています。

逆にリザードン入りパーティを相手にするときは、相手のリザードンがどちらにメガシンカするかを予測することが重要で、人気実況者のライバロリさんも過去にポケモンだいすきクラブへの寄稿記事として「メガリザードンXとYの見分け方！」という記事を書いています。

www.pokemon.jp

ここではポケモングローバルリンク（PGL）のデータを使って、あるポケモンがパーティに入っているとき、一緒に入っているリザードンがどれくらいの確率でXまたはYなのかをベイズ推定します。

結果だけ見たい人はこちら 

ステップ１

今回はデータ収集の容易さからQRレンタルチームを使うことにしました。検索ページで「どうぐ」にリザードナイトを指定して結果を表示します。

f:id:charines:20190605022803p:plain

3ds.pokemon-gl.com/rentalteam/usum/search より

必要なのは緑枠内の「対戦に使われた回数」と「リザードン以外のポケモン」です。これをそれぞれのリザードナイトで50パーティずつ集めました。

またレーティングバトルのページでシングルレートにおけるリザードンの持ち物の割合を調べます。結果はリザードナイトXが53.7%、リザードナイトYが46.3%でした。この割合はシーズンによって変動しますが概ねXが50%〜55%程度です。（リザードナイトXとリザードナイトYの割合を足すと100%になるように正規化しています）

ステップ２

 メガリザードンXもしくはYがパーティに入っているときに、あるポケモンが同じパーティに入っている確率P(p_i|x),P(p_i|y)を求めます。xは「メガリザードンXがパーティに入っている」yは「メガリザードンYがパーティに入っている」、p_iは「ポケモンiがパーティに入っている」です。

具体的な操作としては、P(p_i|x),P(p_i|y)を0で初期化し、ステップ１で調べた50個ずつのパーティを順に見ていって、ポケモンiが入っていれば(\textrm{対戦に使われた回数})\times(\textrm{50パーティの対戦に使われた回数の合計})をP(p_i|x)またはP(p_i|y)に足していきます。

ステップ３

次にリザードン以外の各ポケモンがパーティに入っている確率P(p_i)を求めます。当然ですがメガリザードンが入っていないパーティは考慮する必要がないので、これはP(p_i)=P(p_i,x)+P(p_i,y)=P(p_i|x)\times P(x)+P(p_i|y)\times P(y)

で求められます。ステップ１よりP(x)=0.537,P(y)=0.463です。

ステップ4

最後にあるポケモンがパーティに入っているときに、メガリザードンXもしくはYがパーティに入っている確率P(x|p_i),P(y|p_i)を求めます。ベイズの定理よりP(x|p_i)=\frac{P(p_i|x)P(x)}{P(p_i)}です。P(y|p_i)も同様に計算できますが、メガリザードンが入っているパーティのみを考慮しているのでP(y|p_i)=1-P(x|p_i)です。

結果

各ポケモンに対する、P(x|p_i)を以下の表に示します。ただしP(p_i)が低いデータは信頼性に欠けるためP(p_i)\le0.05のものは排除しています。

f:id:charines:20190605033437p:plain

上の方のポケモンと一緒に入ってるほどXの確率が高い

考察

最初に紹介した「メガリザードンXとYの見分け方！」でも紹介されていた有名な判別方法として「でんきタイプに弱そうなパーティのリザードンはX」というものがありますが、実際にメガリザードンXが電気弱点のアシレーヌ・テッカグヤ・パルシェンと同時に採用されやすいことがわかります。メガリザードンYと一緒に採用されやすい電気弱点は、そもそも耐久の低いゲッコウガと、リザードンとは同時選出のされにくいギャラドスだけです。

 意外なのはカバルドンで、カバリザYが有名な並びなのにカバルドンと一緒に採用されるリザードンはXの方が多いという結果になりました。

 しかし、そもそもリザードンの「一緒に手持ちに入れられているポケモンTOP10」にすら入っていないルカリオが41.85%で採用されているとなっている辺り、QRレンタルチームから収集したこのデータが実際のシングルレート環境と合っていないことは明らかです。

まとめ

ベイズ推定は手法としては有効かもしれませんが、PGLのデータのみから推定を行うのは無理がありそうです。結局は対戦を重ねて経験を積むしかないのかもしれません。