さて,いよいよ,第1レベルの最重要部分である。ここでは,新しく置いた石が相手の石を何個挟んでいるか,ということを問題にする。
a b c d e f g h
┏━┳━┳━┳━┳━┳━┳━┳━┓
1┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃○┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
2┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃○┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
3┃ ┃ ┃ ┃ ┃ ┃ ┃●┃○┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
4┃ ┃ ┃ ┃ ┃●┃○┃○┃*┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
5┃ ┃ ┃ ┃ ┃ ┃ ┃○┃ ┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
6┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃○┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
7┃ ┃ ┃ ┃ ┃●┃ ┃ ┃○┃
┣━╋━╋━╋━╋━╋━╋━╋━┫
8┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃●┃
┗━┻━┻━┻━┻━┻━┻━┻━┛
上のような状況で,*に●石を置いたとき,裏返る○石は,どのようにすれば見つかるか,を考えてみよう。
裏返る石の条件を書き上げると、次のようになる。
*から8方向(上,下,左,右,左上,左下,右上,右下)の方向に,空白を挟むことなく○が1個以上続いて直後に●があるとき,それらの○が裏返る。
これに従って,上の図の場合を調べてみよう。
図の場合には,左方向にだけ,裏返る石があることが分かった。
8方向すべてをいきなり考えると難しいので,とりあえず,1方向だけの場合にどのようにすればよいかを考えよう。 問題を次のように簡単にする。
練習問題2
int a[10] と宣言された配列 a があり,最初と最後の要素 a[0] と a[9] の値は -1
であるが,その他の要素の値は 0, 1, 2 のいずれかとする。また,p を 1 <= p <= 8 であるような整数とする。
a[p+1], a[p+2], ... の要素の値を見たとき,0を挟まず2が1個以上続いて,その直後に 1
があるかどうかを調査し,そうであれば続いている2の個数を,そうでなければ 0 を返す関数 check(a, p) を作れ。
解答解説
たとえば,配列 a の内容が次のようであったとする.
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
-1 |
0 |
2 |
0 |
2 |
2 |
1 |
0 |
2 |
-1 |
p==3 のとき, a[4] == a[5] == 2, a[6] == 1 であるから, check(a, 3) == 2 である。
この問題の解答は,番兵というテクニックを用いると簡単に解決できる。
番兵を用いない,次のような問題をやってみれば,番兵のありがたさが分かるだろう。
一発で間違いのないコーディングができた人は,それだけでこの授業の単位を出しても良いほどだ。
レポート問題 Othello-1
int a[8] と宣言された配列 a があり,その要素の値は 0, 1, 2 のいずれかとする。また,p
を 0 <= p < 8 であるような整数とする。a[p+1], a[p+2], ...
と調査したとき,0を挟まず2が1個以上続いて,その直後に 1 があるとき,その続いた2の個数を返し,そうでないとき 0 を返す関数 int check(int a[8], int p)を作れ。
解答解説
さて,先ほど作った check という関数は, a[p+1], a[p+2], ... と調査を行うが,a[p-1], a[p-2],
... の向きにも調査を行う関数を作りたい。じつは, check をほんのちょっと書き直せば, どちらの方向にも調査可能な関数に作り直せるのだ。
次の関数は,調査する方向を,引数 d によって指定している。
int check(int a[10], int p, int d) { int i; for (i = 1; a[p+i*d] == 2; i++); if (a[p+i*d] == 1) { return i-1; } else { return 0; } }
この関数は, d == 1 のときは配列の添え字が増える方向に, d = -1 のときは減る方向に調査する。この関数を番兵を用いないで書いてみると,とても数行では済まない。
さて,いよいよ,オセロゲームの場合である。この場合は,1次元ではなく2次元配列であり,調査すべき方向が8方向もある。しかし,本質的には,上で 作った関数 check と同じだ。舞台が2次元ならば,調査開始する場所指定が p, q と二つになるし,調査する方向も2次元,すなわち d の代わりに d, e と二つ用意すればよい。
プレイヤーは 1 か 2 であるから, 1 の相手は 2 であり, 2 の相手は 1 。よって player の相手は 3-player である。これを aite としてマクロ定義しておく。
#define aite(player) (3-(player))
int count_turn_over(int board[B][B], int player, int p, int q, int d, int e) { int i; for (i = 1; board[p+i*d][q+i*e] == aite(player); i++) {}; if (board[p+i*d][q+i*e] == player) { return i-1; } else { return 0; } }
石を置く場所が盤の中の方の場合、隅の方の場合、など、いろんな場合があって、それらをすべて含めて複雑な判断を行う関数なの に、たった数行という、驚くべき簡単さでその定義が終わっている。 これもそれもみんな,番兵さんのお陰なのだ(感謝)。
この count_turn_over 関数を用いて,第1レベルの残りの主要部分を作ることができる。
プレーヤーが打った手の合法性,すなわち,打った場所が盤内で、そこが空いていて、裏返る石が少なくとも一つある,ということを 調べる関数を作る。
int is_legal_move(int board[B][B], int player, int p, int q) { if (p < 1 || p > 8 || q < 1 || q > 8) return 0; if (board[p][q] != 0) return 0; if (count_turn_over(board, player, p, q, -1, 0)) return 1; /* 上 */ if (count_turn_over(board, player, p, q, 1, 0)) return 1; /* 下 */ if (count_turn_over(board, player, p, q, 0, -1)) return 1; /* 左 */ if (count_turn_over(board, player, p, q, 0, 1)) return 1; /* 右 */ if (count_turn_over(board, player, p, q, -1, -1)) return 1; /* 左上 */ if (count_turn_over(board, player, p, q, -1, 1)) return 1; /* 右上 */ if (count_turn_over(board, player, p, q, 1, -1)) return 1; /* 左下 */ if (count_turn_over(board, player, p, q, 1, 1)) return 1; /* 右下 */ return 0; }
最初の行で,指定された場所が盤の範囲内を調べている。次に,その場所に既に石があるかどうかを調べている。もしもあれば,もちろん石は置けない。続く8つの行で,8方向それぞれに裏返る石があるかどうかを調べている。どれか一つでもあれば,合法的な手である。
上の関数で,同じような行を8つも書くのが嫌な人は,
for (d = -1; d <= 1; d++) { for (e = -1; e <= 1; e ++) { ...... if (count_turn_over(board, player, p, q, 1, -1)) return 1; /* 左下 */ ...... } }
のように for 文を用いて d と e とを動かせば,count_turn_over を 書くのは 1 行ですむ.
レポート問題 Othello-2
関数 is_legal_move の定義を,上のように2重 for 文を用いて書き直せ.
解答解説
これは,8×8のすべての升目を調べるだけの単純な関数である.ひとつでも合法的な手があれば,1を返す.なければ0を返す
int exist_legal_move(int board[B][B], int player) { int i, j; for (i = 1; i <= 8; i++) { for (j = 1; j <= 8; j++) { if (is_legal_move(board, player, i, j)) return 1; } } return 0; }
プレーヤーに指し手の入力を促し,それを受け取る関数を作る。
入力は c5 のように,列記号と行番号を続けて入力することとする。
指し手が間違いであれば,再度入力を促す。
void get_move(int board[B][B], int player, int *p, int *q) { char str[100]; /* 入力した文字列が入るバッファ */ int i, j; printf("Player %d ", player); while (1) { printf("> "); fgets(str, sizeof(str), stdin); *q = str[0]-'a'+1; *p = str[1]-'1'+1; if (is_legal_move(board, player, *p, *q)) return; } }
fgets(char * str, int n, FILE* stream) は入力ストリーム stream から文字列を読み込む関数である(関数名は file get string の略)。 読み込んだ文字列は str に収納される。 読み込みは,n-1文字を読み込むか,改行文字 '\n' かファイルの終わりに行き当たるまで行われる。改行文字も str に収納される。 収納された文字列の最後にヌル文字 '\0' が付加される。
stdin は標準入力ストリームである。通常はキーボードからの入力のことを意味する。 stdin を使用するには,それに先立って, stdio.h をインクルードする必要がある。
次の部分を説明しよう。
*q = str[0]-'a'+1;
文字はアスキーコードの値で表される。文字'a' がどのような値を持っているかを知りたければ、 次を実行すればわかる。
main() { printf("%d\n", 'a'); }
その値は 'a'==97 である。そして,'b'==98, 'c'==99 と続く。したがって,たとえば
buf[0] == 'c' のとき, buf[0] - 'a' + 1 の値は,3 となる。
次を実行して、関数がうまく働いているかを確かめよう。
main() { int p, q; init_board(board); get_move(board, 1, &p, &q); board[p][q] = 1; print_board(board); }
先ほど作った get_move で,5c のように列と行の入力の順序を間違えても受け付けて,入力値が合法的でないときには,次のように親切に,合法的な手の一覧を表示するよ
うに変更しよう。
a b c d e f g h
------------------
1| 0 0 0 0 0 0 0 0|
2| 0 0 0 0 0 0 0 0|
3| 0 0 0 0 0 0 0 0|
4| 0 0 0 2 1 0 0 0|
5| 0 0 0 1 2 0 0 0|
6| 0 0 0 0 0 0 0 0|
7| 0 0 0 0 0 0 0 0|
8| 0 0 0 0 0 0 0 0|
------------------
Player 1 > c5
select a legal move: d3 c4 f5 e6 > 4c
a b c d e f g h
------------------
1| 0 0 0 0 0 0 0 0|
2| 0 0 0 0 0 0 0 0|
3| 0 0 0 0 0 0 0 0|
4| 0 0 1 2 1 0 0 0|
5| 0 0 0 1 2 0 0 0|
6| 0 0 0 0 0 0 0 0|
7| 0 0 0 0 0 0 0 0|
8| 0 0 0 0 0 0 0 0|
------------------
レポート問題 Othello-3
列と行の入力の順序を間違えても受け付けて,入力値が合法的でないときには,合法的な手の一覧を表示した後に再度入力
を促すように, get_move を変更せよ。
解答解説
石を指定された場所に置いて、その石で挟んだ相手の石を裏返す関数を作る。
void set_and_turn_over(int board[B][B], int player, int p, int q) { int count, d, e, i; for (d = -1; d <= 1; d++) { /* 上下方向 */ for (e = -1; e <= 1; e++) { /* 左右方向 */ if (d == 0 && e == 0) continue; count = count_turn_over(board, player, p, q, d, e); for (i = 1; i <= count; i++) { board[p+i*d][q+i*e] = player; /* 裏返す */ } } } board[p][q] = player; /* 石を置く */ }