ぷよぷよ確率計算シミュレータ - PPSim
確率計算のアルゴリズム
このページでは、PPSimの確率計算アルゴリズムを示します。
計算の原理が分かりやすいように、できる限り簡潔なアルゴリズムにしました。
実際のプログラムでは無駄な処理を省くためにごちゃごちゃしていますが、基本的にはこのページで示したものと同じです。
また、条件設定によって途中消しが発生した場合はその盤面を無効とするか残り手数を減らすかのいずれかを行っていますが、話がややこしくなるのでこのページでは省略しています。
確率計算とは直接関係のない部分についてはブラックボックスな関数にしています。
※このアリゴリズムでは関数の再帰呼び出しを使っているのでプログラミングに不慣れの方は分かりづらいかもしれません。
その場合は、まずn=1としてこの関数を追っていけば分かりやすいと思います。
今回内容を示す関数
double probability(Field field, Tsumo cur_tsumo, int n):
盤面と現在手が与えられた時に、n手以内に条件を満たす確率を返します
ネクストは未知である（16種類のツモが等確率で出現する）とします
上記関数の中で使用する関数
bool Field::satisfiesCondition():
fieldに連鎖が生じた場合はそれを実行した上で、設定した条件（5連鎖など）を満たしたらtrueを返します
vector
現在手を置いた後の盤面状態としてあり得るもの全て（最大22要素）を返します
引数
Field field: 盤面状態を表すデータ（78マスそれぞれ赤、緑、青、黄、おじゃま、空のどれかを示します）
Tsumo cur_tsumo: 現在手（軸ぷよと子ぷよそれぞれ赤、緑、青、黄、のどれかを示します）
定数
Tsumo TSUMOALL[16]: 16種類のツモの配列
以下に確率計算のアルゴリズムを示します
double probability(Field field, Tsumo cur_tsumo, int n)
{
// 盤面状態が設定された条件（5連鎖など）を満たした場合は確率1を返します
// 後述のように、この時点のfieldはツモを置いただけで連鎖発生によるぷよの消去は行っていません
// そのため条件を満たさない場合も、fieldに連鎖が生じている場合はそれを実行してfieldを更新します
if(field.satisfiesCondition()) return 1;
// 条件を満たさないまま残り手数が0になったら確率0を返します
if(n == 0) return 0;
// 上2つの条件は再帰関数の末端処理で、ここからがメインの計算です
double p = 0;
// ループ1（平均値の計算）
// ネクストを見て現在手の置き方を決めるため、ネクスト毎に次の盤面状態の確率を計算します
for each(next_tsumo in TSUMOALL) {
// 次の盤面状態の確率が最も大きくなるように現在手を置くため、最大値を記録する変数を用意します
double max_p = 0;
// ループ2（最大値の探索）
// 現在手の置き方それぞれについて、次の盤面状態の確率を計算します
for each(next_field in nextfieldList(field, cur_tsumo)) {
// 1手進めたため、残り手数をn-1としてprobabilityを再帰呼び出しし、次の盤面状態の確率を得ます
// next_fieldは単にツモを置いただけの状態であることに注意
// 連鎖の実行は呼び出したprobabilityの先頭で行われます
double next_p = probability(next_field, next_tsumo, n-1);
// 今までの置き方よりも大きな確率になった場合は最大値を更新します
if(next_p > max_p) max_p = next_p;
}
// max_pは特定のネクストの時の確率であるため、そのネクストが出現する確率1/16をかけてから足します
p += max_p/16;
}
// ネクスト毎に求めた確率の平均値を返します
// これで、ネクストまで見て手を決めた場合の確率を求めたことになります
return p;
}
probability(Field field, Tsumo cur_tsumo, int n)を直接呼べば、現在の盤面状態と現在手から決まる確率を計算できます。ネクストまで見た状態の確率を求めたい場合は、まずnextfieldList(field, cur_tsumo)で現在手の置き方全てを列挙し、それぞれの確率を計算して最大値を取ります。逆に、盤面状態のみから確率を計算したい場合は、現在手を16パターン生成して、それぞれのprobability(Field field, Tsumo cur_tsumo, int n)の和を16で割れば求まります。