/* ○×ゲーム 必勝法（実は“必・引き分け法”）の出力、およびコンピュータとの対戦 | | 8 | 7 | 6 ---+---+--- ---+---+--- | | 5 | 4 | 3 ---+---+--- ---+---+--- | | 2 | 1 | 0 左の図のように、３×３のマス目を書く。二人のプレイヤーが、交互に、先攻は○を、 後攻は×を、マスの中に書いてゆく。いったん○または×が書かれたマスにはもう何も 書くことはできない。これを、空いたマスがなくなるまで続け、縦・横・斜めのいずれ かに、自分の記号を三つ並べた者が勝ちである。両者とも並べることに成功した場合は 引き分けとする。 （ただし、ゲームの画面では、○は O で、×は X で表現される。以下の説明の中の、 ゲームの画面の図でも同様である。） 右の図のようにマスに番号を振る。考えられるおのおのの局面に、「三進表記をした際 に 9 ケタ以下となる非負整数で、下から k ケタめ（一の位を 0 ケタめと数える）が 『k が振られたマスに○が書かれていれば 1, ×が書かれていれば 2, 何も書かれて いなければ 0』であるもの」を対応させる。 次に、三進表記で 0 から 222222222（2 が九つ、十進では 19682）までの整数 n を 考える。これらの数のそれぞれが、上の対応でこのゲームのある局面に対応するかどう か、するとしたらどちらかが勝ってゲームが終わっているか、ゲームの途中なら次は どちらの手番か、などを判別して返す関数が f() である。 それが返した値をいったん b[n] に代入する。 ゲームの途中で、○か×が一つ書き込まれ、ある局面からある局面へと変わると、上の 対応で対応する整数は必ず増加することに注意する。 n が三進表記の 222222222 から始めて 0 まで、1 ずつ戻りながら、その局面から一手 で移りうる局面すべてを考え、○の手番なら○が、×の手番なら×が最も有利になる 行き先にゆくために○あるいは×を書いてよいマスの番号すべてを考える。 たとえば○の手番でそれが 8, 6, 2 だったとすると、三進表記で下から 8 ケタめ、 6 ケタめ、2 ケタめだけが 1 でほかは 0 である整数、すなわち 101000100 を a[n] に 代入する。×の手番でそれが 8, 7, 2 だったとすると、三進表記で下から 8 ケタめ、 7 ケタめ、2 ケタめだけが 2 でほかは 0 である整数、すなわち 220000200 を a[n] に 代入する。また、b[n] は、最終的に○が勝つか、×が勝つか、引き分けるか、それとも あり得ない局面であるか、のいずれかで置き換える。（このように、b[n] を二通りに 使うところが少々ややこしい。b[n] の代わりに一時変数を使うことも試したが、元に 戻した。） こうしてゆくと、局面 n に対する必勝法あるいは“必・引き分け法”が得られる。 main() の終わり近くの print() で、それらを表にして出力する。その冒頭は 000|000|000 111|111|111 引き分け となるので、先手が最初にどこに○を書いても、双方が最善をつくせば、ゲームは 引き分けに終わることがわかる。どこに書くかは本質的には三通りだが、 000|000|001 202|022|220 引き分け 000|000|010 222|222|202 引き分け 000|010|000 222|202|222 引き分け であることから、先手が第一手を打つ場所ごとに、後手が×を打つべき位置がわかる。 それらを図示すれば以下のようになる。 X | | X X | X | X X | X | X ---+---+--- ---+---+--- ---+---+--- | X | X X | X | X X | O | X ---+---+--- ---+---+--- ---+---+--- X | X | O X | O | X X | X | X （その局面になったら自分の負けしかない、という局面もある。それは、それ以前に まずい手を打ってしまった場合である。その局面に対しては「空いているマスのどこに 打っても負け」ということで 000|011|122 222|200|000 ○の勝ち のように表示される。） コンピュータと対戦するときは、コンピュータは、最善の結果にいたる手のうちから ランダムに選んで打ってくる。どの手が、人間にとって最善の手を返すのが一番難しい か、などは考えていない。（コンピュータが先手の場合、第一手のみは例外で、中央に 打ってくる確率をほかのマスの４倍にしてある。それは、隅や辺は４箇所ずつあり、 その４箇所のどこに打っても本質的には同じことなので、「隅に打ってくる確率」「辺 に打ってくる確率」「中央に打ってくる確率」を等しくしたかったからである。 付）3 のベキ乗を計算する関数や、三進表記の i ケタめを返す関数を書いて利用しては みたが、素朴に、毎回計算するように戻してしまった。特に理由はない。 付）必勝法は 19683 行にわたって出力されるが、そのうち「あり得ない局面」とされる ものが 13637 行あり、残りは 6046 行である。 付）あり得ない局面とされなかった局面は、すべて起こり得る。それは、空いている マスがある限り、ゲームは続くからである。 付）ttt.c との違いは、「両者とも並べることに成功した場合は引き分け」としたこと である。プログラムは、関数 f() の変更だけで済んだ。 付）ttt.c でもこの ttt2.c でも、両者が最善をつくせば引き分ける。そのため、この ttt2.c を相手にプレイするときも、ttt.c だと思ってプレイして構わない。しかし、 この ttt2.c は、そうは考えないで打ってくる。つまり、たとえば、プレイヤーがあと 一手で自分の記号を並べられる局面で ttt2.c の番のとき、今後双方が最善をつくせば 引き分けであり、そのあと、自分も自分の記号を並べられると判断すれば、プレイヤー が自分の記号を並べるのを阻止しようとしないこともある。 */ #include #include #include #define N ((3*3*3)*(3*3*3)*(3*3*3)) /* 19683 に等しい */ #define YES 1 #define NO 0 #define O 1 /* ○ */ #define X 2 /* × */ int f(int n); void print(void); void play(void); void show(int n); void show2(int i); int a[N]; /* どこへゆくべきか、がはいる */ int b[N]; /* 結論がはいる。メモリが不足するときは signed char 型にしても可 */ main() { int n; /* 局面に対応する非負整数 */ int pow; /* 3 のベキ乗に値をとる */ for (n = N-1; n >= 0; n--) { /* m > n とすると、b[m] は -10, 0, 10, -123 のどれかであることに注意 */ a[n] = 0; /* 0 は行き先がないことを示す印 */ b[n] = f(n); if (b[n] == 10 || b[n] == 0 || b[n] == -10 || b[n] == -123) { ; /* 終わっているとき、ありえないときは何もしない */ } else if (b[n] == 1) { /* ○の手番のとき */ b[n] = -10; /* 最悪の場合、すなわち×の勝ち、としてみる */ /* 注)次の for ループ通過後は b[n] は -10 か 0 か 10 */ for (pow = 1; pow < N; pow = pow * 3) { /* 空いているマスを探し、試しに○を置いて、よくなるか調べる */ if ((n / pow) % 3 == 0) { /* マスが空いていたら */ if (b[n] == b[n + pow]) { /* 置いてみて等しければ */ a[n] = a[n] + pow; /* そのケタも 1 にする */ } else if (b[n] < b[n + pow]) { /* 置いてみてよくなれば */ a[n] = pow; b[n] = b[n + pow]; /* そこだけ 1 にする */ } } } } else if (b[n] == -1) { /* ×の手番のとき */ b[n] = 10; /* 最悪の場合、すなわち○の勝ち、としてみる*/ /* 注)次の for ループ通過後は b[n] は 10 か 0 か -10 */ for (pow = 1; pow < N; pow = pow * 3) { /* 空いているマスを探し、試しに×を置いて、よくなるか調べる */ if ((n / pow) % 3 == 0) { /* マスが空いていたら */ if (b[n] == b[n + 2*pow]) { /* 置いてみて等しければ */ a[n] = a[n] + 2*pow; /* そのケタも 2 にする */ } else if (b[n] > b[n + 2*pow]) { /* 置いてよくなれば */ a[n] = 2*pow; b[n] = b[n + 2*pow]; /* そこだけ 2 に */ } } } /*（b[n + 2*pow] == -123 はありえないことに注意）*/ } } printf("このままでは、このプログラムはこの文章以外何も出力しません. "); printf("プログラムの、main() の終わり近くにある、この文章を出力する箇所"); printf("の次の二行のどちらか（あるいは両方）のコメントをはずし、この文章"); printf("を出力する部分はコメントにして、再度コンパイルしてください.\n"); /* print(); /* 必勝法の出力 */ /* play(); /* ゲームで遊ぶ */ } /* 整数 n に対応する局面の○と×の配置を見て、次の数を返す。「〜の勝ち」とは、その 印が縦か横か斜めに並んでいることを意味する。 10 ... ○のみ勝ち（ゲームは終了している）。 1 ... 勝敗はついておらず、次は○の手番。 0 ... どちらも勝ちか、どちらも勝ちでない。（ゲームは終了している）。 -1 ... 勝敗はついておらず、次は×の手番。 -10 ... ×のみ勝ち（ゲームは終了している）。 -123 ... ありえない局面。-123 という数に特別の意味はない。 */ int f(int n) { int i, counto, countx, owin, xwin; int c[9]; for (i = 0; i < 9; i++) { /* 三進表記の各ケタを求める */ c[i] = n % 3; /* c[0] が一の位 */ n = n / 3; } counto = 0; /* ○の数を数える */ for (i = 0; i < 9; i++) { if (c[i] == O) { counto++; } } countx = 0; /* ×の数を数える */ for (i = 0; i < 9; i++) { if (c[i] == X) { countx++; } } if (counto != countx && counto != countx + 1) { return -123; /* ○と×の数が合わないので、ありえない場合 */ } if (c[0] == O && c[1] == O && c[2] == O) { /* ○が勝ちのケースを網羅 */ owin = YES; } else if (c[3] == O && c[4] == O && c[5] == O) { owin = YES; } else if (c[6] == O && c[7] == O && c[8] == O) { owin = YES; } else if (c[0] == O && c[3] == O && c[6] == O) { owin = YES; } else if (c[1] == O && c[4] == O && c[7] == O) { owin = YES; } else if (c[2] == O && c[5] == O && c[8] == O) { owin = YES; } else if (c[0] == O && c[4] == O && c[8] == O) { owin = YES; } else if (c[2] == O && c[4] == O && c[6] == O) { owin = YES; } else { owin = NO; } if (c[0] == X && c[1] == X && c[2] == X) { /* ×が勝ちのケースを網羅 */ xwin = YES; } else if (c[3] == X && c[4] == X && c[5] == X) { xwin = YES; } else if (c[6] == X && c[7] == X && c[8] == X) { xwin = YES; } else if (c[0] == X && c[3] == X && c[6] == X) { xwin = YES; } else if (c[1] == X && c[4] == X && c[7] == X) { xwin = YES; } else if (c[2] == X && c[5] == X && c[8] == X) { xwin = YES; } else if (c[0] == X && c[4] == X && c[8] == X) { xwin = YES; } else if (c[2] == X && c[4] == X && c[6] == X) { xwin = YES; } else { xwin = NO; } if (counto + countx == 9) { /* 盤がいっぱいになっている */ if (owin == YES && xwin == YES) { /* 両方が勝ち */ return 0; } if (owin == YES) { /* ○が勝ちの局面 */ return 10; } if (xwin == YES) { /* ×が勝ちの局面 */ return -10; } return 0; /* どちらも勝ちでない */ } else { /* 盤がいっぱいになっていない */ if (counto == countx) { /* ○×同数なら次は○の手番 */ return 1; } else { /* そうでなければ×の手番 */ return -1; } } } /* 必勝法の出力。三進で n と a[n] を表記し、結論をことばで書く。1 が○に、2 が×に 対応する。0 はどちらも置かれていないところ。三ケタずつ区切って表示する。n が 200|010|021 は下の局面にあたる。 X | | ---+---+--- | O | ---+---+--- | X | O このとき a[n] は 001|001|000 と出力され、その右に「○の勝ち」と表示されるが、 これは、次に 6 か 3 のマスに○を書けば、また、その場合のみ、以下双方が最善を つくしても○（先攻）の勝ち、という意味である。つまり、これが必勝法（引き分けに 持ち込むのがベストの局面では“必・引き分け法”）を示している。 */ void print(void) { int n, pow; for (n = 0; n < N; n++) { /* 以下、n を三進で上のケタから表示 */ for (pow = (3*3*3)*(3*3*3)*(3*3); pow > 0; pow = pow / 3) { printf("%d", n / pow % 3); if (pow == (3*3*3)*(3*3*3) || pow == (3*3*3)) { printf("|"); } } printf(" "); if (a[n] == 0) { /* 以下、a[n] を三進で上のケタから表示 */ printf(" | | "); } else { for (pow = (3*3*3)*(3*3*3)*(3*3); pow > 0; pow = pow / 3) { printf("%d", a[n] / pow % 3); if (pow == (3*3*3)*(3*3*3) || pow == (3*3*3)) { printf("|"); } } } if (b[n] == 10) { printf(" ○の勝ち\n"); } else if (b[n] == -10) { printf(" ×の勝ち\n"); } else if (b[n] == 0) { printf(" 引き分け\n"); } else if (b[n] == -123) { printf(" あり得ない局面\n"); } else { /* 以上のどれかになるはずだが、念のため次の行も用意した。*/ printf(" 何かが変です!\a\n"); /* \a は警告音を鳴らす働きをする */ } } } /* ゲームで遊ぶ。ここではマスの番号が冒頭のコメントと異なるが、表示も変えてあるの で大丈夫。（必勝法の表を見るときは、番号の違いは気にせずに見ればよい。） */ void play(void) { int i; /* （人間が）先攻のとき 1, 後攻のとき 2 */ int n; /* 局面の番号 */ int j, k; /* さまざまに使う変数 */ int x; /* ユーザ入力に使う */ int pow; /* 3 のベキ乗に値をとる */ { /* この中カッコの中はわからなくてもよい */ unsigned seed; seed = (unsigned)time(NULL); /* 現在時刻を種にして */ srand(seed); /* 乱数を初期化 */ } printf("マスの番号を覚えてください. （テンキーと同じです. ）\n\n"); printf(" 7 | 8 | 9 \n"); printf("---+---+---\n"); printf(" 4 | 5 | 6 \n"); printf("---+---+---\n"); printf(" 1 | 2 | 3 \n\n"); for (i = 0; i == 0; ) { printf("先攻 O にしますか？ 後攻 X にしますか？ "); printf("先攻 ... 1, 後攻 ... 2 ＞"); scanf("%d", &i); if (i != 1 && i != 2) { i = 0; /* これで入力し直しになる */ } } if (i == 1) { /* 人間が先攻なら */ n = 0; /* 何もないところから打たせる */ } else { /* 人間が後攻なら */ j = rand() % (9 + 3); /* 乱数を使って初手を決めるのだが、j が */ if (j >= 9) { /* 4 となる（＝まん中に打つ）確率がほか */ j = 4; /* のマスの 4 倍になるよう細工してある */ } for (n = 1; j > 0; j--) { n = 3 * n; } } for ( ; f(n) == 1 || f(n) == -1; ) { /* 決着がついていない限り */ show(n); /* 盤面を表示 */ for (x = 0; x == 0; ) { if (i == 1) { printf("あなたは O です. "); /* これ、意外と忘れるので */ } else { printf("あなたは X です. "); /* 毎回出力するようにした */ } printf("どこに打ちますか？ "); scanf("%d", &x); /* ユーザが打つ場所を入力 */ if (x < 1 || x > 9) { /* 範囲外の値を入力したとき */ x = 0; /* これで入力し直しになる */ } else { pow = 1; for (j = 0; j < x - 1; j++) { pow = pow * 3; } if (n / pow % 3 != 0) { /* そこに O か X が書いてあったら */ x = 0; /* これで入力し直しになる */ } } } n = n + i * pow; /* ユーザの入力に従い局面を変える */ show(n); /* 盤面を表示 */ if (f(n) == 1 || f(n) == -1) { /* 決着がついていない場合 */ /* 以下、コンピュータの打つ手を考える */ k = 0; /* 以下、a[n] の三進表記で 0 でないものの数を k に入れる */ for (pow = 1; pow < N; pow = pow * 3) { if (a[n] / pow % 3 != 0) { k++; } } /* 以下、乱数を使って、その中から一つ（下から j 番め）を選ぶ */ j = rand() % k; for (pow = 1; j >= 0; pow = pow * 3) { if (a[n] / pow % 3 != 0) { j--; } } pow = pow / 3; /* コンピュータが先攻なら pow を、後攻なら 2*pow を n に加える */ n = n + pow * (3 - i); } } /* 決着がついてループを抜けるとここへくる */ show(n); /* 画面表示 */ if (i == 1 && f(n) == -10 || i == 2 && f(n) == 10) { printf("私の勝ちです.\n"); } else if (f(n) == 0) { printf("引き分けです.\n"); } else { /* 上のどちらかになるはずだが、念のため */ printf("そ、そんなバカな...。この私が敗れるなんて...。ぐふっ！\n"); } } /* ゲーム用に、局面を画面表示 */ void show(int n) { printf("\n"); show2(n / ((3*3*3)*(3*3*3)) % 3); /* 6 ケタめを表示 */ printf("|"); show2(n / ((3*3*3)*(3*3*3)*(3)) % 3); /* 7 ケタめを表示 */ printf("|"); show2(n / ((3*3*3)*(3*3*3)*(3*3)) % 3); /* 8 ケタめを表示 */ printf("\n"); printf("---+---+---\n"); show2(n / (3*3*3) % 3); /* 3 ケタめを表示 */ printf("|"); show2(n / ((3*3*3)*(3)) % 3); /* 4 ケタめを表示 */ printf("|"); show2(n / ((3*3*3)*(3*3)) % 3); /* 5 ケタめを表示 */ printf("\n"); printf("---+---+---\n"); show2(n % 3); /* 0 ケタめを表示 */ printf("|"); show2(n / 3 % 3); /* 1 ケタめを表示 */ printf("|"); show2(n / (3*3) % 3); /* 2 ケタめを表示 */ printf("\n\n"); } /* x に応じて、空白、O, X を出力 */ void show2(int x) { if (x == 0) { printf(" "); } else if (x == 1) { printf(" O "); } else { printf(" X "); } }