ありえない局面

すべての盤面の中からありえない局面をとりのぞき、
オセロ局面を満足する盤面数を減らすために必要。

今のところありえない局面となる条件

• 中央四マスいずれかが緑
• つながってない石がある
• 一手戻せない。
• ありえない辺がある

の四つ

親話題→終局局面数
子話題→オセロ局面・非局面である証明

---

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 (&quot;%d %d\n&quot;, 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 
二次元は私も考えてましたがなかなか難しいですね。 
唯一思いついたのがこれです。 
盤面は２つとも左上隅とします。 
●○●＋＋　　　|●○●＋＋ 
＋※※＋＋　　　|○※※＋＋ 
＋＋＋＋＋　　　|●※＋＋＋ 
＋＋＋＋＋　　　|＋＋＋＋＋

＋は石の有無は問わないとして※の箇所が全て空白は不可能。 
理由：白石は、隅と辺の黒石に挟まれてるので、黒石より後から打たなければならない。 
　　そのとき、※の箇所が全て空白だと打てない。

496 名無しさん＠５周年 sage 2006/04/23(日) 19:55:23 
疑問に思ったんだけど、中央４×４のボックスから初期配置４石を除いた１２マスが 
全て埋まる最長手数は何手なんでしょう？ 
最短手数は１２ですよね。 
感覚的には５９手までボックスのうちの１マスを開けておくのは不可能に思えるのですが。 
これが不可能であれば６４マス埋まった盤面から１手戻すときもボックスは除外できます。 

さらに言えば終局前の数手はほとんど隅の近くしか空いてないと思うのですが、 
これも証明は難しいですよね。 

497 名無しさん＠５周年 sage 2006/04/23(日) 20:59:39 
f5d6c3d3c4f4c5b3c2b4e3e6c6f6a5a4b4a6d7c7e7e8b6d8 
g3f7g5d1c1b1g6a7g8h6h5f8c8h4g4b2a1b7e1h3a2h7a3g2 
a8b8g7h8h2h1g1f1f2e2d2f3  

最後まで開けられる模様。 

498 名無しさん＠５周年 sage 2006/04/23(日) 21:57:44 
どうやって見つけたんだ！ 

一ヶ所バグがあったので直した 
f5d6c3d3c4f4c5b3c2b4e3e6c6f6a5a4b5a6d7c7e7e8b6d8 
g3f7g5d1c1b1g6a7g8h6h5f8c8h4g4b2a1b7e1h3a2h7a3g2 
a8b8g7h8h2h1g1f1f2e2d2f3  

17手めb4→b5 

499 名無しさん＠５周年 sage 2006/04/24(月) 09:52:05 
496です。 
そうですか、可能でしたか！でも早速の反例ありがとうございます。 

501 284 sage 2006/05/03(水) 13:11:34 
あと>>474- からの流れの、直前手が可能かどうかでの不可能盤面についてですが以下のことを考えました。 
例として>>455の盤面を使わせてもらいます。 

455の盤面で480の条件を使い直前手を選びます。（私なりに表現を変えていますが同じ意味です） 
条件１：その石と同色で３石以上並んでいなければならない。（ただし３石並びの真ん中は除く） 
下図の星の位置 
＋＋＋＋＋＋＋＋ 
＋☆＋☆＋○☆＋ 
＋☆●○●★☆＋ 
＋☆●☆★●☆＋ 
＋☆＋★○＋☆＋ 
＋●★＋＋●●＋ 
＋○○●●○○＋
＋＋＋＋＋＋＋＋ 

条件２：どの方向にも相手の石を挟んでいない。 
条件２を加えると黒の３石が残る。 
＋＋＋＋＋＋＋＋ 
＋○＋○＋○○＋ 
＋○●○●★○＋ 
＋○●○●●○＋ 
＋○＋★○＋○＋ 
＋●★＋＋●●＋ 
＋○○●●○○＋ 
＋＋＋＋＋＋＋＋

黒★の１つは初期配置なので、それも除き直前可能位置は２つですね。 
（続く） 

502 284 sage 2006/05/03(水) 13:12:20 
（続き） 
この２石を着手する前の盤面は次の４つ。 
＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋ 
＋○＋○＋○○＋　｜　＋○＋○＋○○＋ 
＋○●○●※○＋　｜　＋○●○●※○＋ 
＋○●○○●○＋　｜　＋○●○○●○＋ 
＋○＋●○＋○＋　｜　＋○＋○○＋○＋ 
＋●●＋＋●●＋　｜　＋●●＋＋●●＋ 
＋○○●●○○＋　｜　＋○○●●○○＋ 
＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋ 

＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋ 
＋○＋○＋○○＋　｜　＋○＋○＋○○＋ 
＋○●○●●○＋　｜　＋○●○●●○＋ 
＋○●○●●○＋　｜　＋○●○○●○＋ 
＋○＋○○＋○＋　｜　＋○＋○○＋○＋ 
＋●※＋＋●●＋　｜　＋●※＋＋●●＋ 
＋○○●●○○＋　｜　＋○○●●○○＋ 
＋＋＋＋＋＋＋＋　｜　＋＋＋＋＋＋＋＋ 
この４つの盤面も同じように遡っていけば元の盤面が可能かどうか分かります。 

と、ここまでは理論ですが、私が考えたのは455の３０石ある盤面で直前可能手が２手、 
直前可能盤面は４つ、というのは少ない気がします。 
（直前可能手、直前可能盤面が少ないので不可能盤面ではないか、ということです） 
例えば、>>494で 
＞辺がありうる並びだったとき3％弱程度が1手戻せなかった 
とされていますが、残り97％の直前手可能数と 
ランダム棋譜で６０手進めた時の直前手可能数を比べてみてはどうでしょう。 
感覚的には後者のほうが直前手可能数が多いように思います。 

この続きはオセロ局面・非局面である証明