見出し画像

世界15位のオセロAIを作りました

にゃにゃん(山名琢翔)

こんにちは、ものづくり・プログラミング・ルービックキューブのにゃにゃんです。今回もプログラミングの内容です。

オセロAIとは？

オセロを自動でプレイするプログラムのことです。

今回作ったものはGitHubで公開しています。

https://github.com/Nyanyan/Reversi


作ったオセロAIの強さ

2021/12/09追記

2021/12/09現在このAIの改良版が世界1位です。記事はこちら

また、オセロAIの作り方を詳しく解説する記事集を書きました(有料記事ですが投げ銭機能の意味なので全編無料です)。

追記終わり

かなり強いオセロAIを作りました。具体的に言うと、オセロAIの中で世界15位の強さです。

CodinGameというゲームAI(オセロに限らずゲームを自動でプレイするプログラム)のコンテストサイトがあり、そこで他のAIと戦わせたらなんか世界15位になれました

画像1


また、インターネットで公開されているオセロAIの中でもとても強い部類に入るMaster Reversiにも勝ちました。

Master Reversiのリンクを貼っておきます。ほとんどの人間は勝てないのではないかと思います。

http://t-ishii.la.coocan.jp/mr/mr.html


ゲームAIの考え方(の一例)

おそらく大半の人は「AI？！難しそう…どうやって作るんだろう」と思うことと思います。私も2週間くらい前まではそうでした。

でも基本的な概念は簡単です。

2人で対戦するゲームは一般的に、先手と後手が交互に操作をしていき、最終的に何らかの指標で勝者を決定します。

オセロであればプレイヤーは最終的な自分の石数を最大化することを目標に手を打っていきます。そして、これに加えて大切な考え方が、プレイヤーは「自分にとって一番有利=相手にとって一番不利」な手を選ぶということです。

つまり、二人で対戦するゲームであれば、以下の繰り返しでゲームが進んでいきます。

先手: 先手にとって一番有利な手=後手にとって一番不利な手を選ぶ
後手: 先手にとって一番不利な手=後手にとって一番有利な手を選ぶ

ゲームAIを作るときにこの考え方はとても大事です。

ゲームAIは、次にどの手を打てば自分が勝てる可能性が一番高いかを常に考えることになります。これを先程の議論を踏まえて言い換えると、相手が最善な手を打ってくる、つまり、相手が自分に一番不利な手を必ず打ってくるとしたとき、自分がどの手を打てば勝てるのかを考えることになります。

相手がもし最善でない手を打ってきても、それは自分にとってますます有利になるだけなので考えなくて良さそうです。


ゲームAIアルゴリズム(の一例)

この記事では有名なアルゴリズムであるminimax法というアルゴリズムを念頭に紹介しますが、他にも様々な派生アルゴリズムや全く別のアルゴリズムがあります。ちなみに私のゲームAIではminimax法の派生であるNegaScout法を使いました。

さて、先程の議論で、ゲームAIにおいて次の手を決定するときには相手が必ず最善手を選んでくることを仮定するとしました。では実際のアルゴリズムを見てみましょう。

画像2

この図は一番上(盤面A)が現在の盤面で、そこから考えうる手を考えたときに次の盤面、その次の盤面がどうなるかを考えたものです。盤面には説明のためにアルファベットを振ってあります。

一番下の盤面(EからJ)には数字がついています。これはその盤面がどれくらい自分に有利かを示した数値で、評価値と言います。評価値については後で詳しく説明しますが、一般的には0は互角、正なら自分が有利、負なら相手が有利とします。

2手分の全ての盤面を読んだ結果、評価値5(盤面E)が一番自分にとって有利そうです。しかし、評価値5の盤面Eに至るためには相手がそのように手を打つ必要があります。よく見ると、盤面Eに至るには、現在の盤面Aから盤面Bを経由して、盤面Eとなる必要があることがわかります。しかし、盤面Bからは次の盤面として評価値2の盤面Fが生えています。盤面Bから操作するのは相手で、相手は相手にとって一番有利=自分にとって一番不利な手を選びます。よって、実は評価値5の盤面Eに直面することは(相手が最善な手を打ってくる仮定の元では)ありません。

ところで、ゲームAIが今知りたいのは何でしょうか。次に自分がどの手を打つと一番有利なのかを知りたいのです。つまり、盤面B、C、Dのどれが一番有利なのかを知りたいのです。これを知るために、上の議論が役に立ちます。

現在、盤面BからDには評価値がついていません。そのため、どの盤面が有利かはわからないのです。しかし、そこから一つ進んだ盤面EからJには評価値がついています。この評価値たちをうまく使って盤面BからDに評価値をつけられないでしょうか。

ここでもまた、「相手は相手にとって一番有利=自分にとって一番不利な手を打ってくる」考え方が出てきます。

相手は選びうる盤面の中で評価値が一番低くなる盤面を選ぶように手を打ってきます。つまり、

画像3

この図で相手は太い線の手を打ってくることが予想されます。よって、BからDの盤面では太い線の先の評価値が採用できます。

それぞれの盤面での評価値は、Bは2、Cは-1、Dは-10です。自分はこの中で一番評価値の大きい(自分にとって一番有利な)手を選べば良いので、盤面Aから盤面Bに至る手を打てば良いことになります。

これでゲームAIの求めたいもの「次にどの手を打つのが最善か」を知ることができました。めでたしめでたし。

探索深さを今回は2手としました(2手先まで読みました)が、これを深くしても、自分は評価値の大きい手を選び、相手は評価値の小さい手を選ぶという考え方を適用できます。


評価値の決め方

評価値は全て決まった尺度で決める必要があります。そのためには評価関数という名前の関数を自分で作って使うのですが、この評価関数、うまい作り方はありません！！

いや、むしろ評価関数をうまく作れないからこそゲームとして面白いんです。評価関数を簡単に作れる、つまり盤面の評価値を簡単に決められてしまっては、人間は常に最善に近い手を打つことが簡単にできてしまいます。これではつまらないですね。

しかし、評価関数を作る上で指針はあります。これについてはツカモさんの記事がとてもわかりやすいです。

https://qiita.com/tsukammo/items/de70b49dcd8912e78505

私のオセロAIの場合、評価関数は以下の値を使って書きました。

1. 盤面の各マスにつけた重みの平均の差
2. 合法手数の差
3. 確定石の差
4. 直前の手の開放度
5. 内側への入り込み度合い

オセロでは一般的に、角を取ると良い、だの打てる場所が多いと良いだの言われています。これを念頭に、盤面の状態を評価することにしたらこのような値を使う評価関数が適当でした。


最後に

かなり強いオセロAIを作ったよ！という話でした。本格的にゲームAI作りをしたのは初めてでしたが、とても楽しめました。

まだまだゲームAIに関する知識は乏しいので、間違ったことを書いていたりしたらコメントなりTwitterのメンションなりDMなりをください。

それでは～！

いいなと思ったら応援しよう！