(2/3) へ

C# で解く「なぜ関数プログラミングは重要か」(3/3)

2015-01-30 (鈴)

4. 「5. 人工知能からの例」について

「なぜ関数プログラミングは重要か」§5「人工知能からの例」は,チェスなどのゲームでゲームプレイヤの状態がどのくらい良いものかを見積もるアルゴリズムを例にとっている。 その議論ではゲームを次の三つの構成要素に抽象化している。

  1. ゲームの状態を表す position 型
  2. position 型のオブジェクトが与えられたとき,可能な次の状態のリストを返す moves 関数
  3. ある状態でプレイヤがどれだけ勝っているか (負けているか) を先読みなしで静的に評価する static 関数

ゲームの例として三目並べが挙げられているが,上記三つの実装は与えられていない。 そこで実験のために下記のような Position 型を定義する。

  1. 三目並べの1局面を表す Position クラス
  2. Position クラスのメソッド IEnumerable<Position> moves()
  3. Position クラスのメソッド int staticEval()
static は C# ではキーワードですからメソッド名として staticEval を使うことにします。 @ 記号を使って static と命名することもできますが,そうまでしてわざわざコードを読みにくくすることもないでしょう。 「なぜ関数プログラミングは重要か」がしばしば難解だと言われる理由として,§4 の内容の理解にいくらかの数学の素養が必要なことに加えて §5 で上記3要素の具体的な実装が与えられておらず,話がいわば抽象論になっていることが挙げられるかもしれません。
    // 三目並べの 1 状態
    class Position {
        private int[] board = new int[9];
        /* 
           0 1 2
           3 4 5
           6 7 8 の各添え字位置が -1 なら x, 0 なら空き, +1 なら o
         */

        public Position() {}

        public Position(int[] otherBoard) {
            for (int i = 0; i < 9; i++)
                board[i] = otherBoard[i];
        }

3×3 の盤面を単純に 9 要素の一次元整数配列で表現する。 "x" は -1, "o" は 1 とする。 例えば

|x|x| |
|-+-+-+
| |o| |
|-+-+-+
| | | |

のような局面を {-1, -1, 0,   0, 1, 0,   0, 0, 0} のような配列で表現する。 文字列にするときは,上記の局面を1次元的に xx_|_o_|___ と横に並べて表す。

        public override string ToString() { // "xx_|_o_|__" など
            var sb = new System.Text.StringBuilder();
            for (int i = 0; i < 9; i++) {
                if (i == 3 || i == 6)
                    sb.Append('|');
                int e = board[i];
                char ch = (e == -1) ? 'x' : (e == 1) ? 'o' : '_';
                sb.Append(ch);
            }
            return sb.ToString();
        }

「なぜ関数プログラミングは重要か」の例示では moves 関数は対称性を考慮して冗長な候補を挙げることを避けていた。 しかし,ここでは簡単のため,配列の先頭から順に空いた場所を探し,そこに手番のコマを打った盤面を列の要素として返す。 もしも相手がすでに三目並べているならば,詰みだから,列の要素を何も返さない。 盤面上のコマの個数の総数の偶奇でどちらの手番かを判断する。 「なぜ関数プログラミングは重要か」の例示にしたがって先手を "x" とする。

staticEval() メソッドは,マイナスならば先手 "x" 優勢,プラスならば後手 "o" 優勢とする。 すなわち,評価値大が好ましい側のプレイヤをここでは後手 "o" とする。 評価方法は,三目を並べられる筋がどれだけあるか,そこにどれだけコマを置いたかで点数を積み上げる。

        // 可能な次の局面の列を返す。先手を x とする。
        public IEnumerable<Position> moves() {
            int count = board.Select(e => (e == 0) ? 0 : 1).Sum();
            int teban = (count % 2 == 0) ? -1 : 1; // 偶数なら x の手番
            if (evalFor(-teban) == 20) {
                // Console.WriteLine("  {0} --> #", this);
                yield break;    // 相手に詰まされているなら何も打たない。
            }
            for (int i = 0; i < 9; i++) {
                if (board[i] == 0) { // 空いた場所に打った局面を次々に返す。
                    Position next = new Position(board);
                    next.board[i] = teban;
                    // Console.WriteLine("  {0} --> {1}", this, next);
                    yield return next;
                }
            }
        }

        public int staticEval() { // 静的評価: マイナスならば x 優勢
            return evalFor(1) - evalFor(-1);
        }

        // 詰みになる配置
        private int[][] lines = {
            new int[]{0, 3, 6}, new int[]{1, 4, 7}, new int[]{2, 5, 8},
            new int[]{0, 1, 2}, new int[]{3, 4, 5}, new int[]{6, 7, 8},
            new int[]{0, 4, 8}, new int[]{2, 4, 6}
        };

        // 手番に対する評価値 (詰みで勝っているならば 20)
        private int evalFor(int teban) {
            int r = 0;
            foreach (var line in lines) {
                int score = 0;
                foreach (int i in line) {
                    int e = board[i];
                    if (e == teban)
                        score += 1;
                    else if (e == -teban) // 線上に相手のコマがあればダメ
                        goto EXIT;
                }
                if (score == 3)
                    return 20;  // 詰み
                r += score;     // あと1手または2手打てれば詰み
                EXIT:;
            }
            return r;
        }
    }

以下の議論は,この実装に限らず同じようなメソッドを定義した任意の対戦ゲームに適用できる。

4.1 ミニマックス法

ゲームツリーの表現として §2.1 のラベル付き順序ツリー Tree<T> をそのまま使う。 このとき,ラベルから新しいラベルのリストを作る関数 f をもとに,元になる1個のラベルから再帰的に1本のツリーを生成する reptree 関数は次のようにかける。

    static Tree<T> reptree<T>(Func<T, IEnumerable<T>> f, T a) {
        var seq = f(a);
        if (seq == null) {
            return new Tree<T>(a, null);
        } else {
            return new Tree<T>(a, seq.Select(e => reptree(f, e)));
        }
    }

ある局面 p から開始して,そこから可能なすべてのゲーム展開を網羅したゲームツリーを得る gametree 関数は reptree を使って次のように書ける。

    static Tree<Position> gametree(Position p) {
        return reptree(pos => pos.moves(), p);
    }
gametree 関数を呼び出した直後は moves() は元の引数 p に対して1回呼び出されているだけ,つまり実際にゲーム展開を得ているのは初手だけです。 次の相手の番の展開はサブツリー (IEnumerable<Tree<Position>> 型) の各要素を LINQ メソッドや foreach 文で参照するときまで行われません。

§2.1maptree 関数を使うとゲームツリー g から静的評価の木を maptree(p => p.staticEval(), g) として得ることができる。これは Tree<int> 型である。

各プレイヤが可能な手のうち最良のものを選ぶと仮定したとき,評価値大が好ましいプレイヤの番での局面の正確な評価値は,次のようにして得られる。 自分の指し手となるサブツリーの各要素 (=各候補手) において対戦者すなわち評価値小が好ましいプレイヤが minimise で得た値のうちの最大値 (=最良手の値) を .Max() で選ぶ。

    static int maximise(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree.Label;
        } else {
            var m = tree.Subtrees.Select(minimise);
            try {
                return m.Max();
            } catch (InvalidOperationException) { // m has no elements
                return tree.Label;
            }
        }
    }

評価値小が好ましいプレイヤの番での局面の正確な評価値 minimise は対称的に次のようにして得られる。 サブツリーにおいて対戦者が maximise で得た値のうちの最小値を .Min() で選ぶ。

    static int minimise(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree.Label;
        } else {
            var m = tree.Subtrees.Select(maximise);
            try {
                return m.Min();
            } catch (InvalidOperationException) { // m has no elements
                return tree.Label;
            }
        }
    }

ルートから n を超えるところにあるすべてのノードを切り捨てる prune 関数は次のように書ける。

    static Tree<T> prune<T>(int n, Tree<T> tree) {
        if (n == 0 || tree.Subtrees == null) {
            return new Tree<T>(tree.Label, null);
        } else {
            return new Tree<T>(tree.Label,
                               tree.Subtrees.Select(t => prune(n - 1, t)));
        }
    }

これらを組み合わせると,評価値大が好ましい側のプレイヤがこれから打とうとする局面に対して五手先読みしてどちらがどれだけ優勢かを判定する関数は次のように書ける。

    static int evaluate_v1(Position pos) {
        var g = prune(5, gametree(pos)); // 5 手まで先を読む
        var m = maptree(p => p.staticEval(), g);
        return maximise(m);
    }

ここで Position クラスの実装では後手 "o" を評価値大が好ましい側のプレイヤとしていた。 後手番となる次の局面を評価してみよう。

|x|o| |
|-+-+-+
| |x| |
|-+-+-+
| | | |
       var pos = new Position(new int[]{-1, 1, 0,  0, -1, 0, 0, 0, 0});
       Console.WriteLine("{0}: {1}", pos, evaluate_v1(pos));
xo_|_x_|___: -18

先手優勢,後手劣勢であることが分かる。

この局面では次の "o" の手は右下一択,その次に左下に "x" を打たれれば,次にどこに "o" を打っても "x" が三目並べることを防げませんから,この計算結果はたしかに妥当そうです。

4.2 α-β 発見法

関数 maximise' は次のように書ける。 この関数はサブツリーが空ならばラベルの値を結果の列の唯一の要素として返す必要がある。 しかし,サブツリーが非 null の場合は実際に foreach でループしてみるまで空かどうか分からない。 ここでは empty フラグを使って手続き的に関数を実現する。

    static IEnumerable<int> maximise_dash(Tree<int> tree) {
        if (tree.Subtrees == null) {
            yield return tree.Label;
        } else {
            bool empty = true;
            foreach (int i in mapmin(tree.Subtrees.Select(minimise_dash))) {
                empty = false;
                yield return i;
            }
            if (empty)          // Subtrees が空リストだったならば
                yield return tree.Label;
        }
    }

関数 mapmin は次のように書ける。 整数の列 nums の各要素を .Any.Min の二つの LINQ メソッドでそれぞれ参照するから,要素を求める計算を無駄に繰り返さないように §3.3Cached<T> を使う。

    static IEnumerable<int> mapmin(IEnumerable<IEnumerable<int>> numss) {
        bool isFirst = true;
        int pot = 0;
        foreach (var ii in numss) {
            var nums = ii;
            if (isFirst) {
                isFirst = false;
            } else {
                nums = new Cached<int>(nums); // Any と Min で使われるから
                if (nums.Any(i => (i <= pot)))
                    continue;
            }
            pot = nums.Min();
            yield return pot;
        }
    }

関数 minimise_dashmapmax も同じように書ける。

maximise_dash を使って改良した評価器は次のように定義できる。

    static int evaluate_v2(Position pos) {
        var g = prune(8, gametree(pos));
        var m = maptree(p => p.staticEval(), g);
        return maximise_dash(m).Max();
    }

評価木の各ノードごとにサブツリーをソートすることで,この α-β アルゴリズムを改良できる。 サブツリーの階層ごとに (つまり手番が交替するごとに) 評価木のラベルの値 (つまり静的評価値) を順逆入れ替えてソートする highfirst 関数と lowfirst 関数を次のように書く。

    static Tree<int> highfirst(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree;
        } else {
            var subtrees = tree.Subtrees.Select(lowfirst)
                .OrderByDescending(t => t.Label);
            return new Tree<int>(tree.Label, subtrees);
        }
    }
    static Tree<int> lowfirst(Tree<int> tree) {
        if (tree.Subtrees == null) {
            return tree;
        } else {
            var subtrees = tree.Subtrees.Select(highfirst)
                .OrderBy(t => t.Label);
            return new Tree<int>(tree.Label, subtrees);
        }
    }
ソートするときは各要素のラベルしか見ませんから,各要素のサブツリーが未評価のままでソートされます。 したがって,これらの関数を使ったからといって余分に評価が深くなることはありません。 各要素の値は .OrderByDescending メソッドや .OrderBy メソッドの内部でソートのためにキャッシュされますから,それぞれ一度しか計算されません。 したがって,これを使った下記の evaluate_v3 関数では mapminmapmaxCachched を利用しなくても実は問題ありません。

highfirst を使って改良した評価器は次のように定義できる。

    static int evaluate_v3(Position pos) {
        var g = prune(8, gametree(pos));
        var m = maptree(p => p.staticEval(), g);
        return maximise_dash(highfirst(m)).Max();
    }

ここで探索を制限するために,静的評価値でソートした上位3手だけを考慮すれば十分であると考えよう。 評価木の各サブツリーを n 手だけ採る taketree 関数は次のように書ける。

    static Tree<T> taketree<T>(int n, Tree<T> tree) {
        return tree.Reduce((x, yy) => new Tree<T>(x, yy),
                           yy => yy.Take(n),
                           (IEnumerable<Tree<T>>) null);
    }

taketree を使ってソート結果の上位3手だけ採るように改良した評価器は次のように書ける。

    static int evaluate_v4(Position pos) {
        var g = prune(8, gametree(pos));
        var m = maptree(p => p.staticEval(), g);
        return maximise_dash(taketree(3, highfirst(m))).Max();
    }

先手 "x" が初手を打ったそれぞれの局面について,後手 "o" がどれだけ優勢か評価してみよう。

       foreach (var p in new Position().moves()) {
           Console.WriteLine("{0}: {1}", p, evaluate_v4(p));
       }
x__|___|___: 0
_x_|___|___: 0
__x|___|___: 0
___|x__|___: 0
___|_x_|___: 0
___|__x|___: 0
___|___|x__: 0
___|___|_x_: 0
___|___|__x: 0

三目並べで先手がどこに初手を打っても,先手も後手もまだどちらも優勢でない引き分けの状況であることが分かる。

5. おわりに

ここでは LINQ と組み合わせた C# が遅延評価的な関数型言語と同じように,それ以前では考えられなかった方法で問題を分解しプログラムを構成することを可能にしていることを 「なぜ関数プログラミングは重要か」のプログラム例の再現によって実証した。 一部の関数は手続き的な処理で実現せざるを得ないが,プログラムの枠組みに影響を与えることなく,その関数内に「泥臭さ」が閉じていることに注目したい。

B. Stroustrup: "The C++ Programming Language", 3rd Ed., Addison-Wesley, 1997, ISBN 0-201-88954-4 の§2.5 と §2.6 によれば「オブジェクト指向」パラダイムとは 抽象データ型 (abstract data type) のパラダイムに継承 (inheritance) を導入したものである。

すなわち抽象データ型のパラダイムとは:

Decide which types you want;
provide a full set of operations for each type.

一方,オブジェクト指向のパラダイムとは:

Decide which classes you want;
provide a full set of operations for each class;
make a commonality explicit by using inheritance.

C++ の設計者によるこの定義付けは,プログラムで扱うデータが可変であるかどうかとは関係しない。 いずれにせよ継承とは基底型から派生型をつくる型拡張 (type extension) であり,実行時の型は静的な型の派生型であり得る。 型に対する演算ないし操作 (operation) の実行時の実装は,実行時の型である派生型に対して定義された実装になり得る。

言語の意味論等の議論を追えばもっとさかのぼれるかもしれませんが,知る限りでは継承を型拡張と表現したのは Reiser & Wirth: "Programming in Oberon", ACM Press, 1992, ISBN 0-201-56543-9 など Oberon の文脈が最初でした。 Fortran 2003 以降の Fortran も同様に「型拡張」の語で継承を表現しているようです。 ここでは「継承」にまとわりついた連想を振り払い, それが要するに互換性があり拡張された型を定義することだということを強調するために Oberon の用語法から「型拡張」を借りました。

つまり,オブジェクト指向のパラダイムと,その演算ないし操作の記述が手続き型言語によるものか,関数型言語によるものかは独立である。 オブジェクト指向言語であることと,関数型言語であることは矛盾なく両立できる,ある意味,直交した概念であると言ってもよい。

このように考えれば LINQ を伴った C# が Position クラスなどに見るようにオブジェクト指向的な道具立てを活用しながら関数プログラミング向けの機能を生かして,およそ 30 年前に主張された関数型言語の特権的な利点を享受していることは驚くべきことではないかもしれない。

もちろん今の C# がプログラミング言語の到達点だと言っているわけではありません。 例えば C# が使われる文脈に限って考えても,C# より F# が記法の簡潔さなどの点でより良い選択だと主張できるかもしれません。 F# は「なぜ関数プログラミングは重要か」の§2で,遅延評価をしないがために手続き型言語とともに否定された関数型言語 ML (Standard ML) の一族の末裔です。 .NET Framework 上の言語として本稿で示した解法を同じように,かつ関数型言語としてよりエレガントに記述できるだろうと予想します。
歴史的には ML の遅延評価的な遠縁として 1985 年ごろイギリスに Miranda が生まれ,それをもとに「委員会によって(再)設計された」言語として 1990 年ごろ Haskell が生まれました。 F# は ML のごく近い分家として同じく 1985 年ごろ対岸のフランスに生まれた Caml [inria.fr] のオブジェクト指向的な子である OCaml [ocaml.org] の .NET 版です。 ある意味,同じ島の一族の遠縁に討たれ,宗家としての名も奪われた旧家の復讐を,海を渡って帰ってきた同族の子孫が LINQ を供に 30 年ぶりに果たすことができるわけです。 F# はケンブリッジの Microsoft Research 生まれですから,まるで舞台は英仏を行ったり来たりの中世劇ないし近世劇です。 正確にいえば「なぜ関数プログラミングは重要か」で名指しで批判された Standard ML はエジンバラの ML の 1990 年生まれの直系の子であり,実質,ニュージャージーへの新大陸移民というべきかもしれません。 結局,F# は大叔父 (大叔母?) のかたきを取るかたちになります。
Standard ML が名指しされたのは,今になって遅延評価をしない関数型言語を新しく作っても……という思いが,ちょうど同じころ Haskell を共同して設計していた一人としての「なぜ関数プログラミングは重要か」の著者にあったのかもしれません。

一方、もしも個々の処理を手続き的に簡単に書けてそれが効率的ならば,そう書くことができる。 例えば,フィボナッチ数列は,もし実際にそうした数列が欲しいならば 8. フィボナッチ数の計算 1: 半手続き的なアプローチ に例示したように破壊的な代入を使って書けばよい。 これまでの例でそうしてきたように,仮に局所的に手続き的に書いたところで LINQ が実現する関数プログラミング的な枠組みには影響しない。 正確には,影響しないように組むことができる,というべきだが,それに求められる注意深さは普段手続き型のコードを書くときに求められる水準と特に変わらない。 メソッドや関数の枠外への大域的な副作用に節度を持たなければプログラムが破綻することはいつでも同じである。

本稿が,個々の処理を従来型の手続きとして記述しながら,全体の処理をあたかも純粋な関数型言語であるかのように構成する混成的なアプローチの典型例となれば幸いである。 手続き的なプログラミングに親しんだ多くのソフトウェア技術者が関数プログラミングの利点を享受することを,このアプローチが可能にすることを期待したい。


Copyright (c) 2015 OKI Software Co., Ltd.