「Transposition」の編集履歴（バックアップ）一覧はこちら
「Transposition」(2009/08/20 (木) 00:01:12) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
*Transposition
違う手順で同じとなる局面。
例）F5D6C3D3C4とF5D6C4D3C3
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋●＋＋＋＋＋ ＋＋●○＋＋＋＋ ＋＋●○＋＋＋＋
＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋●●＋＋＋→＋＋＋○●＋＋＋→＋＋●●●＋＋＋
＋＋＋●○＋＋＋ ＋＋＋●●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋●○＋＋＋＋
＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋●●●＋＋＋→＋＋●○●＋＋＋→＋＋●●●＋＋＋
＋＋＋●○＋＋＋ ＋＋＋●●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
このように３手目以降の置石の位置が違うが、５手目で同じ局面となっている。
直感以上にかなり存在する模様。
***どのくらいの割合で存在するのか？
あくまで予測だが[[棋譜数・局面数・盤面数>http://www9.atwiki.jp/othello?cmd=upload&act=open&pageid=39&file=kihu_banmen_kyokumen.jpeg]]のグラフを見て欲しい。
このグラフから判るように６０手目、棋譜数は局面数の
10000000000000000000000000000000倍（３０ケタ）以上存在している。
ゆえに平均的に一つの６０手目局面は１0＾30通り以上の棋譜で表現できることとなる。
上の例では
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●○＋＋＋＋
＋＋●●●＋＋＋
＋＋＋○●●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
が２通りの棋譜で表現できている
このグラフでは
○○○○○○●●
○○○●○○○●
○○●○●○○●
○○●●○○●●
○○●○●○●●
○●○○●●○●
○○○○○○●●
○○●●●●●●
みたいな任意の６０手目の局面が10000000000000000000000000000000通り
の棋譜で表現できることを示している。
つまり後半常に何重のTranspositionが起きていると考えられる。
親話題→[[終局局面数]]
親話題→[[棋譜数のカウント]]
姉妹話題→[[枝刈り]]
----
260 ：256：2006/02/20(月) 07:59:34
プログラムを作って実際の数を調べてみた。
1・・・4
2・・・12
3・・・56
4・・・244
5・・・1396
6・・・8200
7・・・55092
8・・・390216
9・・・3005320
10・・・24571192
24571192*33*33*...*33*32*...*3*2*1=1.39e+70
急ごしらえなのであんまり速くないからとりあえず10手まで。
あと、まだバグがあるかも知れないから誰か検証お願い。
274 ：256：2006/02/22(水) 03:27:33
違う手順で同じ局面になる事があるんだけど、
この扱いはどうすればいいかな？(transposition)
例えば次のような局面。
F5D6C3D3C4とF5D6C4D3C3
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●○＋＋＋＋
＋＋●●●＋＋＋
＋＋＋○●●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
F5F6E6F4E3とF5F4E3F6E6
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋●＋＋＋
＋＋＋○●○＋＋
＋＋＋●●○＋＋
＋＋＋＋●○＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
F5F6E6F4G5D6E7G6とF5F6E6F4G5D6E7F7
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋○○○＋＋ ＋＋＋○○○＋＋
＋＋＋○○○●＋ ＋＋＋○○○●＋
＋＋＋○○○○＋ ＋＋＋○○○＋＋
＋＋＋＋●＋＋＋ ＋＋＋＋●○＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
>>260ではこれらを別物としてカウントしてます。
275 ：名無しさん＠５周年：2006/02/22(水) 10:30:49
あー、あれですよ。「オセロの試合結果」というものをどう取るか次第。
1）勝ち・負け・引き分け派 → 3通りということでFinal answer
2）決着時の盤面が何種類あるか派 → 回転・対称な盤面は1つに
3）棋譜？が何通りあり得るか派 → 全部別物ということで
プログラムとか組みやすいのは3）だろうね。自分は2）派。
282 ：256：2006/02/23(木) 07:56:46
>>275
>>260のプログラムを作るときに2)で数えるか3)で数えるか迷いましたが、
作るのが簡単な3)でやってみました。
プログラムの改良にと思ってTransposition Tableをハッシュ法で実装してみたら、
ごく一部でハッシュ値の衝突（全く違う局面から同じハッシュ値が生成）が起きたようで、
値が少し違う結果が出てきてしまいました。（速くはなりましたが）
もうちょっとよく考えてみます。
違う手順で同じとなる局面。
例）F5D6C3D3C4とF5D6C4D3C3
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋●＋＋＋＋＋ ＋＋●○＋＋＋＋ ＋＋●○＋＋＋＋
＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋●●＋＋＋→＋＋＋○●＋＋＋→＋＋●●●＋＋＋
＋＋＋●○＋＋＋ ＋＋＋●●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋●○＋＋＋＋
＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋●●●＋＋＋→＋＋●○●＋＋＋→＋＋●●●＋＋＋
＋＋＋●○＋＋＋ ＋＋＋●●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋ ＋＋＋○●●＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋ ＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
このように３手目以降の置石の位置が違うが、５手目で同じ局面となっている。
直感以上にかなり存在する模様。
***どのくらいの割合で存在するのか？
あくまで予測だが[[棋譜数・局面数・盤面数>http://www9.atwiki.jp/othello?cmd=upload&act=open&pageid=39&file=kihu_banmen_kyokumen.jpeg]]のグラフを見て欲しい。
このグラフから判るように６０手目、棋譜数は局面数の
10000000000000000000000000000000倍（３０ケタ）以上存在している。
ゆえに平均的に一つの６０手目局面は１0＾30通り以上の棋譜で表現できることとなる。
上の例では
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●○＋＋＋＋
＋＋●●●＋＋＋
＋＋＋○●●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
が２通りの棋譜で表現できている
このグラフでは
○○○○○○●●
○○○●○○○●
○○●○●○○●
○○●●○○●●
○○●○●○●●
○●○○●●○●
○○○○○○●●
○○●●●●●●
みたいな任意の６０手目の局面が10000000000000000000000000000000通り
の棋譜で表現できることを示している。
つまり後半常に何重のTranspositionが起きていると考えられる。
親話題→[[終局局面数]]
親話題→[[棋譜数のカウント]]
姉妹話題→[[枝刈り]]
----
260 ：256：2006/02/20(月) 07:59:34
プログラムを作って実際の数を調べてみた。
1・・・4
2・・・12
3・・・56
4・・・244
5・・・1396
6・・・8200
7・・・55092
8・・・390216
9・・・3005320
10・・・24571192
24571192*33*33*...*33*32*...*3*2*1=1.39e+70
急ごしらえなのであんまり速くないからとりあえず10手まで。
あと、まだバグがあるかも知れないから誰か検証お願い。
274 ：256：2006/02/22(水) 03:27:33
違う手順で同じ局面になる事があるんだけど、
この扱いはどうすればいいかな？(transposition)
例えば次のような局面。
F5D6C3D3C4とF5D6C4D3C3
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●○＋＋＋＋
＋＋●●●＋＋＋
＋＋＋○●●＋＋
＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
F5F6E6F4E3とF5F4E3F6E6
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋●＋＋＋
＋＋＋○●○＋＋
＋＋＋●●○＋＋
＋＋＋＋●○＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
F5F6E6F4G5D6E7G6とF5F6E6F4G5D6E7F7
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
＋＋＋○○○＋＋ ＋＋＋○○○＋＋
＋＋＋○○○●＋ ＋＋＋○○○●＋
＋＋＋○○○○＋ ＋＋＋○○○＋＋
＋＋＋＋●＋＋＋ ＋＋＋＋●○＋＋
＋＋＋＋＋＋＋＋ ＋＋＋＋＋＋＋＋
>>260ではこれらを別物としてカウントしてます。
275 ：名無しさん＠５周年：2006/02/22(水) 10:30:49
あー、あれですよ。「オセロの試合結果」というものをどう取るか次第。
1）勝ち・負け・引き分け派 → 3通りということでFinal answer
2）決着時の盤面が何種類あるか派 → 回転・対称な盤面は1つに
3）棋譜？が何通りあり得るか派 → 全部別物ということで
プログラムとか組みやすいのは3）だろうね。自分は2）派。
282 ：256：2006/02/23(木) 07:56:46
>>275
>>260のプログラムを作るときに2)で数えるか3)で数えるか迷いましたが、
作るのが簡単な3)でやってみました。
プログラムの改良にと思ってTransposition Tableをハッシュ法で実装してみたら、
ごく一部でハッシュ値の衝突（全く違う局面から同じハッシュ値が生成）が起きたようで、
値が少し違う結果が出てきてしまいました。（速くはなりましたが）
もうちょっとよく考えてみます。
