Transposition

違う手順で同じとなる局面。

例）F5D6C3D3C4とF5D6C4D3C3 
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋●＋＋＋＋＋　＋＋●○＋＋＋＋　＋＋●○＋＋＋＋
＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋●●＋＋＋→＋＋＋○●＋＋＋→＋＋●●●＋＋＋
＋＋＋●○＋＋＋　＋＋＋●●●＋＋　＋＋＋○●●＋＋　＋＋＋○●●＋＋　＋＋＋○●●＋＋　＋＋＋○●●＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋○＋＋＋＋　＋＋＋○＋＋＋＋　＋＋＋○＋＋＋＋　＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋

＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋○＋＋＋＋　＋＋●○＋＋＋＋
＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋＋○●＋＋＋→＋＋●●●＋＋＋→＋＋●○●＋＋＋→＋＋●●●＋＋＋
＋＋＋●○＋＋＋　＋＋＋●●●＋＋　＋＋＋○●●＋＋　＋＋＋○●●＋＋　＋＋＋○●●＋＋　＋＋＋○●●＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋○＋＋＋＋　＋＋＋○＋＋＋＋　＋＋＋○＋＋＋＋　＋＋＋○＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋　＋＋＋＋＋＋＋＋

このように３手目以降の置石の位置が違うが、５手目で同じ局面となっている。
直感以上にかなり存在する模様。

どのくらいの割合で存在するのか？

あくまで予測だが棋譜数・局面数・盤面数のグラフを見て欲しい。
このグラフから判るように６０手目、棋譜数は局面数の
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をハッシュ法で実装してみたら、 
ごく一部でハッシュ値の衝突（全く違う局面から同じハッシュ値が生成）が起きたようで、 
値が少し違う結果が出てきてしまいました。（速くはなりましたが） 
もうちょっとよく考えてみます。