跳慮跋考

興味も思考も行先不明

電王戦のコンピュータ将棋のスペック及び「人間の敗北」だと?

第2回将棋 電王戦というのがありまして、プロ棋士とコンピュータ将棋がガチバトルした訳です。それでコンピュータ側は3勝1敗1分の大殊勲だったと。
人間側完敗などと悲観的? に受け取る向きもある様ですが*1、私としては「よくもまぁコンピュータのゴリ押しでここまで戦えたなぁ」という感じです。もっと丸い表現で言えば「人間はここまでコンピュータに対抗できるのか」とでも言いましょうか。

コンピュータ将棋どころか将棋にも詳しくないのでアレですが、Wikipedia大先生によるとコンピュータ将棋の基本アルゴリズムは「評価関数の学習」と「局面の探索」に集約されるみたいです。
評価関数はその名の如く局面の有利さを評価する手段ですが、じゃあ「学習」って何だというと、要するに人間の思考をブラックボックス化してプログラムがその振舞いを模倣する様にパラメータを調節するんですね。それはもう厖大な棋譜を自動で処理して。
「探索」ってのは手当たり次第で次にあり得る局面を並び立てて、評価関数の値が高い、有利っぽい手を探す事です。
となると結局「中身は分からないが人間っぽい振る舞いをするプログラム」を作ってる訳で、そりゃ将棋には勝てるかも知れないけど、自然科学としては全き「敗北宣言」ではないかと私は思うのです。「どうしてその手を打つのか」は結局分からないのですから。

何とか人間に対抗し得るプログラムが現れ始めた事は勿論大きな一歩でしょうが、そういう訳で私は「コンピュータが人間に勝利した」というのに違和感を覚えてしまいます。
もっと人間の思考を追究し、明解なアルゴリズムによって本当に「考える」コンピュータが現れれば、電王戦に使われた様な化物級のマシンでなくとも人間が敗北を喫す日が来るであろう――というのが私の淡い期待です。
それには現在の論理ガチガチなコンピュータ・アーキテクチャでは望み薄という感じもしますが。今や細密化し過ぎたCPUはトンネル効果により回路間で漏電が起こって困ってるそうですが、寧ろそんなノイズバリバリの回路を有効活用したりとかどうかな(適当)。

兎に角その「化物級」スペックなんだよ、という主張をする為にデータを集めてたというかデータの前振りのつもりで何となく書いてたんですが完全にそっちが主題です本当にありがとうございました。以下スペック情報の引用。3GHzのCPUとか天から降ってこないかな。

*1:こうゆう所でさりげなく大嘘を吐く人とかもいるので、普通に「へーそうなんだ」と思った人は注意した方がいいですよ。

続きを読む

二重階乗の一般化

その昔、Eulerは階乗 n!の一般化として積分 \int_{0}^{1} \left( \log \frac{1}{y} \right)^n dy = n! を見出し、後にGaußが \Pi(n) = \int_{0}^{\infty} e^{-x} x^n dx = n! と書き直した訳ですが、では二重階乗 n!!なんかはどうなるのという話。
因みに現代では \Gamma(n) = \Pi(n-1) = (n-1)! というややこしい定義のガンマ函数が罷り通っていますが、ここでは使いません。その方が綺麗なので。

さて取り敢えず n=2mの場合を考えてみる。
 (2m)!! = 2m \cdot (2m-2) \cdot (2m-4) \cdots 4 \cdot 2
 = 2^m (m \cdot (m-1) \cdot (m-2) \cdots 2 \cdot 1)
 = 2^m m!
なので、nが偶数の場合 n!! = 2^{\frac{n}{2}} \Pi\left(\frac{n}{2}\right) (甲)が成り立つ。
この右辺は奇数の場合にも使えないだろうか? という訳で n=2m+1としてみる。
 \Pi\left(\frac{2m+1}{2}\right) = \frac{2m+1}{2} \cdot \frac{2m-1}{2} \ \cdots \frac{5}{2} \cdot \frac{3}{2} \Pi\left(\frac{1}{2}\right) = \frac{ (2m+1)!! }{ 2^m } \Pi\left(\frac{1}{2}\right)
ここで \Pi\left(\frac{1}{2}\right) = \Gamma\left(\frac{3}{2}\right) = \frac{1}{2} \Gamma\left(\frac{1}{2}\right) = \frac{ \sqrt{\pi} }{2} となるのはガンマ函数界では有名な話なので、nが奇数の場合 n!! = \frac{1}{\sqrt{\pi}} 2^{\frac{n+1}{2}} \Pi\left(\frac{n}{2}\right) (乙)が成り立つ。

さて甲乙2式を比べると、奇数の場合のみ因子 \sqrt{ \frac{2}{\pi} } が掛かっているので、 f(2m) = 0, f(2m+1) = 1 \qquad (m \in {\mathbb Z}) を満たす解析函数fが欲しい。
実軸上で実数値函数とすれば、三角函数が正にそれである。 f(x) = \frac{ 1 - \cos(\pi x) }{2} = \sin^2 \frac{\pi x}{2} とすれば \left( \frac{2}{\pi} \right)^{ \frac{f(n)}{2} } でこの因子が記述できる。

以上より

となり、右辺は負の偶数を除く実数全体で定義される。

Maximaでチェック&プロット。

(%i1) f(n):=(2^n*(2/%pi)^(sin(%pi*n/2))^2)^(1/2)*gamma(n/2+1);
(%i2) makelist(f(n), n, 10);
(%o2) [1,2,3,8,15,48,105,384,945,3840]
(%i3) makelist(n!!, n, 10);
(%o3) [1,2,3,8,15,48,105,384,945,3840]
(%i4) plot2d( f(x), [x, -7, 7], [y, -100, 100] );
(%i5) plot2d( log(f(x)), [x, 0, 20] );

普通に描いたのがこれ。
f:id:quinoh:20130411002510p:plain
sinの影響でうねうねしてますね。あと発散点を巧く処理できてなくて途中で切れてます。
対数はこれ。
f:id:quinoh:20130411003959p:plain

そしたら三重階乗とかも考えたいところですが、同じ様に \Pi\left(\frac{n}{3}\right) を使うと
 (3m-2)!!! = 3^m \Pi\left( \frac{3m-2}{3} \right) / \Pi\left(-\frac{2}{3}\right)
 (3m-1)!!! = 3^m \Pi\left( \frac{3m-1}{3} \right) / \Pi\left(-\frac{1}{3}\right)
 (3m-0)!!! = 3^m \Pi\left( \frac{3m-0}{3} \right) / \Pi(0)
となるので、これを自然に書くのは無理があると思いますねぇ。

F#の無限シーケンスで素数列

Haskellでよくある

primes = [2, 3]
       ++ filter (\n -> all (\p -> mod n p /= 0)
                 $ takeWhile (\p -> p*p <= n) primes) [5, 7 ..]

的なやつを。

let infty n m = Seq.initInfinite (fun i -> n + i * m)

let rec primes = seq {
    yield! [2; 3]
    for i in infty 5 2 do
        if Seq.forall (fun x -> i % x <> 0)
                  (Seq.takeWhile (fun x -> x*x <= i) primes)
        then yield i
    }

なんか若干「そういう言語じゃねーから」みたいな感じがしますね。
F#は正格評価の言語なので、C#でいうとIEnumerable<T>とか書く時のごてっとした感じ?

make10

「8 8 9 9」のmake10を四則演算でやれと言う話なので。分かんないので。
アルゴリズムとしては「切符の番号で10を作る」のと同じです。カッコよく言うと分割統治法。コードはあんま美しくないけど。

import Data.List


data Expr = C Int | Add Expr Expr | Sub Expr Expr | Mul Expr Expr | Div Expr Expr

instance Show Expr where
    show (C x)     = show x
    show (Add x y) = "(" ++ (show x) ++ "+" ++ (show y) ++ ")"
    show (Sub x y) = "(" ++ (show x) ++ "-" ++ (show y) ++ ")"
    show (Mul x y) = "(" ++ (show x) ++ "*" ++ (show y) ++ ")"
    show (Div x y) = "(" ++ (show x) ++ "/" ++ (show y) ++ ")"

instance Eq Expr where
    (C x)     == (C y)     = x == y
    (Add x y) == (Add u v) = (x == u && y == v) || (x == v && y == u)
    (Sub x y) == (Sub u v) = (x == u && y == v)
    (Mul x y) == (Mul u v) = (x == u && y == v) || (x == v && y == u)
    (Div x y) == (Div u v) = (x == u && y == v)
    _         == _         = False


search n a = nub $ concat $ map (\(e,b) -> _search n b (C e)) (picks a)

_search :: Int -> [Int] -> Expr -> [Expr]
_search n a p = if null a
                    then (if eval p == Just (fromIntegral n) then [p] else [])
                    else concat $ map (\(e,b) -> concat $ map (\q -> _search n b q) (opr (C e) p)) (picks a)
 where
     opr x y = [Add x y, Sub x y, Sub y x, Mul x y, Div x y, Div y x]

picks a = [pickAt i a | i <- [0..(length a)-1]]
pickAt n l = (\(a,b) -> (head b, a ++ tail b)) (splitAt n l)

eval :: Expr -> Maybe Rational
eval (C x) = Just (fromIntegral x)
eval (Add x y) = eval x >>= (\m -> eval y >>= Just.(+ m))
eval (Sub x y) = eval x >>= (\m -> eval y >>= Just.(\n -> subtract n m))
eval (Mul x y) = eval x >>= (\m -> eval y >>= Just.(* m))
eval (Div x y) = eval x >>= (\m -> eval y >>= (\n -> if n == 0 then Nothing else Just (m / n)))

出力結果は

*Main> search 10 [2,3,7,7]
[(7+((7+2)/3)),((3+(7*2))-7),(3-(7-(7*2))),(3+((7*2)-7)),(3+((7+7)/2))]
*Main> search 10 [8,8,9,9]
[]

みたいな。要するに最初のは解無しっぽいという話でした。

連分数


みたいなのを連分数と呼ぶ。これだとスペースを取るので

とか(低い位置の+は直前の分数の分母にそれ以降を足す感じ)、分子が皆1の時は+の左の数字を並べてとも書く。
値を求めるには、これをと置くと

よりとなるから

は普通に考えて正なので、の正を取るとこの値は黄金比である。従って

が成り立つ。

実数の連分数展開

ある実数を整数部と小数部に分けられれば、それを連分数に展開できる。
例えば円周率

という感じでになる(WolframAlphaで計算)。
ここでと近似すると、

という有名な近似分数が現れる。

円周率は二進法なら11.0010010...だし十六進法なら3.243f6a88...だが、連分数展開により現れる数列は円周率の値のみで定まる。
それ故、連分数展開はより数の自然な表現を与えるとも言えよう。

一次分数変換

ところで、定数について

なる函数を一次分数変換とかメビウス(Möbius)変換とか呼ぶ。ではに「潰れる」ので除いておく。
一次分数変換及びを合成してみると

となる訳だが、これは

という行列積の要素と見事に符合している! ので、

という表記を用いると一次分数変換の合成等を行列の計算で扱える。

連分数と行列

さて

を眺めると、これが一次分数変換

により

と表せる事に気付く。
すると、例えばの場合、と置いて
('13/03/06 係数の誤りを訂正)
と対角化する事で

より

を得る。より

なので、再び

を得る。

級数の連分数展開

級数を無理やり連分数に展開して

と出来るから、

又は「約分」して

となる。
ここで

より分母位置の0を消去できる。即ち





例えばとすると、

という指数函数の連分数展開が得られる。

こうした展開例については数学研究ノートの連分数の項に詳しい。('17/08/04 移転していたのでリンク修正)

和の比と比の和の不等式


数学的帰納法により示す。

の時
 \frac{x_1}{a_1} + \frac{x_2}{a_2} - \frac{ x_1 + x_2 }{ a_1 + a_2 }
 \frac{a_2 x_1 + a_1 x_2}{a_1 a_2} - \frac{ x_1 + x_2 }{ a_1 + a_2 }
 = \frac{ (a_1 + a_2)(a_2 x_1 + a_1 x_2) - a_1 a_2 (x_1 + x_2) }{ a_1 a_2 (a_1 + a_2) }
 = \frac{ a_2^2 x_1 + a_1^2 x_2 }{ a_1 a_2 (a_1 + a_2) }
 > 0
よって成り立つ。

 n = k の時に成り立つとすると

ここで (x_k, a_k) \to (x_k + x_{k+1}, a_k + a_{k+1}) と置き換えると

 n = 2 の場合より

であるから

となり n = k + 1 でも成り立つ。

以上より任意の n \ge 2 について示された。 \qed


はてな記法 \TeXを試してみようと、何かの証明に使おうとした補題を載せてみる。
はてなで使われてるmimeTeXは美しくないので、「LaTeXのオンライン数式画像生成ツールの比較」を参考に要所々々でCodecogsのを使ってみると好い感じかな? ってゆう。

形態素解析器

C#から直截形態素解析器のライブラリを使いたいよぉ…ふぇぇ…って人に。
茶筌はツン過ぎて辛かっただって何ですかstring[]渡すだけなのに。

using System.Runtime.InteropServices;

class MeCab : IDisposable
{
    IntPtr ptr;

    [DllImport("libmecab.dll", CallingConvention = CallingConvention.Cdecl)]
    private extern static IntPtr mecab_new2(string arg);
    [DllImport("libmecab.dll", CallingConvention = CallingConvention.Cdecl)]
    private extern static IntPtr mecab_sparse_tostr(IntPtr m, string str);
    [DllImport("libmecab.dll", CallingConvention = CallingConvention.Cdecl)]
    private extern static void mecab_destroy(IntPtr m);

    public MeCab()
    {
        ptr = mecab_new2(@"-F%m\s%f[6]\s%f[0]\n");
    }
    public string sparse_tostr(string str_in)
    {
        return Marshal.PtrToStringAnsi(mecab_sparse_tostr(ptr, str_in));
    }
    public void Dispose()
    {
        mecab_destroy(ptr);
    }
}

class Chasen
{
    [DllImport("libchasen.dll", CallingConvention = CallingConvention.Cdecl)]
    extern static int chasen_getopt_argv([MarshalAs(UnmanagedType.LPArray, ArraySubType = UnmanagedType.LPStr, SizeParamIndex = 1)]string[] argv, IntPtr file);
    [DllImport("libchasen.dll", CallingConvention = CallingConvention.Cdecl)]
    extern static IntPtr chasen_sparse_tostr(string str_in);

    public Chasen()
    {
        string[] argv = { "", "-s", "-F", @"%m %M %H\n", null };

        if (chasen_getopt_argv(argv, IntPtr.Zero) == 1)
            throw new ArgumentException();
    }
    public string sparse_tostr(string str_in)
    {
        return Marshal.PtrToStringAnsi(chasen_sparse_tostr(str_in));
    }
}