2009 年度「計算数学1」 2009-06-29

§69 文字列検索の計算量

(69.1) 前回やった文字列検索の計算量は、p[ ] の長さと a[ ] の長さとの積に比例する。 a[ ]1 ばかりが並んだもの、 p[ ]1 が並んだあとに 2 が 1 個だけあるもの、 のときが最悪の場合である。

(69.2) これを改良する方法が知られているが、その説明はこの授業では割愛する。

§70 ゲームの必勝法(三山崩し)

(70.1) 簡単なゲームの中には、コンピュータで容易に必勝法を見つけられるものがある。 ここでは、三山崩し(みやまくずし)をとりあげてみよう。

(70.2) 碁石などの小さな石を、三箇所に、何個かずつ置く。個数は同じでなくても構わない。 それらを三つの山とみなす。 プレイヤーは交互に、 どれか一つの山を選んで、そこから石を任意の個数(ただし一個以上)だけ、 取り去ることができる。 そして、最後の石を取り去ったプレイヤーが勝ちとなる。

(70.3) これは有名なゲームなので、必勝法を知っている人もいるだろう。 しかし、ここでは、ルール以外は何も知らないとして、必勝法について考えてみよう。 (「必勝法とは何か」も、その中で明らかになってくる。)

(70.4) それぞれの山の石の個数は 9 以下に限定し、たとえば 「第一の山に 7 個、第二の山に 3 個、第三の山に 5 個」置かれている状態を 「735」で表そう。

(70.5) 「000」という局面はゲームには現れない。 その直前に最後の石をどちらかのプレイヤーがとった時点でゲームは終わるから。 しかし、これも含めて考えたほうが、わかりやすい。 すると、このゲームの勝ち負けの決め方は 「000 の状態で自分の番になったプレイヤーが負け」 と言い換えることができる。

                                 000×




      001       010       100           002       020       200





      011             101             110             022           202           220


  012     021     102     201     120     210         122           212           221


      211             121             112                           222



                      111

(70.6) いま、さらに簡単にするため、各山の石の個数は 2 個以下としてみよう。 すると全部で 3×3×3 = 27 通りの局面が考えられる。

(70.7) 「000」で自分の番になったら、負けなのであった。 このことを、「必敗(ひっぱい)」と呼び、右肩に「×」をつけて表そう。 (以下、上の図を参照。このあとは自分で印などをつけること。)

(70.8) 「001」で自分の番になったとき、勝てるのは明らかであるが、 いちおう、よく考えてみよう。 このとき、石のとり方は一つしかない。 そうとると、「000」にいたる。 「000」には必敗のマークがついていた。 よって、「001」で自分の番だったら、この石のとり方で必ず勝てる、 つまり、「必勝」というわけである。 だから、「001」から「000」に向かう矢印を書こう。 この矢印が、あるいは矢印の指す先が、「必勝法」と言える。 「010」、「100」も同様である。

(70.9) 「002」で自分の番になったときも、勝てるのは明らかであるが、 よく考えてみる。 第三の山から一つとると「001」にいたる。 すると、上の考察により、相手が必勝になる。 そうではなく、第三の山から二つとると「000」にいたり、相手は必敗。 よって、「000」へ行く、すなわち、石を二つとるべきであり、 一つだけとるべきではない、とわかる。 だから、「002」から「000」へ向かう矢印を書こう。 この矢印が「必勝法」である。 「020」「200」も同様である。

(70.10) 「011」の場合。 「010」に進むか、「001」に進むかだが、 どちらも、相手に必勝法があるのだった。よって、この場合は「必敗」である。 右肩に「×」を書こう。 「101」、「110」も同様である。

(70.11) 「012」の場合。 「002」、「011」、「010」へ進めるが、 相手が必敗になるのは「011」のみである。よって、そこへ向けて矢印を書く。 「021」、「102」、「201」、「120」、「210」 も同様。

(70.12) 「211」の場合、「011」へ進めば勝てる。よってそこへ向かって矢印を書く。 「121」、「112」も同様。

(70.13) 「111」の場合、「011」、「101」、「110」 のどこへ進んでも勝てる。すべてへ向かって矢印を書いてもよいし、一本だけ書いてもよい。

(70.14) 残りについては、各自で検討せよ。

(70.15) 上の考察法をまとめると、こうなる。

(70.16) 上では、思いつくままの順序で 27 通りのケースを検討したが、 次の事実を利用すれば、系統的に扱うことができる。 それは、たとえば「211」を十進法による整数の表記、 すなわち「二百十一」のことだと思うと、 進みうる先は必ずこれよりも小さな整数になる、ということである。 すなわち、こうやって整数と思ったとき、小さいほうから順に検討してゆけばよい。

(70.17) つまり、次のように考えればよい。数学的帰納法である。

  1. 000」は必敗である。
  2. ある整数 k までに対応する局面については必勝法または必敗であるという事実がわかっていると仮定すると、 k+1 に対応する局面についても、(70.15) で述べた方法によって、 必勝法を知るか、必敗であるという事実を知ることができる。

(70.18) 以上を元に、各山の石の個数が 9 個以下として、 プログラムを書いてコンピュータに必勝法を求めさせてみよう。

#include <stdio.h>

int a[1000];    /* 必敗の印か、どこへ進むのが必勝法か、を入れるところ */

main() {
    int i, j, n;

    a[0] = -1;  /* 必敗の印 */
    for (i = 1; i < 1000; i++) {
        a[i] = -1;          /* まずは仮に必敗の印を入れる */

        n = ???;            /* i の百の位 */

        /* ここで、仮に i の百の位が 7 だったら、a[i - 100], a[i - 200],     */
        /* ..., a[i - 700] のうちに必敗の印がはいっているものがあるかどうか  */
        /* を調べ、あったら、その添え字を a[i] に代入する。(矢印をひくこと  */
        /* に当たる。a[i] に仮に入れてあった必敗の印は上書きされて消える。) */

        n = ???;            /* i の十の位 */

        /* ここで、仮に i の十の位が 3 だったら、a[i - 10], a[i - 20],       */
        /* a[i - 30] のうちに必敗の印がはいっているものがあるかどうか        */
        /* を調べ、あったら、その添え字を a[i] に代入する。(矢印をひくこと  */
        /* に当たる。a[i] に仮に入れてあった必敗の印は上書きされて消える。) */

        n = ???;             /* i の一の位 */

        /* ここで、仮に i の一の位が 5 だったら、a[i - 1], a[i - 2], ...,    */
        /* a[i - 5] のうちに必敗の印がはいっているものがあるかどうか         */
        /* を調べ、あったら、その添え字を a[i] に代入する。(矢印をひくこと  */
        /* に当たる。a[i] に仮に入れてあった必敗の印は上書きされて消える。) */
    }

    for (i = 0; i < 1000; i++) {
        /* 結果の出力(どんなスタイルにするかは各自で考えること。) */
    }
}

(70.19) i の百の位、十の位、一の位を求める式がむずかしいと感じる人は、 先に進む前に、それらを画面に出力させてチェックするとよい。

(70.20) a[i] に代入されるべき必勝法は一つみつかればよいのだが、 一つみつかったところでループを抜ける方法は教えていないので、 最後までループを進んでしまえばよい。 結果として、最後にみつかった必勝法が代入されることになる。

(70.21) この出力結果全体が必勝法とも言えるが、それではあまりに膨大である。 出力結果を見てよく考えると、世間でいう意味での必勝法が見つかるかも知れない。 それは、「こういうパターンのときにはこういう風に石をとる」といったものである。

(70.22) 上のプログラム例では結果を出力して終わりとしたが、 これを元に、人間と戦うプログラムを書いてもよい。

(70.23) 各山の石の個数を 0 から 99 まで、とすることもできる。

(70.24) 注意:C言語のプログラムにおいて、 「x = 010;」と書いた場合、 「0 で始まる数は八進表記とみなす」という約束があるため、 x には十でなく八が代入される。


岩瀬順一