筑波大学オセロサークルMiN2

MiN2のにゃにゃんです。

実は私は趣味でオセロAI(オセロに着手するプログラム)を制作していまして、世界的なオセロAIコンテスト*1で世界1位だったりします。画像は2022年10月現在の順位表で、一番上が私です。

私の開発したオセロAI Egaroucidは、オセロの研究に使えるソフトとして無料で公開しています。こちらもぜひご覧ください。

www.egaroucid-app.nyanyan.dev

人力でのオセロの実力は連盟2級程度ではありますが、オセラー兼オセロAI開発者として色々と思うことがあったので、今回はオセラー向けに「オセロAIとの付き合い方」という内容で記事を書きます。オセラー向け記事ですので、技術解説は全くしません。気になる方は最後に紹介する私の別記事などをご覧ください。

オセロAIは速いが人間は賢い

オセロAIとの付き合い方を考える上で、まずはオセロAIが根本的に人間とは違うことをご説明しましょう。

AIと聞くとなんだか人知を超えた魔法のような気がするかもしれませんが、そんなことはありません。むしろ、とても単純な計算しかしていません*2。コンピュータというものはそもそも、「賢い」というよりは、「単純な計算を爆速でできる」ことに価値があります。これが人間との大きな違いです。人間は思考(計算)スピードこそコンピュータに敵いませんが、できる思考(演算)はコンピュータよりも高度であると言えます。

盤面に着手した状態を想像する作業は、人間にとっては結構大変なものですが、コンピュータにとっては何ら苦労せずにできる作業です。具体的な数字を出しましょう。私のオセロAI Egaroucidでは、1手着手する処理にかかる時間はたったの $10^{-8}$ 秒、10ナノ秒ほどです。これがコンピュータの計算スピードです。

しかし、コンピュータは「常識的な手」を見つけることが苦手です。中割り程度であれば機械的に計算することができますが、例えば辺への着手など、様々な要因が絡む着手は非常に苦手です。これが人間の賢さです。コンピュータは、明確に(そしてある程度簡潔に)記述できることしか処理できません。

オセロというゲームにおいて、この特性が顕著に現れるのがまさに先読みです。

私も含めて多くのオセラーは、「この手を打ったら多分相手はあの手で返してくるから、そうしたらこう切り返せるから大丈夫そうだ」のように、手筋を読むでしょう。そして、特に私について言えば、読む深さは深くとも5手の筋を1、2本読む程度です。

しかし、オセロAIはその計算スピードを武器に、良手も悪手もなりふり構わず、とにかく全部先読みしてしまいます。*3そして、オセロAIは手筋を読むのではなく、先読みをした結果の盤面の見た目で判断します。オセロAIを触ったことがある方ならご存知でしょうが、実用上、オセロAIは20手から30手程度の先読みをします。これは、コンピュータが十分高速であるから為せることとも言えますし、逆に、手筋を読めないがためにそれだけ深く読まないと良手を発見できないとも言えます。さらには、この後解説する評価関数に起因する要因が深読みせざるを得ない状況を作っているとも言えます。

評価関数という統計

オセロAIを触ったことがある方は「評価関数」という言葉をご存知でしょう。評価関数は、盤面の見た目で優勢か劣勢かを判定する部分のことです。実は、オセラーがオセロAIに対して感じる疑問や不満は、ほとんどこの評価関数の問題に帰着できます。

そもそも、評価関数というものは統計の上に成り立つだけで、それ以上の根拠を持っていません。わかりやすく例えるならば、「ピュアウィングは弱い」と言う知識を統計的に持っているだけのようなことです。しかし、それは概ねそう言えるだけです。例えば下の画像のような場合であれば、黒がピュアウィングを作る手が最善です。

EdaxやEgaroucidを含む現代の強豪オセロAIの評価関数は、盤面の一部のマスだけを見て、その中の石の並びで点数をつける作業を繰り返すことで評価関数を構成しています。*4 *5

盤面の一部のマスを見ることを繰り返しているに過ぎないため、実は現代の強豪オセロAIは盤面を俯瞰できないのです。盤面を俯瞰できなければ、当然盤面を正しく評価することは難しくなります。これが現代のオセロAIにおける評価関数の大きな問題です。

オセロAIがやけに深くまで先読みするのには、評価関数の精度の悪さという根本的な理由があります。深くまで読めば、探索すべき局面は多くなります。具体的な数式を挙げれば、オセロにおける各局面での合法手がだいたい $b$ 個のときに $d$ 手の先読みをすれば、探索すべき局面はだいたい $\sqrt{b^d}$ 個になります。*6具体的に数字を入れてみましょう。わかりやすく合法手 $b=10$ 個、 $d=10$ 手先読みするとすれば、探索すべき局面は $10^5$ 個、つまり10万個にもなります。これだけ沢山の局面を見ることができれば、評価関数の精度の悪さはある程度無視できるようになると期待できます。

オセロAIは明らかな悪手を省いて探索する

ここまで、「オセロAIは全ての合法手をなりふり構わず先読みする」ような書き方をしてきましたが、実際には少しだけ違います。EdaxやEgaroucidなどのオセロAIは、主に2種類の方法で探索を省略しています。このうち、特に1つの手法がオセラーにとって重要な意味を持つので解説します。*7

EdaxやEgaroucidでは、強さのレベルに応じてになにやら確率のような数字が出てきます。例としてEgaroucidの画面を出しましょう。

Egaroucidでは、「探索確率」として、81%から100％の数値で探索を行っています。わかりやすさのために、ここからは終局まで読み切ることを念頭に話を進めましょう。

100%の確率で探索するというのは、要するに完全読みです。終局まで完全読みをすれば、オセロAIの評価値が狂うことは一切ありません(オセロAI自体にバグがなければ)。

では「100%未満の確率で探索する」というのはどういうことでしょうか？唐突ではありますが、ここで人間のあなたに一つ先読みをしていただきましょう。

こちらの盤面は、黒番で様々な変化が考えられます。この局面に初めて遭遇したとします。多くの場合、それぞれの手について着手した様子を頭の中で想像してみることでしょう。しかし、特別な理由がない限り、g7の手は最初から考慮しないと思います。なぜでしょうか？h8の隅を取られやすくなる、見るからに悪手だからです(人間であればあえて打つ場合もあるでしょうが…)。

100%未満の確率で行う探索はまさに今のような思考をコンピュータにさせるようなものです。具体的には、深い探索を行う前に十分に浅い探索を行って、その結果があまりにも悪ければ、もうそれ以上の探索をしないというものです。*8

では確率の数値は何を表すかと言うと、要するにどれくらい勇み足で探索を省略してしまうかの度合いです。値が大きければ省略に慎重になりますが、値が小さければ少し際どい手も思い切って探索を省略してしまいます。

オセロAIの評価値が顕著に狂うことがある

強いはずのオセロAIが、評価を著しく間違うことがあります。この原因について、簡単に解説しましょう。

少し先読みを浅くしていますが、この局面は多くのオセロAIが評価を間違えやすい局面です。実はこの盤面の最善手は黒a3で、評価値は+10です。この誤差は主に2つの要因によって起きる現象です。順番に説明しましょう。

1つ目の原因は、単純に評価関数の精度の悪さによるものです。上の画像では10手先読みした結果を表示していますが、まさに評価関数の精度の問題で値が著しく実際のものとずれています。

2つ目の原因は、明らかな悪手を省いた影響です。上の画像では10手を100%の確率で先読みしていますが、これを最終手まで読み切らせる設定にしてみましょう。下の画像では99%の確率での探索を行っています。

同じ局面を最終手まで99%の確証で読み切らせた様子。依然a3の評価値(実際は+10)がおかしい

最終手まで読み切っているはずなのに、評価値は本来の+10からかなり離れた値になっています。これは悪手と思しき手を省いてしまった影響です。

ちなみに、ある手が悪手かそうでないかを判定するためにはもちろん評価関数を使用するため、結局はこれも評価関数の精度の問題に帰着できます。

要するに、オセロAIの評価がおかしいときには、評価関数にとってこの局面が難しいんだろうということになります。

評価値が全てではないと思う

ここまでで、主にオセロAIの評価関数に関する特徴的なクセを解説しました。

これは個人の考えの範疇を出ませんが、私はオセロAIを作りつつ人力でオセロを楽しむ中で、評価値が全てではないという考えを強めています。上記のように、オセロAIが評価を間違えることがあるという文脈でも言えますし、それ以上に、人間によるオセロの楽しさは、人間の先読みが手筋を読むことであるとも思うからです。

ここに書いたことはかなり細かい内容ですが、オセロAI開発者として、どうか、オセロAIとうまく付き合っていただければ幸いです。

オセロAIの技術が気になった方へ

オセロAIの技術については、いくつかの記事を書きましたのでよろしければご覧ください。

私がオセロAIで世界1位となるまでの軌跡を書いたものです。

qiita.com

オセロAIを作ると何が嬉しいのかを熱弁し、オセロAIを作る最初の一歩の手助けをする記事です。

qiita.com

オセロAIの初歩からステップアップして強いものを作るための記事集です。投げ銭機能がありますが全編無料で読めますので、ぜひご覧ください。

note.com

また、私のオセロAI Egaroucidのソースコードは全部公開しています。表示してあるライセンス*9の下で自由にお使いください。

github.com

オセロAIに関する(ものも、関係ないものも)質問をお待ちしています。また、筑波大オセロサークルMiN2は人力オセロのサークルですが、オセロAIについても教えることが可能ですので、オセロAIに興味がある方もぜひMiN2へ！！

*1:CodinGame Othello Leaderboard "Othello" - CodinGame

*2:オセロAIに限らず、最近話題の色々なAIも、結局は単純な計算を大量に行っているだけです

*3:この言い方だと少し語弊があるのですが、技術の内容になるのでここでは解説しません。気になる方はαβ法による枝刈りを調べてみてください。

*4:厳密に言えば、私のEgaroucidはさらなる工夫を施しました。詳細は私のこちらの研究報告にあります(が、2022年現在有料です) 情報学広場：情報処理学会電子図書館

*5:ちなみに、この方法は1997年にオセロAI Logistelloが当時の世界チャンピオン村上健氏に勝利したときから25年ずっと変わっていません。

*6:なぜこの数式になるかが知りたい方は、minimax法とαβ法について調べてみてください。

*7:ここで説明しないもう一つの省略はαβ法による後ろ向きな枝刈りです。これは探索結果に影響を及ぼさないのでここでは解説しません。

*8:この手法はProbCutと言い、こちらも1997年頃のオセロAI Logistelloからほとんど形を変えていません。さらに余談ですが、前述のパターンによる評価とProbCutが「Experiments with Multi-ProbCut and a New High-Quality Evaluation Function for Othello」という同一の論文で1997年に提案されました。

*9:2022年現在でGPL-3.0という若干再利用しにくいライセンスですが、個別に相談してくだされば可能な範囲で対応しますのでお気軽に連絡をください。