またまた、すばらしきチームリーダーのおかげで、更新が滞ってしまいました。
こいつでブログを書いた方がネタに困らないかもです。
今日なんて、あるプログラムが動作中にアクセスし続けるファイルがあるのだけど、
プログラム稼働中にこのファイルをオペレーターが誤って外部から消去しても正常に動作しろだもんなぁ。
さて、気を取り直して前回の続きです。 NUnitでレッドになってしまいましたが、Stageの内容がわからないので、 Stageクラスに ToStringを実装することにします。
let piece_str = function
| CIRCLE -> "O"
| CROSS -> "X"
| _ -> "-"
override self.ToString() =
let mutable s = (piece_str _move) + ":"
for i = 0 to 2 do
for j = 0 to 2 do
s <- s + (piece_str _board.[i,j])
s <- s + ","
s
NUnitの結果を見てみると、
TicTacToeTest.ComputerTest.next1:
Expected: <X:OOO,XX-,---,>
But was: <X:OOO,XX-,---,>
となっています。 これを見ると同じ結果に見えます。 そう、本当はあっているのです。 では、なぜレッドになってしまうかというと、 StageクラスのEqualsメソッドが次の手と駒の配置から同じどうかを判断しているわけではないためです。 ということで、Equalsメソッドをオーバーライドすることにします。
override self.Equals(o:Object) =
let s = o :?> Stage
if _move <> s.Move then
false
else
_board = s.Board
これで、無事グリーンになりました。ただ、コンパイル時に警告が出ています。 Equalsをオーバライドしたときは、GetHashCodeもオーバーライドしないとこうなります。 そこで、GetHashCodeもオーバーライドして起きます。
override self.GetHashCode() =
(hash _move) ^^^ (hash _board)
F#には、hash関数があるのでこれを使ってみましたが、正直こんなコードでいいのかどうか…。 まぁ、全部同じハッシュ値になっても動作はするわけですが…。
それでは、与えられた局面に対してコンピューターが思考した次の一手(局面)を返す next 関数を実装することにしましょう。
ところで、本家の evaluate 関数について１つ疑問が…。
これって確かに評価値として最適なものは見つかると思いますが、
どの手で最適な評価値になったのかわからなくような気がするのですが…。
ということで、以下の解法では最初の部分は陽に展開しています。
1: let next (st:Stage) =
2: let s_eval = if st.Move = CIRCLE then
3: (fun (st:Stage) -> st.eval(CIRCLE, CROSS))
4: else
5: (fun (st:Stage) -> st.eval(CROSS, CIRCLE))
6: let evaluate = minimise << lazymap s_eval << prune 3 << gametree
7: let eval_list = List.map (fun x -> (evaluate x, x)) (moves st)
8: let v, new_st = List.maxBy (fun (x,y) -> x) eval_list
9: new_st
2〜5行では、手番によって盤面の静的評価 eval の自分の駒と相手の駒が逆になるので、
これを決定しています。
6行では、評価用の関数を合成しています。本家では、maximise なのが minimise になっているのは、
先ほどの理由で最初のサブツリーはこの関数内で展開しているためです。
7行で、これをサブツリー全体に適用しています。
8行で、そのなかで一番値が大きいものを見つけて、
これに対応する局面 new_st が関数値となります(9行)。
それでは、NUnitを実行してみましょう。
グリーンになると思ったのですが、残念ながらレッドになってしまいました。
これについては次回に…。
注意: 原因を探す場合、思考ルーチンは疑わない方が吉です。
盤面の静的評価ルーチンの実装が完了したので、 ミニマックス法による思考ルーチンを作成することにしましょう。 ミニマックス法については「なぜ関数プログラミングは重要か」(以下、本家)の説明を参照していただくとして、 まずは指定された深さ n で刈り込む prune 関数です。
let rec prune n (node:Node<_>) =
match n with
| 0 -> { node with sub = lazy([]) }
| n -> { node with sub = lazy(List.map (prune (n-1)) node.sub.Value) }
これは、深さ n になったら、問答無用にサブツリーを空リストに置き換えるだけなので、 特に説明の必要はないと思います。
本家では、この刈り込んだゲーム木のすべてに静的評価関数 static を maptree で適用しています。 今回の場合、静的評価値が必要になるのはサブツリーが空の場合だけです。 それ以外の局面の静的評価値は必要ありません。 本家では、遅延評価である Miranda なので問題ないですが、 F# は先行評価のためそのままでは中間値でも計算してしまいます。 そこで、すべてを遅延評価とする lazymap を作成することにします。
let rec lazymap f (node:Node<_>) =
{ n = lazy(f node.n)
sub = lazy(List.map (lazymap f) node.sub.Value) }
この lazymap による評価ツリーを与えられたときに、ミニマックス法による計算を行う、 maxmise と minimise を以下に示します。
// ミニマックス法
let rec maximise (node:Node<Lazy<'a>>) =
match node.sub.Value with
| [] -> node.n.Value
| sub -> List.max (List.map minimise sub)
and minimise (node:Node<Lazy<'a>>) =
match node.sub.Value with
| [] -> node.n.Value
| sub -> List.min (List.map maximise sub)
google-code-pretty、ダメダメですねー。
まぁ、OCamlとはリリースの度に別物になっていくのでしょうがないですけど。
F#では、関数の前方宣言がないので前方参照が出来ません。
よって、上記のような相互参照の場合は、andでつないで同列にします。
個人的には、これや再帰の時のrecって何とかならないのかと思うのですが…。
本家とは少し構成が異なりますが、一通り部品がそろったので、 ある局面 s を渡すと、なるべく良い手を返す next を考えて見てください。 とりあえず、テストケースとして以下のようなものを用意しておきます。
// 次の一手
// 次で勝ち
// ○○− ○○○
// ××− → ××−
// −−− −−−
[<Test>]
member self.next1() =
let b = Array2D.init 3 3 (fun i j -> if i = 0 && j <> 2 then CIRCLE
elif i = 1 && j <> 2 then CROSS
else NONE)
let s = Stage(CIRCLE, b)
let next_s = next s
s.put(0, 2) |> ignore
Assert.That(next_s, Is.EqualTo(s))
さすがに、この時に(0,2)に○以外の手を返すようでは困りものですね。
局面を静的評価値を返す eval メソッドを実装することにしましょう。 とりあえず、自分の駒の種類と相手の駒の種類と局面を渡すと評価値を返す関数 static_eval があるとします。 そうすれば、eval メソッドは以下のように書けます。
member self.eval(mp, yp) = static_eval mp yp _board
さて、static_eval ですが、以下のようなものにしてみました。
01: let static_eval mp yp (bd:_[,]) =
02: let piece_count =
03: seq {
04: let mc1 = ref 0
05: let yc1 = ref 0
06: let mc2 = ref 0
07: let yc2 = ref 0
08: // 縦横
09: for i in 0..2 do
10: mc1 := 0
11: yc1 := 0
12: mc2 := 0
13: yc2 := 0
14: for j in 0..2 do
15: // 横
16: if bd.[i,j] = mp then
17: mc1 := !mc1 + 1
18: elif bd.[i,j] = yp then
19: yc1 := !yc1 + 1
20: // 縦
21: if bd.[j,i] = mp then
22: mc2 := !mc2 + 1
23: elif bd.[j,i] = yp then
24: yc2 := !yc2 + 1
25: yield (!mc1, !yc1)
26: yield (!mc2, !yc2)
27: // 斜め
28: mc1 := 0
29: yc1 := 0
30: mc2 := 0
31: yc2 := 0
32: for i in 0..2 do
33: // (0,0)-(2,2)
34: if bd.[i,i] = mp then
35: mc1 := !mc1 + 1
36: elif bd.[i,i] = yp then
37: yc1 := !yc1 + 1
38: if bd.[i,2-i] = mp then
39: mc2 := !mc2 + 1
40: elif bd.[i,2-i] = yp then
41: yc2 := !yc2 + 1
42: yield (!mc1, !yc1)
43: yield (!mc2, !yc2)
44: }
45:
46: let line_value = function
47: | (0, 0) -> 0
48: | (x, 0) -> List.fold (fun a b -> a * 10) 1 [1..x]
49: | (0, x) -> List.fold (fun a b -> a * 10) -1 [1..x]
50: | _ -> 0
51:
52: Seq.fold (fun a b -> a + (line_value b)) 0 piece_count
seq内に展開してしまったため、ちょっどだらだらな感じになってしまった piece_count 関数(2〜44行)ですが、
これは縦・横・斜め、すべての並びに対して、自分の駒(mp)と相手の駒(yp)の個数を数えて、
(自分の駒の個数, 相手の駒の個数)というタプルのシーケンスを返しています。
「refなんて使わずに、mutableを使えばいいのに」と思った方も多いのではないでしょうか？
実は私も最初はカウンタ用の変数をmutableで宣言しました。
だけど、それではエラーになってしまうようです。
推測ですが、mutableで宣言した値はスタック上に確保されるからだと思います。
seq内の処理は、yieldの次から再開されますので、
この中で宣言された値をスタック上に確保するわけにはいきません。
よって、ヒープ上に確保して ref で参照する必要があるのだと思います。
line_value 関数は、piece_count 関数でカウントした(自分の駒の数, 相手の駒の数)というタプルから、 その並びの評価値を計算しています。 48行が自分の駒のみの場合、49行が相手の駒のみの場合になります。 F#ではべき乗はfloatに対してでintにはないので、個数分10を掛けています。
52行は、piece_count関数の個々の要素に、line_value関数を適応した結果の合計を求めています。 これが、指定された局面の静的評価値になります。
木曜日の夜頃から38.5度くらいの発熱が続いたため、体調不良でまたまた更新が滞ってしまいました。 本来は１日くらい安静にしていれば治ったと思うのですが、結局昨日まで仕事でした。 このご時世、孫請けの立場じゃ何も言えないのですけど…。
さて、ある局面の評価ですが、以下のように重み付けをすることにします。 各並びに対して、
- 自分の駒がn個で相手の駒が0個の場合、10n点
- 相手の駒がn個で自分の駒が0個の場合、-10n点
- 双方の駒が１個以上ある場合、その並びではどちらも勝つことが出来ないので0点
交互に駒を置くというルールは局面の評価とは関係ないので、 仮に以下のような場合で自分が○であれば評価値はいくつでしょうか。
| ○ | ○ | ○ |
答えは、1050です。 横に○が3個並んでいるので、一瞬、103で1000と思ってしまいそうですが、 縦の並びおよび斜めの並びすべてで10になりますので+50されます。
このような局面の評価値を返すメソッド eval(mp, yp) を Stage クラスに追加することにします。 mp には自分の駒、yp には相手の駒を渡すものとします。 そうすると、先ほどの局面のテストコードは以下のように書けます。
// 盤面の静的評価
[<Test>]
member self.staticEval() =
let b = Array2D.init 3 3 (fun i j -> if i = 1 then CIRCLE else NONE)
let st = Stage(CIRCLE, b)
let result = st.eval(CIRCLE, CROSS)
Assert.That(result, Is.EqualTo(1050))
これがグリーンになるような、eval(mp, yp) の実装を考えてみてください。