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

オセロのページ

更新情報

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

CPU のレベルについて

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

レベル１〜３は、シンプルなオセロのCPUです。 レベル４〜６は、モンテカルロ木探索を用いたCPUです。各プレイアウトにレベル１のCPUを使います。 レベル７〜１０は、モンテカルロ木探索を用いたCPUです。各プレイアウトにレベル３のCPUを使います。

CPU同士の自己対戦

各レベルは、下のレベルに対して勝率60%程度となります。 CPU同士の自己対戦によってCPUの強さを評価することができます。

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

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

CPU の n について

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

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

ということになります。

より具体的な解説

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

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

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

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

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

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

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

このオセロを作った経緯

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

モンテカルロ木探索 - Wikipedia

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

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

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

そして今後

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

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

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

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

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

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