逆向きに全探索する

前回の記事では合法手の数が34通りあるようなオセロの局面を生成しましたが、あれは初期局面から到達可能かどうかを考慮していませんでした。初期局面から到達可能で、かつ合法手の数が34通りあるような局面は存在するのでしょうか？　いっぱい存在すると期待してとりあえず試してみましたが、結果的には見つかりませんでした。

github.com

z3で局面を列挙する

z3は答えが充足可能のときその具体例を1個出力してくれます。なので、「既知の解とは異なっていなければならない」みたいな制約を追加して再計算させることで別解を1個ずつ得ていくことができます。これは本当はばかげた方法でして、列挙機能をもつソルバーもありますが、今回はとりあえずこの方法で1600個の解を生成しました。1600に意味はありませんが、1個目から1600個目まで全て数秒おきに生成されてきて、解の総数は莫大なのかもしれないと思い適当に打ち切りました。

初期局面から到達可能な序盤を全列挙する

得た34箇所空き(=26手目)とかの局面から逆向きに深さ優先探索して初期局面に到達できるかを調べたいわけですが、その前に半分全列挙の要領で序盤側を全列挙したほうが良いと考えました。初期局面から深さ優先探索して、盤上の石がn個でかつ石を置く合法手が存在する局面を、対称な局面を同一視しつつstd::set < std::array < uint64_t , 2 > >にinsertしました。「石を置く合法手が存在する」というのは、その時点でwipeoutされていたりパスせざるを得ない局面は（今回の目的から考えて不要なので）除くという意味です。対称な局面を同一視する方法は、edaxではboard_unique関数が提供しています。

https://github.com/abulmo/edax-reversi/blob/master/src/board.c

int board_unique(const Board *board, Board *unique)
{
	Board sym;
	int i, s = 0;

	assert(board != unique);

	*unique = *board;
	for (i = 1; i < 8; ++i) {
		board_symetry(board, i, &sym);
		if (board_compare(&sym, unique) < 0) {
			*unique = sym;
			s = i;
		}
	}

	board_check(unique);
	return s;
}

board_symetryは第2引数に応じて転置と上下左右の反転をやる関数で、board_compareは盤面を128bit変数とみなして比較する関数です。C++ではないので比較演算子のオーバーロードとかはできません。対称な局面たちのうち最も順番が若い局面を返すわけです。

結果として、序盤の局面数は以下の通りでした。

盤上の石の数	局面数
5	1
6	3
7	14
8	60
9	322
10	1773
11	10649
12	67245
13	433993
14	2958551
15	19785690

逆向きに深さ優先探索する

これをやるときに新しく作る必要がある部品は、flip関数の逆版みたいなやつです。flipはある座標に石を置くことでひっくり返る石を求めるものですが、逆に「直前に相手がここに置いたことで現在の局面になったとしたら、その着手でどの石がひっくり返ったと考えられるか？」という問いに全列挙で答えるやつです。ナイーブに実装すると以下のようになります。

//posはopponentの石の座標を示しているとする。
//現在局面がplayerの手番だとして、それが「直前にopponentがposに石を置いたからこうなった」と仮定したときに、
//その着手によってひっくり返った石のビットボードとしてありうるものを列挙してresultに入れる。個数を返り値とする。
//ただし返り値が非ゼロのときresult[0]=0で、これは便宜上そうしているだけ。返り値はこれを含めているので1引くべし。
int retrospective_flip(uint64_t pos, uint64_t player, uint64_t opponent, std::array<uint64_t, 10000> &result) {

	assert(pos < 64);
	assert((1ULL << pos) & opponent);
	assert(((1ULL << pos) & 0x0000001818000000ULL) == 0);

	int answer = 0;

	const int xpos = pos % 8;
	const int ypos = pos / 8;

	//上方向
	if(ypos >= 2){
		int length = 0;
		while (1) {
			if ((1ULL << (pos - ((length + 1) * 8))) & opponent)++length;
			else break;
			if (length == ypos)break;
		}

		//この時点で、上方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//上方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			result[0] = 0;
			answer = 1;
			for (int i = 1; i < length; ++i) {
				result[answer] = result[answer - 1] | (1ULL << (pos - (i * 8)));
				++answer;
			}
		}
	}

	//下方向
	if (ypos < 6) {
		int length = 0;
		while (1) {
			if ((1ULL << (pos + ((length + 1) * 8))) & opponent)++length;
			else break;
			if (length == 7 - ypos)break;
		}

		//この時点で、下方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//下方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			if (answer == 0) {
				result[0] = 0;
				answer = 1;
				for (int i = 1; i < length; ++i) {
					result[answer] = result[answer - 1] | (1ULL << (pos + (i * 8)));
					++answer;
				}
			}
			else {
				const int old_answer = answer;
				uint64_t direction = 0;
				for (int i = 1; i < length; ++i) {
					direction |= (1ULL << (pos + (i * 8)));
					for (int j = 0; j < old_answer; ++j) {
						result[answer++] = result[j] | direction;
					}
				}
			}
		}
	}

	//右方向(最下位ビットが右上で、横に連続しているとして。これはA1～H1などといったオセロの記法とは左右反転している。以下同様)
	if (xpos >= 2) {
		int length = 0;
		while (1) {
			if ((1ULL << (pos - (length + 1))) & opponent)++length;
			else break;
			if (length == xpos)break;
		}

		//この時点で、右方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//右方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			if (answer == 0) {
				result[0] = 0;
				answer = 1;
				for (int i = 1; i < length; ++i) {
					result[answer] = result[answer - 1] | (1ULL << (pos - i));
					++answer;
				}
			}
			else {
				const int old_answer = answer;
				uint64_t direction = 0;
				for (int i = 1; i < length; ++i) {
					direction |= (1ULL << (pos - i));
					for (int j = 0; j < old_answer; ++j) {
						result[answer++] = result[j] | direction;
					}
				}
			}
		}
	}

	//左方向
	if (xpos < 6) {
		int length = 0;
		while (1) {
			if ((1ULL << (pos + (length + 1))) & opponent)++length;
			else break;
			if (length == 7 - xpos)break;
		}

		//この時点で、左方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//左方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			if (answer == 0) {
				result[0] = 0;
				answer = 1;
				for (int i = 1; i < length; ++i) {
					result[answer] = result[answer - 1] | (1ULL << (pos + i));
					++answer;
				}
			}
			else {
				const int old_answer = answer;
				uint64_t direction = 0;
				for (int i = 1; i < length; ++i) {
					direction |= (1ULL << (pos + i));
					for (int j = 0; j < old_answer; ++j) {
						result[answer++] = result[j] | direction;
					}
				}
			}
		}
	}

	//右上方向
	if (xpos >= 2 && ypos >= 2) {
		int length = 0;
		while (1) {
			if ((1ULL << (pos - ((length + 1) * 9))) & opponent)++length;
			else break;
			if (length == std::min(xpos, ypos))break;
		}

		//この時点で、右上方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//右上方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			if (answer == 0) {
				result[0] = 0;
				answer = 1;
				for (int i = 1; i < length; ++i) {
					result[answer] = result[answer - 1] | (1ULL << (pos - (i * 9)));
					++answer;
				}
			}
			else {
				const int old_answer = answer;
				uint64_t direction = 0;
				for (int i = 1; i < length; ++i) {
					direction |= (1ULL << (pos - (i * 9)));
					for (int j = 0; j < old_answer; ++j) {
						result[answer++] = result[j] | direction;
					}
				}
			}
		}
	}

	//左下方向
	if (xpos < 6 && ypos < 6) {
		int length = 0;
		while (1) {
			if ((1ULL << (pos + ((length + 1) * 9))) & opponent)++length;
			else break;
			if (length == std::min(7 - xpos, 7 - ypos))break;
		}

		//この時点で、左下方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//左下方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			if (answer == 0) {
				result[0] = 0;
				answer = 1;
				for (int i = 1; i < length; ++i) {
					result[answer] = result[answer - 1] | (1ULL << (pos + (i * 9)));
					++answer;
				}
			}
			else {
				const int old_answer = answer;
				uint64_t direction = 0;
				for (int i = 1; i < length; ++i) {
					direction |= (1ULL << (pos + (i * 9)));
					for (int j = 0; j < old_answer; ++j) {
						result[answer++] = result[j] | direction;
					}
				}
			}
		}
	}

	//左上方向
	if (xpos < 6 && ypos >= 2) {
		int length = 0;
		while (1) {
			if ((1ULL << (pos - ((length + 1) * 7))) & opponent)++length;
			else break;
			if (length == std::min(7 - xpos, ypos))break;
		}

		//この時点で、左上方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//左上方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			if (answer == 0) {
				result[0] = 0;
				answer = 1;
				for (int i = 1; i < length; ++i) {
					result[answer] = result[answer - 1] | (1ULL << (pos - (i * 7)));
					++answer;
				}
			}
			else {
				const int old_answer = answer;
				uint64_t direction = 0;
				for (int i = 1; i < length; ++i) {
					direction |= (1ULL << (pos - (i * 7)));
					for (int j = 0; j < old_answer; ++j) {
						result[answer++] = result[j] | direction;
					}
				}
			}
		}
	}

	//右下方向
	if (xpos >= 2 && ypos < 6) {
		int length = 0;
		while (1) {
			if ((1ULL << (pos + ((length + 1) * 7))) & opponent)++length;
			else break;
			if (length == std::min(xpos, 7 - ypos))break;
		}

		//この時点で、右下方向にlength個の連続したopponentの石があると判明している。

		if (length >= 2) {

			//右下方向に0～(length-1)個の石をひっくり返したという可能性があるので、それらのビットボードを格納しておく。

			if (answer == 0) {
				result[0] = 0;
				answer = 1;
				for (int i = 1; i < length; ++i) {
					result[answer] = result[answer - 1] | (1ULL << (pos + (i * 7)));
					++answer;
				}
			}
			else {
				const int old_answer = answer;
				uint64_t direction = 0;
				for (int i = 1; i < length; ++i) {
					direction |= (1ULL << (pos + (i * 7)));
					for (int j = 0; j < old_answer; ++j) {
						result[answer++] = result[j] | direction;
					}
				}
			}
		}
	}

	return answer;
}

答えの総数は最大で5759です。例えば「C4だけが空いている局面で、相手がC4に置くと全部相手の石になる局面」は5760通りあります。（うち一つは63個全部相手の石なので置けない）そう考えると、26手目(=34箇所空き)から逆向き探索して11手目(=盤上の石が15個)まで全探索できるか怪しい気がしますが、実際試したところすぐに計算完了しました。

あと必須ではないのですが、逆向き探索で盤上の石が除かれていくときに、孤立した石が生じた場合はその時点で到達不可能として枝刈りできます。

//bがオセロの置かれている石のビットボードだとして、すべての石たちが8近傍で連結しているか調べる。しているならtrue、いないならfalseを返す。
bool IsConnected(const uint64_t b) {

	uint64_t mark = 0x0000'0018'1800'0000ULL, old_mark = 0;

	assert((b & mark) == mark);

	//真ん中4つの石にマークをつけたとして、マークがついている石の8近傍の石にマークをつける。変化しなくなれば終了。
	while (mark != old_mark) {
		old_mark = mark;
		uint64_t new_mark = mark;
		new_mark |= b & ((mark & 0xFEFE'FEFE'FEFE'FEFEULL) >> 1);
		new_mark |= b & ((mark & 0x7F7F'7F7F'7F7F'7F7FULL) << 1);
		new_mark |= b & ((mark & 0xFFFF'FFFF'FFFF'FF00ULL) >> 8);
		new_mark |= b & ((mark & 0x00FF'FFFF'FFFF'FFFFULL) << 8);
		new_mark |= b & ((mark & 0x7F7F'7F7F'7F7F'7F00ULL) >> 7);
		new_mark |= b & ((mark & 0x00FE'FEFE'FEFE'FEFEULL) << 7);
		new_mark |= b & ((mark & 0xFEFE'FEFE'FEFE'FE00ULL) >> 9);
		new_mark |= b & ((mark & 0x007F'7F7F'7F7F'7F7FULL) << 9);

		mark = new_mark;
	}

	//すべての石が8近傍で連結していれば、このやり方ですべての石にマークをつけられる。
	return mark == b;
}

結果

合法手が34手ある局面を1600通り生成し、452通りのuniqueな局面が得られましたが、すべて初期局面から到達不可能でした。もっと頑張っていっぱい生成すれば到達可能局面が得られる可能性はあります。それ以外の方向性としては、解の総数の数え上げをまず試みるとか、flip関数を分岐不要で書き下せば到達可能性を含めてソルバーに投げられるかもしれないとかが考えられます。