今回も 4 つのパズルを出題します。SML/NJ で解法プログラムを作成してください。
マスターマインドは、0 から 9 までの重複しない 4 つの数字からなる隠しコードを当てるゲームです。数字は合っているが位置が間違っている個数を cows で表し、数字も位置も合っている個数を bulls で表します。bulls が 4 になると正解です。
(6 2 8 1) : 正解
---------------------------------
1. (0 1 2 3) : cows 2 : bulls 0
2. (1 0 4 5) : cows 1 : bulls 0
3. (2 3 5 6) : cows 2 : bulls 0
4. (3 2 7 4) : cows 0 : bulls 1
5. (3 6 0 8) : cows 2 : bulls 0
6. (6 2 8 1) : cows 0 : bulls 4
図 : マスターマインドの動作例
マスターマインドを解くプログラムを作ってください。
15 人の女生徒が毎日 3 人ずつ 5 組に分かれて散歩をするとき、1 週間 (7 日) のうちに、どの女生徒も他のすべての女生徒と 1 回ずつ同じ組になるような組み合わせを作ってください。(出典 : 大村平 (著), 『数理パズルの話』, 日科技連出版社, 1998)
「カークマンの 15 人の女生徒」を解くプログラムを作ってください。
下図に示す 6 行 6 列盤のナンバープレース (数独) において、解となる盤面の総数を求めてください。
┏━┯━┯━┳━┯━┯━┓ ┃１│２│３┃４│５│６┃ ┠─┼─┼─╂─┼─┼─┨ ┃４│５│６┃１│２│３┃ ┣━┿━┿━╋━┿━┿━┫ ┃２│１│４┃３│６│５┃ ┠─┼─┼─╂─┼─┼─┨ ┃３│６│５┃２│１│４┃ ┣━┿━┿━╋━┿━┿━┫ ┃５│３│１┃６│４│２┃ ┠─┼─┼─╂─┼─┼─┨ ┃６│４│２┃５│３│１┃ ┗━┷━┷━┻━┷━┷━┛ 図 : 数独 (6 行 6 列盤) の解 (一例)
余裕のある方は 9 行 9 列盤の数独を解くプログラムも作ってみてください。
三目並べは、皆さんお馴染みの二人で対戦するゲームです。ひとりが○側でもうひとりが×側を受け持ち、3 行 3 列のマス目に○×を書いて、3 つ並べた方が勝ちというゲームです。
┌─┬─┬─┐ │×│○│○│ ├─┼─┼─┤ │○│○│×│ ├─┼─┼─┤ │×│×│○│ └─┴─┴─┘ 図 : 三目並べ
上図は○側が先手で引き分けになった例です。三目並べは、両者が最善を尽くすと引き分けになることが知られています。本当に引き分けになるのか、プログラムを作って確かめてください。
それではプログラムを作りましょう。正解を見つけるアルゴリズムですが、簡単な方法があります。質問したコードとその結果を覚えておいて、それと矛盾しないコードを作るようにします。具体的には、4 つの数字の順列を生成し、それが今まで質問したコードと矛盾しないことを確かめます。これは生成検定法と同じですね。
矛盾しているかチェックする方法も簡単で、以前に質問したコードと比較して、bulls と cows が等しいときは矛盾していません。たとえば、次の例を考えてみてください。
(6 2 8 1) が正解の場合
(0 1 2 3) => bulls = 0, cows = 2
(0 1 2 3) と比較する
--------------------------------------------------------
(0 X X X) 0 から始まるコードは bulls = 1
になるので矛盾する。
・・・・
(1 0 3 4) cows = 3, bulls = 0 になるので矛盾する
・・・・
(1 0 4 5) cows = 2, bulls = 0 で矛盾しない。
--------------------------------------------------------
(1 0 4 5) => bulls = 0, cows = 1
次は、(0 1 2 3) と (1 0 4 5) に矛盾しない数字を選ぶ
図 : マスターマインドの推測アルゴリズム
(0 1 2 3) で bulls が 0 ですから、その位置にその数字は当てはまりません。したがって、(0 X X X) というコードは (0 1 2 3) と比較すると bulls が 1 となるので、矛盾していることがわかります。
次に (1 0 3 4) というコードを考えてみます。(0 1 2 3) の結果は cows が 2 ですから、その中で合っている数字は 2 つしかないわけです。ところが、(1 0 3 4) と (0 1 2 3) と比較すると cows が 3 になります。当たっている数字が 2 つしかないのに、同じ数字を 3 つ使うのでは矛盾していることになりますね。
次に (1 0 4 5) というコードと比較すると、bulls が 0 で cows が 2 となります。これは矛盾していないので、このコードを質問することにします。その結果が bulls = 0, cows = 1 となり、今度は (0 1 2 3) と (1 0 4 5) に矛盾しないコードを選択するのです。
まず最初に bulls と cows を求める関数を作ります。
リスト : bulls と cows を求める (* 等しい要素があるか *) fun mem(_, []) = false | mem(x, y::ys) = if x = y then true else mem(x, ys) (* bulls を数える *) fun count_bulls(xs, ys) = ListPair.foldl (fn(x, y, a) => if x = y then a + 1 else a) 0 (xs, ys) (* 同じ数字を数える *) fun count_same_number(xs, ys) = foldl (fn(x, a) => if mem(x, ys) then a + 1 else a) 0 xs
関数 count_bulls は ListPair.foldl を使うと簡単です。ListPair.foldl の型を示します。
val it = fn : ('a * 'b * 'c -> 'c) -> 'c -> 'a list * 'b list -> 'c
ListPair.foldl は 2 つのリストを引数に受け取ります。ListPair モジュールには map や foldr など 2 つのリストを引数に受け取る高階関数が定義されています。匿名関数の引数 a が bulls の個数で、x と y がリストの要素になります。x と y が等しい場合、a を +1 すれば bulls の個数を求めることができます。
次は、cows を数える処理を作ります。いきなり cows を数えようとすると難しいのですが、2 つのリストに共通の数字を数えることは簡単にできます。この方法では、bulls の個数を含んだ数を求めることになりますが、そこから bulls を引けば cows を求めることができます。
関数名は count_same_number としました。この処理は foldl を使うと簡単です。匿名関数の引数 a が共通の数字の個数で、x がリスト xs の要素です。関数 mem で x が ys に含まれていれば、a の値を +1 します。
次は生成したコードが今までの結果と矛盾していないか調べる関数 check を作ります。次のリストを見てください。
リスト : 今までの質問と矛盾しているか
fun check(_, []) = true
| check(q, (qcode, qbulls, qcows)::query) =
let
val bulls = count_bulls(q, qcode)
val cows = count_same_number(q, qcode) - bulls
in
if bulls = qbulls andalso cows = qcows then check(q, query) else false
end
質問したコードとその結果は組にまとめてリストに格納します。最初が質問したコード、次が bulls の個数、最後が cows の個数です。データはパターンマッチングで取り出して、局所変数 qcode, qbulls, qcows にセットします。そして、code と qcolde から bulls と cows を count_bulls と count_same_number で求めます。
bulls と qbulls が等しくて、cows と qcows が等しい場合、code は矛盾していないので、次のデータを調べます。そうでなれば code は矛盾しているので false を返します。すべてのデータを調べたら true を返します。
マスターマインドを解くプログラムは次のようになります。
リスト : マスターマインドの解法
fun mastermind code =
let
fun iter([], _) = 0
| iter(x::xs, query) =
if check(x, query) then
let
val bulls = count_bulls(x, code)
val cows = count_same_number(x, code) - bulls
in
print_intlist(x);
print(": bulls " ^ Int.toString(bulls));
print(", cows " ^ Int.toString(cows) ^ "\n");
if bulls = 4 then length(query) + 1
else iter(xs, (x, bulls, cows)::query)
end
else iter(xs, query)
in
iter(permutation(4, [0,1,2,3,4,5,6,7,8,9]), [])
end
関数 mastermind の引数 code が正解のコードで、実際の処理は局所関数 iter で行います。関数 permutation はリストの中から 4 個の要素を選ぶ順列を生成し、それをリストに格納して返します。
あとは iter でコードを順番に取り出して、今まで質問したコードと矛盾していないか調べます。引数 query が今までに質問したコードと結果を格納したリストで、x が質問するコードです。check が true を返す場合、x は矛盾していないので、x と code を比較して bulls と cows を求めます。そして、その結果を表示します。
もしも、bulls が 4 ならば正解なので質問回数を返して処理を終了します。そうでなければ、query に今回の結果を追加して iter を再帰呼び出しします。x が矛盾している場合は iter を再帰呼び出しするだけです。
これでプログラムは完成です。それでは実行例を示しましょう。
- mastermind([0,1,2,3]); 0 1 2 3 : bulls 4, cows 0 val it = 1 : int - mastermind([9,8,7,6]); 0 1 2 3 : bulls 0, cows 0 4 5 6 7 : bulls 0, cows 2 5 4 8 9 : bulls 0, cows 2 6 7 9 8 : bulls 0, cows 4 8 9 7 6 : bulls 2, cows 2 9 8 7 6 : bulls 4, cows 0 val it = 6 : int - mastermind([9,4,3,1]); 0 1 2 3 : bulls 0, cows 2 1 0 4 5 : bulls 0, cows 2 2 3 5 4 : bulls 0, cows 2 3 4 0 6 : bulls 1, cows 1 3 5 6 1 : bulls 1, cows 1 6 5 0 2 : bulls 0, cows 0 7 4 3 1 : bulls 3, cows 0 8 4 3 1 : bulls 3, cows 0 9 4 3 1 : bulls 4, cows 0 val it = 9 : int
肝心の質問回数ですが、5, 6 回で当たる場合が多いようです。実際に、5040 個のコードをすべて試してみたところ、平均は 5.56 回になりました。これは参考文献「数当てゲーム (MOO, マスターマインド)」の結果と同じです。質問回数の最大値は 9 回で、そのときのコードは [9, 4, 3, 1], [9, 2, 4, 1], [5, 2, 9, 3], [9, 2, 0, 4], [9, 2, 1, 4] でした。
なお、参考文献には平均質問回数がこれよりも少なくなる方法が紹介されています。単純な数当てゲームと思っていましたが、その奥はけっこう深いようです。興味のある方はいろいろ試してみてください。
(*
* mastermind.sml : MaterMind 解答プログラム
*
* Copyright (C) 2012-2020 Makoto Hiroi
*)
(* 表示 *)
fun print_intlist([]) = ()
| print_intlist(x::xs) = (print(Int.toString(x) ^ " "); print_intlist(xs))
(* 要素を削除する *)
fun remove(_, []) = []
| remove(x, y::ys) =
if x = y then remove(x, ys) else y :: remove(x, ys)
(* 等しい要素があるか *)
fun mem(_, []) = false
| mem(x, y::ys) = if x = y then true else mem(x, ys)
(* 順列の生成 *)
fun permutation(n, ls) =
let
fun perm_sub(0, _, y, z) = (rev y)::z
| perm_sub(n, xs, y, z) =
foldr (fn(a, b) => perm_sub(n - 1, remove(a, xs), a::y, b)) z xs
in
perm_sub(n, ls, [], [])
end
(* bulls を数える *)
fun count_bulls(xs, ys) =
ListPair.foldl (fn(x, y, a) => if x = y then a + 1 else a) 0 (xs, ys)
(* 同じ数字を数える *)
fun count_same_number(xs, ys) =
foldl (fn(x, a) => if mem(x, ys) then a + 1 else a) 0 xs
(* 矛盾していないか *)
fun check(_, []) = true
| check(q, (qcode, qbulls, qcows)::query) =
let
val bulls = count_bulls(q, qcode)
val cows = count_same_number(q, qcode) - bulls
in
if bulls = qbulls andalso cows = qcows then check(q, query) else false
end
(* マスターマインドを解く *)
fun mastermind code =
let
fun iter([], _) = 0
| iter(x::xs, query) =
if check(x, query) then
let
val bulls = count_bulls(x, code)
val cows = count_same_number(x, code) - bulls
in
print_intlist(x);
print(": bulls " ^ Int.toString(bulls));
print(", cows " ^ Int.toString(cows) ^ "\n");
if bulls = 4 then length(query) + 1
else iter(xs, (x, bulls, cows)::query)
end
else iter(xs, query)
in
iter(permutation(4, [0,1,2,3,4,5,6,7,8,9]), [])
end
「カークマンの 15 人の女生徒」の解法プログラムは Yet Another SML/NJ Problems (4) 問題 74 で作成した関数 group_partition を改造すると簡単に作成することができます。次のリストを見てください。
リスト : カークマンの 15 人の女生徒
fun remove(x, []) = []
| remove(x, y::ys) =
if x = y then remove(x, ys) else y :: remove(x, ys)
fun iota(n, m) =
let
fun iter i a = if i < n then a else iter (i - 1) (i::a)
in
iter m []
end
fun mem(_, []) = false
| mem(x, y::ys) = if x = y then true else mem(x, ys)
fun print_intlist2([]) = print("\n")
| print_intlist2(x::xs) =
(
print("( ");
List.app (fn y => print(Int.toString(y) ^ " ")) x;
print(")");
print_intlist2(xs)
)
exception Kirkman_exit
val check_table : int list array = Array.array(16, [])
fun check_person([], _) = true
| check_person(y::ys, x) =
if mem(x, Array.sub(check_table, y)) then false
else check_person(ys, x)
fun add_person(ls, x) =
List.app (fn y => (
Array.update(check_table, x, y::Array.sub(check_table, x));
Array.update(check_table, y, x::Array.sub(check_table, y))
))
ls
fun del_person(ls, x) =
List.app (fn y => (
Array.update(check_table, x, tl (Array.sub(check_table, x)));
Array.update(check_table, y, tl (Array.sub(check_table, y)))
))
ls
fun kirkman () =
let
fun kirkman_sub([], a, b) =
if length(b) = 6 then (
List.app (fn x => print_intlist2(x)) (rev (a::b));
raise Kirkman_exit
)
else kirkman_sub(iota(2, 15), [[1]], a::b)
| kirkman_sub(x::xs, a, b) = (
List.app (fn y => if length(y) < 3 andalso check_person(y, x) then
(
add_person(y, x);
kirkman_sub(xs, (x::y) :: remove(y, a), b);
del_person(y, x)
)
else ())
a;
if length(a) < 5 then kirkman_sub(xs, [x]::a, b) else ()
)
val s = Timer.startRealTimer()
in
kirkman_sub(iota(2, 15), [[1]], []) handle _ => ();
Timer.checkRealTimer(s)
end
15 人の女生徒を 1 から 15 までの数値で表します。変数 check_table は、いっしょに散歩した人を格納する配列です。0 番目はダミーです。たとえば、[1, 2, 3] というグループを作った場合、check_table の 1 番目には [2, 3] を、2 番目には [1, 3] を、3 番目には [2, 3] をセットします。この check_table を使って、同じ女生徒と 2 回以上散歩しないようにグループ分けを行います。
関数 check_person(ys, x) はグループ ys に x を追加するとき、既に散歩した女生徒がいるかチェックします。check_table の y 番目からリストを取り出し、それに x が含まれていれば、y は既に x と散歩をしています。この場合は false を返します。x が ys の女生徒達とまだ散歩していない場合は true を返します。
関数 add_person(ys, x) は check_table にグループ ys と x の関係を追加します。ys の要素を y とすると、check_table の x 番目のリストに y を、y 番目のリストに x を追加するだけです。関数 del_person(ys, x) は ys と x の関係を削除します。ys の要素を y とすると、check_table の x 番目の先頭要素と、y 番目の先頭要素を削除します。
解法プログラム kirkman の実際の処理は局所関数 kirkman_sub で行います。第 1 引数が女生徒を格納したリスト、a が作成中のグループ分けを格納するリスト、b が完成したグループ分けを格納するリストです。b の長さが 7 になれば解を見つけたことになります。
プログラムでは第 1 引数が空リストになり (a がひとつ完成する)、b の長さが 6 の場合、完成した a を b に追加し、それを rev で反転して要素を print_intlist2 で表示します。そうでなければ、a を b に追加して kirkman_sub を再帰呼び出しして次の日のグループ分けを作成します。
グループ分けの処理は group_partition とほぼ同じですが、check_person でチェックを行い、add_person で check_table を更新してから、kirkman_sub を再帰呼び出しします。再帰呼び出しから戻ってきたら、del_person で check_table を元に戻します。
それでは実行結果を示します。
- kirkman();
( 15 14 13 )( 12 11 10 )( 9 8 7 )( 6 5 4 )( 3 2 1 )
( 15 4 3 )( 14 10 9 )( 13 11 8 )( 12 5 2 )( 7 6 1 )
( 15 12 7 )( 14 11 1 )( 13 10 6 )( 9 4 2 )( 8 5 3 )
( 15 11 2 )( 14 7 5 )( 13 9 3 )( 12 8 6 )( 10 4 1 )
( 15 9 6 )( 14 12 3 )( 13 5 1 )( 11 7 4 )( 10 8 2 )
( 15 10 5 )( 14 8 4 )( 13 7 2 )( 12 9 1 )( 11 6 3 )
( 15 8 1 )( 14 6 2 )( 13 12 4 )( 11 9 5 )( 10 7 3 )
val it = TIME {usec=14137301} : Time.time
実行時間は 14.14 秒 (SML/NJ v110.98, Windows 10, Intel Core i5-6200U 2.30GHz) でした。興味のある方は高速化に挑戦してみてください。
解の総数を求める場合、単純な方法では 6 * 6 のナンバープレースでも大変です。そこでラテン方陣のような標準形を考えることにします。ナンバープレースの場合、数字 N と数字 M を交換しても数独の条件を満たすので、数字の配置を下図のように限定することにします。
1 2 3 4 5 6 4 5 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 図 : 数字の配置
一番上の行で数字を交換することで 6! = 720 通り、右上のグループの残り 3 つの数字を交換することで 6 通りの解が生成されます。したがって、上図の解の総数を I とすると、解の総数は I * 720 * 6 になります。
今回は盤面を二次元配列で表すことにします。SML/NJ のモジュール Array2 には、二次元配列を操作する関数が用意されています。ここで簡単にモジュール Array2 の基本的な操作関数を説明しておきましょう。
二次元配列の生成は関数 Array2.array を使います。
Array2.array(行, 列, 要素の初期値)
関数 array は m 行 n 列の二次元配列を生成します。また、関数 formList は 'a list list を二次元配列に変換します。関数 nRows は行数を、nCols は列数を返します。dimensions は (m, n) を返します。
- Array2.array; val it = fn : int * int * 'a -> 'a Array2.array - val a = Array2.array(2, 3, 0); - Array2.nRows a; val it = 2 : int val a = - : int Array2.array - Array2.nCols a; val it = 3 : int - Array2.dimensions a; val it = (2,3) : int * int - Array2.fromList; val it = fn : 'a list list -> 'a Array2.array - val b = Array2.fromList [[1,2],[3,4],[5,6]]; val b = - : int Array2.array - Array2.nRows b; val it = 3 : int - Array2.nCols b; val it = 2 : int - Array2.dimensions b; val it = (3,2) : int * int
要素のアクセスは関数 sub と update を使います。
Array2.sub(a, m, n) Array2.update(a, m, n, x)
- Array2.sub; val it = fn : 'a Array2.array * int * int -> 'a - Array2.update; val it = fn : 'a Array2.array * int * int * 'a -> unit - Array2.sub(a, 0, 0); val it = 0 : int - Array2.update(a, 0, 0, 10); val it = () : unit - Array2.sub(a, 0, 0); val it = 10 : int - Array2.sub(b, 2, 1); val it = 6 : int - Array2.update(b, 2, 1, 100); val it = () : unit - Array2.sub(b, 2, 1); val it = 100 : int
指定した行や列を取り出す関数 row, column もあります。
Array2.row(a, n) : n 番目の行を取り出す Array2.column(a, n) : n 番目の列を取り出す
これらの関数は vector を返すことに注意してください。
- Array2.row; val it = fn : 'a Array2.array * int -> 'a vector - Array2.row(b, 0); val it = #[1,2] : int vector - Array2.row(b, 2); val it = #[5,100] : int vector - Array2.column; val it = fn : 'a Array2.array * int -> 'a vector - Array2.column(b, 0); val it = #[1,3,5] : int vector - Array2.column(b, 1); val it = #[2,4,100] : int vector
このほかにも、いろいろな関数が用意されています。詳細は SML/NJ のリファレンス The Array2 structure をお読みください。
最近のパソコンは高性能なので、ナンバープレースは単純なバックトラックでも高速に解くことができます。プログラムは次のようになります。
リスト : 数独 (6 行 6 列盤) の解の総数を求める
(* 初期値 *)
val init_board = [
[1, 2, 3, 4, 5, 6],
[4, 5, 6, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0]
]
(* 数字を置けるか *)
fun check(board, n, x, y) =
let
(* 縦横のチェック *)
fun iter1 6 = true
| iter1 i =
if Array2.sub(board, i, x) = n orelse Array2.sub(board, y, i) = n then false
else iter1 (i + 1)
(* 枠のチェック *)
fun iter2 () =
let
val x1 = (x div 3) * 3
val y1 = (y div 2) * 2
fun iter3 _ 2 = true
| iter3 3 j = iter3 0 (j + 1)
| iter3 i j =
if Array2.sub(board, y1 + j, x1 + i) = n then false
else iter3 (i + 1) j
in
iter3 0 0
end
in
iter1 0 andalso iter2 ()
end
(* 単純な深さ優先探索 *)
fun solver () =
let
val board = Array2.fromList init_board
val cnt = ref 0
fun dfs _ 6 = cnt := !cnt + 1
| dfs 6 y = dfs 0 (y + 1)
| dfs x y =
if Array2.sub(board, y, x) <> 0 then dfs (x + 1) y
else
app (fn n => if check(board, n, x, y) then
(
Array2.update(board, y, x, n);
dfs (x + 1) y;
Array2.update(board, y, x, 0)
)
else ())
[1,2,3,4,5,6]
in
dfs 0 0;
!cnt
end
プログラムに難しいところはないと思うので、説明は割愛させていただきます。実行結果は次のようになりました。
- solver_exec(); val it = 6528 : int
解の総数は 6528 * 720 * 6 = 28200960 になります。
9 行 9 列盤のナンバープレースも簡単です。プログラムは次のようになります。
リスト : ナンバープレースの解法
(* 数字を置けるか *)
fun check(board, n, x, y) =
let
(* 縦横のチェック *)
fun iter1 9 = true
| iter1 i =
if Array2.sub(board, i, x) = n orelse Array2.sub(board, y, i) = n then false
else iter1 (i + 1)
(* 枠のチェック *)
fun iter2 () =
let
val x1 = (x div 3) * 3
val y1 = (y div 3) * 3
fun iter3 _ 3 = true
| iter3 3 j = iter3 0 (j + 1)
| iter3 i j =
if Array2.sub(board, y1 + j, x1 + i) = n then false
else iter3 (i + 1) j
in
iter3 0 0
end
in
iter1 0 andalso iter2 ()
end
(* 盤面の表示 *)
fun print_board _ _ 9 = print "\n"
| print_board b 9 y = (print "\n"; print_board b 0 (y + 1))
| print_board b x y =
(
print (Int.toString (Array2.sub(b, y, x)) ^ " ");
print_board b (x + 1) y
)
(* 単純な深さ優先探索 *)
fun solver xs =
let
val board = Array2.fromList xs
fun dfs _ 9 = print_board board 0 0
| dfs 9 y = dfs 0 (y + 1)
| dfs x y =
if Array2.sub(board, y, x) <> 0 then dfs (x + 1) y
else
app (fn n => if check(board, n, x, y) then
(
Array2.update(board, y, x, n);
dfs (x + 1) y;
Array2.update(board, y, x, 0)
)
else ())
[1,2,3,4,5,6,7,8,9]
in
dfs 0 0
end
(*
* 問題 (出典: 数独 - Wikipedia の問題例)
*)
val qs = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
それでは実行してみましょう。
- solver qs; 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 val it = () : unit
三目並べは簡単なゲームなので、ゲーム終了まで読み切ることができます。局面の状態は、○側の勝ち、×側の勝ち、引き分けの 3 通りしかありません。あとは、ミニマックス法により最善手を選択させ、その結果を求めればいいわけです。とりあえず、プログラムでは指し手を保存しないで、評価値の結果だけを出力することにします。初手をどこに選んでも、引き分けの評価値が出力されるはずです。
三目並べとミニにマックス法については、拙作のページ「お気楽 Common Lisp プログラミング入門」の「ミニマックス法と三目並べ」で詳しく説明しています。そのプログラムを SML/NJ で書き直すと次のようになります。
リスト : 三目並べ
(* 駒 *)
datatype Piece = Maru | Batu | Kara
(* 定数 *)
val MaxValue = 2
val MaruWin = 1
val Draw = 0
val BatuWin = ~1
val MinValue = ~2
(* 盤面 *)
(*
* 0 1 2
* 3 4 5
* 6 7 8
*)
val SIZE = 9
val board = Array.array(SIZE, Kara)
(* 直線 *)
val line = Array.fromList(
[[(1, 2), (3, 6), (4, 8)], (* 0 *)
[(0, 2), (4, 7)], (* 1 *)
[(0, 1), (5, 8), (4, 6)], (* 2 *)
[(0, 6), (4, 5)], (* 3 *)
[(1, 7), (3, 5), (0, 8), (2, 6)], (* 4 *)
[(2, 8), (3, 4)], (* 5 *)
[(0, 3), (2, 4), (7, 8)], (* 6 *)
[(1, 4), (6, 8)], (* 7 *)
[(0, 4), (2, 5), (6, 7)]] (* 8 *)
)
(* アクセス関数 *)
fun get_piece n = Array.sub(board, n)
fun put_piece(n, p) = Array.update(board, n, p)
fun del_piece n = Array.update(board, n, Kara)
(* 3 つ同じ駒が並ぶか *)
fun check_line(p, a, b) = get_piece(a) = p andalso get_piece(b) = p
(* 勝負の判定 *)
fun check_win(n, p) =
let
fun iter([]) = false
| iter((a, b)::xs) =
if check_line(p, a, b) then true else iter(xs)
in
iter(Array.sub(line, n))
end
(* 先手 *)
fun think_maru n =
if n = SIZE then Draw
else
let
fun iter 9 value = value
| iter x value =
if get_piece x = Kara then
if check_win(x, Maru) then MaruWin
else (
put_piece(x, Maru);
let
val v = think_batu (n + 1)
in
del_piece x;
iter (x + 1) (if value < v then v else value)
end)
else iter (x + 1) value
in
iter 0 MinValue
end
(* 後手 *)
and think_batu n =
if n = SIZE then Draw
else
let
fun iter 9 value = value
| iter x value =
if get_piece x = Kara then
if check_win(x, Batu) then BatuWin
else (
put_piece(x, Batu);
let
val v = think_maru (n + 1)
in
del_piece x;
iter (x + 1) (if value > v then v else value)
end)
else iter (x + 1) value
in
iter 0 MaxValue
end
(* 解法 *)
fun solver(9) = ()
| solver(n) =
(
put_piece(n, Maru);
print(Int.toString(n) ^ " : " ^ Int.toString(think_batu 1) ^ "\n");
del_piece n;
solver (n + 1)
)
それでは実行結果を示しましょう。
- solver 0; 0 : 0 1 : 0 2 : 0 3 : 0 4 : 0 5 : 0 6 : 0 7 : 0 8 : 0 val it = () : unit
初手がどこでも、結果は引き分けとなりました。これで、両者が最善を尽くすと引き分けになることが確かめられました。
それでは、ルールを「3 つ並べた方が負け」に変更すると、結果はどうなるでしょうか。プログラムは簡単に改造できます。関数 think_maru では、Maru が 3 つ並んでいたら MaruWin を出力していましたが、これを BatuWin に変更します。逆に、think_batu で Batu が 3 つ並んでいたら MaruWin を出力します。ようするに、勝敗の判定を逆にするだけです。
このルールでは先手が不利なように思いますが、それでも引き分けになるのでしょうか。さっそく実行してみましょう。
- solver 0; 0 : ~1 1 : ~1 2 : ~1 3 : ~1 4 : 0 5 : ~1 6 : ~1 7 : ~1 8 : ~1 val it = () : unit
初手が中央の場合のみ引き分けで、あとは後手の勝ちとなりました。後手必勝にはなりませんでしたね。興味のある方は、実際にプレイして確かめてみてください。また、今回のプログラムは評価値を出力するだけでしたが、指し手を表示するように改造してみるのも面白いと思います。