ゲームの状態
ゲームはプレイヤーの意思決定によって状態が変化していきます。ゲームの最初の状態を初期状態として、そこから様々な状態に遷移し、目標状態（勝敗がついた状態）になります。
ゲーム木
ゲームの状態遷移を図形化した場合、初期状態（根）から目標状態（葉）に広がるため、ゲーム木とよばれます。
すべての状態をゲーム木に表した場合（完全ゲーム木）、その状態すべてを数えると総状態数（総局面数）がわかります。
弱解決のために、初期局面からの先手の完璧な意思決定のみで構成されるゲーム木を生成することもあります。（証明木）
情報量
総状態数が多いゲームはそれだけ情報量の多いゲームとわかります。総状態数は平均合法手数がM手のゲームにおいて、平均終了手数がN手の場合、N×N×…N＝NのM乗で概算できます。（かなり雑）
| ゲーム | 総局面数 | 解決状態 |
|---|---|---|
| 三目並べ | 765・26830 | 強解決 |
| どうぶつしょうぎ | 246, 803, 167 | 強解決 |
| チェッカー | 約1020 | 弱解決 |
| リバーシ | 約1028 | 未解決 |
| チェス | 約1047 | 未解決 |
| 将棋 | 約1070 | 未解決 |
| 囲碁 | 約10170 | 未解決 |
上の図はゲームの総状態数です。総状態数は盤面の対称性を考慮（正規化）したり、遷移可能局面のみを計算するなどで、減らして数える場合もあり、数え方によって総数に差がでます。
参考
ゲーム情報学概論 - ゲームを切り拓く人工知能 - | コロナ社
ゲームは，古くから人工知能，認知科学の中心的な研究テーマとして扱われてきた。本書では，まずこの研究分野の基礎的な知識と歴史を押さえ，それを支える重要な理論について述べ，デジタルゲームの応用分野まで概観する。
www.coronasha.co.jp
ゲーム木 - Wikipedia
ja.wikipedia.org
コメント