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通りしかありえない。この不完全な部分も木に組み込むことになる。プレイヤに選択権がある場合は最適な手を選べば良いだけだが、不完全な部分に対して予測を立てる必要があり、そこで枝分かれが増えるために木が横に広がってしまう。

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


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

最近、将棋や囲碁のプログラムが非常に強くなった。将棋は機械学習を取り入れるようになったのだが、囲碁は「モンテカルロ木探索」という方法を取り入れて、一気にアマチュア高段者レベルに達した。

難しいと言われる囲碁でこれだけ成果を出した「モンテカルロ木探索」を、別の分野で試し、有効性を検証してみることにした。


ゲームをプログラムにプレイさせるとき、一般にはゲーム木なるものを作り、それぞれの手を選んだ時の勝率を計算し、より勝率の高い手を選ぶことで実現するのが一般的だ。木を完全に展開できる場合、つまり全ての可能性を読み切れる場合はそれでお終いなのだが、ほとんどのゲームは読み切れるほど木が小さくないので、適当なところで盤面を評価し、各葉ノード値とし、それを元に次の一手を選ぶ。このとき、盤面評価の性能が強いか弱いかを決めることになる。


しかし、盤面評価は難しい。この難しい部分を、定石などに基づいてガチにプログラムを組むことが行われていたが、なかなか成果が出ないのが現実である。そこで、当然考えられるのが、盤面評価が面倒なら、面倒なこと自体を放棄しよう。どうせ無駄だ、、、という考えがある。


面倒なプログラムを書くには、対象にしているゲーム(課題)を十分に研究しないといけないが、全部やめてしまうとどうなるか。でも、最後までプレイして、勝ったか負けたか、あるいは成功か失敗かくらい分かれば何とかなるかも知れないではないか。ということで、何の知識も持たない、ただルールを厳守するだけのどうしようもないプレイヤー・プログラムを用意し、これとモンテカルロ木探索を組み合わせて、十分強い、十分賢いプログラムができるかどうか検証してみる。


囲碁は、二人完全情報ゲームである。類似のものとして、オセロがあり、これは本ブロクでも紹介されているので別のことを考える。まず、二人でないゲームとして、一人と多人数という選択肢があるが、一人の方がプログラムが楽そうなので、一人ゲーム、一人遊びを選択する。完全情報ゲームはやめて、不完全情報ゲームを選ぶ。また、はっきり有限手数で終わるものを選ぶ。つまり、一人有限完全情報ゲームでモンテカルロ木探索の有効性を検証する。



さて、利用するひとり遊びは、トランプのひとり遊びの中から「計算」を選んだ。このひとり遊び(ソリティア)は、数学者&コンピュータ研究者として著名な野崎昭弘氏の「とらんぶ」ダイヤモンド社、初版昭和49年により知った。

一度絶版になったが、今は朝日選書として復刊しているようだ。



tramp1.jpg   tramp2.jpg



計算のルール


準備:


ジョーカーを除いた52枚のカードを使用する。ただし、スーツ(種類)は無視する。

A,2,3,4の4枚を取り出し、並べる。これらが台札である。

4つの台札の下に、4つの屑札をおける場所を確保しておく。

のこり48枚のカードは、しっかり切って、重ねて手札とする。


lab1-1.png

各台札の上には、それぞれ最初の台札(1,2,3,4)だけの間隔を開けてカードを重ねることができる。

つまり、次のようになる。Kの次には、A,2,...と繋がると考える。

なお、全ての数字を1文字表示にしたいので、10はTで示している。


lab1-2.png

プレイ:


手札を1枚めくる。

表になった手札は、台札に重ねるか、屑札に重ねることができる。台札に重ねるときは、指定された間隔を保たなければならないが、屑札に重ねるときには、どの屑札でも構わない。

屑札の一番上のカードは、台札にいつでも重ねることができる。もちろ、、指定された間隔を保たないといけないが。

手札を台札か屑札の上に移動し終えると、手札をめくることができる。

以上が、可能なカードの動かし方の全てだ。


lab1-3.png

         ※上図の手札は最初(一番上)の5だけが見えていて、それ以降は本当は見えていない。



目的:


この遊びは、以上のルールに従ってカードを動かし、全てのカードを台札に重ねることができたら成功である。

そのとき、どの台札も、一番上はKになる。



例:


次に、「計算」の最初の方のカードの移動を図で示す。ほとんど台札に重ねられる数字が手札から出てこなかったため、延々と屑札の上に積み重ねている。


最初の方だけ、実際にどのようにプレイが進んでいくかを示す。図についての説明は面倒なので省略するが、分かると思う。


lab1-4.png


今回の説明はここまでにしておく。

まず、この一人遊びを実際にプレイしてみて、自分の頭でどのくらいの成功率になるか確認していただきたい。

もし1割以上の成功率ならば、相当優秀である。

モンテカルロ木探索では、戦略は無視なのだが、次回は「計算」の戦略を紹介する。その戦略を使うと、人手でプレイしても一気に成功率が上昇する。

問題

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

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

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

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

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

つまり、

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

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

問題

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

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

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

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

という訳で、

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

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

しかし、今度は

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

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

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

問題

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

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

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

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

前回までのあらすじ

オセロシリーズに続く題材としてシェフィを実装しようと思い立った俺達は大まかな設計をしただけで力尽きてしまった。実際のコードはまだ一行も書かれていない。果たして無事にゲームを実装し終えることができるのか。

問題

前回、新人研修の一環として「オセロの実装」を課題として設定したものの、 設定した当人が実装できないようでは話にならないので頑張って実装しました (一人二役で指す寂しいゲーム編 / 遅延評価編 / 仮AI作成編 / 本格AI作成編 / AI高速化編 / AI vs AI編)。

これはこれで楽しかったものの、良くも悪くもオセロですから、 寝るのも忘れて遊びたくなるものかと言われるとそういうものではありませんでした。

どうせならもっとエキサイティングでキュートなゲームを実装してみたいものです。 何か良い題材はないものでしょうか。

これまでのあらすじ

オセロを実装し始めて早幾年。 ようやくまともな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

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