おまいら最強のConnect4プログラムしてみろよ
■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさん
2008/08/25(月) 18:44:54Connect4は囲碁や将棋のような２人で遊ぶゲームで重力つき4目並べとも呼ばれます。
下のサイトで遊べます。
http://www.2flashgames.com/f/f-581.htm
ルール
1.盤は横７、高さ６のサイズとする。
2.先手、後手が互いに黒石、白石を盤に着手する。
3.石は下から積み重ねるものとし、空中におくことは出来ない。
4.同色の石が縦、横、斜めのいずれかに一直線に4目以上並べば勝ち。（長連も勝ち）
このゲームの強いAIを作りつつ、最適化技法を語りましょう。
プログラム言語は基本的にはC/C++を考えていますが、どんな言語を使ってもOK.
ハードウェアも基本的にはPC/AT互換機を考えていますが、それ以外のハードや、FPGAや、GPGPUなどマニアックなものもOK.
とにかく、どんな手段を使っても、
●強ければ強いほどいい。
●計算時間は短ければ短いほどいい。
●メモリ使用量は少なければ少ないほどいい。
●ロードモジュールは小さければ小さいほどいい。
●使用ハードウェアは安ければ安いほどいい。
等々、あらゆる角度から最適化を考えるスレです。
オセロの完全解析は無理でもConnect4なら完全解析いけるはず。
0002デフォルトの名無しさん
2008/08/25(月) 19:06:19`」 ┼, 二Z二 レ / /´レ' ＼ ―７￣｝ | ー-、 /
（＿＿ （|フ) （＿＿ノ ＿ノ ∨` ノ / / ＿ノ ＼＿
─┼- / | ‐┼- | ー|―
─┼─ | ＼ レ / ￣Tー / ノ -─
(二フヽ ＼/ ＿ノ (二フ＼ ヽ＿ノ / 、＿＿
ｉ';ｉ
/__Y
||V|| ／⌒彡
＿ ||.I.|| ／⌒＼ /冫、 ）
＼ ||P||￣￣￣￣￣￣￣＼ `.／⌒ i ` ／ゝ _,,..,,,,_
||＼`~~´ （＜二：彡） ＼( > ('＼＼ ./ ,' 3 `ヽｰっ
||＼||￣￣￣￣￣￣￣￣￣||￣＼`つ ⌒ ＿） l ⊃ ⌒_つ
.||￣￣￣￣￣￣￣￣￣|| `'ｰ---‐'''''"
0003デフォルトの名無しさん
2008/08/25(月) 19:22:5700041
2008/08/25(月) 22:26:24http://www-2ch.net:8080/up/download/1219669877888722.yqLFqt
にアップしました。
普通にMain.cppをC++コンパイラでコンパイルしてください。
ポイントとしては盤面のデータを出来るだけコンパクトにし、かつ速度も遅くならないようにビット演算を駆使したところ。
普通の配列を使った実装と比べて速度が速いか遅いかはよくわからないです。
ざっと動かしたところちゃんと動いているように見えますが、あんまりテストしてません。
かなり変態的コードでしかもコメントも何も書いてないのでこのコードを解読するのはキツイだろうけど、
もし興味がある人がいたら解説します。
0005デフォルトの名無しさん
2008/08/25(月) 22:26:43こんなとこでアイデア募ろうなんて手は食わないぜ
0006１
2008/08/26(火) 00:56:08Connect4にこれを適用してみよう。
0007デフォルトの名無しさん
2008/08/26(火) 23:37:020008デフォルトの名無しさん
2008/08/27(水) 00:15:4100091
2008/08/27(水) 18:18:20完全解析を達成したプログラムだってそんなに簡単なものじゃないだろうし、
より速く、より小さくを目指してやることは残ってるとおもう。多分…
0010デフォルトの名無しさん
2008/08/28(木) 00:31:42おまえリバーシ１か？
0011デフォルトの名無しさん
2008/08/28(木) 00:33:360012デフォルトの名無しさん
2008/08/28(木) 00:42:47一部に特徴の一致も相違も見られるから判断がつきかねる
00131
2008/08/28(木) 18:18:53リバーシ１なんて名乗ったこともないしそう呼ばれたこともないんだが。
面倒なことに巻き込まれるのは御免だぜ？
とりあえず、事情を教えてくれ。
0014デフォルトの名無しさん
2008/08/29(金) 01:16:01リバーシ１は↓の初代スレの１
おまいら最強のリバーシプログラムしてみろよ
http://pc10.2ch.net/test/read.cgi/tech/1166749119/
おまいら最強のリバーシプログラムしてみろよ part2
http://pc11.2ch.net/test/read.cgi/tech/1169413998/
おまいら最強のリバーシプログラムしてみろよ part3
http://pc11.2ch.net/test/read.cgi/tech/1173784074/
00151
2008/08/29(金) 18:28:58要するにリバーシ１は危険人物で俺がそいつに似てるからマークされてるということ？
0016デフォルトの名無しさん
2008/08/29(金) 19:56:00巻き込まれたくないって言いながら話を広げるのは愚考
0017デフォルトの名無しさん
2008/08/29(金) 20:23:34p2todatを使うと見れるかも
00181
2008/08/29(金) 20:24:35何か怖いからこのスレに書き込むのもやめにするよ。
0019デフォルトの名無しさん
2008/08/29(金) 22:42:45奴は単なる打たれ強い馬鹿
00201
2008/08/29(金) 23:03:22じゃあ、俺がこのスレ続けても別に危険じゃないわけね。
0021デフォルトの名無しさん
2008/08/29(金) 23:10:420022１
2008/08/29(金) 23:42:51よろしく。
0023１
2008/08/31(日) 19:39:59ほどほどのところでやめとくべきなんだろうな…。
0024デフォルトの名無しさん
2008/09/12(金) 03:37:26今どうなってるの？
0025１
2008/09/12(金) 06:27:45UCTの実装が私には意外と難しくてあんまり進んでいません。
UCTは有望な手の枝が成長していくのですが、どう実装すればいいか試行錯誤してるところです。
とりあえず、木が成長しない原始モンテカルロ法での実装はしてみました。
はっきりいって弱いです。
現状のコードは以下です。
http://www-2ch.net:8080/up/download/1221167364802747.5m2UcY
00261
2008/09/28(日) 21:31:34全然強くないです。
なにを間違えてるんだろう？
00271
2008/09/30(火) 23:08:11遊んでみてください。
マシンパワーがないと思考時間、結構かかります。
ソースはいろいろ試行錯誤してとっちらかっているので今回はアップ見送り。
http://www-2ch.net:8080/up/download/1222782844449693.2caUfX
0028デフォルトの名無しさん
2008/09/30(火) 23:29:5500291
2008/10/01(水) 00:01:30すばやいレスありがとうございます。
モンテカルロは評価関数やヒューリスティックな手法が要らないから革命的、というイメージがあったのですが、
プレイアウトを完全にランダムにしてしまうとなかなか性能が出ないようです。
やはり最低限のヒューリステックは入れたほうが性能がでますね。
0030デフォルトの名無しさん
2008/10/01(水) 00:04:51終盤はソルバー使ってる？
00311
2008/10/01(水) 00:16:29いまのところ序盤と終盤でアルゴリズムは使い分けていません。
ただモンテカルロ木が成長した結果、必勝か必敗か
わかってしまった場合は途中で読みが打ち切られます。（多分）
あと、プレイアウトには４手読みを使っています。４手以内で必勝の手があれば
必ずそれを選ぶし、必敗の手があれば避けるようにプレイします。
（４手読みはちょっと贅沢かもしれません。工夫の余地があると思います。）
0032デフォルトの名無しさん
2008/10/01(水) 00:29:0000331
2008/10/01(水) 21:19:09http://www-2ch.net:8080/up/download/1222862895202427.8ihBjm
ところで皆さんのマシンはデュアルコアorクアッドコアなんでしょうか？
並列計算で高速化するのも面白そうです。
あと、盤面に64bit整数を使用しているので、64ビットコンパイラをつかって64bitOSで走らすと速くなるはず。
0034デフォルトの名無しさん
2008/10/01(水) 22:10:03自分が想像してたよりもシンプルなコードなんだな
俺のマシンはデュアルコアでOSも64bit
00351
2008/10/02(木) 19:41:31体感でもだいぶ速い気がします。
http://www-2ch.net:8080/up/download/1222943679080154.IDCGpI
0036１
2008/10/03(金) 22:58:48かなり強いAIが出来たと思ってたけど、やはり完全解析からは程遠いようです。
0037１
2008/10/07(火) 18:40:38とはいえ、素朴な方法では完全解析は難しそうです。
さてどうしたものか。
0038デフォルトの名無しさん
2008/10/22(水) 11:12:44>>7
これ本当に完全解析できてます？
できればURLが知りたいです。
0039デフォルトの名無しさん
2008/10/22(水) 13:53:200040デフォルトの名無しさん
2008/10/22(水) 14:13:31http://ja.wikipedia.org/wiki/%E5%9B%9B%E7%9B%AE%E4%B8%A6%E3%81%B9
英語ページ
http://en.wikipedia.org/wiki/Connect_Four
先手必勝(1988年)
なるほど…一度解かれた問題をもう一度やるのか…
0041１
2008/10/22(水) 20:52:27最近はサボりっぱなしです。すいません。正直、Connect4に対する情熱が薄れてきました。
>>40
誰もが最先端のレベルの研究が理解できるというわけでもないので。
私も含め、過去の成果から学ぶこともたくさん有ると思っています。
ところで、Connect4は少し中断して囲連星というゲームに浮気しようかと思ってます。
http://pc11.2ch.net/test/read.cgi/gamedev/1154589225/
しばらく留守にしますが、このスレが落ちる前には帰ってきたいと思います。
0042デフォルトの名無しさん
2008/10/26(日) 17:49:35とりあえずルールだけ適応させて
次の１手がＸ軸７通りだから７分岐ツリーで全パターン計算させたら、
14手先読みするだけで結構時間かかりますね。
42手は天文学的に無理。
やっぱり、無駄な手を相当省略しないと完全回答出せませんね（当然か…）
http://www.connectfour.net/Files/connect4.pdf
これちゃんと読まないとダメか…
これを1988年に解読って、天才って居るもんですな…
本腰入れてやらないと解けないっぽ orz
0043１
2008/12/09(火) 21:00:16しかし、オフィシャル採用のYさんのAIは鬼のように強い。
今の俺のプログラムの位置からは想像を絶するほどの高みにいる…
これを超えるのはムリポかも。
0044デフォルトの名無しさん
2008/12/23(火) 02:00:12打ってみたいから打てるようになったらどこかにUPしてよ。
Yさんのはやっぱり強いのか。
00451
2008/12/23(火) 09:49:48一応打つだけならいまでもできるんですが、Yさんのプログラムと比べてあまりに惨め。
Yさんのプログラムと比べて少しでも面白い特徴があればいいのですが、
Yさんのプログラムを単に計算時間を長くして着手の質を劣化させたような感じです。
これをUPするのはつらすぎる。
せめてYさんのプログラムにはない特徴が１個でも出せるまで待ってください。
0046デフォルトの名無しさん
2008/12/23(火) 19:01:490048デフォルトの名無しさん
2009/03/19(木) 20:21:540049デフォルトの名無しさん
2009/05/18(月) 02:29:040050デフォルトの名無しさん
2009/05/19(火) 00:20:30■ このスレッドは過去ログ倉庫に格納されています