オセロ終盤の探索をちょっと高速化する手法

edaxというオセロソフトのソースコードをガチャガチャいじって遊んでいたのですが、いろいろわかって満足したので忘れる前に書いておきます。

探索アルゴリズムの基本的な説明

最初なので基本的というか、将棋ソフトとかと共通していてedaxでも使われているキーワードを書いておきます。

ミニマックス探索

ゲームの局面をノードとして合法手を有向エッジとする木をゲーム木と呼びます。ゲーム木の葉ノードでは最終スコアが得られます。勝ち負けだけに興味があるなら「先手の勝ちは+1、引き分けは0、後手の勝ちは-1」とか、適当にスコアに換算します。ゼロサムゲームなので、先手はスコアを高くしたいのと同様に後手はスコアを低くしたいと考えるでしょう。

子ノードの最終スコアが全て判明しているような内部ノードにおいて、それが先手の手番ならばスコア最大の子に行くエッジを選びます。後手は最小のエッジを選びます。すると深さ優先探索によって任意のノードの最終スコアが得られます。これをミニマックス探索と呼びます。

アルファベータ法

深さ優先探索において、n手目(n≧2)を読むとき(i.e.内部ノードを通りがけるとき)には1~(n-1)手目の厳密解がわかっているので、それらの最大スコアを超えられないことが判明した時点でn手目の探索を打ち切ることができます。これをアルファベータ法と呼びます。最良計算量はミニマックス探索の平方根です。ただしそれを達成するためには最善手を最初に探索する必要があります。(これは無茶振りでして、最善手が既知ならそもそも探索する必要はありません)逆に最悪計算量となるのはスコアが小さい順に探索した場合で、そのオーダーはミニマックス探索のと同じです。

scout法

アルファベータ法のアルファとベータの値の差を1にして(α+1=β)探索すると、最終スコアがα以下かβ以上のどちらなのかを高速に判定できます。これをNull Window Search(NWS)と呼びます。2手目以降はまずNWSして、n-1手目までの最大スコアを超えるとわかった場合のみ通常の探索をするわけです。これをscout法とかPrincipal Variation Search(PVS)とか呼びます。

aspiration search

アルファとベータの差を適切に小さい値にすると、その範囲外の超悪手とかは高速に枝刈りされます。しかも、最終結果の値が(α、β)の区間内だった場合は厳密解であることが保証されます。この探索手法をaspiration searchと呼びます。区間外だった場合は区間を広げて再探索します。

transposition table

transpositionとは、原義では「異なる棋譜によって同じ局面に到達すること」を意味します。つまりゲーム木が木ではなくDAGになっている状態のことです。その場合、深さ優先探索でとある内部ノードの厳密解が求まったとき、帰りがけにその値をハッシュテーブルに書き込んでおいて、またその局面に到達したときにテーブルの値を引けば再探索を省略できるわけです。このハッシュテーブルをtransposition tableと呼びます。日本語では置換表と呼ばれています。

iterative deepening

置換表にスコアだけでなく最善手も書き込んでおくこともできます。すると、深く探索する前にあらかじめ浅く探索しておいて有望な手を保存し、深く探索するときにその手を優先するというテクニックが可能になります。これはアルファベータ法の「最善手を最初に探索せよ」という無茶振りへの実用的な答えになっています。iterative deepeningとか反復深化深さ優先探索とか呼ばれています。ちなみに、これをやりつつ再探索を省略するやつもやる場合、完全読みの完全性を保証するためには、スコアの根拠となる探索深さも書き込んでおく必要があります。

評価関数

浅く読むということは、ゲームの途中の局面で探索を打ち切るということです。このときは最終スコアが得られないので、代わりとして局面のスナップショットを入力すると完全読み結果の予測値を返す関数が必要になります。これは(静的)評価関数と呼ばれています。edaxでは石の局所的な配置パターンを素性ベクトルとして重み付き線形和を計算しています。

ちょっと面白い関数

search_solve_3は、3箇所が空いている局面を受け取って厳密解を返す関数です。オセロ特有のテクニックが2つ使われています。

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

static int search_solve_3(Search *search, const int alpha)
{
	Board *board = search->board;
	Board next[1];
	SquareList *empty = search->empties->next;
	int x1 = empty->x;
	int x2 = (empty = empty->next)->x;
	int x3 = empty->next->x;
	register int score, bestscore;
	const int beta = alpha + 1;

	SEARCH_STATS(++statistics.n_search_solve_3);
	SEARCH_UPDATE_INTERNAL_NODES();

	// parity based move sorting
	if (!(search->parity & QUADRANT_ID[x1])) {
		if (search->parity & QUADRANT_ID[x2]) { // case 1(x2) 2(x1 x3)
			int tmp = x1; x1 = x2; x2 = tmp;
		} else { // case 1(x3) 2(x1 x2)
			int tmp = x1; x1 = x3; x3 = x2; x2 = tmp;
		}
	}

	// best move alphabeta search
	if ((NEIGHBOUR[x1] & board->opponent) && board_next(board, x1, next)) {
		bestscore = -board_solve_2(next, -beta, x2, x3, search);
		if (bestscore >= beta) return bestscore;
	} else bestscore = -SCORE_INF;

	if ((NEIGHBOUR[x2] & board->opponent) && board_next(board, x2, next)) {
		score = -board_solve_2(next, -beta, x1, x3, search);
		if (score >= beta) return score;
		else if (score > bestscore) bestscore = score;
	}

	if ((NEIGHBOUR[x3] & board->opponent) && board_next(board, x3, next)) {
		score = -board_solve_2(next, -beta, x1, x2, search);
		if (score > bestscore) bestscore = score;
	}

	// pass ?
	if (bestscore == -SCORE_INF) {
		// best move alphabeta search
		if ((NEIGHBOUR[x1] & board->player) && board_pass_next(board, x1, next)) {
			bestscore = board_solve_2(next, alpha, x2, x3, search);
			if (bestscore <= alpha) return bestscore;
		} else bestscore = SCORE_INF;

		if ((NEIGHBOUR[x2] & board->player) && board_pass_next(board, x2, next)) {
			score = board_solve_2(next, alpha, x1, x3, search);
			if (score <= alpha) return score;
			else if (score < bestscore) bestscore = score;
		}

		if ((NEIGHBOUR[x3] & board->player) && board_pass_next(board, x3, next)) {
			score = board_solve_2(next, alpha, x1, x2, search);
			if (score < bestscore) bestscore = score;
		}

		// gameover
		if (bestscore == SCORE_INF) bestscore = board_solve(board, 3);
	}

 	assert(SCORE_MIN <= bestscore && bestscore <= SCORE_MAX);
	return bestscore;
}

ひとつはparity based move sortingです。まず前提として、オセロの終盤では離れて孤立した空白マスに打つのは一般に有望な手です。なぜなら、それでひっくり返した石を相手が取り戻すのは多くの場合不可能だからです。そこで、edaxではオセロ盤面を4つの"象限"に分割して、各象限の空きマスの数の偶奇を常に保持しています。偶奇だけ保持することで計算を軽くできます。そして最終盤では、「空きマス数が奇数であるような象限の中の空きマス」を先に探索します。(偶数の象限を後回しにするとも言えます)なぜなら、合計3マス空きのとき偶数の象限には(空きがあるならば)必ず2箇所の空きがあり、密な可能性が高いからです。

ふたつめはNEIGHBOURというビットマスクです。手を探索する前にそれが本当に合法手なのか(=そこに打ったときにひっくり返る石があるのか)確かめる必要がありますが、しかし合法手生成やflipは比較的重いのが問題です。なので、絶対にひっくり返せないケースを高速に検出してスクリーニングできれば有用です。そのためにedaxでは、座標xの8近傍のビットだけが立っているビットボードの配列 NEIGHBOUR を用意していて、NEIGHBOUR[x] と相手の石のビットボードとのandが非ゼロかどうかでスクリーニングしています。空きマスの8近傍に相手の石がなければ、明らかに何もひっくり返せないので非合法手だと言えるわけです。

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

/** Conversion array: neighbour bits */
const unsigned long long NEIGHBOUR[] = {
	0x0000000000000302ULL, 0x0000000000000705ULL, 0x0000000000000e0aULL, 0x0000000000001c14ULL,
	0x0000000000003828ULL, 0x0000000000007050ULL, 0x000000000000e0a0ULL, 0x000000000000c040ULL,
	0x0000000000030203ULL, 0x0000000000070507ULL, 0x00000000000e0a0eULL, 0x00000000001c141cULL,
	0x0000000000382838ULL, 0x0000000000705070ULL, 0x0000000000e0a0e0ULL, 0x0000000000c040c0ULL,
	0x0000000003020300ULL, 0x0000000007050700ULL, 0x000000000e0a0e00ULL, 0x000000001c141c00ULL,
	0x0000000038283800ULL, 0x0000000070507000ULL, 0x00000000e0a0e000ULL, 0x00000000c040c000ULL,
	0x0000000302030000ULL, 0x0000000705070000ULL, 0x0000000e0a0e0000ULL, 0x0000001c141c0000ULL,
	0x0000003828380000ULL, 0x0000007050700000ULL, 0x000000e0a0e00000ULL, 0x000000c040c00000ULL,
	0x0000030203000000ULL, 0x0000070507000000ULL, 0x00000e0a0e000000ULL, 0x00001c141c000000ULL,
	0x0000382838000000ULL, 0x0000705070000000ULL, 0x0000e0a0e0000000ULL, 0x0000c040c0000000ULL,
	0x0003020300000000ULL, 0x0007050700000000ULL, 0x000e0a0e00000000ULL, 0x001c141c00000000ULL,
	0x0038283800000000ULL, 0x0070507000000000ULL, 0x00e0a0e000000000ULL, 0x00c040c000000000ULL,
	0x0302030000000000ULL, 0x0705070000000000ULL, 0x0e0a0e0000000000ULL, 0x1c141c0000000000ULL,
	0x3828380000000000ULL, 0x7050700000000000ULL, 0xe0a0e00000000000ULL, 0xc040c00000000000ULL,
	0x0203000000000000ULL, 0x0507000000000000ULL, 0x0a0e000000000000ULL, 0x141c000000000000ULL,
	0x2838000000000000ULL, 0x5070000000000000ULL, 0xa0e0000000000000ULL, 0x40c0000000000000ULL,
	0, 0 // <- hack for passing move & nomove
};

しかし、よく考えると8近傍に相手の石があってもなお、明らかに何もひっくり返せないケースは存在します。

f:id:eukaryo:20200426024507p:plain

例えばこの図(黒の手番だとします)で、D2の8近傍には3つの白石がありますが、これはひっくり返せません。NEIGHBOURのスクリーニングが偽陽性になる例です。しかし「外周の石は絶対にひっくり返せない」とは限らなくて、H2に打てばH3をひっくり返せます。じゃあ「外周の空白ますに打てば外周の石をひっくり返せる」というわけでも必ずしもなく、H2はH1とG1をひっくり返せません。

結論を直観的に言うと、空白マスからある8近傍のマスを見たときの位置関係が、「相手の真後ろに壁があるように見える」形になっている場合は絶対にひっくり返せません。そういう位置関係をビットマスクから除外すると以下のようになります。edaxのNEIGHBOURをこれに差し替えるとほんの少しだけ速くなります。

const uint64_t NEIGHBOUR_WITHOUT_KABEDON[] = {
	0x0000000000000302ULL, 0x0000000000000604ULL, 0x0000000000000e0aULL, 0x0000000000001c14ULL,
	0x0000000000003828ULL, 0x0000000000007050ULL, 0x0000000000006020ULL, 0x000000000000c040ULL,
	0x0000000000030200ULL, 0x0000000000060400ULL, 0x00000000000e0a00ULL, 0x00000000001c1400ULL,
	0x0000000000382800ULL, 0x0000000000705000ULL, 0x0000000000602000ULL, 0x0000000000c04000ULL,
	0x0000000003020300ULL, 0x0000000006040600ULL, 0x000000000e0a0e00ULL, 0x000000001c141c00ULL,
	0x0000000038283800ULL, 0x0000000070507000ULL, 0x0000000060206000ULL, 0x00000000c040c000ULL,
	0x0000000302030000ULL, 0x0000000604060000ULL, 0x0000000e0a0e0000ULL, 0x0000001c141c0000ULL,
	0x0000003828380000ULL, 0x0000007050700000ULL, 0x0000006020600000ULL, 0x000000c040c00000ULL,
	0x0000030203000000ULL, 0x0000060406000000ULL, 0x00000e0a0e000000ULL, 0x00001c141c000000ULL,
	0x0000382838000000ULL, 0x0000705070000000ULL, 0x0000602060000000ULL, 0x0000c040c0000000ULL,
	0x0003020300000000ULL, 0x0006040600000000ULL, 0x000e0a0e00000000ULL, 0x001c141c00000000ULL,
	0x0038283800000000ULL, 0x0070507000000000ULL, 0x0060206000000000ULL, 0x00c040c000000000ULL,
	0x0002030000000000ULL, 0x0004060000000000ULL, 0x000a0e0000000000ULL, 0x00141c0000000000ULL,
	0x0028380000000000ULL, 0x0050700000000000ULL, 0x0020600000000000ULL, 0x0040c00000000000ULL,
	0x0203000000000000ULL, 0x0406000000000000ULL, 0x0a0e000000000000ULL, 0x141c000000000000ULL,
	0x2838000000000000ULL, 0x5070000000000000ULL, 0x2060000000000000ULL, 0x40c0000000000000ULL,
	0, 0 // <- hack for passing move & nomove
};

面白かったポイントは他にもあるのでたぶん続きます。