石を裏返す

オセロのページに戻る

裏返る石の数

さて,いよいよ,第1レベルの最重要部分である。ここでは,新しく置いた石が相手の石を何個挟んでいるか,ということを問題にする。

  a b c d e f g h
 ┏━┳━┳━┳━┳━┳━┳━┳━┓
1┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃○┃
 ┣━╋━╋━╋━╋━╋━╋━╋━┫
2┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃○┃
 ┣━╋━╋━╋━╋━╋━╋━╋━┫
3┃ ┃ ┃ ┃ ┃ ┃ ┃●┃○┃
 ┣━╋━╋━╋━╋━╋━╋━╋━┫
4┃ ┃ ┃ ┃ ┃●┃○┃○┃*┃
 ┣━╋━╋━╋━╋━╋━╋━╋━┫
5┃ ┃ ┃ ┃ ┃ ┃ ┃○┃ ┃
 ┣━╋━╋━╋━╋━╋━╋━╋━┫
6┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃○┃
 ┣━╋━╋━╋━╋━╋━╋━╋━┫
7┃ ┃ ┃ ┃ ┃●┃ ┃ ┃○┃
 ┣━╋━╋━╋━╋━╋━╋━╋━┫
8┃ ┃ ┃ ┃ ┃ ┃ ┃ ┃●┃
 ┗━┻━┻━┻━┻━┻━┻━┻━┛


 上のような状況で,*に●石を置いたとき,裏返る○石は,どのようにすれば見つかるか,を考えてみよう。
裏返る石の条件を書き上げると、次のようになる。

*から8方向(上,下,左,右,左上,左下,右上,右下)の方向に,空白を挟むことなく○が1個以上続いて直後に●があるとき,それらの○が裏返る。

これに従って,上の図の場合を調べてみよう。

図の場合には,左方向にだけ,裏返る石があることが分かった。

問題を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 のときは減る方向に調査する。この関数を番兵を用いないで書いてみると,とても数行では済まない。

オセロの盤(2次元)の場合

 さて,いよいよ,オセロゲームの場合である。この場合は,1次元ではなく2次元配列であり,調査すべき方向が8方向もある。しかし,本質的には,上で 作った関数 check と同じだ。舞台が2次元ならば,調査開始する場所指定が p, q と二つになるし,調査する方向も2次元,すなわち d の代わりに d, e と二つ用意すればよい。

int count_turn_over(int board[B][B], int player, int p, int q, int d, int e) の関数仕様
board が表すゲーム盤の状況において, player (1または2)が,p行q列のマス目に石を置いたとき,そのマス目から(d, e) 方向(d, e は -1, 0, 1 のどれか。ただし,両方とも0 でなはい)にある,裏返る相手の石の個数を返す。

 プレイヤーは 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) の関数仕様
board が示すゲーム盤の状況において,player が (p,q) のマス目に石を置くことができるかどうかを返す。
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 文を用いて書き直せ.
解答解説

合法的な手の存在を調べる

int exist_legal_move(int board[B][B], int player) の関数仕様
ゲーム盤 board の状況において、プレイヤー player に合法的な手があるときに1をないときに0を返す。

これは,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) の関数仕様
標準出力にプレーヤー名 player(番号)と入力を促すプロンプト "> " を出力し,続いて標準入力から文字列を1行を読み込む。その先頭の2文字から,行番号を *p に,列番号を *q に設定する。入力値が合法的でない場合,再度入力を促す。戻り値はない。
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) の関数仕様
ゲーム盤 board の状況において, player の石を p, q の位置に置き,挟んだ相手の石を裏返す。
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; /* 石を置く */
}
オセロのページに戻る