この「オセロのページ」の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(レベル１)を用いたモンテカルロ木探索（ `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の強さに関するアンケートは締め切りしました！多数の回答ありがとうございました

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

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

ということになります。

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

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

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

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

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

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

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

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

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

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

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

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

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

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