Common Lisp 入門 の番外編です。今回は「三目並べ」のプログラムを Common Lisp で作ってみましょう。なお、このドキュメントは拙作のページ Memorandum で取り上げた「三目並べ」をまとめたものです。内容は重複していますが、ご了承くださいませ。
三目並べは、皆さんお馴染みの二人で対戦するゲームです。ひとりが○側でもうひとりが×側を受け持ち、3 行 3 列のマス目に○×を書いて、3 つ並べた方が勝ちというゲームです。下図は○側が先手で引き分けになった例です。
┌─┬─┬─┐ │×│○│○│ ├─┼─┼─┤ │○│○│×│ ├─┼─┼─┤ │×│×│○│ └─┴─┴─┘ 図：三目並べ
三目並べは、両者が最善を尽くすと引き分けになることが知られています。実際、ミニマックス法を使って確かめてみると、初手がどこでも結果は引き分けになります。興味のある方は拙作のページ Puzzle DE Programming 三目並べ をお読みくださいませ。
ところで、参考文献 [1] によると、三目並べで両者が次の戦略を用いると、ゲームは常に引き分けになります。
本当に引き分けになるのか、プログラムを作って確かめてみましょう。
最初に、ゲームに必要なデータ構造を定義します。
┌─┬─┬─┐ │０│１│２│ ├─┼─┼─┤ │３│４│５│ ├─┼─┼─┤ │６│７│８│ └─┴─┴─┘ 図：盤面の番号
リスト：データ構造の定義
; 直線
(defvar *line*
'((0 1 2) (3 4 5) (6 7 8) (0 3 6)
(1 4 7) (2 5 8) (0 4 8) (2 4 6)))
; 場所と直線の関係
(defvar *position-line*
#(((1 2) (4 8) (3 6)) ; 0
((0 2) (4 7)) ; 1
((0 1) (4 6) (5 8)) ; 2
((0 6) (4 5)) ; 3
((0 8) (1 7) (2 6) (3 5)) ; 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
盤面はベクタ board で表します。先手 ○ をシンボル maru で、後手 × をシンボル batu で、空き場を nil で表します。盤面の場所とベクタの対応は、上図左のように定義します。すると、駒が 3 つ並ぶ直線はリスト *line* で表すことができます。そして、場所から直線を求めるためベクタ *position-line* を定義します。たとえば、場所 0 が属する直線は 3 本あって、残り 2 か所の場所は (1 2), (4 8), (3 6) となります。
勝敗の判定は *line* を使うと簡単です。次のリストを見てください。
リスト：勝敗の判定
(defun check-win (board)
(dolist (x *line*)
(let ((piece (aref board (first x))))
(if (and piece
(eq piece (aref board (second x)))
(eq piece (aref board (third x))))
(return piece)))))
関数 check-win は 8 本の直線を調べ、同じ駒が 3 つ並んでいるか調べます。直線の先頭に maru か batu があり、残り 2 つの場所に同じ駒があれば 3 つ並んでいることがわかります。maru が 3 つ並んでいれば maru を、batu が 3 つ並んでいれば batu を返します。どちらも 3 つ並んでいなければ nil を返します。
次は同じ駒を 3 つ並べることができる場所を探す関数 get-win-position を作ります。
リスト：駒を 3 つ並べられるか
(defun get-win-position (turn board)
(dotimes (x 9)
(unless (aref board x)
(dolist (y (aref *position-line* x))
(if (and (eq (aref board (first y)) turn) ; 残り 2 か所が同じ駒
(eq (aref board (second y)) turn))
(return-from get-win-position x))))))
この処理は次の 1 手で勝てる場所を探すことになるので、関数名を get-win-position としました。引数 turn は駒の種類を、変数 x は調べる場所を表します。まず、場所 x があいているかチェックします。あとは *position-line* から直線を取り出して、残り 2 か所の駒が turn と同じであれば、駒を 3 つ並べることができます。return-from で場所 x を返します。
次はコンピュータの指し手を決める関数 move-com を作ります。
リスト：コンピュータの指し手を決定する
; 空いている隅を返す
(defun get-corner-position (board)
(dolist (x '(0 2 6 8))
(if (null (aref board x)) (return x))))
; 空いている場所を返す
(defun get-space-position (board)
(dotimes (x 9)
(if (null (aref board x)) (return x))))
; コンピュータの指し手を決める
(defun move-com (turn board)
(let (pos)
; 自分の手番で勝ちがあるか
(setq pos (get-win-position turn board))
(unless pos
; 相手の手番で勝ちがあるか
(setq pos (get-win-position (if (eq 'maru turn) 'batu 'maru) board))
(unless pos
; 中央が空いているか
(setq pos 4)
(when (aref board 4)
; 隅が取れるか
(setq pos (get-corner-position board))
(unless pos
; 空き場所を返すだけ
(setq pos (get-space-position board))))))
; 場所を返す
pos))
関数 move-com は戦略に従ってコンピュータの指し手を決定します。引数 turn は自分の駒の種類を表します。最初に get-win-position を呼び出して、駒を 3 つ並べることができるか調べます。自分が勝てるのであれば、その場所 pos に駒を置きます。そうでなければ、相手が駒を 3 つ並べることができるか調べます。これは get-win-position で相手の駒の種類を渡せば調べることができます。そうであれば、その場所 pos に自分の駒をおきます。
それ以外の場合は、優先順位（中央 -> 隅 -> 空き場所) に従って駒を置きます。空いている隅は関数 get-corner-position で求めます。空き場所は関数 get-space-position で求めます。最後に指し手 pos を返します。これで戦略に従ってコンピュータの指し手を決定することができます。
あとはとくに難しいところはないでしょう。詳細は プログラムリスト をお読みくださいませ。
それでは実行結果を示します。動作は clisp と xyzzy Lisp で確認しました。xyzzy Lisp の場合、*scratch* で関数 tic-tac-toe を評価してください。引数が 'maru だと人間側が先手、'batu だと人間側が後手、それ以外だとコンピュータ側が先手と後手の両方を受け持ちます。
盤面 先手 4 後手 0 先手 2 後手 6 ０ １ ２ ＿ ＿ ＿ × ＿ ＿ × ＿ ○ × ＿ ○ ３ ４ ５ ＿ ○ ＿ ＿ ○ ＿ ＿ ○ ＿ ＿ ○ ＿ ６ ７ ８ ＿ ＿ ＿ ＿ ＿ ＿ ＿ ＿ ＿ × ＿ ＿ 先手 3 後手 5 先手 8 後手 1 先手 7 × ＿ ○ × ＿ ○ × ＿ ○ × × ○ × × ○ ○ ○ ＿ ○ ○ × ○ ○ × ○ ○ × ○ ○ × × ＿ ＿ × ＿ ＿ × ＿ ○ × ＿ ○ × ○ ○
確かに引き分けになりますね。そこで問題です。
相手が次の戦略を用いる場合、先手に必勝法があります。それを見つけてください。
簡単な問題なので、息抜きや気分転換のときにちょっと考えてみてください。
;
; tictactoe.l : 三目並べ
;
; Copyright (C) 2004,2005 Makoto Hiroi
;
; 盤面
; 0 1 2
; 3 4 5
; 6 7 8
; 場所と直線の関係
(defvar *position-line*
#(((1 2) (4 8) (3 6)) ; 0
((0 2) (4 7)) ; 1
((0 1) (4 6) (5 8)) ; 2
((0 6) (4 5)) ; 3
((0 8) (1 7) (2 6) (3 5)) ; 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
; 直線
(defvar *line*
'((0 1 2) (3 4 5) (6 7 8) (0 3 6)
(1 4 7) (2 5 8) (0 4 8) (2 4 6)))
; 3 個並ぶ場所を返す
(defun get-win-position (turn board)
(dotimes (x 9)
(unless (aref board x)
(dolist (y (aref *position-line* x))
(if (and (eq (aref board (first y)) turn) ; 残り 2 か所が同じ駒
(eq (aref board (second y)) turn))
(return-from get-win-position x))))))
; 空いている隅を返す
(defun get-corner-position (board)
(dolist (x '(0 2 6 8))
(if (null (aref board x)) (return x))))
; 空いている場所を返す
(defun get-space-position (board)
(dotimes (x 9)
(if (null (aref board x)) (return x))))
; 盤面を表示する
(defun print-board (board)
(let ((piece-list '((maru . "○") (batu . "×") (nil . "・"))))
(dotimes (x 9)
(format t "~A " (cdr (assoc (aref board x) piece-list)))
(if (or (= x 2) (= x 5) (= x 8)) (terpri)))))
; 勝利判定
(defun check-win (board)
(dolist (x *line*)
(let ((piece (aref board (first x))))
(if (and piece
(eq piece (aref board (second x)))
(eq piece (aref board (third x))))
(return piece)))))
; 終了判定
(defun game-over (board)
(let ((win (check-win board)))
(cond (win
(format t "~A の勝ち" win)
t)
((null (get-space-position board))
(format t "引き分け")
t)
(t nil))))
; コンピュータの指し手を決める
(defun move-com (turn board)
(let (pos)
; 自分の手番で勝ちがあるか
(setq pos (get-win-position turn board))
(unless pos
; 相手の手番で勝ちがあるか
(setq pos (get-win-position (if (eq 'maru turn) 'batu 'maru) board))
(unless pos
; 中央が空いているか
(setq pos 4)
(when (aref board 4)
; 隅が取れるか
(setq pos (get-corner-position board))
(unless pos
; 空き場所を返すだけ
(setq pos (get-space-position board))))))
; 場所を返す
pos))
; 人間側の指し手
(defun move-human (board)
(loop
(format t "指し手 > ")
(let ((pos (read)))
(if (and (integerp pos)
(<= 0 pos 8)
(null (aref board pos)))
(return pos))
(format t "正しい数値を入力してください~%"))))
;
; 三目並べ
; trun = maru 先手
; batu 後手
;
(defun tic-tac-toe (&optional (human 'maru))
(let ((board (make-array 9)) (turn 'maru) pos)
(format t "三目並べ~%")
(print-board board)
(loop
(setq pos
(if (eq human turn)
(move-human board)
(move-com turn board)))
(format t "~%~D におきます~%" pos)
(setf (aref board pos) turn)
(print-board board)
(setq turn (if (eq turn 'maru) 'batu 'maru))
; ゲーム終了のチェック
(if (game-over board) (return)))))
解答の一例を示します。
盤面 先手 0 後手 4 先手 8 後手 2
０ １ ２ ○ ＿ ＿ ○ ＿ ＿ ○ ＿ ＿ ○ ＿ ×
３ ４ ５ ＿ ＿ ＿ ＿ × ＿ ＿ × ＿ ＿ × ＿
６ ７ ８ ＿ ＿ ＿ ＿ ＿ ＿ ＿ ＿ ○ ＿ ＿ ○
（Ａ）
先手 6 後手 3 先手 7
○ ＿ × ○ ＿ × ○ ＿ × 先手の勝ち！
＿ × ＿ × × ＿ × × ＿
○ ＿ ○ ○ ＿ ○ ○ ○ ○
初手を中央ではなく隅へ着手するのがポイントです。後手は戦略に従って中央を取るので、次は初手の対角線上にある隅を取ります (局面 A)。後手が戦略に従う場合、次は隅を取ることになりますね。どちらの隅を取っても、先手は残りの隅を取れば勝つことができます。
もちろん、後手が戦略に従わなければ、局面 A からでも引き分けになります。一例を示しましょう。
盤面 先手 0 後手 4 先手 8 後手 1
０ １ ２ ○ ＿ ＿ ○ ＿ ＿ ○ ＿ ＿ ○ × ＿
３ ４ ５ ＿ ＿ ＿ ＿ × ＿ ＿ × ＿ ＿ × ＿
６ ７ ８ ＿ ＿ ＿ ＿ ＿ ＿ ＿ ＿ ○ ＿ ＿ ○
（Ａ）
先手 7 後手 6 先手 2 後手 5 先手 3
○ × ＿ ○ × ＿ ○ × ○ ○ × ○ ○ × ○ 引き分け
＿ × ＿ ＿ × ＿ ＿ × ＿ ＿ × × ○ × ×
＿ ○ ○ × ○ ○ × ○ ○ × ○ ○ × ○ ○
このように、局面 A で後手が隅を取らなければ引き分けになります。
Common Lisp 入門 の番外編です。今回はパズル「変形魔方陣」の解法プログラムを Common Lisp で作ってみましょう。なお、このドキュメントは拙作のページ Memorandum で取り上げた「変形魔方陣」をまとめたものです。内容は重複していますが、ご了承くださいませ。
それでは問題です。
┌─┬─┬─┐ 式
│Ａ│Ｂ│Ｃ│ A + B + E + D = N
├─┼─┼─┤ B + C + F + E = N
│Ｄ│Ｅ│Ｆ│ D + E + H + G = N
├─┼─┼─┤ E + F + I + H = N
│Ｇ│Ｈ│Ｉ│ A + C + I + G = N
└─┴─┴─┘
図：変形魔方陣
上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。図では、A - B - E - D のように 2 * 2 マスの正方形が 4 つ、大きな正方形 (A - C - I - G) がひとつあります。魔方陣は縦横斜めの合計が等しくなるように数字を配置しますが、今回は上図の式で表すように、正方形の頂点の合計が等しくなるような配置を見つけてください。
出典は 『Ｃマガ電脳クラブ第 92 回 変形魔方陣』, C MAGAZINE 1998 年 8 月号, ソフトバンク です。Ｃマガ電脳クラブの問題は、2 * 2 マスの数字の合計が等しくなることが条件でしたが、今回は大きな正方形も条件に加えてみました。
プログラムを作る場合、対称解のチェックは面倒だと思われる方もいるでしょう。ところが、下図のように四隅の大小関係を利用すると簡単です。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│
├─┼─┼─┤ A < C < G
│Ｄ│Ｅ│Ｆ│
├─┼─┼─┤ A < I
│Ｇ│Ｈ│Ｉ│
└─┴─┴─┘
図：対称解のチェック
魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。また、早い段階で枝刈りを行うため、盤面の番号と試行順序を工夫します。
┌─┬─┬─┐
│０│４│１│ (1) B[0] + B[1] + B[2] + B[3] = N
├─┼─┼─┤ (2) B[0] + B[4] + B[5] + B[6] = N
│５│６│７│ (3) B[1] + B[4] + B[6] + B[7] = N
├─┼─┼─┤ (4) B[2] + B[5] + B[6] + B[8] = N
│２│８│３│ (4) B[3] + B[6] + B[7] + B[8] = N
└─┴─┴─┘
図：盤面の番号と試行順序
盤面を 1 次元配列 B で表すことにします。試行順序を上図のように定義し、配列の添字と対応させます。そうすると、最初に四隅 (0, 1, 2, 3) の数字が選択されますね。ここで対称解のチェックが行われるので、枝刈りの効率は良くなります。また、数字の合計値 N も決めることができるので、あとは 2 * 2 マスの正方形が完成したら、合計値が N と等しいかチェックしていくだけです。
M.Hiroi のマシンはオンボロなので、枝刈りをちょっと工夫してみました。まあ、最近のパソコンであれば、こんなことをしなくても単純な生成検定法で高速に解けると思います。
プログラムは次のようになります。配列を使っているので Lisp らしくありませんが、ほかのプログラミング言語に移植するのは簡単でしょう。興味のある方は挑戦してみてください。
リスト：解法プログラム
; 盤面
(defvar *board* (make-array 9))
; 解の表示
(defun print-answer ()
(format t "~D ~D ~D~%~D ~D ~D~%~D ~D ~D~%~%"
(aref *board* 0) (aref *board* 4) (aref *board* 1)
(aref *board* 5) (aref *board* 6) (aref *board* 7)
(aref *board* 2) (aref *board* 8) (aref *board* 3)))
; 4 つの数字を足し算する
(defun add-number (a b c d)
(+ (aref *board* a) (aref *board* b) (aref *board* c) (aref *board* d)))
; 枝刈り
(defun checkp (n value)
(or (and (= n 1) (> (aref *board* 0) (aref *board* 1)))
(and (= n 2) (> (aref *board* 1) (aref *board* 2)))
(and (= n 3) (> (aref *board* 0) (aref *board* 3)))
(and (= n 6) (/= value (add-number 0 4 5 6)))
(and (= n 7) (/= value (add-number 1 4 6 7)))))
; 解法
(defun solve (&optional (n 0) (numbers '(1 2 3 4 5 6 7 8 9)) value)
(dolist (x numbers)
(setf (aref *board* n) x)
; 枝刈り
(unless (checkp n value)
; value のセット
(if (= n 3)
(setq value (add-number 0 1 2 3)))
; 解けたか
(cond ((= n 8)
(if (= value (add-number 2 5 6 8) (add-number 3 6 7 8))
(print-answer)))
(t (solve (1+ n) (remove x numbers) value))))))
次は 8 個の数字を使う魔方陣です。それでは問題です。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│ 式
├─┼─┼─┤ A + B + C = N
│Ｄ│ │Ｅ│ A + D + F = N
├─┼─┼─┤ C + E + H = N
│Ｆ│Ｇ│Ｈ│ F + G + H = N
└─┴─┴─┘
図：変形魔方陣
上図の A から H の場所に 1 から 8 までの数字をひとつずつ配置します。4 辺の合計が等しくなるような配置を見つけてください。なお、合計の値 (N) は 12, 13, 14, 15 の 4 通りの場合があります。
プログラムの作成は簡単です。問題１のプログラムを改造するだけです。特に難しいところはないので、説明は省略いたします。詳細は プログラムリスト をお読みくださいませ。
ところで、問題２は数字 { 1, 2, 3, 4, 5, 6, 7, 8 } を使いましたが、数字を奇数 { 1, 3, 5, 7, 9, 11, 13, 15 } にする、または、数字を偶数 { 2, 4, 6, 8, 10, 12, 14, 16 } にするとどうなるでしょうか。実は、問題２の答えがわかると簡単に解くことができます。答えを見る前に、ちょっと考えてみてくださいね。
最後は素数を使った変形魔方陣です。
┌─┬─┬─┐
│Ａ│Ｂ│Ｃ│ 式
├─┼─┼─┤ A + B + C = N
│Ｄ│ │Ｅ│ A + D + F = N
├─┼─┼─┤ C + E + H = N
│Ｆ│Ｇ│Ｈ│ F + G + H = N
└─┴─┴─┘
図：素数の変形魔方陣
上図の A から H の場所に素数 { 3, 5, 7, 11, 13, 17, 19, 23 } をひとつずつ配置します。4 辺の合計が等しくなるような配置を見つけてください。なお、合計の値 (N) も素数になります。
;
; 変形魔方陣の解法プログラム
;
; Copyright (C) 2004,2005 Makoto Hiroi
;
; 盤面
;
; ０４１
; ５ ６ 0 < 1 < 2, 0 < 3
; ２７３
;
(defvar *board* (make-array 8))
; 解の表示
(defun print-answer (rest-num)
(format t "Rest ~A, Sum ~D~%" rest-num (add-number 0 4 1))
(format t "~2D ~2D ~2D~%~2D ~2D~%~2D ~2D ~2D~%~%"
(aref *board* 0) (aref *board* 4) (aref *board* 1)
(aref *board* 5) (aref *board* 6)
(aref *board* 2) (aref *board* 7) (aref *board* 3)))
; 数字を足し算する
(defun add-number (n1 n2 n3)
(+ (aref *board* n1) (aref *board* n2) (aref *board* n3)))
; 枝刈り
(defun checkp (n value)
(or (and (= n 1) (> (aref *board* 0) (aref *board* 1)))
(and (= n 2) (> (aref *board* 1) (aref *board* 2)))
(and (= n 3) (> (aref *board* 0) (aref *board* 3)))
(and (= n 5) (/= value (add-number 0 5 2)))
(and (= n 6) (/= value (add-number 1 6 3)))))
; 解法
(defun solve (&optional (n 0) (numbers '(1 2 3 4 5 6 7 8)) value)
(dolist (x numbers)
(setf (aref *board* n) x)
; 枝刈り
(unless (checkp n value)
; value のセット
(if (= n 4)
(setq value (add-number 0 1 4)))
; 解けたか
(cond ((= n 7)
(if (= value (add-number 2 7 3))
(print-answer (remove x numbers))))
(t (solve (1+ n) (remove x numbers) value))))))
対称解（回転解と鏡像解）を除くと、解は下図の 1 通りしかありません。
┌─┬─┬─┐ │１│８│３│ ├─┼─┼─┤ │６│５│４│ ├─┼─┼─┤ │７│２│９│ └─┴─┴─┘
解の個数は対称解（回転解と鏡像解）を除いた場合です。
┌─┬─┬─┐ │１│８│３│ ├─┼─┼─┤ │５│ │７│ ├─┼─┼─┤ │６│４│２│ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ │１│７│５│ │１│８│４│ ├─┼─┼─┤ ├─┼─┼─┤ │４│ │６│ │７│ │３│ ├─┼─┼─┤ ├─┼─┼─┤ │８│３│２│ │５│２│６│ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ ┌─┬─┬─┐ │１│６│７│ │３│７│４│ ├─┼─┼─┤ ├─┼─┼─┤ │５│ │３│ │６│ │２│ ├─┼─┼─┤ ├─┼─┼─┤ │８│２│４│ │５│１│８│ └─┴─┴─┘ └─┴─┴─┘
┌─┬─┬─┐ │３│５│７│ ├─┼─┼─┤ │４│ │２│ ├─┼─┼─┤ │８│１│６│ └─┴─┴─┘
偶数 { 2, 4, 6, 8, 10, 12, 14, 16 } の場合は、問題２の数字を 2 倍することで求めることができます。奇数 { 1, 3, 5, 7, 9, 11, 13, 15 } の場合は、数字を 2 倍して -1 することで求めることができます。下図に一例を示します。
┌─┬─┬─┐ ┌─┬─┬─┐ ┌─┬─┬─┐ │１│８│３│ │２│16│６│ │１│15│５│ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ │５│ │７│ │10│ │14│ │９│ │13│ ├─┼─┼─┤ ├─┼─┼─┤ ├─┼─┼─┤ │６│４│２│ │12│８│４│ │11│７│３│ └─┴─┴─┘ └─┴─┴─┘ └─┴─┴─┘ 問題２の解 （Ａ）偶数の場合 （Ｂ）奇数の場合
┌─┬─┬─┐ 合計値 N = 31（素数） │３│23│５│ ├─┼─┼─┤ │17│ │19│ ├─┼─┼─┤ │11│13│７│ └─┴─┴─┘