2007年10月06日

QuartusII Ver7.2

今日気付いたのだが、QuartusIIのVer7.2がリリースされていたので、早速インストールして使ってみた。

http://www.altera.co.jp/b/quartus72-web-se.html?f=hp&k=t0

ちょっと触った感じでは、やや大きめのモノだと「確かに速くなったな」と判るくらいなので俺的にOK。そろそろ彩の作者に醤油を飲ませる準備に入ろうかと思う、てか本業が一段落ついたらな、ふっふっふっ。
posted by Masa at 15:19| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2007年05月08日

FSMの記述法

選手権が終って戻ってきた。謎電の結果は散々(汗)だったが、色々得るものがあったので由とする。で、知っている人間にとっては馬鹿馬鹿しく簡単なのだが「FSMをHDLでどう書くんだ?」という質問をとある方に受けたのでそれを先に回答しようと思う。

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

2006年12月22日

Neuroモドキ

10年前のNeuroGoの資料:
http://www.cgl.ucsf.edu/go/Programs/neurogo-html/NeuroGo.html

簡単に言えば3層パーセプトロンで局面の形勢評価(その学習も含む)ということになる。これは飽くまで局面評価をNeuroな手法を用いているわけだが手生成にも使える。最も簡単な方法としては「1手進めてどの程度形勢が良くなるか」の評価値をそのまま手の優先度にすれば良いだけの話。

前稿で言うNeuroモドキとは、学習モドキ(単なる統計計算)は別システムで行う、更にコネクション数を極力減らし取り敢えず小規模なニューラルネットワークモドキでやってみる、くらいで考えている。PC上でシミュレーションを行って有効性を確認してから具体的な設計に入った方が良い気もしている。

今読んでいる参考資料:
http://www.murata.elec.waseda.ac.jp/~mura/u-tokyo/slide07.pdf#search='%E4%B8%89%E5%B1%A4%E3%83%91%E3%83%BC%E3%82%BB%E3%83%97%E3%83%88%E3%83%AD%E3%83%B3'
http://www2.ic.sie.dendai.ac.jp/neural/%E8%AC%9B%E7%BE%A910.pdf
posted by Masa at 16:27| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年12月21日

二試/準備 (2)

大雑把な仕様と方針と目標を決めることにする。一試での結果は勿論、開発の進め方に対する反省点も沢山ある。正直ちょっとどころか相当計算機囲碁をナメていたという気がする。しかしながら一試は彩は勿論、岡崎正博(39)を倒すという最終目標の為のMonteCarlo法の有効性の予備調査くらいの位置付けだったし大筋理解出来たし感触は悪くないというより極めて有力な手法であることが判ったので、この経験を踏まえて二試の仕様を決めようと思う。

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

2006年12月20日

MonteCarloMethod考 (2)

基本的には試行回数を元に精度(誤差)を計算できる。試行回数4n(あるいは22n)回とした時、nビットの精度±1/2LSBになる。例えば410=約1,000,000回の試行で10ビット精度±1/2LSB。実際にノード毎にそのような膨大な回数の試行は無理なので、いいとこ43=64回。これで3ビット精度、誤差±1/2LSBを得ることが出来る。余談だがノード毎に合法手数の自乗を超えて試行しても効果は薄いように感じる。直感的にそう思うのであって数学的な証明は用意してない。単に最善手を求める為に必要なレゾリューションを上回る試行はあまり意味がないだろうというくらいのことで、恐らく局面状態に因って試行回数の増減制御を行った方が効率が良い筈だが、その具体的な手法は今のところ no idea である。

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

2006年12月17日

更に再調査

前回の調査では交点優先度を8ビットとしたが、多分巧く工夫すれば1ビット減らせそうなので7ビットに変更し再度ビルドして調べてみた。結果は次の通り。
使用デバイス:StratixIII EP3SL150F1152C2
Info: Estimated most critical path is register to register delay of 6.114 ns
Info: Total cell delay = 2.866 ns ( 46.88 % )
Info: Total interconnect delay = 3.248 ns ( 53.12 % )
消費リソース:982ALMs
--
使用デバイス:StratixII EP2S60F1020C3
Info: Estimated most critical path is register to register delay of 9.575 ns
Info: Total cell delay = 3.074 ns ( 32.10 % )
Info: Total interconnect delay = 6.501 ns ( 67.90 % )
消費リソース:951ALMs
コレだとStratixII上で200[MHz]動作を実現出来そうである。因みにアービトレイションを行う前処理として「乱数生成+優先度の算出」、後処理として「交点座標デコード+手生成信号出力(+合法性判定処理が必要か否かの判断)」を行うことになるが、これらが1サイクル(5.0[ns])未満で行えるかどうかがポイントだ。この内、前処理部分は直前のサイクルで一部前倒し処理が可能なので、後処理がタイミング的に間に合うか否かがカギになる。
posted by Masa at 05:49| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年12月15日

予備調査(9路盤手生成用アービトレイタ)

九路盤用の3分木4レベルアービトレイタを作成しクリティカルパスを調べてみた。五路盤用と異なるのは、交点数が違うことは勿論、交点優先度情報(gp)が6ビット→8ビットに、交点位置情報(ga)が5ビット→7ビットに増えた点である。

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

2006年12月14日

三分木アービトレイタの再調査

将棋でもそうだが囲碁でも優先付けを強化した手の生成コストは大きい。非常に基礎的な実験を繰り返し行い改善策やツールの巧い使い方を発見することで、少なくとも表面的な性能は向上できる。というわけで、再度手生成の要であるアービトレイタについて詳細に調査を行った。

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

2006年12月06日

QuartusII Ver6.1

QuartusII 6.1がリリースされていたので早速DL&インストールした。で、以前、http://professionalhearts.seesaa.net/article/19829299.htmlで調べた三分木アービトレイタ(25交点用)について同じ条件、デバイスはStratixIII(EP3SE50F484/C2)を使ってクリティカルパスを調べ直してみると次のようになった。

> Info: Estimated most critical path is register to register delay of 4.674 ns
> Info: Total cell delay = 3.046 ns ( 65.17 % )
> Info: Total interconnect delay = 1.628 ns ( 34.83 % )

タイミングモデルがpreliminaryだし最高グレイド品を使ってみたし、fitterの最適化部分が改善されたのかも知れないが、StratixIIの1.5倍以上速くなってる。特に注目したのが配線遅延時間だ。思ったより短い。この分だと5路盤なら400MHz位、9路盤が250MHz程度、19路盤が150MHz前後で動く計算になる。C4グレイドだと性能が2割引きくらいになるので19路盤で125MHz。因みにEP3SL150が$549位(但しロットで購入の時の単価)になるらしく、これだと(ホスト間I/Fと別途分散器を含めて)9路盤コアが8個、19路盤コアなら2個は余裕で入りそうなので、なんとか実用域に入ってきたという感じである。ちょっとウロ覚えだが、PLD WORLD 2006の時に、「IIIはIIの3倍コストパフォーマンスが良い」とか言ってた。早くタマを出して欲しいところだ。
posted by Masa at 04:56| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年11月20日

怪しい、怪し過ぎるぜ!!

↓目には目を、歯には歯を、モンテカルロにはモンテカルロを!?
061120.PNG
恐らくプログラム名は彩ではなく怪だと謎電の作者は分析している。
posted by Masa at 22:23| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年11月01日

二試/準備(一試/反省) (1)

というわけで、今日から二試に入る。

一試については反省点が多い。これまで試作したモノについては、意図した結果が出てなさそうだという意味では失敗、試作したことによっていろいろ判ってきたという意味では成功。今回得た様々な反省を踏まえて二試の準備にかかる。

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

2006年09月30日

一試/動作検証&デバグ (4)

結局、未だ何か変である。あれから更にバグと思われる場所を修正してみたら位置格差が減ったが、それでも目標範囲内に入らないし、彩の作者の結果と微妙に離れたままだ。初手は「中央が最善、隅が最悪」という結論が同じというだけでは何か不安だ。設計上に根本的なミスがあるような気もしてきた。

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

2006年09月24日

一試/動作検証&デバグ (3)

計算機囲碁の神様は、謎電の作者に試練を与えてくださっているようだ(汗) 案ずるより産むが易しのつもりだったが、結構一筋縄ではいかないようである。その原因を作っているのは自分自身だが。生活の掛かった仕事で用いるような無難に動く堅実な設計より、道楽だからこそ出来る極めて大きな危険を内包した挑戦的な(この場合はちょーインチキな)手法を数多く試みている。それ自体は由としても、実績のない(あるいは少ない)手法はやはり綿密な計画を立て予備実験を重ね、ウラを取ってから使うべきだったかとも思う。が、後悔はしていない。開発とは決して後悔しないことだからである。

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

2006年09月11日

一試/動作検証&デバグ (2)

やはり変である。思うに、彩の作者の結果と比べて(交点あたり1,000,000局の評価として)各交点の平均期待値差が±数‰以内に収まり、上下、左右、対角対称の期待値の誤差(というか格差)が、同様に数‰以内にならないと、何か問題があるような気がする。今のところどちらの条件も満たしてない。少し立ち返ることになるが設計を見直してみようと思う。

余談だが、動作速度については今のところ最適化条件を厳しくするとfitterが遅くなり過ぎるので緩めている。現在は(評価器も分散器も共に)80[MHz]でしか動かしてないが、先の問題をクリアしたら2並列化と共に評価器のrequired fmaxを132[MHz]、速度優先にして試してみるつもりだ。
【追記】
上記で「数‰」というなにやら怪しい記述になっている。これを少し補足しようと思う。根拠がちょっとエエカゲンだが、謎電の作者は次のように考えている。
試行局数がSの時、精度Pは大雑把に1/√Sになる筈である。S=1,000,000の時、P=1/1000ということになり、言い換えれば「十進数で3桁の精度」ということだ。つまりは[‰]単位の精度が得られることになるのだが、使用している乱数は純粋な真性乱数ではないので、幾らか甘い結果になるだろうという読みで「数‰」とした。ここでいう精度の基準は、得られる期待値の最大範囲、即ち−25〜+25の50の幅の「半分」=25が対象。従って±1‰は地の数にして±0.025という意味になる。念の為に書くが、ここでのPは「‰(千分率)」の単位であって「%(百分率)」ではない。
posted by Masa at 22:38| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年09月10日

一試/動作検証&デバグ (1)

というわけで曲がりなりにも(というより曲がりまくってるような気がするが)何となく動いているレベルまで来たようである。

が、しかしだ。

なんか、http://www32.ocn.ne.jp/~yss/monte.html で示されている結果と微妙に異なる。C3の位置に打つ手が最大になる、即ち最善手は同じだが期待値がやや大きく違う。このような現象が起きる理由は、アルゴリズムが微妙に異なるからなのではないかと思うが、もしかするとこっちのバグかも知れないので、もちょっと精密な検証が必要のようだ。

因みに現在、シングルコア実装で試験を行っているもののゴールが見えてきたような気がする。ふ、これでまた一歩、無謀に近づいたな。
posted by Masa at 21:45| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2006年08月06日

一試/フロアプラン

結局単体完まで漕ぎ着けたとは言い難い。部分的にはもう少し手を入れたいが、凝り出すとキリがなくなりそうなので、一試でもあるし一旦終了して、結合試験(&デバグ)に入ろうと思う。

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

2006年07月02日

一試/実装進捗 (1)

というわけで、全ユニットとその構成についてリストを作り、これまで一時的・試験的に作ったコンポーネントについて纏めてみた。

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

2006年07月01日

一試/GPUブロック図

なんだかあっという間に6月が終わってしまった。頭の中ではほぼイメージ出来たし、わざわざ解説するまでもないものまで書いていくと年を越えて続きそうなので、心臓部である交点ユニット単体を図で示して設計フェイズを終了する。

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

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月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) | 計算機囲碁 | 更新情報をチェックする

2006年05月25日

一試/評価器の機能仕様

今回の試作は、特にこの謎的モンテカルロ評価器の開発が要である。この評価器の特徴は、

・完全にハードウエアで実現していること
・またデータフロで石の活死判定を行い極めて高速であること
・更に地球環境に優しい低消費電力であること
・付け加えて将来、低コスト超分散並列処理を視野に入れていること
・何と言っても謎電の作者が冗談と道楽でやっていること

等々がある。これは、x86系マイクロプロセッサがどんなに速くなろうともソフトウエア処理の追随を絶対に許さず、計算機囲碁開発者に対してモーレツ且つキョーレツなプレッシャ〜を掛けるには充分な要件を満たしている。が、しかしだ。もし開発に失敗すれば、

何だよ、脅かすなよ、そんなオチが待ってたのかよ、このブログは!!

と蔑まされシャレでは済まなくなり、今後二度とこの業界に足を踏み入れることが出来なくなるところまで進んじゃってるんじゃないかと、最近の本ブログのアクセス数を見て謎電の作者は分析している。

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

2006年05月24日

一試/NiosII(分散器)の機能仕様

この試作でのNiosIIの役割は、基本的には評価器の検証(デバグ含む)が主目的だが、時代のトレンドとなっている並列処理を実現する為の「分散器」の役も担わせている。将来、専用回路を組む為の予備実験の意味も持たせているので、機能の詳細については決定し難い部分が多い。従ってここではNiosIIをどのような設定にするかについてのみ決めておくことにする。

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

2006年05月23日

一試/NiosII-評価器間通信および評価器分散並列制御仕様 (2)

更に一歩踏み込んで仕様を(暫定的であるが)規定する。NiosIIからの評価器制御は、今回Memory mapped I/Oで行う。つまりはNiosIIからは評価器が単なるメモリ(SRAM)に見える、ということになる。具体的な仕様を次に示す。

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

2006年05月22日

一試/NiosII-評価器間通信および評価器分散並列制御仕様 (1)

ここでは、PC(IDE)からNiosIIへ渡されたデータとRコマンドによって実行指示を受けた時点での「NiosIIと2つ評価器の動作仕様」について決める。これらの動作仕様について箇条書きにすると次の様になる。

【NiosII側】
・評価器に対して局面データ、乱数手生成の為の種値、および動作モードを設定する(初期設定)。
・空いている(Ready状態の)評価器を起動する(これで評価器は処理を開始しBusy状態に入る)。
・評価器の処理が終了するのを待ち、終了した評価器から値を貰いそれを積算する。
・設定された回数分の評価処理終了後、その積算結果をPC(IDE)へ返す。

【評価器側】
・NiosIIからの起動指示でモンテカルロ評価処理を開始する(Busy状態に入る)。
・処理終了と同時にNiosIIへ終了表示行う(Ready状態に戻る)。

NiosII-評価器間通信および分散制御(動作)シーケンスを次に示す。

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

2006年05月21日

一試/PC(IDE)-NiosII間通信仕様

NiosII IDEにはコンソール即ちテキスト端末が用意され、NiosII間とUART(USB-JTAGを介して)通信が行えるようになっている。これを用いて手入力でNiosIIにテキストコマンドを送り、それに応じてNiosII側で何かしら処理を行わせレスポンスを返すことで実現する。ここでは、そのコマンド・レスポンスについて仕様を決める。具体的なコンソール入出力イメージを次に示す。

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

2006年05月20日

一次試作仕様作成

実際にこの試作を行う為には、予め仕様を決めておく必要がある。機能単位に分けて項目を挙げてみると、次の様になる。

1) PC(IDE)-NiosII間の通信仕様
2) NiosII-評価器間の通信仕様(評価器の分散並列制御仕様含む)
3) NiosIIの機能仕様
4) 評価器の機能仕様

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

2006年05月19日

先ずは試作だ

というわけで本家でも書いた、例のNiosII評価キットを使って一次(検証)試作を行おうと画策している。このことは計算機囲碁開発者、特に彩の作者とChrillyにはマジで内緒だ(笑) 要求仕様としては、

・5×5盤モンテカルロ評価器
・その2面分散並列処理
・当然、手の乱数生成は面独立(でなければ、分散並列化の意味がない)

この回路によって計算させた結果が、既に判っている結論、例えばhttp://www32.ocn.ne.jp/~yss/monte.htmlで示されるような内容と一致するかどうかを検証するのが目的だ。

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

2006年03月18日

I bet.

「囲碁のプログラムは何であんなに弱いんだ!俺がサクっとFPGAでハードウエア化して2年以内に9路盤で圍棋文化研究會の岡崎正博(40)に勝つシステムを作ってやるぜ、焼酎を50升賭けるぞ!」

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

2005年12月26日

石を取り除く処理 (7)

ここまでは特に活死判定方法について考察し、判定開始〜活死判定終了までの処理を設計して来た。最後は「死んでいる石をリセットする仕掛け」を作れば盤上から「石を取り除く」ことが出来るわけだが、それと同時に死んでいる石のカウントも必要だと思われる。それも含めて考えることにする。

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

2005年12月24日

石を取り除く処理 (6)

ユニットが動作中か否かの監視を実現する方法は、簡単に言えば「活死判定ユニットのssoが、ある時間経過して変化したか否か」を全ユニットについて検査する、ということである。ユニットの中の何れか1つでも変化があれば動作中、全く変化がなければ「結論が出た」と判定するわけだ。ここでいう「ある時間」とは「基準クロックのサイクル時間」という意味になる。

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

2005年12月19日

石を取り除く処理 (5)

この手の回路はかなり特殊で、実質的クリティカルパスが内部データによって異なるような設計は一般に殆ど行わない。先に示したユニットを何の工夫もなく使えばトンでもなく遅くなり実用的ではなくなる。先ずその理由を考えてみることにする。

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

2005年12月18日

石を取り除く処理 (4)

先の図の中から何れか黒石1つを取れば、そこに空点が生まれることになる。となれば、その交点ユニットのsoはOFFからONに変化し、そのことで活死判定ユニットのssoもONに変化する。その信号が上下左右の4つのユニットに対して送られることになるが、白石に対してどのようにその情報が伝搬するかをここでは考察する。

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

2005年12月17日

石を取り除く処理 (3)

実際に先の回路を格子状に接続してみる。なお、生きているか否かを判定するユニットを今後「活死判定ユニット」と呼ぶことにする。ここでは簡単な「シングル処理」のユニットを用い、図が複雑にならないように、意味のある信号名のみ表示しているので注意。

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

2005年12月12日

石を取り除く処理 (2)

結論を先に書くと、生きていることを報せる相手の交点は同色の石でなければならない、ということだ。そのことが先の回路では考慮されていない。このままでは、ある任意の色の石に空点が接続されているか否かの判断を正確に行うことは出来ないので、その対処を入れてみたのが下図。ここでは2つの案がある。

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

2005年12月11日

石を取り除く処理 (1)

p.30の「3.4石を取り除く処理」は、7頁に渡り4項に分かれて解説されている。それだけ重要な処理だということで、ここは気合を入れてデザインする必要があると思われる。ざっとこの節を読んでみて感じたのは、FPGAに組み込むならハードならではのアルゴリズムに置き替えなければ意味がない、ということだ。ソフトでは関数の再帰呼び出しによって石が生きてるか否かを単純に判断できる。しかしここに書かれてある通りのことをそのままハードで行うことは、実現が難しいというより寧ろ複雑になるし、それ程速くはならない。
ハードが得意とする、てかFPGAを使うことの意味は「分散化・多並列化とデータフロ化」による処理の高速化で、再帰的手続きそのものを分散化・多並列化・データフロ化してもこの場合意味がなく、そもそもハード処理には向かない。そこで発想の転換が必要になる。
ここでは交点数と同じ数の分散並列化とデータフロ化によって(再帰処理なしで)石が生きていることを検出する方法を何回かに分けて考えることにする。余談だが「分散化」と「並列化」は似て非なるものである。但し、今回は並列化するために分散化している。念の為、言葉の定義を示す。

・並列化:複数の処理を同時に進行させる事により、効率の向上をはかる手法のこと。
・分散化:複雑・大規模な処理を複数に分割して処理し、その結果を結合して実現する手法のこと。

まず単純に考えてみる。ある石が生きているか否かの判定の基本は「四方に空点が1つでもあるか否か」である。それだけを考慮し設計した交点毎の回路が下図である。

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

2005年12月10日

対局の流れ

本の中では一見フロチャート風で書かれているが、ここではSDで書き直してみることにした。純粋なソフト屋では見慣れてないか全く書かないかも知れないが、ファームorハード屋の場合は必須のドキュメントと言える。特にFSMを設計する場合最低でもこれを書かずに作り始める奴はいない。慎重な技術屋なら更にマトリクス(状態遷移表)を書く。

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

2005年12月09日

碁盤の表示

p.26の3.2碁盤の表示に進む。表示とは、機械側が持つデータを人間に表し示すことだ。ソフト的には二次元配列変数board[y][x]で(x,y)位置のデータを管理し、それを何かしら目に見える形で出力すれば良いだけの話。ハード的には、最初にその内容をread(あるいはそこへ任意のデータをwrite)する為の仕掛け、つまりはアドレッシングが予め必要なので、先ずその処理をここでは考えてみる。

GPRは結局2ビット幅のメモリの、その1つと見立てることが出来る。9路盤なら2ビット幅×81のRAMとして機能出来れば良い。となれば、GPRの「住所」を決定するためのアドレスデコーダが必要になる。で、具体的に9路盤用でデザインしてみたのが下図である。

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

2005年12月08日

碁盤の初期化

以上で、ここをご覧になる訪問者は、もー完全なハードのエキスパートであるものとして次に進む。

p.25の碁盤の初期化を行う関数。これをハード的に行うのは極めて簡単だ。先の回路図のclrn(負論理なので注意)を一旦(ON状態から)OFFにすれば初期化終了(clrnは通常ONでレジスタの中身をクリアしたい場合、一時的にOFFにする)。9路盤なら81組の、19路盤なら361組のGPRを一瞬にして初期化出来る(つまりは盤全体が完全に石なし状態となる)。
posted by Masa at 01:43| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月06日

待ってましたの第3章

第3章 碁盤プログラムの作成
やっとプログラムの話が出て来ました。トップクラスの囲碁プログラマが推奨する囲碁プログラムの作り方は? 楽しみです。ここは「節」単位で噛み締めてみる。
3.1 碁盤の表現(データ構造)
考え方としては空点と色(敵味方)の識別ができれば良いわけで2ビットで表現できるわけですが。ここではbit0を白、bit1を黒として、その色の石がある時ONということで。更に盤外表現でどちらもON。これはソフトならではの常套手法で囲碁の場合は特に合理的。ハードに置き換える場合は不要といえば不要な概念。結局交点を管理する「交点ユニット」が3種類必要。端と壁と完全な盤内(盤外を傍に持たない交点)用の3種。但しこの場合、回路記述自体は1つで充分の筈。

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

さて、第2章

第2章 囲碁プログラムの設計
p.22より引用「チェスプログラムや将棋プログラムのような先読みをするプログラム(中略)この方式が将来、主流になると予想される」
ええっ?将来!? いやあ、今現在が主流なのかと思ってました。ってことは今の主流は「探索」というものを行ってないってことなんですかね、その方が驚きですが。
で余談ですが、さっき彩の最新バージョン(5.54?)を試してみました。これは探索やってますね。9路強い。考えずに打ってると私の方が負けます。19路も考えずに打ったらいい勝負になる。おっかしいなあ、てか10年前にとある囲碁プログラムを試した時は10局やって10回勝てたんですが、しかも大差で。当時あまりに弱いんでアホらしくなって興味が失せたんですが。やっぱ技術の進歩ってのは恐ろしいなあと思いましたね、ええ。
posted by Masa at 00:25| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月05日

やっと届いた

先日発注した本が今日(正確には昨日の昼間)に届いた。で、早速バッと全体を斜め読みしてみる。やや初心者向けのような気もするが、今まで囲碁プログラムを書いたことのない私にはピッタリかもしれない。というわけで、これから少しずつ読んで、その感想を日誌的にこのブログに記録しようかと思う。
第1章 コンピュータと囲碁
p.7から引用「チェスや将棋では、駒の損得という比較的重要でかつ簡単に計算可能な基準があるが、囲碁の場合には、それに匹敵するほどはっきりした基準はない」
ええっ?そうなの!? と思った。いやあ、そういう感覚はなかったなあ。Chrillyもそうだと思う。つまり「囲碁をナメてた」かも知れない。まだ良く理解してないのだが。
http://www32.ocn.ne.jp/~yss/igo.htmlに拠れば、「囲碁のプログラムは何であんなに遅いんだ!俺がさくっとFPGAで囲碁のプログラムをハードウェア化して1年以内に9路盤で初段のプログラムを作ってやるぜ!ビールを50リッター賭けるぞ!」だそうだが、Chrillyの負け? 既に1年経ってるしなあ。
posted by Masa at 00:04| Comment(0) | 計算機囲碁 | 更新情報をチェックする

2005年12月02日

例の本を発注した

例の本とは、ズバリ「コンピュータ囲碁の入門」。
以前、http://www32.ocn.ne.jp/~yss/howtogo.htmlを読んだりはしてました。が、あまり真剣に囲碁の研究はやってなかったので、これくらいは読んでおかないと、というわけで。
このことは山下さん(特に名を出す)には秘密だ(笑)
posted by Masa at 01:00| Comment(0) | 計算機囲碁 | 更新情報をチェックする

広告


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

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

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


×

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