考察
盤面は各cellがwhite/red/blueの3状態で高々3^9通りしかない。手番は塗られたcell数のparityで決まり、終了していなければ現在playerは「一手先に自分が勝つstateがあるか」だけを選べばよい。terminalで同色三目があればその色のplayerが勝ち、全埋まりならred取得weight和とblue取得weight和を比較する。非terminalでは一つでもcurrent player勝利となるchildがあれば勝ち、全childが相手勝利なら負ける。
採用する候補: 盤面stateをmemo化したminimax再帰で勝者を判定する
全game treeの同一盤面を共有し、有限DAG上の勝敗を高々3^9×9遷移で解ける。
棄却する候補: 局所的に最高weightのcellをgreedyに取る
三目完成による即勝利がscoreより優先され、相手のthreatもあるためweightだけの局所選択は最適でない。
redMask,blueMaskまたはternary codeをstate keyにする。8本のwinning maskを検査し、full boardならmask別weight sumを比較する。未終了ではmove数偶数ならTakahashi、奇数ならAokiとして各empty cellを自色へ追加し再帰し、自分勝ちchildを見つけたらtrueをmemoする。初期stateのwinnerを出力する。
典型の発動条件
有限完全情報gameのminimax
発動条件: 運要素がなく、双方が勝利を目的に最適行動し、state遷移がacyclicである。
terminal winnerをbaseに、存在/全称でcurrent playerの勝敗を後ろ向きに決める。
bitmask盤面表現
発動条件: 3×3盤面の占有とwinning line包含を高速に検査したい。
playerごとの9-bit maskを持ち、(mask&line)==lineで三目を判定する。
問題固有の要素
score最大化gameではなく勝敗gameなので、途中の三目は残りweightに関係なく即終了し、score比較は9手完了時だけ行う。
別の問題へ持ち帰る視点: 複数終了規則のgame DPではrule priorityをterminal evaluatorにそのまま反映する。
正当性
三目成立なら即勝敗、全埋めなら重み合計で終端。非終端は手番の人が自分勝ちchildを一つでも選べると勝ち、全child負けなら負け。このminimax帰納法は空き数を減らすDAG上で厳密。同盤面は将来同じなのでmemo可能。
実装上の注意
- 三目判定をfull-board scoreより先に行う。Aは負でもscoreをsigned 64bitで合計し、総和odd保証によりfull board tieはない。
復習の核
- 即勝ちを取る局面、相手三目をblockする局面、三目なしで負weightを含むscore決着を手作業minimaxと比較する。
計算量と制約
時間
9マス。ternary盤面は3^9、各9遷移で O(9·3^9)。
空間
memo O(3^9)、再帰深さ9。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: |A_{i,j}| \leq 10^9; \sum_{i=1}^3 \sum_{j=1}^3 A_{i,j} is odd.; All input values are integers.
出典