はじめてのコンピュータ将棋入門(3)

前回、kouryo()関数は実はサボれる、という話をしました。

これは、同じ結果を得られるけれど、新しいやり方はより少ない時間で

回答を見つけられる、という意味でお話しました。

今回は、ほぼすべての将棋ゲームプログラムの基礎となっている、アルファベータ法

という探索アルゴリズムを紹介いたします。

まずはC言語で書かれたkouryo()関数と、AlphaBeta()関数を見てもらいましょう。

int kouryo(int *te, int fukasa)

{

    int te2;

    int teban = 1; // 先手がCOMPUTER, -1なら後手がCOMPUTER

    int val = AlphaBeta(&te2, -10000, 10000, fukasa, teban);

    *te = te2;

    return val;

}

int AlphaBeta(int *te, int alpha, int beta, int depth, int teban)

{

    int kazu;

    int hairetsu[1024];

    kazu = kanoushu(hairetsu, teban); // hairetsu[0] から hairetsu[kazu-1]に手が入る

    if (depth <= 0) { return hyouka(teban);}

    int i;

    int ret = 0;

    for ( i = 0 ; i < kazu ; i++) {

          int te, te2;

          te = hairetsu[i];

          sasu(te);

          int a = - AlphaBeta( &te2, -beta, -alpha, depth - 1, (-1)*teban);

          modosu(te);

          if ( a > alpha) { // alpha update

              alpha = a;

              ret  = te;

          }

          if ( ban >= beta ) { // beta cut

               *te = ret;

                return ban;

          }

     }

     *te = ret;

     return ban;

}

まずkouryo()関数に探索深さがわたると、その中でAlphaBeta関数を呼び出します。

このとき重要なのがalphaとbetaと呼ばれる二つのパラメータです。

AlphaBeta関数には面白い性質があります。探索の答えの値（評価値）が、

alpha以上beta以下だと、AlphaBeta関数はその答えの値を返します。

もしalphaからbetaの範囲内に答えが無かったら、alphaかbeta（大小による）

を返します。この、alphaからbetaの範囲のことをウィンドウと言いますが、

もしある程度の誤差でAlphaBeta関数の答えをあらかじめ知っていれば、

ウィンドウを狭めて検索することで早く答えを出す事ができます。

AlphaBeta()関数の内部を見て行きましょう。

この前のkouryo()関数と似ていますがいくつか異なる点があります。

まずfukasaをdepthという値に置き換えて、探索が深くなるとdepthが

小さくなるようにしています。hyouka()を返す条件をdepthが0以下と

しました。またhyouka()は手番をとるように変更しました。

また、手番を追加しました。1を先手、-1を後手とします。

同じAlphaBeta関数を中で呼んでいる（これを再帰といいます）

あと、二つの条件文のところにコメントで、

alpha update, beta cutと書いてあります。この二つがとても

重要です。

厳密にはこのアルゴリズムはアルファベータ法ではなく、

ネガマックス法という、より簡略化した手法ですが、同じ正解を

得られます。

ではalpha updateとbeta cutの説明をしましょう。

alpha updateとは、「答えかもしれない良い手に出会いました」

という意味で、alpha updateのときは手と評価値を保存します。

またalphaパラメータを更新して、より大きい値に変更します。

つまりウィンドウを狭める訳です。

beta cutは正確にはbeta cut-offと言います。

これが実はサボりのために必要な部分です。

評価値がbetaを超えた場合、その手はとても良い手なので、

その手で探索を打ち切ります。それより後ろの可能手を

AlphaBeta()関数で調べなくても、最終的な正解は変わらない

という性質を利用しています。

結果、極端な場合には始めの一手でbeta cutが起こると、

その手しか調べません。これが効率がよい秘密です。

このAlphaBeta関数には入っていませんが、可能手を、beta cut-off

しやすい順にならべれば、探索する探索木はより深くまで読める

ような理想型になります。このソート（並べ替え）のことを

ムーブオーダリングと呼び、強い将棋ソフトには必須の機能です。

またこの探索木の理想型のことをoptimal treeと呼んでいます。

Knuth先生という方の論文に、このoptimal treeになったときに

どのくらい局面を探索するか、という値が計算されています。

詳しくはその論文に譲りますが、まじめに全部調べるよりずっと

少ない数になります。

ではねちゃお！

はじめてのコンピュータ将棋入門(2)

今回は将棋の思考ルーチンについてお話したいと思います。

前のブログエントリーで、kouryo()関数になっていたところです。

なぜコンピュータは計算しかできないのにあんなに強い将棋を指せるのか、

という問いに対する簡単な答えを提供できたらな、と思います。

まず思考ルーチンには二つの関数が必要です。

一つは与えられた盤面に対して先手、あるいは後手が動かすことのできる全ての手（可能手といいます）を列挙する関数です。ここではkanoshu()関数という名前とします。

もう一つは与えられた盤面がどの程度先手にとっていいかを数値化してくれる関数（評価関数といいます）です。hyouka()関数という名前だとします。

本当は評価関数としてhabu()みたいな、羽生先生が見て点数を付けたような評価関数が

欲しいところですがw　いまのところ無理なので、「ある程度」確からしい評価関数を使う

ことにします。

実は、コンピュータのすごいところは、この評価関数がそれほど正確でなくても何手も

深く読んで強い一手を指せるところにあります。

思考ルーチンの関数kouryo()は、おおむね次のような処理をします。

ここで、kouryo()は、選んだ手（整数）と、その評価値（整数）を返すことに変更します。C言語で書くと書きづらいですが、こんな感じです。

    int te;

    int hyouka = kouryo(&te, 0);

    こうすると、teには選んだ手の整数が、hyoukaには評価値が入ります。

　では処理を見て行きましょう！

• 自分が先手なら盤面で先手の指せる手、後手なら後手の指せる手を、まずは全部列挙します。初手で30手くらいでしたでしょうか
• 全ての手の評価値を求めます。これはすべての手について、盤面を一手進めた盤面を作って、kouryo()を計算します。で、評価値はkouryo()の値をマイナス符号を付けた値（-1を掛けた値）になります
• 全ての手の評価値の中で、一番大きい値を持つ手を選んでteとして返します。この手の評価値も一緒に返してあげます

鋭い人は「kouryoがkouryoを呼んで、またkouryoを呼んで、、、終わらなくない？」という問いかけをすると思います。確かに今の仕様ではそうなってしまいます。

それを避けるために、呼び出す深さがN（決められた数値、例えば3とか）になったら、kouryo()の代わりに、hyouka()という、暫定の評価値を返す関数を呼ぶ事にします。

これが最初二つ用意した関数のうちの２番目の評価関数というものです。

C言語で書いてみましょう。

int kouryo(int *te, int fukasa)

{

    int kazu;

    int hairetsu[1024];

    kazu = kanoushu(hairetsu); // hairetsu[0] から hairetsu[kazu-1]に手が入る

    if (fukasa > 3) { return hyouka();}

    int i;

    int ban = -1000000; // とても小さい数

    int ret = 0;

    for ( i = 0 ; i < kazu ; i++) {

          int te, te2;

          te = hairetsu[i];

          sasu(te);

          int a = - kouryo( &te2, fukasa + 1);

          if ( a > ban) { // 暫定の最大値とその手を計算する

              ban = a;

              ret  = te;

          }

          modosu(te);

     }

     *te = ret;

     return ban;

}

hairetsuとは、箱が横にいっぱいならんでいて、hairetsu[10]とすると10個目の箱の値を取り出せる仕組みです。

for文は、ここでは0からkazu-1まで、iを増やしながら {}を繰り返す、の意味です。

*teという記述があります。これはポインタというのですが、外から場所をもらい、

その場所に数字を書くという意味になります。結果として、kouryoの第一引数の指定

された変数（＆が付いている）に、最善の手が入ります。

sasuは前に出てきました。一手進める手です。modosuはその反対の動作をする関数です。つまり一手もとに戻します。

実際にはkouryoはもっとたくさんの引数を必要とします。先手か、後手かなどです。

そして重要なことですが、この関数はかなり遅いです。実は処理をさぼっても同じ結果を得られる方法があります。これについては後日お話します。

まずは計算だけで将棋が指せることを実感してみてください！

ではねちゃお！

はじめてのコンピュータ将棋入門(1)

今回から数回に分けて、コンピュータ将棋プログラムを作りたい人向けに簡単な文章を提供したいと思います。メカウーサー将棋は弱いので、これを読んで強い将棋プログラムを作って下さる方が現れるとうれしいなと思っています。長文すみません。

　※分かりやすく書いたら長文で分かりにくくなりました。。。(T_T)

１回目はまず、将棋プログラムとはなんぞや、というところから始めたいと思います。プログラミングの知識のある人にとっては「いらね」という説明が続きますが、そのときはスキップしちゃってください。よろしくお願いします。

まずプログラムとはなんぞやというところから話を始めたいと思います（えーw）
プログラムとはなんぞや、という問いに答えられる人は「※普通はここから読んでください」から読み始めてください。

まず、プログラムは通常機械語と呼ばれる数字の集まりからなるデータの塊です。
で、これを人間がしこしこ書くのは辛いし効率が悪いので、あたまの切れる人が、
「人間に馴染みのある人工言語をつくって、そっから一気に機械語に直すプログラム
を作れば楽勝じゃん？」ということをひらめいて、実際そういうものをつくりました。
この、「人工言語→機械語」の変換プログラムはコンパイラと呼ばれ、あたまのいい
人が作るすごいプログラムの一種です。で、私たちはそれを作らないと変換できない
のではなく、もう出来上がったコンパイラを場合によってはタダで使えます。
素晴らしい世の中です。

多くのエンジニアによってたくさんの人工言語（プログラミング言語といいます）が
発明されてきました。今回はその中でも長い間よく使われて来たC言語という言語
を使って説明していきたいと思います。

　※普通はここから読んでください

で、ここでやっと将棋プログラムとはなんぞやという説明に入ります。
将棋には先手と後手があり、その内のどちらかをコンピュータが指すとします。
先手番の場合、第１手を「考えて」指し、後手の手を待って後手が指したら
その手を受け取って、第３手を指し、以下どちらかが投了するまで同じことを
続けます（将棋に詳しい人は話をはしおりすぎると思うかもしれませんが、
まずは千日手や入玉のことは忘れてくださいませ）。

そこで、この手順をC言語（っぽい）プログラミング言語で書いてみたいと思います（図１）。

C言語が分かる人は図１を直接見て察してください。分からない人のために説明を以下に書きました。//はコメントと言って、//のあとの文字は無かった事にするという意味を持ちます。

まず、intは32bitの符号付き整数で、、、つまりプラスとかマイナスになる数ですね。
簡単のため、数を色んな場所で使っていますが、それぞれに約束ごとがあります。

int game(int teban) {...} というのを関数といい、実行する内容をまとめて一つにしたもの
です。最初のintは数字が返ってくることを表し、(int teban)は数字を引数に与える
ことを指します。引数は関数専用の入力だと（ここでは）思ってください。

つまり関数gameは将棋対戦をして自分が負けたら0を、勝ったら1を返す関数です。

{}で囲まれた中が関数の中身です。ここに何をしたいかを書きます。

引数のtebanはintの変数といいます。つまり数字を入れる箱です。
自分が先手の時には0が、後手の時は1が入ります。

関数の一番最初にifというキーワードがあります。これはC言語で決まっている
キーワードと言って、特殊な単語です。この単語は変数の名前には使えません。

ifキーワードはelseキーワードと一緒に使い、「CだったらAを、さもなければBを」
という風に条件により異なる内容を実行します。
if (C) { A} else {B}
という形をしていて、Cを条件式と呼び、Aをthenパート、Bをelseパートと呼びます。

ここで、{}の本当の働きを説明します。{}は、一つ以上の文をまとめたものです。
一つの文は「文;」(;はセミコロンと云います)と書きます。これを続けて書くと
{ 文１;文２; } のようになります。つまり文の最後にはセミコロンが入ります。
プログラムは文を使って構成します。詳しくは後々の例を見て行きましょう。

先手番、後手番、両方ともやる事が似ています。
特に、先手番後手番ともに内容がwhileキーワードによって囲まれています。

while(C) { 文; ...} は、Cだったら {}内を実行し続けます。
ここではCに1（条件一致）を与えているので、常に実行を続け、この文は
永遠に返ってきません！　でもそれでは困るので、脱出する手段をこの{}
内に書きます。これについては後述します。

つまり先手も後手も一定の処理を条件が整うまで繰り返します。
その条件とは「投了」です。

処理の内容を先手番で見てみましょう。

まず、int te = kouryo(); という記述があります。これは関数呼び出し
と言います。つまり関数を実行します。
鋭いひとはkouryo()関数の中身がここでは書かれていないことに気がつく
でしょう。実はそれこそが私たちの欲しい思考ルーチンなのです。
思考ルーチンの説明は後日します。今日は将棋プログラムがどんなものなのか
まずは感覚で感じてください。

ここでも一つ約束をします。teは先手の手で、0が手がない、それ以外が
何らかの手です。つまり全ての可能な将棋の手に番号を付けておいて、その
番号をこのkouryo()関数が返します。

次のif は {} も elseもありませんが、立派な条件分岐です。
teが0だったら、return 0 を実行します。
条件式の中で同じということを判断するには=ではなく==を使うことに
注意してください。

return 0;というものが現れました。これは0をgame()関数の返すものとして、
game()関数を終了する、という意味になります。0は投了だったので、
この場合はもう先手に指せる手が無くて、投了した、ということになります。

ここで、teに入っているのは可能な手であり、関数gameの値として返すのは
勝敗であることに注意してください。本来は型というものを作って区別するの
ですが、まずは簡単のためすべて数で表現しています。

次のsasu(te)は、コンピュータが持っている盤面で、先手の手を進めます。
詳細は略ですが、盤面の表し方には色々あるので、その方法次第で何を
するかが決まります。

printf("%d¥n", te);  はプリント文と云って、何かをスクリーンに出力する
関数です。これはコンパイラと一緒にすでに用意されています。
暗号みたいな記号が書かれていますが、いまはteの数字をスクリーンに
出す、と覚えてください。

次にaite=gote();とあります。これは後手が手の数字を入力して、その内容を
aiteに入れる事を指します。詳細は略ですが、コンピュータ将棋選手権などでは、
通信して相手の手をもらいます。

これで相手の手がわかりました。もし相手が投了ならreturn 1をして自分が勝ちで終了です。

コンピュータ将棋プログラムは相手が指すときは何もしないと思うかもしれませんが、
一つだけ仕事があって、それは自分の盤面で相手の手を一手動かすことです。
sasu(aite)が相手の手を指して一つ進めます。

さて、これを先手、後手どちらかが投了するまでつづける、というのがコンピュータが
先手番の場合でした。


後手の説明は簡単にしてしまうと、相手の手を待って投了か判断した後に
相手の手を指し、次に自分の手を考えて投了か判断した後に自分の手を
一手進めます。コンピュータが後手番の場合はこれを投了まで繰り返します。


int game(int teban)
{
    if (teban == 0) { // 先手
        while (1) { // 無限繰り返し
            int te = kouryo();   // 先手の手を「考える」
            if (te == 0) return 0;  // 先手投了
            sasu(te);                // 自分の心の中の盤面で先手の手を指す
            printf("%d¥n", te); // 先手の手を相手に知らせる
            int aite = gote();     // 後手の手を受け取る
            if (aite == 0) return 1;  // 後手投了
            sasu(aite);             // 自分の心の中の盤面で後手の手を指す
        } // while
     } else {
        while (1) { // 無限繰り返し
            int aite = sente();   // 先手の手を受け取る
            if (aite == 0) return 1;  // 先手投了
            sasu(aite);                // 自分の心の中の盤面で先手の手を指す
            int te = kouryo();     // 後手の手を「考える」
            if (te == 0) return 0;  // 後手投了
            sasu(te);             // 自分の心の中の盤面で後手の手を指す
            printf("%d¥n", te); // 後手の手を相手に知らせる
        } // while
     }
}

ここで中身を書いていないすべての関数に中身を与える必要があります（printf除く）。
特にkouryo()が難しくて、これのことを思考ルーチンと呼びます。

最後に、game()を誰が呼んでいる、という疑問があると思います。mainが呼びます。

int teban = 0; // コンピュータ先手番

int main(int ac, char *av[])
{
    return game(teban);
}

だめだー、自分文才なさすぎ。すみません。。。