|
とるべき石が最後の１個である石とりゲームでは、先手必勝か後手必勝かは定まっており、また、最善手を見つけることは容易である。 それに対して、例えば、１回にとることのできる玉は １～10個までと決まっていて、図のように、何個かの 10, 1, -1, -10点の玉があるようなゲームでは、高得点をとるためにはどのようにとっていけばよいのか、と問われるとちょっと困る。 （こちらから順にとる）→
なかなか面倒そうな問題に見えるが、実はちょっと考えてみると極めて簡単に最善手が得られるのである。 ----------------------------------------------------------- 例題として、上図の問題について考よう。 まず、 ○ １回にとることができる玉の個数は、1～10個とする。 本来、このゲームは相手に勝つことを目的とするものであるが、ここでは、高得点をとることを最善とする （勝つにしてもできるだけ高得点で勝つ、負けるにしてもできるだけ高得点で負ける）。 次の記号を用いる。 ○ Computer の番で、残りの玉が n個のときの最善でのとる玉の個数を p(n) で表す。 ○ Computer の番で、残りの玉が n個のとき、k個の玉（最善とは限らない）をとったとする。その後はいろいろ変遷があるであろうが、最終的にこのゲームの Computer の得点を ｆ [ n, k ] で表す。 したがって、ｆ [ n, p(n) ] は、残りの玉が n個のとき、Computer が最善手をとったときの、このゲームでの最終得点を表すことになる。 我々がやりたいことは、上の問題での p(n) (n=1,2,…,20) を求めることである。 まず、n が 10 以下についての p(n) は、相手も最善手をとることを考えて、次のようになることは容易にわかる。 p(1)=1 ｆ [ 1, 1 ]= 10 p(2)=2 ｆ [ 2, 2 ]= 10 p(3)=3 ｆ [ 3, 3 ]= 9 p(4)=4 ｆ [ 4, 4 ]= 9 p(5)=5 ｆ [ 5, 5 ]= -1 p(6)=1 ｆ [ 6, 1 ]= 1 p(7)=2 ｆ [ 7, 2 ]= 1 p(8)=3 ｆ [ 8, 3 ]= 1 p(9)=4 ｆ [ 9, 4 ]= 0 p(10)=5 ｆ [ 10, 5 ]= 10 さて、１回にとることができる玉の個数が 10個までなので、一般には n が 11以上になると直ぐには最善手が得られなくなり、可能な場合についてすべて検討してみなくてはならない。 といっても、初手でとることのできる場合の数は 1,2,…,10個の 10通りで、2手目以降は互いに既に求めている最善手をとる場合だけを考えればよいので、結局 10通りを検討し、そのうちで最高得点になるものを最善手とすればよいのである。 大切なことは、p(n) を求める順序として、 p(1), p(2), …, p(10) は考察により求める。 次に、p(11) を求める。 p(11) が求まってから p(12) を求める。 以下同様にして、p(20) まで求める とすることである。 実際にやってみよう。 残りの玉が 11個のときは、次のようになる。 f[11,1]=（11個目の玉の得点）+ (相手が p(10)=5個とるので、f[5,5])=0+(-1) = -1 f[11,2]=（11,10個目の玉の得点）+ (相手が p(9)=4個とるので、f[5,5])=(0+10)+(-1) = 9 f[11,3]=（11～9個目の玉の得点）+ (相手が p(8)=3個とるので、f[5,5])=(0+10-1)+(-1) = 8 f[11,4]=（11～8個目の玉の得点）+ (相手が p(7)=2個とるので、f[5,5])=(0+10-1+0)+(-1) = 8 f[11,5]=（11～7個目の玉の得点）+ (相手が p(6)=1個とるので、f[5,5])=(0+10-1+0+0)+(-1) = 8 f[11,6]=（11～6個目の玉の得点）+ (相手が p(5)=5個とるので、0)=(0+10-1+0+0+1)+0 = 10 f[11,7]=（11～5個目の玉の得点）+ (相手が p(4)=4個とるので、0)=(0+10-1+0+0+1-10)+0 = 0 f[11,8]=（11～4個目の玉の得点）+ (相手が p(3)=3個とるので、0)=(0+10-1+0+0+1-10+0)+0 = 0 f[11,9]=（11～3個目の玉の得点）+ (相手が p(2)=2個とるので、0)=(0+10-1+0+0+1-10+0-1)+0 = -1 f[11,10]=（11～2個目の玉の得点）+ (相手が p(1)=1個とるので、0)=(0+10-1+0+0+1-10+0-1+0)+0 = -1 したがって、 p(11)=6 ｆ [ 11, 6 ]= 10 を得る。 n が 12以上に対しても同様に行う。 この例題のように、玉の個数が 20個のような場合には、このように手計算でもできるが、computer にやらせると、あっという間に p(20) まで求めてしまう。ちなにみ、次の結果を得た。
塞翁が馬 Ⅱ、および 塞翁が馬 Ⅲ は、112個の玉があり p(112) まで求めなくてはならないが、computer はやはりあっという間に求めてしまうのである。 最善手をとったら最高得点はいくら？ 先手必勝？ 後手必勝？ それとも引き分け？ それは、ゲームの楽しみをなくしてしまいますので秘密です。 ところで、塞翁が馬 Ⅱ は 毎回同じ問題ですが、Computer のマネをしてもダメですよ。賢いあなたに最善手を見破られないように、Computer はときどき最善手ではない手をとってきますので。でもそれだけ、あなたが勝利するチャンスは大きくなります。 塞翁が馬 Ⅲ は、毎回異なった問題です。Computer は常に最善手をとってきますので、勝利できたら、あなたはすごい！！ (2005. 6.19)
|
Copyright(C) 2005 YokahiYokatoki