急に三目並べ(いわゆる○×ゲーム)のプログラムを書きたくなったんで、書く。
言語はRacketを使う。
・盤面
まずは盤面設定を考えるが、これはリストのリストとしてみよう。
例えば
'((x o o) (o x o) (x #f x))
みたいな3x3のリストを盤面とするわけだ。
#fはいまだoもxも置かれてない「空の」スペースと解釈する。
・勝敗判定
最初に勝敗判定関数を考えよう。
平たく言うと、三目並べ(tic-tac-toe)は3つ並んだマス目が全部oかxになれば「ゲーム終了」となる。
この「3つ並んだ」は縦、横、斜めの3ケースがあり得るわけだが、取り敢えず「リストのリスト」を受け取った時に要素側のリストが全部oなのかxなのか、を調べる関数を書けばいいわけだ。
この「全部がなんかの同一要素」かどうかを調べるには、srfi-1のeveryと言う関数が流用出来る。
(define (check puzzle)
(define (check-help letter)
(call/cc
(lambda (return)
(foldl (lambda (row init)
(and (every (lambda (cell)
(eq? cell letter)) row)
(return (car row)))) #f puzzle))))
(or (check-help 'o) (check-help 'x)))
この関数のポイントは以下の通り。
ローカル関数内のfoldlでリスト内リストの全要素が引数letterと同じか調べていくが、「三要素が全部同じだ」と言うことが分かった時点でcall/ccでその要素((car row))を持って「脱出」する。全リストを必ずしも調べるわけじゃない・・・と言うのも、あるリストの3つの要素が同じな時点で勝敗は決定し、残りを走査する必要はないから、だ。
このfoldl + 脱出、と言う技法は純粋な関数型言語ユーザーは眉を顰めるやり方かもしんない・・・事実、似たようなことがOCamlでも可能なのか、と海外のOCamlユーザーにも尋ねたこともあったんだけど
「Schemeでもこういうやり方は好まれてないんじゃないのかなぁ」
等と言われたことがあった。
しかしこれは逆に言うと朗報なんだよ。Lispでは理論的にそう動ける、って思えることはそう書ける、ってことなんだ。そして通常の関数型言語だと高階関数(イテレータ)の動作を途中で止める手段がない。大体そのテの実装上の言い訳がついて回るが、Lispにはそういうことがない。言い換えると、プログラムを組む側の思惑を言語の仕様や実装が邪魔をすることがないんだ。
それはプログラミング言語では極めて珍しい(※1)。
また同様に、Pythonのリスト内包表記も途中で中断する手段がない。イテレータを自在に止めることが可能だ、と言うLispの自由度の高さをむしろ褒め称えるべきだと思う(※2)。
さて、次に横・・・行列で言うと行のチェック関数を書く。
(define rows check)
これは基本的に先に書いた関数、checkをラッピングしただけ、だ。名前を変えただけ、だが、それが「行をチェックしてる」と言う目的をハッキリさせる。
次は縦(列)のチェック関数を書く。列は引数である「リストのリスト」をsrfi-1のzipを使うことで組み上げられる。
(define (columns puzzle)
(check (apply zip puzzle)))
最後に斜めをチェックする関数を書く。一旦与えられたリストのリストを行へと分解して、斜めの要素で構成されたリストを2つ生成してcheckする。
(define (diagonals puzzle)
(match-let ((`(,row1 ,row2 ,row3) puzzle))
(check `((,(car row1) ,(cadr row2) ,(caddr row3))
(,(caddr row1) ,(cadr row2) ,(car row3))))))
あとは、盤面(リストのリスト)が与えられた際にrows、 columns、diagonalsを順次適用して、縦、横、斜めが同要素で占められた時、その要素を持って脱出するように書けば勝敗判定関数の出来上がり、だ。
(define (winner puzzle)
(call/cc
(lambda (return)
(foldl (lambda (proc init)
(cond ((proc puzzle) => (lambda (x)
(return x)))
(else init))) #f `(,rows ,columns ,diagonals)))))
・出力用文字列整形
次は盤面の出力に使う文字列生成関数を書こう。
以前見たが、出力関数の複数回の呼び出しにはコストがかかる。
よって出力する際には「生成した文字列」を一気に、一回のみ、で呼び出した方がいい。そしてその辺を特にC言語ユーザーは気にせんわけだ。
一つの理由として、C言語では「文字列生成」を行うのがかなりかったるいんだ。一方、モダンな言語だと文字列を「操る」機能の提供が数多い。
結果、最初に文字列を自由に生成して一挙に出力、と言うのがモダンな言語だと望ましい方策になる。
(define (string-line line)
(map (lambda (sym)
(if sym
(symbol->string sym)
"_")) line))
(define (tic-out position)
(string-join
(map (lambda (line)
(string-join line ""))
(map string-line position)) "\n"))
基本的な発想は、リストの要素のシンボルを文字列に直して結合するだけ、だが、「空のマス」をアンダースコア(_)へと置き換えている。
また、リストとリストの間のセパレータとして改行文字を付け足している。
> (tic-out '((x o o) (o x o) (x #f x)))
"xoo\noxo\nx_x"
・メッセージ
次にプロンプト等の出力に使うメッセージを設定する。例によってメッセージ分離方式、だ。
今回のゲームに使うメッセージを次のように設定しよう。
(define *msg*
(hasheq 'choice "Do you want to be X or O?: "
'Error "Bad answer"
#t "Enter the number of the row and then the column: "
'Congratulation "Congratulations! You have won."
'brag "Ha-Ha! I won"
#f "Now I'll make my move."))
上から、初期化の際のメッセージ(自手がXかOか選ぶ)、エラーメッセージ、自手の入力を促すメッセージ、勝ったときのメッセージ、負けたときのメッセージ、コンピュータの番でのメッセージ、となる。
・環境設定
次にゲームで持ち回すデータの塊、環境を構造体で定義する。
(struct Env (turn sign board) #:transparent)
プレイヤーの手番、手番がXなのかOなのかのデータ、そして盤面であるリストのリスト、と3つのデータを保持させよう。
なお、turn(手番)は真偽値、手番の記号はハッシュテーブル、と言う想定だ。
また、XかOかを選べる、にせよ、プレイヤーは常に先手で、プレイヤーは#t(真)、コンピュータは#f(偽)の二値とする。
・環境の初期化
ここでプレイヤーは記号をXかOか選び、また、初期化された盤面が環境にセットされる。
(define (play-tic-tac-toe)
(Env #t (let ((ans (string->symbol
(string-upcase (input (hash-ref *msg* 'choice))))))
(cond ((eq? ans 'X) (hasheq #t 'x #f 'o))
((eq? ans 'O) (hasheq #t 'o #f 'x))
(else (raise-user-error 'failed))))
(make-list 3 (make-list 3 #f))))
なお、ここでは入力関数として、Pythonに影響を受けた自作ユーティリティinputを用いてる。そしてinputの返り値は文字列となる。
そして、初期化過程でユーザーにXかOかを選ばせるわけだが、そのどちらかが入力されなかった場合、例外を投げて終了する。ユーザーによる「入力エラー」に対しては、Racketではraise-user-errorと言うそのまんまの便利関数が用意されているのでそれを使おう。
さて、いよいよRead-Eval-Print Loopを作っていこう。
・Read
以前見たが、コンピュータとの対戦プレイだろうと何だろうと、REPLの構造は変わらない。
問題は「どの時点でコンピュータ・プレイヤーが介入するか」だが、その計算に於いては評価器(eval)が関わらない方がプログラムはシンプルになる。と言うか、コンピュータの思考ルーチンによる「入力」は人に用意されてる「入力」をコンピュータが奪った方がいい、と言うことだ。
これは麻雀だろうと何だろうと、そうデザインした方がラクだ、と言うことだ。
これを前提として、「人の為の入力機構」をコンピュータが「奪う」カタチにする。そしていつコンピュータが介入するのか、と言うのは、このゲームでは、環境のturnデータが#fになった時、だ。
(define (get-input env)
(match-let (((Env turn sign board) env))
(cond (turn
(match (map string->number
(regexp-split #rx"[ |,]+" (input (hash-ref *msg* turn))))
(`(,x ,y) #:do ((define-values (i j) (values (sub1 x) (sub1 y))))
#:when (not (list-ref (list-ref board i) j))
`(,i ,j))
(_ (raise-argument-error 'get-input "'input" env))))
(else (displayln (hash-ref *msg* turn))
(make-move env)))))
大枠は、turnが#t(真)だった時には人間のプレイヤーに入力を促し、#f(偽)だった時はコンピュータが手を入力する。コンピュータの手はmake-move関数で計算されるが、それは後回しだ。
人間の手の入力はinput関数で行う。想定としてはスペース区切り、あるいはカンマ区切りの2つの数値、と言うことにしてる。それらを含んだ文字列を性器正規表現で分割する。
想定はそうする、と言うことにするが、原則エラーチェックがない。例えば受け取った文字列が2分割にならない、とか、あるいは数値情報じゃなく文字情報でsub1出来ない、または入力値がリストの長さを超えている、等の不具合が考えられるが、ここでは「不具合が起きたら起きたでエエんじゃない?」と言う基本作戦になっている。そうだな、例外処理だ。
エラーが起きたらこの関数の外側(つまりREPL)でそれを捕まえて、正常に動くようにユーザーを誘導するんだ。
また、match式内では#:whenで「マス目が空に限り」と言う条件を付けている。マス目が既に埋まってる場合はここのパターンにハマらない。
結果、まとめてraise-argument-error(引数エラー)で例外を投げる。これも外枠のREPLで例外をキャッチして、そっちで処理させよう、ってこった。
なお、返り値としては、盤面のマスの座標(i, j)を意図したリストを返すこととなる。
・Eval
Eval(評価器)のやることは簡単だ。手順(turn)を反転させること。盤面(board)リストを更新すること、の2つがその役割になる。
実際は、盤面リストの更新がちとややこしいが、それは補助関数を書いて凌ごう。
(define (play-role x env)
(match-let (((Env turn sign board) env))
(Env (not turn) sign (enter x (hash-ref sign turn) board))))
(define (enter x sign board)
(let ((position (+ (* 3 (car x)) (cadr x))))
(let-values (((head tail) (split-at (flatten board) position)))
(match-let ((`(,a ,b ,c ,d ,e ,f ,g ,h ,i) `(,@head ,sign ,@(cdr tail))))
`((,a ,b ,c) (,d ,e, f) (,g ,h ,i))))))
評価器play-roleは入力xと環境envを受け取り、まずはenvをスロットへと分解し、そして環境を組み立て直して返す、と言うのが大枠だ。その際、turnで与えられた真偽値を反転させ、補助関数enterで盤面を構築し直す。
さて、リストのリストを構築し直すのが補助関数enterの役割だが、これがちとややこしい。一般にリストのリスト・・・となると、その中の特定要素を「書き換える」と言うのは極めて面倒くさい。単なるリストをcarしたりcdrしたり・・・と言うのは至極簡単なんだけど、二次元になると途端に難易度が跳ね上がるんだ。
実はC言語もそうなんだけど、この辺「上手いことやる」ハッカーなんかは二次元配列なんかをマトモに扱わない。代わりに二次元配列として想定されるブツを敢えて一次元配列として記述して「操作を簡単にする」ってことを良くやるんだ。LispとC言語は抽象度の上下では天と地程の差があるが、「二次元配列の扱い」に関して言うと、一周回って同じ結論になってしまう(笑)。もっと言うと、Lispやその他の抽象度の高い言語でも、二次元配列あるいはリストの抽象化は不十分だ、と言う言い方が出来るだろう。今後、「新しく抽象化を導入する」と言う辺りだと二次元配列/リストの操作がブルーオーシャンになるかも、と言う予想が出来る(※3)。
補助関数enterはまずは受け取った座標データ(i, j)を3i + jのカタチ、つまり「一次元リストの何番目の要素を指すか」の形式へと変換する(position)。例えば座標(0, 1)は1、(0, 2)は2、(2, 2)は8、(1, 2)は5、となる。
|0|1|2||3|4|5||6|7|8|
検算して確かめて欲しい。
そしてboardをflattenして一次元のリストに直したものを位置positionで分割してhead部とtail部へと分ける。tail部のcarが挿げ替え対象の要素なんで、それをsign(つまりXかO)で置き換えて再び一次元のリストに戻し、さらに二次元リストへと戻す。
手順自体は簡単ではあるんだけど、思いついたり書いたりするのが面倒と言えば面倒な補助関数ではある。
・Print
出力関数Printも簡単だ。既に出力用の文字列整形関数tic-outを書いてるんで、環境envから盤面boardを引っこ抜いてきてtic-outを適用してから出力すればいい。
(define (print env)
(displayln (tic-out (Env-board env)))
env)
最後に与えられた環境envをそのまま返すのを忘れないようにしよう。
・AI
さて、Read、Eval、Printを書き上げたんで、この3つを組み合わせてループさせればREPL完成、ソフトウェア完成、だ。
その前に、このゲームは「コンピュータと対戦する」わけで、コンピュータの手の思考ルーティンを書かなければならない。今風に言うと「人工知能」を書かないとならないわけだ。
現時点、REPLのRead部分で、順番が来ると「コンピュータが人からの入力を奪う」ことで「対戦ゲーム」を成立させている。このモデルが優秀なのは、コンピュータの思考ルーティンがREPLからも、敢えて言うと「独立してて」、「もっと強い対戦相手にしたい」と言う場合、思考ルーティンを「すげ替えれば」いくらでも強いAIを利用することが出来る。ここではmake-move関数はどのような実装にしてもいい、と言うことだが、結果、REPLのシステムは「ゲームプレイの為のガワ」として成立し、「コンピュータの思考ルーティン」部分は独立したモジュールになってて完全に切り離されている、ってことだ。
この考え方は色々と応用可能だ。例えばターン制のRPGの「敵の動き」も独立してて「プレイヤーの入力を奪って」成立させることが可能だし、「全ては逐次実行が基本」のコンピュータ・プログラムでは、(計算と)動作が速いだけ、でシューティングゲームでさえ同様の「人から入力を奪う」ことで成立出来る可能性さえある(※4)。
さて、ここでは、三目並べのAIとして超古典的な・・・21世紀、2020年代の現代ではとてもAIとは呼べないが・・・思考ルーティンの実装法を紹介しよう。
我々が実際人と三目並べを対戦する際、「どこのマス目に自手を置けば有利になるか」と言うのを経験則的に把握してると思う。要は「全てのマス目の価値は平等ではない」っちゅーわけだ。
つまり、これを利用して、「三目並べのマス目に点数らしきものを付ける」わけだ。
ここではこのように評価してみる。
|2|6|4||7|1|8||5|9|3|
ここでは数が少なければそのマス目の価値が高い、と言うことにしている。
このマス目の評価法を「重み付け」等と呼ぶ(※5)。
中央が一番価値がある、のはここを押さえておけば上下左右斜めへとどこにも伸びていけるからだ。また、角を押さえておくのは中央の十字ラインを押さえるより有利にゲームを展開できるから、だ。
要は「取るべきマス目」の順序を先に決定しておき、マスが空の時に、順序良くマスを埋めていけば、超古典的AIが成立する、ってことだ・・・1960年代の人工知能黎明期ではこういう手法から研究がスタートしてるわけだ。
(define *choose-move* '((1 1) (0 0) (2 2) (0 2) (2 0) (0 1) (1 0) (1 2) (2 1)))
(define (make-move env)
(match-let (((Env turn sign board) env))
(call/cc
(lambda (return)
(map (lambda (position)
(match-let ((`(,i ,j) position))
((if (list-ref (list-ref board i) j)
identity
return) position))) *choose-move*)))))
*choose-move*はマス目の優先順位を定義したリストで、そのリストを先頭から走査し、boardのマス目が空、つまり#fだった時にその座標を持って脱出する・・・それだけ、で「コンピュータの思考ルーティン」として成立する。
非常に単純なアルゴリズムだが、最低限、対人間としては役立たないわけではない・・・いや、決して強くはないけどね(笑)。ただ、「AI」と呼ばれるモノに対して、なんか不気味であるとか、とてつもない黒魔術だと思い込んでる人に対しては、「こういう単純な仕組み」から研究が発展して来たんだよ、と言いたい。最初の取っ掛かり、なんてのはこんな程度、だったんだ。
これから何十年も先のAlphaGoの、遠い祖先がこういう単純な思考ルーティンだったわけだ。
あとはREPLを書けばソフトウェアとして成立する。例外処理だ何だ、ってのを付け足す必要はあるが、その辺の「組み立て方」は毎度毎度同じなんで特に取り上げない。
よって今回の記事はここで終了しよう。
なお、完成したソースコードはここに置いておく。
 | これがLISPだ (Information&Computing 30) J.R.アンダーソン サイエンス社 |
※1: 他の言語だと仕様や実装がこちらがわの「思惑」を邪魔することが多々ある。
※2: 実際は、理論的にはよう知らんが、「高階関数の動作を途中で止める」と言うのは関数型プログラミングのスタイルとしては望ましくないらしい・・・と言うより、そもそも、call/ccの「継続」と言う「機能」そのもの、が関数型プログラミングに反した存在らしい。
※3: この辺「上手くやってる」と言えるのが、商用処理系のMATLABだろう。ただし、いまだMATLABの「方策」は汎用プログラミング言語に取り入れられていない。Lispが次のステップに登るには、一次元のリストに加えて二次元以上、つまり「行列」に対する強力な抽象化能力を手に入れることなんじゃないか、となんとなく思っている。
※4: もっともシューティングゲームやアクションゲームの場合、「ユーザー入力は途切れない」と言う前提があるんで、REPLモデルが素直に適用出来ないケースにはなるだろう。
※5: 不自然な日本語だが、そう、英語表現(weighted)の直訳だ。
余談だが、統計解析の回帰分析なんかでも、変数の重要度を恣意的に振り分ける技法があり、「重み付き」回帰分析等と呼んだりする。
