オセロの試合結果は全部で何通りか

オセロの試合結果は全部で何通りか at SIM

848:838
09/12/27 00:59:16
では最大着手数 45 の否定を。
「最果ての○は自分の余碗を消耗してしまう」という原理を応用する。
○の最果ては８つあり、その最果ての「内部」にしか●がない場合は
○はそこでそれぞれ１つ○余碗を消費してしまう。
内部は３方向だけであり、腕の総数４に満たないからだ。
複数の最果てを○が兼ねたら、その兼ねた数だけ○余碗を消費する。
結局●がライン上かもしくは最果ての外にない限り、
○は計８余碗の消費を免れない。

ex最北　最北西　
５５５７５４　最果ての○の余碗を消すには、
４○４５○１　最果てライン上か、最果ての外に相棒●を追加せざるを得なくなる。
０００４１０　そのとき、相棒●の位置と消費してしまう●の余碗数は次のようになる。

つまり、ひとつの最果ての○の余碗１つの消去につき最低でも４の●余碗を消費する。
つまり、○余碗の回復のための「●の外打ち」数をＮとすると、
○の総余碗数 >= 8-N
●の総余碗数 >= 4N
となる。これを連立させて解くと、
32 <= ●の総余碗数 + 4○の総余碗数
が必要になる。

849:838
09/12/27 01:00:06
これを満たす ★=42～46 を全て書きだすと、
★=44, ●=7 , ○=13, ●余腕=10, ○余腕= 6

★=43, ●=6 , ○=14, ●余腕= 2, ○余腕=10
★=43, ●=6 , ○=15, ●余腕= 2, ○余腕=14
★=43, ●=7 , ○=13, ●余腕=10, ○余腕= 6
★=43, ●=7 , ○=14, ●余腕=10, ○余腕=10
★=43, ●=8 , ○=13, ●余腕=18, ○余腕= 6
★=43, ●=9 , ○=12, ●余腕=26, ○余腕= 2

★=42, ●=6 , ○=14, ●余腕= 2, ○余腕=10
★=42, ●=6 , ○=15, ●余腕= 2, ○余腕=14
★=42, ●=6 , ○=16, ●余腕= 2, ○余腕=18
★=42, ●=7 , ○=13, ●余腕=10, ○余腕= 6
★=42, ●=7 , ○=14, ●余腕=10, ○余腕=10
★=42, ●=7 , ○=15, ●余腕=10, ○余腕=14
★=42, ●=8 , ○=13, ●余腕=18, ○余腕= 6
★=42, ●=8 , ○=14, ●余腕=18, ○余腕=10
★=42, ●=9 , ○=12, ●余腕=26, ○余腕= 2
★=42, ●=9 , ○=13, ●余腕=26, ○余腕= 6
★=42, ●=10, ○=12, ●余腕=34, ○余腕= 2

である。よって最大着手 45 は否定される。

ちなみに、この話を実際のオセロ盤の広さで考えてみると、
最果てを兼ねるなんて言ってる場合ではなくて、
できるだけ「内部」を広く取って
できるだけたくさんそこに石を詰めれるように
最果て○をいっぱい作らなくといけなくなって、
そのために着手数をもっと削らないといけないことがよく分かる。
今日は以上です。

850:名無しさん＠５周年 ◆ZTZ.ji25iA
09/12/27 09:22:34
長き解析お疲れ様です。5年分のレス見てみたけど　素人の私でも感動･･･
どうか、初見の方は、応援するだけしてゆっくりと見守ってほしいですな。

851:名無しさん＠５周年
09/12/27 16:53:19
分散型のソフトを開発したら皆さん参加しますか？
作ろうかどうか皆さんの反応で決めたいと思います。

852:名無しさん＠５周年
09/12/27 18:40:20
>>851
まず分散型じゃないソフトをつくるんだ！

853:名無しさん＠５周年
09/12/27 19:09:43
>>852
もう作って解析しております

854:名無しさん＠５周年
09/12/27 19:27:38
どれくらいの速度？

855:名無しさん＠５周年
09/12/27 21:18:30
解析って全探索？

856:名無しさん＠５周年
09/12/28 04:42:02
8×8のオセロが解析出来たら、
次は10×10のグランドオセロもおながいします

857:名無しさん＠５周年
09/12/28 23:37:24
てか VHDL とか論理回路で実装したらめっちゃはやくね？
INIT:
　own = 0x0000001000000000;
　opp = 0x0000000818080000;
　pStuck = 0;
　count = 0;
BEGIN:
　can = revchk(own,opp);
　if can goto SET;
PASS:
　{opp,own}={own,opp};
　can = revchk(own,opp);
　if can goto SET;
GAMEOVER:
　if pStuck==0 then halt;
　count++;
　{own,opp,can} = stuck[--pStuck]; //pop
　if can goto SET else BEGIN;
SET:
　set = least1(can);
　can = can & ~set;
　stuck[pStuck++] = {opp,own,can}; //stuck
　[opp,own] = setrev(own,opp,set);
　goto BEGIN;

858:857
09/12/28 23:39:02
これをこんな風に最適化して stuck, pop, goto BEGIN, halt が生じる間の計算を全部１クロックで実現可能。
BEGIN:
　}simultaneously if(!revchk(own,opp) && !revchk(opp,own) && !pStuck && stuck[pStuck-1].can){
　　{{own,opp,can}, stuck[pStuck], count} = {
　　　stuck[pStuck],
　　　{opp, own, revchk(own,opp) & ~least1(revchk(own,opp))},
　　　count+1
　　}; //pop and stuck
　}simultaneously if(!revchk(own,opp) && !revchk(opp,own) && !pStuck && !stuck[pStuck-1].can){
　　{{own,opp,can}, pStuck, count} = {stuck[pStuck], pStuck-1, count+1}; //pop
　}simultaneously if(revchk(own,opp)){
　　{{opp,own}, stuck[pStuck], pStuck} = {
　　　setrev(own,opp,~least1(revchk(own,opp))),
　　　{opp, own, revchk(own,opp) & ~least1(revchk(own,opp)),
　　　pStuck+1
　　}; //stuck
　}simultaneously if(revchk(own,opp) && !revchk(own,opp)){
　　{{own,opp}, stuck[pStuck], pStuck} = {
　　　setrev(opp,own,~least1(revchk(opp,own))),
　　　{own, opp, revchk(opp,own) & ~least1(revchk(opp,own)),
　　　pStuck+1
　　}; //stuck
　}else{
　　halt;// halt
　}
　goto BEGIN;
"simultaneously if" は同時に評価するってことね。
own(64), opp(64), can(64), stuck[pStuck](192), stuck[pStuck-1].can(64), count(233), pStuck(7) の
計 688 ビットの並列のフリップフロップと
(64+64+64)x64 = 12288 ビットのスタックメモリさえあればＯＫ

859:857
09/12/28 23:59:32
stuck ってなんだよ。stack だよ

860:名無しさん＠５周年
09/12/30 03:32:58
>>650
四隅空いた状態で勝ったことあるよ
珍しいから写メ撮った

861:名無しさん＠５周年
09/12/30 05:29:53
ああ、あのときね
なんで盤面撮らずに俺撮るんだろうと思ったけど
四隅空いた盤面よりそんな俺の顔の方が珍しいってか、あはは

お前馬鹿にしてんのか

862:名無しさん＠５周年
10/01/05 20:30:40
>>858 の感じで Verilog-HDL で記述した。
>>858 は結構間違い入ってるのが判明したけど。
4x4 のシミュレーションでちゃんと 60060 通りって出たから合ってると思う。

着手可能手探索＋石反転＋深化 or バックトラックを合わせて 1clk、
そのあとにメモリリードライトで 1clk という設計。
ほんとはこの２つをパイプラインにすればさらに半分になるんだけど。
探索完了まで 191,375 clk でした。
FPGA ってだいたい何 MHz までいけるんだっけ。
メモリを外付けにするならそこの I/O の時間も気になってくる。
ちなみに 4x4 の CPU シミュレーションだと 18 分かかります

863:名無しさん＠５周年
10/02/01 19:16:05
URLﾘﾝｸ(alfalia.web.fc2.com)

864:名無しさん＠５周年
10/02/26 11:12:45
あげるよ

865:名無しさん＠５周年
10/03/04 00:52:02
まだ発表されてないが８ｘ８オセロも後手必勝。
これは検証プロセスと論文準備の段階。
もうすぐパブリックレポート。

ちなみに６ｘ６も後手必勝。
これは結構前に発表されている。

866:名無しさん＠５周年
10/03/04 01:31:41
デタラメは要らないから。

867:名無しさん＠５周年
10/05/20 19:17:53
なんか話題ないの？

868:名無しさん＠５周年
10/05/20 22:44:58
試合結果は「勝」「負」「引き分け」の三通りしかないだろ。
試合経過はたくさんあるけど・・・