edX ColumbiaXのAI (CSMM.101x) Week4のまとめです。
日本語資料では、下記が参考になりそうです。
ミニマックス法とアルファベータ法
http://www.geocities.jp/m_hiroi/light/pyalgo24.html
Suggest Readings
下記が参照記事としてあげられています。
Adversarial Search(∽game)が今回のテーマです。Adversarial Searchは適切な訳が見つけられませんでした。
ゲームの特徴は我々がコントロールできない相手が存在することで、最適なソリューションは一連の行動ではなく、strategy(policy)となる。
ゲームの種類は、プレイヤーの手が全て見えているかどうか、また運の要素があるかどうかの二軸で、四次元に分けられる。
Perfect Information
Deterministic: Chess, Checkers, Go, Othello
Chance (stochastic): Backgammon, Monopoly
Imperfect Information
Deterministic: Battleships, Blind Tictactoe
Chance (stochastic): Bridge, Poker, Scrabble Nuclear War
AIで主に扱うのは、ゼロサムゲームと呼ばれる、Chess, Checkers, Go, OthelloなどのPerfect Informationが与えられ、Deterministicなゲームである。
Zero-sum Gamesの特徴
* Adversarial: Pure Competition
* Agents have different values on the outcomes
* One agent maximizes one single value, while the other minimizes it
4.2 Minimax algorithm
ミニマックス法の説明が行なわれている。
以下が特徴としてあげられる。
1. DFSである
2. 最適な解は探索木のどの深さでもありうる。
3. 解は最適であり、有限な探索木であれば完全性が保証される
4. 時間計算量は O(b^m), 空間計算量はO(bm)
が、現実的な場面では時間が限られており、全てのリーフの探索はできない。
対応方法のひとつとして「枝刈り」がある。
4.3 Alpha-Beta Pruning (アルファ・ベータ枝刈り)
代表的な方法としてα-β 枝刈りが紹介されている。
Strategy: ミニマックス法と同じく、DFSである。
αは、Maxのなりうる最大値であり、その時点でのMaxの最下限の数値である
βは、Minのなりうる最小値であり、その時点でのMinの最上限の数値である
4.4 Stochastic games
サイコロをなげる、カードをシャッフルするなどランダムな要素のあるゲーム
探索木にChanceノードというノードを追加し、ランダムな要素を組み込む
例：バックギャモン（バックギャモン、日本では一般的なゲームではないので、私としてはわかりにくい例です）
Week 4 Quiz: Adversarial Search and Games
前半は好調でしたが、後半間違いを重ねてしまい、得点はギリギリPassの60%でした。
ミニマックス法とα-β枝刈り法の設問は基本的なものが多かったものの、Utility/Eval functionに関するものや、Expectiminimaxに関する質問は該当の箇所の講義をしっかりと視聴していなかったため、得点できませんでした。
Week 4 Project: Adversarial Search and Games
Week 2と同様にPythonでのコーディングの課題です。やはり分量が多いので、どこかで時間を作ってWeek 2とまとめて取り組んだ方が良さそうですね。
Week 4 Discussion Questions
チェッカーというゲームのChinook(チノーク)というAIについて議論するのが課題になっていますが、グレードの対象外ですので、スキップしました。
日本語資料では、下記が参考になりそうです。
ミニマックス法とアルファベータ法
http://www.geocities.jp/m_hiroi/light/pyalgo24.html
Suggest Readings
下記が参照記事としてあげられています。
Checkers, Solved! http://spectrum.ieee.org/computing/software/checkers-solved
Google's AlphaGo Beat a Go World Champion: https://www.theatlantic.com/technology/archive/2016/03/the-invisible-opponent/475611/
WIRED: Inside Libratus, the Poker AI That Out-Bluffed the Best Humans: http://www.wired.com/2017/02/libratus/
4.1 Adversarial Search and GamesAdversarial Search(∽game)が今回のテーマです。Adversarial Searchは適切な訳が見つけられませんでした。
ゲームの特徴は我々がコントロールできない相手が存在することで、最適なソリューションは一連の行動ではなく、strategy(policy)となる。
ゲームの種類は、プレイヤーの手が全て見えているかどうか、また運の要素があるかどうかの二軸で、四次元に分けられる。
Perfect Information
Deterministic: Chess, Checkers, Go, Othello
Chance (stochastic): Backgammon, Monopoly
Imperfect Information
Deterministic: Battleships, Blind Tictactoe
Chance (stochastic): Bridge, Poker, Scrabble Nuclear War
AIで主に扱うのは、ゼロサムゲームと呼ばれる、Chess, Checkers, Go, OthelloなどのPerfect Informationが与えられ、Deterministicなゲームである。
Zero-sum Gamesの特徴
* Adversarial: Pure Competition
* Agents have different values on the outcomes
* One agent maximizes one single value, while the other minimizes it
4.2 Minimax algorithm
ミニマックス法の説明が行なわれている。
以下が特徴としてあげられる。
1. DFSである
2. 最適な解は探索木のどの深さでもありうる。
3. 解は最適であり、有限な探索木であれば完全性が保証される
4. 時間計算量は O(b^m), 空間計算量はO(bm)
が、現実的な場面では時間が限られており、全てのリーフの探索はできない。
対応方法のひとつとして「枝刈り」がある。
4.3 Alpha-Beta Pruning (アルファ・ベータ枝刈り)
代表的な方法としてα-β 枝刈りが紹介されている。
Strategy: ミニマックス法と同じく、DFSである。
αは、Maxのなりうる最大値であり、その時点でのMaxの最下限の数値である
βは、Minのなりうる最小値であり、その時点でのMinの最上限の数値である
サイコロをなげる、カードをシャッフルするなどランダムな要素のあるゲーム
探索木にChanceノードというノードを追加し、ランダムな要素を組み込む
例：バックギャモン（バックギャモン、日本では一般的なゲームではないので、私としてはわかりにくい例です）
Week 4 Quiz: Adversarial Search and Games
前半は好調でしたが、後半間違いを重ねてしまい、得点はギリギリPassの60%でした。
ミニマックス法とα-β枝刈り法の設問は基本的なものが多かったものの、Utility/Eval functionに関するものや、Expectiminimaxに関する質問は該当の箇所の講義をしっかりと視聴していなかったため、得点できませんでした。
Week 4 Project: Adversarial Search and Games
Week 2と同様にPythonでのコーディングの課題です。やはり分量が多いので、どこかで時間を作ってWeek 2とまとめて取り組んだ方が良さそうですね。
Week 4 Discussion Questions
チェッカーというゲームのChinook(チノーク)というAIについて議論するのが課題になっていますが、グレードの対象外ですので、スキップしました。
