5ちゃんねる ★スマホ版★ ■掲示板に戻る■ 全部 1- 最新50  

■ このスレッドは過去ログ倉庫に格納されています

おまいら最強のConnect4プログラムしてみろよ

1 :デフォルトの名無しさん:2008/08/25(月) 18:44:54
基本的にはConnect4を題材にプログラムの最適化技法を語るスレです。

Connect4は囲碁や将棋のような2人で遊ぶゲームで重力つき4目並べとも呼ばれます。
下のサイトで遊べます。
http://www.2flashgames.com/f/f-581.htm

ルール
1.盤は横7、高さ6のサイズとする。
2.先手、後手が互いに黒石、白石を盤に着手する。
3.石は下から積み重ねるものとし、空中におくことは出来ない。
4.同色の石が縦、横、斜めのいずれかに一直線に4目以上並べば勝ち。(長連も勝ち)

このゲームの強いAIを作りつつ、最適化技法を語りましょう。

プログラム言語は基本的にはC/C++を考えていますが、どんな言語を使ってもOK.
ハードウェアも基本的にはPC/AT互換機を考えていますが、それ以外のハードや、FPGAや、GPGPUなどマニアックなものもOK.
とにかく、どんな手段を使っても、

●強ければ強いほどいい。
●計算時間は短ければ短いほどいい。
●メモリ使用量は少なければ少ないほどいい。
●ロードモジュールは小さければ小さいほどいい。
●使用ハードウェアは安ければ安いほどいい。

等々、あらゆる角度から最適化を考えるスレです。

オセロの完全解析は無理でもConnect4なら完全解析いけるはず。



2 :デフォルトの名無しさん:2008/08/25(月) 19:06:19
 ―┼‐         ノ     /   |  --ヒ_/     /   \ヽヽ    ー―''7
   `」   ┼,   二Z二   レ   /  /´レ' \ ―7 ̄}  |  ー-、   /
 (__  (|フ)   (__ノ  _ノ  ∨`  ノ  /  /     _ノ    \_


    ─┼-        /   |   ‐┼-   |     ー|―
    ─┼─ |   \ レ  /   ̄Tー  /      ノ -─
   (二フヽ  \/    _ノ   (二フ\  ヽ_ノ   / 、__

     i';i
    /__Y
     ||V||                   /⌒彡
  _ ||.I.||         /⌒\     /冫、 )
  \ ||P|| ̄ ̄ ̄ ̄ ̄ ̄ ̄\ `./⌒ i `  /ゝ     _,,..,,,,_
  ||\`~~´  (<二:彡)    \( >     ('\\  ./ ,' 3 `ヽーっ
  ||\|| ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄|| ̄\`つ    ⌒ _) l   ⊃ ⌒_つ
     .|| ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄ ̄||                `'ー---‐'''''"

3 :デフォルトの名無しさん:2008/08/25(月) 19:22:57
まず>>1がこのスレの基調プログラムを発表すべきだな

4 :1:2008/08/25(月) 22:26:24
まずはルール部分だけ書いてみました。
http://www-2ch.net:8080/up/download/1219669877888722.yqLFqt
にアップしました。

普通にMain.cppをC++コンパイラでコンパイルしてください。

ポイントとしては盤面のデータを出来るだけコンパクトにし、かつ速度も遅くならないようにビット演算を駆使したところ。
普通の配列を使った実装と比べて速度が速いか遅いかはよくわからないです。

ざっと動かしたところちゃんと動いているように見えますが、あんまりテストしてません。

かなり変態的コードでしかもコメントも何も書いてないのでこのコードを解読するのはキツイだろうけど、
もし興味がある人がいたら解説します。



5 :デフォルトの名無しさん:2008/08/25(月) 22:26:43
こらこら、夏休みの宿題で追い込まれたからって
こんなとこでアイデア募ろうなんて手は食わないぜ

6 ::2008/08/26(火) 00:56:08
コンピュータ囲碁界ではモンテカルロ木探索が大ブームらしい。
Connect4にこれを適用してみよう。



7 :デフォルトの名無しさん:2008/08/26(火) 23:37:02
完全解析されてるよ…

8 :デフォルトの名無しさん:2008/08/27(水) 00:15:41
m9(^Д^)プギャーーーッ

9 :1:2008/08/27(水) 18:18:20
いやぁ、まあ完全解析されてたっていいのさ。
完全解析を達成したプログラムだってそんなに簡単なものじゃないだろうし、
より速く、より小さくを目指してやることは残ってるとおもう。多分…


10 :デフォルトの名無しさん:2008/08/28(木) 00:31:42
>>1
おまえリバーシ1か?

11 :デフォルトの名無しさん:2008/08/28(木) 00:33:36
書き込みの特徴から考えて、おそらく違う

12 :デフォルトの名無しさん:2008/08/28(木) 00:42:47
どうだろうな
一部に特徴の一致も相違も見られるから判断がつきかねる


13 :1:2008/08/28(木) 18:18:53
この不穏な空気は何?
リバーシ1なんて名乗ったこともないしそう呼ばれたこともないんだが。
面倒なことに巻き込まれるのは御免だぜ?
とりあえず、事情を教えてくれ。


14 :デフォルトの名無しさん:2008/08/29(金) 01:16:01
>>13
リバーシ1は↓の初代スレの1

おまいら最強のリバーシプログラムしてみろよ
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/

15 :1:2008/08/29(金) 18:28:58
すまない、俺、モリタポもってないから過去ログよめないんだが、
要するにリバーシ1は危険人物で俺がそいつに似てるからマークされてるということ?



16 :デフォルトの名無しさん:2008/08/29(金) 19:56:00
関係ないんだったら関係ありませんって言ってそれで終われ
巻き込まれたくないって言いながら話を広げるのは愚考

17 :デフォルトの名無しさん:2008/08/29(金) 20:23:34
>>15
p2todatを使うと見れるかも

18 :1:2008/08/29(金) 20:24:35
俺は関係ない。
何か怖いからこのスレに書き込むのもやめにするよ。


19 :デフォルトの名無しさん:2008/08/29(金) 22:42:45
リバーシ1が危険って事は無いな
奴は単なる打たれ強い馬鹿

20 :1:2008/08/29(金) 23:03:22
なんだ。ビビって損した。
じゃあ、俺がこのスレ続けても別に危険じゃないわけね。


21 :デフォルトの名無しさん:2008/08/29(金) 23:10:42
本当にリバーシ1じゃないなら応援するよ

22 ::2008/08/29(金) 23:42:51
じゃあ、このスレは続けさせてもらいます。
よろしく。


23 ::2008/08/31(日) 19:39:59
いま、テスト書いてるんですが、完璧なテスト書こうとすると大変。
ほどほどのところでやめとくべきなんだろうな…。


24 :デフォルトの名無しさん:2008/09/12(金) 03:37:26
>>1
今どうなってるの?

25 ::2008/09/12(金) 06:27:45
>>24
UCTの実装が私には意外と難しくてあんまり進んでいません。
UCTは有望な手の枝が成長していくのですが、どう実装すればいいか試行錯誤してるところです。
とりあえず、木が成長しない原始モンテカルロ法での実装はしてみました。
はっきりいって弱いです。

現状のコードは以下です。
http://www-2ch.net:8080/up/download/1221167364802747.5m2UcY


26 :1:2008/09/28(日) 21:31:34
木が成長するタイプのモンテカルロ、できたつもりなんですが…
全然強くないです。
なにを間違えてるんだろう?



27 :1:2008/09/30(火) 23:08:11
まあまあ強くなったようなのでexeだけ一旦アップします。
遊んでみてください。
マシンパワーがないと思考時間、結構かかります。
ソースはいろいろ試行錯誤してとっちらかっているので今回はアップ見送り。

http://www-2ch.net:8080/up/download/1222782844449693.2caUfX


28 :デフォルトの名無しさん:2008/09/30(火) 23:29:55
強いね


29 :1:2008/10/01(水) 00:01:30
>>28
すばやいレスありがとうございます。
モンテカルロは評価関数やヒューリスティックな手法が要らないから革命的、というイメージがあったのですが、
プレイアウトを完全にランダムにしてしまうとなかなか性能が出ないようです。
やはり最低限のヒューリステックは入れたほうが性能がでますね。



30 :デフォルトの名無しさん:2008/10/01(水) 00:04:51
>>29
終盤はソルバー使ってる?


31 :1:2008/10/01(水) 00:16:29
>>29
いまのところ序盤と終盤でアルゴリズムは使い分けていません。
ただモンテカルロ木が成長した結果、必勝か必敗か
わかってしまった場合は途中で読みが打ち切られます。(多分)

あと、プレイアウトには4手読みを使っています。4手以内で必勝の手があれば
必ずそれを選ぶし、必敗の手があれば避けるようにプレイします。
(4手読みはちょっと贅沢かもしれません。工夫の余地があると思います。)




32 :デフォルトの名無しさん:2008/10/01(水) 00:29:00
なるほどね

33 :1:2008/10/01(水) 21:19:09
ざっと整理したのでソースも上げときます。
http://www-2ch.net:8080/up/download/1222862895202427.8ihBjm

ところで皆さんのマシンはデュアルコアorクアッドコアなんでしょうか?
並列計算で高速化するのも面白そうです。

あと、盤面に64bit整数を使用しているので、64ビットコンパイラをつかって64bitOSで走らすと速くなるはず。


34 :デフォルトの名無しさん:2008/10/01(水) 22:10:03
すばらしい
自分が想像してたよりもシンプルなコードなんだな
俺のマシンはデュアルコアでOSも64bit


35 :1:2008/10/02(木) 19:41:31
64bitコンパイラ(VC)でコンパイルしてみました。
体感でもだいぶ速い気がします。

http://www-2ch.net:8080/up/download/1222943679080154.IDCGpI


36 ::2008/10/03(金) 22:58:48
AI vs AIでゲームすると黒が勝ったり白が勝ったりしますね。
かなり強いAIが出来たと思ってたけど、やはり完全解析からは程遠いようです。


37 ::2008/10/07(火) 18:40:38
Connect4の場合、やはり完全解析は避けて通れませんね。
とはいえ、素朴な方法では完全解析は難しそうです。
さてどうしたものか。


38 :デフォルトの名無しさん:2008/10/22(水) 11:12:44
今日初めて来た新参者ですが、
>>7
これ本当に完全解析できてます?
できればURLが知りたいです。

39 :デフォルトの名無しさん:2008/10/22(水) 13:53:20
Wikipediaくらいは辿ったのか?

40 :デフォルトの名無しさん:2008/10/22(水) 14:13:31
日本のページには記載なし。
http://ja.wikipedia.org/wiki/%E5%9B%9B%E7%9B%AE%E4%B8%A6%E3%81%B9
英語ページ
http://en.wikipedia.org/wiki/Connect_Four
先手必勝(1988年)
なるほど…一度解かれた問題をもう一度やるのか…


41 ::2008/10/22(水) 20:52:27
1です。
最近はサボりっぱなしです。すいません。正直、Connect4に対する情熱が薄れてきました。

>>40
誰もが最先端のレベルの研究が理解できるというわけでもないので。
私も含め、過去の成果から学ぶこともたくさん有ると思っています。

ところで、Connect4は少し中断して囲連星というゲームに浮気しようかと思ってます。
http://pc11.2ch.net/test/read.cgi/gamedev/1154589225/

しばらく留守にしますが、このスレが落ちる前には帰ってきたいと思います。

42 :デフォルトの名無しさん:2008/10/26(日) 17:49:35
ムー、
とりあえずルールだけ適応させて
次の1手がX軸7通りだから7分岐ツリーで全パターン計算させたら、
14手先読みするだけで結構時間かかりますね。
42手は天文学的に無理。
やっぱり、無駄な手を相当省略しないと完全回答出せませんね(当然か…)
http://www.connectfour.net/Files/connect4.pdf
これちゃんと読まないとダメか…
これを1988年に解読って、天才って居るもんですな…
本腰入れてやらないと解けないっぽ orz

43 ::2008/12/09(火) 21:00:16
囲連星プログラム、9路でやってるのですが徐々に形になってきました。
しかし、オフィシャル採用のYさんのAIは鬼のように強い。
今の俺のプログラムの位置からは想像を絶するほどの高みにいる…
これを超えるのはムリポかも。


44 :デフォルトの名無しさん:2008/12/23(火) 02:00:12
>>43
打ってみたいから打てるようになったらどこかにUPしてよ。
Yさんのはやっぱり強いのか。

45 :1:2008/12/23(火) 09:49:48
>>44
一応打つだけならいまでもできるんですが、Yさんのプログラムと比べてあまりに惨め。
Yさんのプログラムと比べて少しでも面白い特徴があればいいのですが、
Yさんのプログラムを単に計算時間を長くして着手の質を劣化させたような感じです。
これをUPするのはつらすぎる。
せめてYさんのプログラムにはない特徴が1個でも出せるまで待ってください。



46 :デフォルトの名無しさん:2008/12/23(火) 19:01:49
やっぱり19路より9路の方が作りやすいですか?

47 :1:2008/12/23(火) 23:39:35
>>46
大して変わらないかも


48 :デフォルトの名無しさん:2009/03/19(木) 20:21:54
ははは

13 KB
■ このスレッドは過去ログ倉庫に格納されています

★スマホ版★ 掲示板に戻る 全部 前100 次100 最新50

read.cgi ver 05.04.00 2017/10/04 Walang Kapalit ★
FOX ★ DSO(Dynamic Shared Object)