2006年06月26日

一試/乱数手生成 (7)

細かな代替仕様を書き出すとキリがなくなるので、最後に今回用いるアービトレイタについて検討する。当初将棋の方で用いようと思っていた三分木アービタを使ってアービトレイタを構成することも試みる。余談だが、チェスでは26=64枡なので二分木アービタ6レベルで構成するのが常識と言えるが、書くまでもなく将棋に二分木アービタを用いると端数が出る。そもそも34=81枡なので、三分木4レベルにした方がピッタリである上にクリティカルパスを減らせて高速化が可能だ(但し多少資源を喰うが)。

さて、ここでは5x5盤25交点のアービトレイションなので二分木・三分木どちらを用いても端数が出て、二分木だと5レベル、三分木だと3レベルになる。どちらがどの程度資源を喰うか、また処理効率がどのくらい変化するかについて予備調査を行ってみることにする。

続きを読む
posted by Masa at 00:23| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月25日

一試/乱数手生成 (6)

低速版の乱数手生成器の設計に入る。高速版と異なり25交点中の候補手どれか一つをランダム且つ確実に生成する為に、少し特殊なメカニズムを使う。先ずはその基礎について述べる。大きくは次の2つ。

・優先度を基準にした全候補手のアービトレイション
・全交点で同時に擬似乱数生成を行う為のテーブル

前者の方は、チェスのハード探索(Move generator)でも用いられている手法で以前本家でも解説したが、これは最も優先度の高い手を生成する為のカラクリで囲碁の手生成にも適用出来る。チェスの場合は「最も価値の高い駒」を見つけ出し、その後に「最も価値の安い駒」で取る、といったような2つの手順を踏んで手を生成する。が、今回のモンテカルロ碁への応用では、単に「候補として妥当な交点で生成した乱数の中で最も値の大きい手を選ぶ」といった考え方で乱数手生成を行う。

それを実現するには、各交点の優先度を決める値を生成する必要があり、しかも優先度を示す擬似乱数が「同じ値にならない」ようにしなければならない。この解決策としては、最初から「全交点で見て重複しない擬似乱数テーブル」を用意しおく、というインチキ臭いというより全くインチキそのもの、というやり方を使う。勿論、最終的に得られる乱数手の一様性・周期性そして非線形性については、前項の高速版と同等の品質になる工夫は施す。

続きを読む
posted by Masa at 13:03| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月24日

一試/乱数手生成 (5)

現時点で考えている乱数手生成器の方式は2つあり、それらを同時に動かしてスルプットを上げることを考えている。これら2つの特徴を箇条書きにすると次の様になる。

・高速版1サイクル動作乱数手生成:
(5路盤なら)25交点に対して一様な乱数手を生成する。が、その際に候補手として妥当か否かは別にして「生成失敗」が起きる確率が幾らかある。

・低速版3サイクル動作乱数手生成:
25交点全てに対し候補手として妥当な乱数手を必ず生成するが、アービトレイションを行っている為、少し時間を要するという問題がある。

ここでは、生成した手が間違いなく合法な手であるか否かまでを判断した上での乱数手生成ではなく、合法性判定が必要な手であれば更にそのステートへ移る。なお「乱数手」は単に機械的に生成した手を意味し、「候補手」と「合法手」の定義も少し異なるので、この違いについて簡単に書いておく。

・候補手:空点に打ち且つコウでなく且つ目を潰さない手ではあるが、自殺手あるいは敵石を取れるか否かを判断しないと合法かどうか判らない手
・合法手:囲碁のルール上、打つことが可能な手

高速版は低速版の補助的な乱数手生成器という位置にある。低速版が生成中の時のみ高速版が働くという意味だ。特に盤上に石が少ない場合(中盤以前)で高速化に貢献すると思われる。本項では先ずこの高速版の乱数手生成器について設計する。

続きを読む
posted by Masa at 17:30| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月21日

で、最近思ったのだが

囲碁という歴史ある競技に、FPGAというやや先端を行く技術(てか枯れつつあると言っても過言ではない程、謎電の作者にしてみれば一般的だが)を使いながらも、モンテカルロ法とかLFSRとか分散並列データフロとか、

インチキ臭さ満載の技法ばかり

を寄せ集めて、将来、彩を含めて世界第一戦級のプログラムに立ち向かおうってのがブッ飛んでるよな、このブログは。と自分で思う。で、結構安定した読者を掴んでいるよ、このブログ…ぜんぜん宣伝してないのになあ。なんでなんじゃ(笑) 兎に角、囲碁とFPGAの組み合わせは、ググっても他に実例が未だに見当たらない。その事の方がもっと不思議だが、何か、ちょー最先端(というかちょーインチキ)なことをやってるのかも知れないと思うと、将棋にFPGA使うよりこっちの方がアツくなるよな。

でもって、全く脈絡がないんですけど。
日本語:http://www.kanko-otakara.jp/vjc_cm/jp.html
英語:http://www.kanko-otakara.jp/vjc_cm/en.html
日本の観光政策に首相自らが乗り出すとは素晴らしい。昔は「日本の首相はトランジスタの行商人」とイヤミを言われたものだが。外国からの観光客が少ないのは、地震が多い(日本人は慣れてるからそれが判らない)、国内の航空運賃が高すぎて広く観光旅行が出来ない、英語喋れる日本人が少ない、ってあたりが理由じゃないのかな。そういった意味でライエルは尊敬に値するよ。
posted by Masa at 21:00| Comment(0) | ブログ | 更新情報をチェックする

2006年06月19日

一試/乱数手生成 (4)

やっと序説が終わったという感じだが(笑)先ずはLFSRの持つ本質的な欠陥のみを改善することを試みることにする。非線形性についてはLFSRの特性をほぼ保持したままだが、次の2つを根本的に改善することにした。

・二進数1桁で統計的性質を見た時、0と1が均等(一様)に生じるようにする(従って、2n−1ではなく2n、即ち偶数周期になる)。
・レジスタ全体を値として見た時、0を含めて全ての値が均等に生じるようにする。

結論から書けば、これらの問題は単に「all '0' 出力」が1回の周期中に1度だけ適切な位置に挿入して現れるようにすれば表面的には解決する。その実現は高々状態数2のFSMを付加して制御するだけで可能だ。具体的には、例えば all '1' を出力しようとする直前に一旦LFSRに対し生成トリガを出すのを止めて強制的に all '0' を出力し、その次のトリガで状態を復帰してやる、という細工を施すわけである。

続きを読む
posted by Masa at 02:12| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月18日

一試/乱数手生成 (3)

乱数に関しては一家言どころか二家言、三家言、四家言と語りたいところだがキリが無くなって次に進まなくなるのでそろそろ本題に入ろう、と思いつつもまだまだ語り足りないのでやっぱりもう少し書くことにする。全く余談だが、谷川には十七世のみならず、十八世、十九世、二十世永世名人位も目指して欲しいと謎電の作者は願っているところである。

冗談はさておき。計算機を用いた乱数の生成は、書くまでもなくその計算機資源に依存した限界がある。従って作れるのは「あくまで擬似乱数」であって、純粋な乱数(真性乱数)と呼べるものではない。乱数生成アルゴリズムに概ね共通するのは、生成する為の初期値即ち「種値」に乱数の品質が大きく左右されることだ。線形合同法やMTがそうだしLFSRであっても例外ではなく同様、特に周期性を改善しようとすればする程局所的な生成で統計的性質が悪化する(値が偏る)問題が生じる。そのような理由で種値には極めて多大な注意を払う必要があるのだが、逆に言えば極端に長い周期を必要としないなら品質の高い(統計的性質が安定し、非線形性をある程度確保した)モンテカルロ法向きの擬似乱数を生成し易い。ところで暗号用、あるいは置換表のハッシュキー用といった用途で使う乱数では、また別の条件が要求されるのだが、ここではそれらについてまで熟慮した乱数生成の議論はしないことを予めお断りしておく。

続きを読む
posted by Masa at 09:44| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月12日

一試/乱数手生成 (2)

謎的乱数手生成法について書く前に、ちょっとウンチクを語ることにする。例えば仮に「符号なし32ビットの無限周期の完全な乱数」を得ることが出来る関数があり(0〜232−1まで均等に生成できるものとし)、それはperfectRandomUnsigned32()という関数名だとしよう。この関数を使って「発生確率が均等な0〜4までの乱数」を得てunsigned 32ビット変数numberに入れたい時、多くのCプログラマは次のように書くだろう。

number = perfectRandomUnsigned32() % 5;

一見これで正しいように見えて、これは全く数学的じゃない、というより算数的レベルで間違ってる。ちょっと賢い小学生にツッコミを入れられてしまう程お粗末だ。perfectRandomUnsigned32()がどんなに完璧に均等な乱数を吐き出しても、この計算式によって得られるnumberが「0〜4まで発生確率が均等」になることを理論的に保証出来る理屈がないというより、寧ろ「均等にならないこと」を証明出来る。いや自明と言えるかも知れない。

続きを読む
posted by Masa at 05:19| Comment(2) | 計算機囲碁 | 更新情報をチェックする

2006年06月11日

一試/乱数手生成 (1)

(擬似)乱数生成に関して一家言ある謎電の作者だが、このモンテカルロ法を使った碁の局面評価について「ふ、俺の右に出る者は少なくとも日本には居ねーな」などとちょー強気に思ってしまう出来事が最近あった(笑)。古くはノイマンの平方採中法、レーマの線形合同法、そのバリエイションで乗算合同法や混合合同法などがあるが、このブログで説明するには狭すぎるので詳しくはググって欲しい。これらは算術演算が絡んで遅いし、ハードで実現しにくい(完全に等価の処理にしたいなら資源を喰い過ぎる)上に良質な乱数が作れるとは言い難い。現在では(暗号用乱数としては向いてないが)極めて長周期でモンテカルロ法で使う分には優れているとされる「メルセンヌ・ツイスタ(略してMT)」がある。しかしながら、何れも謎的評価器では用いてない。理由は一言でいえば「遅いから」だ。MTは捨てがたいが、謎的電碁の中で使うにはゴージャス過ぎる。

今年の選手権の初日、とある方(特に名を秘す)に「ハードで乱数が作れるんですか?」と尋ねられた。謎電の作者は「出来ますよ、あくまで擬似乱数ですけど、ある程度周期の長い」と答えたことを覚えている。その時思ったね。「ふ、コイツまだまだ計算機科学とゆーものが判ってねぇな…。いいか、擬似乱数とは、こお作るんじゃああああぁぁぁ」。その最も典型的なものが「M系列(Maximal Length Sequence:最長符号系列)信号生成器」、別称LFSR(リニアフィードバックシフトレジスタ)と呼ばれ、一見インチキ臭い程単純なものである。先ずは具体的なLFSR回路例と特徴を示す。この手法の欠点を考慮しモンテカルロ碁に合わせた謎的改良内容については後日述べる。

続きを読む
posted by Masa at 12:02| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月10日

一試/評価器状態遷移図

というわけで、今日はシーケンサ(FSM)の詳細設計から入り、サクっと状態遷移図を描いてみた。

続きを読む
posted by Masa at 20:27| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月04日

一試/評価器の仕様変更(と方針変更)

評価器の詳細仕様を決めていく最中、特に乱数手生成方式をどうするか考えているうちに思ったのだが。以前「性能は追及しない」とか書いたものの、やっぱ性能を追求しないと意味ないし、その前にこの世界で曲がりなりにもメシを喰っている者としてのコケンに関わる(汗)ので、将来九路盤評価器を作ることも考慮し、且つChrillyを迎撃する予定もあるので、

世界を視野に入れたモンテカルロ評価器

にすることにした(笑)

続きを読む
posted by Masa at 23:18| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年06月03日

一試/スケジュール

本業モードに入ったものの土日くらいは試作を続けて行きたいところである。計算機将棋側の開発が煮詰まっている、てかワンチップマルチコア化の予備実験として、こっちの試作は利用価値があるので謎電の作者は結構冗談マジである。

さて一試の開発スケジュールだが、大雑把に次のような計画を立てた。
6月:詳細設計
7月:実装
8月:デバグ
9月:システム評価と二試への準備(九路盤)

今月は、特に評価器の機能ブロック別の詳細設計を進めていくつもりであるし、月末にはそれを完了させる予定だ。
posted by Masa at 23:57| Comment(0) | 計算機囲碁 | 更新情報をチェックする

広告


この広告は60日以上更新がないブログに表示がされております。

以下のいずれかの方法で非表示にすることが可能です。

・記事の投稿、編集をおこなう
・マイブログの【設定】 > 【広告設定】 より、「60日間更新が無い場合」 の 「広告を表示しない」にチェックを入れて保存する。


×

この広告は1年以上新しい記事の投稿がないブログに表示されております。