no-image

AlphaZeroを読み解く #1

はじめに

えむいーさんは趣味で将棋をやっているのだが、自分のプログラミング力で将棋をするAIをつくれないかと考えていました。

昔はいろいろとめんどくさいことを考えていたのですが、最近はディープラーニングで勝手にAIを作れるそうです。

最強のAIといえばGoogle DeepMindが開発したAlphaZeroで異論はないでしょう。

DeepMindが作ったAlphaZeroは人間の棋譜を全くベースにしないまま学習し、世界最強プログラムであるstockfishよりもチェスが強く、Elmoよりも将棋が強く、alphaGo Zeroより囲碁が強いという。

それがたった12時間程度でできたというのだから驚きである。

というか、この記事の内容が今更すぎますね。

同じものを個人が作ることは無理

ちなみにたった3日といっても、Googleの学習専用マシーンであるTPUのリソースをアホみたいに使って学習しているので普通のPCでは同様の学習は無理です。

TPUは1台で180TFLOPSでGTX1080Tiが11.3FLOPSで18倍の計算能力がある上に、それを5000台並列で繋げているという…

ということは1080Tiで同じ学習をしようとすると、12*18*5000/24=45000 日だけかかる

計算になる。これはおよそ120年である。

AlphaZeroの論文を読み解く

こんなのは既に別の方がされていると思うのだが、自己学習のために自分で再度読み直すことにする。

検索手法(MCTS and Alpha-Beta Search)

ここ40年間の最強のコンピュータチェスプログラムであるStockfishは「Alpha-Beta法」を使用している。Alpha-Beta法とはMinimax法の1つであり、おおざっぱにいえば「評価値のツリーを考える際に考えても考えなくても良い部分を省略して計算を効率的に行う方法」だと考えてもらって良い。

コンピュータは以下のような仕組みで盤面を評価している。

  1. あるN手目の局面から次の一手(N+1手目)考える。
  2. 合法手に対する(N+1手目の)局面を評価。
  3. 相手も最善手を返すはずなので、次の一手(N+2手目)を考える(1手読み)。

これに対してAlphaZeroは全く異なるアプローチであるMCTSを用いて局面を評価している。

MCTSというのはMonte Carlo tree searchのことで、ある種の決定問題に対するヒューリスティックな検索アルゴリズムである。ヒューリスティックというのは、正解にある程度近い答えを返すおおざっぱだけれど高速な方法のことである。

このMCTSは今までに見向きもされなかった。その理由はMCTSはAlpha-Beta法に比べてめっちゃ弱かったから(原文:traditional MCTS were much weaker than alpha-beta search)らしい。

では何故今更MCTSが復権してきたのだろうか?

それはAlphaZeroがMCTSにディープラーニングを組み合わせてきたからに他ならない。更に、AlphaZeroは他のチェスプログラムと異なるアプローチで盤面を評価している。

相違点: AlphaZeroは他のチェスプログラムが局面を線形近似をしているのに対して、ディープラーニングニューラルネットワークに基づく非線形近似を用いて評価している

非線形にすることで局面をより強力に表現することができるのだが、その代償として誤った似誤差を引き起こしてしまう可能性がある。

この近似誤差というのがやっかいで、少しでも評価を誤ってしまうと「少し誤った評価から次の局面の評価を少し誤り~」というのを繰り返してどんどん評価値が真の値からズレていってしまう。

MCTSではそれらの近似誤差を平均化することで解決を試みている。近似誤差というものは、

  • 真の値よりも良い方向に誤差(評価値の誤差が+)
  • 真の値よりも悪い方向に誤差(評価値の誤差が-)

という二種類が考えられる。MCTSはランダム性があるのでこれらの誤差が同じくらい発生するはずで、「同じくらい発生するのであれば、平均化すれば最終的に誤差は相殺されるはずだ」という考え行っている。つまり、深く手を読んでいっても評価が狂いにくいということである。

MCTSが近似誤差を平均化するのに対して、alpha-beta法では最大誤差を評価ツリーの根まで伝播している。

これは枝刈りをするalpha-beta法のアルゴリズムの仕組みとして避けようがない問題で、評価を誤ってしまった場合に本来は有効な手であるはずなのにそもそも全く検討されないという「切り捨て」が行われてしまう場合があるのである。

MCTSを使うことでAlphaZeroはニューラルネットワークによる強力な盤面表現と、ドメイン独立検索を効率的に組み合わせることができるのである。

ドメイン知識

ドメイン知識とは「盤面などから得られる情報・ルール」などのプレイヤーが知り得る情報のことである。ドメイン情報には以下の5つがある。

  1. 盤面情報(駒の情報など)
  2. ゲームのルール(駒が取られる条件・禁じ手・勝利条件・引き分けなど)
  3. 駒の動かし方(キャスリング・成り・持ち駒など)
  4. 合法手の数
  5. 最大手数(将棋とチェスはある手数よりも長く続いた場合は引き分けとする)
    チェスは駒が少なくなると先手・後手ともにチェック・メイトすることが不可能になるためひきわけとする。同様に将棋は相入玉すると双玉が詰まなくなるので持将棋として引き分けにする。

AlphaZeroはこれ以外に定跡などの他の知識を全く使用しないという。

盤面表現

論文によるとAlphaZeroの将棋におけるポジショニングは362通りだという。

  • 先手の駒 14パターン
  • 後手の駒 14パターン
  • 反復回数(千日手) 3パターン
  • 先手の持ち駒 7パターン
  • 後手の持駒 7パターン
  • 手番 1パターン
  • 手数 1パターン
解説
  • 駒は(歩・香車・桂馬・銀・金・角・飛車・玉)の8種類である金と玉以外の6種類は成れるので全部で14通りとなる。
  • 4回同じ局面を繰り返すと千日手になるので、3回までカウントすれば良いので3通り。
  • 持駒は(歩・香車・桂馬・銀・金・角・飛車)の7通り。
  • 手番は先手か後手の1つの情報(2通り)で良い。
  • 現在の手数を保存するので1つの情報(最大手数を256手とするなら256通り)で良い。

ここから8手分の指し手を入力として与えていきます。すると(14+14+3+7+7)*8+2=362で、論文の数値と一致します。

ニューラルネットワークに与える入力

一番大事なところが恐らくこれ。

というのも、どういう情報から学習するかっていうのはめっちゃ大事だからです(語彙力皆無)

ここを間違えたらクソザコナメクジなAIができてしまいます。

ちなみに、入力はN*N*(MT+L)の(MT+L)層構造の画像として与えられます。「ディープラーニングは全部画像化すればええんや」っていう暴論がありましたがあれは真実だと思います(笑)。実際、ディープラーニングを用いた株価予想とかもチャートを全て画像として入力していますし!

ところで、N*N*(MT+L)の構造というのがイマイチピンときません。原文には「The input to the neural network is an N × N × (MT + L) image stack that represents state using a concatenation of T sets of M planes of size N × N.」とあるのですが、これはどう訳すのが適当なんでしょうか?

普通に読めば「サイズN*Nの平面MのT組連結」ということになるので、N*N(将棋で言えば9*9の81マス)の平面が参考にする履歴数T(T=8)くらい積み重なったものという感じなのですが。

そうなると入力はN*N*Tになるんじゃないかと思うんですけれど、こういう表現をするのが正しいんでしょうか?(詳しい人教えてください)

各平面Mはt-T+1, t-T+2, … , t手目の局面の駒情報を表現していて、局面が1手目未満の場合は0と設定します。1層目にあれば自分の駒、2層目にあれば相手の駒というように区別しているようです。これも合理的な方法ですね。将棋の場合は持ち駒の概念があるのでそれも更に加えます。

で、これに更に定数Lを加えます。Lというのはプレイヤの手番と手数と特別なルールを加えたものです。特別なルールというのは千日手とかそういうのです。チェスにも50手ルールとかあって、そういうのです(適当)

うーん、上手くイメージがつかめないのでさらなる精進が必要なようです。

駒の動きに関する情報

表だけ見てもイマイチわからないので、最初から読んでいきます。

駒の動きは2つの方法で表現されます。

  1. 動かす駒の位置の場合の数。
  2. その動きはその駒にとって合法な動きかどうか。
チェスの場合

合法手のバリエーションをπ(a|s)を使って表すと…

[mathjax]$$\pi(a|s)=8*8*73=4672$$

いやいやいや、その73ってどっからでてきた数字だwww

チェスの場合であれば盤のサイズは8*8であるので駒の位置は64通り選択できます。なので、

駒の位置は64通りあるのは納得できます。問題は次の73通りの意味。

原文では「The first 56 planes encode
possible ‘queen moves’ for any piece: a number of squares [1..7] in which the piece will be moved, along one of eight relative compass directions {N, NE, E, SE, S, SW, W, NW}. 」とあります。つまり、ナイト以外の全ての駒はクイーンよりも動ける範囲が小さいので、クイーンの場合の数で上から抑えるということですね。

さて、駒があったときにその駒がどの方向に動くかをコンパスの向きになぞらえて8通りで表現することが可能です。チェスはマスがタテ・ヨコ8列ですが「同じ場所に動く」という動きはありえないので最も動けるクイーンでも移動先は7通りを考えれば良いことになります。よって、クイーンの動きは最大で7*8=56通り。ナイトは八方桂と呼ばれるように、8方向動けるので8通りです。

さらに、ポーンは「成る」ことができるのでそれを考えます。基本的には最強の駒であるクイーンに成るのですが、ごく稀にそれ以外の駒(ルーク・ビショップ・ナイト)に成った方が良い場合があります。また、ポーンは相手駒を取る場合のみナナメに進むことができるのでそれも考えます。7列目から相手駒をとったり動いたりする他のポーンはクイーンに成ります(よくわからない)。

すると9通りになります(なんで?)

アンダープロモーションするかどうかで8通り、ナナメに取るかどうかで1通り?

[mathjax]$$\pi(a|s)=8*8*(56+8+9)=4672$$

なんでなのかよくわからないのですが、とりあえず飛ばします。

将棋の場合
  • (最も動けたとして)8*8=64通り。
  • 桂馬は2通り。
  • (桂馬以外の駒が)成る場合は64通り。
  • 桂馬が成る場合は2通り。
  • 持ち駒から打つ駒の種類は7通り。

[mathjax]$$\pi(a|s)=9*9*(64+2+64+2+7)=11259$$

こう考えると表現に関して言えばチェスの高々3倍くらいしか複雑じゃないんですね。

学習部

めんどくさいので将棋のところだけ。

  • 最小バッチ数: 70万
  • 訓練期間: 12時間
  • 対局数: 2400万
  • 思考時間: 800シミュレーションで80ms

1手80msとはいえ、将棋は1局が平均100手ほどなので1局8秒。8秒とはいえ、それを2400万局もやるとなると1回のシミュレーションで9.13年もかかってしまいます。ここはGoogleお得意の資源で一気に済ませてしまったのでしょう。

個人レベルでこんなに対局することは不可能ですが、計算資源が潤沢にあれば、対局数やシミュレーション数を減らしても実現可能な時間内でそこそこ強いプログラムはできるのではないかと期待。

評価

ロジスティック関数を用いてイロレーティングを算出。「強くなってなかったらパラメータを変えてやり直す」みたいな感じ。

評価にはあのやねうら王が使われている!

評価部も大事なんだけれど、将棋プログラムを作る上ではそんなに大事じゃないので省略します。