Blokus

Blokusというゲームと、そのAIを実装したい。 と思って2年以上経っても強化学習の勉強があまり進まなかったので、ここで自分なりに目標と必要なことを整理してみます（随時更新）。

Blokusとは

シンプルなルールの陣取りゲームです。 詳細なルールはWikipediaあたりをご参照ください。 いつだかの正月で親戚がちびっこたちと遊ぶために持ってきたのをきっかけに知りました。

最終目標

まずは理想形から考えてみます。

• ログイン制Webアプリとしてゲームを実装
  • ユーザーは対戦ルームを作れる
    • ルームにパスワードを付けることが可能
    • パスワードがない場合はフリー募集となる
  • ルームに4人集まると試合開始できる
  • 4人未満の場合は、CPUを入れることができる
    • CPUの強さ（使用モデル）が選択可能
      • 松：最強AI。人間の対戦履歴を勝手に学習して強くなって欲しい
      • 竹：ランダム×適当なアルゴリズム
      • 梅：完全ランダム

例えば他にも、ユーザーごとに戦績を管理するとか、部屋の個数を制限するとか、建てた部屋が一定時間で消えるとか、色々な要件が思いつきます。 人間の対戦履歴が松モデルの強さに寄与できるほどの量集まらない、みたいなことは気にしませんが、竹より強い松AIが爆誕してくれることを願っています。

計画？？

上記の理想形を直接実装できる能力はないので、手戻りの発生を気にせずその場でできることを進めます。 あまり難しいことは後回しにして、とりあえずアプリとして触れるものを作りたいところです。 計画としてはざっくりこういう感じでしょうか。

• APIを叩くことで駒を配置する＝盤面を更新するシステムの作成
• ゲームマスターの実装
  • 叩かれたAPIに対して合法手判定
    • 少しでも時短のためAIからの行動はそのまま合法判定
  • ターン進行
• AI向けの合法手洗い出しシステム
  • N手目時点での合法手と盤面の差分からN+1手目での合法手を計算したい
  • 駒と盤面の畳み込みで都度洗い出しだと重いが、比較用に作ってみてもいい

使用言語は以下のような想定です。Rust勉強したいので、Rust中心で作ってみたいところ。

• AIプレイヤーの実装: Python
• フロントエンド的なところ: JavaScript？
• 棋譜管理: ？？？
• 他: 可能な限りRust

経験からの課題

過去に「強化学習プレイヤー1人VSランダムプレイヤー3人」というプログラムをローカル環境のPythonのみで作ろうとしたことがありました。 当時を思い出すと、以下の課題があったように思われます。

• 合法手を洗い出すのに時間が掛かった
  • 人間が遊ぶときは気にする必要がない程度だった
  • scipyの2次元畳み込みを利用して、盤面と駒を畳み込んだ結果から合法手を計算していた
  • 駒とその回転全てに対して盤面との畳み込みを繰り返すため駒の数に比例して重くなった
  • 盤面差分を見ることで解決？？
• 強化学習自体が猛烈に重かった
  • 膨大なメモリを占めていた
  • 恐らく素人実装のため
  • 強化学習をスクラッチ実装する前提なら言語を変えれば改善の可能性？？