コンピュータ三目並べ
空気読まずに復活してみるテスト。
二人零和有限確定完全情報ゲームのおさらい
【不敗アルゴリズムが必ずある！(数学的な意味で】
wikipedia:二人零和有限確定完全情報ゲームには先手か後手(どちらであるかはゲームのルール依存で決まる)が確実に勝利または引き分け(これもどちらであるかはゲームのルール依存で決まる)に持ち込める最善手が存在します。ホントであることはこことか見るとワカル
【最善手とはなんぞや？】
ネットをちらほら覗く限りでは定義を明確に述べている場所が見当たらないようだけど(→気のせい)
さっきのリンク先を注意深く推測混じりで(何
読むと、プレイヤーxの最善手とは、ノードにゲイン付けられたゲーム木において、根ノード(ゲーム開始の状態)から葉ノード(勝負がついてゲームを終える状態)に到る径路のうちで、xが最も有利になる道順を成すxの手、というのが包括的な定義のようです。ただし有利不利の判断は用いる戦略(min-max, max-min等)依存です、ということらしい。
【特に、二人零和有限確定完全情報ゲームにおける最善手とは？】
二人零和有限確定完全情報ゲームで勝ち方はともかくとして勝敗のみを問題にする場合、「零和」条件からAND/OR木だけを考えれば良いとさっきのリンク先には書いてある(ように読める)。
これからすると最善手を曖昧さの無い形で定義できて、不敗アルゴリズムの存在証明の基礎となります。
実際、
- 局面
- 盤上の駒の配置の具体例
- 手
- 局面を次の局面に推移させる方法の具体例
- xの手番
- プレイヤーxが自身の手を具現化する番
- Win(x)
- プレイヤーxの勝利が確定する条件
とすると、2人のプレイヤーx,yの対戦において、xの勝利(確定)手が次のように再帰的に定義されると思う木がします。
-
- xの手番において、Win(x)を成立させる手はxの勝利手である。
- xの手番において、yの勝利手を現出せしめることなくxの勝利手を現出せしめる手はxの勝利手である。
- 上記2条件のいずれかを満たすものだけがxの勝利手である。(←追加)
将棋で言えば、 条件1.は詰んだ相手の王将を取るのは最善手勝利手だということを主張しています。 条件2.は自身が優勢のままWin(x)にたどり着く手筋を成す手は最善手勝利手だということを主張しています。
ていうかこれはさっきのリンク先のゲーム木の色分けを言葉で焼き直しただけですが、、
とにかくゲーム開始後、xが1回でもxの勝利手を打てた(指せた)なら、以降xがミスしない限りxの勝利は確定するので(定義より明らか)、勝負だけを問題にするなら勝利手皆最善手と言ってもいいし、時間も重視するなら勝利手のうち最小手数のものを最善手と定義してもいい。
、、ハズ
ひとたびこの概念を認めるなら、いくつか(素人目には)面白いことが言えます。
