お久しぶりです。arikaです。タイトルはカッコつけで英語になりました。

先日、wiztoolsにこんなツールを実装いたしました。その前にバグ直せとか言わない


魔道杯ポイント調整ツール : http://wiztools.net/tools/adjust_pt/


魔道杯でポイント調整をうまいことラクチンにこなすための計算を勝手にやってくれます。

これの技術的な背景とかについて書いていこうと思います。

 

そもそも、なにこれ?

ボード上には、ゾロ目調整をしたがるプレイヤーが極稀に生息しています。

しかし、冷静に考えてみてください。

 

どこで何ポイントもらえるか知ってますか?

 

もちろん、知らないと調整できません。
なんたって、1位は6000Ptとか6800Ptで、キリがいい数字だからです。

 

みなさんわかりましたか?わかりませんよね。
僕もカンニングしないとわからないです。
(ちなみに紹介した青北さんは、以前はフィーリングで調整してたとか…こわっ)

ポイントを把握してもそこで終わりではありません。
ポイント調整のために計算をやらなければいけません。魔道杯中に。
意外かもしれませんが、72時間弱ずっとゲームをやってきた人間にはただの算数も厳しいのです。

 

関連画像

イメージ図…と言いたいところだが、本当にこれぐらい知能が低下している

 

…という事情があり、長らくポイント調整は敷居が高いものでした。

それを改善するためのツールがこれ!というわけです。

揃えようね!

 

 

簡単に作れそうだけど…

結論から言いましょう。簡単に作れます。
ですが、何も知らないと厳しいかと思います。

似たようなツールを作りたい人向けに情報を書き残しておきますので、暇ならお読みください。

 

まずは理論から

簡単なケースから考えていきましょう。
イベ覇が1回6000Ptだった時、18000Pt稼ぐにはどうしたらいいでしょう?

簡単ですね。$$6000 \times 3  = 18000Pt$$ ということで、イベ覇を3回クリアすればいいわけです。

先ほどの例を踏まえてもう1個考えましょう。
イベ絶が1回3900Ptだった時、21900Pt稼ぐにはどうしたらいいでしょうか?

…これも難しくはありません。$$6000 \times 3 + 3900 \times 1 = 21900Pt$$ です。

 

このように、目標ポイントは「どこを」「何回」クリアしたかの合計を取ればいいことになります。これを小難しく数式で表すと

$$ P_{sum} =  \sum_{i} P_i C_i $$

となります。

さて、調整するにしてもクエストに挑戦する回数を多くしたくはありませんよね。つまり、先ほどの数式で言えば

$$  \sum_{i} C_i : Minimum $$

にしたい、という制約条件が課されます。めんどそうですね!

 

偉い人は難題を解決する方法を見つけました。「線型計画法(Linear Programming)」です。

今回のような場合はクリア回数は整数しかとれないので、「整数線形計画法」あるいは「整数計画法」となります。
英語で書くと「Integer Linear Programming」です。

つまり、この記事のタイトルは「整数線型計画法を使ってポイント調整」です!

最初から日本語で書け

 

で、具体的にどういう方法?

Wikipediaに丸投げします。僕は途中で読む気力がなくなりました。

 

glpk.js でお手軽導入

理論を知らなくてもどうにかできちまう方法があります。
他人の作ったものをパクればいいんです。

ここで、glpk.jsというJavascriptライブラリを使っていきましょう。 GPL-2.0 License なので注意してください。

どこかの紹介サイトにぶんなげたいところですが、素晴らしいことにドキュメントサンプルといったものが一切ないのでここで紹介します。
本当にもったいない…

 

概要

どういった計算を行うかを記した文字列を投げると、最適化された変数結果がObjectで返ってきます。

 

計算jobの記述方法

基本はLive Demoのサンプルを元に。まずはここで色々試すといいでしょう。
それぞれの意味を一つずつ推測で書いていきます(Documentないの頭おかしい)

計算目的指定

Maximizeなら最大化、Minimizeなら最小化。obj: の後ろに条件式を記述。
今回のポイント調整ツールの場合は

x1とかx2は操作する変数。今回の例で言えばCi(クエストクリア回数)に該当する。

係数を弄ることができるのがわかりやすいよう1を書いたが、これは省略できる。

 

推移条件指定

Subject To (改行) cap:まで必須。その後ろに推移条件を書く。
今回のポイント調整ツールの場合は

3900とか2200は言うまでもなく1回あたりの獲得ポイント数(Pi)である。
最後の8888888は取得したいポイント。

ここでは等式(=)だが、不等式ももちろんできる。

 

値条件指定

推移条件のところに書いてもいい気がするが、ここに書いたほうがわかりやすい。

今回の場合は、クリア回数が負数になることはありえないので全て0以上になるよう指定。

 

整数指定

ここに書いた変数は整数しかとれなくなる。

当然、クリア回数は整数しかとれないので全変数を記載。

最後に ENDを入れて、計算ジョブ文章は完成。

 

例えば

これは、8888888Pt取得する最小のx1~x14を返す計算ジョブとなります。

 

実行方法

まず、Workerサイドの動作を記述した以下のjsを保存して、参照できる範囲で置いておきます。
以下のリンクを右クリックすれば保存できるはずです。
これは公式のサンプルを少し書き換えCDN化してあるものです。

glpk_worker.js

 

あとは、こんな感じで実行すればOK。

 

結果

obj.resultはこんな感じで返ってきます。

あとはこれを加工すれば終わりです。

 

ね、簡単でしょ?