start
move option 1
counter-move 1
counter-move 2
move option 2
counter-move 3
counter-move 4
第一回 : 無限に怠惰に後回し
ボードゲームはお互いの手番の繰り返しで成り立っており、それぞれの手番によって盤面の状態が更新されます。可能な着手は多数存在し、かつそのそれぞれに対して対戦相手による多数の返し手が存在するため、考えうるゲームの展開は盤面の状態による木構造をなします。
着手と返し手による木構造
ゲームのルールにもよりますが、このようなゲーム木は無限に大きくなりえます。
これを Frege や Haskell のような遅延評価を行う関数型言語でモデリングする自然な方法は、木のサイズについてはまったく気にせず、どうやって木を構築するかにのみ注意を払うことです。ここでは木を生成することに注目し、生成される木を制限する作業は後回しにします。
以下に挙げたのは、任意の型「a」の値を要素とする木を構築する関数です。要素である「a」型の値をすべて unfold することで、再帰的に各ノードの子要素となるノードを生成します。
再帰による一般的な木の構成
buildTree :: (a -> [a]) -> a -> Tree a
buildTree unfold a = Node a children where
children = map (buildTree unfold) (unfold a)ここでは、再帰が停止するための底となる場合分けや、木の大きさに対する制限については何も考えていません。しかし buildTree を呼んでもメモリや計算時間を使い果たしたりしないことに注意してください。言語が持つ遅延評価の機能によって、必要な時だけ子要素を生成するように考えられているのです。
与えられたデータ型 Board と、合法手を適用してすべての盤面を生成する関数 move を用いて具体化すると以下のようになります。
盤面からすべての合法手を適用しゲーム木を生成する
gameTree :: Board -> Tree Board
gameTree board = buildTree moves boardこの具体化は部分型を必要とせず、また依然として完全に型安全です。ここまで非侵入的にシステムを拡張してきましたが、さらにここからやはり非侵入的な方法でゲーム木のサイズを制限していきます。
深さ「n」までに制限して木の評価を行う際は、単純にその深さで木を枝刈りします。このコードは今回のゲームにおける使用例とは独立であり、それゆえ任意の木のノードに対して同じように動作します。再帰的な定義は以下のようになります。
任意の木に対する枝刈り
prune 0 (Node a children) = Node a []
prune n (Node a children) = Node a (map (prune (n-1)) children)枝刈りされたゲーム木を作り出すためには、関数合成 (.) を使用します。
深さ 5 でのゲーム木の枝刈り
prunedTree = prune 5 . gameTree実際にはまだ木を具現化しているわけではないことに注意してください！ 枝刈りされた木を使う側は、レベル 5 より深い部分を見ることは決してありません。これより深い位置にある子要素は評価されず、それゆえに、これが遅延評価のいいところですが、決して実際に生成されることはありません。
遅延評価によってインクリメンタルな開発が可能となる範囲は、一般化された木を生成するところから特殊化されたロジックとデータ型を扱うまでの範囲に留まりません。枝借りの条件ですら「外部から」非侵入的に与えることができるのです。枝刈りの必要性をあらかじめ予期する必要はありません。
変更の際にも、既存のコードに戻る必要はまったくありませんでした。再コンパイルすらなし！
以上、第一回でした。第二回に続く。
参考文献
| John Hughes | |
| Tic Tac Toe |