MTGの単純化 - 探索の無駄をなくす -

前回の探索プログラム

前回、木探索のプログラムを書いてはみたものの、時間がかかりすぎて終わらなかった。できるだけ無駄な探索を減らして効率的な探索に修正する必要がある。

単純化

　プレイヤーが選択することはアタックとブロックである。すごく簡単にしたけど、これでもクリーチャーが５体ずつ並んでいる場合に、１体がアタックする場合のブロックの仕方は2^5通りある。2対の場合は3^5、3体の場合は4^5となり、１ターン中のアタックを選んでブロックを行うときのの場合の数は

36,232通りとなる。

この試行をライフが0になるまでランダムに繰り返す。こんなこと20ターンも繰り返せば終わるわけない。

条件の絞込み

　探索を行う上で誤った試行は省きたい。

アタック・ブロックの最低ルール

1. 相手のライフを0以下にできるならすべてのクリーチャーでアタックする。
2. 自分のライフが０以下になるブロックは行わない。
3. 2/2が2体ブロッカーに立っている場合に3/3がアタックして2/2と3/3の交換になるような損なアタックは行わない。
4. 2/2を残して3/3でチャンプブロックのようなメリットのないチャンプは行わない。

アタック・ブロックのルールの数式化

これらをプログラムに落とせるように数式で表現する。

1. アタッカーがA(1) ~ A(n)までのn体いて、同様にブロッカーB(k){k=1,2,.....,m}がいるとする。このときAatk(1)  <= Aatk(2)<=.... <=Aatk(n)とする。

   

   のとき、すべてのクリーチャーでアタックする。

2.  [1,n]の範囲から攻撃を通すクリーチャーを選んで整数の集合Sとして表記する。

   

   を満たすブロックが合法手である。

3. A(k){k=1,2,..n}でアタックを試みる。すべてのブロッカーB(k){k=1,2,...,m}の集合をSとする。Sを部分集合の集合X1,X2,....Xnに分割するとき、すべてのkに対して

   

   となる分割Xが存在する場合非合法である。
4. アタッカーがA(1) ~ A(n)までのn体いて、同様にブロッカーB(k){k=1,2,.....,m}がいるとする。このときAatk(1)  <= Aatk(2)<=.... <=Aatk(n)であり、Batk(1)<=Batk(2)<=... <=Batk(m)とする。A(p)をB(q)でブロックするときBatk(q) < Aatk(p)を満たす場合、「Batk(k) < Batk(q)」かつ「B(k)はブロックを行わないかダブルブロック以上を行う」を満たすkが存在する場合非合法である。

・さらに、 MTGのルールではないが、最善手を見つけたらそれ以上そのノードの探索は行わない。を付け足す。

終わりに

　これで計算終わるのか？ひとまずコードにしてみようと思う。