最良の選択肢は？

[管理人]

　
　
今、ポーカーをする時、コンピュータがどんな行動を取れば一番強くなるか考えていますが、うまく計算出来ません・・。

数学的に確率を計算するのが一番なのでしょうけど、この場合、相手のカードや他ものすごい様々な場合わけを計算する必要があり、手計算出来ないので、
実際にシミュレートしてみて、確率を出そうと思いました。
しかしシミュレート結果に不思議な値が出たのでちょっとお聞きしたいと思い、投稿しました。

シミュレートの対象は以下のような状況です。

ポーカーを現在しているとします。
今配られた５枚のカード、何の役もありません。 このとき、
・１枚交換した方がいいのか？
・２枚交換した方がいいのか？
・３枚交換した方がいいのか？
・４枚交換した方がいいのか？
・５枚交換した方がいいのか？
一体どのような行動をしたら一番役になりやすいのか、調べる為シミュレートを行います。

とりあえず、フラッシュになりかけているときは、行動を変える・・などやっていると条件分岐がきりないので、
「ワンペアじゃないとき、ワンペアになる確率」と限定してシミュレートを行います。
添付に書いたプログラムは手札にワンペアがあったら即「役あり」と判定しているので、ワンペア以外にもツーペアやフルハウスなどになっているかもしれませんが、それはよしとします。

すると面白い結果になりました。
100万回シミュレートを行って確率を出しました。

・手札を山に返した時の結果
1枚の交換　[24.7632％]
2枚の交換　[38.2780％]
3枚の交換　[45.4380％]
4枚の交換　[48.8022％]
5枚の交換　[49.2094％]

・手札を山に返さなかったときの結果
1枚の交換　[25.5863％]
2枚の交換　[39.9794％]
3枚の交換　[47.5972％]
4枚の交換　[50.2623％]
5枚の交換　[48.8712％]

　
　
このようになりました。
手札を山に返した時、つまり、山に返したカードを引いてしまうかもしれないときと、そうではないときで
何枚交換すればよいのか変わってしまいます。

公式ルールは後者なので、4枚の交換がベストということになるのですが、何故4枚になるのか腑に落ちません・・。
シミュレートのしかたが間違っているんでしょうか？

みなさんご意見お聞かせいただければ光栄ですm(_ _)m

p.s.
ちなみに、「手札を山に返す」時はそのまま。
「手札を山に返さない」時はmain関数内の、「hand_ini関数」を呼んでいる行をコメントアウトすれば出来ます。

[管理人]

先ほどのプログラムは、毎回自分が最初に交換を行っているので、今度は、先に誰かが交換することを想定して場合わけで結果を出しています。
表にしたほうが見やすいでしょうけど、ちょっと時間がないので、こうしました。

どんな状況でもやはり4枚がベストのようです。

実行結果
先に誰かが0枚交換した場合
1枚の交換　[25.5410％]
2枚の交換　[39.9990％]
3枚の交換　[47.5020％]
4枚の交換　[50.5340％]
5枚の交換　[49.0110％]

先に誰かが1枚交換した場合
1枚の交換　[25.3630％]
2枚の交換　[39.9610％]
3枚の交換　[47.5550％]
4枚の交換　[50.2480％]
5枚の交換　[49.0590％]

先に誰かが2枚交換した場合
1枚の交換　[25.6990％]
2枚の交換　[40.1650％]
3枚の交換　[47.6750％]
4枚の交換　[50.1120％]
5枚の交換　[48.8300％]

先に誰かが3枚交換した場合
1枚の交換　[25.6230％]
2枚の交換　[39.9470％]
3枚の交換　[47.5820％]
4枚の交換　[50.4380％]
5枚の交換　[48.8660％]

先に誰かが4枚交換した場合
1枚の交換　[25.5140％]
2枚の交換　[39.8960％]
3枚の交換　[47.4030％]
4枚の交換　[50.1650％]
5枚の交換　[49.0540％]

先に誰かが5枚交換した場合
1枚の交換　[25.4450％]
2枚の交換　[39.9640％]
3枚の交換　[47.7610％]
4枚の交換　[50.2050％]
5枚の交換　[48.7480％]

先に誰かが6枚交換した場合
1枚の交換　[25.6650％]
2枚の交換　[39.7080％]
3枚の交換　[47.7760％]
4枚の交換　[50.3130％]
5枚の交換　[48.9960％]

先に誰かが7枚交換した場合
1枚の交換　[25.2350％]
2枚の交換　[39.9360％]
3枚の交換　[47.5260％]
4枚の交換　[50.2080％]
5枚の交換　[48.9690％]

先に誰かが8枚交換した場合
1枚の交換　[25.6600％]
2枚の交換　[40.2880％]
3枚の交換　[47.2740％]
4枚の交換　[50.4220％]
5枚の交換　[49.1440％]

先に誰かが9枚交換した場合
1枚の交換　[25.5760％]
2枚の交換　[39.7840％]
3枚の交換　[47.4700％]
4枚の交換　[50.6480％]
5枚の交換　[48.8950％]

先に誰かが10枚交換した場合
1枚の交換　[25.5890％]
2枚の交換　[39.9460％]
3枚の交換　[47.3880％]
4枚の交換　[50.1780％]
5枚の交換　[48.9640％]

先に誰かが11枚交換した場合
1枚の交換　[25.7240％]
2枚の交換　[39.7460％]
3枚の交換　[47.3830％]
4枚の交換　[50.4470％]
5枚の交換　[49.2090％]

先に誰かが12枚交換した場合
1枚の交換　[25.7430％]
2枚の交換　[39.9830％]
3枚の交換　[47.5670％]
4枚の交換　[50.3420％]
5枚の交換　[48.8880％]

先に誰かが13枚交換した場合
1枚の交換　[25.4380％]
2枚の交換　[40.0610％]
3枚の交換　[47.5610％]
4枚の交換　[50.1380％]
5枚の交換　[48.7950％]

先に誰かが14枚交換した場合
1枚の交換　[25.4240％]
2枚の交換　[40.1110％]
3枚の交換　[47.8790％]
4枚の交換　[50.2420％]
5枚の交換　[49.1760％]

先に誰かが15枚交換した場合
1枚の交換　[25.4270％]
2枚の交換　[39.8580％]
3枚の交換　[47.4580％]
4枚の交換　[50.2310％]
5枚の交換　[48.9460％]

[Justy]

＞相手のカードや他ものすごい様々な場合わけを計算する必要があり
　相手のカードのカード覗いて CPUが思考したら、まずくないですか？
　あ、ひょっとしてスタッド系のポーカーですか？
　それとも覗いてもＯＫでとにかく最強を目指していますか？


＞シミュレートのしかたが間違っているんでしょうか
　ざっと見た感じ、特に問題ないように見えます。
（細かいところで幾つかありますが、大勢に影響しないものばかりです）

　確率の細かい計算は他の方に譲るとして（笑）、
何か確率計算上の何かバランスの分岐点がそのあたりにあるんでしょうかね。

[管理人]

相手のカードを覗いてCPUが思考したらまずいです。
しかし、どの場合でどのような確率となるのかは知っていないと選択肢として選ばせる事が出来ないので、調べたかったのです・・。

ルールはいたって標準です。
普通にカードを５枚配って人には見せず、１回交換ののち、勝敗判定です。

＞（細かいところで幾つかありますが、大勢に影響しないものばかりです）

どの辺がおかしかったでしょうか？
厳密な所まで間違いがないようにしたいので、よければ教えてください＞＜

教授など、べてらんのプログラマや数学の教授に聞きに行きましたけど、結局はっきりした答えは返って来ませんでした。
ですので、ベテランのポーカーマニアに聞いてみました。
何も役が無かった時は、４枚交換し、「1枚は役と成った時、一番強いカードを残す」ということでした。
そして、確率は40%以上だということだったので、シミュレート結果は正しそうでした。

[Justy]

＞しかし、どの場合でどのような確率となるのかは知っていないと
＞選択肢として選ばせる事が出来ないので、調べたかったのです・・
　なるほど。
　難しそうですね。


＞どの辺がおかしかったでしょうか？
＞厳密な所まで間違いがないようにしたいので、よければ教えてください＞＜
　どれも現状ではそんなにたいしたことではないのですが

[color=#d0d0ff" face="sans-serif]・　rand()を２つ組にして使う[/color]
　この話はrand()内で線形合同法が使われている場合に限ります。

　rand()を１個ずつ使うときは問題はありません。
　が、複数の組として利用すると質が悪くなります。

　x = rand();
　y = rand();
　
　このように rand()を２回使って xと yの値を出した場合、使用者が期待する
２つの値のとりうる組み合わせは RAND_MAX * RAND_MAX通りです。
　が、上記の場合それだけの組み合わせを確保できません。

　今回は %を使って相当小さく丸めているのでほとんど影響はないのですが、
可能なら例えば

int t = rand() % (4 * 13);
x = t / 13;
y = t % 13;

　のように複数の組で使用しないようにするのが理想的です。

　http://ja.wikipedia.org/wiki/%E3%83%A1% ... 9%E3%82%BFのようなある程度の複数の組でも質が保証されているものや、
http://www.kmonos.net/alang/boost/classes/random.htmlのようなオブジェクト毎に異なるシードを保持できるものを
使うとそういう問題は起こりません。



[color=#d0d0ff" face="sans-serif]・　手札への配り方[/color]
　現在の「誰かがそのカードを所持していたら配布を有効にせず戻る」ようなやり方ですと
空きカードが少なくなったとき著しくパフォーマンスが低下します。
　特に上の乱数問題と絡んで最悪無限ループに近い状態になったりします。

　ゲームの最初の段階で山札データを用意して、そこから手札に配るようにすれば、
一定時間で配布を完了することができると思います。



＞教授など、べてらんのプログラマや数学の教授に聞きに行きましたけど
　ポーカーの確率計算は最初に配られた段階でのものはよく見掛けますが、
その後の交換までとなるとあまり見ないですね。


＞「1枚は役と成った時、一番強いカードを残す」ということでした。
　あー、私もそれに近いことをポーカーでよくやります。
　１０よりも大きい数字だった場合のみそれを残して残りを交換。
　１０未満だったら全部交換ってかんじで。

[管理人]

詳しくありがとうございます。
しかしまだ理解できず、

＞２つの値のとりうる組み合わせは RAND_MAX * RAND_MAX通りです。
＞が、上記の場合それだけの組み合わせを確保できません。

という意味がわかりません。
VC++において、randの値は

static long x=S;
int rand() { x=x*A+C; return(int)(x>>16)&32767; }
void srand(unsigned s) { x=s; if (F) rand(); }
A=214013, C=2531011, F=0, S=1。

によって生成されているんですよね？
連続で同じ値が出ることがないか調べてみたところ、100万回中30回位でるようです・・。
妥当な数値かなと思います。
うぅん、何故よくないのかわかりません・・。


後、rand関数について疑問に思ったのが、Linuxでプログラムを書いたときは、RAND_MAXが2の31乗だったのですが、ウィンドウズでは2の15乗ですよね。
コンパイラによるこういう違いって結構多いんですか？
ちょくちょくあったらすんなり移植できないですね・・。

[管理人]

紹介いただいたSFMTを用いて改めてシミュレートしてみました。
randとの比較を以下に示します。

rand()      NextMt()
1枚の交換　[25.5863％] [25.6027％]
2枚の交換　[39.9794％] [40.0063％]
3枚の交換　[47.5972％] [47.5172％]
4枚の交換　[50.2623％] [50.1816％]
5枚の交換　[48.8712％] [48.9857％]

　
　
このような結果になりました。
SFMTは予測可能ではあれども、かなり良質な乱数のようですね。
今後シミュレートや良質な乱数が必要な時はこれを利用したいと思います。

余談ですが・・・、
Justyさん、最終ランクアップおめでとうございますｗ
といっても先ほど下がってしまったようですが＾＾；
HP開設当時から本当にお世話になっています。
これからもよろしくお願いします。
次は100万ポイント目指して下さいm(_ _)m

[YuO]

本論部分はいろいろと考えることが多そうなのでそうでない部分について。


> ＞２つの値のとりうる組み合わせは RAND_MAX * RAND_MAX通りです。

正確には，(RAND_MAX + 1) * (RAND_MAX + 1)通りですね。
# rand()の戻り値は[0, RAND_MAX]なので。

> ＞が、上記の場合それだけの組み合わせを確保できません。
> という意味がわかりません。

非常に品質の悪いrandの実装の場合，あるrand()の戻り値が決定すると，次の戻り値は一意に決まったりします。
良い乱数、悪い乱数 : http://www001.upp.so-net.ne.jp/isaku/rand.html


> 後、rand関数について疑問に思ったのが、Linuxでプログラムを書いたときは、RAND_MAXが2の31乗だったのですが、ウィンドウズでは2の15乗ですよね。
> コンパイラによるこういう違いって結構多いんですか？
> ちょくちょくあったらすんなり移植できないですね・・。

RAND_MAXは最低32767であることは規格で定められていますが，実装定義の事項とされています。
変数の幅が実装定義なのと同じです。
# rand()の実装にMT使っていても規格違反ではないですし。

[Justy]

＞うぅん、何故よくないのかわかりません

　VC2003/2005と環境を特定してしまえば、たしかに VCはアルゴリズムが改善されいて
上位ビットから使うようになっているのでほとんど問題にはなりませんが、
他の環境では保証できません。
　それに改善後であってもやはり完全ではありません。

うえぽんSW局
http://shinshu.fm/MHz/14.30/2006/12/17/

　まぁ、そうはいっても、今回のケースではまず問題にはならないので、
（ここまでひっぱいといて何ですが）気にしなくてもいいのかもしれません。


＞コンパイラによるこういう違いって結構多いんですか？
　それはもう山のようにありますよ。
　環境（ＯＳとか）の違い、コンパイラの制限からの違い、etc...
　規格書に載って規定されている項目ですら、コンパイラベンダーが守ってなくて
挙動が異なることもありますしね。


＞ちょくちょくあったらすんなり移植できないですね・・。
　同じ VisualStudioでもバージョン違いやコンパイラの設定でビルドできなくなりますからねぇ。



＞Justyさん、最終ランクアップおめでとうございますｗ

　ありがとうございます。


＞といっても先ほど下がってしまったようですが
　あ、ほんとだ（ｗ



＠ YuOさん
＞正確には，(RAND_MAX + 1) * (RAND_MAX + 1)通りですね。
　おー、そうですね、失礼しました。

[Justy]

＞HP開設当時から本当にお世話になっています
　あー、あのころ開設時だったんですか。
　前からあったのかなぁ、と思ってました。

＞次は100万ポイント目指して下さいm(_ _)m
　なかなか厳しい数字ですが、頑張ります　<(_ _)>

[管理人]

なるほど、確かにLinuxで乱数発生させたとき、偶数と奇数が交互に出てきた時にはびっくりしました。
色んな環境を考慮する事も必要ですね。

なんだか最高ランクになると目指すところがなくなってしまい、つまんないですねｗ
まぁこれ以上ランク作っても結局自分達だけのためのランクになってしまいそうなので、この辺のキリのいい数字でやめときます＾＾；