الدرس 2 من 2 · نظرية الألعاب
الألعاب الصفرية ومبرهنة Minimax والشبكات التنافسية Zero-Sum Games, Minimax and GANs
في اللعبة الصفرية ما يكسبه لاعب يخسره الآخر؛ مبرهنة Minimax تضمن أن \(\max\min = \min\max\) بالاستراتيجيات المختلطة، والشبكات التوليدية التنافسية لعبة صفرية بين مولّد ومميّز، والانحدار-الصعود التدرجي المتزامن قد يدور أو يتباعد حول التوازن بدل التقارب.
محتويات الدرس
1 مقدمة
المولّد في GAN يحاول خداع المميّز، والمميّز يحاول كشف المزيف. ما يكسبه أحدهما يخسره الآخر. هذا هيكل اللعبة الصفرية، وهو يفسر لماذا تدريب GANs مختلف جذرياً عن تصغير دالة خسارة واحدة.
الأهداف التعليمية
- حساب maximin وminimax ونقطة السرج
- حل لعبة صفرية 2×2 بالاستراتيجيات المختلطة
- كتابة هدف GAN واشتقاق المميّز الأمثل
- تحليل الانحدار-الصعود التدرجي على \(f(x, y) = xy\)
2 لماذا ندرس هذا الموضوع؟
هدف GAN الأصلي (Goodfellow وآخرون، 2014) مسألة min-max. والتدريب التنافسي (Adversarial Training) لجعل النماذج متينة ضد الهجمات مسألة min-max أيضاً. وفهم ديناميكيات التدرج في الألعاب يفسر عدم استقرار تدريب GANs وظواهر مثل الدوران حول التوازن.
3 الشرح النظري
اللعبة الصفرية
عائد الثاني سالب عائد الأول: \(B = -A\). الأول يعظم A والثاني يصغرها. أفضل ما يضمنه الأول باستراتيجية خالصة \(\max_i\min_j A_{ij}\) (maximin)، وأفضل ما يضمنه الثاني \(\min_j\max_i A_{ij}\) (minimax)، ودائماً \(\text{maximin} \le \text{minimax}\).
نقطة السرج
إذا تساويا وُجدت نقطة سرج: عنصر هو الأصغر في صفه والأكبر في عموده. في \(\begin{bmatrix}4&2\\3&1\end{bmatrix}\) العنصر 2 نقطة سرج وقيمة اللعبة 2.
مبرهنة Minimax
لفون نيومان (1928): بالاستراتيجيات المختلطة يتساوى الطرفان دائماً:
\[\max_{p}\min_{q} p^\top A q = \min_{q}\max_{p} p^\top A q = v\]
لـ \(A = \begin{bmatrix}3&-1\\-2&1\end{bmatrix}\): maximin الخالص \(-1\) وminimax الخالص 1، أما بالخلط فالقيمة \(v = 1/7\) و\(p^* = 3/7\).
GAN لعبة صفرية
\[\min_G \max_D\; \mathbb E_{x\sim p_{\text{data}}}[\log D(x)] + \mathbb E_{z}[\log(1 - D(G(z)))]\]
لمولّد ثابت يكون المميّز الأمثل \(D^*(x) = \frac{p_{\text{data}}(x)}{p_{\text{data}}(x) + p_g(x)}\)، وبالتعويض يصبح هدف المولّد \(-\log 4 + 2\,\mathrm{JSD}(p_{\text{data}}\|p_g)\)، فقيمته الصغرى \(-\log 4\) عندما \(p_g = p_{\text{data}}\) وعندها \(D^* = 1/2\) في كل مكان.
ديناميكيات التدرج في الألعاب
على أبسط لعبة \(f(x, y) = xy\) (x يصغر و y يعظم) التوازن \((0, 0)\). التحديث المتزامن:
\[x_{t+1} = x_t - \eta y_t,\qquad y_{t+1} = y_t + \eta x_t\]
هو دوران مع تكبير: البعد عن الأصل يُضرب في \(\sqrt{1 + \eta^2}\) كل خطوة، فيتباعد المسار حلزونياً. أما التحديث المتناوب (y يستخدم x الجديدة) فيبقي المسار على مدار مغلق تقريباً. لذلك تُستخدم في GANs تقنيات مثل التحديث المتناوب ومعدلات تعلم مختلفة والتنظيم.
4 التعريفات الرياضية
- اللعبة الصفرية
- لعبة مجموع عوائد لاعبيها صفر في كل نتيجة.\[B=-A\]
- نقطة السرج
- عنصر هو الأصغر في صفه والأكبر في عموده، فيتساوى عنده maximin وminimax.
- قيمة اللعبة
- العائد المضمون للاعب الأول عندما يلعب الطرفان استراتيجيتيهما المثلى.\[v=\max_p\min_q p^\top Aq\]
- الشبكة التوليدية التنافسية
- مولّد ومميّز يُدرَّبان معاً في لعبة min-max.
- اللعبة الصفرية (Zero-Sum Game)
- لعبة يساوي فيها كسب أحد اللاعبين خسارة الآخر.\[B=-A\]
- مبرهنة Minimax (Minimax Theorem)
- بالاستراتيجيات المختلطة يتساوى maximin وminimax في الألعاب الصفرية المنتهية.\[\max_p\min_q p^\top Aq=\min_q\max_p p^\top Aq\]
- هدف الشبكة التنافسية (GAN Objective)
- لعبة min-max بين مولّد ومميّز حلها \(p_g = p_{\text{data}}\).\[\min_G\max_D\mathbb E[\log D]+\mathbb E[\log(1-D(G(z)))]\]
5 المعادلات
6 مثال محلول خطوة بخطوة
لعبة مختلطة
المسألة: حل اللعبة الصفرية \(A = \begin{bmatrix}3&-1\\-2&1\end{bmatrix}\).
- لا نقطة سرج: maximin = −1 وminimax = 1.
- \(d = 3 + 1 + 2 + 1 = 7\)، \(p^* = (1 + 2)/7 = 3/7\).
- \(v = (3 \cdot 1 - (-1)(-2))/7 = 1/7\).
النتيجة: \(v = 1/7\)، \(p^* = 3/7\)
المميّز الأمثل
المسألة: عند نقطة x تكون \(p_{\text{data}}(x) = 0.6\) و\(p_g(x) = 0.2\). ما \(D^*(x)\)؟
- \(D^* = 0.6/(0.6 + 0.2)\).
النتيجة: \(D^* = 0.75\)
تباعد التدرج
المسألة: بـ \(\eta = 0.1\)، بكم يُضرب البعد عن التوازن في كل خطوة متزامنة على \(xy\)؟
- \(\sqrt{1 + 0.01}\).
النتيجة: \(\approx 1.00499\)، فبعد 100 خطوة يتضاعف تقريباً 1.64 مرة
7 تطبيق عملي في الذكاء الاصطناعي
- الشبكات التوليدية التنافسية: المولّد والمميّز يلعبان لعبة min-max، وتدريبهما بحثٌ عن توازنها.
- التدريب التنافسي: لجعل المصنف متيناً نحل \(\min_\theta \max_{\|\delta\| \le \epsilon} L(x + \delta)\).
- الألعاب ذات الوكلاء: خوارزميات لعب الشطرنج والبوكر تبحث عن استراتيجيات Minimax أو تقريبات لتوازن ناش.
8 مختبر تفاعلي مرتبط بالدرس
ألعاب ثنائية بمصفوفتي عوائد مع توازنات ناش الخالصة والمختلطة ودالتي أفضل استجابة، والألعاب الصفرية ومبرهنة Minimax، وديناميكيات التعلم: الانحدار-الصعود التدرجي المتزامن والمتناوب واللعب الوهمي.
افتح مختبر نظرية الألعاب9 تمارين تدريبية
أسئلة مراجعة للتفكير
- لماذا يكون \(D^* = 1/2\) عند التوازن في GAN؟
- لماذا يتباعد التحديث المتزامن على \(xy\)؟
أخطاء شائعة
- معاملة تدريب GAN كتصغير خسارة واحدة وانتظار تناقصها الرتيب.
- افتراض وجود نقطة سرج خالصة في كل لعبة صفرية.
- الظن أن الانحدار-الصعود المتزامن يتقارب دائماً إلى التوازن.
- نسيان أن الاستراتيجيات المختلطة ضرورية لمساواة maximin وminimax.
10 ملخص الدرس
- في اللعبة الصفرية maximin ≤ minimax.
- بالخلط يتساويان (مبرهنة Minimax).
- هدف GAN min-max وحله \(p_g = p_{\text{data}}\).
- التدرج المتزامن يدور ويتباعد حول التوازن في أبسط الألعاب.
11 اختبار قصير
5 أسئلة · 10 دقائق · النجاح من 60% — اجتيازه يُكمل الدرس.
