C言語リバーシ 石を数える

シェアする

  • このエントリーをはてなブックマークに追加

こんにちは。今期のアニメは意外と面白いのが多いですね。何でも見てみるものです。

さて、前回は終了・パス判定を実装して、最後までちゃんと遊べるようにしたわけですが、今回は石の数を数える関数を作りたいと思います。

対局中に石数を表示して、対局終了時に石数を比べて勝敗を表示できるようにします。

さて、そもそも盤面は64ビット変数で黒白それぞれの石の存在箇所を保持するという形をとっていたのでした。

となると、石数を数えるというのは「2進数で表現したときの1の数を数える」ということになります。

ですが、上から順に64箇所チェックしていくのではありません。うまい方法があるのです。

簡単にするためにまず8ビットで考えましょう。

11010011という数を考えます。1の数は5つです。

これを、まず2ビットごとに分割します。

11 01 00 11

この数について、それぞれの区間で1の数を数えましょう。

各区間は2ビットなので、計算は「上位が1なら下位+1、上位が0なら下位そのもの」となります。(00なら0、01なら1、10なら0+1で1、11なら1+1で2個になります)

したがって、「上位ビットと右に1シフトした値+下位ビット」で計算できます。

何を言ってるか分からないかもしれませんが、次のように計算します。

まず、各2ビット区間について、上位ビットだけを取り出すマスク10101010を用意し、計算する数とビットANDを取ります。

11010011
10101010 (&
--------
10000010

これを右に1だけシフトすると、01000001となります。

同じように、下位ビットだけも取り出します(シフトはしません)。

11010011
01010101 (&
--------
01010001

以上の二つを足します。

01000001
01010001 (+
--------
10010010

すると、結果を2ビットずつ分けてみると10 01 00 10、つまりそれぞれ10進数にすると2 1 0 2となり、各区間の1の数が計算できています!

つぎに、2ビット区間を二つずつまとめた4ビット区間(元の数字では1101 0011)について考えますが、今計算で出てきた10010010に対して同じように上位2ビットを取り出して右に2だけシフトしたものと、下位2ビットだけ取り出したものを足せば、

10010010
11001100 (&
--------
10000000 →右に2シフト→00100000

10010010
00110011 (&
--------
00010010

これらを足して、

00100000
00010010 (+
--------
00110010

となり、4ビット区間0011 0010をそれぞれ10進数にすると3 2となり、元の数字を4ビット区間に分割したときのそれぞれの区間での1の数を表せています。

最後に同じことをおこなって、

00110010
11110000 (&
--------
00110000 →右に4シフト→ 00000011

00110010
00001111 (&
--------
00000010

これらを足して

00000011
00000010 (+
--------
00000101

となり、この00000101を10進数で書くと5になります。これた元の数字11010011の1の数に一致しています。

これと同じことを、64ビット区間になるまで繰り返していきます。

関数のコードは以下のようになります。

// 石の数を数える関数
int NumOfStone(uint64_t bits){
	bits = (bits & 0x5555555555555555) + (bits >> 1 & 0x5555555555555555);	// 2bitごと
	bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);	// 4bit
	bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);	// 8bit
	bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);	//16bit
	bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);	//32bit
	return (bits & 0x00000000ffffffff) + (bits >> 32 & 0x00000000ffffffff);	//64bit
}

名前はNumOfStone()にしています。

マスク掛けとシフトの順番を入れ替えて、マスクの種類を減らしています。(16進数で書いているので、マスクの意味は2進数に置き換えて考えてください。)

これでも目的の操作はできるのですが、高速化の観点から、最初と最後を以下のように改善することができます。

// 石の数を数える関数
int NumOfStone(uint64_t bits){
	bits = bits - (bits >> 1 & 0x5555555555555555);							// 2bitごと
	bits = (bits & 0x3333333333333333) + (bits >> 2 & 0x3333333333333333);	// 4bit
	bits = (bits & 0x0f0f0f0f0f0f0f0f) + (bits >> 4 & 0x0f0f0f0f0f0f0f0f);	// 8bit
	bits = (bits & 0x00ff00ff00ff00ff) + (bits >> 8 & 0x00ff00ff00ff00ff);	//16bit
	bits = (bits & 0x0000ffff0000ffff) + (bits >> 16 & 0x0000ffff0000ffff);	//32bit
	return (bits + (bits >> 32)) & 0x000000000000007f;						//64bit
}

詳しくはビットボードを用いた 4x4 オセロ 完全解析をご覧ください(解説丸投げ)

さて、これをもちいて石数表示と結果表示を行いましょう。

石数表示はShowBoard()関数に書き込みます。盤面表示のしたに「黒石:14個, 白石:11個」みたいに表示させましょう。

現在のShowBoard()関数がこれ。

// 盤面を表示する関数
void ShowBoard(BOARD *board){
	int i, rank = 1;
	uint64_t pos = (uint64_t)1<<63;
	printf("  a b c d e f g h\n");
	// 盤面表示
	for ( i = 0; i < 64 ; i++){
		// 行番号
		if(i % 8 == 0) printf("%d", rank++);
		// 盤面状態表示
		if( ( board->black & pos )!= 0) printf("黒");
		else if( ( board->white & pos ) != 0) printf("白");
		else printf("口");
		// 8回表示が終わるごとに改行
		if(i % 8 == 7) printf("\n");
		// posを一つずらす
		pos >>= 1;
	}
	// 手番表示
	printf("\n手番: ");
	switch(board->teban){
		case SENTE: printf("先手\n"); break;
		case GOTE: printf("後手\n"); break;
		default: break;
	}
}

改良版がこれ。

// 盤面を表示する関数
void ShowBoard(BOARD *board){
	int i, rank = 1;
	uint64_t pos = (uint64_t)1<<63;
	printf("  a b c d e f g h\n");
	// 盤面表示
	for ( i = 0; i < 64 ; i++){
		// 行番号
		if(i % 8 == 0) printf("%d", rank++);
		// 盤面状態表示
		if( ( board->black & pos )!= 0) printf("黒");
		else if( ( board->white & pos ) != 0) printf("白");
		else printf("口");
		// 8回表示が終わるごとに改行
		if(i % 8 == 7) printf("\n");
		// posを一つずらす
		pos >>= 1;
	}
	//石数表示
	printf("黒石: %d個, 白石: %d個\n", NumOfStone(board->black), NumOfStone(board->white));
	// 手番表示
	printf("\n手番: ");
	switch(board->teban){
		case SENTE: printf("先手\n"); break;
		case GOTE: printf("後手\n"); break;
		default: break;
	}
}

盤面表示と手番表示の後に入れています。

次に、結果表示用の関数を作りましょう。

// 結果を出力する関数
int ShowResult(BOARD *board){
	if(NumOfStone(board->black) > NumOfStone(board->white)){
		printf("黒の勝ち!\n");
		return 1;
	}else if(NumOfStone(board->black) < NumOfStone(board->white)){
		printf("白の勝ち!\n");
		return -1;
	}else{
		printf("引き分け!\n");
		return 0;
	}
}

見れば大体分かりますね。この関数が呼ばれた時に、黒石の方が多ければ黒の勝ち、白石の方が多ければ白の勝ち、同じなら引き分けです。ゲーム終了時にのみ呼び出します。

return文は別に必要ないのですが、何かのときに役に立つかもしれないので結果を判別できるように入れておきました。

さて、これをmain関数に入れましょう。対局が終了したときというのはwhile(board.teban != GAME_OVER)のループから抜けたときなので、その後に入れましょう。

int main(void){
	BOARD board;
	uint64_t pos, valid;
	int i;
	
	// 局面を初期化
	Init(&board);
	
	// 局面を表示
	ShowBoard(&board);
	
	// 石を置く
	while(board.teban != GAME_OVER){
		// 合法手を得る
		valid = GenValidMove(&board);
		// 手を受け取る
		pos = GetPos();
		if( pos == INPUT_ERROR ){
			printf("エラーです。\n");
			continue;
		}else if( (pos & valid) == 0){
			printf("非合法手です。\n");
			continue;
		}
		Put(&board, pos);
		ShowBoard(&board);
		
		CheckFinishPass(&board);
	}
	
	ShowResult(&board);
	
	return 0;
}

こんな感じです。最後に書き足すだけです。

これで対局中に石の数が表示されます。さらに対局終了時には結果が表示されます(確認は面倒なのでしていません)。

以上、今回も長くなりましたがここまでにします。次回はAI実装の準備としてmain関数をいじったりしたいと思います。では。

スポンサーリンク
レクタングル(大)
レクタングル(大)

シェアする

  • このエントリーをはてなブックマークに追加

フォローする