命令セット自作のすすめ
この記事はISer Advent Calendar 2020の22日目として書かれたものです。昨日はKazuki Otaさんのp5.jsからPythonの関数を呼び出す。でした。
こんにちは。IS20erのRisebbit1と申します。自作CPUがなんとか完動したのでこの記事を書いています。
IS(東京大学理学部情報科学科)といえばCPU実験ですね。この実験では学生が3~4人の班に分かれてCPUやコンパイラなどを作ります。私が担当するコア係は土台となるハードウェアの部分であるプロセッサコアを作るのが仕事です。命令セットを設計して、その命令セットを動作させる回路を設計したらVerilog HDLに書き起こすというのが大まかな流れになります。
さて、そんなわけでまず最初にやるのは命令セットの設計です。せっかくオリジナルのCPUを作るわけですから、命令セットもオリジナルな物を作りたいですよね？...ね？
ところが結局、今年命令セットを1から作ったのは私の班だけでした。えぇ...。他の班はRISC-VやMIPSをベースに作っているようです。しかしこれは寂しいのでオリジナル命令セットを作る方が1人でも多くなることを期待してこの記事を書くことにしました。
自作しようと思った理由
自作と言ってもアセンブリの書き方はほとんどRISC-Vと同じです。大きく異なるのは各命令に対応する機械語のフォーマットです。以下に示すのがRISC-VのR形式のフォーマットです。
これを見ると分かるのですが、パーツがやたら多いです。アセンブリでは例えば add a0, a1, a2 と書いているので、この命令に対応する機械語は4つのパーツがあれば十分なはずです。functなんて使わずに全部opcodeにまとめてしまいたい、そう思ったのが自作のきっかけです2。もちろんRISC-Vがこのような設計になったのは理由があるはずで、高性能なハードウェアの実現に役立っていることでしょう。しかし、複雑なフォーマットであることも事実で、初めて作るCPUはより単純なフォーマットにしたいと考えました。他にも、自分で設計したものは自分が一番良く分かっているので改良がしやすいというメリットもあります。
また、仕様書を読むのが苦手で既存のフォーマットを理解して再現するぐらいなら自分で設計したほうが楽しいと思ったのも理由の一つです。今まで他人が決めたルール(言語仕様やアーキテクチャ)の上で動くものをさんざん作ってきたわけです。このCPU実験はそんなルールを決める側になる数少ない機会です。コンパイラは自分が決めたルールを守ってくれます。世界のルールを決定する神になる、そんな貴重な機会を逃すわけにはいきません。
自作命令セットの紹介
そうは言っても、課題プログラムがどのようなものかよく分からない状態で完璧な命令セットを作るというのは無理な話で、私自身完動するまでに命令セットの改良を何度も行いました。
設計の方針としてはまず最初に必要そうな命令を列挙して、オペランドの数や種類を見て形式を分けます。オペランドがレジスタ3つの命令とオペランドに即値がある命令は別の形式にしたほうが良さそうだなーといった具合です。そしてそれぞれの形式の中身を決めていきます。後で必要と分かった命令が増えることもあり得るので余裕を持たせておくと良いです。こうして一番最初に作ったフォーマットはこのようなものになりました。
MSB側の3ビットは命令形式を識別するために使っています。nは即値、r0, r1, r2はレジスタを指定するフィールドです。上述の通りopecodeを左側に1つにまとめ、右側から即値、レジスタを並べて間を0で埋めるというシンプルな構造です。しかしこのフォーマットには重大な欠点がありました。命令の形式が分からないとアクセスすべきレジスタの番号が分からないのです。これは普段ハードウェア設計をしている方ならすぐに気づきそうなことですが、初めてだと気が付きませんでした。レジスタを指定するフィールドを同じ場所に置かなかったのが原因で、これによってレジスタフェッチまでに1クロック多く使ってしまうのです3。気をつけることはこれぐらいで、これさえ守っていれば基本的にはうまくいくと思われます。(というかこれを守らなかったとしても単位を取るには十分なコアができる気がします。)
この後D形式が必要ないことに気がついたり、メモリアクセスをワード(4バイト)単位にしたりといった仕様変更を経て、完動したときのフォーマットはこのようなものになりました。
レジスタの位置を揃えた点を除いて初期のフォーマットとあまり変化はありません。opecodeを左側に1つにまとめるというコンセプトは初期から全く変わっていません。この分かりやすいフォーマットにより、命令デコーダやアセンブラの実装が楽になったと考えています。また、拡張性などを無視して必要最低限の命令が実装できれば良いので、RISC-Vなどに比べて即値により多くのビット数を割り当てることができました。
ちなみに形式ごとのフォーマットを決めたら個々の命令を作るのは簡単でopの部分が重複しないように並べていけば良いです。並べ方によってデコーダの書きやすさが変わってきますが、それは書いてみれば分かります。具体的な命令の例を少し示します。
終わりに
ここまで読んでいただきありがとうございました。命令設計がそんなに難しいものではなくむしろ他の実装を楽にしてくれるものであり、ルールを作る喜びを味わえるものであるということが伝われば幸いです。
CPU実験のコア係が作るコアは、FPGAの上で動かすことになるのでFPGAの制約を守る必要があります。逆に言えばそれさえ守っていればどんなに変なアーキテクチャにしても良いということです4。今後オリジナルな命令セットや特殊なアーキテクチャが多く作られることを期待したいですね。
私の班の2ndアーキテクチャはまだ設計中ですが、少し珍しいものになりそうです。成功するかどうかは分かりませんが、失敗しても許されるという学生の特権を存分に利用してCPU実験を最後まで楽しみたいです。
OCamlでオセロAIを書く(FL実験2020)
理学部情報科学科3年の必修科目、「関数・論理型プログラミング実験」では最終課題としてオセロAIの実装を行います。これに取り組む上で考えたこと、実装したものを時系列に沿って書いていこうと思います。
まず最初に、okuraさんの記事がとても参考になりました。一部のアイディアも拝借させてもらっています。本当にありがとうございます。
言語を決める
「関数・論理型プログラミング実験」の名前の通り、使用できる言語は関数型・論理型やそれに類する言語に制限されています。具体的にはOCaml, Haskell, Prolog, Rustが明示的に許可されました。ほとんどの人がOCamlで、速度を求める一部の人がRustを使っていた印象です。OCamlはランダムに打つサンプルプログラムが提供されていたのですが、Rustにはそれがなく、審判サーバーと通信する部分なども自分で書く必要があります。明らかに大変そうなので私はOCamlを選びました。Rustをいちから勉強してAIをフルスクラッチした人は本当にすごいと思います。速度で殴ってくるRust勢にOCamlで対抗するためにはアルゴリズムを工夫するしかありません。とはいえ、OCamlも決して遅い言語ではなくそこまで大きな速度差はないように感じました。
準備
開発を始める前に、棋譜を再生できるVisualizerや人間がAIと対戦できるインターフェースを作りました。しかしあまり役に立つ場面はなかった気がします。
ビットボード
オセロの盤面を64bit整数2つで表現します。実行速度が命のAIには必須の技術です。解説サイトがたくさんあるので詳しくはそちらに譲ります。これを忘れて実装を進めると後で大量に修正することになりかねないので最初にやっておくと良いです。
OCamlのint型はガベージコレクションに1ビットが使われているため、64bit整数を扱うためにはint64型を使う必要があります。整数の末尾にLをつけて1Lなどと書くとint64型として扱われます。
骨組みを作る
終盤読み切り
準備ができたのでまず何も考えずに全探索を書きます。全ての盤面を探索して最善の手を選択します。ある意味最強の戦略であり、終盤であれば可能な盤面数が少ないので現実的な時間で読み切ることができます。オセロのようなゲームの全探索の手法はmini-max, nega-maxと呼ばれており、それを枝刈りなどによって高速化したものにalpha-beta, nega-alpha, nega-scoutなどの手法があります。ひとまずmini-max, alpha-beta1を順に実装し、この時点で14手2を安定して読み切ることができました。
中盤
中盤は数手先まで全探索して評価関数が最大の手を選択します。結局全探索です。終盤との違いは評価関数だけです。ということで終盤読み切りのコードを流用し、簡単な評価関数を実装しました。評価関数は強さを決める重要な要素なので後でしっかり調整します。
序盤定石
オセロにはうさぎ定石や牛定石といった定石があり、両者が定石通りに打っていれば序盤ではほとんど差がつかないと言われています。そのためAIにも定石を覚えさせておくと良さそうです。定石と言うからには世に出回っている定石集の内容をコンピュータ用に翻訳したものが落ちているのかと思っていたのですが、そんなものはありません。少なくとも私は見つけられませんでした。定石というのは棋譜です。強いAIや人間が打った手ならそんなに悪い手はないやろという発想です。定石としてLOGISTELLOというAIの棋譜を採用しました。データ形式が扱いやすかったからです。棋譜から序盤の20手を取り出しAIに覚えさせました。ところが棋譜を眺めていると中には白が16石差で負けている試合もあるわけです。もちろんこの差の原因が中盤以降にある可能性も否定できませんが、この棋譜通りに進んでそのまま負けることも考えられます。そこで定石を黒と白に分け、最終的に勝った試合の棋譜のみを採用するようにしました。この仕様が勝敗に影響したかどうかは分かりませんが、少なくとも序盤で不利になる可能性をできる限り排除できたと思います。
強くする
これで骨組みは完成し、ランダム打ちの相手にはほぼ100％勝てるようになりました。これをもとに強くしていきます。この作業は試行錯誤の繰り返しなので苦労したのにあまり強くならなかった時がつらいですね。
pop_countの高速化
pop_countとは64bit整数の立っているビット数を数える関数です。ビットボードを用いた実装ではこの関数が頻繁に出現します。今までは1ビットずつ見ながら数えていたのですが、『ハッカーのたのしみ―本物のプログラマはいかにして問題を解くか』という本を参考により高速なアルゴリズムを実装しました。分かりやすいアルゴリズムでネット上にもいくつか記事があるようです。
move ordering
alpha-beta法では探索の順番によって枝刈りの度合いが大きく異なります。極端な話、最初に最善の手を見つけることができれば探索はすぐに終わります。よってなるべく良さそうな手から探索していくことが重要になります。初めは評価関数を用いて並べ替えていましたが評価関数がまあまあ重いので、okuraさんのアイディアを借りて相手の着手可能数の少ない順に探索することにしました。相手の着手可能数が少ない手というのは良い手でありかつ探索量が少ない手でもあるので、これは良い実装だと考えています。
以上の高速化によって中盤は9手、終盤は20手3程度の探索ができるようになりました。
評価関数
さて、これが問題です。序盤は定石を使っている限り大きな差はつきません。終盤は手数に差はあれ全探索をほとんどの人が実装しています。つまり中盤の評価関数の差が勝敗を左右することになります。評価関数の調整は自作AIどうしの対戦結果や既存のオセロAIの評価関数などを見て行いました。これには多くの時間を費やしました。基本的にはこの報告書の提案を使い以下の3つの値の線形結合としました。
- BP(盤の各マスに割り振られたポイント)
- CN(着手可能な候補数)
- FS(辺上の確定石4の数)
各値の詳しいことはリンク先をお読みください。チューニングの結果、評価関数はBP + CN × 10 + FS × 50になりました。例えばBPを使わないことが検討されましたが、CNとFSだけでは評価関数が同じ値を返すことが多くそれによって悪手を打っていると予想されたため、同じ値の時の判断材料としてBPを小さな重みで加えています。
終盤探索の時間制限
今回のルールは1分切れ負けです。そのため終盤探索には時間制限を設ける必要があります。時間切れにならない範囲でなるべく多く時間を使って探索したい。そこで「残り時間の半分」を制限時間にすることに決めました。これを超えると中盤と同様に評価関数を使います。この手法によって時間切れによって負けることはほぼなくなりました。また、最初はじっくり探索することができ、一度成功すればそれ以降の探索盤面数は基本的に半分以下なので最後まで探索できるというわけです。
しかし、この手法にも問題点があって、最初の探索に失敗すると30秒近くの時間を無駄にすることになります。本番の環境も分からないので無茶な手数を設定してしまうと大きなタイムロスになりかねません。この問題に対処するために考えたのが動的に読み切り手数を決定するという手法です。前の試合ですばやく読み切れたら次の試合は少し多く読もうとします。逆に前の試合で読み切れなければ読み切る手数を少し減らします。こうすることで与えられた計算環境の中で最適な読み切り手数を見つけ持ち時間を有効活用することができました。
終盤のハッシュテーブル
終盤ですでに結果が分かった局面をハッシュテーブルに入れて記憶しておこうというアイディアです。目的は2つあり、1つはすでに見た盤面の再探索を防ぐため、もう1つは終盤近くなって落ちてきた評価関数の精度を補完するためです。後者が分かりにくいので補足します。例えば残り21マスの段階で9手先読みの中盤探索を行うと残り12マスの盤面を評価関数で評価することになります。これほど終盤になってくると評価関数の精度が落ちているように感じていました。そこで、もし以前の対局で残り12マスのこの盤面をすでに読み切っていたらどうでしょう。どの評価関数よりも正確な評価結果が得られます。私はどちらかというとこちらの目的を重視していました。そこで実装してみたのですがなぜか中盤でハッシュテーブルを引き当てることはできませんでした。alpha-beta法とハッシュテーブルの組み合わせは難しいので何かを間違えたかもしれません。また、この目的のためには1試合終わってもハッシュテーブルは残り続ける必要があり、数試合するうちに莫大なエントリー数によってハッシュテーブルのアクセス速度が崩壊しました。結局目立った効果は見られず修正点ばかりが現れてしまったのでハッシュテーブルの使用を断念しました。
必勝読み・完全読みとnega-scout
提出締め切り前日になり、最後にnega-scoutを実装しようかなと考えていたのですが、どの解説を読んでもnega-scoutはnega-alphaの上に成り立っていました。私はalpha-betaを書いていたのでnega-alphaをまず実装しなければなりません。さすがに大変だなと思いました。そもそもnega-scoutが速い理由はNull Window Searchにあります。Windowが小さいほど枝刈りが多くなり動作が速くなるわけです。それなら勝敗だけ読むようにすればWindowが小さくなって速くなると考えられます。こうして必勝読みを実装することになりました。今までのalpha-beta法ではα=-65, β=1としており、これはなるべく良い手を探して勝ちが見つかったら打ち切るという発想です。これで必勝読みのつもりだったのですが、差の小さい負け方を探しているうちに勝ちルートを見逃す可能性がありました。これを書き換えてまず必勝読みを行い、負けが分かった場合のみ完全読みを行うようにしました。こうすると勝っているときには速く読み切れますが、負けているときには必勝読みを行なっている分以前より遅くなってしまいます。とはいえ実力の近いAIであればこちらとほぼ同じ手数を読み切っているはずなので、負け試合を捨ててでも勝てる試合を落とさないほうが重要だと考えました。結局nega-scoutは実装しませんでしたが、その発想によっていくらか強くなった思います。
対戦成績
学科内での対戦成績107勝9敗で順位は1位でした。
やったね。とても嬉しい。
ところが勝敗表を見ると2位と勝ち点が同じなんですね。しかも直接対決で2位に負けていました。
あれ？これは1位なのか？
やや疑問は残りますが、勝ち点が同じなら勝った試合数を見るというルールだったため1位になりました。良かったです。
まとめ
やったことを全て書こうとした結果長くなってしまいましたが、ここまで読んでいただきありがとうございました。今年はオンライン授業のせいか例年よりは締め切りが緩かったようで、じっくり性能向上に取り組むことができました。また、この課題を通してゲームAI作りの楽しさに気づかされました。自分自身ができないことを自作AIがやってくれると嬉しいですね。
評価関数が重要なのはもちろんですが、細かい高速化や時間の使い方が学科内の接戦に勝てた原因の1つではないかと考えています。これからオセロAIを実装する方の参考になれば幸いです。評価関数についてはやはり人間の手で調整するのは限界があるので強化学習が強そうだなという気がします。OCamlで強化学習はかなり大変そうですが期待したいですね。
