俺主催囲碁プログラミングコンテスト

1 名前：デフォルトの名無しさん [02/06/14 12:17] 俺に勝てたら、賞金が出ます 255 名前：デフォルトの名無しさん [02/10/18 22:03] ようするに手を全部データベース化して１手づつ検索かければ必勝なんだろ。 全部の手をデータベースにすんのって何バイト必要なんだろ？ ２０＊２０＊〜〜〜〜〜〜？？？わかんね 256 名前：デフォルトの名無しさん [02/10/18 22:05] 3^(19*19) > 2^400 = 1024^390 > 10^(3*390) 単純計算すると ０が１０００個くらいつくのかな？ 257 名前：デフォルトの名無しさん [02/10/20 20:43] 囲碁ってルールの実装がめちゃムズ コウが組み込めない。 258 名前：デフォルトの名無しさん mailto:sage [02/10/20 20:55] コウ：その手でﾊﾞﾝﾒﾝが前と同じになったら打てない。 簡単そうだが。 259 名前：デフォルトの名無しさん [02/10/20 21:17] 全部記録しておけばいいの？ それって非効率的な気がして。 260 名前：デフォルトの名無しさん mailto:age [02/10/20 21:21] 石を置いた付近に限定して記憶すればいいのでは？ 261 名前：デフォルトの名無しさん mailto:age [02/10/20 21:24] 置いた石から上下左右一目の石の配置を記憶。 262 名前：minikat [02/10/20 21:26] コウは日本ルールとスーパーコウルールなら読む深さが違うし、 スピードアップにどんなアルゴリズムを使うかで議論があるでしょう。 ＡＩ囲碁のDavid Fotlandはシンプルコウルール判断（日本/韓国？）で充分といっていますが。 普通はＨａｓｈで保存した局面をさかのぼり同一局面をチェックかな？ 場所とか１個取ったとかの条件判断はこんがらがりますね。 263 名前：デフォルトの名無しさん [02/10/20 23:01] >>262 ハッシュ関数はどんなのを使えばいいの？ 264 名前：デフォルトの名無しさん [02/10/20 23:02] スピードアップにどんな意味があるんだろうか・・・・ 265 名前：デフォルトの名無しさん mailto:sage [02/10/20 23:03] ＣＰＵの思考速度。 266 名前：デフォルトの名無しさん [02/10/20 23:25] 評価関数＋αβ探索だけでやっても ほとんど何も上手くいかない・・・ なんで？ 評価関数がダメなのかな。 267 名前：デフォルトの名無しさん mailto:sage [02/10/20 23:38] 日本ルールに限定するなら、 抜いた石が一個の時にコウフラグを立てて位置を記憶すればいいのでは。 268 名前：デフォルトの名無しさん [02/10/20 23:51] www.google.co.jp/search?q=cache:m1o_rVb098YC:www.edu.ipc.hiroshima-cu.ac.jp/~f23006/SOTAGE/5/game.html+%CE%B1%CE%B2%E6%8E%A2%E7%B4%A2%E3%80%80%E5%9B%B2%E7%A2%81&hl=ja&ie=UTF-8 との事。 269 名前：デフォルトの名無しさん [02/10/21 08:06] １．最初にランダム数（３２ビットか６４ビット）を決め、着手（整数）とＸＯＲ で次局面、戻るにはまたＸＯＲで戻る。チェスプログラマーの良くやる手です。 コウフラグ等よりも早いでしょう。コンピュータ囲碁の初期にＺｏｂｒｉｓｔが 提唱しました。英文が各所にあります。検索はzobrisy keyで。 ただし、私は使っていませんが。 局所的にαβ探索、例えば詰め碁をやれば１命令でも早くしたいものです。 局面記憶もＸＯＲで簡単ですね。グラフィックの重ね合わせと同じでしょう。 私も１０数年ぶりに囲碁プログラム再開しましたのでよろしく。 270 名前：minikat [02/10/21 08:09] 269です。書き忘れましたが、５*５は完全読みで黒２５目勝ちが読みきれたそうです。 次は7*7か？もちろん枝はうまく刈りますが。 271 名前：minikat [02/10/21 08:12] すみません。タイプミスです。 Zobristが正解。 272 名前：デフォルトの名無しさん [02/10/21 11:32] >>269 なんかできそうな、できなさそうな。 少し考えないと理解できなさそうです。 何も打たれていない状態のハッシュコードをSとして、 次局面のハッシュコードS'を、打たれた手をAとして S' = S xor A とするわけですね。 でも、石の配置が同じ局面でも 異なったハッシュコードを持ちそうな気がするのですが、 どうでしょうか？ 石が一度も取られなければ、 S→A→S'→A'→S'' S''=S xor A xor A'=S xor A' xor A という事は理解できますが。 273 名前：minikat [02/10/21 12:01] 自分は使っていないが、コードの衝突は起こらないはず。 同一ゲームなら同じコードになります。あくまでそのゲーム のチェック用ということで、新たなゲームでは最初の乱数が違うから コードももちろん違う。３コウでも６手さかのぼるだけかな？ とにかくコウの場所、フラグ等は先読みからの手戻りで単純化できないから 不利と思います。 ボクもルールは自殺手などややこしいので日本ルールのみ考えています。 それから配列は１次元がたやすいですね。 274 名前：デフォルトの名無しさん [02/10/21 21:50] >>273 とりあえず勘違いしてるかも。 そのやり方で作るのはハッシュコード。 使い方は、 ある時点までの局面をすべて保存しておく際に ハッシュコードで区別しながら保存する。 history[board.getHashcode()%HASHSIZE].add(board) で、次の一手を指した後の局面のハッシュコードを計算して そこの配列？の中に同一局面があるかどうかを調べる。 あれば同型反復禁止で、そこには置けない。 xorは a xor b xor c.... = b xor a xor c.... なので おそらく 石を取り除く時もxorをするのだと思う。 そうするると 同じ盤面であれば同じハッシュコードが作れる。 まあ、要するに int getHashcode(int board[][]){ int start=0; for(int i=0;i<board.length;i++){ for(int j=0;j<board[i].length;j++){ if(board[i][j]==black)start=start xor (i*j); else if(board[i][j]==white)start = start xor (-i*j); } } return start; } って事なんだけどね。 i*jの部分は工夫して作らないとだめだけど。 275 名前：minikat [02/10/21 23:31] コードと書いてあるので別に勘違いはしていません、と思います。 その後比較するのは当然。焦点はコードの出し方。 テーブルの保存方法やルールで後戻りが違ってくるのはプログラムで 変わる。言いたいのは別にＸＯＲ使わなくても局面を表現できる 整数値が違えばいいということ。もっといい方法があるかもね。 自分も最初は１個取ったとか場所がどうとか考えたがこれが最速で 簡単。自分はパターン照合の関係でつかっていない。 ＸＯＲといえば　手番＝手番　ＸＯＲ　３ででる。黒１白２の場合。 手番＝３−手番でも可だが。 もっといろいろ話しましょう。 276 名前：minikat [02/10/22 00:42] 追加です。 ２７４のコ−ドで気が付いたがgetＨashcodeは盤面を全走査 していますが、現局面と現着手のXORだけでいいのでは？ 最初に配列の位置に乱数を割り当てて１手（位置、石）のみＸＯＲをとる。 もう一度着手（位置、石）ＸＯＲで前局面に戻る。 アゲ石処理でＸＯＲ消去はもちろん必要だが。XOR　1命令で再走査がいらないところに 値打ちがあるように思います。 コード書いていないだけに間違っていたらスマン。 277 名前：デフォルトの名無しさん [02/10/22 09:34] >コードと書いてあるので別に勘違いはしていません、と思います。 了解 >>２７４のコ−ドで気が付いたがgetＨashcodeは盤面を全走査 結局のところは全走査する事で実現できる＝手順によらない という事を言いたかった。 実際は、 すべての局面を記録していくわけだけど、 その際、同時にhashcodeを生成してしまえばいいわけだよね。 石がとられたら、その分もxorで。 自分のは今のところ速度にこだわっていないので これを実装するかどうかは未定かな。 今、考えてる事は、 探索の打ち切りとか、もっと深く読むとか。 278 名前：デフォルトの名無しさん [02/10/22 11:24] 囲碁のプログラムをやっとの事で完成させて 19*19で動かしてみると その大きさに愕然とする。 そして、ほとんどの人がやめていく。 279 名前：デフォルトの名無しさん [02/10/22 11:25] 局地戦ならともかく、布石とかは相当厄介だと思われ。 280 名前：デフォルトの名無しさん mailto:sage [02/10/22 11:50] 布石ぐらいだったらデータベースで何とかできそうな気はするけど。 やっぱり死活でしょう。 攻め合いとかコウとか。 281 名前：デフォルトの名無しさん mailto:sage [02/10/22 12:00] 別の隅を評価しながらの布石は、結構厄介だった。 282 名前：デフォルトの名無しさん mailto:sage [02/10/22 17:17] >>281 それはかなり高度な部類に入るかと・・・。 実際、それを生かすだけの棋力を持つプログラムは存在しないと思われ。 283 名前：278 [02/10/22 18:49] 定石データベース＋αβ探索だけで囲碁を作って見て思ったんだけど、 人間の脳ってなんであんなにすごいんだ？ 284 名前：デフォルトの名無しさん mailto:sage [02/10/22 19:13] 囲碁は特に画面認識とか、人間の脳に向いている作業が多いからね。 しかし、αβということはまともに探索してるの？ それはすごいね。 285 名前：デフォルトの名無しさん mailto:age [02/10/22 20:03] 学習して、自ら改善するっていうプログラムじゃないんだよねぇ。 なら、実際に打ってみて足りない点を逐一カバーしていくってのが いいと思うよ。 つーわけで、遊ばせてくださイ。ちゃんと報告するから。 　　　　　　　　　　　　よろしく。 286 名前：278 [02/10/22 20:16] ２ｃｈネラーだという事がばれると なんか恥ずかしいのでそれは勘弁して>>285 それに、弱すぎてやっても意味ない。 αβに関してだけど、現状の評価関数だとほとんどやっても意味ないかも。 コンピューター同士で対戦させて どのくらい読みが的中するのかを調べたところ 打つ場所の残りが１０箇所くらいになって 当たりだすくらい。 それに１９＊１９だと 最初の幅優先探索がえらく時間がかかる。 それをふまえて、自分がどうやっているのか 検証してみたんだけど・・・・ 287 名前：デフォルトの名無しさん [02/10/22 21:48] 無料の囲碁のフレームワークってないですかねぇ。 ルールを組み込むのがすごく大変で。 288 名前：デフォルトの名無しさん mailto:sage [02/10/22 22:35] ここを見てみたら。 www.inventivity.com/OpenGo/ 289 名前：デフォルトの名無しさん [02/10/23 00:45] >>288 ありがと。 これでAI作りに専念できそうです。 まずは探索から実装してみます。 290 名前：minikat [02/10/23 08:22] ルールは狭義には、コウと自殺手判断ぐらい。厳密には終局計算を含む。 昔アップルIIの囲碁ソフトはウッテガエシが打てなかったよ。 返品しようとおもったがそれ以外なかった。 どのルールも１石の自殺手はできないがSSTルールやニュージーランドルール は認めている。 日本ルールではセキは地にならないが、中国ルールではなる。 とにかく市販ソフトでもセキ判断は完全でないのでルールが完璧とは いえないのでこちらまかせ。　 でもルール作りのハードルが高いならシチョウ、ゲタなんてもっと大変よ。 がんばってください。 291 名前：minikat [02/10/23 09:08] ＞＞どのルールも１石の自殺手はできないがSSTルールやニュージーランドルール は認めている。 スマン。表現がおかしい。 多石の自殺手を認めているという意味。 292 名前：デフォルトの名無しさん [02/10/23 09:59] ルールなんか 日本ルールに 決まってるだろ 293 名前：デフォルトの名無しさん [02/10/23 10:02] とりあえず五路地盤のを作ってみたら？ 294 名前：ニュージーラン土人 mailto:sage [02/10/23 11:32] ジャップ消すゾ 295 名前：デフォルトの名無しさん [02/10/23 22:47] もう少しにぎやかにならないかな。 296 名前：デフォルトの名無しさん [02/10/23 22:52] 着手生成アルゴリズムってどんなのがあるの？ 297 名前：デフォルトの名無しさん mailto:sage [02/10/23 23:06] パターンが楽なんじゃないの？ こんな形は１間で、これは2間、ケイマ、とか色々。 298 名前：デフォルトの名無しさん [02/10/25 00:32] 候補手列挙を学習する方法ってない？ 例えば、パターンだったら 探索した結果良いものを集めてデータベース化していくと。 でも、パターンだとマッチングが大変じゃない？ ある点が候補としてあげられるかは その点の付近のパターンを、データベースで比較しなくてはならない。 ハッシュを使えばいいのかな。 299 名前：デフォルトの名無しさん mailto:sage [02/10/25 01:57] 学習だったらプロ棋士の棋譜を使えばいいんじゃない？ たしか公開されてたはずだしね。 パターンマッチングの高速化はどうするんだろうね。 データベースをハッシュでまとめてしまえば高速で可能なような気もする。 完全一致から似ている形まで、とかなると難しそうだけど。 あと、単純なパターンだとうまくいかないかもね。 この石はシチョウで取られる、とか、ダメが２以上ある、とか 色々な情報をパターンの中に組み込む必要があるかも。 ここに打った場合の手順とかも。 300 名前：デフォルトの名無しさん [02/10/25 02:22] データがあっても、アルゴリズムがないとね（藁 似ている物まで探してくるのは無理だと思うなぁ。 似ているの基準から定義しないとわからんけど。 >あと、単純なパターンだとうまくいかないかもね。 候補を列挙するだけだからいいんじゃない？ あとは、それを探索するだけ。 301 名前：minikat [02/10/25 06:16] ハッシュよりも実プログラムでは２分木探索が速いという報告もありムヅ。 普通に照合するよりは何十倍か早いだろうけど。 パターンは骨格と肉付けがあり、２０年前の同級生で様子が違ってもある程度 認識できるのと似ている。黒、白、空点と、黒白空点どちらでもいいというのが厄介。 rotationで８種類、反転で１６種類ある。広さの問題もあるなあ。 人間は碁をやって入ればますます、パターン認識は早くなるが、機械は照合に ドンドン時間が食われる。ここに根本的な問題ありだろ。 AI囲碁で２０００くらい。最初手入力してたらしいが途中からBITMAPにして グラフィックエディターで入力したらしい。うまいね。 302 名前：デフォルトの名無しさん mailto:sage [02/10/25 08:44] 学習のアルゴリズムかぁ。 分からんね（ｗ 完全一致で出現した回数とかなら簡単だけど。 大量の棋譜から学習で楽をしよう、というのは誰もが誘われる麻薬みたいな もの？だが実際は少数のパターンを人間が自分で判断して打ち込んだほうが 精度の高いものが出来そうな気もする。 何より、プログラムがその手をなぜ打ったかを推理できるからね。 303 名前：デフォルトの名無しさん [02/10/25 11:12] >ハッシュよりも実プログラムでは２分木探索が速いという報告もありムヅ。 ２分木にする時のキーとして、何を使うの？ それがハッシュコードなら ハッシュテーブルの大きさによると思うよ。 似てる物を集めてくるのはちょっとつらいよね。 >だが実際は少数のパターンを人間が自分で判断して打ち込んだほうが >精度の高いものが出来そうな気もする。 おそらくそうだと思う。 だから、外からのデータを与えるんじゃなくて 自分でデータを生成検証して、候補手を生成するアルゴリズムを 学習するようなものがいいね。 304 名前：デフォルトの名無しさん [02/10/25 13:04] あらかじめ、全ての手を計算しておいて、データベース化しておく。 データベースの構築には、膨大な計算力とディスクスペースが必要なので、 SETIのように分散処理で解決。 データベースができた後は、最善手のみが打てる。 一度プロジェクト起こしてみては？ それなりに金になると思うぞ。 あと、首謀者は地位と名誉も得られる。 305 名前：デフォルトの名無しさん [02/10/25 13:06] もし、それで碁の必勝法がみつかれば、歴史に名が残るね。 少ない資金で多大な効果が得られる、数少ないプロジェクト。 早い者勝ちだぞ。 306 名前：デフォルトの名無しさん mailto:sage [02/10/25 13:08] 相手が知ってたら意味ないじゃ〜ん 307 名前：デフォルトの名無しさん mailto:sage [02/10/25 13:12] お前ら・・・囲碁の可能な局面の数は 3^19^2 = 10^230 にもなるんだぞっと。 308 名前：デフォルトの名無しさん mailto:sage [02/10/25 13:15] 完全解析したらゲーム自体消滅 309 名前：デフォルトの名無しさん [02/10/25 13:37] 3^19^2 ＝ 1350851717672992089 ≒ 10^18 1千万台(10^7台)のコンピュータを使えば、10^11回の演算で済む。 1台のコンピュータが1秒に3170回の演算が行えるとして、10年間。 現行の性能では難しいが、将来は可能になるかもしれない。 可能になった時点で、誰が先に演算を終えるか？ 先に演算を始めた者に決まってる。 310 名前：デフォルトの名無しさん [02/10/25 13:39] オセロならもっと早く演算が終了する。 早い者勝ちだぞ。 ゲームを消滅させろ。 311 名前：minikat [02/10/25 15:03] >>２分木にする時のキーとして、何を使うの？ パターンをbit化すればいいのと違うかな？ >>ハッシュテーブルの大きさによると思うよ。 そうだね。やって見ないとわからない。ハッシュの計算や衝突の際の探索も時間がかかるし。 でも２，３千のパターンではアマ初段には間に合わない。 瀬越の手筋辞典や官子譜見たらとんでもない筋やパターンがでている。 NHK囲碁の解説聞いていても「これは筋ですねえ」といわれても、知らない、わからない のが結構多い。筋の定義もムズだが、パターンとも共通性があるし。 コスミ自体は１種類しかないが、周りの状況でヨセからワタリ等等役目はゴマンと ある。要するにパターンは目的を入れないと絵に描いたモチ。 312 名前：デフォルトの名無しさん [02/10/25 15:09] 分散処理で計算する方法は考えたんだけどさ、 黒（自分）が最善手を常に打つとして、 白（敵）が最善かどうかわからない手を打つとすると 19*19では (19*19-1)*(19*19-3)*(19*19-5)....となる。 これを300*300*300......(19*19-100) と近似しても激しい値になる。 コレをどこへ保存すればいいのだろうか？ 地球上のコンピューターをすべて集めてきても 保存できない。 >3^19^2 ＝ 1350851717672992089 ≒ 10^18 コレ間違ってるよ。 3^(19*19) > 2^400 log10 2^10=3 log10 2^400 =120 まあ120桁はあるな。 313 名前：デフォルトの名無しさん mailto:sage [02/10/25 15:15] 爺さんの楽しみが無くなるなあ〜 314 名前：デフォルトの名無しさん [02/10/25 15:23] 賞金 １００円 みんな ガンバレ〜〜 315 名前：デフォルトの名無しさん [02/10/25 15:27] >>311 候補手といっても、いろいろなレベルがあると思う。 例えば、どの手を選んでも悪手にはならない 候補手の列挙から どの手を選んでも良い手であるような 候補手の列挙から・・・ あるいは攻撃的な手だけを列挙できるようになるのも 有効だし 守備的な手だけを列挙できるようになるのも有効だね。 候補手が列挙できたら、あとは探索するのみ。 316 名前：デフォルトの名無しさん [02/10/25 15:36] 今考えてるのは 精度の粗い候補手列挙システム （つまり、悪手は切り捨てるけど良手は絶対に切り捨ててはいけない。 判定不能の物は残す） と 高機能なαβサーチの組み合わせでの アルゴリズムを作ろうと思ってる。 候補手列挙は、やっぱり周辺パターンのデータベースしか ないのかな。 候補手列挙で一つ思いついたのは、 応手作成アルゴリズム。 相手の手を、どんな手なのか予測分類して （２つに分類するなら、攻撃的か守備的か） 候補手を列挙する。 まあ、まだアイディアを練ってる段階だけど 317 名前：デフォルトの名無しさん mailto:sage [02/10/25 19:09] 絶妙手をも切り落とさないシステムだと大変かもね。 そういう手は弱いレベルには悪手だから。 プログラムの棋力にふさわしい普通の手が10手から20手程度抽出できれば 十分じゃないかな。 囲碁はまだそれほど深く読めないので（シチョウは除いて） 探索手法自体の重要性は低いと思われ。 やはり最大の難関は評価関数かと。 地の判定から、石の連絡、強弱、空間の支配力、 この辺を適当に数値化しないといけないからね。 318 名前：デフォルトの名無しさん [02/10/25 21:30] >>317 俺は(中盤の）評価関数の作成が無理だと思うんだよね。 評価関数の作成が将棋と同程度の難しさなら、 現状のルールベースの候補手生成アルゴリズムと組み合わせれば きっと将棋と同程度の強さになってると思うんだ。 探索空間の広さが同程度になると思うから。 囲碁は、終盤に近づくほど評価関数が正確な値を示すようになってくる(気がする）が 序盤では定石に頼らないとまったく打てない（はず）。 それは定石データベースを持たない囲碁プログラムを作れば おのずとわかると思う。 という事は、評価関数の精度をあげるには深く読んでみる事が 一つの方法であると思う。 そこで、いかに有効な手を深く読むかが重要だと思う。 評価関数が曖昧と仮定している以上、αβサーチは使えない。 じゃあ、どうするかというと、深く読む。 どうやって幅を絞るかというと・・・ アイディアはあるけど今は暖め中という事で。 >そういう手は弱いレベルには悪手だから。 絶対評価と相対評価がメチャクチャになってるかもね。 人間にとって一見悪手にみえるが良い手である手を妙手という？から それがコンピューターにとって妙手かといえば、違うと思う。 目指すは”最強”なのでｗ 319 名前：minikat [02/10/25 23:46] 例えば、１０年くらい前の棋道で趙治勲の読みの内容に関するする連載があったが、 プロでも驚くところまで読んでいる。多分、プロの頭には過去の膨大な筋や パターンと、ものすごい読む力が備わっている。全部の可能着手数なんて考える必要ないんだ。 反面、故岩本九段のようにパラパラ打って碁にする棋風もあるが。それは一言で言えば、バランス。 理論でもいいから趙さんの読みの深さまで深化できるアルゴリズムでなければ 先の見通しは暗い。 評価関数でいえば、人間は盤面計算や評価を毎着手やっていないでしょ。 一段落したところでやる。それまでは手順をつくすか、ある死活なら死活に集中する。 その意味でプログラムは人間を徹底的に模倣し、攻めあいや終盤計算等の得意分野で人間を追い越さ なければいつまでたっても初心者レベル。と思う。 それから今のプログラムはエントロピーが低い。着手に多様性がないからプログラムは かならずこう来るんだ。とか読まれてしまう。ノゾキにいつもツグぐようなものやね。 プロでも道策にケイマにカケられて安井家はいつも下うけでこなされる。 道策の深読みと多様性についていけない。この２点をどう表現するか。 320 名前：デフォルトの名無しさん [02/10/26 00:02] 多様性に関しては学習なのかな。 負けたゲームから何かを学ぶ。 少なくても、相手が同じ事をしてきたら それに対して何か別の策をこうじるようにならないと。 まあ、それができるなら 永遠とコンピューター同士で学習すると 最強になってしまうんだけど。 321 名前：デフォルトの名無しさん mailto:sage [02/10/26 02:33] 深く読むかぁ。 何手ぐらい読めば妥当なんだろうね。 >>319さんの言うように当然の手順、というのを抽出できれば それに沿って読みさえすれば5手、10手、20手先の局面でも 正確に読めそうな気もする。 この場合、地合でなく、戦いを重視したプログラム、ということになるのかな。 322 名前：デフォルトの名無しさん [02/10/26 08:15] 実際に人間は何手くらい読んでるのかな？ 俺は囲碁初心者だけど ぱっとみで候補が５くらいあがって そして７手先くらいは読んでるね。 確かに、読みっていうのは そこへ打っても大丈夫かといった チェックをしているような気がする。 つまり、感覚だけである種の最善手がはじき出されている。 323 名前：デフォルトの名無しさん [02/10/26 19:03] >この場合、地合でなく、戦いを重視したプログラム、ということになるのかな。 それは、当然の手順＝最適な手順がなんなのかによりそう。 324 名前：デフォルトの名無しさん mailto:sage [02/10/26 21:31] 将棋や囲碁では、状態をイメージ（画像）として捕らえるような作業を 人間は行っているだろうね。陣形とか、血合とか。 以前ちょっと考えたことがあるのが、上記の考えを元に、 盤面を白黒で２分割、４分割・・・１６分割くらいして、 （分割はそれぞれが優勢な部分を中心とする） そのそれぞれのブロックで、細かい判定を行うというもの。 でも、すでに他の人が同じような研究を行っていたという罠。 325 名前：デフォルトの名無しさん [02/10/26 21:55] >>324 白黒で・・・ってどういう意味ですか？ これだけだと実装の仕方だけでもいろいろあると思うから 他の人が研究してようが問題ないのでは？ たとえば、優勢な部分を判定するアルゴリズムが大きく効いてそうだし 細かい判定で何を判定するのかによっても全然違うものが でき上がると思うよ。 俺には作れなさそうだ。 326 名前：デフォルトの名無しさん [02/10/27 19:33] いい加減な事を書くなよ 327 名前：名無しさんに接続中… [02/10/27 21:09] 囲碁の場合、アバウトなイメージだから難しい。 将棋の場合は、駒がぶつかったら「取る」ことを考えるし 王手をかけられたら「避ける」しかないので必然の手がある 囲碁の場合は１マスぐらいずらして打っても構わないので これをプログラミングするのは難しいだろうな 328 名前：デフォルトの名無しさん [02/10/29 00:20] 学習といえば、ニューラルネット使った奴が けっこういい成績残したね。 俺にはｻﾊﾟｰﾘなんですが。 329 名前：デフォルトの名無しさん mailto:sage [02/10/29 10:50] どこかに論文があったと思うよ。 あった。ここ。 www.markus-enzenberger.de/compgo.html 330 名前：デフォルトの名無しさん mailto:sage [02/10/30 23:25] とうとう7行に収まったようです。 pc3.2ch.net/test/read.cgi/tech/1033143528/530 331 名前： [02/11/01 03:48] コンクール・コンテスト総合掲示板 jbbs.shitaraba.com/music/3054/ 332 名前：1 [02/11/01 10:36] 結局、俺に勝てる囲碁プログラムを作れた奴はいないのか。 ２ｃｈってバカばっか。 333 名前：デフォルトの名無しさん mailto:sage [02/11/01 12:06] >>332 結局、自分に勝てる囲碁プログラムを作れた1はいないのか。 2chってバカばっか。 334 名前：デフォルトの名無しさん [02/11/01 19:42] 厳しい事言うね。 プログラムの中でも囲碁は難しいほうだよ。 日本中探し回っても、囲碁の思考の部分をプログラムできる人は 数えるほどしかいないと思うけど。 335 名前：デフォルトの名無しさん mailto:sage [02/11/01 19:49] だいたいまだ３００レスじゃねーか。 336 名前：デフォルトの名無しさん mailto:sage [02/11/01 23:50] 囲碁の評価関数の話をしませんか？ 思うに、評価関数自体で再帰的に探索するような仕組みを作れば いいような気がする。 石の死活はこの石を殺すには先にこの石を殺して、その前に・・・と 延々続いていくので、この部分を上手に再帰的に処理できれば 石の死活に関してはかなり強くなるのでは。 とか書いてみる。もちろんアイデアだけで実現できてません。 337 名前：デフォルトの名無しさん [02/11/02 22:48] >>336 提案してるのは「再帰」なわけ？ ぶっちゃけ、君相当レベル低いかも。 MiniMaxとか知ってる？ 木構造＝再帰で処理できる 再帰的に処理できる事のメリットはコーディングが容易なだけだけど。 評価関数の話で一つ問題を提起すれば 状況に応じて評価関数を切り替えるという方法は 一般的な方法だけれど、 では、状況というものをどう定義するか。 つまり、どういう状況に振り分けるか。 序盤、中盤、終盤に分ける方法が一番短絡的かもしれない。 他にもコウの時は別の評価関数を用意できるかもしれない。 評価関数の中身は別として、 どれくらいの状況に分けられるのか？ 振り分けるアルゴリズムがあるかどうかはまた別の問題だと思う。 まあ、囲碁に限った話ではないんだが。 338 名前：デフォルトの名無しさん [02/11/03 21:04] 再帰という言葉を覚えたから使ってみたかったんだろ。 339 名前：デフォルトの名無しさん mailto:sage [02/11/03 21:17] 盤の端っこでの死活の問題はさ、強い人ほど先を読まずに形を暗記して うってるんですよ。 というわけで、死活はデータベースを作ればよろしい。 340 名前：デフォルトの名無しさん [02/11/03 21:35] 今なら１０万件くらいは余裕で処理できそうだから・・・ log3 100000 =10 よって3*3の範囲なら全部覚えられる。 マス目の数＊0.477=必要なレコードの桁数 １６マスなら7桁、つまり１００万レコードだ。 341 名前：デフォルトの名無しさん mailto:sage [02/11/03 21:46] >>340 とりあえず、死活１００選とかそういう本をざっと眺めてみる ことをお勧めする。 342 名前：デフォルトの名無しさん [02/11/03 22:19] >>341 たしかに、すべてのパターンは必要にならないけど 相手が常に最善を打ってくるとは限らないので 340に出てる数字と大差ないというか。 一マス増やしただけで、桁数が0.5桁増えるというのは 恐ろしい事だよ。 まあ、実際のプログラムでは 眼形データベースと演繹的な処理で判定するわけだけど。 詰め碁がデータベースでできたら、学会誌には出てこないよ。 343 名前：デフォルトの名無しさん [02/11/05 01:44] 書き逃げ？ 344 名前：デフォルトの名無しさん mailto:sss [02/11/10 22:01] HSP イイ!! 345 名前：デフォルトの名無しさん [02/11/10 23:38] あきらめたとか？ 346 名前：デフォルトの名無しさん mailto:sage [02/11/10 23:48] 盤のはしっこのデータベースつっても３＊３じゃ正直狭すぎでわ？ 5目中手ですら３＊４の大きさは必要だし。 外側の石の状態とかも必要と思われ（安全、攻め合いになってる、とか） 347 名前：デフォルトの名無しさん mailto:sage [02/11/11 17:08] >1に勝ったら賞金が出力されるロジックが必要なんだと思ってた・・ 348 名前：デフォルトの名無しさん [02/11/13 16:46] うにゅ 349 名前：デフォルトの名無しさん [02/11/14 10:43] 完全読みすれば死活の判定はできそうだけど 350 名前：デフォルトの名無しさん [02/11/15 03:26] 2*2でも、完全読みをするのはめちゃくちゃ時間がかかる 351 名前：デフォルトの名無しさん mailto:sage [02/11/16 03:07] 3x3が何とかなるレベル。 ４は、今のPCだと辛すぎる。 ５以上は間に睡眠や人生をはさまないと無理。 352 名前：デフォルトの名無しさん mailto:sage [02/11/17 01:49] 5x5は解かれた、と情報が流れていたけど？ 353 名前：minikat [02/11/17 19:30] 解いた見たいですね。 確か結果は、白全滅。 354 名前：デフォルトの名無しさん [02/11/17 20:22] それは完全読みじゃなくて、 ヒューリスティックを使ってるんじゃなかったっけ？ 355 名前：デフォルトの名無しさん mailto:sage [02/11/17 21:12] 10/21のメールから。 天元に打って黒25目勝ち。 4時間で解いたとか書いてるな。 Yesterday my program solved 5x5 Go starting with the first move in the centre. As was expected it is a win for the first player with 25 points (the whole board belongs to black). I used an iterative deepening Alpha-beta search (PVS) with: - Transposition tables (2-deep replacement scheme, 2 x 2^24 entries) - Enhanced transposition cut-offs - Symmetry lookups in the Transposition table - 2 killer moves - History heuristic - Benson's algorithm for unconditional live (extended with unconditional territory) - Heuristic evaluation for positions that are not fixed by benson The solution was found at 22 ply deep (23 for the empty board).(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz) The main reason why my search was able to solve 5x5 is Benson's algorithm which reduced the depth where a proven full-board-win is detected by at least 6 plies (compared to by old implementation which had to play many things out). Only the simple (japanese) ko-rule was used, so the result is independent of any superko-rule. This does not mean that super-ko is irrelevant, just that from the empty 5x5 board there is a forced line that avoids all long cycles.

---

---

[ 続きを読む ] / [ 携帯版 ]

read.cgi ver5.27 [feat.BBS2 +1.6] / e.0.2 (02/09/03) / eucaly.net products.
担当:undef