オセロAIを作ってみた話（設計編）

この記事について

はじめに

タイトル通り、この記事はオセロAIを作った道程をまとめた話です。電王戦が開催されていた時期からいつか自分でも作れたらなあと思ってました。ようやくある程度の成果が見えたのでここでアウトプットしておきます。
このページは設計編です。仕組みについてを説明します。実装した際の話は別記事にしますので、良ければそちらも是非ご覧ください。私が思いつきで考えた仕組みなのでボードゲームAIについての参考となる解説にはなりませんし、ましてやAIという言葉の一般論とは何の関係もございません。ご了承ください。
モンテカルロ木探索を自分なりに変えてみたことが主な話です。数学的な導出というよりは直観的な発想を試行錯誤した内容です。一応解説もしてみますが誤りを含んでいる可能性は十分にあります。

テーマ

それと今回AIを作るにあたっていくつかのテーマがありました。

• オセロについての戦略的な知恵は実装しない
• なるべく単純かつ直観的なアルゴリズムで実装する
• 自分には勝てるくらい強く

例えば角におくと強いとか序盤は石をとりすぎないとか、オセロについての知恵はプログラムしないこととします。オセロについてプログラムに教えることはルールだけです。なのでプロの棋譜から学習させることもしません。
なるべくわかりやすいアルゴリズムを目指しました。直観的に納得感があるようなものを作りたかったのです。
上記を満たしてもまるで弱かったら面白味がありません。長年ここで上手くいっていなかったのですがとりあえずオセロ素人である自分が負ける程度には強くなったのでよしとしました。

目次

• ビットボード
• モンテカルロ法を発展させる
  • モンテカルロ法
  • 発展させる
• 既知のアルゴリズムと比較する
  • モンテカルロ木探索
  • Thompson Sampling

ビットボード

まずはオセロを実装しなければ始まりません。ただ実装しただけも駄目で、高速に処理できてメモリ消費が少ないことが重要です。なぜこのふたつが重要かというと、人間では一生かけても不可能かもしれない探索を数十秒で処理しないといけないからですね。
オセロを実装するのに主な問題となる処理は下ふたつでした。

• 挟まれた石をひっくり返す
• ひっくり返せるマスを判定する

普通なら8×8の2次元配列と各8方向の繰り返しと条件処理をまず思い浮かべると思いますが、重いし遅いし到底間に合わないです。
ボードゲームにはビットボードというアイデアがあります。オセロなら64マスの石の有無をビット列で表現します。黒石白石合わせて128ビットで全ての盤面を表現できます。詳しくは調べてみてください。64ビットというと現代のアーキテクチャと丁度ハマっていそうですよね。実際コード上でひとつのInteger変数として扱えるのでオセロは特に楽でした。これが理由でオセロにしたようなもんですね。

問題のふたつの処理をビット列でどう実装するのかですが、私は下記記事を参考にしました。というかほぼパクりました。
https://primenumber.hatenadiary.jp/entry/2016/12/26/063226
https://qiita.com/klattimia/items/0f9dd41da83a68aa6d0f
いやホントすごいよね…。こんなのどうやったら思いつくんだ。ありがとうございます。

余談ですが、システムを作るときにまずデータ構造から考えるって大事だなあと改めて思いました。データ構造によってアルゴリズムが決まると言ってもいいですからね。

モンテカルロ法を発展させる

モンテカルロ法

さてAIと呼ぶ部分の話です。タイトルでは便宜上AIと呼称しましたが、実体としては探索アルゴリズムです。何をAIと呼ぶかは人によるところがありますが、私は教師あり学習より探索こそAIみを感じますね。
ここの章では発展の基盤となるモンテカルロ法についての説明をします。なのでわかっているかたは次の見出しへ飛ばしてしまって結構です。
局面の推移を木構造で考えます。ノードひとつがひとつの局面にあたります。その局面から1手進んだノードが子ノードです。置ける場所が複数ある場合は同じ数だけ子ノードもあることになります。今回は根のノードを現在の局面と考え、その子ノードを手の選択肢と考えます。わかりやすいので。

オセロであり得る全てのノードを展開することは不可能です。全てのノードは5個の子ノードを持つと単純化すると、あり得る局面の数はおよそ5の60乗になります。現代のハードウェア性能ではオセロの完全解析は現実的でないです。
ので、乱数を活用したシミュレーションによって勝率を見積もります。とある局面（つまりノード）から見込みのある手（つまり子ノード）を選びたいとき、子ノードをランダムに選択しさらにその子ノードもランダムに選択するのを繰り返してゲームをシミュレーションします。いずれは終局し勝敗が決着します。
1回のシミュレーションをプレイアウトと呼びます。プレイアウトを何回も繰り返した結果、勝率が良かった子ノードが見込みのある手と考えることができます。なにせランダムなシミュレーションなので、勝率に差が出るとしたら始めの子ノードが有利あるいは不利であったはずです。

ただこのモンテカルロ法、それほどうまくいかない気がします。複数の子ノードのうち抜群に良い手がひとつあった場合、親ノードの推定値がランダムに子を選ぶせいで低い推定値になってしまうんですよね。実際のゲームでは最も良い手を選ぶのが当たり前なので最も良い子ノードの勝率がほとんど親ノードの勝率であるはずなのに、全ての子ノードを平均したような勝率を算出してしまっている感じです。

効率的に探索する

そこで、プレイアウト中に子ノードを選ぶときの「ランダム」について考えます。先に書いたランダムというのは「全ての子ノードが等しく選ばれる可能性を持つ」という意味です。実際の手順っぽく考えると、全ての子ノードそれぞれについて一様分布[0,1]から生じる乱数を引き、最も数値の高かった子ノードを選べばランダムということになります。

このランダムを、もっと賢いランダムにしたいです。これまでのプレイアウトで勝率が良ければ良いほど1に偏った乱数値を引くようにしたいです。そうすればでたらめに石を置くのでなく良いと思われる手を優先して選ぶシミュレーションができます。モンテカルロ法のランダムゆえに平均化してしまう問題を回避できます。双方良いと信じる手を選ぶのが本来のゲームであり、自然なシミュレーションと考えることもできるでしょう。
ベータ分布乱数を利用することで上記の賢いランダムが実現できそうです。ベータ分布は母数αβによって[0,1]において確率密度分布関数を持ちます。αが大きいほど1側に偏り、βが大きいほど0側に偏ります。またふたつの数が大きいほど分散が小さくなります。プレイアウトの結果勝ちであればαに、負けであればβに何らかの評価値、単純に考えれば1を足せば分布の形は都合よく偏っていきます。この分布から乱数を生成すれば望んだ乱数が得られそうです。

ただ、本当は他にもっと良い子ノードがあるのに偶然シミュレーション初期で勝ってしまった子ノードがいた場合、局所解に陥らないかという疑問も浮かびます。一応分散が良く作用するはずで、試行が少ないノードほど乱数の分散も大きく、高い乱数値を引く余地があります。よって勝率の考慮と未知の探索とをバランス良くしてくれるはずです！（思考放棄）

プレイアウトを重ねる毎に木構造データは大きくなり、各々の情報も更新されていきます。乱択によって選ばれた子ノードはさらにその子ノードを展開し、また乱択によって子ノードが選ばれ…というのを繰り返しながらプレイアウトは進んでいきます。やがて終局ノードに達し勝敗が決まったら辿ってきたノードを遡るように勝敗情報を母数に反映していきます。

母数をどう更新すればいいかは難しい問題です。1回のプレイアウトで序盤から終盤にかけてのノードが全て更新されるわけですが、序盤と終盤のノードで母数を更新する値が等しいのはどうかと思うんですよね。プレイアウトは乱択で進むので、1回1回のプレイアウトによる勝敗も偶然性を多分に含みます。探索の初期は特にですね。プレイアウトの最終的な勝敗は序盤ノードに遡っていくほど相関が少なくなっていくと考えられます。
なので、序盤ノードと終盤ノードが同じ速度で更新されないように調整します。ノードを遡る毎に更新値を割り引いていきます。これで偶然による勝敗によって乱数が偏ることも防ぎ、分散が小さくなりすぎることも防ぎます。ただどの程度割り引けば良いかがまた難しく、ここの話は実装編でまたお話したいと思います。

既知のアルゴリズムと比較する

モンテカルロ木探索

先に言うべき話でしたが、ボードゲームAIを木構造で考えるアイデアはモンテカルロ木探索と呼ばれる既知のものです。今回私が考えた探索方式もモンテカルロ木探索の特殊系といえます。モンテカルロ木探索は何らかの優先値を持って子ノードを展開する部分と一様な乱択によってプレイアウトを進める部分が分かれています。ノードは設定した試行回数を超えると子ノードが展開されます。
私が思いつきで実装したモンテカルロ法発展形は、モンテカルロ木探索で子ノードを展開する条件がなく、プレイアウト中にそのノードに至った時点で子ノードを展開する特殊系と言えます。そしてゲーム終了まで子ノードを展開するので、一様な乱択部分は存在しません。

Thompson Sampling

実装中に知ったのですが、ベータ分布乱数を利用する今回のアイデアはどうやらThompson Samplingという既知のアルゴリズムのようです。バンディット問題の優先度の算出式としてUCTが有名ですが、ThompsonSamplingもかなり有力なアルゴリズムのようですね。といっても数式をきちんと追ったわけではないので、今回のアイデアが本当にこれに該当するかはおそらくという話になります。

おわり

といった感じでオセロAIの仕組みを思いつくまま作ってみた話でした。わかりやすく説明するのは難しいですね…上手に説明できない。意味わからないところとか間違っている箇所などあればコメントくださればできる限り対応します。
実際に実装したときの話は別編で記事にしますのでご興味あれば是非。

Ubuntuでもゲームがしたいっ！

SteamのProtonとかいうグレートなやつ

私用PCはUbuntuです。過去にノリでWindowsからUbuntuに換えて、やはりUnixベースは使い勝手がよくそのまま使っています。
使い勝手がいいとは言ったものの、世の中大半のPCゲームはWindows向けに発売されます。なかにはUbuntu版も開発してくれる意識高いゲームもあったりしますが、数は少ないです。流行りのPUBG、APEX Legends、Dead by Daylightなど、全てWindows版のみの発売です。
Ubuntuは気に入っているので使い続けたいのですが、無性にゲームがしたくなるときがたまにあります。親がゲームを買ってくれなくてクラスの輪に入っていけない小学生の気分です。
Ubuntuユーザーがゲームを楽しめないという問題に、Steamが取り組んでくれています。それがProton。Unix系OSでWindowsゲームを動かすプログラムの開発は昔からされていましたが、ValveがそれをSteamに向けた本格的な実装としました。
最近Protonの存在を知って、私も試してみることにしました。開発側は圧倒的多数であるWindowsに向けて開発するしかなく、そうなるとユーザもWindowsを選ぶしかないこの負のスパイラルを断ち切るんや！

グラフィックボードを買い換える

とはいったものの、私のPCはそもそも最新ゲームを遊ぶスペックがありません。スペック詳細をわざわざ書きませんが、グラフィックボードはGTX750Tiです。これではProtonを使ったところでですね。
なので多少のスペックアップをすることにしました。GTX1050Tiに換えます。ローエンドじゃねーかと言われそうですが、PCがローエンドなのでバランス的にこんなもんです。画質設定を下げれば最近のゲームでも何とかなるようです。
グラフィックボードの交換は初めてします。PCの自作経験がないのでけっこうわくわくというかどきどきでした。
いざ交換してみると、トラブルがなさすぎてあっけなかったです。ドライバのインストールさえ不要でした。同じGTX系だったからでしょうが、それにしてもハードが換わったのにドライバってすごいな…とひとり感心していました。こんなシステムエンジニアで大丈夫か？

引退するGTX750Ti

Steam Playを設定する

さて次はProtonの設定です。Steamを普通に使っていればProtonを手動インストールする必要はないようですが、Protonを動作させるためにいくつかやっておくべきシステム要件があるそうです。
まずはSteamの設定を変更します。デフォルトだとSteam Play（Protonが起動されるモード的な？）はValveが動作確認を取れたゲームのみが対象となっています。どんなゲームでもSteam Playで起動させるためにはクライアントの設定を変えましょう。

お次にProtonのシステム要件を確認しましょう。どうやらnvidiaドライババージョンが最新である必要があるようです。ドキュメント通りにコマンドを実行していきますが、apt installのところで私は失敗しました。既にnvidiaドライバはありますから、それはそうかもしれません。aptitude installを実行したところ何も問題なくアップデートできました。
これでProtonが実行できるようになりました！

圧倒的容量不足

さあゲームするぞ！と意気込み私は鉄拳7のインストールを始めました。ちょうどセールになっていたし、昔ちょっとやっていたので。
私のPCはSSDの100GBしか容量を積んでおらず、最近のゲームは数GBとか普通らしいからな〜足りるかな〜と思っていたところ、

嘘だろおい。Windowsよりでかくねーか？
これは追加のディスクが必要ですね…。まあ100GBじゃあ窮屈だなと前から思っていたので、いい機会です。HDDを増設することにします。
というわけでAmazonでHDDをポチったのですが、ここで閃きました。そういえば遥か昔私がまだ大学生だった頃、ファイルサーバが欲しくて買ったものの結局使わずじまいで眠らせてあるNASがありました。中開けてディスク取り出せば使えるんじゃね…？

HDDを追加する

申し訳なく思いながらもAmazonの注文はキャンセル。NASをばらしてみます。製品はこれ。当然ですが、ユーザが勝手に開けたりすれば保証の対象外です。自己責任です。

おーいたいた。普通の3.5インチSATA接続のHDDですね。これなら問題なく使えるでしょう。
というわけで取り出したディスクをPCのドック？に接続。なんだかネジ穴の位置が合わず何度もディスクをガシガシ動かしている間にだいぶこすり、側面が傷だらけになってしまいましたが気にしない。

OSも問題なく認識してくれました。ただファイルシステムがNTFSだったので（そりゃそうか）、一度フォーマットしました。

ゲームを起動する

いよいよです。いよいよゲームができます。鉄拳7のインストールも無事終わり、Ubuntuから起動します！

…何も問題なく起動しました。Valveが動作確認済みだとは知っていましたが、こんなにすんなりと動くものか。Valve最高やん。Steam信者になっちゃう。
というわけで普通に鉄拳7が遊べちゃいました。文字化けくらいするかなと思っていましたがそれもないですね。

こうなると動作確認済みでないゲームも試してみたくなります。FFXIVでも試してみるかなあ。
というわけでPCPCした週末でした。

ラズパイでインターネット速度を観測する

インターネット速度を観測したい

前回はpingコマンドから自宅回線のMbpsを計測してみました。今回は計測した結果を24時間記録する仕組みを作ってみたいと思います。
結論を先に書きます。途中から当初の「回線環境が悪いと困る」という動機ではなく、「どうせ業者は理論値なんて言って消費者を搾取しているんだろうから俺が暴いてやる」という歪んだ動機に変わっていましたが、実際はそんなことはありませんでした。一般使用では特に困らない程度の速度が出ていましたし、安定もしていました。回線業者を勝手に疑って勝手に申し訳ない気持ちになっています。

ラズパイを使う

自宅のデスクトップPCを24時間つけッばなしにしておくわけにもいかないので、何か低消費電力で24時間動かせるコンピュータが欲しいです。Raspberry pi、通称ラズパイを使うことにします。
ラズパイにもいくつか種類があります。今回はpingとちょっとしたスクリプトを動かす程度のスペックでいいので、ラズパイのゼロシリーズを使うことにします。1000円で買えてしまうコンピュータです。

下はiPhone7。めちゃ小さい。
ゼロシリーズには有線LANアダプタが備わってません。今回は自宅のネットワーク環境でなく回線のネットワーク環境を観測したいので、有線で直接ルータに接続したいです。
PLANEXのUSB有線LANアダプタをたまたま持っていたのでこれを使います。ドライバ内蔵型なので挿しただけで使えます。素晴らしい。

セットアップ

さてラズパイを購入したのでセットアップを始めます。公式ドキュメントに従ってセットアップすれば何も困りませんでした。
インストールは簡単で、公式で配布されているイメージをmicroSDに書き込み、ラズパイに挿し込んで起動すればインストールが始まります。ラズパイとmicroSDとの相性問題が多少あるようですが、私は何も問題なくインストールできました。
OSはRaspbianというラズパイ用のものです。Linux派生のOSなので、普通に使う分には学習コストも特にありません。gitも使えますし、cronも動きます。もちろんpingも。
つまりアプリケーション側のセットアップもほとんど手間はありませんでした。自分のGitHubからコードをダウンロードすればいいです。アプリを定期で自動実行したいので、cronに登録します。何となくgit pullもcronに仕込みました。これでアップデートしたソースコードは勝手に取り込まれます。
有線LANアダプタも問題なく使えました。マジで手がかからなくてあっけなかったです。
今回書いたコードです。別に何の特徴もありませんが。

可視化する

いよいよ実際に記録したデータを見てみます。

文字が重なっちゃってますが、10分毎のMbpsを3週間ほど記録した推移です。
ね？2回ほど大きく下がった瞬間がありましたが、30~45Mbpsが安定して出ています。私インターネット回線ってもっと不安定なものだと思ってました。同居人や隣人がYouTubeでも観ていようものならMbpsが10未満まで落ちたり、夜間は全国的に回線が詰まってMbpsが20程度だったりとか、そんなもんだと思っていましたよ。なので観測結果に驚いています。いやあお恥ずかしいというか、インターネットってすごいなあと感心しています。

次回

結果が出たので次回もなにもないのですが、今度は統計分析的な何かをやりたいなあ。

pingでインターネット速度を計測する

ご挨拶

Markdownでブログが書きたいなあということではてなブログ始めました。
都内で働くしがないシステムエンジニアです。
自己紹介記事を書いたほうがいいのかもしれませんが、それはまた改めて。

ネットワーク速度を測りたい

突然ですが、最近引っ越しました。
引っ越し先はインターネット回線が備え付いてあり、自分で回線工事やプロバイダ契約などする必要はないとのことでした。備え付けのものを利用するなら使用料金もかからないらしいので、ありがたく使わせてもらっています。
ただ気になるのは通信速度です。備え付きの回線業者名を聞いたところ、はじめて聞くような名前でした。YouTubeやNETFLIXが止まる＆画質が悪いと困ります。
そこで回線速度を観測することにしました。

pingで測る

さてまずはデータをどうやって取るか。
2秒くらい悩んで、pingコマンドで取ればいいなと考えました。他にもFTPやらで測る方法もあるでしょうし、そもそも速度を測定するための便利なライブラリがネットに転がっているでしょうが、せっかくだし自分でやってみます。
例えばyahoo.co.jpにpingを打ってみるとこうなります。

$ ping -s 1024 -c 5 yahoo.co.jp
PING yahoo.co.jp (182.22.59.229) 1024(1052) bytes of data.
1032 bytes from f1.top.vip.ssk.yahoo.co.jp (182.22.59.229): icmp_seq=1 ttl=51 time=100 ms
1032 bytes from f1.top.vip.ssk.yahoo.co.jp (182.22.59.229): icmp_seq=2 ttl=51 time=33.7 ms
1032 bytes from f1.top.vip.ssk.yahoo.co.jp (182.22.59.229): icmp_seq=3 ttl=51 time=33.7 ms
1032 bytes from f1.top.vip.ssk.yahoo.co.jp (182.22.59.229): icmp_seq=4 ttl=51 time=38.3 ms
1032 bytes from f1.top.vip.ssk.yahoo.co.jp (182.22.59.229): icmp_seq=5 ttl=51 time=31.6 ms

--- yahoo.co.jp ping statistics ---
5 packets transmitted, 5 received, 0% packet loss, time 4006ms
rtt min/avg/max/mdev = 31.604/47.578/100.347/26.477 ms

1キロバイトのデータを5回送り、最後にまとめが表示されます。rtt（ラウンドトリップタイム）というのはデータを送ってから返ってくるまでの時間のことであり、ここのavgつまり平均値を参考とするのが良さそうです。

pingの注意点その１

1回ずつの結果を見てみると、1032バイトのデータが送信先から返ってきているようです。ここを気をつけなくてはならなくて、試しに送信先をgoogle.co.jpに替えてみます。

$ ping -s 1024 -c 5 google.co.jp
PING google.co.jp (172.217.26.3) 1024(1052) bytes of data.
72 bytes from nrt20s02-in-f3.1e100.net (172.217.26.3): icmp_seq=1 ttl=53 (truncated)
72 bytes from nrt20s02-in-f3.1e100.net (172.217.26.3): icmp_seq=2 ttl=53 (truncated)
72 bytes from nrt20s02-in-f3.1e100.net (172.217.26.3): icmp_seq=3 ttl=53 (truncated)
72 bytes from nrt20s02-in-f3.1e100.net (172.217.26.3): icmp_seq=4 ttl=53 (truncated)
72 bytes from nrt20s02-in-f3.1e100.net (172.217.26.3): icmp_seq=5 ttl=53 (truncated)

--- google.co.jp ping statistics ---
5 packets transmitted, 5 received, 0% packet loss, time 4006ms
rtt min/avg/max/mdev = 14.866/17.136/23.417/3.170 ms

送信するデータのサイズは1024と変えていません。ところが、返ってくるデータは72バイトになっています。調べていませんが、ICMPのサーバ側の設定によっては送ったのと同じだけのデータ量を返すとは限らないようです。測定した時間から通信速度を計算するときには要注意です。

pingの注意点その２

pingで送信できるデータサイズの最大値ってどれくらいでしょう。私の手元では60kb程度でした。
ところが送ったpingが返ってくるかは、これもサーバ側の設定次第のようです。試しに先ほどと同じ送信先google.co.jpに大きなpingを打ってみましょう。

$ ping -s 2048 -c 5 google.co.jp
PING google.co.jp (172.217.26.3) 2048(2076) bytes of data.

--- google.co.jp ping statistics ---
5 packets transmitted, 0 received, 100% packet loss, time 4088ms

はい。サーバ側の制限値を超えると返してくれなくなるようです。十分なデータサイズで計測したい場合には、寛大なサーバを探す自分でサーバを建てるべきです。

Mbpsを計算する

さてサーバ側の設定に気を付けつつrttを測れば、そこから通信速度を表す一般的な指標であるMbpsを計算するのは難しくありません。「(送信サイズ+受信サイズ) / rtt」でいいですね。あとは単位に気をつけて(自戒)。
ところで、送信するデータのサイズはどれくらいが適当なのか。サイズを変えたときにMbpsがどのように変わるのか、実験してみました。

そうですね。パケットにはヘッダが付きますので、オーバーヘッドが存在するようです。
ではどの程度のデータサイズで測るべきかと言われると、正直よくわかりません。普段の通信を模したデータサイズであるべきでしょうが、普段どれくらいのデータサイズで通信しているのでしょう。ブログを漁ることもありますし動画を観ることもあります。
よくわからんですが、Mbpsの変動が相対的に落ち着きはじめる50kbくらいの結果を参考にしておきましょう。

次回

これでネットワーク速度を測ることはできるようになりました。しかし、「なんだかネットが重い」と感じたときにリアルタイムの計測値を確認したいですし、過去の計測値も後から見てみたいです。つまり24時間観測したい。
次回は計測値を記録していく仕組みを作ります。おいしそうな名前のあのコンピュータを使いましょう。まさか普段遣いのノートPCを24時間つけっぱなしにしておくわけにはいかないですし。

ここまで読んでくださりありがとうございました。次回も見てくださると幸いです。