最小の碁盤サイズ

探索プログラムを作成してて疑問点が出てきました。
・●●●
という状態で○がパスした場合、●からは打つ手がないので終局となると
思いますが、この●は活きと判断していいのでしょうか？
（アゲハマが無い場合）活きならは黒の１目勝ちですが、死にならば○の３目勝ちだと思います。

コミに半目をつけると
「双方最善を尽くした上で、引き分け」という可能性も
うち砕いてしまうわけでしょ。

となると勝敗の結果に
「どちらかが（あるいは双方が）最善を尽くさなかったために勝敗が付いた」
すなわち実力の差の可能性と
「どちらも最善を尽くしたが白黒の優劣があったために勝敗が付いてしまった」
すなわち運の可能性が
折衷しちゃってるんだよね。

>129
コミに半目がついていたとしても、可能性としては
同型反復ループから外れたほうが損をするためそういう意味での
引き分けが双方にとっての最善となる可能性が残っているのでは？
またこの話題は別スレをたてたほうがが良いのでは

・●●● を活きと判定するのは無理があるように思います。
とすれば、・●・● から３に打つのは損なので、1x4 は無勝負ではないでしょうか？

これが正しいならば、

1x1 ジゴ
1x2 ジゴ（無勝負）
1x3 黒２目勝ち
1x4 ジゴ（無勝負）

となります。

http://kansas.ceser.hyogo-u.ac.jp/~sugiyama/cgi-bin/sin2_/index.html
この三国志ゲームかなりよくできているぞ！

少なくとも
＋●●●の形は死にだと思います。

でも
＋●＋●
この形は黒二目勝ちで終局じゃないの？
どうしてわざわざ打ち込むの？
（なんか俺、ものすっごい勘違いしてそうで怖い
仮にそーだったら優しく諭して下さい。市ねとか言わないで・・・）

コミの話だけど、特別な状況における無勝負は考慮しないことにすると、

コミ小数→最善をつくせばどっちか必勝
コミ適切な整数→最善をつくすと引き分け

ちなみに将棋などは前者で、最善をつくせばどっちか必勝

「最善をつくすと引き分け」の方が本来のゲームのあり方からすると適切なのは確かだが
「最善をつくせばどっちか必勝」の方を採用したところで所詮将棋レベルに落ちただけなので「おかしい」なんてことはない。

以上。新スレ立てるほどのものでもないかと。

>>133
＋●＋● （A）
からは○が３に打って、＋●○＋ となり、コウなので●はパス。
で、○＋○＋ となる。これは最初の状態（A）と同じ。
なので、（A）は●の２目勝ちではなく、無限ループで無勝負

（A）で●が３についで、○が取ってくれれば ○＋＋＋ となり●３に打って ○＋●＋（アゲ：○３）
となり●の１目勝ち。
これは

おまえらアフォか

>>135
自分の考えというか、書き込みに
もの凄い不安を感じたんだがそういうことか。
書き込む、ボタンを押す前に何かイヤーな感じがしたんです。
○が思いっきり３に打てるじゃないか！！！（ｗ
恥ずかしい恥ずかしい。何を勘違いしたのだろう。
無限ループで無勝負、だね、当然。
１さん応援してるから。
こんな勘違いするやつの力添えは役に立たんでしょうが（ｗ

>>137
いえいえ。
> ＋●●●の形は死にだと思います。
という賛同を得られただけでも心強い。

今、αβ探索のプログラム書いているので、1xN (N<255)については遅くとも今晩中には結論がでると思うよ
（if プログラムにバグ・勘違いがなければ）

＋●●●は、生きでしょう。
白からは手を出しても得をしない。
つまり、取られない石なのですから。

じゃ、○＋●＋ の○は？
○が死になら●の４目勝ち
●から２に打つと＋●●＋（アゲ：●１）で３目勝ち
ということは●が２にとっても得にならない。
>>139 が正しければ、○＋●＋ の○は活きってことにならないかい？

http://homepage2.nifty.com/S_HIASA/kiyaku_kaisyaku/kiyaku_zenbun.htm
には「相手方の着手により取られない石(A)、又は取られても新たに相手方に取られない石を生じうる石(B)は「活き石」という。」
とある。
少なくとも＋●●● は(A)には当てはまらない。
(B)はどういう意味なんだろう？

>>140
厳密に知りたいんだったら
ルールの死活判定ってところを探してみ
死活判定をしたときに、白が取っても黒の生き石ができる。
一方、○＋●＋はとられてオワだ。

取られないというのはそういう部分も含めて言ったつもりだったけど
まあ、説明不足でｽﾏｿ

>>141
(B)ってのはまさにこの形のようなことを指している。

やっと意味がわかった。

○＋＋＋ と取られても、○＋●＋ と打てば、新たに取られない石を生じたことになる。
よって、＋●●● は活き石ですね。

○＋●＋ は新たに取られない石を生じないので○は死にってことだ。

thanx >>142, >>143

ってことは、探索プログラム書き換えなきゃ。。。

>>145
どういたしまして。
まあ俺もこのスレはレス一桁の頃からいるもんで
応援してるんよ。

>応援してるんよ。
ありがと～

おかげで、1xN（N>=2）探索プログラムは動作するようになった
結果は、
1x2 ジゴ
1x3 黒２目勝ち
1x4 黒２目勝ち
となったので、それらしく動作している。

が、1x5 では場合の数が爆発してなかなか結果が出ない。
パフォーマンス向上作業をしないとだめだ。
＃ 1x100 は遠い。。。

同型反復チェックは入れてるよな？
盤上のパターンは、3^5以下に収まると思うんだが。

> 同型反復チェックは入れてるよな？
いや、今はループチェックだけで、探索済み局面の登録とチェックは行っていない。
> 盤上のパターンは、3^5以下に収まると思うんだが。
1x3 の場合はそうだが（厳密には対象性を考慮すれば、もっと減るけど）、
1x100 だと 3^100 とかになってしまい、探索済み局面を全てメモリに持つのは不可能だと思う

う～ん、どうしようかな。。。

現在は縦型αβ探索を行っているけど、囲碁の場合手順を変えても同じ局面に
なるので、手順が異なるのに同一局面になり、単純な縦型探索は非効率ってことみたいだ。
探索済み局面をメモリに登録しながらの反復深化がいいのかな？

一般的なパターンが有るかどうかをまず調べるなら、
100にこだわることはない。
もっと少ない数、10くらいまでの結論を出すのが良いと思う。

小路の場合は、コウではないタイプの無限反復が多いし、
局面の保持は必須と思われ。

考えてみたら 1x100 って空点の数は10路盤と同じなんだよね。
これが単純に読みきれることは到底考えられないね。
（着手の幅が狭く、任意にパスできないオセロでも 6x6 が数年前に解かれたくらい）
なので、
＞もっと少ない数、10くらいまでの結論を出すのが良いと思う。
その通りだね。
今からコーディングしてみるよ。

探索済み局面を保存するようにコーディングしたんだけどループしている場合の処理がうまくいかない。
今日は疲れたのでもう寝る。

頑張れ１。結構見守ってる人多いぞ。
と、思うぞ（ﾜﾗ

ありがと (^^;;
とりあえず今現在わかっていることを記述しておくので、間違いがあったら指摘してちょうだい。

・探索するのは、初期状態（盤面が全て空）から囲碁のルールに従って局面を生成した有向グラフ
・状態は、(1)次の手番（黒｜白）、(2)盤面の升目の状態（空｜黒｜白）、(3)コウ、(4)アゲ石数（黒－白）で指定される
・双方着手不可能な場合が存在し（例：＋●●＋）、その状態は末端ノードとなる
末端ノードは地の計算を行うことが可能で評価値（黒字－白地＋アゲ石数）が確定する
・グラフは偶数長でループすることがある
アゲ石数が異なるだけで他は同じ状態に戻る場合もある。これもループとみなす。
・長さ２のループは（コウを含まず）双方パスした場合で、末端ノードとして処理可能で評価値が確定する

（続き）
コウが含まれると一見長さ２のループのようだが、コウ状態が異なるのでループではない
例 黒番：○＋ → (A)白番：＋●（コウ） → 黒番：＋● → (B)白番：＋●
(A),(B) は手番、盤面状態、アゲ石数が同じだが、コウ状態が異なるので、同一状態ではなく長さ２のループではない

・長さ＞２でループする場合がある
黒番：○＋ ２→ 白番：＋●（コウ） Ｐ→ 黒番：●＋ Ｐ→ 白番：＋● １→
黒番：○＋（コウ） Ｐ→ 白番：○＋ Ｐ→ 黒番：○＋（最初の状態）

（多分）上記の長さ６のループが最小サイズで、長さ４のループは存在しない
長さが２より大きいループは無勝負（評価値は０）
（長さが２より大きいループの場合アゲ石数は無視してもよい）

（続き）
ゲーム有効グラフの各ノードについて、
黒番の場合、そこから生成可能なノードの評価値の最大値が状態の評価値になる
白番の場合は最小値

すべての状態の評価値を求めると最善手順が決まる
（αβ探索を行えば、必ずしも全てのノードの評価値をもとめなくともよい）

現状の問題
深さ優先探索を行い、末端状態からMIN-MAX評価を行い、順にノードの評価値を決めていくことができる
しかし、長さ＞２のループがあると評価値が不正になる場合がある
例：
白番：＋●＋＋ Ｐ→ 黒番＋●＋＋ ３→ 白番＋●●＋ … 黒番：○＋＋＋ Ｐ→
白番：○＋＋＋ … 白番：○＋○○ Ｐ→ 黒番：○＋○○ ２→ ＋●＋＋（最初の状態）
(A) からは他の分岐がなくループが必然なので評価値が０になる（アゲ石数を考慮すれば＋３）
しかし、白番：＋●＋＋の本当の評価値は＋２なので、黒番：○＋○○ は＋５でなくてはいけない

つまり、無限ループ＝評価値０としているところに問題があるわけだ。
でも、どうしたらいいんだろう。。。
（パス以外に）分岐がない場合は評価値が確定していないとすればいいのかな？

ここにまとめを書いて、考えを整理したのがよかったのか、
プログラムがなんとか動作するようになったよ。
これもみんなの応援のおかげだ。ありがと～

結果：
1x2 ジゴ
1x3 黒2目勝ち
1x4 黒2目勝ち
1x5 ジゴ
となった。
1x6 はなかなか答えがでない。ループ処理をもうちょっとなんとかするなど
パフォーマンスチューニングをやんないといけないようだ。

頑張ってくれ。
取り敢えず1x5まではあってるみたいだし。

> 頑張ってくれ。
さんきゅ
1x10 までの解くのを当面の目標に、ひまを見つけてはプログラムを改良するよ。

ところで、ソース（C++）が欲しい人にはあげるけど、どこに置けばいいのかな？

ガンガレーage

探索アルゴリズムについてWebで調べていたら、小さい碁盤に関する研究報告を発見した。
TRorp と Walden (1964, 1972) によれば、以下の通りだそうだ。

1x4k 黒の勝ち
1x4k-1 黒の勝ち
1x4k-2 引き分け
1x4k-3 引き分け
2x2 引き分け
2x3 引き分け（パスが最善）
2x4 黒の勝ち（中央の一点のどれか）
3x3 黒の勝ち

30年以上前に結果が出てたのね。。。

TRorp じゃなくて、Thorp が正しい
しかし、話が古すぎてオリジナル論文が見つからない。。。

これまでの研究が結構あってたってことがわかっただけでも良かったじゃないか。
2xｎという一般化は出来てないんだな。
ま、一行が一般化できるのは石が触れたら必ずアタリ、という特殊性
に依存しているからなんだろう。

>>166
うん、そうだね。
すくなくとも >>79 の
１ｘ４N　　　　　　　　　 は黒一目勝ち
１ｘ４N＋１　　　　　　　はジゴ
１ｘ４N＋２　　　　　　　はジゴ
１ｘ４N＋３　　　　　　　は黒一目勝ち
（N≧１）
は Thorp と Walden の研究と矛盾しない

>>1さんてあの人だったのか。
意外だ。わしはROMなのだが。

>>168
ハァ？

まだ、1x10 まで解けていないのだが、少し進歩したので、現状を報告しておこう
(1) （単純な）MIN-MAX法による評価
1x2 引き分け（パスが最善）、探索ノード数：5、深さ：5
1x3 ２で黒＋２、探索ノード数：54、深さ：7
1x4 ２で黒＋２、探索ノード数：2157、深さ：18
1x5 不明、探索深さ：56以上

(2) αβ法による評価
1x2 引き分け（パスが最善）、探索ノード数：5、深さ：3
1x3 ２で黒＋２、探索ノード数：35、深さ：5
1x4 ２で黒＋２、探索ノード数：266、深さ：13
1x5 ２で引き分け、探索ノード数：2,082、深さ：26
1x6 ２で引き分け、探索ノード数：183,205、深さ：54
不明、探索深さ：124以上

αβ法により探索ノード数が大幅に減り（1x4 の場合は 2,157→266）、1x6 までの結果が判明した。

>>168
漏れの勘違いか。ｽﾏｿ

がんばってくだされ

ageﾎｾﾞｰﾝ

おまえら、その勢いで普通のご勉強したらどうだ？　　　　　　　と。

ちなみに1×7路盤で
＋●＋●＋○＋　となった場合にどこが黒地でどこが白地なのでしょうか？
＋●＋○＋●＋　は盤上セキで引き分けと思えるのだが、上の図の解釈は
いかに？

また1×11路盤ではその判定がさらに微妙となる感じがするのだが
どの図で黒勝ちといえるのかもし分かれば教えて欲しい。

＋●＋●＋○＋
白から打つとしたら
＋●＋●☆○＋
＋●＋●＋＋★
＋●＋●＋☆＋
で、元に戻る。あるいは、
＋●＋●＋○☆
＋●＋●★＋＋
＋●＋●●☆＋
＋●＋●●＋★
＋●＋●●★●（白パス）
＋●☆＋＋＋＋
＋●＋★＋＋＋
＋●＋●＋☆＋
で、元に戻る。つまり白は手出しできない。黒から打つとしたら
＋●＋●★○＋
＋●☆＋＋○＋
＋●＋★＋○＋
で、元に戻る。つまり黒も手出しできない。
しかし、

＋■＋▲＋△＋
どの場合に置いても、■の石は取られることはない。
▲と△の石は、どちらから打っても自分が取られてしまう。
つまり、▲と△の石でセキが成り立っていると考えられる。

＊●＋●＋○＋
よって＊の部分は黒の地。ゆえに黒１目勝ち。

だと思うんだけど‥‥。読みが難しい。

176　様　
私もそのように思ったのですがすると
＋＋＋＋＋＋＋＋＋＋＋
＋＋＋★＋＋＋＋＋＋＋
＋☆＋●＋＋＋＋＋＋＋
＋○＋●＋＋＋★＋＋＋
＋○＋●＋＋＋●＋☆＋
＋○＋●＋★＋●＋○＋
もセキに思えるし、黒の作戦を
変えたとしても現時点では黒勝ち
と思える図ができないのですがだれか
わかりますか？