TIM Labs

「オセロを実装する」と一致するもの

原始的なモンテカルロ探索を示したが、これは成功率が1%にも満たないものである。

もっと高い成功率を求めて、囲碁プログラミングで使われだした「モンテカルロ木探索」を、「計算」でも使えないか試してみよう。

ゲームやパズルでは、状況を分析するために、現在の盤面をルート(根)とする木を作るのが一般的である。

3手先までの木を作るとこんな感じになる。

lab-calc6-1.png

これは標準的な木で、一番下の葉のところでプレイアウトして、それぞれの成功確率を計算し、上に遡りながら一番良い手を選ぶというやり方があるが、ここではそれは説明しない。

枝の伸ばしについて、どの場合も同じ割合で伸ばしているが、これで良いのだろうか?

囲碁や将棋を考えてみれば分かるが、これはと思う枝はどんどん深く読んでいくが、これは論外だなというのはさっさと切り捨ててしまう。つまり、こんな感じの木ではなく、特定のところが深く探求され、かなり「いびつな木」が出来上がっている筈だ。それをこれから説明していこうと思う。

モンテカルロ木検索がどのようなアルゴリズムであるかについては、色々なところに説明があるので、ここに説明を長々と書くよりも、良さそうな情報源を紹介する方が役に立つし、こちらは楽なので、紹介するに留める。


モンテカルロ木関連情報


『コンピュータ囲碁におけるモンテカルロ法〜理論編』美添一樹(pdf)

とても丁寧な説明なので、十分理解できると思う。ただ、囲碁に偏った説明が多くなっているが、元々囲碁で使われだしたので、当然囲碁を使って説明が進む。とくに囲碁を理解していなくても大丈夫なのだが、囲碁の説明部分を十分に理解したい場合は、この際囲碁をマスターしてしまおう。

理論的な基礎は、このPDFだけで十分ではないかと思う。というか、それくらいしか読まずに「計算」に適用してみようという大胆なことをやっているのが実情である。

これで書ける「囲碁講習会」全4回@電気通信大学

こちらは、2015年夏に電気通信大学で行われた囲碁プログラミングの講習会で、
実践編2 UCTアルゴリズムで打つ』の中で説明されている。

実際に強いプログラムを作っている人が、囲碁プログラミング初心者向けに、多数のソースコードを用意し、実際の動きを体験させる講習会で、ビデオ、資料も充実しているので、とても参考になった。

ビデオはとても長い。1本約3時間であるが、十分に見る価値がある。

JavaScript でオセロを実装する(モンテカルロ木探索AI)

こちらは、本ブログのもので、囲碁ではなくオセロで試みた例になっている。


「囲碁」と「計算」での相違点

モンテカルロ木探索を使うのだが、ほとんどの説明は囲碁の場合であるが、計算にそのまま適用できない部分がある。
まず、囲碁は、「二人完全情報ゲーム」であり、計算は「一人不完全情報ゲーム」である。 これから、2つの相違点があることが分かる。

二人 vs 一人

二人での対戦型では、プレイヤーが替わる度に盤面評価が逆になる。 自分に良い手は相手にとっては不都合であり、 相手の良い手は自分にとって不都合である。 つまり、一手打つ度に、評価を反転しなくてはならなくて、 そのために、Min-Max法とかαβ法とかいろいろ工夫されている。

しかし、今回は一人ゲームなので、常に自分の手番である。なので、可能な手から一番良い手を選ぶだけでよいので、この点ではとても簡単になる。

完全情報 vs 不完全情報

囲碁は、全ての情報が完全に見えているゲームである。偶然が入る余地はなくて、強い人と弱い人が対戦すると強い人が勝ってしまう。つまり、偶然勝てるなど、ないのである。

しかし、計算は手札を一枚ずつめくってプレイしていくが、どの数字が出てくるかはプレイヤが決めることができない。残りの手札の中のどれかが出てくるのだが、それ以上は決めようがなく、実際には乱数を使って残り手札の中からランダムに選んでおり、不完全情報ゲームになってしまう。

不完全情報ゲームになるのだが、カードをめくる部分なので、最大1〜13通りしかありえない。この不完全な部分も木に組み込むことになる。プレイヤに選択権がある場合は最適な手を選べば良いだけだが、不完全な部分に対して予測を立てる必要があり、そこで枝分かれが増えるために木が横に広がってしまう。

というのが基本的な相違点である。


今日はここまでとし、次回からは、以上を考慮に入れて、ソースコードレベルで実装していく。

問題

前回はオセロの対戦AIを原始モンテカルロ法で作成しました。実際に対戦してみると「角は優先して取るべき」等といったオセロのノウハウを全く知らない乱択ベースとは思えないそれなりの強さでした。

試行回数が200回/手とはいえそれなりの強さだったのですから、試行回数を増やせばもっと強くなるはずです。 しかし単純に試行回数を400回/手、800回/手......等と増やしていくと問題が出てきます。

  • 序盤や終盤は着手可能な場所が限られているものの、中盤になると数が膨大になります。試行回数をn回/手にしてるとAIの思考(試行)完了待ち時間が長くなってストレスフルです。
  • 試行方法を「全体でN回試行する」「各手についてNを等分して試行する」ことにすれば中盤のストレスは減りますが、これは中盤の各手の試行回数を減らしている為、中盤の手筋は質が下がって弱くなります。

そもそも、 着手可能な手を平等に試行する必要はあるのでしょうか? ある程度試行すれば各手の大雑把な勝率が得られますから、 勝率(大雑把)が悪そうな手について試行するよりも 勝率(大雑把)が良さそうな手について試行回数を重点的に割り振った方が効率が良いですよね。

しかし、これは少々の試行回数で割り出した勝率(大雑把)なので、 勝率(真)とはかけ離れている可能性はあります。 勝率(大雑把)が悪いからといって早々に切り捨ててしまうと、それが本当に良い手だった時に困ります。

つまり、

  • 勝率の良さそうな手を重点的に試行する
  • 実はもっと勝率の良さそうな手があるかも知れないので他の手も調べる

という2点を上手いことバランスを取って試行を行えば、 原始モンテカルロ法よりも少ない試行回数で効率良く精度の高い勝率を叩き出せそうですね。 でもこの2点、どう考えても矛盾してます。どうやって最適なバランスを取ればいいのでしょう?

問題

以前、オセロの対戦AIの作成しましたが、そこでは実装を簡略化する為に盤面の価値を

  • 盤面の価値 = 自分の石の数 - 相手の石の数

という単純な方法で決めていました。 でも、これには問題があります。

  • 同じ石でも配置場所によって価値は異なるはずです(例: 角は最強)。それが考慮されていません。
  • ゲーム終盤になってくると石の数が重要になってきます。でも序盤から石の数を重視するのは方向性としておかしいです。

という訳で、

  • 序盤から中盤では石の配置場所を重視する
  • 終盤では石の数を重視する

形で盤面の価値を算出すれば、結構良さそうなAIになりそうです。

しかし、今度は

  • 「序盤」「中盤」「終盤」をどのように区別するのか?
  • 石の配置場所の強弱はどう決めるのか?
  • 同じ配置場所でも周囲の状況次第で強弱が異なるのでは?

という問題が出てきます。これは作るのが面倒臭そうです。

どうにかしてお手軽かつそこそこ強そうなAIを作れないものでしょうか?

問題

以前、 JavaScript でオセロを実装 していたのですが、 この実装には一つ大きな問題がありました。

AI相手にゲームをするのは、それはそれで楽しいものの、 やはりこの手のゲームは人間同士で対戦したくなるものです。 一応、あの実装は人間同士で対戦できると言えばできるのですが、 同じPCの前に座って交代しながら操作する形になので、色々と不便です。

インターネット全盛のこの時代、やはりネット対戦できるようにしたいですよね。 しかしプレイヤー間の通信やプレイ中のゲームの状態の共有は一体どうすれば良いのやら。 オセロのようなターン制の単純なゲームでさえネット対戦対応するには課題が山盛りです。

どうにかして簡単にサクサクっとネット対戦できるようにできないものでしょうか。

これまでのあらすじ

オセロを実装し始めて早幾年。 ようやくまともなAIを作る基礎ができたので、 ここからは「より強いAI」をどう作っていくかを考える段階になりました。 しかし、これには色々と問題があります:

  • 「AIの強さ」を定量化できないと 「ぼくのかんがえたさいきょうのAI」がどれぐらい強いのかさっぱり分からない。
  • かといって人間が判定するにしても 「これは雑魚だなー」 「これは手強かったかも」 程度の大雑把な分類しかできない。
  • そもそもこれまでにテストプレイとして何十回もオセロをやってきたので、 もう手動でオセロをプレイするのは面倒臭い。

という訳でAIとAIを対戦させて自動でゲームを進行させれば手間が省けるのではないでしょうか。

これまでのあらすじ

まともなオセロの対戦AIの作成を開始したものの、 「4手先を読む」だけでも検討にかかる時間が長く、 とても快適に遊べるとは言えない状態でした。 これでは肝心のAIの形勢判断を調整する以前の問題であり、 先読みする手数を増やしてAIの「腕前」を上げることも困難です。

Lv 4のAIとの対戦の様子

先読みする手数を減らせば快適に遊べるようにはなりますが、 それでは「目先のことしか考えない」弱いAIにしかなりません。 どうにかしてAIの動作速度を改善できないものでしょうか。

これまでのあらすじ

一人二役の寂しいオセロから脱却すべく、 オセロの対戦が務まるAIの作成を始めた。 しかし、一通り動きはするものの、このAIは形勢判断を全くせずにテキトーに手を選んでいるだけなので非常に弱い。

オセロってこんな早く終わるゲームじゃないと思うんですけど!?

なので少しは歯ごたえのあるまともなAIを作ろうと思うのであった。

これまでのあらすじ

新人の力量を測るための課題としてオセロの作成を指示したが、 指示した当人が作れないようでは話にならないので実際に作り始めた。 盤面が4x4で黒も白も人間が指す一人二役の寂しいオセロは実装でき、 遅延評価を導入して性能の改善と実装の簡潔さの両立を図った。

しかし一人二役はいくらなんでも虚しい。 なので AI を実装して一人でも遊べるようにしようと思うのであった。

これまでのあらすじ

新人の力量を測るための課題としてオセロの作成を指示したが、 指示した当人が作れないようでは話にならないので実際に作り始めた。 一先ず盤面が4x4で黒も白も人間が指す一人二役の寂しいオセロは実装できたのだが、 快適に遊ぶには大きな問題が潜んでいたのであった。

問題

今年も弊社に新卒採用で入社された方が何名かいます。 採用情報ページに記載されているように、 弊社ではメンター制度が設けられており、 誰かしら指導役の社員が面倒を見たり見なかったりします。 ただ指導するにはまず相手の力量を測る必要があります。 技術者として採用された方を相手にするなら、 適当な課題を与えて、それに対して作り上げたモノを見るのが一番手っ取り早いです。

と言う訳で「適当な課題」として今回は「オセロを実装する」ことにしました。 しかしこれだけではテキトー過ぎるので、以下のように段階を設定しました:

  1. 黒も白も人間が指す一人二役の寂しいオセロを実装する。
    • 盤面のサイズは4x4とする。
    • 外観やUIは凝らなくてよい。
    • 実装はJavaScriptで行い、Webブラウザで遊べるものにする。
  2. 仮AIを実装する。このAIの手筋は以下の通り:
    • 取り得る手のうち最も上の行に石を置ける手を選ぶ。
    • 同一行に指せる手が複数あるなら最も左の列に石を置ける手を選ぶ。
  3. 本格的なAIを実装する。このAIの手筋は以下の通り:
    • 最大4手先まで読み、取り得る盤面のうち最も「優勢」な盤面に辿り着く手を選ぶ。
      • AIの手番を読む時はAIにとって最も「優勢」な盤面になる手を選ぶ。
      • 人間の手番を読む時は人間にとって最も「優勢」な盤面になる手を選ぶ。
    • AIは同じ盤面に対して常に同じ手を指す。
    • 「優勢」度合いの判定は凝らなくてよい。
  4. 盤面を6x6や8x8に拡大する。
    • 拡大に伴って処理すべきデータ量が増大するのでパフォーマンスが落ちる。快適に遊べるようパフォーマンスを改善すること。

各段階での狙いとしては

  1. オセロくらいのロジックはサクサク組める。
  2. 「誰が手を指すのか」を見越して抽象化した処理を書ける。
  3. 再帰的なロジックがサクサク組める。
  4. ボトルネックを見つけ出して適切な対処を取ることができる。

といったところです。

が、課題を設定した人間がこれくらいサクサク書けなくては話になりませんよね。 と言う訳で実際に実装してみることにしましょう。 できれば昨今のビッグウェーブであるところの 関数型プログラミング に乗っかった形で書けばかっこいいんじゃないでしょうか。

(なお、 実際に作成したオセロのソースコードは GitHubで公開されており、 完成品で遊ぶこともできます)

1

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。