ミニマックス: 基礎と応用

By Fouad Sabry

ミニマックスとは

人工知能、意思決定理論、ゲーム理論、統計学、哲学において、ミニマックスとは、確率的損失を最小限に抑えるために使用される決定ルールです。 最悪のシナリオ。 利益について議論するとき、「最小利益の最大化」を表す「マキシミン」という用語がよく使われるのを聞くことがあります。 これは当初、複数のプレーヤーが交互に動作する状況と、同時に動作する状況の両方を含む、複数プレーヤーのゼロサム ゲームの理論のために開発されました。 しかしそれ以来、この機能はより複雑なゲームや、不確実性が存在する場合の一般的な意思決定にまで拡張されました。

どのようなメリットがあるか

(I) 次のトピックに関する洞察と検証:

第 1 章: ミニマックス

第 2 章: ゲーム理論

第 3 章: デシジョン ツリー

第 4 章: アルファ-ベータ プルーニング

第 5 章: エクスペクティミニマックス

第 6 章: 敵対的検索

第 7 章: 評価関数

第 8 章: モンテカルロ木探索

第 9 章: ネガマックス

第 10 章: 人工知能

(II) 一般のよくある質問に答える ミニマックスについて。

(III) 多くの分野でのミニマックスの使用例。

本書の対象者

専門家、大学生、大学院生、愛好家、趣味愛好家、および以下のような人々 あらゆる種類のミニマックスに関する基本的な知識や情報を超えたいと考えています。

人工知能シリーズとは

人工知能の書籍シリーズでは、200 を超えるトピックを包括的にカバーしています。 各電子ブックは、特定の人工知能のトピックを詳しく取り上げており、その分野の専門家によって書かれています。 このシリーズは、読者に人工知能の概念、技術、歴史、応用について徹底的に理解してもらうことを目的としています。 取り上げられるトピックには、機械学習、深層学習、ニューラル ネットワーク、コンピューター ビジョン、自然言語処理、ロボット工学、倫理などが含まれます。 電子ブックは、専門家、学生、およびこの急速に進歩する分野の最新の開発について学ぶことに興味があるすべての人を対象に書かれています。
人工知能の書籍シリーズは、基本的な概念から最先端の研究まで、詳細でありながら親しみやすい探求を提供します。 200 冊を超える書籍により、読者は人工知能のあらゆる側面について徹底的な基礎を身につけることができます。 電子ブックは体系的に知識を構築できるように設計されており、後の巻は以前の巻で築いた基礎の上に構築されます。 この包括的なシリーズは、人工知能の専門知識を開発しようとする人にとって不可欠なリソースです。

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: Jun 29, 2023

Book preview

第1章:ミニマックス

Minmaxは、人工知能、決定理論、ゲーム理論、統計、哲学で使用される決定ルールであり、最悪の場合(最大損失)シナリオで予想される損失を減らすことを目的としています。Minmaxは、特定のコンテキストではミニマックスまたはMMとも呼ばれます。利益について議論するとき、「最小の利益を最大化する」を表す「マキシミン」という言葉をよく耳にするかもしれません。当初は、複数のプレイヤーがゼロサムゲームの理論のために開発され、プレイヤーが交互に動き、同時に動きをする場合の両方をカバーしていました。しかし、それ以来、それはより複雑なゲームだけでなく、不確実性の存在下での一般的な意思決定にも拡張されています。

最大値は、プレイヤーが他のプレイヤーの行動を知らなくても取得することが保証される最大値です。反対の意味では、他のプレイヤーがプレイヤーの行動を知っているときにプレイヤーに取得を強制できる最低値です。それの学術的な定義は次のとおりです。

{\underline {v_{i}}}=\max _{a_{i}}\min _{a_{-i}}{v_{i}(a_{i},a_{-i})}

どこ：

i は関心のあるプレーヤーのインデックスです。

-i は、プレイヤー I を除く他のすべてのプレイヤーを示します。

a_{i} はプレイヤー I が実行したアクションです。

a_{{-i}} 他のすべてのプレイヤーが実行したアクションを示します。

v_{i} はプレイヤー i の値関数です。

プレイヤーの最大値は、最悪のシナリオ手法を使用して計算されます。これは、プレイヤーの考えられる各アクションについて、他のプレイヤーのすべての可能なアクションを調べ、プレイヤーIに可能な限り低い値を与える一連のアクションを特定することを意味します。次に行うことは、この最小値が達成可能な最大値であることを保証するために、私ができるアクションプレーヤーを理解することです。

例として、2人のプレイヤーのための次のゲームを考えてみましょう。「行プレーヤー」と呼ばれる最初のプレーヤーは、T、M、またはBの3つの動きのいずれかを選択できます。「コラムプレーヤー」と呼ばれる2番目のプレーヤーには、LまたはRのいずれかを選択するオプションがあります。ペイアウトテーブルは、両方の動きがプレイされた後のゲームの結果を示します。

{\displaystyle {\begin{array}{c|cc}\hline &L&R\\\hline T&3,1&2,-20\\M&5,0&-10,1\\B&-100,2&4,4\\\hline \end{array}}}

(各セルの最初の数字は、行をプレイしたプレイヤーのペイアウトを示し、2番目の数字は、列をプレイしたプレイヤーのペイアウトを示します)。

この図のために、純粋な戦術のみを見ていきます。各プレイヤーのチェックを順番に実行します。

行のプレーヤーはTをプレイすることができます、これは彼らが少なくとも2の支払いを受け取ることを保証します(Bをプレイすることは100未満の報酬をもたらすかもしれないので危険です)、あなたが勝った場合、Mをプレイすることは10ドルの報酬をもたらすかもしれません。

したがって: {\underline {v_{row}}}=2 .

コラムプレーヤーはLをプレイし、少なくとも0のペイオフを確保 できます(Rをプレイすると、取得するリスクがあります {\displaystyle -20} )。

したがって: {\underline {v_{col}}}=0 .

両方のプレイヤーがそれぞれのマキシミン戦略をプレイする場合 {\displaystyle (T,L)} 、ペイオフベクトルは (3,1) です。

プレイヤーのミニマックス値は、プレイヤーが他のプレイヤーの行動を知っている間に獲得できることが保証される最大の値です。あるいは、プレイヤーの行動を知らなくても、他のプレイヤーがプレイヤーに取得を強制できる最小値です。それの学術的な定義は次のとおりです。

{\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}

定義は最大値の定義と非常によく似ていますが、最大演算子と最小演算子の順序が入れ替わる点が異なります。前の図では、次のようになっています。

行をプレイするプレイヤーは、4(他のプレイヤーがRをプレイする場合)または5(他のプレイヤーがLをプレイする場合)のいずれかの最大値を取得する可能性があるため、次のようになります。 {\displaystyle {\overline {v_{row}}}=4\ .}

列プレーヤーが達成できる最大値は1です。(他のプレイヤーがTをプレイする場合)、1(Mの場合)または4(Bの場合)。

従って： {\displaystyle {\overline {v_{col}}}=1\ .}

マキシミンは、1人のプレーヤーiのミニマックスを超えることはできません。

\underline{v_i} \leq \overline{v_i}

直感的には、最大化では、最大化は最小化の後に来るので、プレイヤーIは他の人が何をするかを知る前に彼らの価値を最大化しようとします。Minimaxでは、最大化は最小化の前に来るので、プレイヤーIははるかに良い立場にあります–彼らは他の人が何をしたかを知って彼らの価値を最大化します。どちらの場合も、最小化が最初に行われます。

表記を右から左に読むことは、それを理解するために使用できるさらに別の方法です。 私たちが書いている間

{\displaystyle {\overline {v_{i}}}=\min _{a_{-i}}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}=\min _{a_{-i}}{\Big (}\max _{a_{i}}{v_{i}(a_{i},a_{-i})}{\Big )}}

結果の最初のセットは {\displaystyle \ v_{i}(a_{i},a_{-i})\ } 両方に依存し、 {\displaystyle \ {a_{i}}\ } 私たちは最初に {\displaystyle \ {a_{-i}}\ .} 、(のすべての可能な値に対して {\displaystyle {a_{i}}} )最大化することによって、から離れて疎外 {\displaystyle v_{i}(a_{i},a_{-i})} し、 のみ {\displaystyle \ {a_{i}}\ } に依存する {\displaystyle {a_{-i}}} 一連の限界結果を生成します 次に、 {\displaystyle \ v'_{i}(a_{-i})\,,} これらの結果を {\displaystyle \ {a_{-i}}\ .} 最小化 {\displaystyle \ {a_{-i}}\ } します。

(マキシミンの場合は逆です。

両方のプレイヤーがミニマックス戦略をプレイした結果のペイ