三山くずしゲームのルール
三つに分かれた石の山があります。二人が交互に山から石をとります．一つの山からは任意の個数を取ることができますが，二つの山に跨って取ることや，一つも取らないことは許されません．
石を取ることが出来なくなった方が負けです．
-
例
ゲームは，例えば，次のように進行します。3つの数が、実行後の各山の数です。
三つの山の数を(4,3,2)と表現します．A:(2,3,2)でプレーヤAが最初の山から2個取ったことを示します．
B:(2,3,1)＞A:(2,1,1)，
B:(0,1,1)＞A:(0,0,1)，
B:(0,0,0) でBの勝ちです．
-
マッチ棒を利用したゲームのようす
（参考文献から）
-
実例
実際にやってみましょう
2進数
-
10進数とは
このゲームは2進数を応用すると、必勝法を導くことができます。私たちは多くの場合、数字を10進数で表現します。10進数は 0,1,2 と順に数え 9 まで進むと、10 に対応する記号は利用せず、二つの記号を用いて 「１０」と表記します。左の１は「10」の桁で、「10」は 10 * 1 の意味ですね。10>11>12> と数え、19 の次は 20 となります。
どうように、「99」 のつぎは 3ケタの数となって「100」となりますね。
-
10進数以外
身の回りの数字で10進数でない数え方もありますね。時刻は 60 と 12/24 進数です。59秒の次は1分、60分の次が1時間、でこれは60進数です。24時間の次が1日で、29/30/31 日の次が1月です。このへんのきまりは歴史的な「事件」や暦（1年の移り変わり）できまっていて、数学的にきれいにきまったことではありません。
-
2進数
コンピュータは、オン（入り）とオフ（切り）を示す何百万という電子的なスイッチで構成されています。このスイッチのオンとオフの二つの記号を ０ と １ で表現すると、数を2進数で表すことができます。
この場合、０＞１＞１０（２）＞１１＞１００（４）＞１０１＞１１０＞１１１（７）＞１０００（８）
と数えます。（ ）の中は対応する10進数です。
2進数の上位の桁は、10進数では２のべき乗の値になります。ここで、2^5 は「２の5乗」の意味です。
1,2,4,8,16,32（2^5）,64,128,256,512,1024（2^10）、
-
指10本で 1023 まで数えることができる
ところで、指を折ったとき ０、伸ばした時を１とすると、5本の指で 31（2^5-1） まで、10本の指では 1023（2^10-1） まで数えることができます。ちょっとトレーニング「練習」が必要です。やってみてください。
-
2進数の演算
2進数の足し算方法は10進数の足し算の方法と変わりません。下の桁から桁上がりを考慮して順に計算します。２進数で和が（10進で）2以上の場合は、次の桁へ桁上げします。
0 0 1 0 + 0 1 1 0 ------------ 1 0 0 0
この計算は、10進数では、2 + 6 = 8 に相当します。
乗算も次のように組み立て算で計算します。桁ごとにずらしながらかけていき、最後に全体を加えます。10進数の場合と同じですね。面倒な 九＊九 を覚える必要はありません。
00101 * 00011 ---------- 00101 00101 00000 00000 ---------- 00001111コンピュータはこのような計算を1秒間に数億回やってしまいます。
-
偶奇性に基づく演算
ここでは、足し算や掛け算でなく、「偶奇性」にもとづく演算を利用します。演算を ^ でかき、これは演算対象の １ が偶数のとき０、奇数のとき１とします。0 ^ 1 ^ 0 = 1 で、0 ^ 1 ^ １ = ０ となります。実は、桁上げを考えない足し算と同じです。
-
いよいよ必勝法の公開です
これで準備ができました。
手法
-
必勝形
この三山くずしゲームには必勝法があり、最初の山の数で（相手がどのように取っても）勝つ方が定まっています．簡単な場合では (0,n,n) の場合，後手が必勝です．後手は先手と同じだけ別の山から石を取り常に (0,n,n) の形を保てば勝つことができます．また，(3,2,1)も必勝形です．この形にすれば、相手がどのようにとっても必ず勝つことができます。
-
一般的な必勝形
一般的な必勝法は次の通りです．各山の数を (a,b,c) とします．a, b, c をそれぞれ二進数に展開し，各桁を ai, bi, ci とします．このとき，すべての桁iについて ai ^ bi ^ ci = 0 のとき、必勝形とよびます。ここで、^ は「偶奇性」にもとづく演算で、1の数が偶数のとき0、奇数のとき1とします．
必勝形にすることができればゲームに勝つことができます。この必勝形に対し，ルールに従って石をとれば，必ず必勝形でなくなり、また，必勝形でない場合，適当に石をとれば必ず必勝形にできることが証明できます．
-
必勝形の例
（５，４，１）、 （６，４，２）、（７，５，２）、（７，４，３） などが必勝形です。各数を2進数で表現し、各桁ごとに偶奇性演算をし、すべて０になれば、必勝形です。
５： １ ０ １ ４： １ ０ ０ １： ０ ０ １ ------------- ０ ０ ０
-
証明
必勝形からどこか一つの山の数を減らすと、どこかの桁の0,1が変化するため、必勝形でなくなります。二つの山から減らすと必勝形が出来ますが、ゲームのルールで行えば必勝形からは必勝形でない数字になります。
必勝形でない形からは必勝形にすることが出来ます。必勝形でない一番大きな桁が１である山を崩せば、（それ以下の桁は好きな値に設定できますから）、必勝形にすることができます。
下の例の場合、必勝形でないのは先頭から2番目の桁です。この桁が１である２の山を崩して１にすれば必勝形にできます。
５： １ ０ １ ４： １ ０ ０ ２： ０ １ ０ -------------- ０ １ ０
別の例を考えます。必勝形でない最大の桁は先頭の桁です。この場合、５，４，６ どの山でもかまいません。
５： １ ０ １ ４： １ ０ ０ ６： １ １ ０ -------------- １ １ ０
たとえば、５の山を崩します。
５： ０ １ ０ ４： １ ０ ０ ６： １ １ ０ --------------- ０ ０ ０
ゲームマシンの作成
-
ゲームマシンの種類
必勝法のあるゲームは比較的簡単にプログラムできます。パソコン（PC）が利用できる場合、プログラムの開発ツールを組み込めば、ゲーム用のアプリ（プログラム）を作成できます。言語は C（これは中京大情報理工学部の必修言語）や Java が基本ですが、研究分野によっては Ruby や PHP なども利用されます。
プログラムの勉強には PC を利用しますが、実際にプログラムを利用する場合には PC ほどの能力はいりません。プログラムの開発ツールさえ手に入れば、携帯型の端末でもプログラムが実行できます。最近はやりのスマートフォン（iPhone、Android）では、無償で開発ツールが提供されています。ただし、iPhone では開発環境がアップル社のPCに限定されますので、私のゼミでは Android 端末を利用します。端末はなくても、PC でエミュレーション（模擬実行）できますから結果の確認もできます。
スマートフォンは電話機能などゲーム以外の機能を組み込んでいます。回路製作が好きならもっと単純な専用のゲームマシンは作ってしまうこともできます。この程度のゲームなら、1個数百円の組み込みコンピュータ（IC:集積回路）で動きます。プログラムは PC で作成し、それを組み込みコンピュータに「焼き込み」ます。表示は３桁のLEDを利用した数字表示、入力はスイッチです。部品代だけなら1000円程度です。
-
C言語でプログラム
ここでは基本的なC言語のプログラムの「かっこう」だけ紹介します。基本のC言語ではマウスやタッチパネルは利用しません。文字入力と文字表示だけ利用できます。
/*********************************************************** nim.c -- 三山くずし ***********************************************************/ #include <stdio.h> #include <stdlib.h> //奥村著：アルゴリズム辞典より int main() { int a[4], i, j, imax, max, n, r, x, my_turn; for (i = 1; i <= 3; i++) {//繰り返し処理 printf("%d 番の山の石の数? ", i); scanf("%d", &a[i]); if (a[i] <= 0) return EXIT_FAILURE; } for (my_turn = 1; ; my_turn ^= 1) { max = 0; for (i = 1; i <= 3; i++) { printf(" %d ", i);//表示 for (j = 1; j <= a[i]; j++) printf("*"); printf("\n"); if (a[i] > max) {//大小比較 max = a[i]; imax = i; } } if (max == 0) break; if (my_turn) { printf("私の番です.\n"); x = a[1] ^ a[2] ^ a[3]; /* 偶奇性演算和 */ j = 0; for (i = 1; i <= 3; i++) if (a[i] > (a[i] ^ x)) j = i; if (j != 0) a[j] ^= x; else a[imax]--; } else {//あなたの番です do { printf("何番の山からとりますか? "); r = scanf("%d", &i); scanf("%*[^\n]");//読み取り } while (r != 1 || i < 1 || i > 3 || a[i] == 0); do { printf("何個とりますか? "); r = scanf("%d", &n); scanf("%*[^\n]"); } while (r != 1 || n <= 0 || n > a[i]); a[i] -= n; } } if (my_turn) printf("あなたの勝ちです!\n"); else printf("私の勝ちです!\n"); return EXIT_SUCCESS; }C言語は情報理工学部の標準（必修）言語です。
実行例
１番の山の石の数?:4 2番の山の石の数?:3 3番の山の石の数?:2 0 :**** 1 :*** 2 :** ....... 何番の山からとりますか?:1 何個とりますか? :1 0 : 1 : 2 :* now I play I win
-
Javaアプレットでプログラム
C言語を少しグレードアップすると、画面上でグラフィックなインタフェースを利用したプログラムも可能ですが、ここではホームページ上で利用できるアプレットを紹介します。アプレットプログラムはJava言語を利用して作成し、ホームページ（web）に組み込むことができます。Java 言語は仮想マシンで実行できますから、仮想マシンを組み込んだマシンならどれでも（PCでもスマートフォンでも）実行できます。下はゲームの画面です。
Javaのプログラミングは選択科目で履修できます。
-
Android での実行
Android OS は Google社が開発し、無償で利用できるOS（コンピュータの管理ソフト）です。Android 上のプログラムは （PC上のとは少し異なりますが）Java言語で書くことができます。センサー、GPS、通話ダイアル、などの機能をフルに活用したアプリを作成し、公開することができます。
Androidでは、主な入力が画面のタップになりますから、ここではボタンのタップにより山の数を増減します。Android のプログラミングは複数のゼミ（研究室）で利用（勉強）しています。
組み込みコンピュータの世界
-
組み込みコンピュータ
組み込みコンピュータ（MPU）はプログラムを実行可能な電子回路を搭載したIC（集積回路）で、小形のものは百円程度で入手できます。MPU は外部の端子を利用して入出力を行います。MPUがプログラムにしたがい特定の端子に １ を出力すると、その端子は電源の電圧になり、数字型のLEDを点滅できます。
また、スイッチのオン/オフによる電圧の変化を端子から読み込み、各山の増減や必勝形の計算をすることができます。電源には単4電池2本を用いています。
写真右側は裏面の配線で、なれれば数時間で配線できます。
簡単な組み込みコンピュータの製作実験は、メディア工学科の講義で行っています。
参考文献
ダン・ピトー：「数学ソフトタッチ」 白揚社
オニール：「独習Java」 トップスタジオ
布留川：「Android2.1プログラミングバイブル」ソシム