体験プロジェクト例

2048

2048の思考プログラムを作ってみよう。(発展)世界記録の794076を塗り替えよう。

リアルタイムの意思決定

ぷよぷよで5連鎖を打てるプログラムを書いてみよう。(発展)日本記録を作ろう(たぶん20連鎖以上)

囲碁とモンテカルロ木探索

オープンソースライブラリのlibegoの囲碁盤機能を使って、現在のコンピュータ囲碁プログラムの思考の要であるUCTの部分を自作してみよう。プレイアウト部分はboard.RandomLightMove(random);を使うと便利。原始モンテカルロ法より強くなることを確認する。
(発展) コンピュータ囲碁で一般的なプロトコルであるgtpの一部分(数個のコマンド)を実装して、goguiと接続して、人間や他のプログラムと対局できるようにする。RAVEを実装してみる。
参考図書: コンピュータ囲碁 モンテカルロ法の理論と実践

グラフとA*探索

最短路問題などを解くために、幅優先探索、ダイクストラ法、A*探索を実装して性能を評価しよう。たとえば、4×4あるいは5×5のスライドパズルを解いてみよう。マンハッタン距離などヒューリスティックの効果を確認する。
(発展)disjoint pattern database (Korf 2002)を使ってさらなる性能向上を確認する。
参考図書: エージェントアプローチ人工知能 4章

多数決サーバとネットワーク/分散プログラミング

コンピュータ将棋のプロトコルであるUSIで将棋プログラム(たとえばgpsfish)を制御して、多数決で次の一手を決めるサーバプログラムを作成してみよう。多数決であればperlなどスクリプト言語で十分だが、GPS将棋が行うような本格的な分散探索機能の追加を視野にいれる場合はBoost.asio で作ると良い。

ゲームと学習

  • 指手の確率の学習: 囲碁や将棋で、棋譜の指手を模倣するようなモデルを、最大エントロピー法やsoftmaxモデルなどで作成してみよう。予測精度を文献と比較したり、用いる棋譜との関係を検討する。
    参考資料例: Computing Elo Ratings of Move Patterns in the Game of Go
  • 評価関数の学習1: オセロの評価関数を探索結果を教師として最小二乗法で作成する。Logistelloの特徴(feature)を使うと次元が100万程度まで大きくなるので、共益勾配法などを用いて効率よく計算する。
  • 評価関数の学習2: Temporal Differenceと呼ばれる強化学習を行って、将棋の駒の強さなどを、対局から学ぶプログラムを作成する。
  • 評価関数の学習3: Comparison Training (あるいはBonanza学習)の一部分を実装して、将棋の評価関数を学習させる。矢倉囲い、美濃囲いなどに組めることが目標。

@東京大学駒場Iキャンパス