カルドセプトサーガの乱数問題

Posted on 2006/12/19 by Kaede Fujisaki

「カルドセプトサーガ」というゲームで、サイコロが常に「偶数・奇数」のパターンを繰り返す、というバグがあって一時期祭りがありました。

以上を参考にしてもらえば大体分かると思います。

■自称「正しいコード」も間違っていた

２ちゃんのスレでどうも自称「正しいコード」が張られたらしい。今チェックしてきたんですが、見つからない。もう遥か昔に消えたか・・・。

　やがてそのような書き込みの中に、Cコードを示して「サイコロなんかたったこれだけで作れるのに」と発言する物が複数現れた。そしてこれが最も重要な点だが、そのようにして示されたコードは、私が見た限りでは一つ残らず全てカルドセプトサーガのプログラマが犯したのと同じミスをしていた。

ﾜﾗﾀ。というわけで、今回は同じ間違いを犯していない正しい乱数発生コードを書こう！がテーマです。

良い乱数・悪い乱数

こちらの記事と一緒に読むと分かりやすいと思われます。

■バグを分析

ダイスの法則性が発見されました

【法則１】

最大ダイス目が偶数のマップでの非ＡＩ戦において、ダイスによって導かれる数値は奇数と偶数を交互に繰り返す。

これはただ単に線形合同法を使って最下位ビットを捨てなかっただけですね・・・。最下位ビットは常に01010101・・・と0と1を交互に繰り返します。（定数値が悪ければ0か１を繰り返します）

【法則２】

最大ダイス目が奇数のマップでの非ＡＩ戦においても法則性が指摘されています。

※確定情報では無いため、現時点での統計情報を採りあげています。

例）

ダイスの最大目が７かつ祠の無いマップにおいて、

前に出た目からの予測が可能な、次の目の傾向。

・１の次は１か４か６

・２の次は２か４か６

・３の次は２か４か７

・４の次は２か５か７

・５の次は１か３か５か７

・６の次は１か３か５

・７の次は１か３か６

これは難しい。上位4ビットだけを取り出したとかだったらありうる周期は2^4=16以下なので、周期がたまたま7とあってしまった、と考えられますが・・・。そんな馬鹿な仕様にしてるはずが無い・・・。

これはすいません置いておきます＞＜

数学が得意な人or解析済んだ人教えて＞＜

XBOX360の改造コードが見つからないということは・・・まだ解析は出来ないのかな？

■改善策

これを使う

ﾜﾗﾀ

だまってメルセンヌツイスタを使う（BSDライセンスです）

ABA GAMESでも使ってました。だから何って話ですが。ABAGAMESの実装でも最下位5ビットは捨ててました。

線形合同法を少し工夫する
- 下位数ビットを捨てる

すっげー当たり前のことを延々と述べてすいません。ってかこの話題って少し詳しい人間なら大体知ってるもんだと思ってたんですが。違うのか。こう偉そうにいっておいて間違ってたら泣けるな・・・。

と思っていたら、上で紹介したスラッシュドットにこんな書き込みが。

　VCのrandはそれほど質が悪くありません。 gccなどは非常に質が悪く、最下位bitは必ず0と1を繰り返します。 XBOX360の開発はVCじゃない（マイクロソフトなのに）ってことでしょうね

gccの標準ライブラリ書く人って大分詳しい人間だと思ってたんですが・・・。

■Cで書いた「自称正しいコード」

懐かしい、成分解析の時のアレ以上に良いコードが思い浮かばない。つーかこれでFA？

少し変えて再度書いちゃいます。

unsigined int seed = 0; //グローバル変数．
unsigned int random(){
int result;
seed *= 214013;
seed += 2531011; // ->次に呼び出されたときのseedに使う
result = seed;
result = result >> 0x10;
result &= 0x7fff;
return result;
}

■

ちなみにこれ、VisualC++の標準ライブラリまんまだと思われます。今回のカルドセプトサーガもXBOX360ということで開発環境はVisualC++だと思うんですが・・・。「開発環境によって乱数の発生アルゴリズムが変わっちゃいけない」と思って自前で用意したんでしょうか。リプレイ機能があるそうなので、ある意味この判断は正しいかも。他機種に移植する気があって、それらのソフト間でリプレイを行き来できるようにする気があるならね。他機種間でネット対戦させるなら、場合によっては必要かも・・・。

gprof「undefined reference to `mcount’」エラー回避

Posted on 2006/10/07 by Kaede Fujisaki

■gprofの概要とか。

　gprofが何なのかよく分かってる人は次の項目からどうぞ。

　現在、Eclipse+CDTを使ってCでゲームを書いているのですが、ちょっと遅い。どこにボトルネックがあるのか気になっていたのですが、手動で時間を計るのは、さすがにめんどくさい。

　というわけでいろいろ探してたところ、どうもGNUのgprofという、関数別に実行時間を測定してくれるソフトがあるらしい。まあ多分一般常識レベルなんでしょうけどね、この世界だと・・・。

　利用するためにはプロファイルというのが必要で、ビルドオプションをいじって、実行後にプロファイルがexeファイルと同じフォルダに出来上がるようにしなきゃいけないらしい。で、このプロファイルとexeファイルをgprofに流し込むと分析してくれるそうな。

　で、Eclipseの設定を眺めると、コンパイラのデバッグオプションの設定項目に、gprof用のプロファイルを出力するオプションがあります。これをチェックすればいいのか、やっぱGUIって何だかんだ言って楽だ†1な、と思って余裕でクリーンコンパイルしたところ、

undefined reference to `mcount'

というのがリンク時に出てきて完了できない。結構これで詰まってる人は多いんじゃないでしょうか。だって、EclipseCDTはこれしか設定項目がないから。

　で、長々と書きましたが、結局は、どうやってEclipse+CDTでプロファイルを出力する実行ファイルを出力するか、がこの記事でやりたいことです。

■リンクエラーが出てしまった原因。

　こちらを参考にすればすぐわかる事ですが、コンパイラオプションだけでなく、リンカオプションにも-pgオプションを設定する必要があります。

　Eclipse+CDTの設定項目はコンパイラオプションにしか追加してくれません。何考えてるの？

■Eclipse+CDTでプロファイルを出力させるには

まずは、[プロジェクト]->[プロパティ]->[C/C++ビルド]を表示させておきます。

■コンパイラオプション

　[GCC C コンパイラー]->[デバッグ]で表示される設定項目のうちの、[gprof向けプロファイル情報の生成(-pg)]をチェック

■リンカオプション

　[GCC C リンカー]->[その他]の、リンカー・フラグに「-pg」を追加します。

■テストするには

　上記を設定したあとに完全コンパイルしたあとに一回実行して、gmon.outが出力されていることを確認。

　コマンドプロンプトを起動して、gprof.exeにパスが通っていることを確認した後にコンパイルしたexeファイルと同じフォルダに移動して、

gprof ***.exe gmon.out -p

とすると、各関数別の実行時間を表示してくれます。下のほうの英文が要らないと思ったら「-b」オプションです。

　なお、静的ライブラリにおいては、コンパイルオプションに-gpがついていると時間測定はしてくれるようですが、何回呼び出されたか、に関しては分からないみたいです。ゲームのうちの中核部分は静的ライブラリにして呼び出していたので、これは残念・・・・。

■ちなみに

　合計で0.01秒以上実行時間がないと時間が不明なので、ゲームの場合は結構な時間動かしておかないと測定できないかも。ゲームで0.01秒って言ったらかなり長い時間ですからね。約0.6フレーム。

■どうでもいいこと

「うさだBlog」をアンテナに追加しました。鋭すぎる。ネトゲ以外にも話題はあるので、ぜひご一読をお勧めします。プログラミング技術もすごいっぽい。

　こういう人に成りたいなぁ。どうやったら成れるのかなぁ。とりあえずはお勉強がんばります。。。。

小文字：１０代女子に流行、難解・新表記　ネット時代の自己表現！？－家庭：MSN毎日インタラクティブ

　要するに、ヵっぉぉゃっょ。

　何をいまさら。7～8年くらい前にぁゃιぃわーるど周辺ではやってませんでしたっけ、この表現。タイトルからしてそうですし。というか、あんぐら全般？今の女子中学生があんな書き込みを見たら、なんて思うのかな？ｗ

†1: まあGUIってホント糞なUIだな、CUI最高と思うこともあるわけですが。

bitGenerations用「警告-健康と安全のために」解除パッチャー

Posted on 2006/09/09 by Kaede Fujisaki

　ウェイトコードと、一部のループをつぶしています。OrbitalとColorisの処理を参考にして作ったので、OrbitalとColorisでは完璧に動作します。

■ダウンロード

Download

　使用にはJavaが動作する環境が必要です。使用方法はファイル名をコマンドライン引数にして実行するだけです。

　Windowsの場合はサーナイトのアイコンのプログラムにドラッグ＆ドロップするだけで使えます。複数ファイルOKです。（と思ったけどサーナイトのアイコンのプログラムの方のバグで無理な場合もあるかも？そのときはひとつづつお願いします。。。。）

使用は自己責任でお願いします。（おやくそく）

■動作リスト

1st
- Boundish—？
- Dial Hex—？
- Dot Stream—？
2nd
- Sound Voyager–？
- Orbital–○
- Digi Drive–？
- Coloris–○

○：完璧に動作する

△：すこし問題あり

×：解除できない、または起動できない

？：不明

テスト結果を募集中です。ご協力お願いします。

「成分解析」 for CGI written in C

Posted on 2006/04/06 by Kaede Fujisaki

「成分解析」 for CGI written in C

もしかして，自分，馬鹿じゃね？（何を今更

これ，プログラミングの練習に丁度いいですね．そうですね，HelloWorldの次の次の次の次くらいに書くには丁度良いですね．

っていうか，その，ポインタで結構苦戦しました（ぉ

Javaの参照型で慣れてるつもりだったんですが，ダメダメですね．

「成分解析」 for CGI written in Cの成分解析結果 :
「成分解析」 for CGI written in Cの40%はやらしさで出来ています。
「成分解析」 for CGI written in Cの34%は柳の樹皮で出来ています。
「成分解析」 for CGI written in Cの22%は砂糖で出来ています。
「成分解析」 for CGI written in Cの2%は鍛錬で出来ています。
「成分解析」 for CGI written in Cの1%は努力で出来ています。
「成分解析」 for CGI written in Cの1%はツンデレで出来ています。

うるさいうるさいうるさい！（ぉ

（04/07追記）GETメソッドにしてみました．こっちの方が簡単なのに，なんでPOSTにしてたんだろ？掲示板とかだとPOSTの方が良いらしいんですが．つか宿題終わってねぇ(‘A`)

（04/12追記）同じパーセンテージの時に，少し結果が変わってしまうのを修正．

「成分解析」 for Java

Posted on 2006/04/04 by Kaede Fujisaki

　「成分解析」解析結果に基づいて，JavaAppletで作っちゃいました．よって，本家と同じ結果を返します．あれ？宿題やるんじゃないの？(‘A`)

　重そうなので下においておきます．つーかさ，Javaでツール作るって結構難しいね．符号なしの型が無いからさ．Cでも本格的にお勉強しようかしら．

　なお，本家には10種類以上表示できないバグ(“あ”といれて見ればわかる．99%にしかならない)があるのですが，Java版では本来の動作をさせています．

　(04/06追記)CでCGIにも移植しました．

カブロボウォッチ　6号さん優勝

Posted on 2006/04/03 by Kaede Fujisaki

カブロボ公式サイト

1 鈴木さやか＠6号さんBayesianRobot　  2005-12-16　  71　  6,896,400円
2 iwatch		BayesianRobot　  2005-12-19　  70　  6,783,500円
3 dal102		BayesianRobot　  2005-12-21　  68　  6,614,500円
4 ぺす		BayesianRobot　  2005-12-25　  67　  6,585,000円
5 悠之介		簡易ロボット        2006-01-01　  62　  6,568,100円

　というわけで，6号さんが一位でした．おめでとうございますオブジイヤー☆（ｗ

　記念という事で続編のぱにぽにたーぼ！よろしくお願いします（ｗ＞スクエニ

マジカル☆なっちん

　なっちんは，資産総額 5,579,100円で総資産でのランキング160 位で終了となりました・・・かも．運用期間が長いので，年率ランキングではランクが落ち，281位でした・・・かも．

　結局最終晩は昭和シェルを買いあさり，エーザイを売ろうとするものの50万円の制限が掛かってたので売れない，というので安定してしまいました・・・かも．原因は，判断基準を長期にしすぎてしまい判断がなかなか切り替わらなかったこと，売るのにも制限をかけてしまったこと（売るのに関しては最低でも一株分，とかすればよかった・・・かも．）などがある・・・かも．

　次回の5月上旬のコンテストにも参加したい・・・かも．6号さんはどうするのかなぁ・・・かも？

■連絡

　宿題がヤヴァイので一週間以上はお休みします(；´Д｀)

　〆切間際の修羅場は逆に落ち着く事が大事なんだよね～

Eclipse + CDT + MinGW + SDL + OpenGL

Posted on 2006/04/02 by Kaede Fujisaki

　昨日のアイレムは凄かったですね．凝りすぎて逆につまらないかと思ったら，ウサギで吹いたｗ

■Eclipse + CDT + MinGWでSDLをコンパイルするメモ

　EclipseのC/C++用プラグイン，CDTとWin用GCCのMinGWを使ってSDLプログラムをコムパイルするメモメモです．なんだか今日はノリノリです．

　とりあえずまずは，C-Compiler Wikiを参考にHelloWorldを表示するプログラムは作れるようになっておいてください．

■SDLを導入しておく

　ダウンロードページより，MinGW用SDL開発ライブラリを手に入れておきます．ファイル名は今のところは「SDL-devel-1.2.9-mingw32.tar.gz」です．

　解凍した後，中身をどこか適当な場所にぶち込んでおきます．ライブラリ用のフォルダを作って，そこに今後はいろいろなライブラリをぶち込んでおくとすると楽です．

　なお，実行するにはSDL.dllをパスの通っているところにおく必要があります．パスを増やしすぎるとなんか認識しなくなるっぽいので，あんまり増やしたくない人はsystem32あたりに入れておいてください．

　なお，大多数のデモはSDL/SDL.hをincludeするので，include中身をすべて，include\SDLにコピーすると楽かもしれません．

■OpenGLもどうせなので

　3DならOpenGlっすよね，ということで，OpenGLも導入しちゃいました．OpenGL自体はMinGWに入っているのですが，GLUTという追加ライブラリは入っていないので導入します．Windows用はこちらよりglut-3.7.6-bin.zipを落としてください．解凍したあと，「glut32.dll」はc:\WINDOWS\system32に，「glut.h」はMinGWのindlude\GLにぶち込んでおいてください．

　これでうまくいくはずですが，テストはしてないので間違ってるかもしれません（ぁ．

■Eclipseの設定

　Makefileの書式をお勉強するのが面倒なのでManagedBuildを使って，とりあえず適当に書いたソースに

#include

を付加し，これでテストしてみます．

libmingw32.a(main.o)(.text+0x106):main.c: undefined reference to `WinMain@16'

とか出てきたんで調査，調査．

結果，以下のようにすればいいっぽいです．

プロパティのビルド構成のCコンパイラの「ディレクトリ」でIncludeパスに”＜SDLのインストール先＞\include”を指定
同じくCリンカの「ライブラリー」ところの「ライブラリー(-l)」に，「mingw32」「SDLmain」「SDL」を上から順に指定．順番が違うとダメっぽい．
ライブラリ検索パスに”＜SDLのインストール先＞\lib”を指定．

これでコンパイル出来るんじゃないんですかね．

　で，ところでprintfが使えなくなったんだけど，仕様的にこれで正しいの？（ぉ

　まあ，今後，SDL+CかDでゲームでも作ってみたいなぁと．Javaに比べ爆速であると期待・・・．あ，なおJava用SDLもありますので，ぜひお試し下さい．あ，そっちからやろうかな，まずはSDLに慣れるってことで．

■自力でコンパイルする方法も発見

　ソースからコンパイルする方法もありました．参考までに．つーか，こっちの方が良いな．今から切り替えてくる．なお，CDTについても少し設定が変わるのでご紹介．

　MinGW用SDL_mixerのバイナリは自力でコンパイルするしかないので，この方がいいかもですよ，うん．

■MSYSで自分でコンパイルする際のCDT設定

　上のサイトの通りにコンパイルしてください．なお，上のファイルの通りにしてlocal\binにインストールしちゃった人は，パスを通してください．私はしちゃいました．コンパイルしなおそうかな．CDTの設定は，次の通りです．

・コンパイラーの「その他」→「その他のフラグ」で「`sdl-config –cflags`」を追加．

・リンカーの「その他」→「リンカーフラグ」で「`sdl-config –cflags`」を追加．

ツールが自動で設定を吐いてくれるので，ずいぶんと楽にはなってますね．これで安心だ．

ポーションの蓋を集めるには何本必要？

Posted on 2006/03/21 by Kaede Fujisaki

　というわけで，前回の「ポーションの蓋を全種類集めるには何本買えばいいかの期待値を求めよ」の答えです．

　今のところ出ている答えはJさんの13～14本．

■まず確認すること

　まず基本的な事として，「１回につき確率nで手に入る物を手に入れるまでの期待値は1/n回」です．

　そうですよね？6本あってある１本（たとえばパッケージに書いてある奴）がほしい場合，買わなければいけない期待値は6本ですよね？

　証明は・・・面倒なので良いですか？（ぇ

■それでは本番

　まず，6本あるうちの，6本どれでも良いので欲しいです．手に入る確率は6/6．手に入れるまでの期待値は6/6本．

　次に，6本あるうちの，手に入れた1本を除く5本のうちのどれかが欲しいです．手に入る確率は5/6．期待値は6/5本．

（中略）

　次に，6本あるうちの，手に入れた4本を除く2本のうちのどれかが欲しいです．手に入る確率は2/6．期待値は6/2本．

　次に，6本あるうちの，手に入れた5本を除く1本が欲しいです．手に入る確率は1/6．期待値は6/1本．

　よって，次のような式になります．本数をD(=Drink)とすると

D = 6/6 + 6/ 5 + 6/4 ・・・ 6/1

= 6 * ( 1/6 + 1/5 + 1/ 4　・・・ 1/1)

= 14.7本

　あとJさん，惜しかったですｗ

　なお，箱買いもチマチマ貧乏くさく買うのも数学的に同じです．

※3/22追記

　レイスタさんの情報より，箱買いするともれなく蓋が6種類２セット，カードがかぶらないように12種類付くらしいです．それだと・・・答えは箱のうちの右半分か左半分6本を買い占めれば蓋に関しては全コンプできるみたいですｗ

■計算ツールを作りました．

　計算ツールです．一発で計算できます．使用は自己責任で．

計算ツールをダウンロードする

　なお，正確に分数の形で計算しているので，37個以上で計算させるのは・・・マシンパワーに余程の自信があるならどうぞ．

　なんでそんなにかかるのかって？足し算ごとに毎回約分してる†1ので，最大公約数を見つけるのに時間がかかってるんです．37回目では，887820718293231097と8992153642237365600の最大公約数を求めるのに凄まじい時間がかかります。。。

　かといって約分をしないためにBigIntegerを使っても・・・多分37回目ぐらいには凄いケタになってて，結局時間がかかりそうなので・・・．

　まあ，小数を使って近似を取るのが一番なんですが，それでは負けな気がしまして（何

　さっきのも一発で計算できます．

　カードの方も計算させて見ました．

　これはひどい．

//あれ・・・？ソフト内の文章がいろいろと変ですね．必要なのは個数ですよね．

//・・・記念に放置！（何

■カードと蓋をどっちも集めるには？

　とりあえずカード集めておけば余程運が悪くない限り集まってますけどねｗ

　まず，6本27枚あるうちの，6本27本どれでも良いので欲しいです．手に入る確率は　6*27/6*27　．手に入れるまでの期待値は　6*27/6*27　本．

　次に，6本27枚あるうちの，5本26本どれかが欲しいです．どちらかが手に入る確率は　1-(5*26/5*27)　．手に入れるまでの期待値は　(6*27)/(6*27-5*26)　本．

　ここまでは分かったんですが・・・この先はもしや蓋が手に入った場合とビンが手に入った場合で場合分けしなくてはいけないのでは・・・？

　場合分けだとすると，調べるのは・・・2^27 = 134217728通りも調べなきゃ・・・．

　ここでスタックオーバーフローした†2ので強制終了させておきます＿|￣|○

　ただ，105.069本と大差ないとは思います．

　だれかうまい方法を教えてください・・・．

■ためしに1億人に買わせてみた

ランダムで買わせて見てどうなるかチェック！（ｗ

人数を多くすればするほど値が正確になっていきますね．

/*ShokuganがShakugan（灼眼）に見えたのはここだけの秘密だ*/


>java Shokugan 1
合計：12個
人数：1人
平均：12.0個


>java Shokugan 10
合計：136個
人数：10人
平均：13.6個


>java Shokugan 100
合計：1323個
人数：100人
平均：13.23個


>java Shokugan 1000
合計：14518個
人数：1000人
平均：14.518個


>java Shokugan 10000†3
合計：146880個
人数：10000人
平均：14.688個


>java Shokugan 100000†4
合計：1465555個
人数：100000人
平均：14.65555個


>java Shokugan 1000000†5
合計：14715499個
人数：1000000人
平均：14.715499個


>java Shokugan 10000000†6
合計：147033596個
人数：10000000人
平均：14.7033596個


>java Shokugan 100000000†7
合計：1469669029個
人数：100000000人
平均：14.69669029個

誤差，0.00330971．こんな話もあったし，これぐらいが限界かなぁ．

//まあ，リンク先の話は・・・ずいぶん前のだとは思うけど．

ちなみにソースは


/*
 * 作成日: 2006/03/21
 *
 */
public class Shokugan {
	public static final int[] STATE = {1,2,4,8,16,32};
	static java.util.Random rnd=new java.util.Random();
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		long count = 0;
		long people = Integer.parseInt(args[0]);
		for(int i=0;i < people;i++){
			count += buy();
		}
		double average = (double)count / people;
		System.out.println("合計："+count+"個");
		System.out.println("人数："+people+"人");
		System.out.println("平均："+average+"個");
	}
	public static long buy(){
		long turn = 0;
		long state = 0;
		while(state != 63){
			state |= STATE[rnd.nextInt(STATE.length)];
			turn ++;
		}
		return turn;
	}
}

です．(一部隠れてるので，コピーして貼り付けてください．)

//Eclipse便利だよなぁ・・・．

†1: そうじゃないとすぐにLongのケタが溢れる
†2: 実際，27回もジャンプしてスタック領域足りるのか？
†3: 1万人
†4: 10万人
†5: 100万人
†6: 1000万人
†7: 1億人

テスト終わった･･･^^;

Posted on 2006/03/05 by Kaede Fujisaki

　ふう，終わりました．

　テスト直前に風邪をひいてしまいました．どう考えてもタイミング良過ぎなので，~~呪札とか魔法陣とか~~探しましたが見つかりませんでした．やはり一般人に分からないように細工がしてあるのでしょうか（結論違

　そういえばいろいろありましたね．ネギま！第二期（どうみても絵がぱにぽに）とか可愛そうな民主党議員（民主党にはコンピュータに詳しい人間が一人もいないらしい）とかいろいろ．

■カブロボ

　そういえばカブロボですが・・・．なっちん，この価格で安定している上，昭和シェルの買いすぎ（あと売らなさ杉）のお陰で硬直状態ですね．

　リセットでも掛けて３月末までの短期決戦を仕掛けようかとにらんでます．

とりあえずはこれだけ．もうすぐ今年度も終わりですね・・・また学年上がるのかぁ・・・はぁ・・・．

もう年取りたくないなぁ・・・・．

カブロボ・ウォッチング

Posted on 2006/02/01 by Kaede Fujisaki

カブロボ・コンテスト KabuRobo

6号さん二位おめでとうございます（笑

　一時期10位以下に転落していましたが，見事にトップグループに．

　賞金をもらうために名前を変えられたようなので，もうすぐトップページの表示も変わっちゃいますねｗ

コンテスト途中経過 | カブロボ・コンテスト

　なっちんも順調にがんばっています．現在，総資産で209位．

　当初は買うだけであとは売ろうとしない，というパターンかと思いましたけど，結構売り買いも激しく行っているようです．バージョンアップ見送り．まあ，不安な部分†1もあるんですが，もうちょっと様子見・・・かも（ぉ

†1: 売り買いをともに50万円単位でしているので，50万円でギリギリ一単位買えた銘柄は，そこまで下がらないと売れないｗ

月と燃素と、ひと匙の砂糖

Category Archives: プログラミング