リバーシの探索を色々試してみた

2020年12月22日2020年12月23日

モンテカルロ法

はじめαβ法を試したがうまく動かなかった。すぐ角を取れてしまう。きっとコードが間違っている。αβ法を諦めモンテカルロ法を試した。300回ランダムに最後まで指して石の数の差を評価値とした。やはりすぐ角を取れてしまう。300回程度では弱い。試す回数が桁違いに少ないようだ。候補手から角の方を削除してみた。弱い。

モンテカルロ法のコードのイメージはこんな感じ。playerは次の番の石のbitboard、opponentはplayerの相手の石のbitboard

// 探索
Search()
{
	// 候補手をすべて求める
	candidates = GetCandidates(player, opponet);

	// 候補手のそれぞれ評価する
	for (candidate in candidates) {
		// 候補手のひとつを打ち、石を反転させ、相手が次のプレイヤーに
		[nextOppnent, nextPlayer] = Reverse(candidate, player, oppoent);
		for (評価する回数) {
			評価結果[評価手のひとつ] += -Montecarlo(nextPlayer, nextOppnent, false);
		}
	}
	候補手の中で評価結果が最大のものを次の手とする。
}
Montecarlo(player, opponent, pass)
{
	//候補手を求める
	candidates = GetCandidates(player, opponent);

	if (candidates == 0) {
		// 候補手がない
		if (pass) {
			//双方がパスなので評価値を返す石の数の差、あるいは勝ち負け等を評価値とする
			return CountDiscs(player) - CountDiscs(opponent);
			あるいは、playerが勝ちなら1,opponentが勝ちなら-1,引き分けなら0を返す。
		} else {
			//パスなので相手の番
			// 石の配置が換わってないのでplayerとopponentを入れ替えて再帰呼び出し
			return -Montecarlo(opponent, player, true);
		}
	} else {
		// 候補手あり
		候補手のうちランダムで次の手を決める
		[nextOpponent, nextPlayer] = Reverse(ランダムで決めた手, player, opponent);
		// 次の番(再帰呼び出し)
		return -Montecalro(nextPlayer, nextOppoinet, false);
	}
}

4×4完全解析

探索の何が悪いのか分からなかったので小さなモデルで完全解析を試してみた。参考にしたのは次のページ。

NegaMax法で参考にしたページの通り動いた。コードイメージはこんな感じ。

// 探索
Search()
{
	// 候補手をすべて求める
	candidates = GetCandidates(player, opponet);

	// 候補手のそれぞれ評価する
	for (candidate in candidates) {
		// 候補手のひとつを打ち、石を反転させ、相手が次のプレイヤーに
		[nextOppnent, nextPlayer] = Reverse(candidate, player, oppoent);
		評価結果[評価手のひとつ] = -NegaMax(nextPlayer, nextOppnent, false);
	}
	候補手の中で評価結果が最大のものを次の手とする。
}
NegaMax(player, opponent, pass)
{
	//候補手を求める
	candidates = GetCandidates(player, opponent);

	if (candidates == 0) {
		// 候補手がない
		if (pass) {
			//双方がパスなので評価値を返す石の数の差、あるいは勝ち負け等を評価値とする
			評価値 = CountDiscs(player) - CountDiscs(opponent);
			空きがあったら勝者に加算する。
			return 評価値;
		} else {
			//パスなので相手の番
			// 石の配置が換わってないのでplayerとopponentを入れ替えて再帰呼び出し
			return -NegaMax(opponent, player, true);
		}
	} else {
		// 候補手あり
		maxVal = -大きな値
		for (candidate in candidates) {
			[nextOpponent, nextPlayer] = Reverse(候補手のひとつ, player, opponent);
			// 次の番(再帰呼び出し)
			maxVal = Max(maxValue, -NegaMax(nextPlayer, nextOppoinet, false));
		}
		return maxVal;
	}
}

4×4では必要ないが早くするためにαβ法でも試してみた。NegaMax法と同じ結果になった。コードイメージはこんな感じ。

// 探索
Search()
{
	// 候補手をすべて求める
	candidates = GetCandidates(player, opponet);

	// 候補手のそれぞれ評価する
	for (candidate in candidates) {
		// 候補手のひとつを打ち、石を反転させ、相手が次のプレイヤーに
		[nextOppnent, nextPlayer] = Reverse(candidate, player, oppoent);
		α = -大きな値;
		β = 大きな値;
		評価結果[評価手のひとつ] = -AlphaBeta(nextPlayer, nextOppnent, false, α, β);
	}
	候補手の中で評価結果が最大のものを次の手とする。
}
AlphaBeta(player, opponent, pass, α, β)
{
	//候補手を求める
	candidates = GetCandidates(player, opponent);

	if (candidates == 0) {
		// 候補手がない
		if (pass) {
			//双方がパスなので評価値を返す石の数の差、あるいは勝ち負け等を評価値とする
			評価値 = CountDiscs(player) - CountDiscs(opponent);
			空きがあったら勝者に加算する。
			return 評価値;
		} else {
			//パスなので相手の番
			// 石の配置が換わってないのでplayerとopponentを入れ替えて再帰呼び出し
			return -AlphaBeta(opponent, player, true, -β, -α);
		}
	} else {
		// 候補手あり
		for (candidate in candidates) {
			[nextOpponent, nextPlayer] = Reverse(候補手のひとつ, player);
			// 次の番(再帰呼び出し)
			α = Max(α, -AlphaBeta(nextPlayer, nextOppoinet, false, -β, -α));
			if (α >= β) {
				// αカット：残りの候補手を評価しない。
				return α;
			}
		}
		return α;
	}
}

αβ法

4×4のαβ法が動いたので8×8でも試してみた。完全解析ではないので石の差とは違う評価が必要だ。評価関数は4手先の配置のみ。おぉ、動いた。やはり最初のαβ法のコードは間違っていた。すぐには角が取れない。コードイメージはこんな感じ。

// 探索
Search()
{
	// 候補手をすべて求める
	candidates = GetCandidates(player, opponet);

	// 候補手のそれぞれ評価する
	for (candidate in candidates) {
		// 候補手のひとつを打ち、石を反転させ、相手が次のプレイヤーに
		[nextOppnent, nextPlayer] = Reverse(candidate, player, oppoent);
		α = -大きな値;
		β = 大きな値;
		depth = 深さ; // 深さが大きいと時間がかかるので4とか
		評価結果[評価手のひとつ] = -AlphaBeta(nextPlayer, nextOppnent, false, α, β, depth);
	}
	候補手の中で評価結果が最大のものを次の手とする。
}
AlphaBeta(player, opponent, pass, α, β, depth)
{
	if (depth == 0) {
		return 評価関数(player, opponent);
	}

	//候補手を求める
	candidates = GetCandidates(player, opponent);

	if (candidates == 0) {
		// 候補手がない
		if (pass) {
			//双方がパスなので終了
			return 評価関数(player, opponent);
		} else {
			//パスなので相手の番
			// 石の配置が換わってないのでplayerとopponentを入れ替えて再帰呼び出し
			return -AlphaBeta(opponent, player, true, -beta, -β, -α, depth - 1);
		}
	} else {
		// 候補手あり
		for (candidate in candidates) {
			[nextOpponent, nextPlayer] = Reverse(候補手のひとつ, player);
			// 次の番(再帰呼び出し)
			α = Max(α, -AlphaBeta(nextPlayer, nextOppoinet, false, -β, -α, depth - 1));
			if (α >= β) {
				// αカット：残りの候補手を評価しない。
				return α;
			}
		}
		return α;
	}
}
評価関数(player, opponent) 
{
	確定石、石の配置場所、候補手の数等を評価して返す。
}

反復進化探索

反復深化探索を試した。深さ3～1秒内で深さを増やしていく。なので毎回1秒かかる。終盤50手目以降は完全解析。評価関数は角から辺に伸びる確定石、盤位置、候補数を評価値とした。まぁまぁ強くなったが、そんなには強くない。早く手を返すことを求めているのでこんなものかな。コードのイメージはこんな感じ。

// 探索
Search()
{
	// 候補手をすべて求める
	candidates = GetCandidates(player, opponet);

	// 候補手のそれぞれ評価する
	for (candidate in candidates) {
		// 候補手のひとつを打ち、石を反転させ、相手が次のプレイヤーに
		[nextOppnent, nextPlayer] = Reverse(candidate, player, oppoent);
		α = -大きな値;
		β = 大きな値;
		if (手数 < 終盤とする手数) {
			timelimit = Date.now() + 制限とする時間;
			for (depth = 3;; ++depth) {
				try {
					評価結果[評価手のひとつ] = -AlphaBeta(nextPlayer, nextOppnent, false, α, β, depth, timelimit);
				} catch {
					// 今の深さの評価は無視してひとつ前の評価値を使う
					break;
				}
			}
		} else {
			// 終盤は最後まで探索する
			評価結果[評価手のひとつ] = -完全解析用AlphaBeta(nextPlayer, nextOppnent, false, α, β);
		}
	}
	候補手の中で評価結果が最大のものを次の手とする。
}
AlphaBeta(player, opponent, pass, α, β, depth, timelimit)
{
	if (depth == 0) {
		return 評価関数(player, opponent);
	}

	if (Date.now() > timelimit) {
		// 制限時間を越えたので評価をやめる
		throw;
	}

	//候補手を求める
	candidates = GetCandidates(player, opponent);

	if (candidates == 0) {
		// 候補手がない
		if (pass) {
			//双方がパスなので終了
			return 評価関数(player, opponent);
		} else {
			//パスなので相手の番
			// 石の配置が換わってないのでplayerとopponentを入れ替えて再帰呼び出し
			return -AlphaBeta(opponent, player, true, -beta, -β, -α, depth - 1, timelimit);
		}
	} else {
		// 候補手あり
		for (candidate in candidates) {
			[nextOpponent, nextPlayer] = Reverse(候補手のひとつ, player);
			// 次の番(再帰呼び出し)
			α = Max(α, -AlphaBeta(nextPlayer, nextOppoinet, false, -β, -α, depth - 1, timelimit));
			if (α >= β) {
				// αカット：残りの候補手を評価しない。
				return α;
			}
		}
		return α;
	}
}
評価関数(player, opponent) 
{
	確定石、石の配置場所、候補手の数等を評価して返す。
}
完全解析用AlphaBeta(player, oppnent, false, α, β)
{
	// 4x4のAlphaBetaと同じイメージなので略
}