لعبة عامة

سودوكو (4×4)

سودوكو (9×9)

سودوكو (25×25)

تتضمن لعبة سودوكو العامة ألغازًا بأحجام مختلفة

في نظرية التعقيد الحسابي ، تُعرَّف اللعبة المعممة بأنها لعبة أو لغز تم تعميمه بحيث يمكن لعبه على لوحة أو شبكة بأي حجم. على سبيل المثال، الشطرنج المعمم هو لعبة الشطرنج التي تُلعب على $n\times n$ لوح، مع $2n$ قطع على كل جانب. تشمل لعبة سودوكو العامة ألعاب سودوكو مبنية على $n\times n$ شبكة.

تدرس نظرية التعقيد الصعوبة التقاربية للمسائل، لذلك هناك حاجة إلى تعميمات للألعاب، حيث أن الألعاب على حجم ثابت للوحة هي مسائل محدودة.

بالنسبة للعديد من الألعاب المعممة التي تستمر لعدد من الحركات يتناسب مع حجم رقعة الشطرنج، فإن مسألة تحديد ما إذا كان هناك فوز للاعب الأول في وضع معين هي مسألة كاملة من فئة PSPACE . وتُعدّ كل من لعبة hex المعممة ولعبة reversi من المسائل الكاملة من فئة PSPACE. ^{[ 1 ]}^{[ 2 ]}

في العديد من الألعاب العامة التي قد تستغرق عددًا من النقلات يتناسب أُسّيًا مع حجم الرقعة، تُعدّ مسألة تحديد ما إذا كان هناك فوز للاعب الأول في وضعية معينة مسألة كاملة من حيث الوقت المُعطى (EXPTIME-complete) . الشطرنج العام ، ولعبة غو (بقواعد كو اليابانية)، ولعبة كويكسو ، ^{[ 3 ]} ولعبة الداما، كلها مسائل كاملة من حيث الوقت المُعطى (EXPTIME-complete). ^{[ 4 ]}^{[ 5 ]}^{[ 6 ]}

انظر أيضاً

مراجع

^ رايش ، ستيفان (1981)، “Hex ist PSPACE-vollständig”، Acta Informatica ، 15 (2): 167–191 ، دوى : 10.1007 / bf00288964 ، S2CID 9125259
^ ايواتا، شيغيكي؛ تاكومي كاساي (يناير 1994)، “لعبة عطيل على أحد $n\times n$ "لوحة كاملة في فضاء PSPACE"، مجلة علوم الحاسوب النظرية ، 123 (2): 329-340 ، doi : 10.1016/0304-3975(94)90131-7
^ ميشيبا، شوهي. تاكيناجا ، ياسوهيكو (2020/07/02). "QUIXO مكتمل EXPTIME" . خطابات معالجة المعلومات . 162 105995. دوى : 10.1016/j.ipl.2020.105995 . ISSN 0020-0190 .
↑ فرانكل، أفيزري س.؛ ليختنشتاين، ديفيد (سبتمبر 1981)، "حساب استراتيجية مثالية لـ $n\times n$ يتطلب الشطرنج وقتًا متزايدًا بشكل كبير $n$ «، مجلة نظرية التوافيق ، السلسلة أ، 31 (2): 199– 214، doi : 10.1016/0097-3165(81)90016-9
↑ روبسون، جيه إم ( 1983)، "تعقيد لعبة جو"، وقائع المؤتمر العالمي التاسع للحاسوب التابع للاتحاد الدولي لمعالجة المعلومات : 413-417
↑ روبسون، جيه إم (مايو 1984)، " $N$ بواسطة $N$ "لعبة الداما كاملة من حيث الوقت المستغرق"، مجلة SIAM للحوسبة ، 13 (2)، جمعية الرياضيات الصناعية والتطبيقية (SIAM): 252-267 ، doi : 10.1137/0213018

[1] رايش ، ستيفان (1981)، “Hex ist PSPACE-vollständig”، Acta Informatica ، 15 (2): 167–191 ، دوى : 10.1007 / bf00288964 ، S2CID 9125259

[2] ايواتا، شيغيكي؛ تاكومي كاساي (يناير 1994)، “لعبة عطيل على أحد $n\times n$ "لوحة كاملة في فضاء PSPACE"، مجلة علوم الحاسوب النظرية ، 123 (2): 329-340 ، doi : 10.1016/0304-3975(94)90131-7

[3] ميشيبا، شوهي. تاكيناجا ، ياسوهيكو (2020/07/02). "QUIXO مكتمل EXPTIME" . خطابات معالجة المعلومات . 162 105995. دوى : 10.1016/j.ipl.2020.105995 . ISSN 0020-0190 .

[4] فرانكل، أفيزري س.؛ ليختنشتاين، ديفيد (سبتمبر 1981)، "حساب استراتيجية مثالية لـ $n\times n$ يتطلب الشطرنج وقتًا متزايدًا بشكل كبير $n$ «، مجلة نظرية التوافيق ، السلسلة أ، 31 (2): 199– 214، doi : 10.1016/0097-3165(81)90016-9

[5] روبسون، جيه إم ( 1983)، "تعقيد لعبة جو"، وقائع المؤتمر العالمي التاسع للحاسوب التابع للاتحاد الدولي لمعالجة المعلومات : 413-417

[6] روبسون، جيه إم (مايو 1984)، " $N$ بواسطة $N$ "لعبة الداما كاملة من حيث الوقت المستغرق"، مجلة SIAM للحوسبة ، 13 (2)، جمعية الرياضيات الصناعية والتطبيقية (SIAM): 252-267 ، doi : 10.1137/0213018

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

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