リバーシ
完全情報ゲームの一つ。(厳密にはルールの既定はあるが)日本ではオセロの名前で知られる。
アップロードしたプログラムについて
概略
CPU対戦ができるリバーシプログラム。2000年台に囲碁AIを大きく進化させたUCTアルゴリズムを搭載。リバーシAIは世界チャンピオンを負かすレベルだけれども、このプログラムは今のところ全然勝てるレベル(Play-out時の方策が単なるランダム選択だからか、それともバグかいまいち不明。。一応UCB1アルゴリズムには勝ち越せていることは確認済み)。
詳細
- アルゴリズム
モンテカルロ木探索のUCTアルゴリズムを採用。理論的なところは全く追ってません(ぉぃ
まぁ簡単に言うとある方策(ランダム)で石を打っていって得た報酬(勝率)をもとに現在の手の良さを決めるっていう処理を繰り返して手を決める「モンテカルロ探査」がベース。UCTアルゴリズムでは、その際、ある程度探索してこの手は良さそうと思ったら、その1手先の良さも決めるっていうことをやる(その際、もとの手自体はミニマックス探索する)。このアルゴリズムは、回数を稼げば最終的に通常のゲーム木探索の結果に収束する。ちなみに、どこの手から打ち始めるか?というと、UCB1という基準を用いる。この基準は、今までに得た報酬(の平均)と、どのくらい探索したことがないかを考慮する。今のところ事前知識はなく勝てば1、引き分けか負けならば0という報酬を与えるだけ。行動選択もランダムという感じ。
まぁ簡単に言うとある方策(ランダム)で石を打っていって得た報酬(勝率)をもとに現在の手の良さを決めるっていう処理を繰り返して手を決める「モンテカルロ探査」がベース。UCTアルゴリズムでは、その際、ある程度探索してこの手は良さそうと思ったら、その1手先の良さも決めるっていうことをやる(その際、もとの手自体はミニマックス探索する)。このアルゴリズムは、回数を稼げば最終的に通常のゲーム木探索の結果に収束する。ちなみに、どこの手から打ち始めるか?というと、UCB1という基準を用いる。この基準は、今までに得た報酬(の平均)と、どのくらい探索したことがないかを考慮する。今のところ事前知識はなく勝てば1、引き分けか負けならば0という報酬を与えるだけ。行動選択もランダムという感じ。
- 実装
C#4.0の力でマルチコア動作。ただ、C#&実装のショボさが響いてとっても遅い。。
操作方法
石を置くのは「ダブルクリック」です。
勝ち例
負け例