オセロAIの大会で優勝しました

オセロAIの大会で優勝したよ！

GGSというサーバー上で開催されたオセロAIトーナメントで優勝しました．
この記事では，このトーナメントについてお話します．

GGSとは

GGS（Generic Game Server）は様々なボードゲームで対戦できるゲームサーバーです．現在では，オセロAI LOGISTELLOの作者であるMichael Buro氏が管理しており，新規アカウントはBuro氏にお願いすることで作成できます．Buro氏のホームページを漁ると，GGSは2000年代には活発に稼働していたことがみてとれますが，現在ではかなり過疎化が進んでおり，人間が対局しているところを見たことがありません．

少し余談ですが，GGS関連の資料を漁るとチラホラ"NEC"の文字をみかけます．実はこのNECは日本電気株式会社のことを指しています．これはBuro氏のかつての所属がNEC北米研究所だったことが理由です．また，Buro氏が開発したAIであるLOGISTELLOで用いられた手法（パターン評価）は現在のAIに大きな影響を与えています．意外なところで日本企業が絡んでいるのですが，当のNECはあまりアピールしていません（悲しい）．

オセロAI「Kalmia」の軌跡とトーナメントに参加したきっかけ

今回のトーナメントには「Kalmia」という名前で参加しました．実はこのAI自体は8年前に高校のイベントで展示したのが始まりです．とはいっても，現在のコードには当時書いたコードの断片は残っておらず，名前だけが受け継がれています．また，開発も8年間継続的に行ったというよりは，飽きては再開してを繰り返しています．Kalmiaの手法は以下のように変遷していきました（分かる人向けに書いているので読み飛ばして構いません）．

2018年: モンテカルロ木探索（UCT） + 一様ランダムな着手によるプレイアウト
2019年: モンテカルロ木探索（UCT） + ヒューリスティックな知識を用いたランダムな着手によるプレイアウト
2021年: モンテカルロ木探索（UCT）+ パターン評価を用いた勝率を予測する評価関数
2023年: 法 + 遺伝的アルゴリズムで構成したパターンを用いた評価関数
2026年: 法 + パターンとFactorization Machineを用いた評価関数

このように割と手法が二転三転していることがわかります．

トーナメントへ参加するきっかけとなったのは今年の冬頃で，Egaroucidという最強格のオセロAIを開発しているにゃにゃんさんからお誘いを受けたのが始まりでした．ただ，そのときは修論に追われていたため，少し間があいて今年の3月末に初めて参加しました．初参加時には色々とトラブルを起こしてしまい，5位という結果に終わりました．以降は4月と5月，そして今回の6月のトーナメントに参加しました．4月は3月と異なりトラブルなしで終えることができ，3位という結果となりました（4位とかなり僅差でした）．5月もなんだかんだで3位を獲ることができました．

Edaxの助け

GGSでは，テキストベースの独自のプロトコルで通信する必要があります．そして，このGGSのプロトコルというのが意外に情報に乏しく，現在鋭意通信プログラムを実装中です．はい，実はまだGGSとの通信を実装していないのです．じゃあ，どうやってトーナメントに参加したんだという話なのですが，今回は最強格のオセロAIであるEdaxのソースコードの大部分を流用いたしました．Edaxは最初からGGSとの通信に対応しているため，ありがたく使わせていただいた形です．ただし，Edaxが用いている手法と私が用いている手法では評価関数（局面の有利不利を判定するモジュール）が異なるため，一部ソースコードを書き換えて，オリジナルの評価関数をEdaxに移植しました．なお，書き換えたソースコードはこちらで公開しています．

最強のプログラム「ymatioun」

ymatiounは，アメリカのYouri Matiounine氏が開発したプログラムです．恥ずかしながら，トーナメントに参加するまでこのプログラムの存在を存じ上げなかったのですが，とてつもなく強いプログラムです．トーナメントでは1位が当たり前で，ほかのプログラムが2位を争うといったような状況が少なくとも私が初参加したときから続いていました．余談ですがYouri Matiounine氏本人もKaggleのCompetitions Grandmasterらしく，世界に400人もいない強い人です．

トーナメントの結果

Kalmiaが見事1位！　遂にymatiounを打倒！と言いたいところですが，実際のところ運が良かったような気がします．というのもymatiounとKalmiaとの直接対決では，Kalmiaの2勝5敗3分と負け越しており，ymatiounは相変わらずの高パフォーマンスを魅せていました．今回はたまたまKalmiaの他プログラムに対する勝率がymatiounよりも僅かに高かったがために1位になれたという結果です．その差はわずか0.5ポイント，すなわち引き分け1回分の差です．

Kalmiaの今後

先に述べたようにKalmiaは評価関数以外はEdaxのソースコードを用いています．そのため，探索部のハイパーパラメータなどはKalmiaの評価関数に合わせてチューニングされていません．Edaxは非常に洗練された探索エンジンを持つプログラムではありますが，やはりEdaxへの依存は早々に無くしたいです．今後のTODOリストは以下の通りです．

• GGSとの通信の自前実装
• 探索の並列化手法であるLazy SMPの検討
• 評価関数のパラメータの削減

ただ，これに加えていろいろとやらなければいけないことが別にあるので，次回のトーナメントに間に合うかは微妙です．

謝辞

今回のトーナメントに向けて下記リンクで公開されている訓練データのうち約13億局面を用いました．

www.egaroucid.nyanyan.dev

技術書典19に申し込みます

技術書典19にサークルで申し込みをします

見出しの通りです。「マジックタンノリターンズ~タンノはマジタンの椅子人間~」というサークル名で 技術書典19に申し込みます。以下がサークルの公式Twitterアカウントです。
Tweets by magic_tanno_rtn twitter.com

メンバー

ハンドルネーム (Twitterアカウント)

Yoka (https://twitter.com/Kalmia24879903)

人参食べたい (https://twitter.com/A_kyoutoyenamta)

最強つちだズ (?)

技術書典とは

技術書典とは、自分で書いた技術書を頒布・販売するイベントです。言うなれば、技術書版コミケです。オンラインとオフラインの両方の形式で開催され、オフライン会場であれば今年は2025/11/16 (日) に池袋サンシャインシティ 展示ホールD（文化会館ビル2F）で開催されます。楽しそうですね。オンラインの場合は、2025/11/15 (土) 〜2025/11/30（日）の期間内であればいつでもやっており、技術書典 ：技術書のオンラインマーケット開催中から電子書籍の形式でいつでも購入できます。（ここまでテンプレ）

techbookfest.org

頒布予定の新刊

タンノ電子計算vol.5-光のかけはしUnity解説&光通信

皆さんが普段から何気なく使っているUnityについての解説をメインにした本になっています。Unityについてはもちろんのこと、光通信についても信号増幅・変調、半導体、光ファイバーの基礎知識まで幅広くカバーしています。また、著者が自作アンテナで21cm線を観測した話や、無線光通信の実験、研究発表で受賞した経験も紹介されています。そんな感じの合同誌です。

8x8リバーシで強化学習!!

物理本で頒布予定です。
リバーシAIを作りながら強化学習を学ぶ書籍です。既刊に「4x4リバーシで強化学習」があり、その続きです。ただし、本としては独立させるつもりで、既刊を読んでいなくても内容を理解できるようにする予定です。既刊では4x4リバーシを題材として、状態と1対1で対応するテーブルを用いて強化学習を実装しました。しかしながら、8x8の本来のサイズのリバーシでは、状態数が膨大なため、テーブルベースの手法は用いることが困難です。そこで、新刊では、テーブルベースではなく、関数近似を用いた手法を中心に紹介していきます。また、関数近似に深層学習モデルを用いた深層強化学習についても紹介する予定です。

頒布予定の既刊

4x4リバーシで強化学習!!

物理本で頒布予定です。
書籍の詳細についてはマーケットをご覧ください。

その他

他にも電子書籍として、技術書典14、15、16、17で頒布した本をオンラインマーケットにて購入可能です。

五目並べ（９路盤）のAIを作る（その3: PV-MCTS）

はじめに

前回，Policy Value Network (PV-Net)を訓練しました．最後にこのPV-Netと探索を組み合わせます．

PV-MCTSとは

まずは原型のモンテカルロ木探索（MCTS）ついて紹介します．MCTSは，選択，展開，ロールアウト，バックアップのサイクルを繰り返す探索アルゴリズムです．選択では，有望度の高い手順を優先的に探索し，末端ノードに到達したら1手先の局面に対応するノードをさらに展開します．ロールアウト*1では，何らかの方策に基づいて，終局まで対局シミュレーションを行い，その勝敗をそのノードの評価値とします．バックアップ*2では，末端ノードで行われた対局シミュレーションの結果を，そのノードに辿り着くまでに経由した全てのノードに伝播させます．

PV-MCTS (policy value MCTS)は，MCTSとDNNを統合した手法であり，選択フェーズにPolicy Networkを用い，ロールアウトはValue Networkで置き換えます．Policy Networkは方策を表す確率分布を出力します．この確率分布を用いて子ノードに重み付けを行い，それに基づいて探索するノードを選択します．Value Networkは，局面の価値（予測勝率）を出力し，対局シミュレーションの代わりに，Value Networkの出力をノードの評価に用います．AlphaZero [Science, 2018] では，これらのPolicy NetworkとValue Networkを1つのDNNに統合しています．

今回は，PV-MCTSを非同期に動作させるAPV-MCTS (asynchronous PV-MCTS) を用います．APV-MCTSでは，末端ノードを直ちに評価するのではなく，評価待ちとしてマークをし，評価待ちキューに局面を追加します．ある程度キューに局面が溜まったら，PV-Netにまとめて評価させます．このようにすることでGPUの並列性能を活かすことができます．

結果

探索による着手の評価

上図は，PV-MCTSによって選択された着手（緑）と，シェルに出力したその評価のスクショです．シェルに出力されている表のpolicy列は，各着手のDNNによる評価であり，DNN単体では，B5（図の黒い四角）を推薦しています．確かにB5に着手することで，同時に2つの三連が作れるので非常に強力です．しかし，この着手は大悪手で白の勝ちです（興味がある方は少し考えてみてください）．PV-MCTSは，5手先で黒が詰むことに気づき，B1（図の緑で囲った箇所）が最善であると判断しています．実際にB1に着手することで黒の勝ちが決まります．

PV-MCTSがPV-Netによって効率よく探索しつつ，PV-Netが出力する方策を改善していることがわかります．

まとめ

深層強化学習で強力な五目並べのAIを作ることができました．ここまでで要したのはたった3日弱の訓練です．しかも，GPUは1枚しか使っていません．また，CPUバウンドの処理を全てPythonで書いた影響で効率よくGPUを使えているわけではありません．ですので，一部をC++などで書き直せば，もっと高速に訓練が可能でしょう．

研究室の研修では，9路盤の五目並べですが，この手法を15路盤にも適用し，結果を記事にしようかと思います．

以下にコードを公開しています．ただ，全く整理できていないので読みにくいと思います・・・
探索部はpv_mcts.py，DQNはdqn_train.py，PV-Netの教師あり学習はsupervised_actor_critic.py，DNNの定義はdual_net.pyにあります．

github.com

*1:プレイアウトともよびます

*2:バックプロパゲーションとも呼びますが，DNNの最適化アルゴリズムの名前と混同するため，最近ではバックアップと呼ぶことが多いです．

五目並べ（９路盤）のAIを作る（その2: Policy Value Networkの訓練）

はじめに

前回，DQNを用いて9路盤五目並べを学習させました．しかしながら，DQNでは，現在の局面のみを利用して次の手を決定するため，深い読みが備わっていません．AlphaZero [Science, 2018] では，policy value Monte Carlo Tree Search (PV-MCTS)という探索手法を用いて深い読みを実現しています．PV-MCTSでは，探索中に着手を評価するPolicy Networkと局面を評価するValue Networkが必要です．AlphaZeroでは，これら2つのDNNを1つのネットワークに統合しています．
さて，前回学習したDNNですが，これは価値 (Value) と方策 (Policy) ではなく，価値とアドバンテージを出力します．そのため，このままではPV-MCTSに組み込むことができません．そこで，DQNで学習した方策を用いてPolicy Value Network（以後, "PV-Net"と表記）を訓練します．

方針

PV-Netの教師あり学習の目的

前回のDQNで得た方策をとします．は価値が最大の行動を選ぶgreedy方策です．

方策は確率分布ですが，greedy方策は決定論的方策ですので，上式では関数のような表記にしました．

PV-Netを，パラメータをとします．PV-Netは，各成分が各行動の確率に対応するベクトルと価値を表すスカラを出力します．

PV-Netの教師あり学習の目的は，を方策に近づけること，を両プレイヤが状態から方策にしたがって対局した場合の期待勝率に近づけることです（次式参照）．

これを実現するために，方策を用いて自己対局を行い，状態と行動，最終的な勝敗のペアをサンプリングします．ここで，は勝ちのときに1，負けのときに0，引き分けのときに0.5を取る値です．これらのサンプルを教師データとしてPV-Netを訓練します．

を用いた自己対局

方策は先述の通り，greedy方策ですので決定論的方策です．そのため，同じ初期局面から対局を開始すれば，必ず同じ着手となり，サンプルに多様性が生まれません．そこで，序盤数手のみは非決定論的方策を用います．具体的には，序盤は次式の確率に従って着手を決定します．

は，状態における合法手の集合であり，分母では全ての合法手についての和をとっています．は温度パラメータであり，ばらつきの度合いを調整するハイパーパラメータです．確率は，行動価値が高い行動であればあるほど大きくなり，で行動価値が最大の行動のみ，確率が1となります．
実験時にはとし，序盤5手のみに従って着手，以降はに従って着手します．

自己対局はGPUの並列性能を活用するために，4096対局並列に実行します．ただし，前回のDQNと同様，対局自体はシングルスレッドで実行し，バッチ処理の部分だけGPUにより並列化します．また，4096対局のうち，全ての局面を保存するのではなく，1対局から1局面のみをサンプリングします．これは過学習を防ぐための対策です．したがって，4096対局を1イテレーションとすると，1イテレーションごとに4096個のが得られます．実験では，5000イテレーション実行し，2048万サンプルを得ました．また，教師あり学習におけるテストデータ用に追加で20イテレーション実行し，81920サンプルを用意しました．を用いた自己対局は，RTX 3080Ti 1枚で15時間弱を要しました．

PV-Netのアーキテクチャ

DQNで用いたDueling Networkとアーキテクチャは同じです．出力する値のみが異なります（下図）．

PV-Netのアーキテクチャ

方策ヘッドでは，出力値をsoftmax関数に通し，価値ヘッドではシグモイド関数に通します．DQNでは，価値の値域を]としていましたが，PV-Netでは，価値を勝率に対応させるため，値域は]とします．わざわざ勝率に対応させる理由は，勝率の方がPV-MCTSに統合するときに都合が良いからです．

損失関数

PV-Netの教師あり学習時の損失関数には次式を用います．

※ 2025/8/24 変更: 損失関数にエントロピー正則化項を追加．

は，によって打たれた着手に対応する要素のみが1となるone-hotベクトルです．はクロスエントロピー損失であり，との分布が近いほど小さな値をとります．についても同様に，PV-Netが予測する勝率が実際の勝敗に近いほど小さな値をとります．は，のときに負の値をとり，その際にとの分布を遠ざける作用が働きます．この式の意味は，互角以上の状態から負けへと至ってしまった場合に打たれた着手は悪手とみなし，できる限りそれを真似ないようにするという意味を持ちます．この式は，Actor-Criticという強化学習手法で用いられているベースラインという考え方に基づくものです．Actor-Criticでは，0.5の部分がなくです．しかし，で試したところ，負けた対局で打たれた全ての着手を悪手とみなしてしまい，全く学習できなかったので0.5を加算しました．0.5を加算するという発想はdlshogiがかつて用いていた損失関数を真似ました．注意が必要なのは，勾配計算をする際に，の部分のは定数とみなさなければいけません．そうしないとを最小化するようにの値が調整されていまします*1．
はエントロピー正則化項です．は，が決定論的方策に近づくほど小さな値をとります．PV-Netが出力する方策は，PV-MCTSにおける探索候補の絞り込みに用います．しかしながら，方策が決定論的になってしまうと，特定の着手のみに過剰に探索が集中し，読み抜けが発生するため，エントロピー正則化を行います．実験では，としました．
はL2正則化項であり，実験ではとしました．

結果

最適化アルゴリズムには，Adam ()を用い，学習率は0.001としました．およそ7時間で収束し，テスト方策損失は0.6191，テスト価値損失は0.6318となりました．
価値損失が大きいですが，おそらくこれは訓練データに引き分けが多いことに起因しています．なんと，2048万局面のうち，約63.3%が引き分けです．ちなみに勝ちは18.72%，負けは17.98%と同程度の割合です．テストデータについてもほぼ同じ割合です．
禁じ手無しの五目並べは先手が非常に有利で，コンピュータが誕生する以前から人の手によって，先手の必勝手順がいくつも見つかっています．しかしそれは15路盤の話であって，9路盤ではその狭さから，ある程度石を置くと，互いに5連を作りにくくなります．それゆえ，後手がうまく妨害すれば，引き分けにすることが可能だと思われます．

定理

9路盤における五目並べでは，双方が最善手を打った場合，引き分けとなる

実は真に驚くべき証明が(ry

誰か弱解決したら，Yokaの9路五目の定理と名付けてください．

次回

次回は，学習したPV-Netを用いて探索を行います．

*1:PyTorchなら，TensorFlowならを使えば，勾配計算の対象から外せます．

五目並べ（９路盤）のAIを作る（その1: DQNによる訓練）

はじめに

所属する研究室の新人研修で，学部生たちが五目並べのAIを作っています．ちょうど良い機会なので自分も作ってみました．普段はあまり深層強化学習を用いておらず，どちらかといえば古典的な機械学習を用いているのですが，学部生のほとんどはPyTorchでAlphaZeroなどの深層強化学習手法を用いているので，自分もそれに合わせることにしました．

一応，自分が試したことについて書き連ねていきますが，ある程度，強化学習の基本的なことを知っている前提で書きます．

使用言語及びフレームワーク

• 言語: Python (CPython 3.13.5)
• フレームワーク: PyTorch

深層学習はフレームワークを用いますが，強化学習に関してはOpenAI Gymなどを用いずに自前で実装します．そもそもOpenAI Gym自体，公式の開発は終了しています．LLMにうつつを抜かしているのでしょうか？？

言語は，できることならC++やC#などのCPUバウンドな処理を高速に書ける言語を使用したいのですが，Pythonのほうが研究室内での使用人口が多く，皆がコードを読めるはずなので，全てPythonで実装します．

五目並べ

五目並べとは，碁盤上でプレイするゲームで，自分の石を相手より先に縦横斜めのいずれかのラインで5つ以上連続で並べたら勝利です．直感的にも明らかですが，このゲームは先手有利です．そのため，黒側に禁じ手を設けるのが一般的です*1．しかし，禁じ手有りでは実装が煩雑となるため，禁じ手は無しとし，その代わり後手の白石を先にいくつか盤上に置いて対局を開始するルールとします．また，本来の五目並べは15路盤（15x15の盤面）を用いますが，研修では9路盤を用います．

方針

五目並べは2人零和有限確定完全情報ゲームです．2人零和有限確定完全情報ゲームは以下の性質を持ちます．

• プレイヤーが2人
• プレイヤー間の利害が対立している（他方が有利になれば，もう片方が同じだけ不利になる）
• 有限の手数で終局する
• 確率的要素がない（サイコロやルーレットを用いない）
• 両プレイヤーに互いの情報が公開されている（自分だけに見える手札などはない）

2人零和有限確定完全情報ゲームには，五目並べ以外にも，チェス，囲碁，将棋，リバーシなどが該当します．このようなゲームは，AlphaZero [Science, 2018] という汎用的な手法を用いることで超人的な棋力に到達させることができます．しかし，この手法はかなり演算コストが嵩み，訓練時間も膨大です．そこでもう少し軽量な強化学習手法を用いることにします．

具体的には，Deep Q-Network (DQN) を用いて，そこそこ強い方策を学習してみます．

DQN

DQNは，Q学習で用いるQ関数をDeep Neural Network (DNN)で近似する手法です．ただし，単にDNNに置き換えるだけでは学習が安定しないため，DQNでは，Target Network，リプレイバッファという2つの仕組みを取り入れています．

更新式

Q学習では，次の更新式でQ関数の値を更新します．

は行動価値関数であり，状態で行動を行った際の価値を出力します．五目並べなら，が手目における局面，が手目の着手にあたります．DQNでは，の値をDNNが出力します．は手目の着手後に手に入った報酬，は割引率です．五目並べにおける報酬とは勝敗のことですが，勝敗は終局するまで決まらないため，終局局面以外では報酬が0となります．
ここで，勝ち，負け，引き分けの報酬をそれぞれとします．すなわち，です．このとき，価値は報酬の期待値ですのでは以上以下の値をとります．さらにを状態における手番プレイヤーから見た価値と定めれば，における相手から見た価値はとなります*2．

以上を踏まえると，五目並べにおけるQ学習の更新式は以下のとおりです（非終端遷移，かつ）．

なお，状態で着手を行って終局した場合の更新式は次のとおりです．

報酬にマイナスを乗じている理由は，1ステップ先の報酬は，相手から見た報酬となるためです．

Q Network

DQNでは，をパラメータのDNNを用いて，と近似します．しかし，このままだと各行動それぞれについてDNNの推論が必要になります．そこで，オリジナルのDQNでは，状態を入力として，各成分が各行動の価値を表すベクトルをDNNに出力させます．

Network Architecture

DNNのアーキテクチャにはDueling Networkを用います．Dueling Networkは単に行動価値を出力するのではなく，状態価値とアドバンテージを出力します．アドバンテージとは，行動 をとることで現在の状態価値からどれだけ価値が変化するかを表す値であり，が成り立ちます．ただし，このままだと識別性の問題で学習が安定しないため，実装上は次のように統合します．

ここではアドバンテージの標本平均です．そのため，Dueling Networkが出力するは厳密な意味での状態価値の推定値とは一致しません．あくまでものみが推定値です．また，行動価値を計算する際に活性化関数を適用する場合は，統合したに対して適用します．

ネットワークの構成は下図の通りです．

Q Networkのアーキテクチャ

なお，畳み込み層の直後にはバッチ正規化層とReLUを挟みます．
また，を計算した後，その結果に双曲正接関数 (tanh) を適用し，が以上以下の値を取るようにします．
細かいアーキテクチャは，dualnet.pyを参照してください．

Target Network

Q関数がパラメータで表現される場合，Q学習の更新式は次式の通りです（非終端遷移，かつ）．

PyTorchを用いる場合，自動微分によってここらへんの計算は勝手にやってくれるので導出は割愛します．
DQNでは，上式のとがDNNによって与えられるのですが，このまま適用すると学習がかなり不安定になります．この更新式はの値をに近づけるようにパラメータを更新することを意味しており，1ステップ先の自分自身の出力を教師データにしていることになります．このように自分自身の出力をターゲットに用いる手法をブートストラップ法と呼ぶのですが，DNNのような表現力の高いモデルを用いると簡単に過学習を起こします．そこで，DQNでは，訓練対象のDNN だけでなく，全く同じアーキテクチャでパラメータのみが異なるTarget Network を用います．そして，次式に従いパラメータを更新します．

一見すると違いがないように見えますが，をとっている対象がTarget Networkで置き換わっています．このように，ターゲットを出力するDNNと訓練対象のDNNを分けることで学習を安定させます．なお，Target Networkのパラメータは，訓練対象のDNNが過去に用いていたパラメータであり，一定の間隔で最新のDNNのパラメータと同期します．

Double DQN

さらに学習を安定化させるために，Double DQN (DDQN)も用いました．DDQNとDQNの差分は更新式のみであり，DDQNでは，次の更新式を用います（非終端遷移，かつ）．

見づらくなりましたが，DQNとほとんど差分はありません．価値が最大の行動は現在訓練中のDNNで選び，その行動の価値はTarget Networkが計算します．このようにすることで最大化バイアスを抑えることができます．もともとDouble Q学習という手法があり，それをDQNにも適用した形です．

Replay Buffer

DQNでは，ある程度過去に訪れた状態と行動をReplay Bufferというバッファに記録します．訓練時は，このバッファからバッチサイズの分だけ状態と行動をサンプリングしてDNNのパラメータを更新します．Replay Bufferはいわゆるdeque（リングバッファ）というデータ構造をとっており，直近個の経験が記録されます．五目並べにおいては，1対局（エピソード）単位でReplay Bufferに格納し，直近3万エピソード分のデータを記録するようにしました．また，サンプリング時には「1対局1サンプル」という制約も加えました．すなわち，1回のDNNのパラメータ更新において，同じ対局から複数のサンプルをとることはしません．過学習を防ぐための対策です．

挙動方策

Q学習では，何らかの方策で状態と行動のサンプリングを行います．この点はDQNでも全く同じです．Q学習およびこれを発展させたDQNは，挙動方策（サンプリングに用いる方策）とターゲット方策（実際に改善する方策）が異なるオフポリシー手法です．そのため，極端な話，全ての行動の中から等確率でサンプリングする方策でも構いません．しかし，それでは効率が悪いです．そこでDQNでは，-greedy方策を挙動方策に用います*3．-greedy方策では，確率で全ての行動の中から等確率で1つをサンプリングし，確率で最も価値が大きい行動を選択します．訓練序盤は，なるべく多くの幅広いサンプルを取得し，訓練が進むにつれて行動価値が大きい行動を選択する方が収束が早いです．そこで，五目並べでは，以下の式に従ってを動的に変化させます．

はDNNのパラメータの更新回数であり，はの減衰速度を決めるハイパーパラメータです．
今回は，としました．

訓練の流れ

訓練においては，GPUの並列演算性能を有効活用するため，複数のエピソードを同時に回します．具体的には256エピソードを同時に実行します．各エピソードは，1ステップごとに同期を取り，サイズ256のミニバッチを作ります．そして，それをDNNに与え，行動価値をGPUで計算します．Pythonにおいては，GILの影響でマルチコアを生かしたプログラムを書くのが難しいため，この256エピソードはシングルスレッドで実行します．しかし，最も重い処理であるDNNの推論は256状態に対してGPUによって並列に行われるため，トータルでは大幅な高速化となります．対局を終えたら，その経験をReplay Bufferに格納します．

オリジナルのDQNでは，1ステップごとにDNNのパラメータ更新を行いますが，五目並べではエピソードが終了するまで報酬が確定しないため，前述の256対局が終わったタイミングでReplay Bufferから256サンプルをランダムにサンプリングし，パラメータを1回更新します．箇条書きで学習の1イテレーションを書くと以下のとおりです．

1. 256対局を並列に実行
2. 1.の結果をReplay Bufferに追加
3. Replay Bufferから256局面分のデータをサンプリング
4. 3.で構成したミニバッチでDNNのパラメータを1回更新し1へ

その他の設定

最適化アルゴリズム: Adam ()
学習率: 0.001
損失関数: Huber loss
Target Networkの更新頻度: 5イテレーションごと
warmup: 25600エピソード分のデータがReplay Bufferに溜まるまでDNNのパラメータを更新しない

結果

9万6千イテレーション程度で訓練を打ち切りました．訓練時間はおよそ20時間です．
ここからは実際に着手を見ていきます．

三連に対する反応

三連とは，同じ色が3つ連続に並んでおり，かつその両端が空いている形です．
相手にこの形が出現したときは，どちらか一方に石を置いて妨害しなければ負けます．
下図は黒に三連が出現した図です．白は真っ先に妨害しています．シェルに表示されているのはDNNが出力する行動価値を期待勝率に変換したものです．この場合，G3かC7に置かなければ白の負けが確定するので，この2つの行動価値が同程度に高く，それ以外は低い値を取っています．

三連に対する妨害

急所の見極め

多少読みが必要な急所も見極めることができています．
例えば，下図はG6，G4が黒の急所であり，実際にDNNもこれら2つの着手に非常に高い評価を下しています．
白がG6に打った場合，斜めの三連ができているので，黒はD3かH7で止めなければいけません．黒がどちらか一方に置いた場合，白はG4に置くことでチェックメイトです．この時点で白に斜めの三連と縦のリーチができ，黒には為す術もありません．G6は1手ほど手順が長いですが，どちらにせよ黒が詰みます．DNNは現在の局面を入力しているだけですので，この急所を見極められることには驚きました．

急所に対する攻撃

次回

DQNでもそれなりに強いプレイヤーができました．しかしながら，DQNは読んでいるわけではないので，とんでもないポカもやらかします．それ故に探索が必須です．AlphaZeroではPV-MCTSという探索手法を用いています．この手法では，方策と価値を出力するDNNが必要です．次回は，今回学習したDueling Networkを用いて，方策と価値の両方を学習します．

ソースコード

以下のリポジトリで公開しています．dqn_train.pyとdualnet.pyが今回の内容です．
他にもGo Text Protocolを用いた通信プログラムなども書いているので，GoGuiというアプリ上でも動きます．面倒なのでまだ使い方を書いていませんがいつかやります（いつ？）．

https://github.com/Yoka0014/Gomoku

*1:禁じ手有りの五目並べを「連珠」と呼び，全国大会などではこのルールで行うのが通常です．

*2:五目並べの零和性（利害の対立）を利用しています．

*3:必ずしも-greedy方策である必要はないです．別に行動価値をソフトマックス関数に通しても良いですし，全く別の挙動方策を用いても良いです．

競プロ用に二分探索のライブラリを作った話

AtCoder始めました

実は今年の4月末からAtCoderを始めました。今年の春に競プロを通じてアルゴリズムを学ぶ講義のTAを担当し、TAが全く競プロができないのはまずいのではないかと危機感を覚えたことがきっかけです。最近は徐々にD以降にも手をつけられるようになったのでそろそろライブラリを整備しようと思った次第です。

使用言語

AtCoderでは基本的にABCに参加しており、A~CをPython、D以降やCの難しめな問題をC#で解いています。D以降とは言っていますが、本番ではDしか解けたことないですorz
C#はPythonと比べたら遥かに高速な言語であり機能も豊富です。しかしながら、競プロ用に用いるには標準ライブラリが少しばかり貧弱なので少しずつライブラリを整備しています。

二分探索

C#には、配列やリスト、 に対して二分探索を行うメソッドが既に用意されています。例えば、Array.BinarySearchメソッドは、ソート済みの配列から指定した値を二分探索し、その値がある位置の添字を返します。それだけでなく、仮に指定した値が見つからなかった場合でも、その値を超える位置の添字をビット反転したものを返してくれます。なぜわざわざビット反転するのかというと、戻り値の正負で指定した値が見つかったかどうかを判断できるようにするためです。すなわち、Array.BinarySearchメソッドは、下限値を探索するのにも用いることができます。

しかしながら、二分探索は必ずしも配列やリストなどに用いるわけではありません。例えば、ABC365のC問題について考えてみます。

atcoder.jp

この問題は二分探索で解く典型的な問題です。この問題、自分は本番時に二分探索を使えるということが分からず、かなり時間をかけてその場しのぎの解法で解いてしまったという苦い思い出があります。
この問題は上限値に関する二分探索で解くことができます。二分探索を適用するときは、費用を円以下にできるの領域と、そうではない領域の境界の位置を求める問題と解釈すればよいです。しかし、この問題の場合は、二分探索の対象が配列ではないので、Array.BinarySeachメソッドなどは使えません。ですので、自分で二分探索を実装する必要があります。以下がC#での実装例です。

var NM = Console.ReadLine().Split().Select(long.Parse).ToArray();
(var N, var M) = (NM[0], NM[1]);
var A = Console.ReadLine().Split().Select(long.Parse).ToArray();

if(A.Sum() <= M)
{
    Console.WriteLine("infinite");
    return;
}

bool Check(long x)
{
    var sum = 0L;
    foreach(var a in A)
        sum += Math.Min(x, a);

    return sum <= M;
}

int ok = 0, ng = (int)1e+9;
while(Math.Abs(ok - ng) > 1)
{
    var mid = (ok + ng) >> 1;
    if(Check(mid))
        ok = mid;
    else
        ng = mid;
}

Console.WriteLine(ok);

個人的には、二分探索の部分を何とかして汎用的なライブラリにしたいです。

関数に対する二分探索

実数値でも二分探索はできますが、ここでは整数値でのみ考えます。二分探索は、単調増加列についてを満たすを求めるアルゴリズムです。重要なのは単調増加列であることなので、は必ずしも配列やリストである必要はありません。例えば、以下のF関数も単調増加列です。試しに0から5をFに与えれば、という単調増加列になります。このように関数も単調増加列として扱えれば、長さが無限大の数列に対しても二分探索ができます。

int F(int n) => n * 2;

関数に対する二分探索の実装

以上の話を踏まえて、関数に対する二分探索を実装します。
以下のBinarySearch.Searchメソッドは、long型の整数を引数に取りTKey型の値を返す関数funcに対して、区間]でとなるようなを探索します。ある程度呼び出し側で挙動をカスタマイズできるように、TKey型の値の比較関数comparisonも引数に与えられるようにしています。省略した場合はデフォルトの比較関数が適用されます。comparison(x, y)は、x == yのとき0、x < yのとき負の数、x > y のときに正の数を返します。

Array.BinarySearchと挙動を揃えるために、となるが見つかった場合は、そのままの値を返し、そうでないときは、を満たすのうち最小のものをビット反転したものを返します。

↑考えてみれば、ビット反転したものを返す仕様にするとマズいことに気づきました。関数に対する二分探索の場合、のときがあるので。
bool型out引数のfoundを与えるようにして、そのfoundの真偽でkeyが見つかった否かを判断できるようにしました。

    public static class BinarySearch
    {
        public static long Search<TKey>(Func<long, TKey> func, TKey key, long left, long right) where TKey : IComparable<TKey>
            => Search(func, key, left, right, (x, y) => x.CompareTo(y));

        public static long Search<TKey>(Func<long, TKey> func, TKey key, long left, long right, out bool found) where TKey : IComparable<TKey>
            => Search(func, key, left, right, (x, y) => x.CompareTo(y), out found);

        public static long Search<TKey>(Func<long, TKey> func, TKey key, long left, long right, Comparison<TKey> comparison)
            => Search(func, key, left, right, comparison, out _); 

        public static long Search<TKey>(Func<long, TKey> func, TKey key, long left, long right, Comparison<TKey> comparison, out bool found) 
        {
            while(left <= right)
            {
                var mid = left + ((right - left) >> 1);
                var y = func(mid);
                var comp = comparison(key, y);

                if(comp == 0)
                {
                    found = true;
                    return mid;
                }

                if(comp > 0)
                    left = mid + 1;
                else
                    right = mid - 1;
            }

            found = false;
            return left;
        }
    }

実装した二分探索の利用

それでは先ほどのABC365のC問題で実装した二分探索を用いてみます。以下がそのコードです。
実際の提出結果はこちら。

var NM = Console.ReadLine().Split().Select(long.Parse).ToArray();
(var N, var M) = (NM[0], NM[1]);
var A = Console.ReadLine().Split().Select(long.Parse).ToArray();

if(A.Sum() <= M)
{
    Console.WriteLine("infinite");
    return;
}

int Check(long x)
{
    var sum = 0L;
    foreach(var a in A)
        sum += Math.Min(x, a);

    return sum <= M ? -1 : 1;
}

Console.WriteLine(BinarySearch.Search(Check, 0, 0, (long)1e+9) - 1);

先ほどのコードと異なり、Check関数の戻り値が少しだけ変わっています。このCheck関数は、条件を満たすときは-1を、そうでないときは1を返します。Check関数は、という単調増加列とみなすことができ、求めるは-1と1の境界にある-1の位置です。ですので、このCheckに対して0を探索する二分探索を行えば、初めてCheckの値が1になるときのが得られます。したがって、このから1を引いた値が答えです。なお、二分探索の区間]は問題の制約から決めています。

配列に対する二分探索の場合

このライブラリの便利である（と思っている）点は、配列やリストに対する二分探索も以下のように行えるという点です。まあ、普通にArray.BinarySearchを使えと言われればそれまでですが・・・

var A = Console.ReadLine().Split().Select(long.Parse).ToArray();    
var key = int.Parse(Console.ReadLine());
Array.Sort(A);
var idx = BinarySearch.Search(i => A[i], key, 0, A.Length, out var found);

if(found)
    Console.WriteLine($"found: A[{idx}] = {A[idx]}");
else
    Console.WriteLine($"lower bound: A[{idx}] = {A[idx]}");

まとめ

今回は競プロ用により汎用的な二分探索ライブラリを作りました。しかしながら、まだまだ未熟者（茶色コーダー）であるゆえ、このライブラリでは抽象化が不十分な点があると思います。とりあえずこのままの実装にしておいて、対応できない問題に遭遇したら改良していこうかなと思います。

C#で自作のディープラーニングフレームワークを作る その5(ソフトマックス層とクロスエントロピー誤差の融合)

クロスエントロピー誤差の不安定さ

前回、クロスエントロピー誤差を実装しましたが、計算にlogが含まれるため非常に不安定でした。しかし、そもそもクロスエントロピー誤差は多クラス分類問題で用いる損失関数であり、その場合はモデルの出力にソフトマックス関数を適用することが一般的です。だったら、ソフトマックス関数とクロスエントロピー誤差の計算をまとめてしまっても良いのではないでしょか。実は、これら2つの計算を1つにまとめると、クロスエントロピー誤差の順伝播が非常に安定し、さらに逆伝播の計算コストも下がります。このようにソフトマックス関数とクロスエントロピー誤差の計算をまとめて行う関数をSoftmaxWithCrossEntropyと便宜上名付けます。

SoftmaxWithCrossEntropy

バッチ単位のモデルの出力をとします。ここで注意が必要なのははソフトマックス関数を適用する前の値です。
SoftmaxWithCrossEntropyをとすると、

と書けます。ここでに着目します。これはソフトマックス関数の出力に対して対数を計算した値です。便宜上、この計算をLogSoftmaxと名付けます。

LogSoftmaxの計算

LogSoftmaxを実際に計算してみましょう。

このLogSoftmaxにはとても嬉しい性質があります。１つにその安定性です。浮動小数点数計算では誤差が生じることは有名ですが、特に大きな値の演算では、小さな値の情報が落ちたり、オーバーフローを引き起こしたりします。ソフトマックス関数では、指数関数の計算を行うので特にそれが問題になりやすいです。しかし、LogSoftmaxでは、ソフトマックス関数にあった大きな値による割り算が消え、代わりに対数の引き算を行なっています。そのため、ソフトマックス関数単体の計算よりも安定します。さらに、このLogSoftmaxをクロスエントロピー誤差と組み合わせれば以下のように書け、を回避できます*1。

上式がSoftmaxWithCrossEntropyの完全な式です。

順伝播の実装

式通りに実装するだけです。

using MathNet.Numerics.LinearAlgebra.Single;

namespace NeuralNET.Layers.Loss
{
    /// <summary>
    /// ソフトマックス関数 + クロスエントロピー誤差
    /// </summary>
    public class SoftmaxWithCrossEntropyLayer : ILossLayer
    {
        readonly bool SAVE_INPUT_REF;
        DenseMatrix? t;
        DenseMatrix? logSoftmax;
        DenseMatrix? loss;

        public SoftmaxWithCrossEntropyLayer() : this(false) { }

        public SoftmaxWithCrossEntropyLayer(bool saveInputRef) => this.SAVE_INPUT_REF = saveInputRef;

        public float Forward(DenseMatrix y, DenseMatrix t)
        {
            SaveInput(t);

            if(this.loss is null || this.loss.RowCount != y.RowCount || this.loss.ColumnCount != y.ColumnCount)
                this.loss = DenseMatrix.Create(y.RowCount, y.ColumnCount, 0.0f);

            if(this.logSoftmax is null || this.logSoftmax.RowCount != y.RowCount || this.logSoftmax.ColumnCount != y.ColumnCount)
                this.logSoftmax = DenseMatrix.Create(y.RowCount, y.ColumnCount, 0.0f);

            y.ColumnLogSoftmax(this.logSoftmax);
            this.logSoftmax.PointwiseMultiply(t, this.loss);
            
            return -1.0f / y.ColumnCount * this.loss.AsColumnMajorArray().Sum(); 
        }
}

逆伝播の実装

をで偏微分します。

ここで、をで偏微分すると、

となり、ソフトマックス関数の出力に一致します。これを用いると、

このようにソフトマックス関数とクロスエントロピー誤差をまとめて計算すると、勾配をMSEの勾配と同様にモデルの予測値と正解データとの差分で計算できます。

あとは式の通り実装します。
Backwardメソッドのみを載せています。逆伝播の際にはソフトマックス関数の計算が必要になりますが、順伝播の際に計算したLogSoftmaxの値を記録しておき、それを指数関数に放り込めば簡単に計算できます。

        public DenseMatrix Backward(DenseMatrix res)
        {
            if(this.logSoftmax is null || this.t is null)
                throw Exceptions.CreateBackwardBeforeForwardException();

            this.logSoftmax.PointwiseExp(res);
            res.Subtract(this.t, res);
            res.Multiply(1.0f / this.logSoftmax.ColumnCount, res);
            return res;
        }

SigmoidWithBinaryCrossEntropy

標準シグモイド関数はソフトマックス関数の特殊形であることを踏まえると、2値クロスエントロピーとまとめて計算すると、逆伝播の計算はモデルの予測値と正解データとの差分を取るだけで済みます。SoftmaxWithCrossEntropyとほぼ同じなので実装は省略します。

次回

ここまで活性化関数と損失関数を実装したので、次回はアフィン変換を行う層の実装に移ります。

今回のコミットは以下です。one-hotベクトルに対応したSoftmaxWithCategoricalCrossEntropyも実装しています。

github.com

*1:が0になれば、になりますが、指数関数の総和が0に近い値になることは起きにくいです。