この「オセロのページ」のCPUについて

オセロのページ

更新情報

  • 2021/09/20 構成をリニューアル
  • 2021/08/30 レベル10を追加するためにやったことを書きました。
    • レベル10(n=50000) を新しく追加しました。自己対戦でレベル9にはほぼ勝ちますが、どのくらい強いかはわからないです。
    • CPUの演算部分を全体的に高速化しました(ビットボードに変えました)。そのおかげで↑が追加できました。
    • モンテカルロ木探索でのプログラム上のミスがあったので、修正しました。レベル4〜レベル9で多少の強さの変動があるかもしません。
  • 2021/08/23 レベル4以上のモンテカルロ木探索CPUに関して、CPUの予想勝率を出すようにしました(評価値はわかりにくかったので)。
  • 2021/08/16
    • 先日、URLを https://www.zawawahoge.com/game/othello/ に移した影響で、クリア済みの記録が消えてしまったかもしれないです。ごめんなさい。
      • CPUの強さ自体は変更ありません。
    • CPUのレベル6の nn'=1000 となっていましたが、正しくは n=3000 の誤りだったので修正しました。
    • 対戦終了後、自動でトップに戻るのをやめて、対局終了画面のまま止まるようにしました。
    • CPU の情報を下記に追加しました。

CPU のレベルについて

レベル 強さ(作者の主観) 説明
ルール覚えてたら勝てるはず! 置ける場所にランダムに置きます
隅を取れれば勝てる 相手の置ける場所を少なくするように置く
露骨なミスをしなければ勝てる 各コマに評価値を事前に割り振ってその合計が大きくなるように置く
これはまだ弱いモンカル CPU(レベル1)を用いたモンテカルロ木探索( n = 100)
適当に打つと勝てないモンカル CPU(レベル1)を用いたモンテカルロ木探索( n = 1000)
ワイはたまに負ける CPU(レベル1)を用いたモンテカルロ木探索( n = 3000)
ワイはほぼ勝てない CPU(レベル3)を用いたモンテカルロ木探索( n = 3000)
結構つよい。がんばって CPU(レベル3)を用いたモンテカルロ木探索( n = 6000)
つよい。猛者は挑戦求む CPU(レベル3)を用いたモンテカルロ木探索( n = 10000)
10 つよい。猛者は挑戦求む CPU(レベル3)を用いたモンテカルロ木探索( n = 50000)

レベル1〜3は、シンプルなオセロのCPUです。
レベル4〜6は、モンテカルロ木探索を用いたCPUです。各プレイアウトにレベル1のCPUを使います。
レベル7〜10は、モンテカルロ木探索を用いたCPUです。各プレイアウトにレベル3のCPUを使います。




オセロCPUの強さに関するアンケートは締め切りしました!多数の回答ありがとうございました

結果は うちのサイトのオセロCPUの強さってどんなもん? にまとめてあります




CPU の n について

基本的な n の性質をざっくりいうと、

  • n が大きいほど、計算時間が長く、強くなる
  • n が小さいほど、計算時間が短く、弱くなる

ということになります。

より具体的な解説

このCPUは、「モンテカルロ木探索」 という手法で探索をしています。

モンテカルロ木探索は、「モンテカルロアルゴリズム」を効率的したものです。

まず、「モンテカルロアルゴリズム」に関しては、以下のような方法で手を決定します。

  1. CPU の手番になる
  2. CPU が打てる候補手をすべて洗い出す
  3. そのそれぞれに対して、ランダムに手を打つCPU同士が勝敗が付くまでシミュレーションを行います
    (これが一回分の プレイアウト となります)
  4. 各候補手を打った局面を開始局面とするプレイアウトをたくさん行うことで、候補手ごとの勝率を求め、最も高い勝率の候補手をCPUの手とします

この 総プレイアウト回数n という値です。

例えば、レベル4では、一手を出力するために合計して100回のプレイアウトを行っていることになります。

これに加えて、 「モンテカルロ木探索」 では、効率的に起こりそうな展開を選択して、深く読むことができます。

このオセロを作った経緯

2018年頃、Alpha碁に触発されて、モンテカルロ木探索でオセロをするAIを作ってみました。

モンテカルロ木探索 - Wikipedia

四隅を取れたら嬉しいといった、ルール以外のオセロの知識を入れずに、ひたすらランダムプレイアウトを行っているだけにもかかわらず、なかなか手強くなりました(レベル7〜9はちょっと入ってますが)。

終盤に近づくと、一回のプレイアウトをするための手数が短くなるため、思考時間も短くなります。こちらが負けの局面で終盤ノータイムされると少し傷つきます。

レベル8、9について、自分では全く勝てないため、どのくらい強いかが分からないので、強い人は感想を教えてください。

そして今後

前のドメインでこのページを公開してから数年経ちました。

ありがたいことに複数の強い人にプレイしていただき、一番上のレベルを倒した報告を頂いたので、さらに強いバージョンを開発しようかと思ってます。

モンテカルロ木探索でオセロを強くするアイデアとしては、次のようなものがあります。

  • ビッドボードを用いて、シミュレートそのものを高速化して、プレイアウト数を増やす ビットボードに対応し、高速化しました
  • 互いに独立なプレイアウトを並列化して、同時実行する

ツイッターなどでシェアしてもらえるとやる気が出ます。

このエントリーをはてなブックマークに追加