最強の立体四目並べAIを作る part0 | 導入
目次
はじめに
こんにちは。数年前になにか一つボードゲームを極めたいと思い、立体四目並べに興味を持ちました。そしてある程度戦えるようになったときに、強いAIを作ってより良い戦略を探そうと思い、ある程度の知見が溜まったのでここにまとめたいと思います。まずはこのゲームの先行研究や現状についてご紹介し、次の記事以降で実際に立体四目AIを作成し、余裕があれば戦略について考察を深めていきたいと思います。
ここで今回作成した立体四目並べAIのコードを公開しています↓↓↓
https://github.com/mikanakim/score4_AI/tree/main/score4
自己紹介
筆者は非エンジニアです。これを作るためにプログラミングを始めました。専門の方々、お手柔らかにお願いします。PythonやC++をよく使います。この記事ではC++がメインです。また、Youtubeにて「立体4目」というチャンネルで、立体四目並べについてなんとなく考えたことを不定期で投稿しています。
先行研究の紹介
先行研究① ~特定の局面における勝敗~
現在でも立体四目並べの必勝法については明らかにされておらず、先手必勝/後手必勝/引き分けのどれに帰結するのかすらもわかっていません。しかし、以前から必勝型についての考察はブログ¹⁾や知恵袋²⁾で散見されていました。必勝型とは、将棋で言う詰将棋のようなもので、次に相手がどんな動きをしても自分の勝利が確定する盤面の事をいいます。いくつか有名なパターンがあるのでそれを覚えておくだけでも対局を有利に進めることができます。
先行研究② ~先手必勝の可能性？~
先ほどのは特定の盤面におけるゲームの勝敗についての考察ですが、ツェルメロの定理によるとゲームの勝敗/引き分けは対局開始前に決まっているといいます。そのようなゲーム序盤における勝敗については、Technische Universität MünchenのRené Romenさんが書いた記事³⁾で一部解析されています。この研究ではゲームを途中まで定石どおりに進め、その先の展開をコンピュータで読み切る方法が採用されています。取りうる展開が多すぎてすべてを読み切ることはできなかったようですが、全体的に先手有利な雰囲気が伺えます。ただし、この研究の一番の注意点は定石を定義しているところです。立体四目並べにおける定石は後述しますが、多くのプレイヤーはこの研究の定石を見て疑念を抱くと思います。したがって、個人的にはこの研究を鵜呑みにはできないと考えています。
こちらに関して、youtubeの方で後手必勝手順は存在しないだろうということを文献を参考に示してみました。ツェルメロの定理から立体四目並べは先手必勝もしくは引き分けになるはずで、少なくとも対局開始直後では先手が有利な状況であると考えられます。
https://youtu.be/apk627q7i8w
先行研究③ ~数理的考察による戦略~
先手必勝/後手必勝/引き分けのどれに帰結するかがわからないので、ひとまずは最適な戦い方を探すこととします。これについては、苫米地(1999)⁴⁾がほぼ唯一の文献です。この研究では、用語の定義から序盤、中盤、終盤それぞれの戦略まで幅広く数理的な背景から考察しています。ぜひ読んでみてください。
私はこの文献を参考に、立体四目並べにおける勝利条件を拡張し、より実践的なものを構築しました。youtubeで一部解説していますが評価関数の作り込みで使用したので追々こちらでも解説すると思います。
https://youtu.be/EAm0VeKuCOA
立体四目並べAIについて
ゲームで遊ぶ中で、自分が成長していくとより強い相手と戦いたくなります。現在、将棋やオセロをはじめとしたボードゲームがそうであるように、ネットやアプリには多くのAIが存在しています。中にはとても人間では太刀打ちできないものまでありますよね。
では立体四目並べのAIはどうでしょう？無料で遊べるものとしては、Score Fourの公開ページ⁵⁾、resu27.com⁶⁾、website⁷⁾などがあります。私はこれら全てと対戦したことがありますが、resu27さんの「超難」AIが一番強かったです。が、勝てないほどではありません。最初は勝つのに苦労しましたが、人間は成長する生き物です。そのうち勝てるようになります。
一方、課金をすれば、AI立体四目⁹⁾が強いらしいです(課金しない主義なので未対戦)。また、少しコンピュータに詳しい方であれば、書籍「ゲームAIと深層学習―ニューロ進化と人間性」の書籍サポート⁹⁾にあるシミュレーションでそこそこ強いAIと対戦できます(コードにバグがあるようでうまく動作しないかもしれません。代わりにこちらの記事¹⁰⁾のコード¹¹⁾を使うとうまくいきます。ほぼ同じものです。)。
マイナーなボードゲームなので仕方がないことですが、現状これだけしか遊べるAIがありません。コードだけならあるんじゃないの？とGithubを検索しても残念ながらなかなか良いものは見つかりません。
既存のアプリで対人戦はできる(やっぱり対人戦が一番おもしろい)ものの、プレイヤーの少なさが仇となり常にマッチするとは限りません。そして既存の強いAIに勝ってしまうとなにか手持ち無沙汰な気分になってしまいます。
そこで、より強いAIを自作しようというわけです。先に紹介したネット上のどのAIよりも強く、多少の心得のある(と思っている)私も勝てないほどのAIを作成することに成功しましたので、後学のためにも公開しようと思います(この後、15回程度対戦をしてようやく先手番で1回勝ちました。その後、後手番でも1回勝てたのでまだ改善の余地はありますね)。
それでは次の記事から技術的な解説をしていきます。ゆっくり更新するので気長に待ってください。
動作環境は以下のとおりです。
>> cat /etc/os-release
NAME="Ubuntu"
VERSION="20.04.6 LTS (Focal Fossa)"
ID=ubuntu
ID_LIKE=debian
PRETTY_NAME="Ubuntu 20.04.6 LTS"
VERSION_ID="20.04"
HOME_URL="https://www.ubuntu.com/"展望
先手後手どちらでもまだ勝つことはできますが、現在対戦可能なAIの中では最も強いです。今後はこのAIを活用して、機械学習を利用しながらさらなる強化を目指します。
参考文献
1) https://www.bodoge-intl.com/strategy/rittai4rulestorategy/
2) https://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1186415351
3) https://tum-csc.github.io/c43d/
4) 苫米地宣裕. 立体4目並べの数理. 八戸工業大学情報システム工学研究所紀要. 1999 Mar; 11(1): 1-4
5) Score Fourの公開ページ(https://www.fit.ac.jp/~sakuta/scorefour/scorefour.ja.html)
6) retsu.27(https://retu27.com/scorefour_cpu_nosupport.html)
7) https://www.google.com/url?sa=t&source=web&rct=j&opi=89978449&url=https://moku-ai.appspot.com/&ved=2ahUKEwjEupbox--JAxWrr1YBHYj1LkEQFnoECFwQAQ&usg=AOvVaw2tBIiBwZx0hNzANr3BFrOa
8) AI立体四目HP(http://www.logi-seq.com/sf/)
9) ゲームAIと深層学習―ニューロ進化と人間性(http://www.iba.t.u-tokyo.ac.jp/software/gameHP/index.html)
10) https://qiita.com/taiyaki8926/items/b1a6f55682736f21259b
11) https://github.com/taiyaki8926/Tic-tac-toe