オセロAIってなんか難しそう？そんなことはありません。むしろゲームAIを学ぶ様々なレベルの人にこれ以上ないくらい最適です。この記事ではオセロAIを作ると何が良いのかをひたすら語っていきます。そしてオセロAIをこれから作る人のために参考になりそうな記事をいっぱい貼り付けていきます。
私自身はもうかれこれ1年以上オセロAIにどっぷりハマっています。詳細は以前書いた記事で。
オセロAIをおすすめする3つの理由
1. 原始的なゲーム木探索を学べる
オセロは「二人零和有限確定完全情報ゲーム」と呼ばれる種類のゲームです。この名称を説明すると、
- 二人: 二人で行われる、
- 零和: どちらかが得をすればもう片方が同じだけ損をする、
- 有限: 探索すべき範囲(ゲーム木)が有限で、
- 確定: 手番が一意に定まり、
- 完全情報: ランダム要素などの予期せぬ情報がない、
- ゲーム: ゲームである
という意味です。チェスとか将棋とか囲碁もこの部類です。
この部類のゲームは特にプログラミングとの相性が良いと思います。そしてこの明快さ故に、何かトリッキーなことを含んだゲーム木探索ではなくて、原始的なゲーム木探索を適用できます。
不完全情報ゲームや多プレイヤーによるゲームも、基本的にはオセロで学べる原始的なゲーム木探索の手法を改良して適用できます。
2. ルールが簡単
オセロのルール、多くの日本人はご存知でしょう。8x8の盤面に石を置いていくゲームです。相手の石を自分の石で挟んだら相手の石を自分の石にできます。最後に石が多い方の勝ちです。単純ですね。
誰しもが知っている単純なルール、ここにプログラミングとの親和性があります。単純だから、ルール自体の実装は比較的簡単にできます。さらに、単純だからこそ、限界まで高速化を目指すことだってできます。
盤面を配列で表す方法から、64bit整数によるビットボードを使う方法まで。さらにビットボードを使えばSIMD(複数の数に対して同じ演算をするとき、並列に行えるもの)を使って限界まで高速化できます。
3. 評価関数が簡単
チェスや将棋、囲碁と比べて、オセロをおすすめできる最大の理由は評価関数の作りやすさにあると思います。
評価関数は盤面を一見して形勢を評価する関数です。オセロにおいては、多くの人がご存知のように隅のマスがとても強力に形勢に作用します。こういった知識を使って、マス自体に重みをつけてやれば、あっという間に評価関数が作れてしまいます。
この評価関数でも人力オセロの2、3級程度までは強くなるようです。ちなみに筆者は人力オセロ5級です。
強豪オセロAIを作ろうと考えると、さすがにもう少し評価関数を工夫する必要があります。その場合は「パターン評価」と呼ばれるものを使うのが主流です。オセロの盤面の特定のマスたちを取ってきて、そのパターンでの石の並びに点数をつけるものです。難しそうに聞こえますが、先例がいっぱいあるのでそれらを参考にできます。さらに、後で紹介する私の書いた記事には評価関数本体と評価関数を作るコードが付属しています。
いざ、オセロAIの世界へ
ここまで記事を読んでくださったあなたなら、もう今すぐにオセロAIを作りたくてたまらないでしょう。そんなあなたのために、私の個人的おすすめオセロAI解説サイトとオセロAIのコンテストをご紹介します。
オセロAIのコンテスト
オセロAI、実はいつでも参加できる常設のコンテストが存在します。コンテストに参加すると、自分のオセロAIがどれくらいの強さなのか、改良したがどれくらい強くなったのか、そういう情報が簡単にわかります。おすすめです。コンテストサイトはこちら
このコンテストはゲームAI関連のコンテストを多く主催するCodinGameの常設コンテストです。便利なことに、ブラウザでその場でコードを書けるエディタ付きです。さらに、簡単なサンプルコードも付属するのでそれを改造していけばスムーズにオセロAIを作れます。さらにさらに、ちょっと嬉しいのが、合法手(自分が打てる手の候補)を入力で与えてくれるところです。自分の合法手生成アルゴリズムがなくても、とりあえず動かすことができます。
ただ、実行時間制限が初手2秒、以降1手0.15秒と短めなのでゴリゴリ深くまで探索するのは結構難しいです。さらに、コード長制限が10万文字なのでパラメータの埋め込みに多少苦労するかもしれません。
これらの面倒な点を考えても、このコンテストはおすすめできます。
オセロAI全般の道標
いざオセロAIを作ろうと思っても、何から手を付けてよいかわからない、そんな人のために以前私が書いた記事(少し内容が古いので近々頑張ってアップデートしたいですが)があります。
この記事では初歩のアルゴリズムから高度なアルゴリズムや高速化の工夫、さらには性能の良い評価関数の作り方まで、手取り足取り解説しています。さらに、サンプルコードを以下のレポジトリで公開しています。
サンプルコードはシンプルなものですが、多くの人にとって参考になると思います。ちなみに実際にサンプルコードを真似したらオセロAIが高速化できた(？)という声も…！
ただ、ボードの実装がトップクラスには速くないのが難点なので、近々アップデートします。頑張ります。
探索アルゴリズムの道標
上で紹介した記事集はオセロAIに特化していますが、なんとゲームAI世界4連覇のthunderさんによるゲーム木探索を全体的に網羅できる記事があります。こちらのαβ法の説明がとてもわかりやすいのでおすすめです。
評価関数の道標
簡単な評価関数としてマス自体に重みをつける(隅を取ったら勝ちやすそうなので隅を重くする、など)手法は、こちらのサイトで紹介されているものをおすすめします(私の記事集でもこちらの記事を参考にしました)。
さらに強くするために使うパターン評価については、オセロAIの教科書で簡単に解説しています。
もっと詳しく知りたい方はパターン評価が提案された英語論文がありますのでそちらをご覧ください(近々私が日本語でわかりやすく解説したい…！)
オセロAIを作ってゲームAIに入門し、ゲームAIを極めよう
オセロという単純明快なゲームのおかげで、オセロAIはゲームAIの入門に最適です。さらに、オセロAIを通して探索アルゴリズムや最適化、高速化、さらにはこの記事では触れませんでしたが、探索の並列化についても学べます。作らない手はないです！！
みんな、とにかくオセロAIを作るんだ