لعبة معادية. حل ألعاب مصفوفة معادية مبادئ حل ألعاب مصفوفة معادية
نظرية اللعبة هي نظرية للنماذج الرياضية لصنع القرار في ظل ظروف الصراع أو عدم اليقين. من المفترض أن تصرفات الأطراف في اللعبة تتميز باستراتيجيات معينة - مجموعات من قواعد العمل. إذا كان مكسب أحد الطرفين يؤدي حتمًا إلى خسارة الجانب الآخر ، فإنهم يتحدثون عن ألعاب عدائية. إذا كانت مجموعة الاستراتيجيات محدودة ، فإن اللعبة تسمى لعبة مصفوفة ويمكن الحصول على الحل بكل بساطة. الحلول التي تم الحصول عليها بمساعدة نظرية اللعبة مفيدة في وضع الخطط في مواجهة معارضة محتملة من المنافسين أو عدم اليقين في البيئة الخارجية.
إذا كانت لعبة bimatrix معادية ، فسيتم تحديد مصفوفة المكافآت للاعب 2 بالكامل من خلال مصفوفة المكافآت للاعب 1 (تختلف العناصر المقابلة لهاتين المصفوفتين فقط في العلامات). لذلك ، يتم وصف لعبة معادية ثنائية المصفوفة بالكامل بواسطة مصفوفة واحدة (مصفوفة المكافآت للاعب 1) ، وبالتالي تسمى لعبة المصفوفة.
هذه اللعبة عدائية. فيه j \ u003d x2 - O ، P ، و R (O ، O] \ u003d H (P ، P) \ u003d -I و R (O ، P) \ u003d R (P ، O) \ u003d 1 ، أو في شكل مصفوفة o p
دع فئة من الألعاب تكون "مغلقة المرآة" ، أي مع كل لعبة من ألعابها تحتوي على لعبة متشابهة مرآة (نظرًا لأن جميع الألعاب التي تكون متشابهة بالنسبة إلى لعبة معينة متشابهة مع بعضها البعض ، يمكننا ، وفقًا لما قيل للتو ، التحدث عن لعبة متشابهة مرآة واحدة). هذه الفئة ، على سبيل المثال ، هي فئة جميع الألعاب العدائية أو فئة جميع ألعاب المصفوفة.
بالتذكير بتعريف المواقف المقبولة في اللعبة العدائية ، نحصل على أن الوضع (X ، Y) في الامتداد المختلط للعبة المصفوفة مقبول للاعب 1 إذا وفقط إذا كان لأي x G x عدم المساواة
تسمى عملية تحويل الألعاب إلى ألعاب متماثلة التناظر. نصف هنا طريقة واحدة للتناظر. سيتم تقديم نسخة أخرى مختلفة اختلافًا جذريًا من التناظر في القسم 26.7. كلا النوعين المتغيرين من التناظر ينطبقان في الواقع على ألعاب معادية عشوائية ، ولكن سيتم صياغتهما وإثباتهما فقط لألعاب المصفوفة.
وبالتالي ، فإن المصطلحات والتسميات الأولية لنظرية الألعاب المتضاربة العامة تتوافق مع المصطلحات والتسميات المقابلة لنظرية ألعاب المصفوفة.
بالنسبة لألعاب المصفوفة العدائية المحدودة ، فقد تم إثبات وجود هذه القيم القصوى من قبلنا في الفصل 10. 1 ، وكان بيت القصيد هو إثبات مساواتهم ، أو على الأقل إيجاد طرق للتغلب على عدم المساواة بينهم.
يُظهر التفكير في ألعاب المصفوفة بالفعل أن هناك ألعابًا معادية بدون حالات توازن (وحتى بدون حالات توازن إلكتروني لـ e> 0 صغيرة بما فيه الكفاية) في الاستراتيجيات المعطاة في البداية للاعبين.
لكن يمكن تمديد كل لعبة (مصفوفة) محدودة إلى لعبة لا نهائية ، على سبيل المثال ، من خلال تزويد كل لاعب بأي عدد من الإستراتيجيات المهيمنة (انظر الفصل 22). من الواضح أن مثل هذا التوسع في مجموعة استراتيجيات اللاعب لن يعني في الواقع توسيعًا لإمكانياته ، ويجب ألا يختلف سلوكه الفعلي في اللعبة الموسعة عن سلوكه في اللعبة الأصلية. وهكذا ، حصلنا على الفور على عدد كافٍ من الأمثلة للألعاب العدائية اللانهائية التي لا تحتوي على نقاط سرج. هناك أيضًا أمثلة من هذا النوع.
وبالتالي ، من أجل تنفيذ مبدأ maximin في لعبة معادية لا نهائية ، من الضروري ، كما في حالة لعبة (matrix) المحدودة ، بعض التوسع في القدرات الإستراتيجية للاعبين. مقابل 96
كما في حالة ألعاب المصفوفة (انظر الفصل 1 ، 17) ، بالنسبة للألعاب العدائية العامة ، يلعب مفهوم الطيف الإستراتيجي المختلط دورًا مهمًا ، والذي ، مع ذلك ، يجب أن يُعطى هنا تعريفًا أكثر عمومية.
أخيرًا ، لاحظ أن مجموعة كل الاستراتيجيات المختلطة للاعب 1 في لعبة معادية عشوائية كما في المصفوفة
حتى النظر في الألعاب العدائية يظهر أن عددًا كبيرًا من هذه الألعاب ، بما في ذلك الألعاب المحدودة ، تحتوي ألعاب المصفوفة على حالات توازن ليس في الاستراتيجيات الأصلية الخالصة ، ولكن فقط في الاستراتيجيات المختلطة المعممة. لذلك ، بالنسبة للألعاب العامة غير العدائية وغير التعاونية ، من الطبيعي البحث عن حالات التوازن بدقة في الاستراتيجيات المختلطة.
لذلك ، على سبيل المثال (انظر الشكل 3.1) ، لاحظنا بالفعل أن "المقاول" لا يضطر أبدًا للتعامل مع عدم اليقين السلوكي. ولكن إذا أخذنا المستوى المفاهيمي لنوع "المسؤول" ، فإن كل شيء يكون عكس ذلك تمامًا. كقاعدة عامة ، النوع الرئيسي من عدم اليقين الذي يجب على "صانع القرار لدينا" مواجهته هو "الصراع". الآن يمكننا توضيح أن هذا عادة ما يكون تنافسًا غير صارم. وفي حالات أقل إلى حد ما ، يتخذ "المسؤول" قراراته في ظروف "عدم يقين طبيعي" ، ونادرًا ما يواجه صراعًا عدائيًا صارمًا. بالإضافة إلى ذلك ، يحدث تضارب المصالح عند اتخاذ القرارات من قبل "المسؤول" ، إذا جاز التعبير ، "مرة واحدة" ، أي في تصنيفنا ، غالبًا ما يلعب لعبة واحدة (أحيانًا عدد صغير جدًا) من ألعاب اللعبة. غالبًا ما تكون مقاييس تقييم النتائج نوعية أكثر منها كمية. الاستقلال الاستراتيجي لـ "المسؤول" محدود للغاية. مع الأخذ في الاعتبار ما سبق ، يمكن القول بأن المواقف الإشكالية بهذا الحجم غالبًا ما يجب تحليلها باستخدام ألعاب ثنائية المصفوفة غير متعاونة وغير معادية ، علاوة على ذلك ، في استراتيجيات بحتة.
مبادئ حل ألعاب مصفوفة معادية
نتيجة لذلك ، من المعقول توقع أنه في اللعبة الموصوفة أعلاه ، سيلتزم الخصوم بالاستراتيجيات التي اختاروها. لعبة مصفوفة معادية بحد أقصى خمس دقائق = min max Aiy>
ومع ذلك ، ليست كل ألعاب معاداة المصفوفة محددة تمامًا ، وفي الحالة العامة
وبالتالي ، في الحالة العامة ، لحل لعبة مصفوفة معادية ذات أبعاد / uxl ، من الضروري حل زوج من مشاكل البرمجة الخطية المزدوجة ، مما يؤدي إلى مجموعة من الاستراتيجيات المثلى ، وتكلفة اللعبة v.
كيف يتم تعريف لعبة المصفوفة العدائية لشخصين؟
ما هي طرق تبسيط وحل ألعاب المصفوفة المتضاربة
في حالة لعبة شخصين ، من الطبيعي اعتبار اهتماماتهما معاكسة تمامًا - فاللعبة معادية. وبالتالي ، فإن مكافأة أحد اللاعبين تساوي خسارة الآخر (مجموع ربح كلا اللاعبين هو صفر ، ومن هنا جاء الاسم ، لعبة محصلتها صفر). سننظر في الألعاب التي يكون لكل لاعب فيها عدد محدود من البدائل. يمكن إعطاء وظيفة المردود لمثل هذه اللعبة التي تتكون من شخصين محصلتها صفر في شكل مصفوفة (في شكل مصفوفة المكافآت).
كما لوحظ بالفعل ، تسمى اللعبة العدائية النهائية المصفوفة.
MATRIX GAMES - فئة من الألعاب العدائية يشارك فيها لاعبان ، ولكل لاعب عدد محدود من الاستراتيجيات. إذا كان لدى أحد اللاعبين استراتيجيات m وكان لدى اللاعب الآخر استراتيجيات n ، فيمكننا إنشاء مصفوفة لعبة ذات بُعد txn. م. قد يكون أو لا يكون لديه نقطة سرج. في الحالة الأخيرة
معهد موسكو لهندسة الطاقة
(جامعة فنية)
تقرير معمل
في نظرية اللعبة
"برنامج بحث عن الاستراتيجيات المثلى للعبة معادية مقترنة مقدمة في شكل مصفوفة"
اكتمل من قبل الطلاب
المجموعة A5-01
أشرابوف دالر
أشرابوفا أولغا
المفاهيم الأساسية لنظرية الألعاب
نظرية اللعبة مصممة للحل حالات الصراع ، بمعنى آخر. المواقف التي تتعارض فيها مصالح طرفين أو أكثر يسعون وراء أهداف مختلفة.
إذا كانت أهداف الطرفين معاكسة بشكل مباشر ، فإنهم يتحدثون عنها صراع عدائي .
لعبه يسمى نموذج رسمي مبسط لحالة الصراع.
يسمى لعب لعبة مرة واحدة من البداية إلى النهاية حفل . نتيجة الحزب دفع (أو فوز ).
الحفلة مكونة من التحركات ، بمعنى آخر. اختيار اللاعبين من مجموعة من البدائل الممكنة.
يمكن أن تكون التحركات شخصيو عشوائي.حركة شخصية ، على عكس عشوائي ، يعني اختيار واع من قبل لاعب خيار ما.
تسمى الألعاب التي يوجد فيها حركة شخصية واحدة على الأقل إستراتيجي .
يتم استدعاء الألعاب التي يتم فيها استدعاء جميع الحركات بشكل عشوائي القمار .
عند القيام بخطوة شخصية ، يتحدثون أيضًا عن الاستراتيجيات لاعب ، أي حول القاعدة أو مجموعة القواعد التي تحدد اختيار اللاعب. في نفس الوقت يجب أن تكون الإستراتيجية شاملة أي يجب تحديد الاختيار لأي موقف محتمل أثناء سير اللعبة.
تحدي نظرية اللعبة- إيجاد الاستراتيجيات المثلى للاعبين ، أي. الاستراتيجيات التي توفر لهم أقصى ربح أو أدنى خسارة.
تصنيف نماذج اللعبة النظرية
لعبه نعادة ما يشار إلى الأشخاص باسم ، أين 
هي مجموعة استراتيجيات اللاعب الأول ، 
- دفع اللعبة.
وفقًا لهذا التصنيف ، يمكن اقتراح التصنيف التالي لنماذج نظرية الألعاب:
منفصلة (مجموعات من الاستراتيجيات 
منفصله)
نهائي
بلا نهاية
مستمر (مجموعات من الاستراتيجيات 
مستمر)
بلا نهاية
نالأشخاص ( 
)
تحالف (تعاوني)
غير متعاون (غير متعاون)
2 أشخاص (مزدوج)
عدائي (ألعاب محصلتها صفر)
(مصالح الطرفين معاكسة ، أي خسارة لاعب يساوي ربح الآخر)
غير معادي
بمعلومات كاملة (إذا كان اللاعب الذي يقوم بنقلة شخصية يعرف تاريخ اللعبة بالكامل ، أي جميع تحركات الخصم)
مع معلومات غير كاملة
بقيمة صفر (إجمالي الدفعة صفر)
بمجموع غير صفري
اتجاه واحد (اليانصيب)
متعدد الاتجاهات
تمثيل مصفوفة للعبة معادية مقترنة
في هذا البرنامج التعليمي ، سننظر ألعاب معادية لشخصين
معطى في شكل مصفوفة. هذا يعني أننا نعرف مجموعة استراتيجيات اللاعب الأول (اللاعب أ){
أ أنا },
أنا = 1,…,
مومجموعة استراتيجيات اللاعب الثاني (اللاعب ب){
ب ي },
ي = 1,...,
نوالمصفوفة أ
= ||
أ اي جاي ||
مكافآت اللاعب الأول. نظرًا لأننا نتحدث عن لعبة معادية ، فمن المفترض أن ربح اللاعب الأول يساوي خسارة الثاني. نحن نعتبر أن عنصر المصفوفة أ اي جايهي مكافأة اللاعب الأول عندما يختار إستراتيجية أ أناوجواب اللاعب الثاني بالاستراتيجية ب ي. سوف نشير إلى مثل هذه اللعبة مثل 
، أين م
- عدد استراتيجيات اللاعب لكن،ن
- عدد استراتيجيات اللاعب في.بشكل عام يمكن تمثيله بالجدول التالي:
|
ب 1 |
|
ب ي |
|
ب ن |
|
|
أ 1 |
|
| |||
|
|
|
|
|
|
|
|
أ أنا |
|
| |||
|
|
|
|
|
|
|
|
أ م |
|
|
مثال 1
كمثال بسيط ، فكر في لعبة تتكون فيها اللعبة من حركتين.
الخطوة الأولى: لاعب لكنيختار أحد الأرقام (1 أو 2) دون إخبار الخصم باختياره.
الخطوة الثانية: لاعب فييختار أحد الأرقام (3 أو 4).
حصيلة: اختيار اللاعب لكنو فيأضف ما يصل. إذا كان المجموع زوجيًا ، إذن فييدفع قيمته للاعب لكن، إذا كان غريبًا - والعكس صحيح ، لكنيدفع للاعب في.
يمكن تمثيل هذه اللعبة على أنها 
بالطريقة الآتية:
|
|
|
|
|
| ||
|
|
(الاختيار 3)
(الاختيار 4)
(الاختيار 1)
(الاختيار 2)من السهل رؤية ذلك هذه اللعبةهي لعبة معادية ، بالإضافة إلى أنها لعبة ذات معلومات غير كاملة ، منذ ذلك الحين لاعب في،عند القيام بحركة شخصية ، لا يُعرف الخيار الذي اتخذه اللاعب لكن.
كما هو مذكور أعلاه ، تتمثل مهمة نظرية اللعبة في إيجاد الاستراتيجيات المثلى للاعبين ، أي الاستراتيجيات التي توفر لهم أقصى ربح أو أدنى خسارة. هذه العملية تسمى قرار اللعبة .
عند حل لعبة في شكل مصفوفة ، يجب على المرء التحقق من وجود اللعبة في اللعبة نقطة سرج . لهذا ، يتم تقديم قيمتين:
هو الحد الأدنى لسعر اللعبة ، و
هو التقدير الأعلى لسعر اللعبة.
من المرجح أن يختار اللاعب الأول الاستراتيجية التي سيحصل فيها على أقصى ربح من بين جميع الإجابات الممكنة للاعب الثاني ، والثاني ، على العكس من ذلك ، سيختار تلك التي تقلل من خسارته ، أي الفوز المحتمل للأول.
يمكن إثبات ذلك α ≤ الخامس ≤ β ، أين الخامس–سعر اللعبة ، أي العائد المحتمل للاعب الأول.
إذا كانت العلاقة α
=
β
=
الخامس، ثم يقولون ذلك اللعبة لديها نقطة سرج
، و حلها في استراتيجيات خالصة
. بعبارة أخرى ، هناك استراتيجيتان 
اعطاء اللاعب لكنالخامس.
مثال 2
دعنا نعود إلى اللعبة التي درسناها في المثال 1 ونفحصها بحثًا عن وجود نقطة سرج.
|
|
|
|
|
|
| |||
|
| |||
|
|
(الاختيار 3)
(الاختيار 4)
(الاختيار 1)
(الاختيار 2)
لهذه اللعبة 
=
-5,
=
4,
لذلك ، ليس لديها نقطة سرج.
مرة أخرى ، لاحظ أن هذه اللعبة هي لعبة معلومات غير كاملة. في هذه الحالة ، يمكنك فقط تقديم المشورة للاعب لكناختر استراتيجية 
، لان في هذه الحالة ، يمكنه الحصول على أكبر عائد ، بشرط أن يختار اللاعب فيالاستراتيجيات 
.
مثال 3
دعنا نجري بعض التغييرات على قواعد اللعبة من المثال 1. دعونا نعطي اللاعب فيمعلومات اختيار اللاعب لكن.ثم فيهناك استراتيجيتان إضافيتان:
- استراتيجية تعود بالفائدة على لكن.إذا كان الاختيار أ - 1 ،ومن بعد فييختار 3 إذا كان الاختيار أ - 2 ،ومن بعد فييختار 4 ؛
- استراتيجية لا تفيد لكن.إذا كان الاختيار أ - 1 ،ومن بعد فييختار 4 إذا كان الاختيار أ - 2 ،ومن بعد فييختار 3.
|
|
|
|
|
|
|
|
| |||||
|
| |||||
|
|
(الاختيار 3)
(الاختيار 4)
(الاختيار 1)
(الاختيار 2)
هذه اللعبة مليئة بالمعلومات.
في هذه الحالة 
=
-5,
=
-5,
، ومن ثم فإن اللعبة لديها نقطة سرج 
. تتوافق نقطة السرج هذه مع زوجين من الاستراتيجيات المثلى: 
و 
. سعر اللعبة الخامس= -5.
من الواضح أن ل لكنهذه اللعبة غير مجدية.
يعتبر المثالان 2 و 3 توضيحًا جيدًا للنظرية التالية ، المثبتة في نظرية اللعبة:
نظرية 1
يتم حل كل لعبة معادية مقترنة بمعلومات مثالية في استراتيجيات خالصة.
الذي - التي. تقول النظرية 1 أن أي لعبة لشخصين مع معلومات مثالية لها نقطة سرج وهناك زوج من الاستراتيجيات الخالصة 
اعطاء اللاعب لكنربح مستدام يساوي سعر اللعبة الخامس.
في حالة عدم وجود سرج نقطة ، ما يسمى ب استراتيجيات مختلطة
:، أين ص أنا وف يهي احتمالات اختيار الاستراتيجيات أ أنا
و
ب يالأول والثاني على التوالي. حل اللعبة في هذه الحالة هو زوج من الإستراتيجيات المختلطة 
تعظيم التوقع الرياضي لسعر اللعبة.
إن تعميم النظرية 1 على حالة لعبة بمعلومات غير كاملة هو النظرية التالية:
نظرية 2
أي لعبة معادية مقترنة لها حل مثالي واحد على الأقل ، أي زوج من الاستراتيجيات المختلطة في الحالة العامة 
اعطاء اللاعب لكنربح مستدام يساوي سعر اللعبة الخامس، وعلاوة على ذلك α ≤
الخامس ≤
β
.
في حالة خاصة ، بالنسبة للعبة ذات نقطة السرج ، يبدو الحل في الاستراتيجيات المختلطة كزوج من المتجهات حيث يكون أحد العناصر مساويًا لعنصر واحد ، والباقي يساوي صفرًا.
أبسط حالة ، تم تفصيلها بالتفصيل في نظرية اللعبة ، هي لعبة زوج محدود محصلتها صفر (لعبة عدائية لشخصين أو تحالفين). خذ بعين الاعتبار هذه اللعبة جي, فيها لاعبان لكنو في،وجود مصالح متعارضة: ربح أحدهما يساوي خسارة الآخر. منذ مكافأة اللاعب لكنيساوي مكافأة اللاعب فيإشارة معاكسة ، لا يمكننا إلا أن نهتم بالمكافأة ألاعب لكن.بطبيعة الحال، لكنيريد تعظيم و في -قلل أ.من أجل البساطة ، دعنا نعرّف أنفسنا عقليًا مع أحد اللاعبين (فليكن لكن)وسوف نسميه "نحن" واللاعب في -"الخصم" (بالطبع ، لا توجد مزايا حقيقية ل لكنلا يتبع من هذا). دعونا لها رالاستراتيجيات الممكنة لكن 1 , أ 2 , ..., لكن مو العدو نالاستراتيجيات الممكنة في 1 ، في 2 ، ..؛ في ن(تسمى هذه اللعبة لعبة ر × ن). دل أ اي جايمكاسبنا إذا استخدمنا الإستراتيجية أ أنا , والعدو استراتيجية ب ي .
الجدول 26.1
|
أ أنا ب ي |
ب 1 |
ب 2 |
ب ن |
|
|
أ 1 أ 2 أ م |
أ 11 أ 21 أ م 1 |
أ 21 أ م |
أ 1 ن أ 2 ن أ مليون |
افترض أن لكل زوج من الاستراتيجيات أ<, في،فوز (أو فوز متوسط) أ, ينعلم. ثم ، من حيث المبدأ ، من الممكن تجميع جدول مستطيل (مصفوفة) ، يسرد استراتيجيات اللاعبين والمكافآت المقابلة (انظر الجدول 26.1).
إذا تم تجميع مثل هذا الجدول ، فإننا نقول أن اللعبة جيإلى شكل مصفوفة (في حد ذاته ، يمكن أن يكون إحضار اللعبة إلى هذا الشكل مهمة صعبة ، وأحيانًا شبه مستحيلة ، بسبب العدد الهائل من الاستراتيجيات). لاحظ أنه إذا تم تقليص اللعبة إلى نموذج مصفوفة ، فسيتم تقليل لعبة الحركات المتعددة في الواقع إلى لعبة من خطوة واحدة - يتعين على اللاعب القيام بحركة واحدة فقط: اختر إستراتيجية. سوف نشير بإيجاز إلى مصفوفة اللعبة ( أ اي جاي).
ضع في اعتبارك لعبة على سبيل المثال جي(4 × 5) على شكل مصفوفة. في حوزتنا (للاختيار من بينها) أربع استراتيجيات ، لدى العدو خمس استراتيجيات. مصفوفة اللعبة مبينة في الجدول 26.2
دعونا نفكر في أي استراتيجية نحن (اللاعب لكن)استغل الفرصة؟ تتمتع المصفوفة 26.2 بمكافأة مغرية "10" ؛ نحن منجذبون لاختيار استراتيجية لكن 3 , حيث سنحصل على هذا "الشهي". لكن انتظر ، العدو ليس غبيًا أيضًا! إذا اخترنا استراتيجية لكن 3 , هو ، على نكاية منا ، سيختار استراتيجية في 3 , ونحصل على بعض المكاسب البائسة "1". لا ، اختر استراتيجية لكن 3 ممنوع! كيف تكون؟ من الواضح ، بناءً على مبدأ الحذر (وهو المبدأ الرئيسي لنظرية اللعبة) ، يجب أن نختار
الجدول 26.2
|
ب ي أ أنا |
ب 1 |
ب 2 |
ب 3 |
ب 4 |
ب 5 |
|
أ 1 أ 2 أ 3 أ 4 |
الاستراتيجية التي الحد الأدنى للربح لدينا هو الحد الأقصى.هذا هو ما يسمى ب "مبدأ minimax": تصرف بطريقة تجعلك ، مع أسوأ سلوك للعدو ، تحصل على أقصى مكاسب.
نعيد كتابة الجدول 26.2 وفي العمود الإضافي الأيمن نكتب الحد الأدنى لقيمة العائد في كل سطر ، (الحد الأدنى للسطر) ؛ دعونا نخصصها أناالصف السادس α أنا(انظر الجدول 26.3).
الجدول 26.3
|
ب ي أ أنا |
ب 1 |
ب 2 |
ب 3 |
ب 4 |
ب 5 | |
|
أ 1 أ 2 أ 3 أ 4 | ||||||
|
β ي |
من كل القيم α أنا(العمود الأيمن) يتم تمييز أكبر (3). إنها تطابق الإستراتيجية أأربعة. بعد اختيار هذه الإستراتيجية ، يمكننا ، على أي حال ، التأكد من أننا (لأي سلوك للعدو) سنكسب ما لا يقل عن 3. هذه القيمة هي مكسبنا المضمون ؛ مع توخي الحذر ، لا يمكننا الحصول على أقل من هذا (قد أحصل على المزيد). يُطلق على هذا المردود السعر الأدنى للعبة (أو "الحد الأقصى" - الحد الأدنى للمكافآت). سوف نشير إليه أ.في حالتنا هذه α = 3.
فلنأخذ الآن وجهة نظر العدو ونجادل لصالحه. إنه ليس نوعًا من البيدق ، ولكنه معقول أيضًا! عند اختيار استراتيجية ، يود أن يعطي أقل ، لكن يجب أن يعتمد على سلوكنا ، وهو أسوأ ما في الأمر بالنسبة له. إذا اختار استراتيجية في 1 , سوف نجيب عليه لكن 3 , فيعطي 10. إذا اختار ب 2 - سنجيب عليه لكن 2 , وسوف يعطي 8 ، وما إلى ذلك. نضيف صفًا سفليًا إضافيًا إلى الجدول 26.3 ونكتب فيه الحد الأقصى للأعمدة β ي. من الواضح أن الخصم الحذر يجب أن يختار الإستراتيجية التي تقلل هذه القيمة (يتم تمييز القيمة المقابلة لـ 5 في الجدول 26.3). قيمة β هذه هي قيمة المكسب ، والتي لن يمنحنا إياها خصم معقول أكثر مما يعطينا. يطلق عليه السعر الأعلى للعبة (أو "minimax" - الحد الأدنى من المكاسب القصوى). في مثالنا ، β = 5 ويتم تحقيقه باستخدام استراتيجية الخصم ب 3 .
لذلك ، بناءً على مبدأ الحذر (قاعدة إعادة التأمين "تعتمد دائمًا على الأسوأ!") ، يجب أن نختار استراتيجية لكن 4 , والعدو - الإستراتيجية في 3 . تسمى هذه الاستراتيجيات بـ "minimax" (مشتق من مبدأ minimax). طالما أن كلا الطرفين في مثالنا يلتزم بإستراتيجيات الحد الأدنى ، فإن المردود سيكون أ 43 = 3.
تخيل الآن للحظة أننا تعلمنا أن العدو ينتهج استراتيجية في 3 . تعال ، دعونا نعاقبه على هذا ونختار استراتيجية لكن 1 - سنحصل على 5 ، وهذا ليس بهذا السوء. ولكن بعد كل شيء ، العدو أيضًا ليس تفويتها ؛ دعه يعرف أن استراتيجيتنا لكن 1 ; كما أنه سريع الاختيار في 4 , خفض المكاسب إلى 2 ، وما إلى ذلك ("سارع الشركاء بشأن الاستراتيجيات"). باختصار ، استراتيجيات minimax في مثالنا غير مستقر فيما يتعلقإلى معلومات حول سلوك الطرف الآخر ؛لا تمتلك هذه الاستراتيجيات خاصية التوازن.
هل هي دائما هكذا؟ لا، ليس دائما. ضع في اعتبارك مثالًا مع المصفوفة الواردة في الجدول 26.4.
في هذا المثال ، السعر الأدنى للعبة يساوي السعر العلوي: α = β = 6. ماذا يتبع هذا؟ استراتيجيات لاعب Minimax لكنو فيستكون مستدامة. طالما تمسك كلا اللاعبين بهما ، فإن المردود هو 6. لنرى ماذا سيحدث لو فعلنا ذلك (لكن)أعلم أن العدو (في)
الجدول 26.4
|
بي أ أنا |
ب 1 |
ب 2 |
ب 3 |
ب 4 | |
|
أ 1 أ 2 أ 3 | |||||
|
β ي |
تتمسك بالاستراتيجية ب 2 ؟ ولن يتغير شيء بالضبط. لأن أي انحراف عن الإستراتيجية لكن 2 يمكن أن تجعل وضعنا أسوأ. وبالمثل ، فإن المعلومات التي يتلقاها العدو لن تجعله يتراجع عن استراتيجيته. في 2 . زوج من الاستراتيجيات لكن 2 , ب 2 يمتلك خاصية التوازن (زوج متوازن من الإستراتيجيات) ، والمكافأة (في حالتنا ، 6) التي يتم تحقيقها باستخدام هذا الزوج من الإستراتيجيات تسمى "نقطة السرج في المصفوفة" 1). علامة على وجود نقطة سرج وزوج متوازن من الاستراتيجيات هي المساواة بين الأسعار الدنيا والعليا للعبة ؛ تسمى القيمة المشتركة لـ α و سعر اللعبة. سوف نسميها الخامس:
α = β = الخامس
الاستراتيجيات أ أنا , ب ي(في هذه الحالة لكن 2 ، في 2 ), التي يتم من أجلها تحقيق هذا المردود تسمى الاستراتيجيات البحتة المثلى ، ويسمى مجموعها حلًا للعبة. في هذه الحالة ، يُقال أن اللعبة نفسها قد تم حلها في استراتيجيات بحتة. كلا الجانبين لكنو فييمكن للمرء أن يشير إلى استراتيجياتهم المثلى التي بموجبها يكون موقعهم هو الأفضل. ما هو اللاعب لكنفي هذه الحالة ، 6 انتصارات ، واللاعب في -يخسر 6 ، - حسنًا ، هذه هي شروط اللعبة: فهي مفيدة لكنوغير موات ل في
1) مصطلح "نقطة السرج" مأخوذ من الهندسة - هذا هو اسم النقطة الموجودة على السطح ، حيث يتم الوصول إلى الحد الأدنى على طول إحداثي واحد والحد الأقصى على طول الآخر في نفس الوقت.
قد يكون لدى القارئ سؤال: لماذا تسمى الإستراتيجيات المثلى "نقية"؟ بالنظر إلى الأمام قليلاً ، دعنا نجيب على هذا السؤال: هناك استراتيجيات "مختلطة" ، والتي تتمثل في حقيقة أن اللاعب لا يستخدم إستراتيجية واحدة ، بل عدة إستراتيجيات ، بالتناوب عليها بشكل عشوائي. لذلك ، إذا سمحنا ، بالإضافة إلى الاستراتيجيات البحتة ، أيضًا بالاستراتيجيات المختلطة ، أيًا منها نهاية اللعبةله حل - نقطة توازن. لكننا ما زلنا نتحدث عن الذرة.
إن وجود نقطة السرج في اللعبة أبعد ما يكون عن القاعدة ؛ بل هو الاستثناء. معظم الألعاب ليس لها نقطة سرج. ومع ذلك ، هناك مجموعة متنوعة من الألعاب التي لها دائمًا نقطة سرج ، وبالتالي يتم حلها في استراتيجيات خالصة. هذه هي ما يسمى بـ "الألعاب ذات المعلومات الكاملة". اللعبة التي تحتوي على رف للمعلومات هي لعبة يعرف فيها كل لاعب التاريخ الكامل لتطورها ، أي نتائج جميع الحركات السابقة ، الشخصية والعشوائية ، في كل حركة شخصية. من أمثلة الألعاب التي تحتوي على معلومات كاملة لعبة الداما والشطرنج و tic-tac-toe وما إلى ذلك.
في نظرية اللعبة ، ثبت ذلك كل لعبة بمعلومات كاملة لها نقطة سرج ،وبالتالي يمكن حلها في استراتيجيات بحتة. في كل لعبة تحتوي على معلومات مثالية ، يوجد زوج من الإستراتيجيات المثلى التي تعطي مردودًا ثابتًا يساوي سلسلة اللعبة الخامس. إذا كانت هذه اللعبة تتكون من حركات شخصية فقط ، فعندما يطبق كل لاعب إستراتيجيته المثالية ، يجب أن تنتهي بطريقة محددة تمامًا - بمكافأة مساوية لسعر اللعبة. لذا ، إذا عُرف حل اللعبة ، فإن اللعبة نفسها تفقد معناها!
لنأخذ مثالاً أوليًا للعبة بمعلومات كاملة: لاعبان يضعان النيكل بالتناوب على طاولة مستديرة ، ويختاران بشكل تعسفي موضع مركز العملة (لا يُسمح بالتداخل المتبادل بين العملات المعدنية). الفائز هو الذي يضع آخر فلس (عندما لا يكون هناك مكان للآخرين). من السهل أن نرى أن نتيجة هذه اللعبة هي في الأساس نتيجة مفروضة. هناك استراتيجية معينة تضمن أن يفوز اللاعب الذي يضع العملة في المقام الأول. وبالتحديد ، يجب عليه أولاً وضع نيكل في منتصف الطاولة ، ثم الرد على كل حركة للخصم بحركة متناظرة. من الواضح أنه بغض النظر عن سلوك الخصم ، لا يمكنه تجنب الخسارة. الوضع هو نفسه تمامًا مع لعبة الشطرنج والألعاب التي تحتوي على معلومات كاملة بشكل عام: أي منها ، مكتوب في شكل مصفوفة ، له نقطة سرج ، وبالتالي يكون الحل في استراتيجيات خالصة ، وبالتالي ، يكون منطقيًا فقط طالما أن هذا الحل غير موجود. لنفترض أن لعبة الشطرنج هي إما دائماًينتهي بالفوز الأبيض ، أو دائماً -الأسود ، أو دائماً -التعادل ، فقط بما هو بالضبط - لا نعرف حتى الآن (لحسن الحظ لعشاق الشطرنج). دعنا نضيف شيئًا آخر: بالكاد سنعرف في المستقبل المنظور ، لأن عدد الاستراتيجيات ضخم جدًا لدرجة أنه من الصعب للغاية (إن لم يكن من المستحيل) تقليص اللعبة إلى شكل مصفوفة وإيجاد نقطة سرج فيها.
الآن دعنا نسأل أنفسنا ماذا نفعل إذا كانت اللعبة لا تحتوي على نقطة سرج: α ≠ β؟ حسنًا ، إذا اضطر كل لاعب إلى اختيار واحدة - الإستراتيجية البحتة الوحيدة ، فلا يوجد ما يجب فعله: يجب أن يسترشد المرء بمبدأ minimax. شيء آخر هو أنه إذا كان من الممكن "مزج" مجموعة من الاستراتيجيات ، بالتناوب العشوائي مع بعض الاحتمالات. يتم تصور استخدام الاستراتيجيات المختلطة على هذا النحو: تتكرر اللعبة عدة مرات ؛ قبل كل لعبة في اللعبة ، عندما يُمنح اللاعب نقلة شخصية ، "يعهد" باختياره للصدفة ، "يلقي الكثير" ، ويأخذ الإستراتيجية التي سقطت (نحن نعرف بالفعل كيفية تنظيم القرعة من الفصل السابق ).
الاستراتيجيات المختلطة في نظرية اللعبة هي نموذج للتكتيكات المرنة المتغيرة ، عندما لا يعرف أي من اللاعبين كيف سيتصرف الخصم في لعبة معينة. غالبًا ما يستخدم هذا التكتيك (وإن كان بدون أي مبرر رياضي) في ألعاب الورق. دعنا نلاحظ في نفس الوقت أن أفضل طريقة لإخفاء سلوكك عن العدو هي منحه طابعًا عشوائيًا ، وبالتالي عدم معرفة ما ستفعله مسبقًا.
لذا ، لنتحدث عن الاستراتيجيات المختلطة. سوف نشير إلى الاستراتيجيات المختلطة للاعبين لكنو فيعلى التوالى سأ = ( ص 1 , ص 2 , ..., ص م), س ب = (ف 1 , ف 2 , …, ف ن)، أين ص 1 , ص 2 , …, ص م(تشكيل ما مجموعه واحد) - احتمالات استخدام اللاعب لكنالاستراتيجيات لكن 1 , أ 2 ,… , أ م ; ف 1 , ف 2 , …, ف ن- احتمالات الاستخدام من قبل اللاعب فيالاستراتيجيات في 1 , في 2 , ..., في ن . في حالة معينة ، عندما تكون جميع الاحتمالات ، باستثناء واحد ، مساوية للصفر ، وهذا الواحد يساوي واحدًا ، تتحول الإستراتيجية المختلطة إلى واحدة فقط.
هناك نظرية أساسية في نظرية اللعبة: أي لعبة محدودة لشخصين محصلتها صفر لها حل واحد على الأقل -زوج من الاستراتيجيات المثلى ، مختلطة بشكل عام 
والسعر المقابل الخامس.
زوج من الاستراتيجيات المثلى 
تشكيل حل اللعبة له الخاصية التالية: إذا التزم أحد اللاعبين بإستراتيجيته المثلى ، فلن يكون من المربح للآخر أن ينحرف عن استراتيجيته.يشكل هذا الزوج من الإستراتيجيات نوعًا من التوازن في اللعبة: يريد أحد اللاعبين تحويل المكاسب إلى الحد الأقصى ، والآخر إلى الحد الأدنى ، ويسحب كل منهما في اتجاهه الخاص ، ومع السلوك المعقول لكليهما ، يريد أحدهما توازنًا وثابتًا. يتم إنشاء مكاسب. الخامس.اذا كان ت> 0 ، فإن اللعبة تكون مربحة لنا إذا الخامس<
0
-
للعدو في الخامس= 0 اللعبة "عادلة" ، وهي مفيدة بنفس القدر لكلا المشاركين.
فكر في مثال لعبة بدون نقطة سرج وقدم (بدون دليل) حلها. اللعبة كالتالي: لاعبان لكنو فيفي نفس الوقت وبدون نطق كلمة أظهر إصبع واحد أو اثنين أو ثلاثة. يتم تحديد الفوز من خلال العدد الإجمالي للأصابع: إذا كان الأمر كذلك ، يفوز لكنويستقبل من فيمبلغ يساوي هذا الرقم ؛ إذا كان غريبًا ، فالعكس صحيح لكنيدفع فيمبلغ يساوي هذا الرقم. ماذا يجب أن يفعل اللاعبون؟
لنقم بإنشاء مصفوفة اللعبة. في لعبة واحدة ، كل لاعب لديه ثلاث استراتيجيات: إظهار إصبع واحد أو إصبعين أو ثلاثة. يتم إعطاء المصفوفة 3 × 3 في الجدول 26.5 ؛ يُظهر العمود الأيمن الإضافي الحد الأدنى للصف ، ويظهر الصف السفلي الإضافي الحد الأقصى للعمود.
انخفاض سعر اللعبة α = - 3 ويتوافق مع الإستراتيجية أ 1 . هذا يعني أنه من خلال السلوك المعقول والحذر ، فإننا نضمن أننا لن نخسر أكثر من 3. عزاء صغير ، ولكن لا يزال أفضل من ، على سبيل المثال ، ربح 5 ، والذي يحدث في بعض خلايا المصفوفة. سيء لنا ، اللاعب لكن...لكن دعونا نواسي أنفسنا:
يبدو أن موقف الخصم أسوأ: التكلفة الأقل للعبة هي β = 4 ، أي أنه مع السلوك المعقول ، سوف يعطينا ما لا يقل عن 4. بشكل عام ، الموقف ليس جيدًا جدًا - لا لأحد ولا من أجل الجانب الآخر. لكن دعنا نرى ما إذا كان يمكن تحسينه؟ اتضح أنك تستطيع. إذا لم يستخدم كل جانب إستراتيجية بحتة واحدة ، بل إستراتيجية مختلطة ، حيث
الجدول 26.5
|
بي أ أنا |
ب 1 |
ب 2 |
ب 3 | |
|
أ 1 أ 2 أ 3 | ||||
|
β ي |
الأول والثالث يدخلان باحتمال 1/4 ، والثاني - باحتمال 1/2 ، أي
عندها سيكون متوسط العائد مساويًا للصفر بشكل ثابت (مما يعني أن اللعبة "عادلة" وذات فائدة متساوية لكلا الجانبين). الاستراتيجيات 
تشكل حلاً للعبة وسعرها الخامس= 0. كيف وجدنا هذا الحل؟ هذا سؤال مختلف. في القسم التالي ، نوضح كيف يتم حل الألعاب المحدودة بشكل عام.
فكر في لعبة زوجية محصلتها صفر محدودة. للدلالة به أمكافأة اللاعب أ، ومن خلال ب- فوز اللاعب ب. لان أ = –بإذن عند تحليل مثل هذه اللعبة ، ليست هناك حاجة للنظر في كلا الرقمين - يكفي النظر في مكافأة أحد اللاعبين. فليكن ، على سبيل المثال ، أ. فيما يلي ، لسهولة العرض ، الجانب أسنقوم بتسمية مشروطة " نحن"والجانب ب – "العدو".
دعونا لها مالاستراتيجيات الممكنة أ 1 , أ 2 , …, أكونو العدو نالاستراتيجيات الممكنة ب 1 , ب 2 , …, ب ن(تسمى هذه اللعبة لعبة م × ن). افترض أن كل جانب قد اختار استراتيجية معينة: لقد اخترناها عاي، الخصم ب ي. إذا كانت اللعبة تتكون فقط من حركات شخصية ، ثم اختيار الاستراتيجيات عايو ب ييحدد بشكل فريد نتيجة اللعبة - مردودنا (إيجابي أو سلبي). دعنا نشير إلى هذا المكسب على أنه aij(الفوز عندما نختار الإستراتيجية عايوالعدو - الاستراتيجيات ب ي).
إذا كانت اللعبة تحتوي ، بالإضافة إلى التحركات العشوائية الشخصية ، على ثمار زوج من الاستراتيجيات عاي, ب يهو متغير عشوائي يعتمد على نتائج جميع الحركات العشوائية. في هذه الحالة ، فإن التقدير الطبيعي للمردود المتوقع هو التوقع الرياضي للفوز العشوائي. للراحة ، سوف نشير بواسطة aijكل من المكافأة نفسها (في لعبة بدون حركات عشوائية) وتوقعها الرياضي (في لعبة ذات حركات عشوائية).
افترض أننا نعرف القيم aijلكل زوج من الاستراتيجيات. يمكن كتابة هذه القيم كمصفوفة تتوافق صفوفها مع استراتيجياتنا ( عاي) ، وتظهر الأعمدة استراتيجيات الخصم ( ب ي):
| ب ي أ ط | ب 1 | ب 2 | … | ب ن |
| أ 1 | أ 11 | أ 12 | … | أ 1ن |
| أ 2 | أ 21 | أ 22 | … | أ 2ن |
| … | … | … | … | … |
| أكون | صباحا 1 | صباحا 2 | … | آمين |
تسمى هذه المصفوفة مصفوفة المكافآت للعبةأو ببساطة مصفوفة اللعبة.
لاحظ أن إنشاء مصفوفة المكافآت للألعاب التي تحتوي على عدد كبير من الاستراتيجيات يمكن أن يكون مهمة صعبة. على سبيل المثال ، ل لعبة الشطرنجعدد الاستراتيجيات الممكنة كبير جدًا لدرجة أن بناء مصفوفة المكافآت أمر مستحيل عمليًا. ومع ذلك ، من حيث المبدأ ، يمكن اختزال أي لعبة محدودة إلى شكل مصفوفة.
انصح مثال 1لعبة 4 × 5 معادية. لدينا أربع استراتيجيات تحت تصرفنا ، لدى العدو خمس استراتيجيات. مصفوفة اللعبة كالتالي:
| ب ي أ ط | ب 1 | ب 2 | ب 3 | ب 4 | ب 5 |
| أ 1 | |||||
| أ 2 | |||||
| أ 3 | |||||
| أ 4 |
ما هي الإستراتيجية التي يجب علينا (أي اللاعب أ) ليستخدم؟ مهما كانت الإستراتيجية التي نختارها ، فإن الخصم المعقول سوف يستجيب لها بالإستراتيجية التي سيكون مردودنا لها ضئيلاً. على سبيل المثال ، إذا اخترنا الاستراتيجية أ 3 (مغريًا بفوز 10) ، سيختار الخصم إستراتيجية ردًا على ذلك ب 1 ، والمكافأة ستكون فقط 1. من الواضح ، استنادًا إلى مبدأ الحذر (وهو المبدأ الرئيسي لنظرية اللعبة) ، يجب أن نختار الإستراتيجية التي الحد الأدنى للربح لدينا هو الحد الأقصى.
للدلالة به أناالحد الأدنى من قيمة العائد للاستراتيجية عاي:
وأضف عمودًا يحتوي على هذه القيم إلى مصفوفة اللعبة:
| ب ي أ ط | ب 1 | ب 2 | ب 3 | ب 4 | ب 5 | الحد الأدنى في الصفوف أنا | |
| أ 1 | |||||||
| أ 2 | |||||||
| أ 3 | |||||||
| أ 4 | ماكسيمين |
عند اختيار استراتيجية ، يجب أن نختار الاستراتيجية التي لها قيمة أناأقصى. دعنا نشير إلى هذه القيمة القصوى من خلال α :
قيمة α اتصل انخفاض سعر اللعبةأو ماكسيمين(الحد الأدنى للفوز). استراتيجية اللاعب أيتوافق مع الحد الأقصى α ، يسمى استراتيجية maximin.
في هذا المثال ، الحد الأقصى α تساوي 3 (يتم تمييز الخلية المقابلة في الجدول باللون الرمادي) ، وإستراتيجية maximin هي أأربعة. بعد اختيار هذه الإستراتيجية ، يمكننا التأكد من أنه بالنسبة لأي سلوك للعدو ، فإننا سوف نفوز بما لا يقل عن 3 (وربما أكثر مع السلوك "غير المعقول" للعدو). هذه القيمة هي الحد الأدنى المضمون لدينا ، والذي يمكننا ضمانه أنفسنا ، نلتزم بإستراتيجية ("إعادة التأمين") الأكثر حذرًا.
الآن سنقوم بتنفيذ منطق مماثل للعدو ب ب أ ب 2 - سوف نجيب عليه أ .
للدلالة به βj أ ب) للاستراتيجية عاي:
βj β :
7. ما هي لعبة القيمة العليا الآن سنقوم بتنفيذ منطق مماثل للخصم ب. إنه مهتم بتقليل مكاسبنا إلى الحد الأدنى ، أي إعطائنا أقل ، لكن يجب أن يعتمد على سلوكنا ، وهو الأسوأ بالنسبة له. على سبيل المثال ، إذا اختار الاستراتيجية ب 1 ، ثم سنجيب عليه بإستراتيجية أ 3 ، وسيعطينا 10. إذا اختار ب 2 - سوف نجيب عليه أ 2 ، وسيعطي 8 ، وهكذا. من الواضح أن الخصم الحذر يجب أن يختار الإستراتيجية التي سيكون الحد الأقصى من مكاسبنا هو الحد الأدنى.
للدلالة به βjالقيم القصوى في أعمدة مصفوفة المكافآت (أقصى عائد للاعب أ، أو ، وهو نفسه ، أقصى خسارة للاعب ب) للاستراتيجية عاي:
وأضف صفًا يحتوي على هذه القيم إلى مصفوفة اللعبة:
عند اختيار الإستراتيجية ، سيفضل العدو الاستراتيجية التي لها قيمة βjالحد الأدنى. دعونا نشير إلى ذلك β :
قيمة β اتصل أعلى سعر اللعبةأو مينيماكس(الحد الأدنى للفوز). إستراتيجية الخصم (اللاعب) المطابقة للحد الأدنى ب)، يسمى استراتيجية minimax.
Minimax هي قيمة المكسب ، التي لن يمنحنا إياها خصم معقول أكثر مما (بمعنى آخر ، لن يخسر الخصم المعقول أكثر من β ). في هذا المثال ، minimax β تساوي 5 (يتم تمييز الخلية المقابلة في الجدول باللون الرمادي) ويتم تحقيقها باستخدام استراتيجية الخصم ب 3 .
لذلك ، بناءً على مبدأ الحذر ("توقع الأسوأ دائمًا!") ، يجب أن نختار استراتيجية أ 4 ، والعدو - استراتيجية ب 3. مبدأ الحذر أساسي في نظرية اللعبة ويسمى مبدأ minimax.
انصح المثال 2. دع اللاعبين أو فيأحد الأرقام الثلاثة مكتوب بشكل متزامن ومستقل عن الآخر: إما "1" أو "2" أو "3". إذا كان مجموع الأرقام المكتوبة زوجيًا ، فعندئذٍ اللاعب بيدفع للاعب أهذا المبلغ. إذا كان المبلغ فرديًا ، يدفع اللاعب هذا المبلغ ألاعب في.
دعنا نكتب مصفوفة المكافآت للعبة ونجد الأسعار الأدنى والأعلى للعبة (رقم الإستراتيجية يتوافق مع الرقم المكتوب):
لاعب أيجب أن تلتزم باستراتيجية maximin أ 1 للفوز على الأقل -3 (أي أن تخسر 3 على الأكثر). استراتيجية لاعب Minimax بأي من الاستراتيجيات ب 1 و ب 2 ، مما يضمن أنه لن يعطي أكثر من 4.
سنحصل على نفس النتيجة إذا كتبنا مصفوفة المكافآت من وجهة نظر اللاعب في. في الواقع ، يتم الحصول على هذه المصفوفة عن طريق تبديل المصفوفة المكونة من وجهة نظر اللاعب أ، وتغيير إشارات العناصر إلى العكس (منذ مكافأة اللاعب أهي خسارة اللاعب في):
بناءً على هذه المصفوفة ، يتبع ذلك اللاعب بيجب أن تتبع أيًا من الاستراتيجيات ب 1 و ب 2 (وبعد ذلك لن يخسر أكثر من 4) ، واللاعب أ- الإستراتيجيات أ 1 (وبعد ذلك لن يخسر أكثر من 3). كما ترى ، فإن النتيجة هي نفسها تمامًا التي تم الحصول عليها أعلاه ، لذلك لا يهم التحليل من وجهة نظر اللاعب الذي نجريه.
8 ما هي لعبة ذات قيمة.
9. ما الذي يتكون منه مبدأ الحد الأدنى. 2. السعر الأدنى والأعلى للعبة. مبدأ Minimax
ضع في اعتبارك لعبة مصفوفة من النوع مع مصفوفة المكافآت
إذا كان اللاعب لكنسيختار استراتيجية ا، فإن كل مكاسبها الممكنة ستكون عناصر أناالصف السادس من المصفوفة من. أسوأ لاعب لكنالحال عند اللاعب فييطبق استراتيجية مناسبة ل الحد الأدنىعنصر من هذا الخط ، مكافأة اللاعب لكنسيكون مساويا للرقم.
لذلك ، من أجل الحصول على أقصى قدر من المكافأة ، اللاعب لكنتحتاج إلى اختيار إحدى الاستراتيجيات التي من أجلها العدد أقصى.
تحتوي مشكلة اتخاذ القرار ، التي يتم النظر فيها في إطار نهج النظام ، على ثلاثة مكونات رئيسية: يتم تحديد النظام ونظام التحكم الفرعي والبيئة فيه. ننتقل الآن إلى دراسة مشكلات اتخاذ القرار ، حيث لا يتأثر النظام بنظم فرعية واحدة ، بل بالعديد من أنظمة التحكم الفرعية ، ولكل منها أهدافه وإمكانياته الخاصة في العمل. يُطلق على هذا النهج في اتخاذ القرار اسم نظرية الألعاب ، ويتم استدعاء النماذج الرياضية للتفاعلات المقابلة ألعاب. نظرًا للاختلاف في أهداف أنظمة التحكم الفرعية ، فضلاً عن بعض القيود المفروضة على إمكانية تبادل المعلومات فيما بينها ، فإن هذه التفاعلات ذات طبيعة تعارض. لذلك ، فإن أي لعبة هي نموذج رياضي للصراع. نحن نقتصر على الحالة عندما يكون هناك نظامان فرعيان للتحكم. إذا كانت أهداف الأنظمة معاكسة ، يسمى الصراع معادٍ ، ويسمى النموذج الرياضي لمثل هذا الصراع لعبة معادية..
في المصطلحات النظرية للعبة ، يسمى النظام الفرعي الأول للتحكم اللاعب 1، النظام الفرعي الثاني للتحكم - اللاعب 2، مجموعات
تسمى إجراءاتهم البديلة مجموعات من الاستراتيجياتهؤلاء اللاعبين. يترك X- مجموعة من استراتيجيات اللاعب الأول ، ص- العديد من الاستراتيجيات
اللاعب 2. يتم تحديد حالة النظام بشكل فريد من خلال اختيار إجراءات التحكم من خلال النظامين الفرعيين 1 و 2 ، أي اختيار الاستراتيجيات
x∈Xو ذ∈ص. يترك F(x,ذ) - تقدير المنفعة للاعب 1 لتلك الحالة
النظام الذي يمر إليه عندما يختار اللاعب 1 إستراتيجية Xو
استراتيجية اللاعب 2 في. رقم F(x,ذ) يسمى الفوزاللاعب 1 في الحالة ( x,ذ) والوظيفة F- لاعب 1 وظيفة المردود. يفوز اللاعب
1 هو أيضًا خسارة اللاعب 2 ، أي القيمة التي يسعى اللاعب الأول إلى زيادتها ، والثاني - تقليلها. هذا ما هو عليه
مظهر من مظاهر الطبيعة العدائية للصراع: مصالح اللاعبين معاكسة تمامًا (ما يفوز به أحدهم ، ويخسر الآخر).
يتم تعيين لعبة معادية بشكل طبيعي بواسطة النظام G =(X ، Y ، F).
لاحظ أن اللعبة المعادية رسميًا يتم وضعها في الواقع بنفس طريقة مشكلة اتخاذ القرار في ظل ظروف عدم اليقين - إذا
تحديد نظام التحكم الفرعي 2 مع البيئة. الاختلاف الجوهري بين النظام الفرعي للتحكم والبيئة هو أن
سلوك الأول هادف. إذا كان لدينا ، عند تجميع نموذج رياضي لصراع حقيقي ، سبب (أو نية) لاعتبار البيئة خصمًا ، والغرض منه هو جلب
لنا أقصى قدر من الضرر ، فإن مثل هذا الموقف يمكن تمثيله على أنه لعبة معادية. بمعنى آخر ، يمكن تفسير اللعبة العدائية على أنها حالة متطرفة لـ ZPR في ظل ظروف عدم اليقين ،
تتميز بحقيقة أن البيئة يُنظر إليها على أنها خصم له هدف. في الوقت نفسه ، يجب أن نحصر أنواع الفرضيات حول سلوك البيئة.
الأكثر إثباتًا هنا هو فرضية الحذر الشديد ، عندما نعتمد ، عند اتخاذ القرار ، على أسوأ سيناريو ممكن بالنسبة لنا للتصرف في البيئة.
تعريف.اذا كان Xو صمحدودة ، ثم تسمى اللعبة العدائية المصفوفة. في لعبة المصفوفة ، يمكننا افتراض ذلك X={1,…,ن},
ص={1,…,م) و ضع aij = F.(اي جاي). وبالتالي ، يتم تحديد لعبة المصفوفة بالكامل بواسطة المصفوفة أ =(aij)، أنا=1,…,ن ، ي=1,…,م.
مثال 3.1. العب بإصبعين.
يظهر شخصان في نفس الوقت إصبعًا واحدًا أو إصبعين ويتصلان بالرقم 1 أو 2 ، والذي ، وفقًا للمتحدث ، يعني الرقم
تظهر الأصابع للآخرين. بعد إظهار الأصابع وتسمية الأرقام ، يتم توزيع المكاسب وفقًا للقواعد التالية:
إذا كان كلاهما قد خمّن أو لم يخمن كلاهما عدد الأصابع التي أظهرها الخصم ، فإن مكافأة كل منهما تساوي صفرًا ؛ إذا خمن واحد فقط بشكل صحيح ، فإن الخصم يدفع للمخمن مبلغًا من المال يتناسب مع العدد الإجمالي للظهور
هذه لعبة مصفوفة معادية. كل لاعب لديه أربع استراتيجيات: 1- أظهر إصبع واحد ويقول 1 ، 2- أظهر إصبع واحد وقل 2 ، 3-
أظهر إصبعين وقل 1 ، 4 - أظهر إصبعين وقل 2. ثم مصفوفة المكافأة أ = (aij) ، أنا = 1,…, 4، ي = 1,…, 4 يعرف على النحو التالي:
a12 = 2، a21 = - 2، a13 = a42 =–3، a24 = a31 = 3، a34 = - 4، a43 = 4، aij = 0 خلاف ذلك.
مثال 3.2. لعبة مبارزة منفصلة.
تصف المهام من نوع المبارزة ، على سبيل المثال ، صراع لاعبين ،
يريد كل منهم القيام ببعض الإجراءات لمرة واحدة (الإفراج عن شحنة من البضائع في السوق ، تطبيق للشراء في مزاد) ويختار وقتًا لذلك. دع اللاعبين يتحركون نحو بعضهم البعض نخطوات. بعد كل خطوة يتم اتخاذها ، يجوز للاعب إطلاق النار على الخصم أو عدمه. يمكن لكل شخص الحصول على طلقة واحدة فقط. ويعتقد أن احتمالية إصابة العدو إذا تقدمت بها ك n = 5 له الشكل
