オセロゲームを作ろう！(AlphaZeroで)

こんにちは、CCCマーケティング株式会社 データベースマーケティング研究所 技術開発ユニットの三浦です。最近娘がオセロに興味を持ち始めました。ずっと相手をするわけにもいかないので、オセロAIを作ろうかな・・・とふと思いつきました。

それだけでなく、技術開発ユニットのメンバーそれぞれでオセロAIを作り、対戦させたら面白そうですし、よい勉強になりそうです。ということで、空いた時間を見つけてオセロAIづくりをしている話を紹介します。

今回の記事はこちらの本を参考にさせて頂きました。
AlphaZero 深層学習・強化学習・探索 人工知能プログラミング実践入門 | ボーンデジタル

実装の前に

今回のオセロの盤面のサイズは8x8としました。オセロAIをつくるにあたり、まずオセロをプログラムで表現する必要があります。

オセロというゲームは

・2人のプレイヤーが交互に合法な手(石を置ける場所)を64個の場所から1つ選び石を置いていく
・石を置いた場所の8方向のいずれかの方向で相手の石を自分の石で挟んでいたらそれらを自分の石にする
・双方合法な手が無くなったらゲーム終了
・ゲーム終了時、より多く自分の石を置いていたプレイヤーが勝ち

のように表現できます。次に合法な手について考えます。オセロにおける合法な手とは

・自分の石も相手の石も置いていない
・8方向のいずれかに相手の石がある
・相手の石がある方向のいずれかの延長線上に自分の石がある

となります。下の図のようなイメージで判定します。

• 合法手か判定する処理のイメージ

つまり自分の番になったらこのような処理で64個の場所1つ1つ合法かどうかを調べ、そのうち1つを返すプログラムを組めば一旦オセロゲームが出来るようになります。

やってみよう

まずは合法な手の中からランダムで1つ返すプログラムを作り、娘と対戦させてみます。

• 対戦の様子

娘の打った手をプログラムに入力し、返ってきた手を自分がオセロ盤に打っていきます。

• 娘の打った位置を入力する

自分はオセロ経験そんなにないのですが、5歳児とランダムプログラムのやり取りによって描かれる盤面の様子にはなんだか不思議なものを感じます。

• 穴が多いから・・・？

途中で娘が飽きたりしましたが、最後まで終わりました。結果は41-23で娘が勝ちました。

• 飽きてゲームをやり始めた

オセロAIをAlphaZeroで作る

ランダムで合法な手を打つだけのプログラムから、勝つために最適な手を打つプログラムに進化させ、オセロAIを作っていきます。 最適な手をどうやって判断させるのか、そこにAlphaZeroというプログラムを導入します。

AlphaZero

2017年に人類最強の囲碁棋士をAIが打ち破った、というニュースが世界中に衝撃を与えました。この時AIに使われていたものがDeepMind社のAlphaGoというプログラムです。 その後、AlphaGo Zeroが発表され、囲碁だけでなくチェスや将棋といったその他のゲームにも使用可能なバージョンとして発表されたものがAlphaZeroです。

AlphaZeroの特徴

AlphaZeroの大きな特徴が「最適な手を選ぶためのデータを自己対戦(Self-Play)で生成する」という点です。つまり囲碁や将棋などのゲームの熟練者の知見が無くとも自身で強くなることが出来ます。そのため人間が考えもつかないような手を打てるようになります。

最適な手を探索するための仕組み

AlphaZeroは最適な手を探索する際に「モンテカルロ木探索」というアルゴリズムを使用します。モンテカルロ木探索は、簡単に表すとある評価値に基づいて合法手を選択、ゲームの展開をシミュレーションするということを一定回数繰り返し、次に打つ手としてシミュレーション中もっとも使われた手を選択する、というものです。

評価値の計算にはニューラルネットワークが使用されます。このニューラルネットワークの学習のためにSelf-Playで生成されたデータが使用されます。

Self-Playによる学習データの収集

自身で交互に合法手を打ち合い、現在の自分と相手の盤面、その局面でモンテカルロ木探索によって得られた合法手の確率分布、そして最終的なゲームの勝敗のデータを収集しニューラルネットワークの学習に使用します。

デュアルネットワークの出力

モンテカルロ木探索に使用されるニューラルネットワークはデュアルネットワークと呼ばれ、自分と相手の現在の盤面を入力するとどの手を打ったらよいかという確率分布と現在の局面の価値を出力します。

分類用の出力と回帰用の出力の2つが同時に出力されるような構造になっているためデュアルネットワークと呼ばれているようです。囲碁であろうと将棋であろうと同じネットワーク構造で対応できるのはすごいですね。

AlphaZeroの学習サイクル

AlphaZeroの学習サイクルは次のようになります。

1. 一定回数のSelf-Playを実行し、デュアルネットワーク学習用のデータを作成する
   
2. 1で作成したデータを使ってデュアルネットワークを学習させる
   
3. 今回学習したネットワークを搭載したプレイヤーと現在最強のネットワークを搭載したプレイヤーを一定回数勝負させる
   
4. 勝率が高い方のプレイヤーのネットワークを保存し、次回以降読み込む
   

このサイクルを回し続けて強化していきます。

つくってみて・・・

本家のAlphaZeroのように潤沢なリソースは無いので、各種サイズを落としてプログラムを作り、学習サイクルを回してみました。実行したPCのスペックは以下の通りです。

・OS：Ubuntu18.04 LTS
・CPU：インテル Core i7-10510U
・GPU：NVIDIA GeForce MX250 2GB GDDR5
・メモリ：16GB DDR4

実行環境はこちらの記事で紹介したようにDockerコンテナで作り、Visual Studio CodeのRemote-Containers extensionを使ってVisual Studio Codeからコンテナに接続して開発しました。Remote-Container、結構便利です！

GPUをガンガン使うので、学習サイクルが始まるとファンが回り続けてかなりにぎやかです。枕元に置いてたら寝不足になりました。

• 怪しい光

夜中に学習サイクルを回す→朝対戦の日々

起きてるうちに色々調べ、夜寝る前に学習サイクルを実行→朝起きたら枕元に置いてあるオセロ盤でAIと対決するという日々を送っています。

• 今人生で一番オセロやってるかも・・・

今の課題

学習サイクルの中で一番ボトルネックになっているのがSelf-Playの部分です。ネットワークを十分に学習させるためにはSelf-Playでより多くの対戦を行わせたいのですがここに時間がかかってしまうと学習の機会をそれだけ減らすことになります。

時間がかかっている理由は2つ考えることができて、

・デュアルネットワークの推論が遅い
・モンテカルロ木探索のシミュレーション回数が多い

上の方は現在使用している機械学習フレームワークKerasに由来する可能性もあり、改善はハードルが高そうです。となると下の方でなんとか出来るとよいのかもしれません。実は何度かAIと対戦していて感じていたことがあります。

すみっこ、大事！

そうです。自分はけしてオセロが強くないのですが、4隅を取ることが勝負において重要だと考えています。絶対に取られない場所ですし。娘とAIとの対戦を見ていると、AIの番で隅が取れる状態なのにそれ以外の場所に置いてしまいます。

Self-Playを繰り返すうちにいつか隅の重要性に気づいてくれるのだと思うのですが、この調子だといつになるかわかりません。そこでAlphaZeroの特徴である「Self-Playで強くなる」という点に反してしまうのですが、4隅の重要性を伝える工夫をしてその分モンテカルロ木のシミュレーション回数を減らしてみるということを試してみています。

工夫

モンテカルロ木の探索で、手が選択される評価値をSelf-Playの時だけ補正します。つまり合法手の中に4隅が含まれていた場合、評価値に少しの補正値を加え、シミュレーション時により選択されるようにします。その結果勝利につながることをこの工夫で伝えられないかと考えています。

今後

今はようやくAlphaZeroの全体図が掴めた段階なので、これから独自の工夫も加えてみたいと思います。いずれ技術開発のメンバーで大会をする予定です。

そこでの結果や優勝者がどのような工夫をしたのかなども、今後の記事で紹介できればと思います！

• 娘(白)とAI(黒)との対戦。白の番ですがいつのまにか置ける場所が無くなっていました。これがAIの力なのか・・・と震えた瞬間です。

後日談

2週間くらい色々チューニングしつつ学習を進め、ある日対決をしたところついにAIに負けました。なんというかなかなか隅に置かせてもらえず、終盤なんとか取れたもののその時にはかなりの石を取られている状態でした。

• 先手(○)が自分で後手(×)がAI

本記事は、CCC MARKETING TECH BLOGを、再編集して転載したものです。