ソーシャルゲームに携わって結構な月日が流れましたが
その大半が俗にいうところの『カードゲーム』でした。

で、カードゲームとなると気になるのが
『ぼくのかんがえたさいきょうのデッキ』なわけです。

『おすすめ編成』みたいな機能は割とよく見かけるので、
サーバサイドで何かしらロジックは組まれていると思うんですが、
よくよく思い返してみると、コードそのものを見たことないなーと気づきました。
(ソーシャルではフロント担当ばっかりなので)

果たしてどんな感じなんだろう？　と気になってしまったので・・・
デッキ内のカードの攻撃力が最大となるような組み合わせを求めるコードを
ソーシャルで(少なくとも自分が関わった中では)よく使われるPHPで考えてみました。

アルゴリズムを考える

まずはいろいろと考えてみたんですが
総当たりにならないパターンでは

攻撃力順に並べて上から入れ、余ったコストに入るカードを入れる
単位コストあたりの攻撃力の高い順から埋める

などがありそうですが、どちらも余剰コストの埋め方・本当にそのカードが入っていていいのかetc...
といった問題が出てきそうなので、基本は総当たりになりそうなんですよね・・・

『ナップサック問題』がいい感じ

で、調べたらすぐに出てきてしまったんですが、
ナップサック問題というのがかなりいい感じです！

このアルゴリズムを一言で言うと

各アイテムを『入れた場合』と『入れない場合』のパターンを再帰的に調べる
1の結果のうち、結果が理想に近いほうを採用する
メモを使って、過去に試した組み合わせは処理を短縮

といった感じでしょうか？

ただ、wikiの例示をそのままだと

最大の容量合計を算出しているので、容量＝価値の時しか使えない
求めるものが『入れるアイテムの容量合計の最大値』なので、どのアイテムを使ったが分からない

といった事になってしまうので、手を加える必要がありますね。

どこに手を加えるか

カードゲームのデッキにある要素と比較すると

カードゲーム	ナップサック問題
デッキの最大コスト	ナップサック容量
デッキの最大枚数	？？？
カードのコスト	アイテムの容量
カードの強さ	？？？

みたいな対応になりそうなので、
？？？に該当する個所をアルゴリズムに加えてあげればよさそうです。

というわけで

できあがったものがこちらです！
(キュー〇ー3分クッキングのテーマに乗せて)

使い方

$knapsack = new Knapsack([デッキ最大コスト], [カードのコスト配列], [カードの攻撃力配列], [デッキに入れられる最大枚数]);
$res = $knapsack->getMaxCombination();

で、$resに最高の組み合わせが格納されます。

試しに以下。

$cardList  = array(
    array('cost' => 50,  'attack' => 1564),
    array('cost' => 20,  'attack' => 333),
    array('cost' => 6,   'attack' => 1923),
    array('cost' => 9,   'attack' => 8913),
    array('cost' => 3,   'attack' => 892),
    array('cost' => 12,  'attack' => 320),
    array('cost' => 88,  'attack' => 38117),
    array('cost' => 65,  'attack' => 23444),
    array('cost' => 15,  'attack' => 1564),
    array('cost' => 487, 'attack' => 15239),
    array('cost' => 43,  'attack' => 8523),
    array('cost' => 6,   'attack' => 5006),
);

$capacities  = array();
$values      = array();
foreach ($cardList as $value) {
    $capacities[] = $value['cost'];
    $values[]     = $value['attack'];
}

$maxCost  = 110; // デッキの最大コスト
$maxCount = 6;   // デッキに入れられる最大枚数
$knapsack = new Knapsack($maxCost, $capacities, $values, $maxCount);
$res = $knapsack->getMaxCombination();

echo implode(",",$res->keys); // 11,6,3,2
echo $res->sum;               // 53959

検算がどうしたものか、というところなのですが

$max = 0;          // メモの中の攻撃力合計の最大値
$f = array();      // $maxに対応するcardListのindex組み合わせ
$c = 0;            // $maxの時の合計コスト

foreach ($knapsack->_memory as $value) {
    foreach ($value as $key2 => $value2) {
        if ($max < $value2->sum) {
            $max = $value2->sum;
            $c = $key2;
            $f= $value2->keys;
        }
    }
}

echo $max;              // 53959
echo implode(",", $f);  // 11,6,3,2
echo $c;                // 110

となりましたので、上手くいっている・・・？　と思います！
※チェック用に $knapsack->_memory を publicに変えてます

注意点

[カードのコスト配列] と [カードの攻撃力配列] は0から始まる添え字配列にする
あるカードのコスト・攻撃力は　[カードのコスト配列] と [カードの攻撃力配列] の同じindexに入れる

どちらもアルゴリズム側の都合になるんですが、
処理中の配列index参照を、0からのインクリメントで行っている、というのと
コストと攻撃力のindexが一致していないと、対応するデータの参照ができないから、です。

引数をコストと攻撃で別配列に分けず、$cardListをそのまま引数に受けることも考えましたが、
コストや攻撃力に対応する配列キー名が外部データ依存(大体DBのカラム名？)なので
この形に落ち着きました。

まとめ

実際のゲームで考えると、
スキル効果があったり、属性での有利不利があったり、
そもそも攻撃力だけで考えていいのかーみたいな問題が山積みなのですが
今回のを基本に据えれば、割といろいろできそうですね～。

みんなもカードゲーム遊んでね！

そのデッキは本当に最強なのか？

アルゴリズムを考える

『ナップサック問題』がいい感じ

どこに手を加えるか

というわけで

使い方

注意点

まとめ