完成品どーん
作りたいもの
キッカケ
ワイ「TRPGおもろいなぁ」
ワイ「特にこのログ・ホライズンTRPGっちゅうのはワイのお気に入りやな」
～～～ある日のこと～～～
ワイ「この攻撃力が45+10D1の技と31+15Dの技はどっちが強いんじゃろか」
ワイ「期待値計算すると、、、、80と83.5か」
ワイ「じゃあ後者の技の方が強いんやな！」
～～～セッション当日～～～
ワイ「うりゃ！31+15Dじゃぁ！喰らえ！」
ワイ「あれ？たったの53？弱すぎひん？」
ワイ「もう1回じゃぁ！」
ワイ「70！？」
ワイ「この技使い物にならんわ」
ワイ「なんで期待値があんな高かったのにこんな弱いんや！」
思ったこと
- ダイスの期待値を計算するのがめんどい
- でも期待値だけじゃ測れないので、期待値だけじゃなくて信頼区間も欲しい (でも手計算は死ぬ)
じゃあ自分でサービスを作ればいいじゃない！
実装する機能
ダイスの期待値を計算するだけのツールだと味気ないのでいろいろ機能を足すことに。作りたい機能をまとめたのが以下。
- ダイス予測
- ダイスの期待値・分散・標準偏差・信頼区間・範囲あたりを計算する
- 入力は
1+2Dとか1d100*1d20みたいな感じ
- ダイスロール
- BCDice使ってダイスを振る
- Saipage的なのが作りたい
- CCFOLIA出力
- CCFOLIAのClipboard APIを使ってキャラ情報からJSON形式で出力できるツール
- 読み込みも対応させる
使う技術スタック
プラットフォームは慣れてるのでWebを使う。Next.js+Reactを基調に慣れてるものを多く使った。今から考えればもう少し新しい技術に触れてもよかったかなと思う。
- Next.js
- React
- Tailwind CSS
- Peggy
Peggyだけが新しく触れた技術。パーサージェネレーターという構文解析を簡単に行えるようにするライブラリの1つ。jsで使えるなかで一番メジャーそうだったので使うことにした。
開発開始
開発を始めたのが6/5。そこから1週間ぐらいでリリースまでたどり着いたわけだが、それを機能ごとに分けて説明していこうと思う。
ダイス予測
ダイスを含んだ計算式に対して期待値などを計算するツールなので、まずはダイスを含んだ計算式を解析しなければならない。ここでPeggyが活躍する。
Peggyの基本
PeggyはPEGというパーサージェネレーターのjs版みたいなもので基本的にPEGと同じ感じで書ける。まずは四則演算を計算する公式サンプルを見てみよう。
// Simple Arithmetics Grammar
// ==========================
//
// Accepts expressions like "2 * (3 + 4)" and computes their value.
Expression
= head:Term tail:(_ ("+" / "-") _ Term)* {
return tail.reduce(function(result, element) {
if (element[1] === "+") { return result + element[3]; }
if (element[1] === "-") { return result - element[3]; }
}, head);
}
Term
= head:Factor tail:(_ ("*" / "/") _ Factor)* {
return tail.reduce(function(result, element) {
if (element[1] === "*") { return result * element[3]; }
if (element[1] === "/") { return result / element[3]; }
}, head);
}
Factor
= "(" _ expr:Expression _ ")" { return expr; }
/ Integer
Integer "integer"
= _ [0-9]+ { return parseInt(text(), 10); }
_ "whitespace"
= [ \t\n\r]*
基本はこれと同じなのでこのサンプルをこねくり回すことにした。分解して見ていこう。
Expression
= head:Term tail:(_ ("+" / "-") _ Term)* {
return tail.reduce(function(result, element) {
if (element[1] === "+") { return result + element[3]; }
if (element[1] === "-") { return result - element[3]; }
}, head);
}
これは<Term> + <Term> - <Term>...みたいな構文を取り出すという意味。Peggyでは{}の中に普通のjsが書けるので、returnで何を返すかを決めている。ここではそれぞれを足したり引いたりしたものを返している。
Term
= head:Factor tail:(_ ("*" / "/") _ Factor)* {
return tail.reduce(function(result, element) {
if (element[1] === "*") { return result * element[3]; }
if (element[1] === "/") { return result / element[3]; }
}, head);
}
これは<Factor> * <Factor> / <Factor> ...みたいな構文を取り出すという意味。これもまた計算結果をreturnで返している。
Factor
= "(" _ expr:Expression _ ")" { return expr; }
/ Integer
これは( <Expession> )のような構文あるいは数字を取り出すという意味。PEGにおいて/はでなければという記号。例えばA / BならAにマッチするならA、でなければBという具合。2つ以上繋げて使うこともできる。
Integer "integer"
= _ [0-9]+ { return parseInt(text(), 10); }
_ "whitespace"
= [ \t\n\r]*
最後に、この部分はInteger(数字)と_(ホワイトスペース)の定義をしている。今までの構文の中にところどころ_が出てきていたが、これは中にスペースが混在していても正しく解析できるようにこういう工夫をしているというわけだ。
どうしてこれで四則演算の解析ができるのだろうか？ExpressionはTermの組み合わせで構成され、TermはFactorの組み合わせで構成されている。つまりExpressionを解析するより先にTermが、Termより先にFactorが解析されるというわけだ。これによって()の中は優先しつつ掛け算・割り算が足し算・引き算より優先される四則演算が実現できる。
細かい部分はガッツリ端折って説明してしまったが、詳しく知りたい人は下の記事なんか読んでみるといいだろう。
抽象構文木(AST)を作る
結構長々とPeggyについて説明してしまったが、実はそこまで詳しく知らなくてもダイスを含んだ式は解析できる。
ここまで「解析」という単語を漠然と使ってきたが、具体的にどういうことなのかを考えてみようと思う。実際のプログラミング言語の解析は以下のようなステップで行われる。
- 字句解析 (文章→トークン)
- 構文解析 (トークン→抽象構文木)
- セマンティック解析 (抽象構文木→実行できる形式)
これをダイス予測の機能に置き換えてみると
- 字句解析 (ダイスを含んだ式→トークン)
- 構文解析 (トークン→抽象構文木)
- セマンティック解析 (抽象構文木→期待値・信頼区間など)
となる。
こうやってPeggyでは上2つの字句解析と構文解析をやって、抽象構文木を出力してからセマンティック解析を頑張ろうという方針で行くことにしました。
そしてできたものはこちら。
Expression
= head:Term tail:(_ ("+" / "-") _ Term)* {
return tail.reduce((result, element) => {
return {
type: 'operator',
operator: element[1],
left: result,
right: element[3]
}
}, head);
}
Term
= head:Factor tail:(_ ("*" / "/") _ Factor)* {
if (tail.length === 0) return head;
return tail.reduce((result, element) => {
return {
type: 'operator',
operator: element[1],
left: result,
right: element[3]
}
}, head);
}
Factor
= "(" _ expr:Expression _ ")" { return expr; }
/ Dice
/ Integer
Dice "dice"
= _ [0-9]+ [Dd] [0-9]* {
const input = text();
const parts = input.split(/d/i);
return {
type: 'dice',
dice: parseInt(parts[0], 10),
sides: parseInt(parts[1] || '6', 10),
}
}
Integer "integer"
= _ [0-9]+ {
return {
type: 'number',
value: parseInt(text(), 10)
}
}
_ "whitespace"
= [ \t\n\r]*
さっきのものをちょっと改造しただけ。変わった点は
-
Integer、_の他にDiceというトークンが増えた - それらが値の代わりにオブジェクトを返すようになった
-
ExpressionとTermが計算するのではなくオブジェクトを返すようになった
の3つ。これだけで抽象構文木が作れちゃうのだ。
例えばこのパーサーに2+2D+4という入力を与えると
{
type: "operator",
operator: "+",
left: {
type: "number",
value: 2
},
right: {
type: "operator",
operator: "+",
left: {
type: "dice",
dice: 2,
sides: 6
},
right: {
type: "number",
value: 4
}
}
}
という抽象構文木が得られる。これで解析できる形になった。
セマンティック解析
最終的に計算したい値は期待値・分散・標準偏差・範囲・信頼区間の5つ。ただ信頼区間を正確に求める方法が思いつかなかったのでとりあえず正規分布に近似させることに。誰か数学に詳しい人教えて欲しい！標準偏差は分散から求められるので求めるべき値は期待値・分散・範囲の3つということになる。
operatorの計算
抽象構文木の中のtype: "operator"の部分を解釈していくことが大事になってくる。そこで登場するのが高校数学である。数学って便利だね。
期待値・分散
期待値と分散の定義
E(X) = \sum_{k=1}^n{p_kx_k} \\
V(X) = \frac{1}{n}\sum_{k=1}^n{(x_k-\bar{x})^2}
定数aに対してこんな公式が成り立つ
E(X+a) = E(X) + a \\
E(aX) = aE(X) \\
V(X+a) = V(X) \\
V(aX) = a^2V(X)
また確率変数X,Yが無相関の時は以下の公式も成り立つ
E(X±Y) = E(X) ± E(Y) \\
E(XY) = E(X)E(Y) \\
V(X±Y) = V(X) + V(Y) \\
V(XY) = V(X)V(Y) + {E(X)}^2V(Y) + {E(Y)}^2V(X)
振るダイスは全て独立なので2これらの公式はもちろん成り立つ。(積の分散は複雑なので教科書には載っていないが)
と、ここまで考えて一つ気付いた。商の期待値・分散の計算ができないことに。もちろん一般的な公式がないというだけでゴリ押しすれば計算できないこともないのだが、、、今回は諦めることにした。アプデで実装されるかもしれないしされないかもしれない。
範囲
期待値・分散に比べれば範囲の計算はわりあい簡単だ。範囲を求めるには最大値と最小値がわかればいいので四則演算それぞれに対して最大値・最小値を考えると次のようになる。
\max(X+Y) = \max(X) + \max(Y) \\
\min(X+Y) = \min(X) + \min(Y) \\
\max(X \times Y) = \max(X) \times \max(Y) \\
\min(X \times Y) = \min(X) \times \min(Y) \\
\max(X-Y) = \max(X) - \min(Y) \\
\min(X-Y) = \min(X) - \max(Y) \\
\max(X \div Y) = \max(X) \div \min(Y) \\
\min(X \div Y) = \min(X) \div \max(Y) \\
式の意味はいたって簡単。足し算・掛け算はそのまま、引き算・割り算は入れ替えるだけ
Dice, Integerの扱い
type: "operator"を扱うには両辺の期待値・分散・範囲がわかっている必要がある。
Integer
定数なので期待値はその値、分散0、範囲はその値だけ(最小値も最大値もその値)になる。
Dice
nDr(r面ダイスをn回振る)の場合について考えると
\begin{align}
E(X) &= n \times \frac{1}{r}\sum_{k=1}^{r}{k} \\
&= \frac{1}{2}n(r+1)
\end{align} \\
\begin{align}
V(X) &= E(X^2) - {E(X)}^2 \\
&= \frac{1}{6}n(r+1)(2r+1) - \frac{1}{4}n(r+1)^2 \\
&= \frac{1}{12}n(r+1)\bigl\{2(2r+1)-3(r+1)\bigr\} \\
&= \frac{1}{12}n(r^2-1)
\end{align}
となる。
これらをすべて踏まえてセマンティック解析を実装したのが次の例。
const resolveNode = (AST: diceAST): resolvedDiceAST => {
if (AST.type === 'operator') {
const left = resolveNode(AST.left);
const right = resolveNode(AST.right);
return {
type: 'resolved',
mean: calcOperator[AST.operator](left.mean, right.mean),
variance: (() => {
const LV = left.variance;
const RV = right.variance;
if (['+', '-'].includes(AST.operator)) {
// V(X+Y)=V(X)+V(Y)
return calcOperator[AST.operator](LV, RV);
} else if (AST.operator === '*') {
// V(X*Y)=V(X)*V(Y)+E(X)^2*E(Y)+E(Y)^2*E(X)
return LV * RV + left.mean ** 2 * RV + right.mean ** 2 * LV;
} else {
if (LV * RV === 0) {
return LV || RV;
} else {
throw new Error('cannot divide by dice roll');
}
}
})(),
range: (() => {
const minmax = [
calcOperator[AST.operator](left.range.min, right.range.min),
calcOperator[AST.operator](left.range.min, right.range.max),
calcOperator[AST.operator](left.range.max, right.range.min),
calcOperator[AST.operator](left.range.max, right.range.max),
];
return {
min: Math.min(...minmax),
max: Math.max(...minmax),
};
})(),
};
} else if (AST.type === 'dice') {
const mean = (AST.dice * (AST.sides + 1)) / 2;
const variance = (AST.dice * (AST.sides ** 2 - 1)) / 12;
const range = {
min: AST.dice,
max: AST.dice * AST.sides,
};
return {
type: 'resolved',
mean,
variance,
range,
};
} else if (AST.type === 'number') {
return {
type: 'resolved',
mean: AST.value,
variance: 0,
range: {
min: AST.value,
max: AST.value,
},
};
} else {
throw new Error('unknown AST type');
}
};
6/15 追記
コードを一部修正
@Nabetani さんありがとうございましたreturn { min: calcOperator[AST.operator](left.range.min, right.range.max), - max: calcOperator[AST.operator](left.range.min, right.range.max), + max: calcOperator[AST.operator](left.range.max, right.range.min), };6/16 追記
コードを一部修正
diffは編集履歴を見て下さい。
これでダイス予測の本体ができました。UIなりは適当に作れば完成！
完成品はこちら
残り2つの機能についても解説したかったが、ここまで書いていて結構長くなったのでまた後日書くことに。失踪しないように気を付けます。
2022/6/29追記
失踪しませんでした。
2022/8/16追記
ダイス予測のアルゴリズムを改善するpart3を書きました。