(38.1) 簡単なゲームの中には、コンピュータで容易に必勝法を見つけられるものがある。 ここでは、三山崩し（みやまくずし）をとりあげてみよう。
(38.2) 碁石などの小さな石を、三箇所に、何個かずつ置く。個数は同じでなくても構わない。 それらを三つの山とみなす。 プレイヤーは交互に、 どれか一つの山を選んで、そこから石を任意の個数（ただし一個以上）だけ、 取り去ることができる。 そして、最後の石を取り去ったプレイヤーが勝ちとなる。
(38.3) これは有名なゲームなので、必勝法を知っている人もいるだろう。 しかし、ここでは、ルール以外は何も知らないとして、必勝法について考えてみよう。 （「必勝法とは何か」も、その中で明らかになってくる。）
(38.4) それぞれの山の石の個数は 9 以下に限定し、たとえば 「第一の山に 7 個、第二の山に 3 個、第三の山に 5 個」置かれている状態を 「735」で表そう。
(38.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
(38.6) いま、さらに簡単にするため、各山の石の個数は 2 個以下としてみよう。 すると全部で 3×3×3 = 27 通りの局面が考えられる。
(38.7) 「000」で自分の番になったら、負けなのであった。 このことを、「必敗（ひっぱい）」と呼び、右肩に「×」をつけて表そう。 （以下、上の図を参照。このあとは自分で印などをつけること。）
(38.8) 「001」で自分の番になったとき、勝てるのは明らかであるが、 いちおう、よく考えてみよう。 このとき、石のとり方は一つしかない。 そうとると、「000」にいたる。 「000」には必敗のマークがついていた。 よって、「001」で自分の番だったら、この石のとり方で必ず勝てる、 つまり、「必勝」というわけである。 だから、「001」から「000」に向かう矢印を書こう。 この矢印が、あるいは矢印の指す先が、「必勝法」と言える。 「010」、「100」も同様である。
(38.9) 「002」で自分の番になったときも、勝てるのは明らかであるが、 よく考えてみる。 第三の山から一つとると「001」にいたる。 すると、上の考察により、相手が必勝になる。 そうではなく、第三の山から二つとると「000」にいたり、相手は必敗。 よって、「000」へ行く、すなわち、石を二つとるべきであり、 一つだけとるべきではない、とわかる。 だから、「002」から「000」へ向かう矢印を書こう。 この矢印が「必勝法」である。 「020」「200」も同様である。
(38.10) 「011」の場合。 「010」に進むか、「001」に進むかだが、 どちらも、相手に必勝法があるのだった。よって、この場合は「必敗」である。 右肩に「×」を書こう。 「101」、「110」も同様である。
(38.11) 「012」の場合。 「002」、「011」、「010」へ進めるが、 相手が必敗になるのは「011」のみである。よって、そこへ向けて矢印を書く。 「021」、「102」、「201」、「120」、「210」 も同様。
(38.12) 「211」の場合、「011」へ進めば勝てる。よってそこへ向かって矢印を書く。 「121」、「112」も同様。
(38.13) 「111」の場合、「011」、「101」、「110」 のどこへ進んでも勝てる。すべてへ向かって矢印を書いてもよいし、一本だけ書いてもよい。
(38.14) 残りについては、各自で検討せよ。
(38.15) 上の考察法をまとめると、こうなる。
(38.16) 上では、思いつくままの順序で 27 通りのケースを検討したが、 次の事実を利用すれば、系統的に扱うことができる。 それは、たとえば「211」を十進法による整数の表記、 すなわち「二百十一」のことだと思うと、 進みうる先は必ずこれよりも小さな整数になる、ということである。 すなわち、こうやって整数と思ったとき、小さいほうから順に検討してゆけばよい。
(38.17) つまり、次のように考えればよい。数学的帰納法である。
(38.18) 以上を元に、各山の石の個数が 9 個以下として、 プログラムを書いてコンピュータに必勝法を求めさせてみよう。
(38.19) その前に、 GNOME 端末で「編集」「現在のプロファイル」「スクロール」として、 「スクロールバックのサイズ」を 1002 以上にしておこう。 出力が長くなるからである。
#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++) {
/* 結果の出力（どんなスタイルにするかは各自で考えること。） */
}
}
(38.20) i の百の位、十の位、一の位を求める式がむずかしいと感じる人は、 先に進む前に、それらを画面に出力させてチェックするとよい。
(38.21) a[i] に代入されるべき必勝法は一つみつかればよいのだが、 一つみつかったところでループを抜ける方法は教えていないので、 最後までループを進んでしまえばよい。 結果として、最後にみつかった必勝法が代入されることになる。
(38.22) この出力結果全体が必勝法とも言えるが、それではあまりに膨大である。 出力結果を見てよく考えると、世間でいう意味での必勝法が見つかるかも知れない。 それは、「こういうパターンのときにはこういう風に石をとる」といったものである。
(38.23) 上のプログラム例では結果を出力して終わりとしたが、 これを元に、人間と戦うプログラムを書いてもよい。
(38.24) 各山の石の個数を 0 から 99 まで、とすることもできる。
(38.25) 注意：Ｃ言語のプログラムにおいて、 「x = 010;」と書いた場合、 「0 で始まる数は八進表記とみなす」という約束があるため、 x には十でなく八が代入される。