PythonによるAIプログラミング入門 ―ディープラーニングを始める前に身につけておくべき15の基礎技術

9章人工知能を使ったゲーム

本章では人工知能を使ったゲームの作り方を説明します。ゲームに勝つための戦略を効率よく立てる探索アルゴリズムの使い方を学び、それを使って、いくつかのゲームの知的な対戦相手（ボット）を作ります。

本章では次の事柄について学びます。

• 探索アルゴリズムのゲーム応用
• 組み合わせ探索
• ミニマックス法
• アルファ・ベータ法
• ネガマックス法
• コイン取りゲーム
• 三目並べ
• 『Connect Four』
• 『Hexapawn』

9.1　探索アルゴリズムのゲーム応用

ゲームの戦略を立てるためには、探索アルゴリズムが使われます。探索アルゴリズムを使って、多数の可能性の中から最良の次の1手を探すのです。考慮すべきパラメータは、スピード、正確さ、複雑さなどさまざまあります。探索アルゴリズムは、その時点で可能なすべての指し手を考慮し、その中から未来の一連の指し手を評価します。ゲームによって勝敗条件は異なりますが、探索アルゴリズムの目標は、最終的な勝敗条件に到達する（すなわちゲームに勝つ）ために資する最適な一連の指し手を見つけることです。

ただし、以上の説明は、対戦相手がいない場合における理想論にすぎません。現実のゲームでは、複数のプレイヤーが参加するので、これほど単純ではありません。2人対戦のゲームを考えてみます。プレイヤーが1手指すたびに、相手プレイヤーはゴール達成を妨げるような手を指してくるでしょう。したがって、探索アルゴリズムが現在の状態から最善手を見つけても、相手がそれを阻止するので、そのとおりに進めることはできません。つまり、探索アルゴリズムは、1手指すたびに常に局面を評価し直さなければならないのです。

そこで、コンピュータにゲームの状況を把握させる方法を検討します。ここでは、ゲームを探索木だと考えます。ゲーム木の各ノードは、未来の状態を表します。例えば、 ...