前回に引き続き、マインスイーパーについて書く。今回は、実際に成功確率を計算するところまで実装して、結果を紹介する。
前回の記事:マインスイーパーの初手 (2) - pzdcの雑記
盤面の配列表現
盤面形状の表現
盤面形状を抽象的に表現する場合には、セルどうしの隣接を、関係R(x, y)の形で表現すればよい。隣接関係は、R(x, y)=R(y, x)を仮定する必要もない。今回は抽象化せずに、通常の正方格子の長方形盤面であることを、前提とする。
処理速度を優先するなら可読性の低いこまごまとしたコードにすることも考えられるが、とりあえずは見通しの良い書き方で実装する。まず盤面サイズをクラスにする。
class BoardSize: __slots__ = ('y_size', 'x_size', ) def __init__(self, y_size: int, x_size: int): self.y_size = y_size self.x_size = x_size def __str__(self) -> str: return f'BoardSize({self.y_size}x{self.x_size})' def __repr__(self) -> str: return str(self) def __eq__(self, b: object) -> bool: if not isinstance(b, BoardSize): raise NotImplementedError return ((self.y_size == b.y_size) and (self.x_size == b.y_size))
画像の走査順序の慣例に従って、(y, x)の順序にしている。盤面の左上のセルが(0, 0)で、左下のセルが(y_size - 1, x_size - 1)である。デバッグしやすいように、__str__
と__repr__
を実装している。等号判定できるように__eq__
を実装している。
次にセルを表すクラスを作成する。
class Cell: """正方格子のセル座標を表すクラス. (y, x)で表現(y, xともに整数) """ __slots__ = ('y', 'x', ) def __init__(self, y: int, x: int): self.y = y self.x = x def __str__(self) -> str: return f'Cell({self.y}, {self.x})' def __repr__(self) -> str: return str(self) def __eq__(self, b: object) -> bool: if not isinstance(b, Cell): raise NotImplementedError return ((self.y == b.y) and (self.x == b.x))
先ほどとほぼ同じ。
盤面サイズクラス(BoardSize
)のオブジェクトを受け取って、セルが盤面の内部にあるかどうかを判定するメソッドを追加する。
def is_in_board(self, board_size: BoardSize) -> bool: """次の条件を満たす場合にTrue. 0 <= self.y < board_size.y_size 0 <= self.x < board_size.x_size """ return ( (self.y >= 0) and (self.y < board_size.y_size) and (self.x >= 0) and (self.x < board_size.x_size) )
あるセルの周囲8マスを取得するメソッドを追加する。この時に、盤面サイズを考慮に入れられるようにしておく。
def get_surround_upto8_in_board(self, board_size: BoardSize): cells = [ s for s in self.get_surround_8() if s.is_in_board(board_size) ] return cells def get_surround_8(self): """セルの上下左右斜め8マスを取得. 盤面の内部/外部を考慮しない """ cls = self.__class__ cells = [ # 上下左右 cls(y=self.y - 1, x=self.x), cls(y=self.y + 1, x=self.x), cls(y=self.y, x=self.x - 1), cls(y=self.y, x=self.x + 1), # 斜め cls(y=self.y - 1, x=self.x - 1), cls(y=self.y - 1, x=self.x + 1), cls(y=self.y + 1, x=self.x - 1), cls(y=self.y + 1, x=self.x + 1), ] return cells
セルを、連番と相互変換するメソッドも用意しておく。
def to_id(self, board_size: BoardSize) -> int: """(y, x)を順番に走査するときの連番を返す.""" return self.y * board_size.x_size + self.x @classmethod def from_id(cls, i: int, board_size: BoardSize): """連番から(y, x)セルに戻す""" y = i // board_size.x_size x = i % board_size.x_size return cls(y=y, x=x)
盤面状態の表現
盤面状態は、たくさんメモリに保持する場面が出てきそうなので、軽い表現にしたい。二次元のnumpy配列で表現しよう。numpyの配列をprintした時の向きを踏まえて、axis=0をy、axis=1をxと対応させる。整数型(np.int32)で、値は次のように定める。
class MineConstant: TARGET = -10 UNKNOWN = -1 # reserved 0~8 (number of target surrounding)
ターゲットのあるマスは-10、まだ開いていないマスは-1、数字が出現済みのマスは0~8で表現する。
numpyのbool配列で条件判定を書きたい場面が多い。bool配列をセルのリストに変換できるようにしておく。
class CellListConverter: __slots__ = () @staticmethod def mask2list(board_mask: np.ndarray) -> list[Cell]: # board_mask: np.ndarray, bool, shape (M, N) cells = [ Cell(y=y, x=x) for y, x in np.vstack(np.where(board_mask)).T ] return cells
盤面の状態を保持するクラス(Board
クラス)を次のように定義する。盤面のサイズ情報や、特定の条件を満たすセルを、簡単に取り出せるようにしておく。
class Board: __slots__ = ("values",) def __init__(self, values: np.ndarray): self.values = values def get_size(self) -> BoardSize: return BoardSize( y_size=len(self.values), x_size=len(self.values[0]), ) def mask_info(self) -> np.ndarray: return self.values >= 0 def mask_target(self) -> np.ndarray: return self.values == MineConstant.TARGET def mask_known(self) -> np.ndarray: return (self.values == MineConstant.TARGET) | (self.values >= 0) def mask_unknown(self) -> np.ndarray: return self.values == MineConstant.UNKNOWN def mask_fully_unknown(self) -> np.ndarray: """未確定で、かつ、周囲8マスに数字がない.""" num_known = self.mask_known().astype(np.int64) kernel = np.full((3, 3), fill_value=1) num_known_surround = convolve2d(num_known, kernel, mode="same") mask_fully_unknown = num_known_surround == 0 return mask_fully_unknown def mask_partially_unknown(self) -> np.ndarray: return self.mask_unknown() & ~self.mask_fully_unknown() def info_cells(self) -> list[Cell]: return CellListConverter.mask2list(self.mask_info()) def target_cells(self) -> list[Cell]: return CellListConverter.mask2list(self.mask_target()) def known_cells(self) -> list[Cell]: return CellListConverter.mask2list(self.mask_known()) def unknown_cells(self) -> list[Cell]: return CellListConverter.mask2list(self.mask_unknown()) def cells(self) -> list[Cell]: return CellListConverter.mask2list( np.full_like(self.values, fill_value=True) )
確率計算の実装
API
いよいよ、マインスイーパーを調べるクラスを作る。次のクラスをベースにする(一応基底クラスにする予定だが、APIに従っていればいい、くらいの気持ちである)。
class EvaluatorBase: __slots__ = ( "counter", "total", "board_size", ) def __init__(self, counter, board_size: BoardSize, total: int): """. Args: counter : 解の数を数えるオブジェクト(requires counter.count(X, y)) board_size : 盤面サイズ total : 盤面全体のターゲットの総数 """ self.counter = counter self.total = total self.board_size = board_size def to_Xy(self, board: Board) -> tuple[np.ndarray, np.ndarray]: unknown_cells = board.unknown_cells() info_cells = board.info_cells() target_cells = board.target_cells() cells = board.cells() mask_target = board.mask_target() # 問題を記述する行列・ベクトル(X, y)のかりの # サイズを決める # M: 表出のあるマスの個数が、(最大の)制約の数 # ただし、全体の個数情報の分、1増やす # N: セルの数が、変数の数 M = len(info_cells) + 1 N = len(cells) # 問題を記述する行列・ベクトル(X, y)を作る X = np.zeros((M, N), dtype=np.int32) y = np.zeros(M, dtype=np.int32) for i, info_cell in enumerate(info_cells): # 表出の周りの最大8マス surrounds = info_cell.get_surround_upto8_in_board(self.board_size) # その最大8マスのセルのidを求めてリストにしておく surround_ids = [s.to_id(self.board_size) for s in surrounds] # その最大8マスに、既にあるターゲットの個数を計算 point_mask = np.zeros_like(board.values) point_mask[info_cell.y, info_cell.x] = 1 kernel = np.full((3, 3), fill_value=1) window_mask = convolve2d(point_mask, kernel, mode="same") window_target_sum = np.sum(window_mask & mask_target) # 制約行列Xと、個数ベクトルyに反映する X[i, surround_ids] = 1 y[i] = board.values[info_cell.y, info_cell.x] - window_target_sum # 未知のマス(変数)に対応する列に絞り込む unknown_cell_ids = [u.to_id(self.board_size) for u in unknown_cells] X = X[:, unknown_cell_ids] # 盤面全体でいくつのターゲットがあるかわかっている場合は、 # 既に解明されているターゲットの個数を引いた残りの数を制約に指定 if self.total is not None: X[M - 1, :] = 1 y[M - 1] = self.total - len(target_cells) return X, y def count_solutions(self, board: Board) -> int: ... def evaluate_probability(self, board: Board) -> ProbabilityEvaluatorReturn: ...
評価用のクラス(EvaluatorBase
クラス)は、初期化時にcounter
(前回の記事で作成済みのカウンタクラスオブジェクト)、total
(盤面全体のターゲットの総数)と、board_size
(盤面サイズ)を受け取る。board
(盤面状態)自体は保持しない。board_size
はわざわざ保持しなくてもboard
から計算できるが、繰り返し使用することになるため、メンバ変数に保持させてしまっている。
メソッドto_Xy
で盤面を前回定義した行列表現に変換する。
メソッドcount_solutions
は、与えられた盤面に対して、解の総数を返す。この処理には、前回の記事で作成済みのカウンタの実装を使えば良い。
メソッドevaluate_probability
は、与えられた盤面に対して、成功確率を評価する。結果を次のクラスで返す。
class ProbabilityEvaluatorReturn: __slots__ = ("probability", "cell", "num_solutions") def __init__( self, probability, cell: Optional[Cell] = None, num_solutions: Optional[int] = None, ): self.probability = probability self.cell = cell self.num_solutions = num_solutions
ベースライン実装
前回の記事で書いた数式をそのまま実装する。
class BaselineEvaluator(EvaluatorBase): """マインスイーパー盤面に対して、 解のカウントと、確率評価をする. """ __slots__ = () def count_solutions(self, board: Board) -> int: X, y = self.to_Xy(board) return int(self.counter.count(X, y)) def evaluate_probability(self, board: Board) -> ProbabilityEvaluatorReturn: """最良なアルゴリズムを選択した場合の成功率を計算する 計算結果は、分数(sympy.Rational)で返す 第二引数で理想的なopen位置を返す """ # 次にあけるマスの候補 unknown_cells = board.unknown_cells() if len(unknown_cells) == 0: return ProbabilityEvaluatorReturn( probability=Rational(1, 1), cell=None) # 確率の分母を知るために、現在の解の数を調べておく total_num_patterns = self.count_solutions(board) if total_num_patterns == 0: return ProbabilityEvaluatorReturn( probability=Rational(0, 1), cell=None) if total_num_patterns == 1: return ProbabilityEvaluatorReturn( probability=Rational(1, 1), cell=None) # それぞれの候補を開いた場合の成功率の格納用変数 probabilities = [] for open_cell in unknown_cells: # 今回は成功する確率を計算したいので、 # 直ちに失敗する場合についての計算は不要 # 0~8が出現する可能性だけを考慮すれば良い # 0~8それぞれが出現する確率に、その時の成功率を乗算したものを、 # 総和することで、このopen_cellに対する成功率を求める probability = Rational(0, 1) # 加算用変数 for n_appear in range(9): # まず、nが出現する確率を求める values_alive = board.values.copy() values_alive[open_cell.y, open_cell.x] = n_appear alive_board = Board(values_alive) num_alive = self.count_solutions(alive_board) if num_alive == 0: # nが出現することがないなら、確率寄与は0 continue # 次に、このnの盤面に対する成功率を再帰で計算 prob_alive = self.evaluate_probability(alive_board).probability # かけ合わせて、成功率への寄与を計算 probability += prob_alive * Rational( num_alive, total_num_patterns) probabilities.append(probability) id_best = np.argmax(probabilities) return ProbabilityEvaluatorReturn( probability=probabilities[id_best], cell=unknown_cells[id_best] )
今回は2個のターゲットがある状況を調べる。結果は次の通り:
BoardSize(1x3) (BaselineEvaluator) 0.004316 [sec] (prob=1/3, pos=Cell(0, 0)) BoardSize(1x4) (BaselineEvaluator) 0.027090 [sec] (prob=1/3, pos=Cell(0, 0)) BoardSize(1x5) (BaselineEvaluator) 0.109548 [sec] (prob=2/5, pos=Cell(0, 0)) BoardSize(1x6) (BaselineEvaluator) 0.720469 [sec] (prob=8/15, pos=Cell(0, 2)) BoardSize(2x2) (BaselineEvaluator) 0.026842 [sec] (prob=1/6, pos=Cell(0, 0)) BoardSize(2x3) (BaselineEvaluator) 0.945886 [sec] (prob=1/3, pos=Cell(0, 0)) BoardSize(2x4) (BaselineEvaluator) 64.514103 [sec] (prob=9/28, pos=Cell(0, 0))
2x4以外は、以前に行った手計算による結果と一致している。2x4については一致していない。かなり計算量が多いので、手計算が間違っている可能性も高い。
計算時間を見ると、2x4という非常に小さい盤面でも1分程度を要している。
確定ターゲットの強制配置+安全なマスのみから開く
上の実装の一つの問題は、ターゲットがあることが確定したマスに実際にターゲットを配置する処理を行っていないことである。このせいで、開くマスの候補の中に常にターゲットのあるマスが残り続けてしまう。
また別の問題は、明らかに安全なマスが複数存在する場合に、開く順序を考慮してしまっていることである。例えば、マスaとマスbがともに安全である場合に、aを開いてからbを開くパターンと、bを開いてからaを開くパターンは、確率計算の上で違いがないので、片方だけ考慮すれば良い。
これらの改善の効果を入れるためには、「確定するマス」を特定する必要がある。その処理自体にどれくらいの処理時間が必要になるかが要点である。
ここでは、解の数のカウンタ実装を流用した単純な実装を使ってみる。
def get_solvable_cells(self, board: Board) -> tuple[list[Cell], list[Cell]]: """確定するマスを求める""" info_cells = board.info_cells() target_cells = board.target_cells() cells = board.cells() # 問題を記述する行列・ベクトル(X, y)のかりの # サイズを決める # M: 表出のあるマスの個数が、(最大の)制約の数 # ただし、全体の個数情報の分、1増やす # N: セルの数が、変数の数 M = len(info_cells) + 1 N = len(cells) # 問題を記述する行列・ベクトル(X, y)を作る X = np.zeros((M, N), dtype=np.int32) y = np.zeros(M, dtype=np.int32) for i, info_cell in enumerate(info_cells): # 表出の周りの最大8マス surrounds = info_cell.get_surround_upto8_in_board(self.board_size) # その最大8マスのセルのidを求めてリストにしておく surround_ids = [s.to_id(self.board_size) for s in surrounds] # その最大8マスに、既にあるターゲットの個数を計算 point_mask = np.zeros_like(board.values) point_mask[info_cell.y, info_cell.x] = 1 # 制約行列Xと、個数ベクトルyに反映する X[i, surround_ids] = 1 y[i] = board.values[info_cell.y, info_cell.x] # 盤面全体でいくつのターゲットがあるかわかっている場合は、 # 制約に指定 if self.total is not None: X[M - 1, :] = 1 y[M - 1] = self.total # 未知のマス(変数)に対応する列に絞り込む # 既に表出があるマス(info cells)にはtargetを置けない # 該当の列を消すことで表現できるが、列番号がずれると、solverの # 出力結果の解釈が難しくなる # そこで、列の並びは変更せずに、代わりに制約を追加することで表現する if len(info_cells) > 0: extra_X = np.zeros((len(info_cells), N), dtype=np.int32) for i, info_cell in enumerate(info_cells): extra_X[i, info_cell.to_id(board.get_size())] = 1 extra_y = np.zeros(len(info_cells), dtype=np.int32) X = np.vstack([X, extra_X]) y = np.concatenate([y, extra_y]) # 既にターゲットが入っているマスについても、制約で、強制的に # 入れる必要がある if len(target_cells) > 0: extra_X = np.zeros((len(target_cells), N), dtype=np.int32) for i, target_cell in enumerate(target_cells): extra_X[i, target_cell.to_id(board.get_size())] = 1 extra_y = np.ones(len(target_cells), dtype=np.int32) X = np.vstack([X, extra_X]) y = np.concatenate([y, extra_y]) true_ids, false_ids = self.solver.solve(X, y) return true_ids, false_ids
結果として、true_ids
(ターゲットが置かれるマス)とfalse_ids
(安全なマス)を返す。
確率評価メソッド内では、次のようにしてターゲットのあるマスを潰す。
# たまにshrinkを実行して盤面をきれいにする use_shrink = depth % 5 == 0 if use_shrink: # わかる範囲で解く t_ids, f_ids = self.get_solvable_cells(board) # ターゲットがあることがわかったマスは、ターゲットを置く for t_id in t_ids: t_cell = Cell.from_id(t_id, board.get_size()) board.values[t_cell.y, t_cell.x] = MineConstant.TARGET
また、「安全なマス」がある場合には、そのマス(どれか一つ)を優先するように処理を切り替える。
# もしターゲットがいないとわかるマスが、既知の表出マスの他に # あるようなら、そこを強制的にあける(他の場所は確率計算をしなくても # 結果の確率は変化しない) known_cells = board.known_cells() if use_shrink and (len(f_ids) > len(known_cells)): known_cell_ids = [c.to_id(board.get_size()) for c in known_cells] open_cells = [ Cell.from_id(f_id, board.get_size()) for f_id in f_ids if f_id not in known_cell_ids ] else: open_cells = unknown_cells
工夫したが、処理時間の変化は観察されなかった。この工夫の効果を発揮するためには、さらなる調整が必要そうだ。いずれ再挑戦したいが、この方向性については、いったん忘れることにする。
処理の削減
もっと有効な対策を見つけた。
まず、盤面が長方形で、初手を知りたいなら、対称性を考慮して初手の候補を減らせる。長方形(非正方形)なら約1/4、正方形なら約1/8まで減らせる。
次に、あるマスcを開いたときに出現する数字の候補を、今までは0~8として解析していたが、この数字の取りうる範囲を事前に調べて絞っておくと、かなり速くなった。
最後にあるマスcを開いてnが出現する場合について、解の数n_alive
を調べてから確率を評価していたが、これは二度手間であることに気づいた。確率を評価する際に解の数を調べるので、この処理は一方だけで良い。
これらの3つの対策を施したクラスを用意する。
まず、出現しうる数の範囲は、次のようにして求める。
# 出現しうる最大の数を求める surround_8_in_board = open_cell.get_surround_upto8_in_board( board.get_size() ) n_min = 0 n_max = 0 for surround in surround_8_in_board: if board.values[surround.y, surround.x] == MineConstant.TARGET: n_min += 1 n_max += 1 elif (board.values[surround.y, surround.x] == MineConstant.UNKNOWN): n_max += 1
確率と解の数は、次のようにして同時に計算する。
result = self._evaluate_probability(alive_board) prob_alive = result.probability num_alive = result.num_solutions
対称性の考慮については、今までのevaluate_probability
を_evaluate_probability
にリネームして、入口の関数を次のように定義する。
def evaluate_probability(self, board: Board) -> ProbabilityEvaluatorReturn: # depth=0だけ特別に対称性を考慮した処理を行う # ただし、盤面(長方形)が完全に未確定である場合に限る if not np.all(board.values == MineConstant.UNKNOWN): return self._evaluate_probability(board) # あけるマスの候補の作成範囲 board_size = board.get_size() y_search_max = (board_size.y_size + 1) // 2 x_search_max = (board_size.x_size + 1) // 2 # あけるマスの候補の格納用 search_cells = [] # 正方形の場合は、さらにx>=yの条件を加える is_square = board_size.y_size == board_size.x_size for y in range(y_search_max): for x in range(x_search_max): if is_square and x < y: continue search_cells.append(Cell(y=y, x=x)) # 確率の分母を知るために、現在の解の数を調べておく total_num_patterns = self.count_solutions(board) # それぞれの候補を開いた場合の成功率の格納用変数 probabilities = [] for open_cell in search_cells: # 今回は成功する確率を計算したいので、 # 直ちに失敗する場合についての計算は不要 # 0~8が出現する可能性だけを考慮すれば良い # 0~8それぞれが出現する確率に、その時の成功率を乗算したものを、 # 総和することで、このopen_cellに対する成功率を求める probability = Rational(0, 1) # 加算用変数 # 出現しうる最大の数を求める surround_8_in_board = open_cell.get_surround_upto8_in_board( board.get_size() ) n_min = 0 n_max = 0 for surround in surround_8_in_board: if board.values[surround.y, surround.x] == MineConstant.TARGET: n_min += 1 n_max += 1 elif (board.values[surround.y, surround.x] == MineConstant.UNKNOWN): n_max += 1 for n_appear in range(n_min, n_max + 1): # まず、nが出現する確率を求める values_alive = board.values.copy() values_alive[open_cell.y, open_cell.x] = n_appear alive_board = Board(values_alive) # num_alive = self.count_solutions(alive_board) # 次に、このnの盤面に対する成功率を再帰で計算 result = self._evaluate_probability(alive_board) prob_alive = result.probability num_alive = result.num_solutions if num_alive == 0: # nが出現することがないなら、確率寄与は0 continue # かけ合わせて、成功率への寄与を計算 probability += prob_alive * Rational( num_alive, total_num_patterns) probabilities.append(probability) id_best = np.argmax(probabilities) return ProbabilityEvaluatorReturn( probability=probabilities[id_best], cell=search_cells[id_best], num_solutions=total_num_patterns, )
結果は
BoardSize(1x3) (EfficientEvaluator) 0.001421 [sec] (prob=1/3, pos=Cell(0, 0)) BoardSize(1x4) (EfficientEvaluator) 0.004651 [sec] (prob=1/3, pos=Cell(0, 0)) BoardSize(1x5) (EfficientEvaluator) 0.018294 [sec] (prob=2/5, pos=Cell(0, 0)) BoardSize(1x6) (EfficientEvaluator) 0.108779 [sec] (prob=8/15, pos=Cell(0, 2)) BoardSize(1x7) (EfficientEvaluator) 0.748816 [sec] (prob=4/7, pos=Cell(0, 2)) BoardSize(1x8) (EfficientEvaluator) 4.331416 [sec] (prob=17/28, pos=Cell(0, 2)) BoardSize(1x9) (EfficientEvaluator) 34.259348 [sec] (prob=23/36, pos=Cell(0, 2)) BoardSize(2x2) (EfficientEvaluator) 0.003896 [sec] (prob=1/6, pos=Cell(0, 0)) BoardSize(2x3) (EfficientEvaluator) 0.119122 [sec] (prob=1/3, pos=Cell(0, 0)) BoardSize(2x4) (EfficientEvaluator) 5.675668 [sec] (prob=9/28, pos=Cell(0, 0)) BoardSize(3x3) (EfficientEvaluator) 26.997285 [sec] (prob=2/3, pos=Cell(0, 1))
だいぶ改善された。しかし、2x5は非常に長い時間がかかる。579秒かけて計算が完了して、結果は13/45 (初手は(0, 0))と求まった。
sympy.Rationalの処理に時間がかかっている可能性を疑って、fractions.Fractionにしたりカスタムの有理数クラス(約分の頻度を下げる)や実数型を試したが、効果はなかった。
どうしてこれほどまでに長い時間がかかるのかがわからず、バグかと思ったのだが、どうもこれが自然な処理時間のようだ。2x5の盤面にターゲットを2個配置する方法は、たったの45通りしかないが、解き手がマスを順番に開いていく順序のパターンは10!(=3628800)通りもある。初手を対称性で削減したり、ちょっと枝刈りするくらいでは、太刀打ちできないのだろう。もっと改善が必要である。