###### tags: `opendev`
# 探索

[三目並べ](
https://www.google.com/search?rlz=1C5CHFA_enJP937JP937&sxsrf=ALeKk02X2cgbcbFcUhljBo6sMnCVJvoY9g:1617523359597&q=%E4%B8%89%E7%9B%AE%E4%B8%A6%E3%81%B9&spell=1&sa=X&ved=2ahUKEwjkxY6KkOTvAhVRZt4KHfV7AyIQBSgAegQIARA1&biw=842&bih=881)を以下の方法で実装する。

## ゲーム理論

数理的に行動原理を研究する理論。

複数のプレイヤーが、自分の利益が最大となることを目的として、相手の行動を予測しながら自分の行動を決めていく。

社会ゲーム(social game)

室内ゲーム(domestic game)

## ゲームの分類

**何人で行うか？**
- 一人
- 多人数

**プレイヤー同士で利益を奪い合うか？**

一方のプレイヤーの利益が、常に他方のプレイヤーの損失(マイナスの利益)になるとき、零和ゲーム(zero-sum game)という。

- 零和
- 非零和

**プレイヤーは協力するか？**
- 協力
- 非協力

**情報は公開されるか(相手の手はわかるか)？**
- 完全情報
- 不完全情報

**偶然に左右されるか？**
- 確定
- 不確定

**手を同時に出すか交互に出すか？**
- 同時進行
- 交互進行

**出す手は、対称か非対称か？**

じゃんけんの場合、出す手が対照。

- 対称
- 非対称

**ゲームは有限か無限か？**
- 有限
- 無限

**手は狭まるか狭まらないか？**
チェスは、取られた駒を使えない(収束していく)。将棋は取られた駒を使える(収束しない)。
- 収束
- 非収束

|ゲーム|人数|零和|情報|確定|着手|有限|協力|進行|収束|
|:----|:----|:----|:----|:----|:----|:----|:----|:----|:----|
|チェス|二人|零和|完全情報|確定|非対称|有限|非協力|交互進行|収束|
|オセロ|二人|零和|完全情報|確定|非対称|有限|非協力|交互進行|収束|
|将棋|二人|零和|完全情報|確定|非対称|有限|非協力|交互進行|非収束|
|ポーカー|多人数|零和|不完全情報|不確定|非対称|有限|非協力|交互進行|収束|
|じゃんけん|二人|零和|完全情報|確定|対称|有限|非協力|同時進行|非収束|
|ルーレット|多人数|非零和|不完全情報|不確定|対称|有限|非協力|同時進行|非収束|

### 二人零和有限確定完全情報ゲーム

三目並べは、**二人零和有限確定完全情報ゲーム**

**二人**：プレイヤーの数が二人
**零和（ゼロ和）**：プレイヤー間の利害が完全に対立し、一方のプレイヤーが利得を得ると、それと同量の害が生じる
**有限**：ゲームが必ず有限の手番で終了する
**確定**：サイコロのようなランダムな要素が存在しない
**完全情報**：全ての情報が両方のプレイヤーに公開されている

チェス・囲碁・将棋・オセロなど

## ゲーム木の探索

### 完全ゲーム木と部分ゲーム木

ゲームの最初から指せる全ての手を含んだゲーム木を**完全ゲーム木**

現在の盤面から指せる手を時間内に探索できるぶんだけ含んだゲーム木を**部分ゲーム木**という。

↓三目並べの最初の2手のゲーム木

## ミニマックス法

自分にとって最も有利な手(max)
相手が自分にとって最も不利な手(min)

先手・後手の双方が互いに最善を尽くすと仮定し、自分にとって最も有利になるように手を選ぶ手法。

後手の勝ちを－１、先手の勝ちを＋１、引き分けを０とおいて、読む深さを無限にすれば結果が必ず得られる。

### 計算量

$b^d$

$b$ : １手あたりの枝分かれの数(branch factor)
$d$ : 読みの深さ(depth)

実装：
https://colab.research.google.com/drive/1-1sW2-D_wJma6rqK1Gtmm2nyn9e6m47o?usp=sharing

## アルファベータ法

ミニマックス法の改良アルゴリズム。


### 計算量
もっとも効率が良い計算量は、 $b^\frac{d}{2}$

実装：
https://colab.research.google.com/drive/1BHmMKkc4i6IAn1HwtyyO0BByrffuYJgA?usp=sharing

## 選択

## $ε$-greedy 法

0以上1以下の確率 $ε$ でランダムに行動を選択し、確率 $1-ε$ で期待報酬が最大となる行動を選択する手法

## UCB-1(Upper Confidence Bound 1)

成功率+バイアスを最大化する行動を選択する手法。

$UCB1 = \displaystyle \frac{w}{n}+(\frac{2log(t)}{n})^\frac{1}{2}$

$n$ : 行動の試行回数
$w$ : 行動の成功回数
$t$ : 行動の試行回数の合計