「ありえない局面」の編集履歴（バックアップ）一覧に戻る
ありえない局面 - (2006/04/26 (水) 23:37:21) のソース
*ありえない局面
すべての盤面の中からありえない局面をとりのぞき、
オセロ局面を満足する盤面数を減らすために必要な証明。
親話題→[[終局局面数]]
----
314 256 sage 2006/02/25(土) 14:40:55
ある石の周囲にある石の数をとりあえず接続数と呼ぶことにします。
接続数について考えてみました。
オセロで実際に存在する盤面は、（当たり前のもありますが、、）
・全ての石の接続数は１以上。
・接続数が１の石に接続している石の接続数は２以上。
・接続数が１の石とそれに接続している石は同じ色。
↓こういうのは存在しない。
●＋＋＋＋＋＋＋
＋○＋＋＋＋＋＋
＋＋●●○○＋＋
＋＋●○●○○＋
＋＋○●○○＋＋
＋＋○●●○＋＋
＋＋●●●●＋＋
＋●●●●●＋＋
・接続数が１の石から３個以下石を辿ると接続数が３以上の石がある。
↓こういう細長いのは存在しない
＋＋＋＋＋＋＋＋
＋●●●＋●●＋
＋●＋●＋＋●＋
＋●＋●●＋●＋
＋●＋●●＋●＋
＋●＋＋＋＋●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋
最後のは証明してませんが反例はまだ見つかってません。
どなたか検証お願いします。
315 293 sage 2006/02/25(土) 15:48:58
>>314
＞・接続数が１の石とそれに接続している石は同じ色。
に対しては反例を挙げておきます。もう少し限定をかければ成立するかもしれませんが。
↓の石に関して。
●＋＋＋＋＋＋＋ → ●＋☆＋＋＋＋＋
＋●＋＋＋＋＋＋ → ＋○＋＋＋＋＋＋
○○○○○○＋＋ → ○○○○○○＋＋
＋＋●○●○○＋ → ＋＋●○●○○＋
＋＋○●○○＋＋ → ＋＋○●○○＋＋
＋＋○●●○＋＋ → ＋＋○●●○＋＋
＋＋●●●●＋＋ → ＋＋●●●●＋＋
＋●●●●●＋＋ → ＋●●●●●＋＋
＞・接続数が１の石から３個以下石を辿ると接続数が３以上の石がある。
の具体例に関しては（極端な例だからかもしれないけど）他の点からも指摘できます。
＋＋＋＋＋＋＋＋
＋④③②＋●●＋
＋⑤＋①＋＋●＋
＋●＋●●＋●＋
＋●＋●●＋●＋
＋●＋＋＋＋●＋
＋●●●●●●＋
＋＋＋＋＋＋＋＋
2と3の順番は逆になるかもしれませんが…とりあえず5は挟む物がないので置けません。
ついでに、最後のは分かりにくい気がするので言い換えを提案します。
・接続数が１の石から接続数が２以下の石だけを辿ると２個分までしか辿れない。
316 256 sage 2006/02/25(土) 15:57:36
>>315
ああ、なるほど。
もうちょっとよく考えて色んなふるいを作りたいと思います。
326 284 sage 2006/03/01(水) 13:18:49
>>314-315あたりを読んでて気が付いたが、
オセロの場合石を置くには最低挟める石と挟む為の石が必要なので、可能盤面は
「初期配置の中央４石を除き、全ての石は３個以上の列に含まれる」と言える。
なので>>314の下の図は、オセロでは有り得ないことが証明出来る。
（>>315の反例を一般化してみた）
475 256 sage New! 2006/04/16(日) 03:29:58
>>474
2^64にはならないと思います。
例えば↓のような局面は無理です。
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●●●●●●●●
●○●○●○●○
下辺に7個の白や黒の石があるどのような状態からも、
8個目を打って●○●○●○●○とする事は出来ません。
必ず辺の石を返してしまいます。
476 よんけた ◆Tl2oC4lIZ2 sage New! 2006/04/16(日) 04:06:45
>>457
(ﾟ◇ﾟ)ｶﾞｰﾝ
60手目、棋譜数は可能盤面数の何兆倍以上あるというのに
棋譜で表現できない盤面があるとは…
いやはや何とも…
477 名無しさん＠５周年 sage New! 2006/04/16(日) 12:51:36
辺のどこかに一箇所でも●○●○の４つの並びがあったら
その局面は実現不可能だと思う
479 名無しさん＠５周年 sage 2006/04/17(月) 16:36:31
>>475>>477
なるほど、辺の条件によっては無理なものがありますね。
辺の条件はＯＫでも不可能な盤面を思いついた。
●●●●●●●○
●○●○●○●●
●●○●○●○●
●○●○●○●●
●●○●○●○●
●○●○●○●●
●●○●○●○●
○●●●●●●●
480 名無しさん＠５周年 sage 2006/04/17(月) 17:25:11
少なくとも一つの方向に３つ以上の同じ色の石が連続していて
なおかつ、どの方向にも相手の石を挟んでいない石が存在しなければ
直前に打った石がないということで、その局面には到達できないってことかな
481 256 sage 2006/04/17(月) 17:32:05
>>479
不可能っぽく見えますけど、なぜ不可能ですか？
プログラムを作って存在できる辺と存在できない辺の形を調べてみました。
辺の８マス3^8=6561通りのうち、
・存在できるもの：5935通り
・存在できないもの：626通り
どなたか検証お願いします。
482 名無しさん＠５周年 sage 2006/04/17(月) 17:56:54
>>481
int p, i, j;
int c = 0;
int a[8];
for (p = 0; p < 6561; p++) {
j = p;
for (i = 0; i < 8; i++) {
a[i] = j % 3;
j /= 3;
}
for (i = 0; i < 5; i++) {
if (a[i] == 1 && a[i + 1] == 2 && a[i + 2] == 1 && a[i + 3] == 2) {
c++;
break;
}
if (a[i] == 2 && a[i + 1] == 1 && a[i + 2] == 2 && a[i + 3] == 1) {
c++;
break;
}
}
}
printf ("%d %d\n", 6561 - c, c);
5969 592
ちょっと違った
483 479 sage 2006/04/17(月) 18:14:27
>>480>>481
475や477と同じ理屈で、最終着手が盤面のどの石でも必ずどれかの石を返します。
484 よんけた ◆Tl2oC4lIZ2 sage 2006/04/17(月) 18:26:17
>>479
すべての石が8方向のうちどれか１方向へ
◆○●（◆はそのマスに置かれているもの
そのマスに置かれている石が白の場合は◇●○となる）
という形をとっている場合、
すべての石が直前の一手となりえないので
その局面は存在しないこととなる。
◆○●は、 ◆○○● ◆○○● ◆○○○● でも可
>>480とちょっと違うな。。どうなんだろ。。
６４マス全部埋まっていなくとも、通用する理論？
485 名無しさん＠５周年 sage 2006/04/17(月) 19:03:48
>>484
基本的には同じことを書いたつもり。
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋●●＋＋＋
＋＋●○○●＋＋
＋＋●○○●＋＋
＋＋＋●●＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
この局面はどの石も３つ以上連続したつながりを持っていないので
直前に打った石がないことになり作れない。
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●●●＋＋＋
＋＋●○○●＋＋
＋＋●○○●＋＋
＋＋＋●●＋＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
これは左上隅の黒石が右と下方向に３つ連続していて、隣接した白を挟んでいないので
少なくとも１手前からは作れる。
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
＋＋●●●＋＋＋
＋＋●○○●＋＋
＋＋●○○●＋＋
＋＋＋●●●＋＋
＋＋＋＋＋＋＋＋
＋＋＋＋＋＋＋＋
これは全ての黒石が白を挟んでしまっているので、作れない。
486 256 sage 2006/04/17(月) 19:21:01
>>483
なるほど。ありがとうございます。
僕の作った不可能な辺の形を調べるプログラムの出力です。
一番右の数字がゼロのものがありえない形です。
Wikiにアップしました。170KBくらいあります。
http://www9.atwiki.jp/othello/?cmd=upload&act=open&pageid=39&file=impossibleedge.txt
487 名無しさん＠５周年 sage 2006/04/17(月) 19:51:56
>>486
機械的に黒白黒白が含まれる数を数えただけなので
●○●●○●
○●○○●○
の６個の並びと
●○●●○○●○
○●○○●●○●
を数え漏らしてたようでした。
すみません。
488 名無しさん＠５周年 sage 2006/04/17(月) 20:13:30
今石を置いていくプログラムを書いたら同じ数になりました。
489 よんけた ◆Tl2oC4lIZ2 sage 2006/04/18(火) 19:38:40
>>485
「辺」の定義を広くして次の盤面も
棋譜で表現不可能かと。
＼ＡＢＣＤＥＦＧＨ
１＋＋＋＋＋＋＋＋
２＋＋＋●○●○＋
３＋＋＋●○●○●
４＋＋●●○●○●
５＋○○○○○○●
６＋＋●●○○●＋
７＋●●●●○＋＋
８＋＋＋＋＋＋＋＋
Ｄ2からＧ2が●○●○となっているため。
＼ＡＢＣＤＥＦＧＨ
１＋＋＋●●○○○
２＋＋＋●○●○○
３＋＋＋○●●○○
４＋＋＋●●●○○
５＋＋＋●○○○○
６＋＋＋○●○○○
７＋＋＋●●●○○
８＋＋＋●●●●○
Ｄ2からＤ7まで●○●●○●となっているため。
これは正しい？
490 名無しさん＠５周年 sage 2006/04/18(火) 23:36:11
>>489
ある連続した石の列をとったとき
その列に属する全ての石が、その列を構成する石からしか挟まれていないか
どの方向にも挟まれていなかった場合
その列に辺の打てないパターンが含まれていたら
その局面は棋譜で表現不能。
ってことでいいのかな？
＼ＡＢＣＤＥＦＧＨ
１＋＋＋＋＋＋＋＋
２＋＋＋＋＋＋＋＋
３＋○○○○＋＋＋
４●●○○●●＋＋
５●●●○●●＋＋
６＋○●●●●●●
７＋＋●●○○＋＋
８＋＋＋○○○＋＋
これのＡ５からＤ８までの斜めのラインとかも？
491 名無しさん＠５周年 sage 2006/04/19(水) 19:09:06
辺の全でに石があるときの、辺の有り得ない形を調べたら
2^8=256のうち106が有り得ない形で、150が可能な配置でした。
と、いうことは６０手後の終局盤面 2^64のうち、少なくとも1-(150/256)^4=0.88くらいは
有り得ない局面だということですね。
隅石の重複を考慮してないので正確ではないですが大体このくらいかと。
さらに、辺は可能でも全体としては不可能な盤面もあるので終局局面数はさらに減るのかな。
492 よんけた ◆Tl2oC4lIZ2 sage 2006/04/19(水) 22:50:59
>>490
ですね。かなり削られますねこれで。
タブーの形が一次元なパターンですが、二次元のパターンはないのかなぁと思ったりもします。
>>491
場合わけをして計算したら、
64マス全て埋まっている状態で
全ての四辺の通り
2＾28 = 268435456
のうち、>>486に引っかからない四辺は、
31640626 でした。（>>486のデータを使わせていただきました。）
６４マス全て埋まっている状態のうち、オセロ到達可能局面は、
12％未満というのはすごく驚きです。
ここらへんの感覚は今まで認知されてたんでしょうか。。
493 よんけた ◆Tl2oC4lIZ2 sage 2006/04/19(水) 23:15:42
>>493
タブーというのは
間違った表記ですね
語彙がいいかげんですみません
494 名無しさん＠５周年 sage 2006/04/20(木) 00:08:32
60個埋まっている最終局面をランダムに発生させて
ありえない局面を除いた割合を調べてみました。
ありえない辺だけを除いた局面の割合
100000000 11788619 0.117886
計算では31640626/2^28=0.117871
辺のパターンは考慮せず白も黒も1手も戻せない局面だけを除いた割合
10000000 9492871 0.949287
ありえない辺と白も黒も1手も戻せない局面を除いた割合
100000000 11447828 0.114478
この100000000回のうち辺のチェックは通った数 11785752
11785752 11447828 0.971328
辺がありうる並びだったとき3％弱程度が1手戻せなかったみたいです。
495 名無しさん＠５周年 sage 2006/04/20(木) 09:27:52
>>492
二次元は私も考えてましたがなかなか難しいですね。
唯一思いついたのがこれです。
盤面は２つとも左上隅とします。
●○●＋＋ |●○●＋＋
＋※※＋＋ |○※※＋＋
＋＋＋＋＋ |●※＋＋＋
＋＋＋＋＋ |＋＋＋＋＋
＋は石の有無は問わないとして※の箇所が全て空白は不可能。
理由：白石は、隅と辺の黒石に挟まれてるので、黒石より後から打たなければならない。
そのとき、※の箇所が全て空白だと打てない。
