Game
- 2. 問題概要 先手と後手が互いに列、行を指定しあって盤面の 数字を回収していく。最終的に得点の多い方が勝 ちになる。 これ以降相手がどうやっても引き分け以上に持ち 込めないときはその時点でゲームは終了する。 両者が最善を尽くしたときどちらが勝って何ターン でゲームが終了するか求める。
- 3. 前処理 残っている列、行を状態として「接待プレイで最大何 点差を獲得できるか」を求めておく。 状態数は2^N * 2^N以下なのでビットDPで十分間 に合う。 この前処理を施しておくことにより、任意の局面で ゲームが打ちきられるかどうかの判定ができる。
- 4. ゲーム木探索の復習 勝ち、負けだけが知りたいときは負けの状態に遷移 することができればその状態は勝ち。 評価値が2値以上とるときはminimax法を用いる。 最短手数での勝ちを求めるタイプのゲーム木探索 は、Mを適当に大きな数として 勝ちの局面にM-(手数) 引き分けの局面に0、 負けの局面に-(M-(手数)) (あるいは手数そのもの) などの評価値を割り振ればminimax法が使える。
- 5. 解法 現状ではゲーム木のノード数が(8!)^2で全て探索し ては到底間に合わない。 なので枝刈り探索を行う。 Minimax法の枝刈りでよく知られているのは、 α-β法、NegaScout、MDT-f などがあるが、今回はα-β法を用いるだけで十分間 に合う。
- 6. α-β法 黄色が先手、後手 が緑とする。 4 8 9 7 10 4 5 6 8 末端ノードの評価値 9 は決まっている
- 7. α-β法 黄色が先手、後手 が緑とする。 9 9≦10なので 打ち切り! 9 10 (βカット) 4 8 9 7 10 4 5 6 8 末端ノードの評価値 9 は決まっている
- 8. α-β法 黄色が先手、後手 9 が緑とする。 9 7 7≦9なので 打ち切り! (αカット) 9 10 7 4 8 9 7 10 4 7 5 6 8 末端ノードの評価値 7 は決まっている
- 9. α-β法 黄色が先手、後手 9 が緑とする。 9 7 8 9 10 7 4 8 9 7 10 4 7 5 6 8 末端ノードの評価値 7 は決まっている
- 10. 解答例 宮村： C++ 156行 3456 byte 橋本： Java 109行 3436 byte