【オセロ,将棋】ボードゲーム Part3【囲碁,War】

**名前は開発中のものです。** · 2019/11/23(土) 19:09:58.05

比較的地味なボードゲーム専用のスレが欲しくて立ててみました。

前スレ
【オセロ,将棋】ボードゲーム Part2【囲碁,War】
https://mevius.5ch.net/test/read.cgi/gamedev/1508056498/

**535** · 2019/11/28(木) 19:43:10.05

ランダムボットと対戦してみます。

**535** · 2019/11/28(木) 20:27:44.97

お、50戦50勝ですね。
既存AIとも対戦させてみたいですが手入力はめんどくさいですね…

**535** · 2019/11/28(木) 20:37:24.27

手入力でやってみようかと思いましたが誤入力してしまうと取り返しがつかずかなり面倒ですね。
ちょっとやってみましたがいきなり先制攻撃して反撃を食らってしまうモンテカルロの癖が見られますね。
まだ既存のモンテカルロ＋ヒューリスティックAIには勝てないかな。

**535** · 2019/12/03(火) 21:41:13.98

ベストポリシー更新こね～～～
丸一日来なかった切なすぎる。orz

**名前は開発中のものです。** · 2019/12/04(水) 12:01:20.94

これがシンプルで初心者向きかと

TLWIN4
http://www2u.biglobe.ne.jp/~shunbook/omocha/tlwin4.htm

**535** · 2019/12/04(水) 20:41:26.48

>>21
囲碁っぽいゲームだね。
自分がそのAI作ろうとは思わないけど、作者がこのスレに書き込んでくれるなら歓迎する。

**535** · 2019/12/04(水) 21:27:51.53

結構昔のゲームなのか。
強いな。勝てない。まあ当たり前か。
アルファベータっぽいアルゴリズムなのかな？
いい枝刈りがあれば完全解析も夢ではないかも。
作者もう開発してないかもね。

センスいいゲームだと思います。

**535** · 2019/12/04(水) 21:35:48.74

ん～16マスだとすべての局面数が高々3^16=43メガか
今のマシンなら完全解析できそうな？
ていうか多分作者がもう完全解析達成してそう？。

**535** · 2019/12/04(水) 21:54:47.77

多分今からやるなら6x6か8x8がいいサイズかな？
でも小さい盤面でも奥が深いのは確かにそう思う。

**535** · 2019/12/04(水) 22:29:16.14

310さんにもコメント頂きたいですね～これは

**名前は開発中のものです。** · 2019/12/05(木) 21:57:34.99

タイルゲーム紹介した人だけど作者ではないけど
ちかいうちにたたき台をあげる
これで実験することで他のゲームにも応用、流用できるはずだろうと

**535** · 2019/12/05(木) 23:28:53.86

>>27
今後、継続的に書き込むなら、なんかコテつけてくれるとありがたいです。

**535** · 2019/12/06(金) 22:26:41.60

ここ3日くらい止まらないで動いてくれてる。
ありがたい。

**535** · 2019/12/07(土) 11:40:38.80

いきなりつける癖が抜けてないですねorz

**310** · 2019/12/09(月) 18:07:44.19

面白そうなゲームですね。このゲーム、千日手筋が出た時の引き分けの扱いが気になり
ます。引き分けにならないのかなぁ。

４×４なら、作者さんの様に盤面の勝敗情報をBook（DB）化して、幅優先探索で虱潰し
に穴埋めします。千日手検出して探索打ち切り筋決めながら。あと、Bookの遡り更新。
強いAIを作るというより、完全解析に向かっちゃいます。時間がどれくらいかかるのか
は不明だけどオセロの４×４は１秒未満で完全解析しちゃうのでいけるかなと。

８×８だと、何らかの評価関数が必要でしょうね。どういう評価関数にするか妄想膨らん
だけど、当面作る予定もない人が、先を予想するのもどうかと思うので、省略。

あと、偶数盤と奇数盤で結構必戦術が違ってきそうな気がしています。

つか、AI的に、ちょっと興味あるかも。

**535** · 2019/12/09(月) 21:43:34.79

ライフゲーム囲碁もうまく行かないし少しこのゲームに寄り道したい気持ちが出てきた。
まだやるかわからんけど。

**535** · 2019/12/14(土) 21:52:48.39

タイルゲームのルール実装しました。
多分4x4の完全解析行けそうな感じです。

**535** · 2019/12/15(日) 00:07:31.40

あれ意外と手ごわいかも？
まだメモリは尽きてないから様子見かなぁ

**535** · 2019/12/15(日) 00:34:33.88

計算上メモリは足りるはず…
頼む、足りてくれ！

**535** · 2019/12/15(日) 02:40:07.52

計算おわらねぇなぁ
310さんの言うように千日手あるのかなぁ
もう今日は徹夜だ

**535** · 2019/12/15(日) 02:48:14.39

このゲーム凄いギリギリのゲームバランスを達成してるのかもしれない。
まだ計算途中だけど白黒で必勝局面の数がほとんど変わらない。
凄い。

**535** · 2019/12/15(日) 02:52:03.54

対称局面考慮すればもうちょっと速くなりそうかな。
8対称にはならないかな？4対称？

**535** · 2019/12/15(日) 03:12:30.90

これ310さんならもっと速くとけるんじゃないかなぁ。
メモリを意識しすぎたかもしれん。
もっと贅沢にメモリ使ってもよかったかも？

**535** · 2019/12/15(日) 03:14:21.83

16手目まで読んでも探索が終わらないだと？
なんか間違えてんのかなぁ

**535** · 2019/12/15(日) 03:50:04.48

4対称いれてみました。

**535** · 2019/12/15(日) 04:10:25.62

この調子だと5x5の完全解析はかなり難しいかもな。
まだ解けてないけど4x4は行けるはず。

**535** · 2019/12/15(日) 04:45:38.29

4対称を考慮したすべての合法な局面数16050722になるっぽい。
でも完全解析はまだできてない。
反復深化っぽいアルゴリズムにしたの失敗だったか？

**535** · 2019/12/15(日) 04:47:02.51

あ、合法局面数えるの終局判定入れてなかったorz
もっと減るかな。

**535** · 2019/12/15(日) 04:50:51.95

14649602に修正

**535** · 2019/12/15(日) 05:17:18.42

反復深化やめたら72秒で完全解析完了しましたｗ
結果は後手の勝ち。

まあバグはあるかもしれない。
310さんもやってみてほしいな～
答え合わせしたいｗ

**535** · 2019/12/15(日) 05:22:54.38

使用メモリは2GBくらい。
うーん。
なんかちょっとバグの予感がしますが。

**535** · 2019/12/15(日) 05:43:15.98

バグあるっぽいｗ
駄目か～

**535** · 2019/12/15(日) 06:32:05.02

千日手が正解の可能性が浮上？

**535** · 2019/12/15(日) 09:52:56.34

勝った～
一勝した。

必勝かどうかは確かめる気力なしｗｗｗ

もう寝るｗｗｗｗ

これ以上バグが無ければ後手必勝と出ました。

**535** · 2019/12/15(日) 17:50:01.09

今のところ完全解析にかかる時間は2分15秒
公式AIにも勝てるし多分バグも大丈夫

ちなみに5x5完全解析は絶望的

6x6くらいをアルファゼロでやってみるのも面白いかもね。

**535** · 2019/12/15(日) 17:55:09.82

ID真っ赤だな俺ｗｗ
まあ今日は頑張ったｗｗ
久しぶりに気分いいわｗｗ

**535** · 2019/12/15(日) 18:19:20.88

公式AIのBookのフォーマット、ドキュメントがありますね。
必勝ブックを作るのもちょっと面白そうだがさすがにそこまではやらないかな。

**310** · 2019/12/15(日) 21:32:35.89

お。早速やりましたか。

必勝法の類の発想ですが、盤面に２×２のフィルタをかけたとして、３＾（２×２）＝８１通り
を、縦接続・横接続・未定に分類して９×９の盤面に置きかえると、作戦を考えやすいの
かなと思っていたりします。

**535** · 2019/12/16(月) 21:09:00.92

AIから日本語で棋理を抽出出来たら面白いなーと妄想したり。
囲碁将棋でだれかやってくれないかな。

**535** · 2019/12/16(月) 21:13:33.69

タイルゲームはわりとツークツワンクが大事っぽいですね。

**535** · 2019/12/16(月) 21:31:10.69

タイルゲームのソースとexe公開しますね。
https://drive.google.com/open?id=1wUN4YK88RWShhqVRfdZLgnicUeGv6oYM

**535** · 2019/12/17(火) 19:35:03.93

あ、27さんの見せ場を奪ってしまったかな？
まあ5x5とか残っているし頑張れ

**535** · 2019/12/19(木) 23:00:30.63

アルファゼロってホントに強くなるのかなぁ？
疑念が収まらないｗｗ

**535** · 2019/12/20(金) 22:46:58.99

DeepMindからAlphaZeroの進化版「MuZero」が登場
？！？

**535** · 2019/12/22(日) 18:05:10.17

ちょっと燃え尽き症候群
充電期間に入ります。

**535** · 2019/12/26(木) 18:46:52.48

19路囲連星をまたやろうかとかぼんやり考えています

**535** · 2019/12/30(月) 18:05:24.77

リレーショナルDBに手を出してみたい
ポスグレが第一候補

**535** · 2020/01/01(水) 00:57:35.38

あけおめことよろ

**310** · 2020/01/01(水) 21:54:10.76

あけおめー。

昨年中に確定探索遡りのバックログを消化するつもりだったのが、
怪しい筋たくさん見つけて全部訂正棋譜を掘ってしまったので、
更にバックログ増加中。

**535** · 2020/01/07(火) 23:13:54.32

ポスグレの入門本買ったけど全く手を付けてない
さぼりモード

**535** · 2020/01/08(水) 20:25:47.47

ポスグレ使うとして囲碁やるかライフゲーム囲碁やるか囲連星やるか心が決まらない

**535** · 2020/01/11(土) 16:36:11.27

とりあえず8TBのHDD買った
どのゲームやるかはまだ決まってない

**535** · 2020/01/11(土) 18:23:32.55

うお、ケースにHDD増設するスペースがないw
外付け化できるやつ買うかw

**535** · 2020/01/11(土) 20:01:59.75

HDD無事OSに認識されました。（最初認識されなくて焦った）
さてここからどうするか。

**535** · 2020/01/11(土) 21:11:20.06

は～心が決まらないorz

**535** · 2020/01/12(日) 01:24:49.63

ライフゲーム囲碁はデータ取るほど弱くなるし、19路囲連星は広すぎるし9路囲連星かなぁ

**535** · 2020/01/12(日) 01:31:22.13

あれ、おかしいな。9路囲連星のソースどこかいっちゃった。
まあ気持ちも新たに１から作るのも悪くないけど。

**535** · 2020/01/13(月) 21:33:57.10

なんかちょっとしばらくさぼってたらコーディングの腕が鈍ってるかも。
勘が働かないというか。

**535** · 2020/01/21(火) 21:15:41.22

マジでモチベが湧いて来ない
ここのところ忙しかったのもあるけど

**535** · 2020/01/25(土) 16:52:30.60

９路囲連星のモチベが上がらないのは本当は心の底ではライフゲーム囲碁をやりたいからなのかもしれない。

**535** · 2020/01/25(土) 20:21:04.06

いや、ちがうな。手っ取り早く結果が欲しいだけなんだ。
心が弱いんだ。

**535** · 2020/01/28(火) 21:14:35.23

やっぱ教科書の通り実装しようとするよりも自分でアイディアひねり出そうともがくほうが楽しいなぁ。
教科書が大事じゃないとは言わないけど、なによりモチベが全ての活動の源泉だからな。

**535** · 2020/01/30(木) 22:19:32.33

対称局面で候補手を絞り込む処理書いてるんだけど、もしかして８対称じゃなくて４対称しか使えないのだろうか？？

**535** · 2020/01/30(木) 22:27:50.02

ちょっと言葉が足りないかな？
着手後の局面が対称局面として同型となる候補手が複数ある場合、
そのうちの一つだけを代表として選択できるようにする、みたいなイメージなんだけど。

**310** · 2020/01/31(金) 20:42:25.38

線対称と回転対称があって、線対称は縦横斜め×２の４通りと、
１８０度回転対称の５通りではないかと思われます。

**535** · 2020/01/31(金) 21:33:38.95

うーむ、線対称はそれぞれ候補手が約半分になるのはわかるが180度回転対称はどうなるんだろう？

**310** · 2020/01/31(金) 23:26:47.00

半分じゃまいかと

**535** · 2020/01/31(金) 23:37:10.96

すいません、まだわかってません。
考えてみます。

**535** · 2020/01/31(金) 23:53:18.86

**535** · 2020/02/01(土) 01:57:04.18

もしかして現局面の対称性を考えるんじゃなくて着手後の対称性を考えるとわかるのだろうか？

**310** · 2020/02/01(土) 09:51:10.99

回転対称の時は、１８０度回した場所と対称になるので、左上と右下みたいな感じです。

（０，０）⇔（８，８）
（０，１）⇔（８，７）
（１，０）⇔（７，８）
（１，１）⇔（７，７）
：
（ｍ，ｎ）⇔（８－ｍ，８－ｎ）

みたいになりますので、図形ではイメージしずらいかも。

**535** · 2020/02/01(土) 18:31:37.87

うーん、回転対称確かに使えるかも。結局８対称全部使えるってことなのかなぁ？

**535** · 2020/02/01(土) 23:53:26.53

とりあえずpostgre sqlをインストールしました。

**535** · 2020/02/03(月) 21:22:57.75

スレッドリッパー3990x今週発売らしいですね。
藤井聡太7段が狙ってるとかなんとかｗ

**310** · 2020/02/04(火) 22:54:13.24

なんか今日のabema中継で藤井君が新PC買ったみたいな話出てたよ。
解説陣の伝聞情報だからアテにならないかも知れないけど。

相変わらず棋譜作り続けているけど、まだまだ局面的にはスカスカな感じ（汗
あと１年くらい続けてもダメかも知れないorz

あと結構たくさんのパブリックドローが、ドローじゃなさそうな感じになってきてます。
ドローから外れる良い手（＋２の分岐）が見つかった時に、それが正しいのかどうかを
チェックしています。深いところの分岐なら時間かければ完全読み切りで確定できる
のですが、浅いところで外れる場合は確認しきれません。Zebraを見ながら間違い探し
をしようにも、こういうのはZebraの評価値も揺れ動いていてあんまりあてにならず。

現在パブリックドローとして拾ってきた棋譜が９９本ありますが、１２本が確定間違い。
１３本が、おそらく間違いという状態です。後者はDAGや対称形を考慮すると４パターン
に集約されます。

ちなみに、F5f6E6f4G5の筋は全滅しそうです。F5d6C3d3C4f4C5b3C2の筋は、たくさん
生き残っています。逆に新発見のおそらくパブリックドロー候補もたくさんあるけど、
まだ怖くて確認してません。

**310** · 2020/02/04(火) 22:57:24.54

対称局面の話ですが、MCTSで探索範囲を絞るのであれば、All Moves As First法が
有効ではないかと思います。

オセロでは全く使えない方法なので僕は詳しくありませんが。

**535** · 2020/02/05(水) 21:51:06.12

うーん、All Moves As First法ですか。
ライフゲーム囲碁は囲碁に似ているゲームだから有効かもしれませんが、手順はやっぱり大事な気がするんですよね～
実装して試したわけじゃないけど、第一感として心のどこかで納得いってない部分はあります。

**310** · 2020/02/06(木) 19:25:08.06

すまんライフゲーム囲碁よくわからんで適当だった。
手順が大事なら無理だね。

こちらはF5f6の筋が全滅している…。
これから間違い探しですが、大変だぁ。

**535** · 2020/02/06(木) 21:50:40.62

いや、実はむしろ囲碁よりライフゲーム囲碁のほうが有効な可能性までありますが…
やはり心のどこかで引っかかるものがあるのです。

**310** · 2020/02/09(日) 10:30:31.08

F5ｆ6の筋復活。

パブリックドローリスト９９件に対して、６パターン１２本の棋譜が確定間違い。
そのほか３パターン９本のおそらくパブリックドローじゃない疑い。

**535** · 2020/02/09(日) 14:41:50.20

あああ、まったく頑張れない
今日も虚しく時間だけが過ぎて行く
Orz

**535** · 2020/02/09(日) 19:12:30.03

SQLのテーブルって一回定義しちゃって運用始まっちゃうと中々変えれないイメージがあって踏ん切りがつかない
それなら初めからテーブル分割気味に定義したほうがいいのだろうか？

**535** · 2020/02/09(日) 19:47:31.15

テーブルに予備項目もたせて後から項目増やしたくなったらそれ使うみたいな手法もないことはないな。
最善策ではないにしても。

**535** · 2020/02/10(月) 20:30:44.20

軽く計算してみたけど8TBのHDDをもってしても12～13手くらいしか全記憶できないっぽいな
うーむ

**535** · 2020/02/10(月) 21:09:48.48

盤面情報と勝率情報をテーブル分けてidでjoinする方向で検討。
親子関係もテーブルに持つようにするかも。

**310** · 2020/02/10(月) 21:49:59.84

F5f6の筋また死亡。
死亡復活を繰り返して３回目くらいに復活安定した筋もあるので、まだまだかかるかも（汗
というか、こういう作業が面倒臭い。

**535** · 2020/02/11(火) 15:02:56.99

C++からpostgre sqlにテストデータを1件登録することに成功した。
夢が広がるなぁ

**535** · 2020/02/11(火) 19:46:16.02

テーブル定義は段々固まってきたけどどういう順序で探索ツリーを展開するか一番肝心なところが決まってない。

**535** · 2020/02/11(火) 21:32:51.43

探索が進むほど有望な局面を選択できるようにしたいがやはりMCTS系の探索だろうか？

**310** · 2020/02/11(火) 21:43:38.70

F5f6の筋復活（汗

その代わり、F5d6E6f4とF5f6E6d6（対称形）に差が出てきて、評価値がずれた。
F5f6E6d6の棋譜をすべてF5f6E6f4に変換して、Bookにはf4系とd6系の２種類登録
しているので、ここの間では差が生じないが、例えばF5f4E3～の筋からたまたま
F5d6E6d6とかに合流してくると、その棋譜については対称変換しないので、差が
生じてしまうという事になるかなと気が付いて、対称変換で差が生じている棋譜を
Bookから逆生成してみたところ結構な件数が…というか、ざっくり見積もって既に
３万件超え。どうやって復旧するか悩むところ。というか、おそらくこれやったらまた
F5f6の筋が死亡しそうな予感。これから対策を考えます。むむむ。

そのほか、部分的に遡って完全読み切りした時に、そこまでたどり着いていない
筋の方が良い評価値になってしまうという、Bookに生じる矛盾を解消する処理を追加。
こちらは結構綺麗にできた。

**310** · 2020/02/12(水) 00:35:06.03

対称形の合流問題、一応のプログラムできた…と思う。

ロジック的には色々なやり方があるのだけど、処理時間とどこまでやるのかという
ところが悩みどころ。今のままで動かすか、どうするか。

ちょっと悩みたいので一旦ペンディング。

**310** · 2020/02/12(水) 22:15:37.07

一晩寝かしてプログラム破棄（汗

もともとある対称盤面の処理ロジックを生かして、F5筋しかない棋譜をC4/D3/E6に
対称変換する事で、根本的に解決しようという方向になりました。副作用はBookが
４倍に膨れるのと、F5スタート限定だった評価関数のエラーがいったん大きくなって
しまうために、学習しなおさなければならない事です。

やってみたら、Bookサイズでかすぎてメモリーギリギリ。仕方がないので６０手目まで
作っていたBookを４０手目までに限定。あと敢えて残して（意図的に作って）あった、
２４手目以降のベストではない分岐も別途保存して一回削除しました。

メモリ６４G以上欲しい…。スレッドは１６くらいで十分なので。

**535** · 2020/02/12(水) 23:03:00.16

メモリ欲しいですよね～。

**535** · 2020/02/12(水) 23:12:45.08

Ryzen Threadripper 3990Xに最適化したDDR4-3600 256GBメモリキットがG.SKILLから
ttp://www.gdm.or.jp/pressrelease/2020/0212/338305

**535** · 2020/02/13(木) 20:29:06.20

今更だけど、メモリよりHDDのほうがでかいわけだが、全部メモリに乗らないとするとどうやってプログラム組めばいいか悩ましいな。
ホント今更だけど。

**310** · 2020/02/15(土) 00:33:20.86

スピードが必要な部分はメモリーに無いといかんわけで。
今は探索でBookを参照しているので、Bookアクセスには速度が必要なわけで。
Bookは重要だけど棋譜は既に重要ではないわけで。
棋譜はSDDに移そうかなと思っていたりします。
どうせ要所要所で保存しているわけだし、都度読み込めばみたいな。
（HDDは遅すぎるので論外かと）

ただ…今のロジックがメモリー前提なのと、棋譜ですら読み込みに数秒かかる
状態なので、できればメモリーに置いときたい。そもそも、大した容量じゃないし。

自分の場合、本体でBook読み込むのと、同時にZebraと突き合わせながら間違い
箇所探しで掘り進める用に、Bookを確認するプログラムも同時に動かしていて、
そちらでも同じサイズのBookを読み込まざるを得ないので、16Gのメモリーが
あっても、半分くらいに抑えておかないといけないという問題があります。

頭の片隅にバイナリファイルのランダムアクセスってのがちょこっとだけありますが、
それって自分用DBを作るようなものなので、悩み中。とはいえ、最終的にもしオセロ
の対戦プログラムにするのなら、今ほど探索時間気にするわけでもなし、動作環境
として要求するメモリー量が大きすぎるのもなんだかなぁと思っていたりもします。

**310** · 2020/02/15(土) 00:35:39.59

そんな事より、対称形サポートして棋譜作っていたら、またF5f6系が全滅して
途方に暮れていたところで、知らぬ間に復活していたり。間違い可能性高い
パブリックドロー筋が復活したと思ったら、またダメだったり。

まだ棋譜作成が足りていないという事実に直面しています。

**310** · 2020/02/18(火) 00:26:29.87

対称形サポートでBookはだいぶ良くなって来た感じですが、完全読み切りの探索時間
が遅くなった。まだ新しい教師データに対して学習不足なんだと思いますが、どこまで
復活するか。

残り３０手読み切り時間がかかりすぎる。棋譜作成のプログラムの方は、ほぼ出来上
がってしまったので、動作具合を見ているだけになっている。何か探索高速化のネタは
無いものか。

PC一つ買って、そちらでオセロの棋譜作成させながら、別の何かの開発を始める時な
のかも知れない。

**535** · 2020/02/18(火) 00:27:41.65

とりあえずモンテカルロ1000poで10～50手打ち進めてその局面で100000po回して結果の黒番の勝利回数、スコアの合計を収集するプログラムを作成。
あんまりいい方法じゃないとはおもうけどこれだというアイディアもないしこれで一回やってみます。

**535** · 2020/02/18(火) 21:44:13.85

マシンパワー欲しいすな。
3990xでも足りないかも。

アルゴリズム見直せと言われそうだが。

**535** · 2020/02/18(火) 22:28:54.62

まーでも310さんも言ってるけど計算にマシン取られるとヒマですね。
AWSとか使うのも面白いかもしれないけどいかんせん金が…