デッキ構成、というパズル
ドラゴンコレクションとかでデッキを構成してて、「これ、パズルになりませんかね」とか思った次第。
■問題について
ドラコレなどのカードゲーム風RPGでは、まぁカードゲームだけあってカードを扱う。カードには、それを使うのに必要なコストと、数値で表されるいくつかの性能（例えば「攻撃力」と「防御力」など）が設定されている。
デッキ構成では、カードを複数枚選び出し、ある性能の合計値ができるだけ高くなることを目指す。
・なにもかも無制限の場合
なにもかも無制限の場合、話は簡単で、持ってるカードをすべてデッキに入れればいい*1。
・枚数だけが制限されている場合
枚数だけが制限されている場合も話は簡単で、ある性能の値が高いカードから順に指定された枚数だけ選べばいい。
・枚数とコストが制限されている場合
これが一般的なドラコレ系のデッキ構成の状況。枚数は10枚以内で、コストはレベルによって上がるけど合計値の限界が存在する。
コスト限界値に対して十分にコストの低いカードしか持っていない場合は話は簡単で、例えば枚数が10枚まで、コストが20までで、所持カードのコストの最大値が2の場合は「枚数だけが制限されている場合」と同じやり方でいい。
問題は、持ってるカードのコストが微妙に高い場合。ベストな組み合わせが単純には見つからなくなる。
■問題
「コスト」「性能」の2つのパラメータを正の数値で持つカードの群、コスト合計値の限界、枚数の限界が与えられた時、「性能」の合計値を最大にするようなカードの組み合わせを求めよ。あるいは、求める手法を確立せよ。
■例題
例えば、以下の条件について考えてみる。
〜各種限界値〜
| コスト限界 | 50 |
|---|---|
| 枚数限界 | 10 |
〜カード群〜
| No. | コスト | 性能 | ■ | No. | コスト | 性能 | ■ | No. | コスト | 性能 | ■ | No. | コスト | 性能 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 1 | 1 | 32 | ■ | 11 | 4 | 80 | ■ | 21 | 6 | 124 | ■ | 31 | 9 | 164 |
| 2 | 1 | 35 | ■ | 12 | 4 | 102 | ■ | 22 | 7 | 113 | ■ | 32 | 10 | 128 |
| 3 | 1 | 33 | ■ | 13 | 4 | 104 | ■ | 23 | 7 | 104 | ■ | 33 | 10 | 135 |
| 4 | 1 | 31 | ■ | 14 | 4 | 85 | ■ | 24 | 7 | 148 | ■ | 34 | 10 | 139 |
| 5 | 1 | 21 | ■ | 15 | 4 | 95 | ■ | 25 | 8 | 124 | ■ | 35 | 10 | 147 |
| 6 | 2 | 41 | ■ | 16 | 4 | 92 | ■ | 26 | 8 | 133 | ■ | 36 | 10 | 148 |
| 7 | 2 | 47 | ■ | 17 | 4 | 71 | ■ | 27 | 8 | 133 | ■ | 37 | 10 | 194 |
| 8 | 3 | 56 | ■ | 18 | 5 | 72 | ■ | 28 | 9 | 121 | ||||
| 9 | 3 | 60 | ■ | 19 | 5 | 103 | ■ | 29 | 9 | 184 | ||||
| 10 | 4 | 95 | ■ | 20 | 6 | 123 | ■ | 30 | 9 | 107 |
■解法1：つよいひとからじゅんにえらぶ
結論から言うとそれっぽい理屈のついた解法の中では最低の部類に入る解法だけど、多分大抵のドラコレ系ゲームの「おすすめデッキ」はこの方法を使ってると思う。邪推。計算簡単だしね。
手順としては、コストを無視して「性能」の高いカードを順に選んでいく。最後ら辺で「コスト」が足りなくなるので、その時はコストの範囲内で最も「性能」の高いカードを選んでいく。「性能」が同じなら、「コスト」の少ないものを選ぶ。
〜例題を解法1で：1……とりあえず強いカードを順に選ぶ〜
上に示したカード群から「コスト」を無視して「性能」の高いカードを順に選んでいく。カードのリストを「性能」で整列して上から選んでいけばいい。
| No. | コスト | 性能 |
|---|---|---|
| 37 | 10 | 194 |
| 29 | 9 | 184 |
| 31 | 9 | 164 |
| 24 | 7 | 148 |
| 36 | 10 | 148 |
の5枚を選んだところで「コスト」合計が45になり、次の
| No. | コスト | 性能 |
|---|---|---|
| 35 | 10 | 147 |
が選べなくなる。
〜例題を解法1で：2……残「コスト」の範囲で「性能」の高いカードを選ぶ〜
コストは残り5しかないので、その範囲で「性能」の高いカードを順に選んでいく。すると最終的には
| No. | コスト | 性能 |
|---|---|---|
| 37 | 10 | 194 |
| 29 | 9 | 184 |
| 31 | 9 | 164 |
| 24 | 7 | 148 |
| 36 | 10 | 148 |
| 13 | 4 | 104 |
| 2 | 1 | 35 |
の7枚が選ばれ、以下のようなデッキが出来上がる。
| 枚数 | コスト | 性能 |
|---|---|---|
| 7 | 50 | 977 |
これが、解法1によるデッキ構成解。
■解法2：「性能」対「コスト」比の良いカードから選ぶ
「コスト」限界値が50の時、性能7・コスト10のカードなら5枚入って35の性能が得られる。性能4・コスト5のカードなら10枚入って40の性能が得られる。後者の方がお得だ。
コストに上限があると、単に性能が高いかどうかではなく「コストの割に性能が高い」かどうかが重要になってくる。例えば「性能÷コスト」の値が大きいカードほどよいカードと言うことができるかも知れない。
〜例題を解法2で：1……「効率」順のリストを作成する。〜
「性能÷コスト」の値を「効率」と呼ぶことにする。カードリストを「効率」で整列すると、以下のようになる。
| No. | コスト | 性能 | 効率 | ■ | No. | コスト | 性能 | 効率 | ■ | No. | コスト | 性能 | 効率 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 2 | 1 | 35 | 35.0 | ■ | 21 | 6 | 124 | 20.7 | ■ | 22 | 7 | 113 | 16.1 |
| 3 | 1 | 33 | 33.0 | ■ | 19 | 5 | 103 | 20.6 | ■ | 25 | 8 | 124 | 15.5 |
| 1 | 1 | 32 | 32.0 | ■ | 6 | 2 | 41 | 20.5 | ■ | 23 | 7 | 104 | 14.9 |
| 4 | 1 | 31 | 31.0 | ■ | 20 | 6 | 123 | 20.5 | ■ | 36 | 10 | 148 | 14.8 |
| 13 | 4 | 104 | 26.0 | ■ | 29 | 9 | 184 | 20.4 | ■ | 35 | 10 | 147 | 14.7 |
| 12 | 4 | 102 | 25.5 | ■ | 9 | 3 | 60 | 20.0 | ■ | 18 | 5 | 72 | 14.4 |
| 10 | 4 | 95 | 23.8 | ■ | 11 | 4 | 80 | 20.0 | ■ | 34 | 10 | 139 | 13.9 |
| 15 | 4 | 95 | 23.8 | ■ | 37 | 10 | 194 | 19.4 | ■ | 33 | 10 | 135 | 13.5 |
| 7 | 2 | 47 | 23.5 | ■ | 8 | 3 | 56 | 18.7 | ■ | 28 | 9 | 121 | 13.4 |
| 16 | 4 | 92 | 23.0 | ■ | 31 | 9 | 164 | 18.2 | ■ | 32 | 10 | 128 | 12.8 |
| 14 | 4 | 85 | 21.3 | ■ | 17 | 4 | 71 | 17.8 | ■ | 30 | 9 | 107 | 11.9 |
| 24 | 7 | 148 | 21.1 | ■ | 26 | 8 | 133 | 16.6 | |||||
| 5 | 1 | 21 | 21.0 | ■ | 27 | 8 | 133 | 16.6 |
〜例題を解法2で：2……とりあえず「効率」順にカードを選ぶ〜
解法1で「性能」順にカードを選んだように、今回は「効率」順にカードを選ぶ。結果は
| No. | コスト | 性能 | 効率 |
|---|---|---|---|
| 2 | 1 | 35 | 35.0 |
| 3 | 1 | 33 | 33.0 |
| 1 | 1 | 32 | 32.0 |
| 4 | 1 | 31 | 31.0 |
| 13 | 4 | 104 | 26.0 |
| 12 | 4 | 102 | 25.5 |
| 10 | 4 | 95 | 23.8 |
| 15 | 4 | 95 | 23.8 |
| 7 | 2 | 47 | 23.5 |
| 16 | 4 | 92 | 23.0 |
となり、以下のようなデッキが出来上がる。
| 枚数 | コスト | 性能 |
|---|---|---|
| 10 | 26 | 666 |
…………あれ、弱くね？
〜例題を解法2で：3……高効率低性能なカードを、低効率高性能なカードに差し替える〜
10枚選んで666は弱すぎるけど、コストはまだ24残っている。既に10枚選んでいるのでカードを追加することはできないけど、1枚入れて1枚抜く差し替えなら枚数は変わらないので問題なく行なえる。
以下に注意する。
- ・「1枚入れ」るカードは、引き続き効率の高いものから順に選ぶ
- まぁ、言うまでもなく。
- ・「1枚抜く」カードは、効率の低いものから順に選ぶ
- 逆も然り。
- ・「1枚入れ」るカードは、「1枚抜く」カードよりコストが大きい
- リストは効率順に並んでいるので、コストが同じならリストの上にあるカードの方が当然性能は高い。
- ・差し替えで性能が下がる場合は差し替えない
- まぁ当然。
分かりにくい作業なので、とりあえず1回分やってみる。
[2-3-1]未選択で高効率のカードを入れる。
つまり今回なら11枚目を選ぶ。
| No. | コスト | 性能 | 効率 | |
|---|---|---|---|---|
| 2 | 1 | 35 | 35.0 | |
| 3 | 1 | 33 | 33.0 | |
| 1 | 1 | 32 | 32.0 | |
| 4 | 1 | 31 | 31.0 | |
| 13 | 4 | 104 | 26.0 | |
| 12 | 4 | 102 | 25.5 | |
| 10 | 4 | 95 | 23.8 | |
| 15 | 4 | 95 | 23.8 | |
| 7 | 2 | 47 | 23.5 | |
| 16 | 4 | 92 | 23.0 | |
| 14 | 4 | 85 | 21.3 | ←追加した |
一時的に11枚になった。
[3-2]選択中でコストが低く低効率なカードを抜く。
今回は、↑のリストで下から3枚目のNo.7を抜く。
| No. | コスト | 性能 | 効率 | |
|---|---|---|---|---|
| 2 | 1 | 35 | 35.0 | |
| 3 | 1 | 33 | 33.0 | |
| 1 | 1 | 32 | 32.0 | |
| 4 | 1 | 31 | 31.0 | |
| 13 | 4 | 104 | 26.0 | |
| 12 | 4 | 102 | 25.5 | |
| 10 | 4 | 95 | 23.8 | |
| 15 | 4 | 95 | 23.8 | |
| (7) | (2) | (47) | (23.5) | ←（一時的に）抜いた |
| 16 | 4 | 92 | 23.0 | |
| 14 | 4 | 85 | 21.3 |
[2-3-3]2-3-2で抜いたカードと差し替えられるカードがあれば、[2-3-1][2-3-2]と同様に差し替える。
2-3-2で抜いたNo.7のカードは当然「未選択」のカードになるので、2-3-1・2-3-2でしたように差し替えが行なえる可能性がある。今回の場合、コスト1のNo.4と差し替えられる。その結果、以下のようになる。
| No. | コスト | 性能 | 効率 | |
|---|---|---|---|---|
| 2 | 1 | 35 | 35.0 | |
| 3 | 1 | 33 | 33.0 | |
| 1 | 1 | 32 | 32.0 | |
| (4) | (1) | (31) | (31.0) | ←抜いた。差し替えられるカードがないので、抜いたまま。 |
| 13 | 4 | 104 | 26.0 | |
| 12 | 4 | 102 | 25.5 | |
| 10 | 4 | 95 | 23.8 | |
| 15 | 4 | 95 | 23.8 | |
| 7 | 2 | 47 | 23.5 | ←1回抜いたけどまた入れた |
| 16 | 4 | 92 | 23.0 | |
| 14 | 4 | 85 | 21.3 |
結果、以下のようなデッキになり、性能が少し上がった。
| 枚数 | コスト | 性能 |
|---|---|---|
| 10 | 29 | 720 |
……まだ弱い。
〜例題を解法2で：4……解法2:3を繰り返す。
手順を紹介したところで、最後まで繰り返す。結果、以下のようなデッキが出来上がる。
| No. | コスト | 性能 | 効率 |
|---|---|---|---|
| 13 | 4 | 104 | 26.0 |
| 12 | 4 | 102 | 25.5 |
| 10 | 4 | 95 | 23.8 |
| 15 | 4 | 95 | 23.8 |
| 16 | 4 | 92 | 23.0 |
| 14 | 4 | 85 | 21.3 |
| 21 | 6 | 124 | 20.7 |
| 19 | 5 | 103 | 20.6 |
| 20 | 6 | 123 | 20.5 |
| 29 | 9 | 184 | 20.4 |
で、その性能は以下の通り。解法1のデッキなんか属性差があってもブチ殺せそうな強いデッキに仕上がった。
| 枚数 | コスト | 性能 |
|---|---|---|
| 10 | 50 | 1107 |
いくつかの例で試したけど、当然ながら解法2が解法1を下回ることはなかった。
■解法3、解法4……
ぶっちゃけ解法4まで試して、解法2よりマシなデッキもできたんだけど、書くの面倒くさいからここまで。俺が倒れても第3第4の解法が現れるはずだー的な。
とりあえず、解法4で作ったデッキを以下に。
| No. | コスト | 性能 | 効率 |
|---|---|---|---|
| 2 | 1 | 35 | 35.0 |
| 10 | 4 | 95 | 23.8 |
| 12 | 4 | 102 | 25.5 |
| 13 | 4 | 104 | 26.0 |
| 15 | 4 | 95 | 23.8 |
| 19 | 5 | 103 | 20.6 |
| 20 | 6 | 123 | 20.5 |
| 21 | 6 | 124 | 20.7 |
| 24 | 7 | 148 | 21.1 |
| 29 | 9 | 184 | 20.4 |
| 枚数 | コスト | 性能 | |
| 10 | 50 | 1113 |
■問題点
解法4まで全てに共通する問題点だけど、逐次的にカードを選んでいるので局所解に陥る危険性がある。また、カードが9枚以下になる可能性を想定していない*2。
■しかし現実は
とまぁ与えられた条件で最善を尽くそうとすると割と面白いことになるデッキ構成だけど、実際にはそんな暇があったらカードのレベル上げしたり強いカード手に入れてレベル上げてコスト限界上げてとやった方が遥かに強くなるわけで、対戦にしてもそもそもコスト限界低い相手を選べば楽勝だったりしてカードバトルというよりもぐら叩きだよねこれ的な状況がある。
残念。
■……で？
なんか良い解法ないかなぁ。
■（追記）
記録更新した。この沼は深いZE……。
| No. | コスト | 性能 |
|---|---|---|
| 7 | 2 | 47 |
| 10 | 4 | 95 |
| 12 | 4 | 102 |
| 13 | 4 | 104 |
| 15 | 4 | 95 |
| 16 | 4 | 92 |
| 20 | 6 | 123 |
| 21 | 6 | 124 |
| 24 | 7 | 148 |
| 29 | 9 | 184 |
| 枚数 | コスト | 性能 |
| 10 | 50 | 1114 |
ちなみに解法5を使用。解法2の発展系で、入れ替えの発生しうる全てのカード*3について、複数枚入れ替えも想定した全ての入れ替え対象との入れ替え効率*4を計算し、効率の高い組み合わせで入れ替えることをコストが最大になるまで繰り返す馬鹿みたいに面倒くさい手法。その割に、あくまでも逐次的な処理なのでやっぱり最適とは言い切れない不遇な手法。
