C言語リバーシ 合法手の生成

シェアする

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

こんにちは。少し前に艦これを始めたのですが、加古ちゃんがなかなか来てくれません。今は愛する木曾ちゃんを1-5レベリングしつつ、たまに2-1回ったりレア駆逐レシピで建造したりして加古ちゃんを捜しています。

さて、前回はとりあえず石を置く関数を作りました。今回は置き場所がルールに従っているかを判定するために合法手を示すビットボードを生成します。

まず「右方向に石を挟める場所」のビットボードを生成し、それに「左方向に石を挟める場所」のビットボードとビットORを取り、さらに「上方向に石を挟める場所」のビットボードとビットORを取り……という風に、8方向すべてについて挟める場所のビットボードのビットORを取ると、「いずれかの方向に石を挟める場所」のビットボードが手に入ります。これが求めていたものです。

では、右方向について考えましょう。

例えば先手番(黒番)で、ある行の配置が以下だったとします。

・・○○○●○●

もちろん右方向に挟める場所は左から2番目です。

右方向に石を挟める場所とは、「その場所の右隣から1つ以上敵石が連続して存在していて、かつ、敵石の連続の後に(空マスをはさまず)自石が存在する」というような場所です。

順番としては、まず「右隣に自石が存在する敵石」(上図の右から2番目と4番目)を探し、「そこから左へ進んでいくときに敵石が連続して存在する場所」を探します。(上図の左から3,4,5,7番目です)

それを右へビットシフトすると、「右隣りから敵石が連続して存在し、その果てに自石が存在する場所」が得られます。(上図の左から2,3,4,6番目です)

ですが、すでに石があるところに置くわけにはいかないので、求めたビットボードと「空白を表すビットボード」のビット&を取ると、「空マスであって、右隣りから敵石が連続して存在し、その果てに自石が存在する場所」が得られます。これが着手可能点になります。

上図でやってみると、

黒:00000101
白:00111010
空:11000000

で、まず「右隣りに自石が存在する敵石」を、白&(黒<<1)で求めます。(これをtとします。)

t =
00111010
00001010 (&
--------
00001010

となります。さらに、「そこから左へ進んでいくときに常に敵石が連続しているところ」を考えます。(すでに石があろうが関係ありません。)

左へ0マス移動した場合は現在のtそのものですが、左へ1マス移動したときにまだ敵石があるような移動先は、白&(t<<1)で得られます。とりあえずこれとtのビットORを取ります。

00111010
00010100 (&
--------
00010000

これとtをビットORして、

t =
00001010
00010000 (|
--------
00011010

これは、「そのマスが敵石で、そのマスのすぐ右隣か、そのマスの2つ右に、自石が存在するマス」を表現しています。

このような操作を繰り返していくのですが、最初のtを求める操作を含めて6回繰り返せば十分です。(右方向にひっくり返せる敵石は最大でも6個だからです。)

6回繰り返すと、上図でいうと次のtが得られます。

t = 00111010

(今回の例ではすべての敵石について右へ連続した先に黒石があるので、白のビットボードと同じになっています。もし最も右の黒石が無ければtは00111000になります。)

これを左へシフトして、空白のビットボードとビットANDをとったものをvalidとすると、

valid =
01110100
11000000 (&
--------
01000000

が得られます。これが「そこに黒石を置くと右方向に石を返せる空マス」を表すビットボードになります。

今は説明のために1行で行いました。

実は、8行で行うには問題があります。

左へシフトする計算が時々出てきますが、左端のビットは左へシフトすると上の行の右端へ移動してしまうのです。

...
01000110
10110000
...

を左へ1シフトすると

...
10001101
0110000?
...

となります。(?は下の行の状態によって変わります。最下行なら0が来ます。)

これを防がなければいけません。

上で解説した手順をよく見ると、左シフトの計算には(最後以外)必ず「白とビットANDを取る」という計算があります。ですので、もし白のh列(右端列)がすべて0なら、この繰り上がりは0と&を取られるので必ず0になってくれます。ありがたいです。

ですが、右端に白石(敵石)がある場合はどうしましょう。

最終的にtに入るのは「右方向にひっくり返される可能性のある白石」です。ということは、端列の石は絶対にtに関係ありません。(端列の石は横方向にひっくり返されない)

ということで、実は、最初に「端を除く白石」を表すビットボードを求め、これを「白」として用いることで繰り上がりの問題を解決できるのです。(ちょっと説明雑です)

端を除く白石のビットボードは、白石のビットボードと、「端列(a列とh列)のみすべて0、そのほかの列ではすべて1」であるビットボードとビットANDを取れば求められます。(このように、残したい部分だけ1で消したい部分は0であるようなビットボードをビットマスクと言い、マスクと&をとる操作を「マスクを取る」とか「マスクをかける」とか言います。)

マスクは

01111110
01111110
...

なので、十六進数では、4ビットずつ考えて0x7e7e7e7e7e7e7e7eとなります。(0xが十六進数のサイン。0111が7で1110がeです。)

したがって、右方向に石をひっくり返せる場所を表すビットボードは以下のコードで得られます。

/(/ 合法手を生成する関数
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に追加する
	valid |= blank & (t << 1);

	/**
	 * 他の方向
	 */
	return valid;
}

引数についてるconstは、「ポインタで受け取るけどboardの中身を変えないよ」という意味です。バグが発生したときに原因の特定を楽にするためです。関数名のGenはGenerate(生成する)の略です。

これと同じ操作(マスクを作って敵石にマスクをかけて、ビット操作を繰り返す)を残り7方向についても行うと、ソースコードは以下になります。

// 合法手を生成する関数
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;
}

この関数を、前回までのソースコードに追加すると、全体はこのようになります。

#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);		// 合法手を生成する関数

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){
	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;
}

// 合法手を生成する関数
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;
}

これでようやく、合法判定が行えるようになりました。main関数の手を打つループで判定を行っています。

手としてf5を入力すると打たれますが、a1などを入力すると「非合法手です。」と表示されます。

ちなみに、合法判定のif文の条件文に pos & valid == 0 と書いてはいけません。ビットANDの&よりも合同判定の==の方が優先順位が高いので、これだとvalid == 0が先に判断され、偽なので0になり、posと0の&を取ると0のままで、if(0)になるので絶対に条件が通らなくなります。(優先順位一覧はこちら→http://www.bohyoh.com/CandCPP/C/operator.html

ところで、このGenValidMove()関数では、せいぜい5回のループが8個あるぐらいで、計算数は100もありません。しかし、この計算で全64マスについて8方向(辺は5方向、角は3方向)についてひっくり返せるかを調べたのと同じことになります。

これが「ビットパラレル」(全てのビットを並列に処理できる)という、ビットボードの利点です。強いAIには高速な計算が必要不可欠ですので、最近ではかなり多くの将棋・チェスプログラムで採用されています。

221行ですか。結構長くなりましたね。でもまだ遊べないんですよね。ひっくり返せないので。

ということで、次回はひっくり返す処理を作りましょうか。内容は今回のGenValidMove()関数と似ています。ビット操作である方向にひっくり返る石を探して、全方向についてビットORを取るのです。そしてひっくり返す処理自体はビットボードの特性を利用します。お楽しみに。

では。

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

シェアする

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

フォローする