لعبة صانع-محطم

لعبة الصانع -المحطم هي نوع من الألعاب الموضعية . ^{[ 1 ]}^{: 13-24} ومثل معظم الألعاب الموضعية، يتم وصفها بمجموعة مواقعها/نقاطها/عناصرها ( $X$ ) وعائلتها من مجموعات الفوز ( ${\mathcal {F}}$ - عائلة من المجموعات الفرعية من $X$ ). يتم لعبها بواسطة لاعبين، يُطلق عليهما اسم الصانع والمحطم، واللذان يتناوبان على أخذ العناصر التي لم يتم أخذها من قبل.

في لعبة الصانع-الكاسر، يفوز الصانع إذا تمكن من الاحتفاظ بجميع عناصر المجموعة الرابحة، بينما يفوز الكاسر إذا تمكن من منع ذلك، أي إذا احتفظ بعنصر واحد على الأقل في كل مجموعة رابحة. التعادل غير وارد. في كل لعبة من ألعاب الصانع-الكاسر، يمتلك إما الصانع أو الكاسر استراتيجية رابحة. السؤال البحثي الرئيسي حول هذه الألعاب هو: أي من هذين الخيارين هو الصحيح؟

أمثلة

لعبة "هيكس" مثال كلاسيكي على ألعاب "صانع-محطم" . في هذه اللعبة، تكون المجموعات الفائزة هي جميع المسارات من أعلى اللوحة إلى أسفلها. يفوز "صانع" بامتلاكه مسارًا متصلًا، بينما يفوز "محطم" بامتلاكه مسارًا متصلًا من اليسار إلى اليمين، لأنه يحجب جميع المسارات المتصلة من الأعلى إلى الأسفل.

يمكن لعب لعبة إكس-أو كلعبة صانع-مُحطِّم. هدف الصانع هو اختيار 3 مربعات متتالية، وهدف المُحطِّم هو منع الصانع من فعل ذلك. في هذا النوع، يمتلك الصانع استراتيجية فوز. وهذا يختلف عن النوع الكلاسيكي (وهو لعبة استراتيجية قوية تعتمد على الموقع ) حيث يمتلك اللاعب الثاني استراتيجية التعادل (انظر: لعبة استراتيجية قوية تعتمد على الموقع#مقارنة بلعبة صانع-مُحطِّم ).

يمكن اعتبار لعبة CNF غير المرتبة ^{[ 2 ]} على CNF إيجابي (جميع الصيغ الموجبة) بمثابة لعبة صانع-محطم حيث يريد الصانع تزييف CNF، ويريد المحطم إرضاءه.

أُجريت بعض الأبحاث حول لعب ألعاب Maker-Breaker عندما تكون لوحة اللعبة هي مجموعة الحواف $E$ من بعض الرسوم البيانية $G$ (عادةً ما تُؤخذ على أنها رسم بياني كامل )، وعائلة مجموعات الفوز هي ${\mathcal {F}}=\{E'\subset E\vert G[E']{\hbox{ له خاصية }}{\mathcal {P}}\}$ ، أين ${\mathcal {P}}$ هي خاصية من خصائص الرسم البياني (تُعتبر عادةً متزايدة بشكل رتيب [هل تحتاج إلى توضيح؟]) مثل الاتصال. ^{[ 3 ]} على سبيل المثال، لعبة تبديل شانون هي لعبة صانع-محطم حيث تكون المجموعات الفائزة هي المسارات بين رأسين مميزين.

ثنائية المُحطِّم والمُنشئ

في لعبة الصانع-المحطم، عادةً ما يبدأ الصانع اللعب أولاً. ولكن من الممكن أيضاً أن يبدأ المحطم اللعب أولاً. اللعب أولاً مفيد دائماً: أي استراتيجية فائزة للصانع الذي يلعب ثانياً ستكون في صالحه. $(X,{\mathcal {F}})$ ينتج عن ذلك استراتيجية رابحة لصانع اللعبة الذي يلعب أولاً $(X,{\mathcal {F}}).$ وينطبق الأمر نفسه على بريكر. ^{[ 1 ]}^{: 15}

علاوة على ذلك، لكل لعبة $(X,{\mathcal {F}})$ يمكننا تعريفها كلعبة عرضية $(X,{\mathcal {F^{*}}})$ حيث تمثل المجموعات الرابحة أصغر المجموعات التي تلامس كل مجموعة رابحة في اللعبة الأصلية. على سبيل المثال، إذا كانت المجموعات الرابحة في اللعبة الأصلية هي { {1,2,3},{4,5,6} }، فإنها في اللعبة الثنائية تصبح { {1,4}, {1,5}, {1,6}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6} }. وبالتالي، فإن استراتيجيات الفوز للاعب Breaker الذي يلعب أولاً هي $(X,{\mathcal {F}})$ هذه هي بالضبط استراتيجيات الفوز لصانع اللعبة الذي يلعب أولاً $(X,{\mathcal {F^{*}}})$ [ ⁴^]^:²

علاوة على ذلك، هناك اتفاقية بديلة في لعبة Misère للعبة Maker-Breaker تسمى لعبة Avoider-Enforcer .

التعقيد الحسابي

لعبة Maker-Breaker كاملة على مستوى PSPACE حتى لو اقتصر حجم كل مجموعة على 5. ^{[ 5 ]} كانت النتيجة الأولى من عام 1978 حيث اقتصر حجم كل مجموعة على 11، ^{[ 6 ]} حيث ذُكرت اللعبة على أنها $G$ (POS CNF 11). تم تحسينه لأول مرة إلى الحجم 6 في عام 2021. ^{[ 7 ]}

الاستراتيجيات

تُستخدم أنواع عديدة من الاستراتيجيات بشكل شائع لحل ألعاب Maker-Breaker.

استراتيجيات الاقتران

في بعض الألعاب، من الممكن تقسيم عناصر المجموعة X (أو مجموعة فرعية منها) إلى مجموعة من الأزواج المنفصلة. في ظل شروط معينة، يمكن للاعب الفوز باستخدام الاستراتيجية الجشعة التالية: "كلما اختار خصمك عنصرًا من الزوج i ، اختر العنصر الآخر من الزوج i ".

تختلف "الشروط المحددة" بالنسبة لصانع القرار وبالنسبة لصانع القرار؛ انظر استراتيجية الاقتران .

استراتيجيات من ألعاب التمركز القوية

كل استراتيجية رابحة للأول في لعبة استراتيجية قوية ، هي أيضاً استراتيجية رابحة لصانع القرار في نسخة صانع القرار (انظر: لعبة استراتيجية قوية#مقارنة بلعبة صانع القرار ). وبالتحديد، إذا لم يكن هناك تعادل في نسخة الاستراتيجية القوية، فإن صانع القرار يمتلك استراتيجية رابحة في نسخة صانع القرار. والعكس ليس بالضرورة صحيحاً: فاستراتيجية رابحة لصانع القرار في نسخة صانع القرار ليست بالضرورة استراتيجية رابحة للأول في النسخة القوية، إذ يمكن للثاني في النسخة القوية الفوز بادعاء مجموعة رابحة قبل الأول.

في المقابل، فإن كل استراتيجية فوز للاعب Breaker في لعبة صانع-محطم، هي أيضاً استراتيجية تعادل للاعب Second في النسخة القوية ذات الوضعية القوية.

استراتيجيات قائمة على الإمكانات

لنفترض أننا نستطيع إيجاد دالة تُعيّن لكل مجموعة فائزة قيمة محتملة بناءً على عدد العناصر التي أُخذت منها بالفعل بواسطة المُنشئ/المُحطِّم. يجب أن تُحقق دالة القيمة المحتملة الخصائص التالية:

تتراوح احتمالية الفوز بمجموعة من النقاط بين 0 و 1؛
عندما يأخذ Breaker عنصرًا، فإن إمكانات جميع المجموعات التي تحتوي عليه تنخفض إلى 0 وتبقى 0؛
عندما يأخذ Maker عنصرًا، تزداد إمكانات جميع المجموعات (غير المكسورة) التي تحتوي عليه؛
تبلغ قيمة الإمكانات لمجموعة مملوكة لصانعها 1.

ثم، يفوز الصانع إذا كان مجموع الاحتمالات أكبر من 0، ويفوز الكاسر إذا كان مجموع الاحتمالات أقل من 1. ومن ثم:

إذا كان المجموع الأولي أكبر من 0، ويمكن لصانع اللعبة أن يلعب بحيث يزداد المجموع المحتمل بشكل طفيف، فإن هذه استراتيجية رابحة لصانع اللعبة؛
إذا كان المجموع الأولي أقل من 1، ويمكن لـ Breaker أن يلعب بحيث ينخفض المجموع المحتمل بشكل طفيف، فإن هذه استراتيجية رابحة لـ Breaker.

شرط الفوز لبريكر

قدّم بول إيردوس وجون سيلفريدج شرطًا عامًا يضمن لـ Breaker استراتيجية رابحة. ^{[ 8 ]} وقد استخدما استراتيجية قائمة على الإمكانات. حدّدا إمكانية أي مجموعة رابحة (غير مكسورة). $E$ مع $|E|$ الرؤوس غير المشغولة كـ $2^{-|E|}$ إذن فإن إمكانية مجموعة يشغلها الصانع هي بالفعل $2^{-0}=1$ كلما أخذ الصانع عنصرًا، تزداد إمكانية كل مجموعة تحتوي عليه إلى $2^{-(|E|-1)}$ أي، يزيد بمقدار $2^{-|E|}$ عندما يأخذ Breaker عنصرًا، ينخفض احتمال كل مجموعة تحتوي عليه إلى 0، أي يتناقص بمقدار $2^{-|E|}$ نُسند لكل عنصر قيمة تساوي إجمالي الزيادة المحتملة في حال أخذه الصانع، أي $w(v):=\sum _{v\in E}2^{-|E|}$ تتمثل استراتيجية الفوز في لعبة Breaker في اختيار عنصر ذي قيمة قصوى . وهذا يضمن أن قيمة الإمكانية تتناقص تدريجيًا بدءًا من الدور الأول لـ Breaker. وبالتالي، إذا كانت قيمة الإمكانية في الدور الأول لـ Breaker أقل من 1، يفوز Breaker. في الدور الأول لـ Maker، يمكنه مضاعفة قيمة الإمكانية على الأكثر (عن طريق اختيار عنصر موجود في جميع مجموعات الفوز). لذلك، يكفي أن تكون قيمة الإمكانية في بداية اللعبة أقل من 1/2. باختصار، تنص نظرية إردوش-سيلفريدج على ما يلي:

لو $\sum _{E\in {\mathcal {F}}}2^{-|E|}<1/2$ ، ثم ${\mathcal {F}}$ فوز بريكر .

تُعطي النظرية شرطًا سهل التحقق منه للغاية، وعندما يتحقق هذا الشرط، فإنها تُعطي أيضًا خوارزمية فعالة لحساب الاستراتيجية المثلى لـ Breaker.

للدالة المحتملة تفسير احتمالي. احتمال مجموعة رابحة هو احتمال امتلاك "صانع" لتلك المجموعة إذا لُعبت اللعبة عشوائيًا من الآن فصاعدًا. وبالتالي، فإن مجموع الاحتمالات هو العدد المتوقع للمجموعات الرابحة التي يمتلكها "صانع" إذا لُعبت اللعبة عشوائيًا. عندما يكون مجموع الاحتمالات أقل من 1، فلا بد من وجود طريقة للعب بحيث يكون عدد المجموعات التي يمتلكها "صانع" صفرًا. من خلال ضمان بقاء مجموع الاحتمالات أقل من 1، يُزيل "المُحطِّم" عنصر العشوائية من هذا الادعاء الاحتمالي حتى يصبح حقيقة مؤكدة في نهاية اللعبة.

لاحظ أنه إذا لعب بريكر أولاً، فإن الشرط يتغير إلى $\sum _{E\in {\mathcal {F}}}2^{-|E|}<1$ .

على وجه الخصوص، إذا كانت جميع مجموعات الفوز من الحجم k (أي أن الرسم البياني الفائق للعبة منتظم من الدرجة k )، فإن نظرية إردوش-سيلفريدج تشير إلى أن لعبة Breaker تفوز كلما $|{\mathcal {F}}|<2^{k-1}$ أي أن عدد المجموعات الفائزة أقل من $2^{k-1}$ [ ⁸^]

الرقم $2^{k-1}$ ضيق: هناك $k$ - الرسوم البيانية الفائقة المنتظمة حيث يكون عدد المجموعات الفائزة بالضبط $2^{k-1}$ وحيث يمتلك Maker استراتيجية رابحة. على سبيل المثال، لنفترض شجرة ثنائية مثالية بارتفاع $k-1$ . لديه $2^{k-1}$ الأوراق. عرّف V على أنها مجموعة عقد الشجرة، وH على أنها عائلة جميع $2^{k-1}$ المسارات من الجذر إلى ورقة. يبدأ المُنشئ باختيار الجذر. ثم، إذا اختار المُكسِّر عنصرًا في الشجرة الفرعية اليسرى، يختار المُنشئ جذر الشجرة الفرعية اليمنى، والعكس صحيح. بالاستمرار بهذه الطريقة، يستطيع المُنشئ دائمًا اختيار مسار كامل، أي مجموعة فائزة.

الرسوم البيانية الفائقة المنفصلة وشبه المنفصلة

إذا كانت جميع المجموعات الفائزة منفصلة بشكل زوجي وكان حجمها 2 على الأقل، فيمكن لـ Breaker الفوز باستخدام استراتيجية الاقتران.

لنفترض الآن أن المجموعات الفائزة منفصلة تقريبًا ، أي أن أي مجموعتين فائزتين تشتركان في عنصر واحد على الأكثر. إذا كانت جميع المجموعات الفائزة بحجم $k$ وعدد المجموعات الفائزة أقل من $4^{kc{\sqrt {k}}}$ (لبعض الثوابت الثابتة c)، فإن لدى Breaker استراتيجية رابحة. ^{[ 9 ]} لذا فإن هذا الوضع أسهل بالنسبة لـ Breaker من الحالة العامة، ولكنه أصعب من حالة مجموعات الفوز المنفصلة.

شرط رابح لصانع المنتجات

عرّف درجة مجموعة من العناصر بأنها عدد المجموعات الفائزة المختلفة التي تحتوي على هذه المجموعة. عرّف درجة الزوج لعائلة مجموعات، ويرمز لها بـ $d_{2}$ ، باعتبارها الدرجة القصوى لزوج من العناصر (الدرجة القصوى على جميع الأزواج). إذا كانت جميع المجموعات الفائزة بحجم $k$ وعدد المجموعات الفائزة أكثر من $2^{k-3}\cdot d_{2}\cdot |X|$ إذن، لدى Maker استراتيجية رابحة. ^{[ 10 ]}^{: النظرية 1}

تستخدم هذه الاستراتيجية نفس دالة الإمكانات التي استخدمها إردوس وسيلفريدج: إمكانية مجموعة رابحة $E$ مع $|E|$ العناصر غير المشغولة (ولا يوجد عنصر مشغول بواسطة بريكر) هي $2^{-|E|}$ قيمة العنصر هي إجمالي الانخفاض المحتمل إذا اختاره اللاعب "المُحطِّم"، وهو نفس إجمالي الزيادة المحتملة إذا اختاره اللاعب "الصانع". وتتلخص استراتيجية اللاعب "الصانع" ببساطة في اختيار العنصر ذي القيمة الأعلى.

كلما أخذ Maker عنصرًا، تزداد احتمالية كل مجموعة فائزة تحتوي عليه بمقدار $2^{-|E|}$ كلما أخذ المُحطِّم عنصرًا، فإن احتمالية كل مجموعة تحتوي عليه ولا تحتوي على عنصر المُنشئ تتناقص بمقدار $2^{-|E|}$ لذلك، إذا اقتصرنا على المجموعات الفائزة التي تم لمسها مرة واحدة فقط، فإن المجموع المحتمل يزداد بشكل طفيف. ولا يمكن أن ينخفض المجموع المحتمل إلا بسبب المجموعات التي تحتوي على كل من عنصر المُنشئ وعنصر المُحطِّم. وتكتسب هذه المجموعات $2^{-|E|}$ لكن بعد ذلك يخسرون $2^{-(|E|-1)}$ لذا فهم يخسرون في المجمل $2^{-|E|}$ بما أن هذه المجموعات تحتوي على عنصرين على الأقل، فإن كل مجموعة منها تفقد ما لا يزيد عن ربع قيمتها. وبافتراض محدودية درجة الأزواج، فإن عدد هذه المجموعات لا يتجاوز d² . وبالتالي، بعد كل جولة، ينخفض مجموع الجهد بمقدار لا يزيد عن d² _/₄ . عدد الجولات هو |X|/2، لذا فإن الجهد النهائي أصغر من الجهد الابتدائي بمقدار لا يزيد عن $d_{2}\cdot |X|/8$ الجهد الأولي هو $|{\mathcal {F}}|\cdot 2^{-k}$ .

لو $|{\mathcal {F}}|\cdot 2^{-k}>d_{2}\cdot |X|/8$ ، الإمكانية النهائية أكبر من 0، لذلك يوجد على الأقل مجموعة فائزة واحدة بإمكانية 1. هذه المجموعة مملوكة لصانع.

الأرقام اللونية واستراتيجيات الفوز

العدد اللوني لـ ${\mathcal {F}}$ هو أقل عدد من الألوان اللازمة لتلوين عناصر X بحيث لا توجد مجموعة واحدة في ${\mathcal {F}}$ أحادي اللون. إذا كان العدد اللوني لـ ${\mathcal {F}}$ إذا كانت النتيجة 3، فإن لدى Maker استراتيجية رابحة. ^{[ 11 ]}

جدول ملخص

يلخص الجدول التالي بعض الشروط التي تضمن امتلاك أحد اللاعبين استراتيجية رابحة. يشير الشرط في عمود "التماسك" إلى متى تُعرف الرسوم البيانية الفائقة التي تتوقف عندها الاستراتيجية عن العمل.

في جميع الحالات، k هو حجم مجموعات الفوز (أي أن الرسم البياني الفائق للعبة هو k- موحد).


حالة	الفائز	ضيق	تعليقات
$\|{\mathcal {F}}\|<2^{k-1}$	كاسر ^{[ 8 ]}	$\|{\mathcal {F}}\|\geq 2^{k-1}$	استراتيجية محتملة
مجموعات الفوز المنفصلة، بحجم لا يقل عن 2	قاطع الدائرة		استراتيجية الاقتران
المجموعات شبه المنفصلة، $\|{\mathcal {F}}\|<4^{kc{\sqrt {k}}}$	كاسر ^{[ 9 ]}
درجة الزوج d ₂ ، $\|{\mathcal {F}}\|>2^{k-3}\cdot d_{2}\cdot \|X\|$	الصانع ^{[ 10 ]}		استراتيجية محتملة

لعبة كسر القواعد

من الممكن لعب لعبة يسعى فيها كلا اللاعبين إلى تحقيق هدف "الكسر" (أي امتلاك عنصر واحد على الأقل في كل مجموعة رابحة). في هذه الحالة، لا تكون اللعبة بالضرورة لعبة محصلتها صفر، بل من الممكن أن يفوز كلا اللاعبين. في الواقع، كلما امتلك "الكسر" استراتيجية رابحة في لعبة "صانع-كسر"، فمن الممكن أن يفوز كلا "الكسرين" في لعبة "كسر-كسر".

يُعدّ أحد تطبيقات هذه الاستراتيجية خوارزمية فعّالة لتلوين المخططات الفائقة. لنفترض أننا نريد تلوين رؤوس مخطط فائق منتظم من الرتبة k بلونين بحيث يُمثّل كلا اللونين في كل حافة فائقة. وقد أثبت إردوس في عام 1963، باستخدام الطريقة الاحتمالية ، أن هذا التلوين موجود كلما كان عدد الحواف الفائقة أقل من $2^{k-1}$ بمعنى آخر، يجب أن يكون الرسم البياني الفائق منتظمًا من الدرجة 2 حتى يوجد مثل هذا التلوين (انظر الخاصية ب ). ومع ذلك، لم يكن البرهان بنائيًا. باستخدام استراتيجية بريكر البنّاءة الفائزة، يمكننا تلوين الرسم البياني الفائق. ${\mathcal {F}}$ عن طريق السماح للاعبَيْن من فئة Breakers باللعب ضد بعضهما البعض باستخدام استراتيجياتهما الفائزة. سيفوز كلا اللاعبين - وبالتالي سيحصل كل لاعب على رأس واحد على الأقل في كل حافة فائقة. ^{[ 1 ]}^{: 17-20}

صنع جزئي

لنفترض أن صانع اللعبة لا يحتاج للفوز إلى شغل مجموعة الفوز بأكملها، بل يكفيه امتلاك جزء منها. متى يمكن لكاسر اللعبة أن يفوز في هذه الحالة؟

صنع جزئي مستمر

عدد العناصر في مجموعة واحدة هو m (حيث لا يمتلك اللاعب المُحطِّم أي عنصر). إذا كان حجم كل مجموعة فائزة m على الأقل، وكان عدد المجموعات أقل من $2^{m-1}$ إذاً، لا يزال لدى بريكر استراتيجية رابحة. تستخدم هذه الاستراتيجية دالة احتمالية: احتمالية المجموعة "المكسورة" هي 0، واحتمالية المجموعة غير المكسورة E هي $2^{-r(E)}$ حيث يمثل r(E) عدد العناصر التي يجب على الصانع أخذها للفوز. لذا فإن الإمكانات الأولية لكل مجموعة فائزة هي $2^{-m}$ ، وإمكانية مجموعة يشغلها الصانع هي 1. ومن هنا يكون البرهان مماثلاً لبرهان نظرية إردوس-سيلفريدج. ^{[ 10 ]}^{: اللمة 1}

التقسيم الجزئي

لنفترض أنه لكي يفوز صانع المحتوى، يحتاج فقط إلى امتلاك جزء t من العناصر في مجموعة فائزة واحدة، حيث $1/2<t\leq 1$ لذا، يحتاج Breaker إلى امتلاك نسبة أكبر من (1- t ) من النقاط في كل مجموعة. عرّف الثابت: $c_{t}:=(2t)^{t}\cdot (2-2t)^{1-t}=2\cdot t^{t}\cdot (1-t)^{1-t}$ (في الصيغة القياسية، $t=1,c_{t}\to 2$ ).

لو $\sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<1$ إذن، يمتلك اللاعب "بريكر" استراتيجية رابحة عند اللعب أولاً . ^{[ 10 ]}^{: المبرهنة 3}
لو $\sum _{E\in {\mathcal {F}}}{c_{t}}^{-|E|}<{1 \over 2-2t}$ إذن، يمتلك بريكر استراتيجية رابحة عند اللعب في المركز الثاني . ^{[ 12 ]}

على وجه الخصوص، إذا كانت جميع المجموعات بحجم k وكان عددها أقل من ${c_{t}}^{k}$ ثم يمتلك اللاعب الذي يلعب أولاً استراتيجية فائزة.

تعتمد هذه الاستراتيجية على دالة احتمالية. وتُعرَّف احتمالية مجموعة رابحة على النحو التالي: $(2t)^{-r}(2-2t)^{-s}$ حيث يُمثل r عدد العناصر التي يحتاجها المُنشئ للسيطرة على المجموعة، بينما يُمثل s عدد العناصر التي يحتاجها المُخرِج لكسرها. إذا سيطر المُنشئ على مجموعة، فإن قيمتها المُحتملة ستكون في مرحلة ما 1 على الأقل. لذلك، يفوز المُخرِج إذا تمكن من إبقاء مجموع القيم المُحتملة أقل من 1. وتتمثل استراتيجية المُخرِج في أخذ العنصر ذي القيمة الأعلى، والذي يُعرَّف بأنه مجموع القيم المُحتملة للمجموعات الفائزة التي تحتوي على هذا العنصر.

عندما يأخذ المُنشئ عنصرًا، يُضرب جهد كل مجموعة تحتوي عليه في 2t ، أي أنه يزداد بمقدار (2t - 1) ضعف الجهد الحالي. وعندما يأخذ المُحطِّم عنصرًا، يُضرب جهد كل مجموعة تحتوي عليه في (2 - 2t ) ، أي أنه يزداد بمقدار (1 - 2t ) ضعف الجهد الحالي. وعندما يلمس كل من المُحطِّم والمُنشئ نفس المجموعة، يُضرب جهدها في 2t ( 2 - 2t )، أي أنه يزداد بمقدار -(2t - 1) ضعف الجهد ^الحالي . ولأن عنصر المُحطِّم له أعلى قيمة، فإن مجموع الجهد يتناقص دائمًا. لذلك، إذا كان مجموع الجهد الأولي أقل من 1، يفوز المُحطِّم.

ألواح لا نهائية

يُصبح تعريف لعبة الصانع-المحطم أكثر دقةً عندما يكون هناك عدد لا نهائي من الرؤوس ( $|V|=\infty$ ) وعدد لا نهائي من مجموعات الفوز ( $|H|=\infty$ في هذه الحالة نقول أن لدى Breaker استراتيجية رابحة إذا كان بإمكان Breaker، لجميع j > 0، منع Maker من احتلال مجموعة رابحة بالكامل بحلول الدور j .

انظر أيضاً

مراجع

1 2 3 حيفتس، دان؛ كريفيليفيتش, مايكل ; ستوياكوفيتش، ميلوش؛ زابو، تيبور (2014). الألعاب الموضعية . ندوات أوبرولفاخ. المجلد. 44. بازل: شركة Birkhäuser Verlag GmbH. رقم ISBN 978-3-0348-0824-8.
↑ الرحمن، محمد لطفر؛ واتسون ، توماس (2018). تعقيد ألعاب CNF غير المرتبة . شلوس داجشتول - Leibniz-Zentrum fuer Informatik. دوى : 10.4230/LIPIcs.ISAAC.2018.9 . او سي ال سي 1081450453 .
↑ تشفاتال، ف.؛ إردوس، ب. (1978). "ألعاب الوضع المتحيزة". حوليات الرياضيات المتقطعة . 2 : 221-229 . doi : 10.1016/S0167-5060(08)70335-2 . ISBN 9780720410433.
^ سيرنينسكي، أندراس؛ مانديتي، سي. إيفيت؛ بلوهار، أندراس (2009). "في الألعاب الموضعية للمنتقي والمنتقي" . الرياضيات المنفصلة . 309 (16): 5141–5146 . دوى : 10.1016/j.disc.2009.03.051 . ISSN 0012-365X .
↑ كوبكه، فين (2025). "حل ألعاب الصانع-الخاسر على الرسوم البيانية الفائقة الموحدة من الدرجة 5 هو مسألة كاملة من فئة PSPACE" . المجلة الإلكترونية للتوافقية . 32 (4). doi : 10.37236/13920 .
↑ شيفر، توماس ج. (أبريل 1978). "حول تعقيد بعض ألعاب المعلومات الكاملة بين شخصين". مجلة علوم الحاسوب والنظم . 16 (2): 185-225 . doi : 10.1016/0022-0000(78)90045-4 . ISSN 0022-0000 .
↑ الرحمن، محمد لطفر؛ واتسون ، توماس (2021). بليزر، ماركوس. مونميج، بنيامين (محرران). "لعبة 6-Uniform Maker-Breaker مكتملة على PSPACE" . الندوة الدولية الثامنة والثلاثون حول الجوانب النظرية لعلوم الكمبيوتر (STACS 2021) . إجراءات لايبنيز الدولية في مجال المعلوماتية (LIPIcs). 187 . داغستوهل، ألمانيا: شلوس داغستوهل – مركز لايبنتز للمعلوماتية: 57:1–57:15. دوى : 10.4230/LIPIcs.STACS.2021.57 . رقم ISBN 978-3-95977-180-1.
1 2 3 إردوش، ب .؛ سيلفريدج، ج. ل. (1973). "حول لعبة توافقية" (ملف PDF) . مجلة نظرية التوافقية . السلسلة أ. 14 (3): 298-301 . doi : 10.1016/0097-3165(73)90005-8 . MR 0327313 .
1 2 بيك، جوزيف (1981). "حول الألعاب الموضعية" . مجلة نظرية التوافيق . السلسلة أ. 30 (2): 117-133 . doi : 10.1016/0097-3165(81)90001-7 . ISSN 0097-3165 .
1 2 3 4 بيك، جوزيف (1981). "ألعاب من نوع Van der Waerden و Ramsey". كومبيناتوريكا . 1 (2): 103-116 . دوى : 10.1007 / bf02579267 . ISSN 0209-9683 . S2CID 36276515 .
↑ هيلز، ألفريد و .؛ جويت، روبرت آي. (1963). "الانتظام والألعاب الموضعية" . معاملات الجمعية الرياضية الأمريكية . 106 (2): 222-229 . doi : 10.1090/S0002-9947-1963-0143712-1 . MR 0143712 .
↑ شياويون، لو (29-11-1991). "لعبة المطابقة" . الرياضيات المتقطعة . 94 (3): 199-207 . doi : 10.1016/0012-365X(91)90025-W . ISSN 0012-365X .

[:02-1] 1 2 3 حيفتس، دان؛ كريفيليفيتش, مايكل ; ستوياكوفيتش، ميلوش؛ زابو، تيبور (2014). الألعاب الموضعية . ندوات أوبرولفاخ. المجلد. 44. بازل: شركة Birkhäuser Verlag GmbH. رقم ISBN 978-3-0348-0824-8.

[2] الرحمن، محمد لطفر؛ واتسون ، توماس (2018). تعقيد ألعاب CNF غير المرتبة . شلوس داجشتول - Leibniz-Zentrum fuer Informatik. دوى : 10.4230/LIPIcs.ISAAC.2018.9 . او سي ال سي 1081450453 .

[ChvatalErdos1978-3] تشفاتال، ف.؛ إردوس، ب. (1978). "ألعاب الوضع المتحيزة". حوليات الرياضيات المتقطعة . 2 : 221-229 . doi : 10.1016/S0167-5060(08)70335-2 . ISBN 9780720410433.

[4] سيرنينسكي، أندراس؛ مانديتي، سي. إيفيت؛ بلوهار، أندراس (2009). "في الألعاب الموضعية للمنتقي والمنتقي" . الرياضيات المنفصلة . 309 (16): 5141–5146 . دوى : 10.1016/j.disc.2009.03.051 . ISSN 0012-365X .

[5] كوبكه، فين (2025). "حل ألعاب الصانع-الخاسر على الرسوم البيانية الفائقة الموحدة من الدرجة 5 هو مسألة كاملة من فئة PSPACE" . المجلة الإلكترونية للتوافقية . 32 (4). doi : 10.37236/13920 .

[6] شيفر، توماس ج. (أبريل 1978). "حول تعقيد بعض ألعاب المعلومات الكاملة بين شخصين". مجلة علوم الحاسوب والنظم . 16 (2): 185-225 . doi : 10.1016/0022-0000(78)90045-4 . ISSN 0022-0000 .

[7] الرحمن، محمد لطفر؛ واتسون ، توماس (2021). بليزر، ماركوس. مونميج، بنيامين (محرران). "لعبة 6-Uniform Maker-Breaker مكتملة على PSPACE" . الندوة الدولية الثامنة والثلاثون حول الجوانب النظرية لعلوم الكمبيوتر (STACS 2021) . إجراءات لايبنيز الدولية في مجال المعلوماتية (LIPIcs). 187 . داغستوهل، ألمانيا: شلوس داغستوهل – مركز لايبنتز للمعلوماتية: 57:1–57:15. دوى : 10.4230/LIPIcs.STACS.2021.57 . رقم ISBN 978-3-95977-180-1.

[es-8] 1 2 3 إردوش، ب .؛ سيلفريدج، ج. ل. (1973). "حول لعبة توافقية" (ملف PDF) . مجلة نظرية التوافقية . السلسلة أ. 14 (3): 298-301 . doi : 10.1016/0097-3165(73)90005-8 . MR 0327313 .

[:0-9] 1 2 بيك، جوزيف (1981). "حول الألعاب الموضعية" . مجلة نظرية التوافيق . السلسلة أ. 30 (2): 117-133 . doi : 10.1016/0097-3165(81)90001-7 . ISSN 0097-3165 .

[beck81-10] 1 2 3 4 بيك، جوزيف (1981). "ألعاب من نوع Van der Waerden و Ramsey". كومبيناتوريكا . 1 (2): 103-116 . دوى : 10.1007 / bf02579267 . ISSN 0209-9683 . S2CID 36276515 .

[11] هيلز، ألفريد و .؛ جويت، روبرت آي. (1963). "الانتظام والألعاب الموضعية" . معاملات الجمعية الرياضية الأمريكية . 106 (2): 222-229 . doi : 10.1090/S0002-9947-1963-0143712-1 . MR 0143712 .

[12] شياويون، لو (29-11-1991). "لعبة المطابقة" . الرياضيات المتقطعة . 94 (3): 199-207 . doi : 10.1016/0012-365X(91)90025-W . ISSN 0012-365X .

[ 2 ]

[ 3 ]

4

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 10 ]

[ 11 ]

[ 12 ]

اللغة	العربية (RTL)
روابط موسوعية	30 رابطاً
المصدر الأصلي	ويكيبيديا ↗