Nim言語でオセロAI【貧弱な終盤ソルバー】

以下の記事の続きです！

オセロは、そのゲームの特性上、最大で60手でゲームが終了するので、ターン数によって終盤判定をします。 (将棋とかになると、ターン数ではなくて「相手を詰ませられるか」になるので、もっと複雑になります！)

そして、終盤になるにつれて、自分・相手の選択肢の幅が狭くなってくるので、(中盤に比べると)ゲーム木が広がりにくくなり、最後まで読み切ることができるようになります。

終盤は、中盤とはまた少し違った性質を持つようになるので、基本的に中盤用のアルゴリズムと終盤用のアルゴリズムはまた違ってきます。この終盤用の機構のことを、終盤ソルバーと言ったりします。

先ほど、終盤になるとゲーム木が広がりにくくなると言いましたが、もしかしたら「簡単そうじゃん♪」と思われたかもしれません。

が、しかし

最近のオセロAIを見ていると、終盤20マス辺りから読み切るそうですね...トッププログラムになると24マスとか...(これは恐ろしいことです)

[補足]あまりピンと来ない人もいると思いますので、簡単な計算をしてみます。終盤20マスから、取り得るゲーム展開の数は、20!(階乗)になります。

$\displaystyle 20! = 20 \times 19 \times 18 \times ... \times 2 \times 1 = 2.43 \times 10^{18}$

また、競プロやってる人は詳しいのですが、コンピュータは10⁷回のループに約1秒掛かると言われています。なので、単純に全探索しようとすると、なんと2×10¹¹(秒)、つまり約6342年掛かります(ﾆｯｺﾘ)

勿論、置ける場所・置けない場所あるので、実際はもっとゲーム展開数は少なくなりますが、スゴみが分かってきたと思います(僕もビビってます...笑)

古いページなんですけど、以下のページが読みやすかったです。

キーワードとしては、

とかかな？

とりあえず、作ってみないと様子が分からないのでパパッと作ってみました。速さ優先探索を意識してNegaScoutチックに書きました。相手の着手可能数が少なくなる順に打っていくイメージです。

動かしたら、以下のような感じになりました。 Turnは今何ターン目か、NodeNは探索したノード数(葉以外)、LeafNは探索した葉の数、Timeは探索に掛かった時間、NPSは1秒に何ノード(+葉)を探索できたかです。

f:id:g-knk-9410:20180401032951p:plain

あまりにも重いので、終盤15手読み切りです。でも、20秒弱掛かってる...。

ひぃぃぃぃぃぃ⚡️🌀✨💭❄️

でも諦めないよ💪💪 伸び代って考えると頑張れる😏

たかろぐ