C言語リバーシ 石を裏返す

シェアする

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

こんにちは。昨日はWORKING!!のニコ生一挙放送のタイムシフトを見ていたので更新できませんでした。まひるちゃんかわいい。

あと、WORKING!!見ながら艦これやってたら加古ちゃんドロップしました!加古ちゃんかわいい。

さて、前回は石を置ける場所の情報を持つビットボードを生成し、手の合法判定を行いました。

今回はついに、挟んだ石をひっくり返して「遊べるリバーシ盤」を作ろうと思います。

実装方法は、「盤面と打つ場所を引数に受け取って、ひっくり返る石の情報を持つビットボード(以下、反転パターン)を返す関数」を作り、石を置く処理の中身で反転処理も行う、という流れでいきます。

早速ですが、右方向から考えていきましょう。下のような局面で石を★に置いたとします。

・★○○●●○・

このとき、ひっくり返る石はもちろん★の右2つです。

ビットボード(1行ですが)で書くと、

black: 00001100
white: 00110010
pos : 01000000

で、反転パターンをrevとすると(reverseの略です)、

rev : 00110000

となります。これを探すのは簡単で、「posから右に見ていって、敵石である間右へ進み続けて、敵石でなくなった瞬間に自石ならそこまでの敵石連続がrevに入る。敵石でなくなった瞬間が空マスならひっくり返らない。」という処理になります。

つまり、posの右に連続する敵石は「暫定rev」に記録され、敵石の連続が途切れたときに自石であれば暫定revが「確定rev」にコピーされ、空マスであれば暫定revは破棄される、ということになります。

まず、posの右の地点(pos>>1で1が立っている場所)に石があると、white & (pos>>1)が0になりません。

このとき、(pos>>1)は「暫定rev」の一部なので、暫定rev(rev_tmpとします)とビットORを取ります(rev_tmpは最初に0で初期化します)。

rev_tmp |= ( pos >> 1 );

(現在は黒の立場で考えていますが、最終的にはwhiteはenemyになります。)

つぎに、pos >> 2 と white のビットANDを取って0でなければ、さらにrev_tmpとORを取ります。

rev_tmp |= ( pos >> 2 );

これを繰り返し、white & (pos >> i)(iは自然数)が0になるまでiを増やしていきます。

そしてwhite & (pos >> i)が0になったら、そのときのpos >> iが自石なら(黒目線で、black & (pos >> i) != 0 なら)rev_tmpをrevに追加するため、rev |= rev_tmp; を行います(revも0で初期化します)。

そして、rev_tmpを0で初期化して、次の方向の処理に移ります。

さて、これで基本的な処理は終わりですが、前回の合法判定と同様に、8×8でやると今回はビットシフトでの繰り下がりが厄介です。

前回同様、実は「端列の敵石」は関係無いのです(横方向の場合)。

右方向に見ていく場合、左端に敵石があってもそれは絶対に右方向にはひっくり返りませんよね。それより左に自石を置けないので。右端に敵石があってもそれは絶対に右方向にはひっくり返りません。それより右に自石が存在しないので。

ということで、今回も関係ない敵石を0にするためのmaskを使用します。すると、white & (pos >> i) & mask とすることで、posの位置が端に来ると(下段に下がってしまう前に)ループを抜けます。もしpos >> iが自石ならrev |= rev_tmpですし、敵石または空マスなら無視します。

ということで、右方向だけ見ると以下のような処理になります。

// 反転パターンを求める関数
uint64_t GetReverse(BOARD *board, uint64_t pos){
	int i;
	uint64_t me, enemy, mask, rev = 0, rev_cand;

	if(board->teban == SENTE){
		me = board->black;
		enemy = board->white;
	}else{
		me = board->white;
		enemy = board->black;
	}

	// 右方向
	i = 1;
	rev_cand = 0;
	mask = 0x7e7e7e7e7e7e7e7e;
	while( ( (pos >> i) & mask & enemy ) != 0 ){
		rev_cand |= (pos >> i);
		i++;
	}
	if( ( (pos >> i) & me) != 0 ) rev |= rev_cand;

	/* 他の方向の処理 */
	
	return rev;
}

手元の原作プログラムではこれなのですが、このwhile文はfor文に書き換えられますね。

for文はfor([最初だけ行う処理]; [繰り返し条件]; [ループ末尾で行う処理]){}の形なので、以下のように書き換えます。

// 反転パターンを求める関数
uint64_t GetReverse(BOARD *board, uint64_t pos){
	int i;
	uint64_t me, enemy, mask, rev = 0, rev_cand;

	if(board->teban == SENTE){
		me = board->black;
		enemy = board->white;
	}else{
		me = board->white;
		enemy = board->black;
	}

	// 右方向
	rev_cand = 0;
	mask = 0x7e7e7e7e7e7e7e7e;
	for(i = 1; ( (pos >> i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> i);
	}
	if( ( (pos >> i) & me) != 0 ) rev |= rev_cand;

	/* 他の方向の処理 */
	
	return rev;
}

他の方向も書くと(マスクに注意)、以下の通り。

// 反転パターンを求める関数
uint64_t GetReverse(BOARD *board, uint64_t pos){
	int i;
	uint64_t me, enemy, mask, rev = 0, rev_cand;

	if(board->teban == SENTE){
		me = board->black;
		enemy = board->white;
	}else{
		me = board->white;
		enemy = board->black;
	}

	// 右方向
	rev_cand = 0;
	mask = 0x7e7e7e7e7e7e7e7e;
	for( i = 1; ( (pos >> i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> i);
	}
	if( ( (pos >> i) & me) != 0 ) rev |= rev_cand;

	/* 他の方向の処理 */
	

	// 左方向
	rev_cand = 0;
	mask = 0x7e7e7e7e7e7e7e7e;
	for( i = 1; ( (pos << i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << i);
	}
	if( ( (pos << i) & me) != 0 ) rev |= rev_cand;


	// 上方向
	rev_cand = 0;
	mask = 0x00ffffffffffff00;
	for( i = 1; ( (pos << 8 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << 8 * i);
	}
	if( ( (pos << 8 * i) & me) != 0 ) rev |= rev_cand;


	// 下方向
	rev_cand = 0;
	mask = 0x00ffffffffffff00;
	for( i = 1; ( (pos >> 8 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> 8 * i);
	}
	if( ( (pos >> 8 * i) & me) != 0 ) rev |= rev_cand;


	// 右上方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos << 7 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << 7 * i);
	}
	if( ( (pos << 7 * i) & me) != 0 ) rev |= rev_cand;


	// 左上方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos << 9 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << 9 * i);
	}
	if( ( (pos << 9 * i) & me) != 0 ) rev |= rev_cand;


	// 右下方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos >> 9 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> 9 * i);
	}
	if( ( (pos >> 9 * i) & me) != 0 ) rev |= rev_cand;


	// 左下方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos >> 7 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> 7 * i);
	}
	if( ( (pos >> 7 * i) & me) != 0 ) rev |= rev_cand;
	
	return rev;
}

また、石を置くPut()関数は以下でした。

// 石を置く関数 posは絶対に合法手
void Put(BOARD *board, uint64_t pos){
	switch(board->teban){
		case SENTE:
			board->black |= pos;
			board->teban = GOTE;
			break;
		case GOTE:
			board->white |= pos;
			board->teban = SENTE;
			break;
		default:
			break;
	}
	board->move_num++;
	return;
}

ここに、boardの中身をルール通り更新する操作を書きます。

さて、ここで、ビット演算にはビットAND(どちらかに1が立っていれば1)とビットOR(どちらか一方あるいは両方で1が立っていれば1)の他に、ビットXOR(どちらか一方のみで1が立っていたら1)がありました。記号は^です。

1つのビットについて書くと、

a ^ b
0 ^ 0 は 0
0 ^ 1 は 1
1 ^ 0 は 1
1 ^ 1 は 0

です。ここで、

0 ^ 1 は 1
1 ^ 1 は 0

を見ると、あるビットと1のXORは、あるビットの逆(元が1なら0、元が0なら1になる)ということが分かります。これはまさにリバーシの反転です。

つまり、黒番で

white: 00110101

に対して反転パターンが

rev: 00110000

のとき、反転後の白石は

00110101
00110000 (^
--------
00000101

となります。

また、

black: 00001010

に対し、

pos: 01000000
rev: 00110000

のとき、反転後の黒石はrevが反転してposも追加されるので、

00001010
01110000 (^
--------
01111010

となります。(上から2段目は pos | rev です。)

よって、Put()関数を以下のようにすると反転処理が行えます。

// 石を置く関数 posは絶対に合法手
void Put(BOARD *board, uint64_t pos){
	uint64_t rev;
	
	// 反転パターン取得
	rev = GetReverse(board, pos);
	
	switch(board->teban){
		case SENTE:
			board->black ^= pos | rev;
			board->white ^= rev;
			board->teban = GOTE;
			break;
		case GOTE:
			board->white ^= pos | rev;
			board->black ^= rev;
			board->teban = SENTE;
			break;
		default:
			break;
	}
	board->move_num++;
	return;
}

さて、これで全体のソースコードを示しましょう。長いですよ。非常に長いです。

#include <stdio.h>

#define INPUT_ERROR 3

// 手番を表す列挙型
typedef enum TEBAN{
	SENTE = -1,
	GOTE = 1,
	GAME_OVER = 0
}TEBAN;

// 局面を表す構造体
typedef struct BOARD{
	uint64_t black, white;	// 黒石・白石のビットボード
	TEBAN teban;		// 手番
	int move_num;			// 何手動いたか(手数)
}BOARD;

// 関数プロトタイプ宣言
void Init(BOARD *board);							// 局面を初期化する関数
void ShowBoard(BOARD *board);						// 盤面を表示する関数
uint64_t GetPos();									// 座標を入力させ、posを返す関数
uint64_t PosTranslate(char file, int rank);			// 座標をuint64_tのposに変換する関数
void Put(BOARD *board, uint64_t pos);				// 石を置く関数 posは絶対に合法手
uint64_t GenValidMove(const BOARD *board);			// 合法手を生成する関数
uint64_t GetReverse(BOARD *board, uint64_t pos);	// // 反転パターンを求める関数

int main(void){
	BOARD board;
	uint64_t pos, valid;
	int i;
	
	// 局面を初期化
	Init(&board);
	
	// 局面を表示
	ShowBoard(&board);
	
	// 石を置く
	for (i = 0; i < 5; i++){
		// 合法手を得る
		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);
	}
	return 0;
}

// 局面を初期化
void Init(BOARD *board){
	board->black = ((uint64_t)1<<28) + ((uint64_t)1<<35);
	board->white = ((uint64_t)1<<27) + ((uint64_t)1<<36);
	board->teban = SENTE;
	board->move_num = 0;
}

// 盤面を表示する関数
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;
	}
}

// 座標を入力させ、posを返す関数
uint64_t GetPos(){
	char file;	// 列番号(アルファベット)
	int rank;	// 行番号(数字)
	uint64_t pos;	// 指定箇所を示すビットボード
	
	printf("座標を入力してください。(例:f5)\n");
	scanf(" %c%d", &file, &rank);
	
	// 不正値ならエラーを返す
	if(file < 'a' || file > 'h' || rank < 1 || rank > 8) return INPUT_ERROR;
	
	
	// 受け取った座標からビットボードを生成
	pos = PosTranslate(file, rank);
	return pos;
}

// 座標をuint64_tのposに変換する関数
uint64_t PosTranslate(char file, int rank){
	int file_num;
	uint64_t pos;
	
	file_num = 7 - file + 'a';
	
	pos = ( (uint64_t)1 << ( file_num + 8 * (8 - rank) ) );
	
	return pos;
}

// 石を置く関数 posは絶対に合法手
void Put(BOARD *board, uint64_t pos){
	uint64_t rev;
	
	// 反転パターン取得
	rev = GetReverse(board, pos);
	
	switch(board->teban){
		case SENTE:
			board->black ^= pos | rev;
			board->white ^= rev;
			board->teban = GOTE;
			break;
		case GOTE:
			board->white ^= pos | rev;
			board->black ^= rev;
			board->teban = SENTE;
			break;
		default:
			break;
	}
	board->move_num++;
	return;
}

// 合法手を生成する関数
uint64_t GenValidMove(const BOARD *board){
	int i;
	uint64_t me, enemy, masked_enemy, t, valid = 0, blank;
	
	// 現在手番の方をme、相手をenemyにする
	if(board->teban == SENTE){
		me = board->black;
		enemy = board->white;
	}else{
		me = board->white;
		enemy = board->black;
	}
	
	// 空マスのビットボードを(黒または白)のビットNOTで得る
	blank = ~(board->black | board->white);
	
	// 右方向
	masked_enemy = enemy & 0x7e7e7e7e7e7e7e7e; //端列を除く敵石
	t = masked_enemy & (me << 1); //自石の左隣にある敵石を調べる
	for(i = 0; i < 5; i++){
		t |= masked_enemy & (t << 1);
	}
	valid = blank & (t << 1);
	
	// 左方向
	masked_enemy = enemy & 0x7e7e7e7e7e7e7e7e;
	t = masked_enemy & (me >> 1);
	for(i = 0; i < 5; i++){
		t |= masked_enemy & (t >> 1);
	}
	valid |= blank & (t >> 1);
	
	// 上方向
	masked_enemy = enemy & 0x00ffffffffffff00;
	t = masked_enemy & (me << 8);
	for (i = 0; i < 5; i++){
		t |= masked_enemy & (t << 8);
	}
	valid |= blank & (t << 8);
	
	// 下方向
	masked_enemy = enemy & 0x00ffffffffffff00;
	t = masked_enemy & (me >> 8);
	for (i = 0; i < 5; i++){
		t |= masked_enemy & (t >> 8);
	}
	valid |= blank & (t >> 8);
	
	// 右上方向
	masked_enemy = enemy & 0x007e7e7e7e7e7e00;
	t = masked_enemy & (me << 7);
	for (i = 0; i < 5; i++){
		t |= masked_enemy & (t << 7);
	}
	valid |= blank & (t << 7);
	
	// 左上方向
	masked_enemy = enemy & 0x007e7e7e7e7e7e00;
	t = masked_enemy & (me << 9);
	for (i = 0; i < 5; i++){
		t |= masked_enemy & (t << 9);
	}
	valid |= blank & (t << 9);
	
	// 右下方向
	masked_enemy = enemy & 0x007e7e7e7e7e7e00;
	t = masked_enemy & (me >> 9);
	for (i = 0; i < 5; i++){
		t |= masked_enemy & (t >> 9);
	}
	valid |= blank & (t >> 9);
	
	// 左下方向
	masked_enemy = enemy & 0x007e7e7e7e7e7e00;
	t = masked_enemy & (me >> 7);
	for (i = 0; i < 5; i++){
		t |= masked_enemy & (t >> 7);
	}
	valid |= blank & (t >> 7);

	return valid;
}

// 反転パターンを求める関数
uint64_t GetReverse(BOARD *board, uint64_t pos){
	int i;
	uint64_t me, enemy, mask, rev = 0, rev_cand;
	
	// 現在手番の方をme、相手をenemyにする
	if(board->teban == SENTE){
		me = board->black;
		enemy = board->white;
	}else{
		me = board->white;
		enemy = board->black;
	}
	
	// 右方向
	rev_cand = 0;
	mask = 0x7e7e7e7e7e7e7e7e;
	for( i = 1; ( (pos >> i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> i);
	}
	if( ( (pos >> i) & me) != 0 ) rev |= rev_cand;
	
	// 左方向
	rev_cand = 0;
	mask = 0x7e7e7e7e7e7e7e7e;
	for( i = 1; ( (pos << i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << i);
	}
	if( ( (pos << i) & me) != 0 ) rev |= rev_cand;
	
	// 上方向
	rev_cand = 0;
	mask = 0x00ffffffffffff00;
	for( i = 1; ( (pos << 8 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << 8 * i);
	}
	if( ( (pos << 8 * i) & me) != 0 ) rev |= rev_cand;
	
	// 下方向
	rev_cand = 0;
	mask = 0x00ffffffffffff00;
	for( i = 1; ( (pos >> 8 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> 8 * i);
	}
	if( ( (pos >> 8 * i) & me) != 0 ) rev |= rev_cand;

	// 右上方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos << 7 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << 7 * i);
	}
	if( ( (pos << 7 * i) & me) != 0 ) rev |= rev_cand;
	
	// 左上方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos << 9 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos << 9 * i);
	}
	if( ( (pos << 9 * i) & me) != 0 ) rev |= rev_cand;
	
	// 右下方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos >> 9 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> 9 * i);
	}
	if( ( (pos >> 9 * i) & me) != 0 ) rev |= rev_cand;
	
	// 左下方向
	rev_cand = 0;
	mask = 0x007e7e7e7e7e7e00;
	for( i = 1; ( (pos >> 7 * i) & mask & enemy ) != 0; i++ ){
		rev_cand |= (pos >> 7 * i);
	}
	if( ( (pos >> 7 * i) & me) != 0 ) rev |= rev_cand;
	
	return rev;
}

これでコンパイルして実行すると、5手だけしか打てませんが、初手f5でちゃんと白石が黒石になっています。

ついに300行を超えましたが、ゴールはまだ先です。

次回は、ゲームの終了判定を実装して、60手最後まで打てるようにしましょう。では。

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

シェアする

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

フォローする