乱数は知能を持つか - モンテカルロ木探索でオセロAIを作った話
これはなに？
このnoteはIS24erと25erによるアドベントカレンダー4日目の記事です。
3Sの関数論理型プログラミング実験の授業の最終課題でオセロAIを作り、履修者が作ったAI同士を総当りで対戦させるということをしました。何年前からこの最終課題が出されているのかわかりませんが、この課題に関する記事は意外と少なかったので書いてみます。
関数論理型プログラミング実験とは
東京大学理学部情報科学科の授業です。関数型言語としてOCamlを、論理型言語としてPrologを学びます。前者のほうが時間をかけてじっくり学びます。特にOCamlでOCaml(っぽい言語)のインタプリタを作るといったことをやります。
オセロとは
オセロ（Othello、Reversi）は、2人のプレイヤーが交互に盤面へ石を打ちながら、相手の石を自分の石で挟むことによって自分の石へと換えていき、最終的な盤上の石の個数を競うボードゲームである。
多分大体の人がルールくらいは知っているので詳細な説明は割愛します。
1997年にオセロAI「ロジステロ」が当時のオセロ世界チャンピオン村上健氏に完勝しています。その年はチェスでもコンピュータプログラムが人間のチャンピオンに勝利していてゲームAIの界隈では記録的な年なんだと思います。自分はオセロは昔一ヶ月位ハマった程度で強くはないのですが、村上健氏の「史上最強カラー図解 強くなるオセロ」だけは持っています。
課題の概略
「オセロの思考ルーチンを実装する」というのが課題の内容です。言語はOCaml, Rust, Prolog, Haskellが認められていますが、それ以外の言語も事前に先生に相談すれば使える可能性があるらしいです。
そして定められたプロトコルに従って対戦できるようにします。課題の締切後、学生が提出したプログラムを先生(もしくはTAさん)が実行して互いに対戦させてくれます。持ち時間は1分です。自分のときは、自分の順位のみを教えてくれました。
結果は？
1位でした。2~5位のプログラムとはおよそ互角の強さだったのでクラスの中で圧勝したというわけではないのですが、他の人達と違う手法を用いていたので記事にしてみます。
みんなが採用している手法と全く異なる方法を選ぶのってわりと勇気がいることだと思うのですが、うまくいくこともあるよ～というの気持ちになってくれたら自分としては嬉しいです。あと、IS25, IS26,… 以降の方の参考になればと思います。
実装について
用いた言語
Rustを使用しました。処理速度が速いらしいというのと、後述する理由で64bitのunsigned intが必要だったというのと、クラスの人にRustを勧められたというのが主な理由です。Rust自体は書いたことが今まで一度もなかったので文法の勉強から始めました。GitHub Copilotが賢いので意外となんとかなりました。コンパイラのエラー出力が丁寧なのが嬉しいです。
かかった期間
自分のコミット履歴を見ると5日くらいで作ったらしいです。期末試験前に2日くらい、後に3日くらいといった感じでした。ただRustの勉強に1日かかったのは数えていません。
あと、そもそも高校生の頃にオセロのAIを作ったことがあってその当時はC++で実装したのでそれをRustで書き直し、改良したって感じです。アルゴリズムを0から書いていたら多分もう少し時間がかかったと思います。
ソースコードは？
さっき公開しました。通信のプロトコルの部分は自分が書いたわけじゃないのであまり理解していません。TAさんに公開していいかの確認は取りました。
どういうアプローチ？
まず試合を序盤、中盤、終盤にわけます。序盤は定石を使います。そして終盤は読み切ります。中盤が一番工夫の市街があるところで自分はモンテカルロ木探索を採用しました。他の人達はだいたい評価関数を書いていました。
序盤について
定石を使います。「オセロ 定石」とかって検索するといくつか見つかります。自分はWZebraという強いオセロソフトの使っている定石を使いました。(ネットや他のソフトの使っている定石を使用してよいかは先生に問い合わせたほうが良いと思います。)
ただし、コンパイル後のプログラムのサイズに制限があります。だから1GBとかの定石を使用することはできません。大きな定石データは良い定石については35手以上書いてあったりしますが、適当な長さで切っていれるといいと思います。あと、どちらかというと良い定石を長く(35手とか)覚えるよりも、相手が悪手(悪い選択肢)を打ってきた場合にどう対応するべきかという定石を持っておくと他の人のプログラムと対戦したときの勝率が上がる傾向がありました。狭く深くより、広く浅くを目指し、良い手でも25手で定石を打ち切りました。
面倒だったので自分はやりませんでしたが、うまいことデータを圧縮して持っておければよりたくさん定石を覚えておけるかもしれません。
相手が定石から外れる手を打ってきたら中盤へと移行します。あまり強くない相手と対戦すると最初の7,8手で定石から外れますが、強い相手だと20手以上定石通りに戦うということもありました。
定石を検索するだけならO(1)でできるので持ち時間の節約にも大きな効果があります。そして中盤のアルゴリズムは試合が進めば進むほど強くなるアルゴリズムなので、できるだけ最初は定石を打つだけにしたいです。
中盤について
モンテカルロ木探索をやります。何が嬉しいかというと評価関数を書く必要がありません。そして並列に実行することが比較的かんたんなアルゴリズムになっています。ただし弱点としては試合があまり進んでいない状態だと弱いということです。モンテカルロ木探索について知らない人向けに書いているので知っている人は次の見出しまで進んでも大丈夫です。
まずアイデアの説明をします。課題では「ランダムに打つプログラムに対して平均的に勝利する」ということが要件となっています。ランダムに打つというのは打てる場所から一様ランダムに選ぶということです。これは非常に弱いです。多分オセロを人生で初めてやる人より弱いと思います。これに対して勝つということを考えると１つのアイデアとして「ある盤面から両者ランダムに手を選んで最後までプレイさせる。それを繰り返すことでその盤面はどちらが有利なのかを判定する」というものが思いつきます。ある盤面$${A}$$において石を置ける場所が$${n}$$個あって、それを順に$${a_1, …, a_n}$$とします。$${a_1}$$に石をおいた後の盤面を$${B_1}$$、$${a_2}$$に石をおいた後の盤面を$${B_2}$$…として、$${B_1}$$から両者ランダムに手を選んで終局まで対戦するというのを100回繰り返し、次は$${B_2}$$から両者ランダムに手を選んで終局まで対戦するというのを100回繰り返し…$${B_n}$$まで、合計で$${100n}$$回の対戦をシミュレートします。そして自分側が勝った回数が最も多い手を選びます。これが最も単純なアイデアです。実際のところこれだけで課題の要件は満たせます。ある意味当然で、相手がランダムに打つとわかっているので、こちらはそれをシミュレートして確率的に勝てる手を打つというだけのことです。ただ、これだけだと人間相手にはほとんど勝てないでしょう。なぜなら人間はランダムに打たないからです。人間は「この手を打つと相手がこうするだろう」とか「この手を打つと相手がこうするだろう」というように相手の手を読むことができます。今度は1手しか読まないのではなく何手か先まで読んだうえでそこから先は両者ランダムに打って終局まで対戦するというのを繰り返します。
では何手先まで読めばよいのでしょうか？根を今の盤面、その子を1つ手を進めた盤面としたゲーム木を考えます。すると深さに対して葉は指数関数的に増加します。中盤であれば5手先まで考えると数万から数十万の葉があることになります。それぞれについて100回のシミュレートをしようとするととても時間がかかってしまい持ち時間が足りません。
再び人間の思考を考えてみると、「良さそうな手については深く読む」というアイデアが出てきます。これを取り入れてみることにすると、勝率の良い手については深く読んでからシミュレートを行い、勝率の悪い手については浅く読んでからシミュレートを行うということができます。また例えば「今までにシミュレートした回数は3回でそのうち1回自分が勝った」という盤面と「今までに100回シミュレートしてそのうち55回自分が勝った」という盤面があったとします。これは後者のほうが勝率が高く信頼性もあると考えられますが、前者は3回しかシミュレートしていないため実際の勝率は$${\dfrac{1}{3}}$$より著しく大きい可能性があります。そのため、次は前者の方をシミュレートするということをやります。
以上をまとめると、モンテカルロ木探索は以下のようなアルゴリズムになります。
ゲーム木の各ノードは盤面を表している
葉ノードにおいてどちらかがどれくらい有利かということをその盤面から両者がランダムにプレイしたときの勝率で見積もる。これをプレイアウトと呼ぶ
一定回数以上プレイアウトした葉ノードは子ノードをもたせる。つまりその盤面から更に1手読むということ。これを展開と呼ぶ。
根から順に「勝率が高くまだあまり訪れていない」子を選択して葉ノードまで辿る
プレイアウトが終わったらその情報を親ノードに伝えて情報を更新する
勝率の高さと訪問回数のバランスの部分は$${\dfrac{w}{n}+\sqrt{\dfrac{2\log N}{n}}}$$という値が最も高い子ノードを選択すればよいらしいです。$${n}$$がその子ノードの訪問回数、$${N}$$が親ノードの訪問回数、$${w}$$がその子ノードにおいて勝利した回数になっています。選択された回数の少ないほど大きくなる値に勝率を足していますね。ただ、これは最初の論文で提唱された計算式で現在は改善された数式が使われているようですが、それについては詳しく知りません。興味がある人は論文を読むと勉強になると思います。
あと、勘違いされがちなのですが、最終的には根ノードから見て最も訪問回数の多い子ノードを選択します。なぜ勝率を基準に選ばないのかというと、訪問回数の多いノードのほうが勝率の信頼度が高いからです。
終盤について
最後は読み切りをします。空いている箇所が残り22箇所以下になったら終盤としました。ただ、読み切りにも
両者最善手を打ったときにどちらが勝つかのみを調べる
両者最善手を打ったときに何石差になるかを調べる
という2種類あります。後者を石数込みの読み切りと呼ぶことにします。前者についてはある盤面において手$${a_1,…,a_n}$$のうち$${a_1}$$に打てば勝てるとわかったら$${a_2,…,a_n}$$という残りの選択肢は調べる必要がありません。石数込みの読み切りではすべての手を調べる必要があります。ということで石数込みの読み切りは空いている箇所が残り16箇所以下になったらやることにします。
石数込みの読み切りができたとき → 最善手を選べば良い
ただの読み切りしかできなかったとき→ 自分が必勝なら必勝手を選べば良い
ただの読み切りしかできず自分が必敗だとわかったとき → 中盤のモンテカルロ木探索を再びやる
ただの読み切りもできなかったとき → 中盤のモンテカルロ木探索を再びやる
という流れになります。
それでこれは強いの？
微妙です。オセロ初心者にはまず勝てると思いますが、少しでもちゃんとやったことある人には勝てません。
どうやったら強くなるの？
ここまではオセロに限定されないゲームAIの話をしていたのですが、ここではオセロ特有の話をします。
取り入れるとよい概念として「着手可能箇所数」というのがあります。の盤面において (自分が打てる場所の数) ー (相手が打てる場所の数)を計算します。この値が大きな盤面というのは自分は選択肢がたくさんあり相手には選択肢があまりないということでオセロにおいては一般的にかなり有利な局面と言えます。
プレイアウトのときに完全に両者ランダムに打つのではなく、一定の確率で着手可能箇所数の差が大きくなるような手を選択することにしました。つまり一定の確率でそこそこ良さそうな手を選ぶというのを実現したということなのですが、どの手がそこそこ良さそうかを調べるのに時間がかかっていたら意味がありません。プログラムで高速に判断できる基準があればよいです。
別の基準としては隅が取れるかということも基準になると思いますが、最初の方は両者盤面の中央に打ちがちでいきなり端の方には打たないという問題がありますね。
これをやるとだいぶ強くなって、自分がプログラムと対戦しても勝てなくなっていました。
他には？
他にもいくつかやると良さそうなことがあります。
ビットボード
オセロは8×8の盤面なので、石がおいてあるかどうかを1bitで表すと64bit整数になります。自分の石と相手の石は区別するべきなので64bit整数2つで表現できることになります。
そしてある盤面から次に打てる箇所はシフト演算とAND、ORで計算できます。愚直に考えると3重ループが必要になるのですが、それが整数演算でできるようになるので計算がかなり早くなります。
さらに配列ではなく整数の演算にすることでメモリアクセスが減ってレジスタ上で計算ができるようになるんじゃないかなと思っています。(これは生成されたアセンブリで確かめたわけじゃないので推測ですが)
とりあえず良いことづく目でデメリットは実装がめんどくさいことだけです。実装は「オセロ ビットボード」って検索すればいろいろな記事が見つかるので読みやすそうなのを探してください。
ちなみにOCamlでは整数がデフォルトで63bitなのでめんどくさいらしいです。
並列化
中盤のプレイアウトは並列にできます。ただ、自分は実装できませんでした。Rustの所有権の概念に阻まれました。コンパイラのエラー出力を眺めCopilotに聞いてコードを修正して再びエラー出力を見て……というのを$${n}$$回繰り返したのですがだめでした！実力不足です。モンテカルロ木探索は探索回数が肝なので並列化できたら強くなると思います。
読み切りの効率化
石数込みの読み切りは全探索なのですが、ただの読み切りをするときには探索順序が計算量に影響を与えます。魔法によって任意の盤面における最善手が分かるなら、本当にその盤面が必勝なのか、もしくは必敗なのかを確かめる計算量が$${\dfrac{1}{2}}$$乗になります。$${\dfrac{1}{2}}$$倍じゃないです。これは同じ時間で読み切れる深さが2倍になるということを意味します。
ただ、もちろん何が最善手かが分かる魔法は存在しないので、良さそうな手から順に調べるということをやります。これによって読み切れる深さがだいぶ増えます。(定量的に比較するのは忘れました。レポートに書くべきだった)
感想
ここまで読んでいただきありがとうございました。
クラス内では1位でしたが、世の中のオセロソフトは自分が作ったプログラムの比じゃないくらい強いので興味があればぜひ色々と調べてみてください。
また来年以降もそうなのかはわかりませんが、自分のときは順位がこの課題の評価に直結するわけではなく、面白いアイデアを実装してきちんとレポートがかければ良い評価がもらえるということだったので、思いついたアイデアは試してみると良いと思います。
最後に適当な感想を述べます。こういうのをポエムと表現しようかと思いましたが、それは詩人とか詩が失礼な気がしてきたので「適当な感想」と表現します。
自分がモンテカルロ木探索を知ったのは中学生の時だったと思います。Google DeepMindの開発した囲碁プログラム「AlphaGo」がイ・セドル九段に勝利したというニュースを見て興味を持ってゲームAIについて調べたり本を読むなどしていました。そしてモンテカルロ木探索について知ったときに、こんな簡単なアイデアで人間の知能と戦えるのかと衝撃を受けました。
何をもって知能と呼ぶのか、というのは難しい問題だと思います。まあオセロが知的な要素を含むゲームであるというのは多くの人が同意すると思うので、乱数を活用した単純なアルゴリズムでも知能を持つという考え方は十分にできるのではないでしょうか？
知能が必ずしも人間らしい形式で実現される必要はないのだと思います。もちろん社会でAIを活用しようとすると、中身も人間に理解されやすい形であることにも価値があると思いますが、単に人間の入出力を真似るだけなら中身が人間らしい必要はないのだと感じました。
その一方でプログラムは人間がプログラミング言語を使って書くので、どうしても言語という思考の枠組みに縛られてしまうように感じます。最終的には命令の列という手順書に翻訳されてしまうわけですし。
その中で、乱数を使うというのは人間の枠組みから比較的外れているという点で面白いですね。論理というものの対極にあるといえます。
ある集合から性質の良い分布に従って要素をサンプリングできる、ということに価値があるのだろうなと思います。たとえばある有限集合$${U}$$から一様分布でサンプリングできれば$${U}$$の部分集合$${A}$$に対して$${\dfrac{|A|}{|U|}}$$の割合を近似できますね。モンテカルロ木探索はある盤面からあり得る棋譜をサンプリングしていることになります。最初は本当にただのランダムですが、探索が進むと強いプレイヤー同士が選ぶ可能性の高い棋譜が優先してサンプリングされるようになりますね。
雑な感想はこの辺にしておきます。ちなみに今は3Aなので、CPU実験をやっています。コンパイラ係です。Rustを使ってます。オセロ以来なので再び文法を思い出すところからやり始めました。頑張ります。
CPU実験もいつか記事にしたいです。ではこの辺で。またどこかでお会いしましょう。
自己紹介を忘れていた
IS24erのiのi乗です。ツイッターのアカウントは https://x.com/iptnatsnoc です。数学が好きです。久々にこのnoteを更新しました。他の記事では数学の話をしていたりしますが、黒歴史みたいな文章が多すぎるので読むと網膜が焼けます。