OUCRC最強オセロAI決定戦@学祭 の報告

OUCRC最強オセロAI決定戦@学祭の報告

執筆者: 終に鮭

最終更新: 2022/12/15

2022年11月5日、2022年11月6日――岡山大学祭が3年ぶりにオンサイト開催されたこの日、電子計算機研究会は一般教育棟A37講義室を借りて展示をしていた。
ゲームが多数展示される中、1つ異質な存在があった。AI vs AI オセロ対決 のディスプレイである。

7月末に発足したこのプロジェクトは、以下のように進んだ。

8月上旬　主犯はゲームを決定するための投票をする。クソデカオセロ（盤面20x20のオセロ、原作）に決定。
8月中旬　主犯はターン制ゲーム用のサーバ（Go, MQTT）を途中まで作っていたが放棄する。
9月下旬　プロジェクトが再始動する。
10月上旬　主犯はモックサーバ（Go, HTTP）の作成を開始する。OpenAPI で仕様書を書いて OpenAPI Generator で自動コード生成したかったらしい（文言からわかるように、頓挫している。理由は仕様を決めかね続けてエターナったため）。
10月中旬　主犯はオキリョウ氏にサーバ（Kotlin, HTTP）作成を依頼する。まっともぉん氏はUnityでディスプレイ用アプリの作成を開始する。まっともぉん氏はAIを完成させ、アプリに内蔵する。
10月下旬　主犯はオセロゲームの作成を開始する。オキリョウ氏はサーバとAIを完成させる。
10月28日　ゲーム内容を通常の8x8のオセロに変更。
11月4日　学祭前日。みんなでデスマーチ :smiling_face:。
11月5日　学祭1日目。未明、主犯はモデルの学習プログラムを完成させ、学習を開始する。明け方、Pon氏はAIを完成させる。1日目展示開始時点で完成していたAIは3つであった。
11月6日　学祭2日目。午前12:03、主犯は通信プログラムを完成させ、AIを使える状態にする。2日目展示開始から数分後にセットアップし、無事4つのAIが対戦した。

ガバガバっぷりが酷い。スケジュールをもう少しきちんとして欲しい。9月の空白の区間は何だったのか。しかももともとこのプロジェクトの参加予定者は4人より多かった。

AIについての作者コメント

AI作者の4名からコメントを頂きました。

まっともぉん（MatsuBot）

仕組み

1. 配置可能な場所をリスト化にする
2. リストの値をランダムに1つ取得する
3. 配置する
ランダム配置 AI BOTです。
時間に余裕あれば開放度理論とマス目自体の重みで判定する簡単なアルゴリズムを組もうとはしてた…

感想

ランダムAIもなんだかんだ勝率良かったのが一番驚愕でした（本当は「時間かけて作ったAIがランダムBOTに負けてる乙ｗｗｗ」って全力で煽りたかったけど、みんな徹夜して作成してたので流石に言えなかった。~~余裕もって作れ！！とは思うけど~~）
対戦・表示する仕組みがせっかく整ったので、AI持ち寄って戦わせる企画を部で相続するのはありかも？プログラミング・AI・通信について学べるし何はともあれお疲れ様どす

確かにプログラミングの重要な要素を色々カバーできてるし、勉強会の材料としてよさそう。~~ソースをオープンにしてくれ。~~ なりました

オキリョウ（Hoge）

仕組み

1. 定石（https://bassy84.net/othello-top-index.html）うさぎと虎と牛のうち、主要なものを入力
2. 開放度理論（https://kozu-osaka.jp/cms/wp-content/uploads/2020/11/077c2ec004566f2968e2f3089333ede7.pdf）を元に、数手先（大体4手くらい）を読んで（自分の開放度 - 相手の開放度）の合計が最も小さくなるような手を打つ
3. 全探索（残り11手）

感想

ガキの時にC#でオセロAIを作ったことがあったがクソ雑魚だった
それから一回り成長したことを実感できてよかった

成績としては自分だけ無双している
勝てる分には嬉しいが、もう少しいい勝負してほしかった
せめて他のBotにはランダムBotくらいボコボコにして欲しかった・・・

コードはこちら：　https://github.com/Wansuko-cmd/reverse-app

ごめん。みんな乱択ベースだから許して。

Pon（Pon）

仕組み

1. 配置可能な場所とその時めくれる石数をリスト化する
2. そのリストを「めくれる石数」の降順でソートする
3. そのリストの「めくれる石数」が同じものを一定確率で入れ替える．
4. そのリストの上位log_2(残りのターン数)個の中からランダムに一つ選ぶ．
5. 選んだものの場所へ配置する．

感想

他のAIに勝てるか自信があまりなかったがまさかランダムAIに引き分けるとは思わなかった．正直めっちゃ悔しい！めくれる，めくられる石数を数手先まで重み付きで読んでみればまた結果は変わったかもしれない．（ワンチャン時間あったら作るかも）
通信関連について勉強することになったのは意外だったが，結構いい勉強になった．他にもpythonのファイル分割などの（個人の実装で）初めて試したことやプログラムの作り方における反省点（最初クソデカ関数作ってしまった）とかが分かったので良い経験になったと思っている．とりあえず次にこのような機会があった時にAIで勝てるよう勉強頑張ります．
お疲れさまでした！

序盤取りすぎないというロジックを乱択で組むのは面白い。Pythonについてはパッケージ管理ツールを使うと便利なので今度教える（今回は NumPy と Requests ぐらいだったので困らなかったが）。

終に鮭（Salmon）

仕組み

畳み込みニューラルネットワーク（転置畳み込みを含むのでそう言っていいかは分からない）で盤面から状態行動価値関数を計算するように作った。
所謂 Deep Q Learning（DQN）のようなものだが、一般的な手法として存在を知っていたわけではなく、足りていない部分が多いと思う。

層は以下の構成だが、振り返るとあまり良さそうではない。オセロにおいて辺や角に置かれている駒は極めて重要なので、畳み込みより全結合のほうが良かったかもしれない。

Salmon AI の CNN の構成

図1: Salmon AI の CNN の構成

学習においては、自身と対戦を行い、各試合の勝敗に応じて各対戦者の指した手に良いか悪いかを割り当てて教師ベクトルとする。
これを100回行うごとにミニバッチ学習をする。

感想

ニューラルネットワーク歴3週間ほどである上、よく使われる構成も知らないため適当に組んだ。これより前には MNIST しか組んでいない。
そもそもQ学習だと思っていない。クラス分類問題のつもりで作った（その割に運用時は argmax ではなく softmax を使っているが）。
とりあえず今思いついている改善点は、
- 全層 fc にする（下手に畳み込みしない）
- 負けたときの手を学習データに含めないようにし、損失関数を CrossEntropy にする
の2つ。

追伸：v2 では全層全結合にした。モデルの state_dict は36KB→100KB超に増えた。
他のAIに対しての勝率は良いとは言えないが、ひとまず v1 には勝てるようになったので良かったかなと。

結果報告

さて、最強決定戦なのにインメモリデータベースに保存しており最早学祭時の対戦データが残っていない本企画である。
オキリョウ氏の協力を頂き、データベースを PostgreSQL に置き換え、再現して実行した。

ルームデータの保存形式（psqlでSELECTしている画面）

図2: ルームデータの保存形式（psqlでSELECTしている画面）

結果を Python で適当に加工し、JSON に変換して保存し直した。

# jq '{ users, results: [.results[0]] }' results.json
{
  "users": {
    "d34a33b0-b29a-4daa-8682-1604bcc4dbf6": "Pon",
    "053b45b6-c029-4b19-9f62-f5d366a9a89e": "MatsuBot",
    "99cb0ee1-f56b-46bf-8d91-6bae860603bd": "Salmon",
    "f751d4ad-cebd-4f9e-be2b-01d9ca8d34f5": "Hoge"
  },
  "results": [
    {
      "black": "99cb0ee1-f56b-46bf-8d91-6bae860603bd",
      "white": "d34a33b0-b29a-4daa-8682-1604bcc4dbf6",
      "board": "2,1,1,2,2,2,2,2|2,2,1,2,2,2,2,1|2,2,1,2,2,2,2,1|2,2,1,1,1,2,2,2|2,1,1,2,2,1,2,2|2,1,2,2,1,2,2,2|2,2,1,1,1,1,2,2|2,2,1,1,1,1,1,2"
    }
  ]
}