Transposition


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

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

例)F5D6C3D3C4とF5D6C4D3C3 
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
++++++++ ++++++++ ++++++++ ++●+++++ ++●○++++ ++●○++++
+++○●+++→+++○●+++→+++○●+++→+++●●+++→+++○●+++→++●●●+++
+++●○+++ +++●●●++ +++○●●++ +++○●●++ +++○●●++ +++○●●++
++++++++ ++++++++ +++○++++ +++○++++ +++○++++ +++○++++
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++

++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
++++++++ ++++++++ ++++++++ ++++++++ +++○++++ ++●○++++
+++○●+++→+++○●+++→+++○●+++→++●●●+++→++●○●+++→++●●●+++
+++●○+++ +++●●●++ +++○●●++ +++○●●++ +++○●●++ +++○●●++
++++++++ ++++++++ +++○++++ +++○++++ +++○++++ +++○++++
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++
++++++++ ++++++++ ++++++++ ++++++++ ++++++++ ++++++++

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



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

あくまで予測だが棋譜数・局面数・盤面数のグラフを見て欲しい。
このグラフから判るように60手目、棋譜数は局面数の
10000000000000000000000000000000倍(30ケタ)以上存在している。
ゆえに平均的に一つの60手目局面は10^30通り以上の棋譜で表現できることとなる。

上の例では
++++++++
++++++++
++●○++++
++●●●+++
+++○●●++
+++○++++
++++++++
++++++++
が2通りの棋譜で表現できている

このグラフでは
○○○○○○●●
○○○●○○○●
○○●○●○○●
○○●●○○●●
○○●○●○●●
○●○○●●○●
○○○○○○●●
○○●●●●●●
みたいな任意の60手目の局面が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 :名無しさん@5周年: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をハッシュ法で実装してみたら、 
ごく一部でハッシュ値の衝突(全く違う局面から同じハッシュ値が生成)が起きたようで、 
値が少し違う結果が出てきてしまいました。(速くはなりましたが) 
もうちょっとよく考えてみます。
ツールボックス

下から選んでください:

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