最大着手可能数

このページの説明

とりあえずオセロの最大着手可能数はいつくか？を求める話をピックアップ。

• 「棋譜に縛られずに作った盤面で」「実際にオセロの中で出てくる棋譜において」の２つの解釈があるが、とりあえず両方考える。

流れの概略

• みつかった最大着手可能数
  • 棋譜に縛られない盤面での着手可能数
    • ２００６年２月 >>256 が棋譜に縛られない盤面で 28、32、33 手着手可能の盤面を発見。
    • ２００６年４月 >>455 が棋譜に縛られない盤面で 34 手着手可能の盤面を発見。
    • ２００９年１１月現在 34 手着手可能が最大。
  • 実際の棋譜上に存在する盤面での着手可能数
    • ２００６年３月 >>400 が実際の棋譜上で 28 手着手可能の盤面を発見。
    • ２００６年３月 >>402 が実際の棋譜上で 29 手着手可能の盤面を発見。
    • ２００９年１１月現在 30 手着手可能が最大。
• 証明・補題・方法などの発見
  • ２００６年３月 >>331 が「最大着手可能数は 46 以下である」を証明する。
  • ２００６年３月 >>331 が「最大着手可能数は int(盤上の石数/3)*8以下になる」という補題を証明する。(これから棋譜数の上限が絞れる)
  • ２００６年４月 >>770 が拘束付き全探索での最大着手可能数の下限の探索を提唱。

レス引用

256 ：256 ：2006/02/19(日) 22:09:07 
オセロで打てる箇所の数は最大で２８かな？ 
例えばこういう↓局面。 
＋＋＋＋＋＋＋＋ 
＋○○○○○○＋ 
＋○●●●●○＋ 
＋○●●●●○＋ 
＋○●●●●○＋ 
＋○●●●●○＋ 
＋○○○○○○＋ 
＋＋＋＋＋＋＋＋ 
「２８」なのかは証明したわけじゃないけど、 
この局面より打てる場所が多いのは思い浮かばなかった。 
もし２８で正しいなら２８より大きいのは２８にしてしまえるから 
28*28*28*28*...*28*27*...*3*2*1=6.21e+75ってできると思う。 
これだと>>244より4桁くらいしぼれるかな 
誰か「２８」の証明か反例探しお願い。 

257 ：256 ：2006/02/19(日) 23:10:46 
>>256 
もっと多いの見付けた・・。 
これで打てる場所は３２個。 
＋＋＋＋＋＋＋＋ 
＋○○＋○○○＋ 
＋○●○○●○＋ 
＋○○●●○＋＋ 
＋＋○●●○○＋ 
＋○●○○●○＋ 
＋○○○＋○○＋ 
＋＋＋＋＋＋＋＋ 
32*32*32*32*...*32*31*...*3*2*1=3.67e+77 
増えていく・・（泣 

258 ：名無しさん＠５周年 ：2006/02/19(日) 23:53:43 
ちょっと試してみたがオレも32ヶ所以上はできなかった 

259 ：256 ：2006/02/20(月) 07:16:44 
33個見つけました。 
＋＋＋＋＋＋＋＋ 
＋○○●○○○＋ 
＋○●＋○●○＋ 
＋●＋●●＋○＋ 
＋○○●○●○＋ 
＋○●＋○●○＋ 
＋○○＋○○○＋ 
＋＋＋＋＋＋＋＋ 
33*33*33...*33*32*...*3*2*1=8.68e+77

330 ：284 ：2006/03/02(木) 09:29:22 
>>329 
最大着手可能数について考えてみました。 

オセロに着手可能数47の盤面がある、と仮定する。 
仮定条件、黒番とし、黒石は挟む石、白石は挟まれる石とする。 
①盤面にある石は17個以下である（64-47=17) 
②黒石（挟む石）１個に対し着手可能数は８（８方向）なので 
47/8=5.875→盤上に６個以上の黒石がある。 
③白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので 
47/4=11.75→盤上に１２個以上の白石がある。 

①の１７個以下と②＋③の１８個以上は矛盾する。 
故に仮定の「オセロに着手可能数47の盤面がある」は間違いなので 
オセロの最大着手可能数は46以下である（証明終了） 

もう少し条件を加えられればさらに減らせると思うのですが。 

331 ：284 ：2006/03/02(木) 09:58:00 
>>330は、もっと単純に出来ましたね。 
330の条件②と③により、着手可能数は 
int(盤上の石数/3)*8以下になる（intは切捨ての意） 
１２手目、１３手目は石数が16,17なのでint(17/3)*8=40 
>>329の１２手目までを使わせてもらって 
1,939,899,208 * 40 * 40 * 46! = 1.708E+70 
１２手目の最大着手数20も入れて 
1,939,899,208 * 20 * 40 * 46! = 8.540E+69

344 ：名無しさん＠５周年 ：2006/03/04(土) 00:50:33 
「手」を n=(盤上の石の数)-4 と逆に定義して、 
１つパスが起きたらパス数p[n]を１つ増やし、 
終局が起きたら終了数e[n]を１つ増やし、 
棋譜数f[n]を求める >>293 の数え方がわかりやすいんじゃない？ 
「手」と盤上の石の数の対応が簡単につくし。 
俺も >>293 と同じ結果の出るアルゴリズムが組めたよ。 

>>331 
＞>>330は、もっと単純に出来ましたね。 
＞330の条件②と③により、着手可能数は 
＞int(盤上の石数/3)*8以下になる（intは切捨ての意） 

うーん、この最後の int(盤上の石数/3)*8 が分からないや…。 
>>330は理解できたんだけど。

346 ：284 ：2006/03/04(土) 08:32:12  
>>344 
＞うーん、この最後の int(盤上の石数/3)*8 が分からないや…。 
330の条件②黒石（挟む石）１個に対し着手可能数は８（８方向）から、 
②’着手可能数８の時、黒石は最低１個必要。 
③白石（挟まれる石）１個に対し着手可能数は４（縦横斜めの４ライン）なので 
③’着手可能数４の時、白石は最低１個必要。 
よって着手可能数８の為には最低限、黒石が１個白石が２個の計３個必要。 
なので盤面の石で３個セットがいくつとれるか（int(盤上の石数/3)）に 
着手可能数８をかけました。

391 ：名無しさん＠５周年 ：2006/03/12(日) 06:05:54 
n手目の着手可能数をe(n)とすると 
e(n+1) <= e(n) + 5 
なぜなら、着手可能数が一番増えるケースは、 

□□□ 
□★□ 
□□● 

の★のところに打ったときであり、●の隣を除去した５つの□マスであるから。 

これから、15手の最大分岐数=23より、 
e(16) <= 23+5*1 = 28 
e(17) <= 23+5*2 = 33 
e(18) <= 23+5*2 = 38 
e(19) <= 23+5*2 = 42 
e(20) <= 23+5*2 = 41 
これ以上は単純な空マスの数の方が小さくなるので 
1891844432704 * 28 * 33 * 38 * 42 * 41! = 9.3333 * 10^67 

Allisによる概算上界 10^58 まであと9桁です。 
http://dais.main.jp/reversi/solve-reversi.html

394 ：284 ：2006/03/12(日) 16:08:18 
>>391 
着手可能数の増加が最大５というのは黒石ゲームの場合ですね。 
その値とオセロゲームでの15手目最大23を単純に足すのはマズいのでは？ 
オセロには黒番・白番があるので。 
通常のオセロでも黒番の着手可能数が１～２でも、白番は＋６（７～８）以上になることは十分ありえますし。

400 ：256 ：2006/03/17(金) 06:26:17 
終盤のほうで、「空き数＝最大着手可能箇所数」の局面が実際にあるか探してみました。 
１～２８個空きでは見つけましたが２９個空きからなかなか見つかりませんでした。 
２９個空きで２８箇所の着手可能箇所がある局面に至る棋譜は見つけましたが・・。 
N手--空数---棋譜 
32----28----F5D6C3D3C4F4F6G6E6E7F7G5E3C5F3B3B4B5B6B7C7G2G3G4D7G7C6B2C2D2F2E2 
33----27----F5D6C3D3C4F4F6G6E6E7F7G5E3C5G7F8D7C7B7B4B6B5B3C6G4G3G2C2B2D2F3F2E2…(wiki注:以下400にも続く)

402 ：256 ：2006/03/17(金) 07:20:04 
２９個見つかりました。 
N手--空数---棋譜 
31----29----F5D6C4F4F6F3D3F7E6C5D7E3E2F2G7E7C3G6G5C7D2B4G3C2B2B3B5B6B7C6G2 

403 ：名無しさん＠５周年 ：2006/03/18(土) 05:08:24 
盤面はどんな感じっすか？

404 ：256 ：2006/03/18(土) 06:08:28 
>>403 
>>402の29個のはこんな感じです。 
F5D6C4F4F6F3D3F7E6C5D7E3E2F2G7E7C3G6G5C7D2B4G3C2B2B3B5B6B7C6G2 
＋＋＋＋＋＋＋＋ 
＋●●●●●◆＋ 
＋●○○○●●＋ 
＋●○○○●＋＋ 
＋●○○●●●＋ 
＋●○○○○●＋ 
＋●●●●●●＋ 
＋＋＋＋＋＋＋＋ 
ちなみに僕が棋譜を並べたり盤面を作ったりする時はいつもこれ↓使ってます。 
http://www2.next.ne.jp/~runoth/runoth.html

450 ：284 ：2006/04/08(土) 16:45:45 
>>449 
１つ思いつきました。 
着手可能の為には挟む石と挟まれる石が必要なので 
最大着手可能数は（挟む石）×（挟まれる石）。 
初手は挟む石（黒石）＝２、挟まれる石（白石）＝２なので 
最大着手可能数＝２×２＝４となる。 

でもこれって、初手着手数４の証明じゃなくて初手着手可能数の上界の証明ですよね。  
それにこれを一般化しても>>330の「46以下」は超えられないし。う～む・・・

455 ：名無しさん＠５周年 ：2006/04/09(日) 19:27:29 
＋＋＋＋＋＋＋＋ 
＋○＋○＋○○＋ 
＋○●○●●○＋ 
＋○●○●●○＋ 
＋○＋●○＋○＋ 
＋●●＋＋●●＋ 
＋○○●●○○＋ 
＋＋＋＋＋＋＋＋ 
ランダムに局面発生させて、34箇所打てる局面発見 
１手目から作れそうにないけど

770 ：757 ：2009/05/14(木) 03:38:12 
>>259 の流れで、棋譜に囚われない任意盤面の最大着手数を
＋＋＋＋＋＋＋＋ 
＋○○？？○○＋ 
＋○●？？●○＋
＋？？！！？？＋ 
＋？？！！？？＋ 
＋○●？？●○＋　？＝{●,○,＋}、！＝{●,○} 
＋○○？？○○＋　●は10個、○は20個、＋は34個 
＋＋＋＋＋＋＋＋　 
という縛りから全探索してみました。 
結果、33手着手可能盤面は52個もみつかりましたが、 
34手着手可能盤面は全部探してもみつかりませんでした。 
上の初期配置は拘束条件として厳し過ぎたかな… 
34手着手可能なときの論理的に正しい盤面拘束条件があれば教えてください… 

ちなみに見つかってなかった33手着手可能盤面の例はこんな感じです。 
まず思いつかないね。 
★★★★★★★★ 
★○○○＋○○★ 
★○●●★●○★ 
★○○○○●○★ 
★★★●●★●★ 
★○●○★●○★ 
★○○○●○○★ 
★★★★★★★★ 

771 ：名無しさん＠５周年 ：2009/05/14(木) 04:17:11 
>>770 
乙 
こりゃ面白い 
>>455に34箇所の局面があるけどこれはありえない形みたい(>>504) 
論理的に正しいってのがよくわからないけどこういう条件はどうだろ 
＋＋＋＋＋＋＋＋ 
＋○？？？？○＋ 
＋？●？？●？＋ 
＋？？！！？？＋ 
＋？？！！？？＋ 
＋？●？？●？＋　？＝{●,○,＋}、！＝{●,○} 
＋○？？？？○＋　●は10個、○は20個、＋は34個 
＋＋＋＋＋＋＋＋ 
緩すぎて全探索終わらなくなりそうな気がするけど 

ちょっと疑問なんだけど 
着手可能箇所数が最大になるときは必ず外周の28箇所は全てに打てるのかな？ 

772 ：名無しさん＠５周年 ：2009/05/14(木) 10:21:16 
>>770 
なかなか面白いアイデアですね。ところで 
＞●は10個、○は20個、＋は34個 
も条件に入れてるんだよね？ 
外したほうが良い気もするけど、外すと探索範囲が増えるぎるね。 

773 ：名無しさん＠５周年 ：2009/05/14(木) 11:00:03 
実現可能かを考慮しなければ、これが最大を与えることは間違いない。 

＋＋＋＋＋＋＋＋ 
＋○？？？？○＋ 
＋？？？？？？＋ 
＋？？●●？？＋ 
＋？？●●？？＋ 
＋？？？？？？＋　 
＋○？？？？○＋　 
＋＋＋＋＋＋＋＋ 


○？？？？○　のパターンは、対称性と端に黒がおけるという条件から限定出来る。 
そこまでしたら全探索すればいいのでは? 

774 ：773 ：2009/05/14(木) 11:12:37 
中心が黒のみは間違えた。　白が混じった方がいいかもしれん。 


○？？？？○の部分は次のいずれか。 
これ以外では端が取れなくなる。 

○○？？○○ 

○○？○？○ 

○？○？○○ 

○？○○？○ 

775 ：773改 ：2009/05/14(木) 11:22:50 
実現可能かを考慮しなければ、これが最大を与えることは間違いない。 

＋＋＋＋＋＋＋＋ 
＋○？？？？○＋ 
＋？？？？？？＋ 
＋？？？？？？＋ 
＋？？？？？？＋ 
＋？？？？？？＋　 
＋○？？？？○＋　 
＋＋＋＋＋＋＋＋ 

○？？？？○　のパターンは、？？？？に黒の着手点が存在する、端におけるという条件から 
○空○○●○、○空○●○○のいずれか。 

776 ：757 ：2009/05/15(金) 02:07:58 
>>771 
> >>455に34箇所の局面があるけどこれはありえない形みたい(>>504) 
おっと忘れてました。もう >>770 の前提が崩れましたね 
>論理的に正しいってのがよくわからないけど 
「この初期条件と拘束条件から全探索すれば必ず 34 手着手盤面を見逃すことはない」という意味です。 

>着手可能箇所数が最大になるときは必ず外周の28箇所は全てに打てるのかな？ 
＞●は10個、○は20個、＋は34個 も条件に入れてるんだよね？ →はい 
このへんまだヒューリスティックな予想でしかないので、 
証明付きの拘束条件が欲しいところです 
>>775 の流れはいい感じかも 

777 ：757 ：2009/05/15(金) 02:09:01 
>>771 の 
>＋＋＋＋＋＋＋＋ 
>＋○？？？？○＋ 
>＋？●？？●？＋ 
>＋？？！！？？＋ 
>＋？？！！？？＋ 
>＋？●？？●？＋　？＝{●,○,＋}、！＝{●,○} 
>＋○？？？？○＋　●は10個、○は20個、＋は34個 
>＋＋＋＋＋＋＋＋ 
これで現在探索中です。 
まだ数分しか経ってませんが 4361971087 盤面をチェックして 
既に 15 個の 34 手着手可能盤面がみつかりました。 
２つほど例を / 
★★★★★★★★ ★★★★★★★★ まだ探索が浅いので似通ってますが。 
★○○★○★○★ ★○○★○★○★ もう34手はいいっすかね。 
★○●●○●○★ ★○●●○●○★ 一個削って35手探しましょうか 
★★○●○○○★ ★★●●○○○★ 
★○○●●★●★ ★○○○●★●★ 
★★●○★●○★ ★★●○★●○★ 
★○○○●○○★ ★○○○●○○★ 
★★★★★★★★ ★★★★★★★★ 

778 ：757 ：2009/05/15(金) 02:21:03 
このへんの流れをおさらいすると、 
17--28手目の最大着手数の下界は、現在では残りの空白全てに打てるとみたものと考えるしかなく、 
それぞれ43--35とされている。 
でも全探索された17手目の真の最大着手数は26で増加率もたいして高くない。 
棋譜に載るかを無視した任意盤面での下界が43手以下になることが実証されると、 
全探索せずとも棋譜数上界が下げられる。 
任意盤面全探索は固定配置や石数などの拘束条件がゆるいと時間がかかるが、 
きつ過ぎると見落とす可能性がある。 
この拘束条件なら見落とすことはないぜっていう拘束条件とその証明が欲しいところです 

779 ：名無しさん＠５周年 ：2009/05/15(金) 02:41:22 
>>757 
周囲4辺はあける。　端から一つ内側は白。　という条件で、すべて生成するのがいいかも。 
全探索は無理でも、着手数を評価値とした探索アルゴリズムで調べたらいいかもしれない。 
現在の着手数と数手先の着手数はある程度関係があるだろうから

 784 ：757 ：2009/05/16(土) 02:49:13 
 >>771 全探索完了 
 ★★＋★★★★★　初期配置=>>771 拘束={●=10, ○=19, 空=35} 
 ★○★○★○○★　結果: 
 ★○●○★●○★　★ = 31: 808976 boards 
 ★○○○●●○★ ★ = 32: 43192 boards 
 ★●★●○★○★ ★ = 33: 648 boards 
 ★○●★★●●★ ★ = 34: 8 boards 
 ★○○●○○○★ ★ = 35: 0 boards 
 ★★★★★★★★　← ★=34 の例 
 
 この回転線対象系 x8 だけみたい…

 785 ：名無しさん＠５周年 ：2009/05/16(土) 03:19:10 
 お、思ったよりも速いんだな。乙。 
 >>775の条件でもできそうかな？ 

 786 ：名無しさん＠５周年 ：2009/05/16(土) 03:37:08 
 ＋★★★★★★★ 
 ★★○★○●○★ 
 ★○○●○○○★ 
 ★★○●●★●★ 
 ★○○●○★○★ 
 ★★●●★●○★ 
 ★○○○○●○★ 
 ★★★★★★★★ 

 787 ： ◆wVoxvyek5Q ：2009/05/16(土) 04:55:29 
 取りテスト 

 788 ：名無しさん＠５周年 ：2009/05/16(土) 21:05:36 
 >>786 
 まだ 34 が最大とは限らないから