Search on the blog

2011年1月6日木曜日

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

こんにちは。

合コンに行ったら、AKB48の前田敦子、篠田麻里子、板野友美、大島優子が現れて、楽しんでいたら、彼女に見つかってしまって怒られる。。
ちなみに、彼女は北乃きい☆
メイプルのCMみたいに、「もう、やめてくださいっ!」って怒られる。。


正月休みが長すぎて、変な想像をして時間を潰しています(笑)
やば、この妄想っぷり。。

今日は、ゲーム問題のプログラミングについて書きます。
ここで言うゲーム問題とは、「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対策の実験のため、有名人の名前を無駄に入れてみました。冒頭の文章は決して私の趣味ではありません。たぶん。。おそらく。。。。

0 件のコメント:

コメントを投稿