December 2016
Intermediate to advanced
440 pages
9h 44m
Japanese
Content preview from アルゴリズムクイックリファレンス 第2版
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
204
■
7
章
AI
における経路探索
図7-5 ミニマックス探索例
7.3.4
分析
各ゲーム状態で固定個数
b
の手があるなら（可能な手の個数が各層で
1
ずつ減ると
しても）、読みの深さが
d
の
ミニマックス
で探索されるゲーム状態の総数は、
O(b
d
)
で、指数的増大を示す。ゲーム木が十分小さくてメモリ内で完全に表現できるなら、
読みの深さに対する制約は取り外せるだろう。
図7-5の結果からわかるように、無用なゲーム状態の探索を止める何らかの方法
があるだろうか。プレイヤーも相手もミスを犯さないと仮定しているので、もしア
ルゴリズムが部分木全体をこれ以上探索する価値がないと判断したら、すぐにゲー
ム木の拡張を停止するような方法を見つけねばならない。後述する
アルファベータ
法
（
AlphaBeta
）がこの機能を適切に実装している。しかし、その前に、ゲーム木の
交互に配置された
MAX
層と
MIN
層を、どのように
ネグマックス
アルゴリズムで単
純化するかを説明しなければな
らない。
7.4
ネグマックス
ネグマックス
＊
1
は、
ミニマックス
の
MIN
と
MAX
という交互の層を、ゲーム木の
各層で同じように使える
1
つの方法に置き換える。これはまた、次に述べる
アルファ
＊1 訳注：NegaMax という呼び名もある。Wikipedia など参照。
7.4
ネグマックス
■
205
A
I
ベータ法
の基盤になる。
ミニマックス
では、ゲーム状態は、常に、最初の手を打ったプレイヤーの観点か
ら評価される（したがって、評価関数はその情報を後で使えるよ
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.