2013年03月28日

モンテカルロ法と擬似乱数

コンピュータ将棋つながりで最近いろんなCOMの思考ルーチン見てたんですが、
最近(もっと前から?)囲碁の方でモンテカルロ法が流行ってるそうです。

モンテカルロ法ってのは簡単に言えば
「答えを出す方法はあるが答えを出す式が分からない」系統の問題に、
手当たり次第適当に答え出しまくって確率で判断するって理論です。

よくある例えが円周率を求める例えで、

1.(0,0)-(1,1)の正方形に適当に点を打つ
2.0.5,0.5を中心に半径0.5の範囲に入っていればそれは円の中である
3.打った点の位置から2.であるか否かは分かる
4.打った点が円の中である点の数/打った点の総数は円の面積の近似である

こんな乱暴な理論なんですが、試行回数が無限になれば誤差0になることは証明されてます。

こういう単純明快で乱暴でそれでも正しい理論って大好きなので、
もうちょい深く調べてたんですが、モンテカルロ法で超重要な「適当」について
いろいろと思い出したことと知ったことがあります。

「適当」ってのは言い換えれば「乱数」なんですが、コンピュータの乱数
(正確に言うと処理系が提供してる疑似乱数生成関数)は大抵色々制限があります。

例えば範囲(返る乱数の種類)ですと
VBA:0〜2^24-1の整数(を16777216で割った浮動小数点)
VC :0〜2^16-1の整数(でもint型で返される)
しかありません。VCだと65536種類です。今のCPUだと一瞬で重複しますね。

周期も問題でして、こちらは VBA:2^24 VC:2^32 となっています。
周期ってのはその周期分取得すると、また同じものが1から出てくるってことで、
周期より多く乱数を取得すると、もはや乱数ではなくなってしまいます。

つまりどちらも、兆超える試行回数だと使い物になりません。
(シミュレーション系や、まさにモンテカルロ法だと必要になるんですよ)

さて、これらの疑似乱数生成関数は大体全部、線形合同法と言われる式を使っています。

こんなの。

X(n+1) = ( A * X(n) + B ) MOD M

※1)M>A M>B A>0 B>=0
※2)周期はA,Bを上手く設定すれば最大M

こんな単純な式で乱数っぽいのが作れるんだから凄いもんですが、
単純なだけに問題がありまして。

1.下位ビットがランダムではない
 作られた乱数に Mod 2 とかやると、0と1が交互に現れます。
 10進数で言うと偶数の次は必ず奇数になるってことですね。

2.組にして使うとランダムではない
 画面へ(Mod 256, Mod 256)で点を打つとかやると、
 永遠に打てない点が出たりします。

とまあ周期以前にえーって感じですが、
ここら辺をどう対応するかは処理系で変わります。

VBAはSingleで返すので、普通はRnd()*(2^24) Mod 16 じゃなくInt(Rnd()*16)でしょう。
VCだと上位ビットだけ返すようにしてます。(だから2^16しか種類が無いんです)

さて、まともな乱数作る方法がこの時代になっても無いのかって話ですが、
(上記でも数万回あたりまでは十分実用的なんですが)
まともな乱数の定義としては以下あたりでしょうか。

1.再現可能である
2.規則性が見られない
3.処理が速い
4.周期が長い
 
自分で考えたのが、円周率の小数点をn桁で区切って10^nで割ればよくね?っての。
円周率は無理数ですし、○桁から〜って指定すれば1.2.4.はいけそうだと思うんですが、
・・・superPIがベンチマークに使われてる以上、考えるまでもなく遅すぎるでしょうね。

で、今回始めて知ったのがXorShift。ソースこんなん。


// 自分用に書き換えてます。スレッドセーフじゃないです。
unsigned __int32 xss[ 4 ];
void xsinit( unsigned __int32 seed )
{
for( int i = 0; i < 4 ; i++ )
{
seed = 1812433253U * ( seed ^ ( seed >> 30 ) ) + i;
xss[ i ] = seed;
}
}
unsigned __int32 xorshift()
{
unsigned long t = ( xss[ 0 ] ^ ( xss[ 0 ] << 11 ) );
xss[ 0 ] = xss[ 1 ];
xss[ 1 ] = xss[ 2 ];
xss[ 2 ] = xss[ 3 ];
xss[ 3 ] = ( xss[ 3 ] ^ ( xss[ 3 ] >> 19 ) ) ^ ( t ^ ( t >> 8 ) );
return xss[ 3 ];
}


見れば分かりますが、ビットシフトとXORしかしてません。名前そのままです。
アルゴリズム的には線形合同法を128ビットに拡張して改造した感じ?(正直自信ない)
ぱっと見、相当早そうな感じです。Modとか無いですし。

で、このXorShift、周期は2^128-1です。これがどれぐらい長いかというと、
「4GHz16コアのCPUを持つPCを1億台繋げて1クロックで1乱数生成できて
スレッド・プロセス・ネットワーク間ロスはゼロ」だという
ありえない仮定を挙げたとしても、周回するまで15701億年かかります。
Wikipediaの時間の比較でもネタが無くなるレベルですね。

あとはメルセンヌツイスタ。これはアルゴリズムから違います。たぶん。
詳しくはよく分からなかったんですが、
1.周期が2^19937-1である
2.多次元において十分に不規則である
3.かなり凄い発明だと思うんですが普及していない
あたりは分かりました。

1の周期はもう一般的浮動小数点計算範囲から離れてるので諦めました。
たぶん宇宙が再配置とかそういう単位です。

2.3.はまあたぶん需要と供給の関係なんでしょう。
本気で乱数が重要な処理系ならハード乱数作るでしょうしね。
posted by Nick at 20:54| Comment(0) | TrackBack(0) | アルゴリズム

2013年03月24日

コンピュータ将棋 電王戦第1戦(COM将棋1)

事前に色々考えてましたが、結局はこーる君勝ちましたね。おめでとう。
まあおめでとうと言える時点で色々感慨深いんですけども。

こんな見方するのは私と技術者の一部ぐらいでしょうけど、
今回の勝負は言ってしまえば究極のデバッガーをごまかせるかどうかが問題。
(いろんな方面に失礼な意見ですが・・・)
ごまかせればCOMの勝ち。ごまかせなければ人間の勝ち。

で、それに「な?」って感じで指して勝ったのがこーる君。
この敗戦からCOM将棋技術者が学ぶことは相当多いんだろうなーと思います。

さて、思うところをつらつらと書いていきます。

1.COMはどこまで強くなるのか
 将棋は完全情報ゼロサムゲームなので、先手後手が決まった時点で勝負も決まります。
 実際に出来たら一部界隈では解明されたと呼ぶわけですが、
 将棋が解明されるのはいろいろ考えて無いだろうと思ってます。
 (コンピュータの進歩はいずれ止まると見てますので)
 
 そういう前提だと、取捨選択が必要になるわけで、
 それが羽生・渡辺より上手い方法を技術者が思いつけるかどうかが問題になりますが、
 難しいんじゃないですかね。
 
 ・・・最高に上手くいってトップ相手に五分五分ぐらいになりそうかなあ?

2.GPS将棋は卑怯という風潮
 正直一番驚いたのがこういう主張が普通にあること。
 数百台を繋いでるからだそうですが、単位が「台」になると1対1の感覚になるんですねえ。
 面白い見方です。人間としては分からなくもない感覚ですし。
 ただまあPCなんて所詮膨大なトランジスタの集まりであって、それぞれ信号をやりとりして動いてるので、
 それがネットワークを介するか信号線を介するかの違いなんて気にすることではないと考えちゃいますね。

3.勝敗予想
 1戦目終わってからするのは卑怯ですが、COMの4-1かプロの3-2かなーとか思ってました。
 この結果からすると、次COMが負けたら全敗もありえますねぇ。

今から一番面白くなりそうです、コンピュータ将棋。
posted by Nick at 21:12| Comment(0) | TrackBack(0) | コンピュータ将棋

2013年03月21日

顧客が本当に必要だったもの

ではないんですが、本当にやりたかったのはこんなのです。

pic5.PNG

前のやつに縦回転を加えたの。モデリングツールとかmitakaとかでやってるあれ。
原点の周りをカメラが球面移動してモデルを上下左右から見回すってやつです。

最初は単純にx軸で回転してy軸で回転すればいいやと思ったんですが、
そういや三次元の複数軸回転って回転する順番で結果変わるなーということを思い出しまして。

結果を一意にする計算方法ってあったけかなー、と探してるうちに
球座標とかクォータニオンとかいろいろ出てきてパニックになりました。

球座標
 原点からの距離、緯度、経度で座標を確定する方法。
 取り得る座標面が原点を中心とした球面になるので(たぶん)この名前。

クォータニオン
 虚数を使った四次元ベクトル。詳細はさっぱり分かりません。

球座標は持ってた参考書に出てきてたので簡単に納得。
確かに座標は一意に定まります。でもこれだとカメラの上方向が確定しないんですよ。
面倒だからってんで上方向(0,1,0)で描画しちゃうと90℃付近で変になる。当たり前ですけど。

クォータニオンに関しては便利そうなのは分かるんですが、
じゃあ自分で書いてみろと言われたら白旗あげます。

いろいろ考えてもよく分からんかったので、考え方を変えました。

クォータニオンですが、私が挫折した当時はそんな単語すら無かったはず。
(ここ最近の3D業界で流行ってる手法のようです)

しかし、当時にも3Dポリゴンゲーはありました。
(最古はドラッケンですかね?え、違う?)

てことはクォータニオンだの使わずとも3D表現は可能である。
原点を中心に球面を描いて移動するカメラなんて誰でも表現したいでしょうから、
当然その手法も存在するはず。なので昔はどう実装してたかを調べることにしました。





えっ!?確定しなくていい!?
計算の順番を固定して、全部それに合わせてるの!?

すごい発想。一意にならなくていいんだ・・・

とりあえずそれを参考に、X軸→Y軸で計算するようにしました。(順番適当)
球座標で悩んだカメラの上方向ですが、元の位置(0,0,距離)と元の上位置(0,1,距離)を
両方とも同じように回転させて、上位置-元の位置で算出してます。

結果。

dx5-5.PNG

おおー、回る回る。出来てるよー。

以下ソース

posted by Nick at 20:47| Comment(0) | TrackBack(0) | DirectX9

2013年03月20日

コンピューター将棋

いろいろ書くことはあるんですが、要約すると

・昔将棋ソフト作ってたけど挫折しました
・今将棋ソフトがプロに勝つかどうかの対局がある

って感じです。とりあえずは土曜日が第1決戦です。
posted by Nick at 22:16| Comment(0) | TrackBack(0) | コンピュータ将棋

2013年03月17日

Unity

この前ジュンクにDirectXの本探しに行ったら数冊しかなくてワロタ
まあ確かに自分の持ってる本も数年以上前の本ですけども。
そこまで人気ないのか。でもPCゲーって大体DirectXなのにな。

数で言えばDirectX:OpenGL:Unityが1:4:5ぐらいな感じ。
OpenGLはまあやること同じなのでどうでもいいとして、
Unityってのが面白そうでした。フリーのツールらしいです。

MSもXNAだったかな?似たようなの出してましたが、
開発終了ですってね。またMSか・・・って感じですけども。
(XBOX360も作れるんですよね。面白い試みでしたが。)

ちょっと気になったのでぐーぐる先生に聞いてみました。
XNA, DirectX, Unity, OpenGL と"3D"で件数チェック。

XNA : 450万件
DirectX: 4600万件
Unity : 3700万件
OpenGL : 2800万件

あらUnityすごい。OpenGLよりも多いのか。
素人さん寄りの人を取り込んでるのかな。
Direct3Dが大体使えるようになったらやってみようかな。

・・・XNAはまあ案の定ということで。
posted by Nick at 22:10| Comment(0) | TrackBack(0) | Unity

2013年03月15日

案の定でした

苦労しました。すっごく。

以下愚痴。

何でこう人の作ったシステムってのは使いづらいのか。
カメラなんて位置と視点決めればそれでいいじゃないか。
上方向ってなんだよちくしょう
※ 全体を回転させる場合に使うんでしょうかね?

RHWってライティングにも関わってくるの!?
どんだけフリーダムなのRHW
※ DirectXのデフォルトはライティング有効なんですが、
  RHWはライティング設定を無視するようです。
  今までRHWしか使ってなかったため、ライティング無効だと勘違いしたんですよ。
  元々は3Dの上に表示するメニュー的なものを扱うためのものだそうで、
  それはまあライティング影響しちゃうと困るでしょうけど。

描写対象にする深度って、具体的に明示するのね・・・
※ フラグみたいなの渡して、それで自動解決するもんだと思ってました。
  だって大抵のゲームってMediumとかHighで設定するので・・・

カリングモードにまで躓いた
※ 時計回りとか反時計回りとか気にしてなかったんですが、
  反時計回りでポリゴン作ってたため描写されずにあせりました。
  背景も表示するようにしちゃいましたが、普通はポリゴンの作り方直すんでしょうね。

愚痴〆

あとは普通に自分のミスですね。
回転関数ぐらいはあるだろうけど面倒だから自前で計算してたら
z軸計算時に計算後のx使ってたりとか、
三次元では2点確定の矩形は平面が確定しないことを忘れてたりとか。

いろいろ苦労しましたが、出来ました。
はじめてのさんじげんぽりごんです。

dx3.PNG

さすが3D、斜めでも問題ないぜ。

※ 左右が良く分からなかったので、mainポリゴンの左に小さいポリゴン置いてます。

以下ソース

posted by Nick at 23:45| Comment(0) | TrackBack(0) | DirectX9

2013年03月14日

Hello_World (Of 3DPolygon)

Direct3Dで二次元表現は概ね満足しました。
ってことで、次行ってみましょう。

ようこそ三次元世界!

目標としてはオブジェクトいろいろ配置して、
カメラをずーっと前に動かしていくって感じの絵を撮れるとこまで。

まずは最初の最初なんで、とにかく簡単なものから始めます。

ぱっと考えたのが、原点に板ポリ1枚置いて、その周囲をカメラが回る形。

c1.png
こんなん。

※1 本当に考えたのはちょっと違うんですが、解決したらいずれ書きます。
※2 この絵は5分もかけてエクセルで作ったんですが、エクセルさん何でも出来ますね。

さて、これをやるために必要なのが以下。

1.3次元に板ポリを置くこと
 RHW使ってる場合は特に気にしなかったんですけど、面倒そう。
 
2.カメラを操ること
 避けては通れませんよねえ

3.投影処理
 DirectXがやってくれるっちゃあそうなんですが、
 どうやらせるのか調べないとね

ま、おいおいやっていきますか。
posted by Nick at 20:01| Comment(0) | TrackBack(0) | DirectX9

2013年03月12日

D3DFVF_XYZRHWは相当特殊な意味らしい

ネットのソースが使ってたので普通に使ってたんですが、これかなり無茶なフラグらしい。
まあ無茶って言ってもサポートされてる以上普通に使えるんですが・・・

三次元の世界を二次元に描く場合、必ず投影処理が入ります。
地図や3DやレイトレやCAD、全部そうです。
それを実際にどうやるかはその処理系次第なんですが、
DirectXの場合はたぶんこう(じゃないかな)。

オブジェクトの位置決め

視点決め

全オブジェクトを視点からの座標に変換

透視投影で座標変換(この時点で二次元)

ウィンドウ座標変換

描写(BitBltと同じ)

どうも、この流れすべて無視するようです。すごいな。自由すぎる。

z座標いじくって遊ぼうとしたら全然変化無くておかしいなーと思ったんですよね。
描写直前の座標として扱われるらしいので、z座標とか関係ないのか。二次元座標だもんな。
だからx,yはピクセル単位(=ウィンドウ座標)なのか。へー。

そろそろ3D座標に手を入れてみようかなー
posted by Nick at 20:31| Comment(0) | TrackBack(0) | DirectX9

2013年03月09日

本番です

ポリゴンできた、テクスチャ貼れた、さあ次はαブレンドだってなもんですが、
αブレンドの計算自体、結構曖昧・・ってかいろいろあります。

よく使われるのが「Result = SrcColor * SrcAlpha + DstColor * ( 1 - SrcAlpha )」というもの。
※ Src:上の画像、Dst:下の画像です。

自分で書く場合もこれ使ってました。Srcにαチャンネルがついてる場合はその分αを掛け算。
つまりSrcのαチャンネル=0.4、SrcAlpha=0.8だった場合、0.32で計算です。

これで大体の場合にいい感じになるんですが、Dstがαチャンネルを持ってるとやっかい。

例えば四角いガラス2枚(Src:青とDst:赤)があったとします。背景は白でいいでしょう。
ガラスなんでαチャンネルは両方とも0.1ずつぐらいとします。
実際にこのガラスを重ね合わせて見ると、たぶん紫色でαチャンネル0.2ぐらいに見えるはず。

では上記の計算だとどうなるか。青が0.1なので赤が0.9になり、まっかっかになります。
α値自体の計算も上記でやっちゃうと、ほぼ不透明な赤い四角になってしまうんですね。
必ず背景(αチャンネル=1)があるのなら背景から計算していけばたぶん上手くいくんですが。

さて、Direct3Dではどうやって対処してるのかなーと見てみれば・・・
これはひどい、と言いたくなるほどのフラグ量。何個ですか。17個ですか。多いわ。
なんというか発想が欧米さんというか、数は用意したからあとは自己責任というか。
自分が使いたいのを探すのに苦労しましたよ。

そんなこんなでとりあえず出来ました!

dx3.PNG

おおー、αブレンドできてるー。

ソースは続きで。

続きを見る

posted by Nick at 07:42| Comment(0) | TrackBack(0) | DirectX9

2013年03月07日

次は当然テクスチャだよね

当たり前も当たり前。作りたいのはノベルゲーなんですから
当然画像を使えなくちゃね!

ただまあ色々調べてるうちに、どうもD3DX(Direct3Dヘルパ)を使わないと
単純に画像を読み込んでセット、は難しいっぽいことが判明。
※ D3DX使うとd3dx9が必要になるので面倒なんです

使わなくてもたぶん出来るんですけど、やってるサンプルが見つからない。
(自前で画像読み込んでテクスチャに色情報他を書き込むって感じだと思うんですが)

んー、まあそれは宿題ってことにして、
とりあえずは動くものにすることを優先させましょう。

ってことでこんなんになりました。

dx2.PNG

おお、GDIっぽい。いや、ポリゴンだけど。


ではソース。

続きを見る

posted by Nick at 20:15| Comment(0) | TrackBack(0) | DirectX9

2013年03月06日

Direct3Dはじめました

というわけで使ってみました。DirectX9で3Dです。


うむ。予想通り。

さっぱり意味が分からない。


「頂点法線ベクトル」とか「パイプラインステート」とか日常会話のごとく出てくるし、
「Direct3Dアプリケーションをプログラムするには3Dジオメトリの原理を
実務で熟知していることが必要です」っておい。そんな奴日本に何人いるというのか。
しかも実務で熟知って、それ思いっきり使ってる奴じゃねえか。
やったこと無い奴はどうすんだ。インロック状態か。

・・・とまあ関係者以外お断りな感じのヘルプでした。

しかも実装方法がCOMベースってのがまた敷居高い。
昔挫折した理由が分かりましたよ。
C++でCOM使うなんて書くどころか考えたことも無かったですから。

ヘルプは意味不明、ソースも意味不明、ポリゴンは苦手、
なるほどそりゃ挫折もしますわな。


今回はまあ多少は知識も増えてることと、
サンプル記載して説明してくれてるページがあったのが救い。

とりあえず板ポリ表示はできるようになりました。

dxnew1.png

こんな感じ。おお、グラデーションかっけえ。

ソースは以下で。コピペはダブルクリック。続きを読む
posted by Nick at 20:21| Comment(0) | TrackBack(0) | DirectX9

2013年03月05日

Direct3Dはじめまして

Direct3Dを始めた理由ですが、αブレンドを使いたかったからです。

元々は逆転裁判みたいなゲームを作ろうかなーと思いまして。
普通にやるならマスク画像AND転送してスプライトだーとか
バックバッファに背景書いてスプライト書いて転送だーとかで
終わるんですが、今時ちょっと古臭すぎかなあと。

最近ならテキストだのスプライトだのもフェードインアウトするのが
当たり前な感じですし、ならやってみようということで。

で、αブレンドを実際どうやるかですが、いくつか方法があります。

1.Win32API / GDI+
 論外です。速度・品質両面で使い物になりません。

2.自前で書く
 そういやVB6でやったことあります。
 少なくともAlphaBlendよりは速くて綺麗だったと思いますが、実践的ではないです。
 
3.自前で書く(SSE)
 昔やりましたが、今時ゴリゴリ書くのもねえ・・・

4.DirectX / OpenGL
 で、選択したのがこれ。OpenGLでも良かったんですが、
 クロスプラットフォームは今のとこ興味ないし、どうせ音はDirectXでやりますしね。

昔3D(ポリゴン)の習得に挫折した思い出もありますし、
ハードウェアαブレンドがどれほどのものかも知りたいですし、
とりあえずやってみることにしました。

まずはDirect3Dで逆転裁判みたいな絵を作ることを目標にします。


※ちなみに私は昔レイトレっぽいソフト作ったぐらいで、ポリゴンは初めてです。
 3Dの知識は一般人よりはあると思いますが、正直CADやってる事務のお姉ちゃんのが
 詳しいような気がします。
続きを読む
タグ:DirectX Direct3D
posted by Nick at 20:08| Comment(0) | TrackBack(0) | DirectX9

2013年03月02日

Google先生

この前仕事で同期系処理調べようとGoogle先生に聞いてみたら、
MSDNの次にこのブログがヒットしたんですが、
なんかどっかで見かけたような・・・とか思ってたら自分のブログでした。

そういえば書いてました、InterlockedExchangeとか。
(ほとんど更新してなかったけど)

まあ最近Direct3D始めたとこですし、仕事も一段落ついたし、
備忘録的なものがあると便利だなーと思ってたので、
これを機会にリニューアルしてみます。

しばらくはDirect3Dの話をまとめてきます。
posted by Nick at 11:10| Comment(1) | TrackBack(0) | その他