لعبة التكافؤ

تُلعب لعبة التكافؤ على رسم بياني مُوجَّه مُلوَّن ، حيث يُلوَّن كل عقدة وفقًا لأولوية - وهي واحدة من عدد محدود من الأعداد الطبيعية . يقوم لاعبان، 0 و1، بتحريك رمز (واحد مشترك) على طول حواف الرسم البياني. يختار مالك العقدة التي يقع عليها الرمز العقدة التالية (يقوم بالخطوة التالية). يستمر اللاعبان في تحريك الرمز، مما ينتج عنه مسار (قد يكون لانهائيًا) ، يُسمى دورة لعب.

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

تقع ألعاب التكافؤ في المستوى الثالث من التسلسل الهرمي لبوريل ، وبالتالي يتم تحديدها . ^{[ 1 ]}

استُخدمت الألعاب المرتبطة بألعاب التكافؤ ضمنيًا في برهان رابين على قابلية حسم نظرية الرتبة الثانية الأحادية لـ n من الخلفاء ( S2S لـ n = 2)، حيث تم إثبات حتمية هذه الألعاب. ^{[ 2 ]} تؤدي نظرية كناستر-تارسكي إلى برهان بسيط نسبيًا على حتمية ألعاب التكافؤ. ^{[ 3 ]}

علاوة على ذلك، تُحدد نتائج ألعاب التكافؤ بمعزل عن تاريخ اللعب. ^{[ 3 ] [ 4 ] [ 5 ]} وهذا يعني أنه إذا كان لدى اللاعب استراتيجية رابحة، فإن هذه الاستراتيجية تعتمد فقط على وضعية رقعة اللعب الحالية، وليس على تاريخ اللعب.

حلّ لعبة التكافؤ على رسم بياني محدود يعني تحديد أيّ اللاعبين يمتلك استراتيجية رابحة، انطلاقًا من وضعية بداية معينة. وقد ثبت أن هذه المسألة تندرج ضمن فئتي NP و co-NP ، وتحديدًا UP و co-UP، ^{[ 6 ]} وكذلك ضمن فئة QP ( زمن شبه متعدد الحدود ). ^{[ 7 ]} ويبقى السؤال مطروحًا حول إمكانية حلّ هذه المسألة في زمن P.

بما أن ألعاب التكافؤ تُحدد دون الاعتماد على التاريخ، فإن حل لعبة تكافؤ معينة يُكافئ حل المسألة البسيطة ظاهريًا التالية في نظرية الرسم البياني. لنفترض وجود رسم بياني ثنائي الأجزاء ملون وموجه محدود يحتوي على n رأسًا${\displaystyle V=V_{0}\cup V_{1}}$وإذا كانت V ملونة بألوان من 1 إلى m ، فهل توجد دالة اختيار تحدد حافة واحدة خارجة من كل رأس من رؤوس V؟${\displaystyle V_{0}}$، بحيث يكون للرسم البياني الفرعي الناتج خاصية أن اللون الأكثر تكرارًا في كل دورة يكون زوجيًا.

قدّم زيلونكا خوارزمية تكرارية لحل ألعاب التكافؤ. لنفترض${\displaystyle G=(V,V_{0},V_{1},E,\Omega )}$تكون لعبة متكافئة، حيث${\displaystyle V_{0}}$على التوالي.${\displaystyle V_{1}}$هي مجموعات العقد التي تنتمي إلى اللاعب 0 أو 1،${\displaystyle V=V_{0}\cup V_{1}}$هي مجموعة جميع العقد،${\displaystyle E\subseteq V\times V}$هي المجموعة الكاملة للحواف، و${\displaystyle \Omega :V\rightarrow \mathbb {N} }$هي دالة تحديد الأولويات.

تعتمد خوارزمية زيلونكا على ترميز الجاذبات. لنفترض${\displaystyle U\subseteq V}$لتكن مجموعة من العقد و${\displaystyle i=0,1}$كن لاعبًا. جاذب i للمجموعة U هو أصغر مجموعة من العقد${\displaystyle Attr_{i}(U)}$يحتوي على U بحيث يمكنني فرض زيارة إلى U من كل عقدة في${\displaystyle Attr_{i}(U)}$يمكن تعريفها من خلال حساب النقطة الثابتة:

${\displaystyle {\begin{aligned}Attr_{i}(U)^{0}&:=U\\Attr_{i}(U)^{j+1}&:=Attr_{i}(U)^{j}\cup \{v\in V_{i}\mid \exists (v,w)\in E:w\in Attr_{i}(U)^{j}\}\cup \{v\in V_{1-i}\mid \forall (v,w)\in E:w\in Attr_{i}(U)^{j}\}\\Attr_{i}(U)&:=\bigcup _{j=0}^{\infty }Attr_{i}(U)^{j}\end{aligned}}}$

بمعنى آخر، يبدأ المرء بالمجموعة الأولية U. ثم، لكل خطوة (${\displaystyle Attr_{i}(U)^{j+1}}$) يضيف المرء جميع العقد التابعة للاعب 0 والتي يمكنها الوصول إلى المجموعة السابقة (${\displaystyle Attr_{i}(U)^{j}}$) بحافة واحدة وجميع العقد التي تنتمي إلى اللاعب 1 والتي يجب أن تصل إلى المجموعة السابقة (${\displaystyle Attr_{i}(U)^{j}}$) بغض النظر عن الحافة التي يختارها اللاعب 1.

تعتمد خوارزمية زيلونكا على انحدار متكرر لعدد الأولويات. إذا كانت الأولوية القصوى تساوي صفرًا، فمن الواضح أن اللاعب صفر يفوز باللعبة بأكملها (بأي استراتيجية). وإلا، فلنفترض أن p هي الأكبر ولنفترض${\displaystyle i=p{\bmod {2}}}$ليكن اللاعب المرتبط بالأولوية.${\displaystyle U=\{v\mid \Omega (v)=p\}}$لتكن مجموعة العقد ذات الأولوية p ولتكن${\displaystyle A=Attr_{i}(U)}$ليكن A هو الجاذب المقابل للاعب i . يمكن للاعب i الآن أن يضمن أن كل جولة تزور A بشكل لا نهائي من المرات يفوز بها اللاعب i .

لنأخذ اللعبة كمثال${\displaystyle G'=G\setminus A}$حيث تتم إزالة جميع العقد والحواف المتأثرة من المجموعة A. يمكننا الآن حل اللعبة الأصغر${\displaystyle G'}$باستخدام التكرار والحصول على زوج من المجموعات الفائزة${\displaystyle W'_{i},W'_{1-i}}$. لو${\displaystyle W'_{1-i}}$إذا كان فارغًا، فكذلك${\displaystyle W_{1-i}}$بالنسبة للعبة G ، لأن اللاعب${\displaystyle 1-i}$لا يسع المرء إلا أن يقرر الهروب من${\displaystyle W_{i}'}$إلى A مما يؤدي أيضًا إلى فوز اللاعب i .

وإلا، إذا${\displaystyle W'_{1-i}}$ليس فارغًا، كل ما نعرفه على وجه اليقين هو أن اللاعب${\displaystyle 1-i}$يمكن الفوز على${\displaystyle W'_{1-i}}$بصفتي لاعبًا، لا أستطيع الهروب من${\displaystyle W'_{1-i}}$إلى A (لأن A جاذب من النوع i ). لذلك نحسب الجاذب${\displaystyle B=Attr_{1-i}(W'_{1-i})}$ثم قم بإزالته من G للحصول على اللعبة الأصغر${\displaystyle G''=G\setminus B}$نقوم بحلها مرة أخرى باستخدام الاستدعاء الذاتي ونحصل على زوج من المجموعات الفائزة${\displaystyle W''_{i},W''_{1-i}}$ويترتب على ذلك أن${\displaystyle W_{i}=W''_{i}}$و${\displaystyle W_{1-i}=W''_{1-i}\cup B}$.

في لغة شبه رمزية بسيطة ، يمكن التعبير عن الخوارزمية على النحو التالي:

وظيفة${\displaystyle solve(G)}$p := الأولوية القصوى في G إذا${\displaystyle p=0}$يعود${\displaystyle W_{0},W_{1}:=V,\{\}}$وإلا U := العقد في G ذات الأولوية p${\displaystyle i:=p{\bmod {2}}}$${\displaystyle A:=Attr_{i}(U)}$${\displaystyle W_{0}',W_{1}':=solve(G\setminus A)}$لو${\displaystyle W_{1-i}'=\{\}}$يعود${\displaystyle W_{i},W_{1-i}:=V,\{\}}$${\displaystyle B:=Attr_{1-i}(W_{1-i}')}$${\displaystyle W_{0}'',W_{1}'':=solve(G\setminus B)}$يعود${\displaystyle W_{i},W_{1-i}:=W_{i}'',W_{1-i}''\cup B}$

يؤدي تعديل طفيف على اللعبة المذكورة أعلاه، والمسألة المرتبطة بها في نظرية الرسم البياني، إلى جعل حل اللعبة من المسائل الصعبة حسابيًا (NP-hard) . تتضمن اللعبة المعدلة شرط قبول رابين ، وبالتالي يُلوَّن كل رأس بمجموعة من الألوان بدلًا من لون واحد. وبناءً على ذلك، نقول إن الرأس v له اللون j إذا كان اللون j ينتمي إلى مجموعة ألوان v . تكون اللعبة اللانهائية رابحة للاعب 0 إذا وُجد رأس i بحيث يكون عدد لا نهائي من الرؤوس في اللعبة له اللون 2i ، بينما يكون عدد محدود منها له اللون 2i+1 .

لاحظ أنه على عكس ألعاب التكافؤ، فإن هذه اللعبة لم تعد متناظرة بالنسبة للاعبين 0 و  1.

على الرغم من أهميتها في نظرية التعقيد، يُمكن اعتبار حلّ لعبة التكافؤ بمثابة الخوارزمية الأساسية لحلّ مشاكل التحقق الآلي وتصميم المتحكمات. فعلى سبيل المثال، من المعروف أن مشكلة التحقق من النموذج لحساب التفاضل والتكامل الموجه (μ-calculus) تُكافئ حلّ لعبة التكافؤ. كما يُمكن اختزال مشاكل القرار، مثل الصلاحية أو الإرضاء في المنطق الموجه ، إلى حلّ لعبة التكافؤ.

• إريك غرادل، فوكيون ج. كولايتيس، ليونيد ليبكين ، مارتن ماركس، جويل سبنسر ، موشيه ي. فاردي ، يدي فينيما، سكوت واينشتاين (2007). نظرية النموذج المحدود وتطبيقاتها . سبرينغر. ISBN 978-3-540-00428-8.{{cite book}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

• إي. غرادل، دبليو. توماس، تي. ويلك (محررون)  : الأوتوماتا، والمنطق، والألعاب اللانهائية ، سلسلة محاضرات سبرينغر في علوم الحاسوب 2500 (2003)، رقم ISBN 3-540-00388-6
• دبليو. زيلونكا  : الألعاب اللانهائية على الرسوم البيانية ذات الألوان المحدودة مع تطبيقات على الأوتوماتا على الشجرة اللانهائية ، TCS، 200(1-2):135-183، 1998

تتضمن مجموعتا الأدوات المتطورتان لحل لعبة التكافؤ ما يلي:

• مجموعة PGSolver
• أوينك