手数の積の平均からの棋譜数予想


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

平均手数からの棋譜数予想と同じようにサラッと考案された。(>>224)
当初この二つはニュアンス的なものから同じようなものと考えられた。
しかし決定的な違いが説明され、「平均手数からの棋譜数予想」の大きな短所が
「手数の積の平均からの棋譜数予測」にはなく、
それ故後者のほうが信頼できる値であることが周知となった。

現在棋譜数の概算値はこれが主流となっている。

姉妹話題→平均手数からの棋譜数予想(初めての方はこっちから読みましょう)



224 名無しさん@5周年 ageだろ 2005/10/11(火) 23:40:05 
ちょこっとプログラムを作ってオセロの概数出してみたので報告。>>167=173とは違う方針2種類で。 
データは同様に「ランダムに配置して置けるマス数を数える」を10000試合行った。 
取り合えず今回は結果だけ。詳細なデータは纏めるまで待って。

1) 
1手ずつの相加平均を出して掛け合わせる。1手目は4、2手目は3,3手目は4.67…という感じ。 
60手目の平均選択肢数が0.9056だったのでここまで掛け合わせた結果、1.21e+52 通りくらい。 

2) 
選択肢の数ということで、1回1回のシミュレーションで1)のように掛け合わせた結果を出す。 
選択肢の数なのでパスの場合も1通りと数える。で、その10000試合分平均を取るわけだが… 
A.普通に相加平均取ってみた。1.8e+54 通り。 
B.どうせなら最後まで掛け算だろ、相乗平均。1.0e+51通り。

さて、どれが近いのやら

224
1)は平均手数の積
2)は手数の積の平均である

352 284 sage 2006/03/05(日) 13:48:45 
「平均手数の積」の問題点を整理してみます。 
(1)ランダム棋譜の発生確率が全て同じではない事>>348 
(2)全棋譜の平均手数を出しても誤差があること>>Wiki5手検索2 
>>333-335の指摘での誤差は、この両方が入ってると思われます。他にもあるかも。

(1)の話しですね。  
多分、乱数によらず過去の棋譜を集めてもこの問題の解決にはならないと思われます。 
むしろこのあたりを考慮したプログラムを組むか、ですね。 
その着手以後の手数を数えて乱数発生確率を変えるか、ですが全検索と同じことになってしまいます。 
せめて数手先までの着手可能数で乱数発生確率を使うかですかね。 

(2)の話しですね。 
>5手検索2に書いたけど、ランダム棋譜からの推測の正確性を計るという意味だと 
>5手検索の方が良かったかもね。 
いえ、ランダム棋譜からの推測だからこそ5手検索2で良いと思いますよ。

なるほど5手目着手可能数の誤差が一般平均1.129(12.9%)、幾何平均1.0570(5.7%)。 
一般平均よりは誤差が少なくなってますね。 

ただ千回も試行すれば相乗の数値がオーバーフローします。これはプログラミングの問題? 

353 293 sage 2006/03/05(日) 14:56:22 
>>352 
解釈ありがとうございます。私は考えるのが苦手なもんで。

プログラム中で平均とっているなら、log(分岐数)の総和を取って 
1/n掛けた後にexp(その結果)でいかがでしょ? 
単純にかけ算してたら6手全探索でもオーバーフロー起こしましたし。 

354 284 sage 2006/03/05(日) 20:13:39 
>>352 の続き、5手検索2で調和平均もやってみました。 
5手目までは良い感じですが6手目で0.8923(-10.8%) 
うーむ・・・ 

>>353 
>log(分岐数)の総和を取って1/n掛けた後にexp(その結果) 
エクセルで試したんですが、答えが合いません。。 
logとかexpが、あんまり解ってないので・・・orz

355 293 sage 2006/03/05(日) 20:53:39 
>>354 
説明不足で申し訳ない。エクセルでやるならlogはln()を使って下さい。
Cのプログラム中ならlog()でOKです。 
それ使ってやった結果を、普通に掛けてn上根取った結果(≦5手目)と比較したら 
1手目:4.88498E-15 
2手目:5.32907E-15 
3手目:1.77636E-15 
4手目:8.88178E-16 
5手目:8.88178E-16 
と、十分小さいと思われますんで。

356 293 sage 2006/03/05(日) 21:15:25 
更に説明不足。↑の数は「普通に掛けて…」と「log()の総和を…」とで出た結果の差の絶対値

361 284 sage 2006/03/06(月) 13:18:36 
>>355-356 
解説ありがとう。エクセルで結果が同一となるのを確認できました。 
プログラムのほうは、まだですがその内やってみます。

「平均手数の積」ではなく「ある棋譜の手数の積の平均」のほうが、 
実際の数に近いのではないか、と思い始めてた所です。

363 293 sage 2006/03/06(月) 15:33:23 
昔のプログラムで、今その結果が残ってる訳じゃないんだけど、 
>>224(これ、私です)の2)の方針ですかね?

365 284 sage 2006/03/06(月) 20:57:30 
>>363 
224の2)はまさにそうですね。既出でしたか。 

>>364 
ある棋譜の発生確率=1/(手数の積)と置くと棋譜数は結果の相加平均で良いと思われます。 
以下、その理由です。

全棋譜数がmとして各々の(手数の積)をA1~Amと置きます。 
ランダムに発生した棋譜がA1である確率は1/A1。 
試行回数をXと置くとA1の発生回数はX*(1/A1)。 
またA1が発生した(手数の積)のトータルはA1*(X/A1)=1*X。 
A2~Amまでも同様なことが言えるので総トータルはm*X 
よって全棋譜数m=総トータル/X(相加平均)

いかがでしょう? >>362の画像を参考にさせていただきました。 
ただしサンプルをとる場合は、選択肢の分岐を一様な乱数にしたほうがいいでしょうね。 

棋譜のツリーの形は5手検索が参考にならないでしょうか? 

367 よんけた ◆Tl2oC4lIZ2 sage 2006/03/07(火) 19:59:33 
>>356 
全く同じことを書かせて下さい。

値Aにその発生確率をかけ、それらをすべて足したものを Aex とします。 
この Aex というのは、手数の積の期待値です。 
(exはexpectationからとったもので、正しい表記ではないとおもいます) 

Aex = 
A1*(1/A1) + A2*(1/A2) + A2*(1/A2) + ・・・ + Am*(1/Am) = m 

です。つまり Aex は 棋譜数m そのものです。 

一回のランダム選棋譜で選出される棋譜の手数の期待値の和は、 Aex です。 
二回のランダム選棋譜で選出される棋譜の手数の期待値の和は、 2*Aex です。 
X回のランダム選棋譜で選出される棋譜の手数の期待値の和は、 X*Aex です。

X回のランダム選棋譜で選出せれる棋譜の手数の期待値の和とは、総トータルのことです。 
つまり、 
 総トータル/X = m 

368 よんけた ◆Tl2oC4lIZ2 sage 2006/03/07(火) 20:06:40 
>>365 
でもこれでは誤差の説明がつかなくなります。 
見直すべきところは 
手数の積A1の発生確率が (1/A1) であるといったとこでしょうか。。

369 284 sage 2006/03/08(水) 08:05:37 
>>368 
>>348での誤差の話しは「平均手数の積」の時の話しです。 
今回「手数の積」の相加平均を採れば誤差が無くなるのではないか、ということです。 
#もちろん乱数発生による誤差は残りますが。 
100万回で試した結果をWiki「メモ05」に入れておきました。 
全検索で出ている14手目まで、かなり良い結果になってると思います。 
最終(60手目)結果が6.5E+54と、>>224とは少し違いますね。。

293氏に折角、相乗平均の方法を教えて貰ったのに使わなくなってしまいました。すみません。
370 293 sage 2006/03/08(水) 09:31:11 
>>365 >>367 にある相加平均を取る証明はその通りだと思います。 
考えなく相乗平均とか言い出して申し訳ないです。

敢えて100万回程度(10の54乗からすれば「たかが」程度)のシミュレーションで 
誤差が出そうな点を挙げれば

>ランダムに発生した棋譜がA1である確率は1/A1。 
>試行回数をXと置くとA1の発生回数はX*(1/A1)。

この 1/A1 が本来 1e-50 程度のはずなので X*(1/A1) も 1e-40 を上回る棋譜が 
そうそうあるとは思えません。それが 1 (ものによっては2以上) まで格上げ 
されることによる誤差が無視できない程度までに大きいということでしょうか。

>>224 との差異もその辺りが原因かと思います。本当は時系列でグラフを出すなり 
定期的に中間結果をアウトプットして平均値の収束状況を見る必要があると思いますが。

まずは一定回数毎に平均値を出して、グラフプロットしてみます。 

371 よんけた ◆Tl2oC4lIZ2 sage 2006/03/08(水) 11:32:46 
>>369>>370 
毎回後進的レスすまんす。 
やとわかった! 
平均手数の積では、>>352の(1),(2)が問題となってくんですが、 
手数の積の平均は、>>352の(1)が消えて(2)みたいな計算誤差・理論と事象の
確率誤差だけが問題となるんですね。

期待値という言葉をつかって平均手数の積を正確に説明するのはややこしいですが。。

僕はこの二つほとんど同じ結果が得られるものだと思ってました。 
全然ちがうんですね。

373 293 sage 2006/03/08(水) 22:02:36 
10時間をかけて取った6億回実験分の平均推移を表すグラフやデータを
Wikiにうpしたいんですが、どうしたらいいですかね?>よんけた 
376 284 sage 2006/03/09(木) 12:59:58 
>>371 
後進的なんてとんでもないです。疑問点はどんどん言ってください。 
それに対してまた、色々考えることが大切ですから。 
その結果「手数(分岐数)の積の平均」を思いつくきっかけにもなっています。

>>373 
Wiki見ました。3億6千万回ですか!しかも10時間で!すばらしいです。 
私は100万回で40分掛かったのにw(私のプログラミングが下手ですね) 
概算値としての6.449E+54は1つの答えですね。

現在オセロゲーム全棋譜数の予測値は、6.449E+54となっている。
2chスレッド内公式データ
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。
添付ファイル