ゲーム問題のプログラミング

こんにちは。

合コンに行ったら、AKB48の前田敦子、篠田麻里子、板野友美、大島優子が現れて、楽しんでいたら、彼女に見つかってしまって怒られる。。

ちなみに、彼女は北乃きい☆

メイプルのCMみたいに、「もう、やめてくださいっ！」って怒られる。。

http://www.youtube.com/watch?v=GRn49MKaoPM

正月休みが長すぎて、変な想像をして時間を潰しています（笑）

やば、この妄想っぷり。。

今日は、ゲーム問題のプログラミングについて書きます。

ここで言うゲーム問題とは、「2人のプレイヤーが交互にプレーし、お互いが自身のターンで最善手を選んだときに、勝つのはどちらのプレイヤーか」という問題です。

大体の場合、これらの問題は、

• 必ずどちらかが勝てるような構造になっている
• 状態が循環することはない

という条件を満たしています。このような条件を満たす場合、オーソドックスな解法は「ゲーム木(game tree)」をDFSで探索するというものです。

取りあえず、例題を見てみましょう。今回は、私のオリジナル問題です。

A君、B君が以下のようなゲームをする。

最初、数字nが与えられて、A君は、n+1またはn+10を選ぶ。

次にB君は、A君が選んだ数字に対して、1または10を足す。さらに、A、B、A、・・・と続く。

先に、100に達した方が、勝ち。

もし、100を超えたら負け。

お互いが、各ターンで最善手を選択するとき、A君はこのゲームに勝つことができるかどうかを求めよ。

ただし、nは[1, 100)とする。

「お互いが、最善手を選択する」というのは、勝てる手があれば勝てる手を選び、勝てる手が1手も無い場合のみ負ける手を選ぶということです。

これだけきちんと理解できれば、比較的簡単に再帰で実装できます。

bool solve(int n) {
   if (n == 100) return false;
   if (n > 100) return true;

   if (!solve(n+1)) return true;
   if (!solve(n+10)) return true;
   return false;
}

この問題の場合は、

• 必ずどちらかが勝てるような構造になっている
• 状態が循環することはない（数字は増えるだけで、減ることはないため）

という条件があったため、ゲーム木による解法で解くことができました。しかし、勝ち負けが必ずしも決まらなかったり、循環したりする問題では、ゲーム木のDFSは使えません。

そのような場合は、DP-likeな解法で解くことができます。この解法は、比較的計算時間がかかりますが、queueを利用することで高速化することもできます。

このDP-likeな解法については、次回書こうかと思います。

（注意）SEO対策の実験のため、有名人の名前を無駄に入れてみました。冒頭の文章は決して私の趣味ではありません。たぶん。。おそらく。。。。