تعقيد اللعبة

تقيس نظرية الألعاب التوافقية تعقيد اللعبة بعدة طرق:

تعقيد فضاء الحالة (عدد المواقف القانونية في اللعبة انطلاقاً من الموقف الأولي)
حجم شجرة اللعبة (إجمالي عدد الألعاب الممكنة)
تعقيد القرار (عدد العقد الطرفية في أصغر شجرة قرار للموقع الأولي)
تعقيد شجرة اللعبة (عدد العقد الطرفية في أصغر شجرة قرار كاملة العرض للموقع الأولي)
التعقيد الحسابي (الصعوبة التقاربية للعبة عندما تصبح كبيرة بشكل تعسفي)

تتضمن هذه التدابير فهم مواقف اللعبة، والنتائج المحتملة، والتعقيد الحسابي لسيناريوهات اللعبة المختلفة.

مقاييس تعقيد اللعبة

تعقيد فضاء الحالة

تعقيد فضاء الحالة للعبة هو عدد أوضاع اللعبة القانونية التي يمكن الوصول إليها من الوضع الأولي للعبة. ^{[ 1 ]}

عندما يكون من الصعب جدًا حساب ذلك، يمكن غالبًا حساب الحد الأعلى عن طريق حساب (بعض) المواقف غير القانونية (المواقف التي لا يمكن أن تنشأ أبدًا أثناء اللعبة).

حجم شجرة اللعبة

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

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

بالنسبة للألعاب التي لا يكون فيها عدد الحركات محدودًا (على سبيل المثال بحجم اللوحة، أو بقاعدة حول تكرار الوضع) فإن شجرة اللعبة تكون بشكل عام لا نهائية.

أشجار القرار

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

تستخدم الطريقتان التاليتان لقياس تعقيد اللعبة أشجار القرار:

تعقيد القرار

تعقيد القرار في اللعبة هو عدد العقد الطرفية في أصغر شجرة قرار تحدد قيمة الوضع الأولي.

تعقيد شجرة اللعبة

تعقيد شجرة اللعبة هو عدد العقد الطرفية في أصغر شجرة قرار كاملة العرض تُحدد قيمة الموضع الابتدائي. ^{[ 1 ]} تشمل الشجرة كاملة العرض جميع العقد عند كل عمق. هذا تقدير لعدد المواضع التي يجب تقييمها في بحث المينيماكس لتحديد قيمة الموضع الابتدائي.

يصعب حتى تقدير تعقيد شجرة اللعبة، ولكن بالنسبة لبعض الألعاب، يمكن إعطاء تقريب بواسطة $GTC\geq b^{d}$ ، حيث يمثل $b$ عامل التفرع المتوسط للعبة ، و $d$ هو عدد الصفوف في لعبة متوسطة.

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

يصف التعقيد الحسابي للعبة الصعوبة التقاربية للعبة عندما تكبر بشكل تعسفي، ويُعبَّر عنه برمز Big O أو بانتمائها إلى فئة تعقيد معينة . لا ينطبق هذا المفهوم على ألعاب محددة، بل على الألعاب التي عُمِّمت بحيث يمكن جعلها كبيرة بشكل تعسفي، عادةً بلعبها على رقعة n × n . (من وجهة نظر التعقيد الحسابي، تُعتبر اللعبة على رقعة ذات حجم ثابت مسألة محدودة يمكن حلها في O(1)، على سبيل المثال باستخدام جدول بحث من المواضع إلى أفضل نقلة في كل موضع).

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

ستستخدم استراتيجية minimax ذات العمق أولاً وقت حساب يتناسب مع تعقيد شجرة اللعبة (لأنها يجب أن تستكشف الشجرة بأكملها)، وكمية من الذاكرة متعددة الحدود في لوغاريتم تعقيد الشجرة (لأن الخوارزمية يجب أن تخزن دائمًا عقدة واحدة من الشجرة في كل عمق حركة ممكن، وعدد العقد في أعلى عمق حركة هو بالضبط تعقيد الشجرة).
سيستخدم الاستقراء العكسي كلاً من الذاكرة والوقت بما يتناسب مع تعقيد فضاء الحالة، حيث يجب عليه حساب وتسجيل الحركة الصحيحة لكل وضع ممكن.

مثال: لعبة إكس أو (الدوائر والعلامات)

في لعبة إكس-أو ، الحد الأعلى البسيط لحجم فضاء الحالات هو 3 ^{× 9} = 19683. (يوجد ثلاث حالات لكل خلية من الخلايا التسع). يشمل هذا العدد العديد من المواضع غير القانونية، مثل موضع يحتوي على خمسة علامات × ولا يحتوي على أي علامة صفر، أو موضع يمتلك فيه كلا اللاعبين صفًا من ثلاث علامات. وبحساب أدق، مع استبعاد هذه المواضع غير القانونية، نحصل على 5478. ^{[ 2 ]}^{[ 3 ]} وعند اعتبار دوران المواضع وانعكاسها متطابقين، لا يتبقى سوى 765 موضعًا مختلفًا جوهريًا.

لتحديد حدود شجرة اللعبة، توجد 9 حركات ابتدائية محتملة، و8 ردود محتملة، وهكذا، بحيث يكون هناك على الأكثر 9! أو 362,880 لعبة إجمالاً. مع ذلك، قد تستغرق بعض الألعاب أقل من 9 حركات لحلها، ويُعطينا تعداد دقيق 255,168 لعبة محتملة. وعند اعتبار دوران وانعكاس المواضع متماثلين، يتبقى 26,830 لعبة محتملة فقط.

تعتمد التعقيدية الحسابية للعبة إكس-أو على كيفية تعميمها . أحد التعميمات الطبيعية هو ألعاب من نوع m ، n ، k : تُلعَب على لوحة m × n ، ويكون الفائز هو أول لاعب يُحقق k صفًا متتاليًا. يمكن حل هذه اللعبة في فضاء DSPACE ( mn ) من خلال البحث في شجرة اللعبة بأكملها. هذا يضعها في فئة التعقيد المهمة PSPACE ؛ وبمزيد من العمل، يمكن إثبات أنها PSPACE-complete . ^{[ 4 ]}

تعقيدات بعض الألعاب المعروفة

نظراً لتعقيدات الألعاب الكبيرة، يوضح هذا الجدول الحد الأقصى للوغاريتماتها للأساس 10 (أي عدد الأرقام). يجب التعامل مع جميع الأرقام التالية بحذر: فالتغييرات الطفيفة ظاهرياً في قواعد اللعبة قد تُغير هذه الأرقام (التي غالباً ما تكون تقديرات تقريبية) بشكل كبير، وقد تكون هذه التغييرات أكبر بكثير من الأرقام الموضحة.

لعبة	حجم اللوحة (المواقع)	تعقيد فضاء الحالة ( كلوغاريتم للأساس 10)	تعقيد شجرة اللعبة ( كلوغاريتم للأساس 10)	متوسط مدة المباراة ( طبقات )	عامل التفرع	مرجع	فئة تعقيد لعبة معممة مناسبة
لعبة إكس أو	9	3	5	9	4		PSPACE-complete ^{[ 5 ]}
سيم	15	3	8	14	3.7		PSPACE-complete ^{[ 6 ]}
البنتومينو	64	12	18	10	75	^{[ 7 ]}^{[ 8 ]}	؟، ولكن في PSPACE
توصيل أربعة	42	12 (4,531,985,219,092)	21	36	4	^{[ 1 ]}^{[ 9 ]}^{[ 10 ]}	؟، ولكن في PSPACE
كالاه ^{[ 11 ]}	14	13	18		50	^{[ 7 ]}	التعميم غير واضح
متسلط (8 × 8)	64	15	27	30	8	^{[ 7 ]}	؟، ولكن في فضاء P ؛ في فضاء P لأبعاد معينة ^{[ 12 ]}
كونغكاك	14	15	33			^{[ 7 ]}
لعبة الداما الإنجليزية (8x8) (الداما)	32	20 أو 18	40	70	2.8	^{[ 1 ]}^{[ 13 ]}^{[ 14 ]}	EXPTIME-complete ^{[ 15 ]}
أواري ^{[ 16 ]}	12	12	32	60	3.5	^{[ 1 ]}	التعميم غير واضح
كيوبيك	64	30	34	20	54.2	^{[ 1 ]}	PSPACE-complete ^{[ 5 ]}
جسر مزدوج وهمي ^{[ ملاحظة 1 ]}	(52)	أقل من 17 عامًا	أقل من 40	52	5.6		PSPACE-complete ^{[ 17 ]}
فانورونا	45	21	46	44	11	^{[ 18 ]}	؟، ولكن في وقت التجربة
لعبة موريس التسعة رجال	24	10	50	50	10	^{[ 1 ]}	؟، ولكن في وقت التجربة
تابلوت	81	27				^{[ 19 ]}
لعبة الداما الدولية (10x10)	50	30	54	90	4	^{[ 1 ]}	EXPTIME-complete ^{[ 15 ]}
لعبة الداما الصينية (مجموعتان)	121	23			180	^{[ 20 ]}	EXPTIME -complete ^{[ 21 ]}
لعبة الداما الصينية (6 مجموعات)	121	78			600	^{[ 20 ]}	EXPTIME -complete ^{[ 21 ]}
ريفيرسي (عطيل)	64	28	58	58	10	^{[ 1 ]}	PSPACE-complete ^{[ 22 ]}
لعبة OnTop (لعبة أساسية لشخصين)	72	88	62	31	23.77	^{[ 23 ]}
خطوط العمل	64	23	64	44	29	^{[ 24 ]}	؟، ولكن في وقت التجربة
غوموكو (15x15، أسلوب حر)	225	105	70	30	210	^{[ 1 ]}	PSPACE-complete ^{[ 5 ]}
سداسي (11x11)	121	57	98	50	96	^{[ 7 ]}	PSPACE-complete ^{[ 5 ]}
الشطرنج	64	44	123	70	35	^{[ 25 ]}	EXPTIME-complete (بدون قاعدة السحب المكونة من 50 نقلة ) ^{[ 26 ]}
بيجيويلد وكاندي كراش (8x8)	64	أقل من 50			70	^{[ 27 ]}	NP-hard
صندوق معاشات التقاعد الحكومي الهندي	37	25	132	90	29.3	^{[ 28 ]}
كونكت 6	361	172	140	30	46000	^{[ 29 ]}	PSPACE-complete ^{[ 30 ]}
الطاولة	28	20	144	55	250	^{[ 31 ]}	EXPTIME-Hard (للإعداد الواقعي حيث تكون استراتيجية الخصم ورميات النرد غير معروفة) ^{[ 32 ]}
شيانغكي	90	40	150	95	38	^{[ 1 ]}^{[ 33 ]}^{[ 34 ]}	؟، يُعتقد أنه مكتمل EXPTIME
أذن البحر	61	25	154	87	60	^{[ 35 ]}^{[ 36 ]}	مستوى صعوبة PSPACE ، وفي EXPTIME
هافانا	271	127	157	66	240	^{[ 7 ]}^{[ 37 ]}	PSPACE-complete ^{[ 38 ]}
بين	572	140	159	60	452	^{[ 39 ]}
جانجي	90	44	160	100	40	^{[ 34 ]}	؟، يُعتقد أنه مكتمل EXPTIME
كوريدور	81	42	162	91	60	^{[ 40 ]}	؟، ولكن في PSPACE
لعبة كاركاسون (لعبة أساسية لشخصين)	72	أكثر من 40	195	71	55	^{[ 41 ]}	التعميم غير واضح
أمازون (10x10)	100	40	212	84	374 أو 299 ^{[ 42 ]}	^{[ 43 ]}^{[ 44 ]}	PSPACE-complete ^{[ 45 ]}
شوغي	81	71	226	115	92	^{[ 33 ]}^{[ 46 ]}	EXPTIME-complete ^{[ 47 ]}
ثورن وسيارات الأجرة (لعبة لاعبين)	33	66	240	56	879	^{[ 48 ]}
انطلق (19x19)	361	170	505	211	250	^{[ 1 ]}^{[ 49 ]}^{[ 50 ]} ^{[ 51 ]}	EXPTIME-complete (بدون قاعدة superko ) ^{[ 52 ]}
أريما	64	43	402	92	17281	^{[ 53 ]}^{[ 54 ]}^{[ 55 ]}	؟، ولكن في وقت التجربة
ستراتيجو	92	115	535	381	21.739	^{[ 56 ]}
الشطرنج اللانهائي	لا نهائي	لا نهائي	لا نهائي	لا نهائي	لا نهائي	^{[ 57 ]}	غير معروف، لكن مسألة mate-in- n قابلة للتقرير ^{[ 58 ]}
ماجيك: ذا غاذرينغ	$\aleph _{0}$	على الأقل $\aleph _{0}$	$2^{\aleph _{0}}$	لا نهائي	على الأقل $\aleph _{0}$	^{[ 59 ]}^{[ 60 ]}	AH-hard ^{[ 61 ]}
ووردل	5	4.113 (12,972)		6		^{[ 62 ]}	مسألة صعبة من نوع NP ، ومن غير المعروف ما إذا كانت مسألة PSPACE-complete مع المعلمات.

ملحوظات

لعبة البريدج ذات الدمية المزدوجة (أي مشاكل الدمية المزدوجة في سياق لعبة البريدج التعاقدية ) ليست لعبة لوحية بالمعنى الحرفي، ولكنها تمتلك شجرة لعب مشابهة، وتُدرس في مجال البريدج الحاسوبي . يمكن اعتبار طاولة البريدج وكأنها تحتوي على خانة واحدة لكل لاعب وحيلة للعب ورقة فيها، وهو ما يتوافق مع حجم لوحة 52. تعقيد شجرة اللعب هو حد أقصى ضعيف جدًا: 13! مرفوعًا للأس 4 لاعبين بغض النظر عن قانونية اللعب. تعقيد فضاء الحالة خاص بتوزيعة واحدة معينة؛ وهو كذلك بغض النظر عن قانونية اللعب ولكن مع استبعاد العديد من عمليات التبديل. آخر 4 حركات هي دائمًا حركات إجبارية بمعامل تفرع 1.

مراجع

1 2 3 4 5 6 7 8 9 10 11 12 فيكتور أليس (1994). البحث عن حلول في الألعاب والذكاء الاصطناعي (ملف PDF) (أطروحة دكتوراه). جامعة ليمبورغ، ماستريخت، هولندا. ISBN 90-900748-8-0.
↑ "التوافقية - حساب اختيار فضاء الحالة في لعبة إكس أو" . موقع تبادل المعلومات الرياضية . تم الاطلاع عليه بتاريخ 8 أبريل 2020 .
↑ تي، برايان (20 أكتوبر 2018). "Btsan/generate_tictactoe" . جيت هاب . تم الاسترجاع في 8 أبريل 2020 .
^ ستيفان ريش (1980). "Gobang ist PSPACE-vollständig (Gobang هو PSPACE مكتمل)". اكتا إنفورماتيكا . 13 (1): 59-66 . دوى : 10.1007 / bf00288536 . S2CID 21455572 .
1 2 3 4 ستيفان رايش (1981). "Hex ist PSPACE-vollständig (Hex ist PSPACE Complete)". اكتا إنفورم (15): 167- 191.
↑ سلاني، وولفغانغ (2000). "تعقيد ألعاب رامزي للرسوم البيانية". في مارسيلاند، تي. أنتوني؛ فرانك، إيان (محرران). الحوسبة والألعاب، المؤتمر الدولي الثاني، CG 2000، هاماماتسو، اليابان، 26-28 أكتوبر 2000، أوراق منقحة . سلسلة محاضرات في علوم الحاسوب. المجلد 2063. سبرينغر. الصفحات 186-203 . doi : 10.1007/3-540-45579-5_12 . ISBN 978-3-540-43080-3.
1 2 3 4 5 6 إتش. جي. فان دن هيريك؛ جيه دبليو إم أويترويجك؛ جيه فان ريجسويجك (2002). "الألعاب التي تم حلها: الآن وفي المستقبل" . الذكاء الاصطناعي . 134 ( 1 – 2): 277 – 311. دوى : 10.1016 / S0004-3702 (01)00152-7 .
↑ أورمان، هيلاري ك. (1996). "البنتومينو: فوز اللاعب الأول" (ملف PDF) . في: نوفاكوفسكي، ريتشارد ج. (محرر). ألعاب بلا حظ: أوراق من ورشة عمل الألعاب التوافقية التي عُقدت في بيركلي، كاليفورنيا، في الفترة من 11 إلى 21 يوليو 1994. منشورات معهد أبحاث العلوم الرياضية. المجلد 29. مطبعة جامعة كامبريدج. الصفحات 339-344 . ISBN 0-521-57411-0MR 1427975 .
↑ جون ترومب (2010). "ملعب جون للعبة كونكت فور" .
↑ إيدلكامب، ستيفان، وبيتر كيسمان. "التصنيف الرمزي لألعاب اللاعبين العامة". KI 2008: التطورات في الذكاء الاصطناعي، تحرير أندرياس ر. دينجل وآخرون، المجلد 5243، سبرينغر برلين هايدلبرغ، 2008، الصفحات 185-192. DOI.org (Crossref)، https://doi.org/10.1007/978-3-540-85845-4_23 .
↑ انظر فان دن هيريك وآخرون لمعرفة القواعد.
↑ لاخمان، مايكل؛ مور، كريستوفر؛ رابابورت، إيفان (2002). "من يفوز في لعبة دومينيرينج على رقعة مستطيلة؟". في: نوفاكوفسكي، ريتشارد (محرر). المزيد من ألعاب انعدام الحظ: وقائع ورشة عمل نظرية الألعاب التوافقية الثانية التي عُقدت في بيركلي، كاليفورنيا، في الفترة من 24 إلى 28 يوليو 2000. منشورات معهد أبحاث العلوم الرياضية. المجلد 42. مطبعة جامعة كامبريدج. الصفحات 307-315 . ISBN 0-521-80832-4MR 1973019 .
↑ جوناثان شيفر وآخرون (6 يوليو/ تموز 2007). "تم حل لعبة الداما" . مجلة ساينس . 317 (5844): 1518-1522 . Bibcode : 2007Sci...317.1518S . doi : 10.1126/science.1144079 . PMID 17641166. S2CID 10274228 .
↑ شيفر، جوناثان (2007). "انتهت اللعبة: دور الأسود في اللعب والتعادل في لعبة الداما" (ملف PDF) . مجلة ICGA . 30 (4): 187-197 . doi : 10.3233/ICG-2007-30402 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 2016-04-03.
1 2 ج. م. روبسون (1984). "لعبة الداما من الرتبة N × N كاملة من حيث الوقت المقدر". مجلة SIAM للحوسبة . 13 (2): 252-267 . doi : 10.1137/0213018 .
↑ انظر أليس 1994 للاطلاع على القواعد
↑ بونيه، إدوارد؛ جامين، فلوريان؛ صفيدين، عبد الله (2013). "حول تعقيد ألعاب الورق التي تعتمد على أخذ الخدع" . في: روسي، فرانشيسكا (محرر). وقائع المؤتمر الدولي المشترك الثالث والعشرين حول الذكاء الاصطناعي، بكين، الصين، 3-9 أغسطس 2013. IJCAI/AAAI. الصفحات 482-488 .
^ إم بي دي شاد؛ إم إتش إم ويناندز؛ جيه دبليو إم أويترويجك؛ إتش جيه فان دن هيريك؛ إم إتش جي بيرجسما (2008). "أفضل مسرحية في Fanorona تؤدي إلى التعادل" (PDF) . الرياضيات الجديدة والحساب الطبيعي . 4 (3): 369-387 . دوى : 10.1142 / S1793005708001124 .
↑ جالاسي، أندريا (2018). "الحد الأعلى لتعقيد جدولة" .
1 2 بيل، جورج آي . (2009). "أقصر لعبة شطرنج صينية ومسائل ذات صلة". الأعداد الصحيحة . 9. arXiv : 0803.1245 . Bibcode : 2008arXiv0803.1245B . doi : 10.1515/INTEG.2009.003 . S2CID 17141575 .
1 2 كاساي، تاكومي؛ أداتشي، أكيو؛ إيواتا، شيجيكي (1979). "أنواع ألعاب الحصى والمسائل الكاملة". مجلة SIAM للحوسبة . 8 (4): 574-586 . doi : 10.1137/0208046 . MR 0573848 . يثبت اكتمال التعميم على الرسوم البيانية العشوائية.
^ ايواتا، شيغيكي؛ كاساي، تاكومي (1994). "لعبة عطيل على $n\times n$ اللوحة كاملة من حيث المساحة (PSPACE-complete) . علوم الحاسوب النظرية . 123 (2): 329-340 . doi : 10.1016/0304-3975(94)90131-7 . MR 1256205 .
↑ روبرت بريزمايستر (2009). تحليل وتطبيق لعبة OnTop (ملف PDF) (أطروحة). جامعة ماستريخت، قسم هندسة المعرفة.
↑ مارك إتش إم ويناندز (2004). البحث المُستنير في الألعاب المعقدة (ملف PDF) (أطروحة دكتوراه). جامعة ماستريخت، ماستريخت، هولندا. ISBN 90-5278-429-9.
↑ تم تقدير حجم فضاء الحالة وشجرة اللعبة للشطرنج لأول مرة في دراسة شانون، كلود (1950). "برمجة حاسوب للعب الشطرنج" (ملف PDF) . المجلة الفلسفية . 41 (314). مؤرشف من الأصل (ملف PDF) بتاريخ 2010-07-06.قدم شانون تقديرات بقيمة 10 ⁴³ و 10 ¹²⁰ على التوالي، وهي أصغر من الحد الأعلى في الجدول، والذي تم تفصيله في رقم شانون .
↑ فرانكل، أفيزري س .؛ ليختنشتاين، ديفيد (1981). "حساب استراتيجية مثالية لـ $n\times n$ يتطلب الشطرنج وقتًا متزايدًا بشكل كبير $n$ " . مجلة نظرية التوافيق، السلسلة أ . 31 (2): 199– 214. doi : 10.1016/0097-3165(81)90016-9 . MR 0629595 .
↑ غوالا، لوتشيانو؛ لوتشي، ستيفانو؛ ناتالي، إيمانويل (2014). "ألعاب بيجيويلد، كاندي كراش، وغيرها من ألعاب المطابقة الثلاثية هي (NP-)صعبة". مؤتمر IEEE لعام 2014 حول الذكاء الحسابي والألعاب، CIG 2014، دورتموند، ألمانيا، 26-29 أغسطس 2014. IEEE. الصفحات 1-8 . arXiv : 1403.5830 . doi : 10.1109/CIG.2014.6932866 . ISBN 978-1-4799-3547-5.
↑ ديدريك وينتينك (2001). تحليل وتطبيق لعبة جيبف (ملف PDF) (أطروحة). جامعة ماستريخت.
↑ تشانغ مينغ شو؛ ما، زد إم؛ جون جي تاو؛ شين هي شو (2009). "تحسينات على البحث عن رقم البرهان في لعبة Connect6". المؤتمر الصيني للتحكم واتخاذ القرار 2009. ص 4525. doi : 10.1109/CCDC.2009.5191963 . ISBN 978-1-4244-2722-2. S2CID 20960281 .
↑ هسيه، مينغ يو؛ تساي، شي-تشون (1 أكتوبر 2007). "حول عدالة وتعقيد ألعاب k-in-a-row المعممة" . علوم الحاسوب النظرية . 385 ( 1-3 ): 88-100 . doi : 10.1016/j.tcs.2007.05.031 .
↑ تيسورو، جيرالد (1 مايو 1992). "قضايا عملية في تعلم الفروق الزمنية" . تعلم الآلة . 8 ( 3-4 ): 257-277 . doi : 10.1007/BF00992697 .
↑ ويتر، آر تي (2021). لعبة الطاولة صعبة. في: دو، دي زد، دو، دي، وو، سي، شو، دي (محررون) التحسين التوافقي وتطبيقاته. مؤتمر كوكوا 2021. سلسلة محاضرات في علوم الحاسوب، المجلد 13135. سبرينغر، تشام. https://doi.org/10.1007/978-3-030-92681-6_38
1 2 شي-جيم ين، جونيور-تشانغ تشن؛ تاي-نينغ يانغ؛ شون-تشين هسو (مارس 2004). "الشطرنج الصيني الحاسوبي" (ملف PDF) . مجلة الرابطة الدولية لألعاب الحاسوب . 27 (1): 3-18 . doi : 10.3233/ICG-2004-27102 . S2CID 10336286. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 14 يونيو 2007.
1 2 دونغهوي بارك (2015). "تعقيد الفضاء والحالة للشطرنج الكوري والشطرنج الصيني". arXiv : 1507.06401 [ math.GM ].
↑ كوروس، باسكال. "تنفيذ مشغل حاسوبي لأذن البحر باستخدام بحث ألفا-بيتا ومونت كارلو" (ملف PDF) . قسم هندسة المعرفة، جامعة ماستريخت . تاريخ الاسترجاع: 29 مارس 2012 .
↑ كوبتشينسكي، جاكوب س (2014). الحوسبة الدافعة: نظرية التعقيد ولعبة أذن البحر (أطروحة). كلية ريد.
↑ جوستين، ب. "إنشاء وكيل لعب في هافانا" (ملف PDF) . تم الاطلاع عليه بتاريخ 29-03-2012 .
↑ إي. بونيه؛ إف. جامين؛ أ. سافيدين (25 مارس 2014). "هافانا وتويكس تي كاملتان في فضاء PSPACE". arXiv : 1403.6518 [ cs.CC ].
↑ كيفن موسكر (2009). Txixt: النظرية والتحليل والتطبيق (ملف PDF) (أطروحة). كلية العلوم الإنسانية والعلوم بجامعة ماستريخت.
↑ غليندينينغ، ليزا (مايو 2005). إتقان كوريدور (ملف PDF) . علوم الحاسوب (رسالة بكالوريوس). جامعة نيو مكسيكو . مؤرشف من الأصل (ملف PDF) بتاريخ 15 مارس 2012.
↑ كاثلين هايدن (2009). تنفيذ مشغل حاسوبي للعبة كاركاسون (ملف PDF) (أطروحة). جامعة ماستريخت، قسم هندسة المعرفة.
↑ عامل التفرع الأدنى مخصص للاعب الثاني.
↑ كلوتزر، جوليان؛ إيدا، هيرويوكي؛ بوزي، برونو (2007). "نهج مونت كارلو في أمازون" (ملف PDF) . ورشة عمل ألعاب الكمبيوتر، أمستردام، هولندا، 15-17 يونيو 2007. الصفحات 185-192 .
↑ هينسجينز، بي بي إل إم (2001). "نهج قائم على المعرفة للعبة الأمازون" (ملف PDF) . جامعة ماستريخت، معهد المعرفة وتكنولوجيا الوكلاء.
↑ آر إيه هيرن (2 فبراير 2005). "أمازونز مكتملة PSPACE". arXiv : cs.CC/0502013 .
^ إيدا، هيرويوكي؛ ساكوتا، ماكوتو؛ رولاسون ، جيف (يناير 2002). "شوغي الكمبيوتر" . الذكاء الاصطناعي . 134 ( 1– 2): 121– 144. دوى : 10.1016/S0004-3702(01)00157-6 .
↑ هـ. أداتشي؛ هـ. كاميكاوا؛ س. إيواتا (1987). "لعبة الشوغي على رقعة n × n تكتمل في وقت أسي". معاملات IEICE . J70-D: 1843– 1852.
↑ إف سي شاد (2009). تقنيات بحث مونت كارلو في لعبة الطاولة الحديثة ثورن أند تاكسيس (ملف PDF) (أطروحة). جامعة ماستريخت. مؤرشفة من الأصل (ملف PDF) بتاريخ 14 يناير 2021.
↑ جون ترومب؛ غونار فارنيباك (2007). "التوافقية في لعبة غو" .تستنتج هذه الورقة الحدود 48 < log(log( N )) < 171 على عدد الألعاب الممكنة N.
↑ ترومب، جون (2016). "عدد المواقف القانونية في لعبة غو" .
↑ "إحصائيات حول مدة لعبة غو" .
↑ جيه إم روبسون (1983). "تعقيد لغة غو". معالجة المعلومات؛ وقائع مؤتمر الاتحاد الدولي لمعالجة المعلومات . الصفحات 413-417 .
↑ كريست-جان كوكس (2006). "تحليل وتطبيق لعبة أريما" (PDF) .
↑ ديفيد جيان وو (2011). "ترتيب وتقييم الحركات في لعبة أريما" (PDF) .
↑ برايان هاسكين (2006). "نظرة على عامل التفرع في أريما" .
↑ فنون الاتحاد الآسيوي لكرة القدم (2010). اللعب التنافسي في لعبة ستراتيجو (ملف PDF) (أطروحة). ماستريخت.
↑ سي دي إيه إيفانز وجويل ديفيد هامكينز (2014). "قيم اللعبة المتسامية في الشطرنج اللانهائي". arXiv : 1302.4377 [ math.LO ].
^ ستيفان ريش، جويل ديفيد هامكينز، وفيليب شليخت (2012). “إن مشكلة الشطرنج اللانهائية قابلة للحسم”. مؤتمر الحوسبة في أوروبا : 78– 88. أرخايف : 1201.5597 .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
↑ أليكس تشرشل، ستيلا بيدرمان، وأوستن هيريك (2020). "ماجيك: ذا غاذرينغ كاملة تورينج". arXiv : 1904.09828 [ cs.AI ].{{cite arXiv}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )
↑ "مجموعات لا نهائية في لعبة ماجيك: 39 مجموعة رائعة لتجربتها" .
↑ ستيلا بيدرمان (2020). "لعبة ماجيك: ذا غاذرينغ صعبة مثل الحساب". arXiv : 2003.05119 [ cs.AI ].
↑ لوكشتانوف، دانيال؛ سوبركاسو، برناردو (14 مايو 2022). "Wordle هي مسألة صعبة من نوع NP". arXiv : 2203.16713 [ cs.CC ].

انظر أيضاً

روابط خارجية

كتاب ديفيد إبستين : التعقيد الحسابي للألعاب والألغاز

[17] لعبة البريدج ذات الدمية المزدوجة (أي مشاكل الدمية المزدوجة في سياق لعبة البريدج التعاقدية ) ليست لعبة لوحية بالمعنى الحرفي، ولكنها تمتلك شجرة لعب مشابهة، وتُدرس في مجال البريدج الحاسوبي . يمكن اعتبار طاولة البريدج وكأنها تحتوي على خانة واحدة لكل لاعب وحيلة للعب ورقة فيها، وهو ما يتوافق مع حجم لوحة 52. تعقيد شجرة اللعب هو حد أقصى ضعيف جدًا: 13! مرفوعًا للأس 4 لاعبين بغض النظر عن قانونية اللعب. تعقيد فضاء الحالة خاص بتوزيعة واحدة معينة؛ وهو كذلك بغض النظر عن قانونية اللعب ولكن مع استبعاد العديد من عمليات التبديل. آخر 4 حركات هي دائمًا حركات إجبارية بمعامل تفرع 1.

[Allis1994-1] 1 2 3 4 5 6 7 8 9 10 11 12 فيكتور أليس (1994). البحث عن حلول في الألعاب والذكاء الاصطناعي (ملف PDF) (أطروحة دكتوراه). جامعة ليمبورغ، ماستريخت، هولندا. ISBN 90-900748-8-0.

[2] "التوافقية - حساب اختيار فضاء الحالة في لعبة إكس أو" . موقع تبادل المعلومات الرياضية . تم الاطلاع عليه بتاريخ 8 أبريل 2020 .

[3] تي، برايان (20 أكتوبر 2018). "Btsan/generate_tictactoe" . جيت هاب . تم الاسترجاع في 8 أبريل 2020 .

[Reisch1980b-4] ستيفان ريش (1980). "Gobang ist PSPACE-vollständig (Gobang هو PSPACE مكتمل)". اكتا إنفورماتيكا . 13 (1): 59-66 . دوى : 10.1007 / bf00288536 . S2CID 21455572 .

[Reisch1980-5] 1 2 3 4 ستيفان رايش (1981). "Hex ist PSPACE-vollständig (Hex ist PSPACE Complete)". اكتا إنفورم (15): 167- 191.

[6] سلاني، وولفغانغ (2000). "تعقيد ألعاب رامزي للرسوم البيانية". في مارسيلاند، تي. أنتوني؛ فرانك، إيان (محرران). الحوسبة والألعاب، المؤتمر الدولي الثاني، CG 2000، هاماماتسو، اليابان، 26-28 أكتوبر 2000، أوراق منقحة . سلسلة محاضرات في علوم الحاسوب. المجلد 2063. سبرينغر. الصفحات 186-203 . doi : 10.1007/3-540-45579-5_12 . ISBN 978-3-540-43080-3.

[GamesSolved-7] 1 2 3 4 5 6 إتش. جي. فان دن هيريك؛ جيه دبليو إم أويترويجك؛ جيه فان ريجسويجك (2002). "الألعاب التي تم حلها: الآن وفي المستقبل" . الذكاء الاصطناعي . 134 ( 1 – 2): 277 – 311. دوى : 10.1016 / S0004-3702 (01)00152-7 .

[8] أورمان، هيلاري ك. (1996). "البنتومينو: فوز اللاعب الأول" (ملف PDF) . في: نوفاكوفسكي، ريتشارد ج. (محرر). ألعاب بلا حظ: أوراق من ورشة عمل الألعاب التوافقية التي عُقدت في بيركلي، كاليفورنيا، في الفترة من 11 إلى 21 يوليو 1994. منشورات معهد أبحاث العلوم الرياضية. المجلد 29. مطبعة جامعة كامبريدج. الصفحات 339-344 . ISBN 0-521-57411-0MR 1427975 .

[9] جون ترومب (2010). "ملعب جون للعبة كونكت فور" .

[10] إيدلكامب، ستيفان، وبيتر كيسمان. "التصنيف الرمزي لألعاب اللاعبين العامة". KI 2008: التطورات في الذكاء الاصطناعي، تحرير أندرياس ر. دينجل وآخرون، المجلد 5243، سبرينغر برلين هايدلبرغ، 2008، الصفحات 185-192. DOI.org (Crossref)، https://doi.org/10.1007/978-3-540-85845-4_23 .

[11] انظر فان دن هيريك وآخرون لمعرفة القواعد.

[12] لاخمان، مايكل؛ مور، كريستوفر؛ رابابورت، إيفان (2002). "من يفوز في لعبة دومينيرينج على رقعة مستطيلة؟". في: نوفاكوفسكي، ريتشارد (محرر). المزيد من ألعاب انعدام الحظ: وقائع ورشة عمل نظرية الألعاب التوافقية الثانية التي عُقدت في بيركلي، كاليفورنيا، في الفترة من 24 إلى 28 يوليو 2000. منشورات معهد أبحاث العلوم الرياضية. المجلد 42. مطبعة جامعة كامبريدج. الصفحات 307-315 . ISBN 0-521-80832-4MR 1973019 .

[13] جوناثان شيفر وآخرون (6 يوليو/ تموز 2007). "تم حل لعبة الداما" . مجلة ساينس . 317 (5844): 1518-1522 . Bibcode : 2007Sci...317.1518S . doi : 10.1126/science.1144079 . PMID 17641166. S2CID 10274228 .

[14] شيفر، جوناثان (2007). "انتهت اللعبة: دور الأسود في اللعب والتعادل في لعبة الداما" (ملف PDF) . مجلة ICGA . 30 (4): 187-197 . doi : 10.3233/ICG-2007-30402 . مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 2016-04-03.

[robson1984-15] 1 2 ج. م. روبسون (1984). "لعبة الداما من الرتبة N × N كاملة من حيث الوقت المقدر". مجلة SIAM للحوسبة . 13 (2): 252-267 . doi : 10.1137/0213018 .

[16] انظر أليس 1994 للاطلاع على القواعد

[18] بونيه، إدوارد؛ جامين، فلوريان؛ صفيدين، عبد الله (2013). "حول تعقيد ألعاب الورق التي تعتمد على أخذ الخدع" . في: روسي، فرانشيسكا (محرر). وقائع المؤتمر الدولي المشترك الثالث والعشرين حول الذكاء الاصطناعي، بكين، الصين، 3-9 أغسطس 2013. IJCAI/AAAI. الصفحات 482-488 .

[Schadd2008-19] إم بي دي شاد؛ إم إتش إم ويناندز؛ جيه دبليو إم أويترويجك؛ إتش جيه فان دن هيريك؛ إم إتش جي بيرجسما (2008). "أفضل مسرحية في Fanorona تؤدي إلى التعادل" (PDF) . الرياضيات الجديدة والحساب الطبيعي . 4 (3): 369-387 . دوى : 10.1142 / S1793005708001124 .

[Galassi2018-20] جالاسي، أندريا (2018). "الحد الأعلى لتعقيد جدولة" .

[Bell_Halma-21] 1 2 بيل، جورج آي . (2009). "أقصر لعبة شطرنج صينية ومسائل ذات صلة". الأعداد الصحيحة . 9. arXiv : 0803.1245 . Bibcode : 2008arXiv0803.1245B . doi : 10.1515/INTEG.2009.003 . S2CID 17141575 .

[pebble-22] 1 2 كاساي، تاكومي؛ أداتشي، أكيو؛ إيواتا، شيجيكي (1979). "أنواع ألعاب الحصى والمسائل الكاملة". مجلة SIAM للحوسبة . 8 (4): 574-586 . doi : 10.1137/0208046 . MR 0573848 . يثبت اكتمال التعميم على الرسوم البيانية العشوائية.

[23] ايواتا، شيغيكي؛ كاساي، تاكومي (1994). "لعبة عطيل على $n\times n$ اللوحة كاملة من حيث المساحة (PSPACE-complete) . علوم الحاسوب النظرية . 123 (2): 329-340 . doi : 10.1016/0304-3975(94)90131-7 . MR 1256205 .

[OnTopComputer-24] روبرت بريزمايستر (2009). تحليل وتطبيق لعبة OnTop (ملف PDF) (أطروحة). جامعة ماستريخت، قسم هندسة المعرفة.

[Winands2004-25] مارك إتش إم ويناندز (2004). البحث المُستنير في الألعاب المعقدة (ملف PDF) (أطروحة دكتوراه). جامعة ماستريخت، ماستريخت، هولندا. ISBN 90-5278-429-9.

[Shannon1950-26] تم تقدير حجم فضاء الحالة وشجرة اللعبة للشطرنج لأول مرة في دراسة شانون، كلود (1950). "برمجة حاسوب للعب الشطرنج" (ملف PDF) . المجلة الفلسفية . 41 (314). مؤرشف من الأصل (ملف PDF) بتاريخ 2010-07-06.قدم شانون تقديرات بقيمة 10 ⁴³ و 10 ¹²⁰ على التوالي، وهي أصغر من الحد الأعلى في الجدول، والذي تم تفصيله في رقم شانون .

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

[Gual14-28] غوالا، لوتشيانو؛ لوتشي، ستيفانو؛ ناتالي، إيمانويل (2014). "ألعاب بيجيويلد، كاندي كراش، وغيرها من ألعاب المطابقة الثلاثية هي (NP-)صعبة". مؤتمر IEEE لعام 2014 حول الذكاء الحسابي والألعاب، CIG 2014، دورتموند، ألمانيا، 26-29 أغسطس 2014. IEEE. الصفحات 1-8 . arXiv : 1403.5830 . doi : 10.1109/CIG.2014.6932866 . ISBN 978-1-4799-3547-5.

[Wentink_thesis-29] ديدريك وينتينك (2001). تحليل وتطبيق لعبة جيبف (ملف PDF) (أطروحة). جامعة ماستريخت.

[EnhancePNConn6-30] تشانغ مينغ شو؛ ما، زد إم؛ جون جي تاو؛ شين هي شو (2009). "تحسينات على البحث عن رقم البرهان في لعبة Connect6". المؤتمر الصيني للتحكم واتخاذ القرار 2009. ص 4525. doi : 10.1109/CCDC.2009.5191963 . ISBN 978-1-4244-2722-2. S2CID 20960281 .

[31] هسيه، مينغ يو؛ تساي، شي-تشون (1 أكتوبر 2007). "حول عدالة وتعقيد ألعاب k-in-a-row المعممة" . علوم الحاسوب النظرية . 385 ( 1-3 ): 88-100 . doi : 10.1016/j.tcs.2007.05.031 .

[32] تيسورو، جيرالد (1 مايو 1992). "قضايا عملية في تعلم الفروق الزمنية" . تعلم الآلة . 8 ( 3-4 ): 257-277 . doi : 10.1007/BF00992697 .

[33] ويتر، آر تي (2021). لعبة الطاولة صعبة. في: دو، دي زد، دو، دي، وو، سي، شو، دي (محررون) التحسين التوافقي وتطبيقاته. مؤتمر كوكوا 2021. سلسلة محاضرات في علوم الحاسوب، المجلد 13135. سبرينغر، تشام. https://doi.org/10.1007/978-3-030-92681-6_38

[Hsu2004-34] 1 2 شي-جيم ين، جونيور-تشانغ تشن؛ تاي-نينغ يانغ؛ شون-تشين هسو (مارس 2004). "الشطرنج الصيني الحاسوبي" (ملف PDF) . مجلة الرابطة الدولية لألعاب الحاسوب . 27 (1): 3-18 . doi : 10.3233/ICG-2004-27102 . S2CID 10336286. مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 14 يونيو 2007.

[Donghwi-35] 1 2 دونغهوي بارك (2015). "تعقيد الفضاء والحالة للشطرنج الكوري والشطرنج الصيني". arXiv : 1507.06401 [ math.GM ].

[PasChor-36] كوروس، باسكال. "تنفيذ مشغل حاسوبي لأذن البحر باستخدام بحث ألفا-بيتا ومونت كارلو" (ملف PDF) . قسم هندسة المعرفة، جامعة ماستريخت . تاريخ الاسترجاع: 29 مارس 2012 .

[Kopczynski-37] كوبتشينسكي، جاكوب س (2014). الحوسبة الدافعة: نظرية التعقيد ولعبة أذن البحر (أطروحة). كلية ريد.

[38] جوستين، ب. "إنشاء وكيل لعب في هافانا" (ملف PDF) . تم الاطلاع عليه بتاريخ 29-03-2012 .

[39] إي. بونيه؛ إف. جامين؛ أ. سافيدين (25 مارس 2014). "هافانا وتويكس تي كاملتان في فضاء PSPACE". arXiv : 1403.6518 [ cs.CC ].

[Thesis_Moesker-40] كيفن موسكر (2009). Txixt: النظرية والتحليل والتطبيق (ملف PDF) (أطروحة). كلية العلوم الإنسانية والعلوم بجامعة ماستريخت.

[MasterQuor-41] غليندينينغ، ليزا (مايو 2005). إتقان كوريدور (ملف PDF) . علوم الحاسوب (رسالة بكالوريوس). جامعة نيو مكسيكو . مؤرشف من الأصل (ملف PDF) بتاريخ 15 مارس 2012.

[CarcassoneComputer-42] كاثلين هايدن (2009). تنفيذ مشغل حاسوبي للعبة كاركاسون (ملف PDF) (أطروحة). جامعة ماستريخت، قسم هندسة المعرفة.

[43] عامل التفرع الأدنى مخصص للاعب الثاني.

[Kloetzer_themonte-carlo-44] كلوتزر، جوليان؛ إيدا، هيرويوكي؛ بوزي، برونو (2007). "نهج مونت كارلو في أمازون" (ملف PDF) . ورشة عمل ألعاب الكمبيوتر، أمستردام، هولندا، 15-17 يونيو 2007. الصفحات 185-192 .

[Hengens_thesis-45] هينسجينز، بي بي إل إم (2001). "نهج قائم على المعرفة للعبة الأمازون" (ملف PDF) . جامعة ماستريخت، معهد المعرفة وتكنولوجيا الوكلاء.

[46] آر إيه هيرن (2 فبراير 2005). "أمازونز مكتملة PSPACE". arXiv : cs.CC/0502013 .

[47] إيدا، هيرويوكي؛ ساكوتا، ماكوتو؛ رولاسون ، جيف (يناير 2002). "شوغي الكمبيوتر" . الذكاء الاصطناعي . 134 ( 1– 2): 121– 144. دوى : 10.1016/S0004-3702(01)00157-6 .

[48] هـ. أداتشي؛ هـ. كاميكاوا؛ س. إيواتا (1987). "لعبة الشوغي على رقعة n × n تكتمل في وقت أسي". معاملات IEICE . J70-D: 1843– 1852.

[Schadd2010-49] إف سي شاد (2009). تقنيات بحث مونت كارلو في لعبة الطاولة الحديثة ثورن أند تاكسيس (ملف PDF) (أطروحة). جامعة ماستريخت. مؤرشفة من الأصل (ملف PDF) بتاريخ 14 يناير 2021.

[cwi-50] جون ترومب؛ غونار فارنيباك (2007). "التوافقية في لعبة غو" .تستنتج هذه الورقة الحدود 48 < log(log( N )) < 171 على عدد الألعاب الممكنة N.

[Tromp2016-51] ترومب، جون (2016). "عدد المواقف القانونية في لعبة غو" .

[52] "إحصائيات حول مدة لعبة غو" .

[Robson1983-53] جيه إم روبسون (1983). "تعقيد لغة غو". معالجة المعلومات؛ وقائع مؤتمر الاتحاد الدولي لمعالجة المعلومات . الصفحات 413-417 .

[Cox2006-54] كريست-جان كوكس (2006). "تحليل وتطبيق لعبة أريما" (PDF) .

[Wu2011-55] ديفيد جيان وو (2011). "ترتيب وتقييم الحركات في لعبة أريما" (PDF) .

[Haskin2006-56] برايان هاسكين (2006). "نظرة على عامل التفرع في أريما" .

[ArtsStratego-57] فنون الاتحاد الآسيوي لكرة القدم (2010). اللعب التنافسي في لعبة ستراتيجو (ملف PDF) (أطروحة). ماستريخت.

[58] سي دي إيه إيفانز وجويل ديفيد هامكينز (2014). "قيم اللعبة المتسامية في الشطرنج اللانهائي". arXiv : 1302.4377 [ math.LO ].

[Brumleve2012-59] ستيفان ريش، جويل ديفيد هامكينز، وفيليب شليخت (2012). “إن مشكلة الشطرنج اللانهائية قابلة للحسم”. مؤتمر الحوسبة في أوروبا : 78– 88. أرخايف : 1201.5597 .{{cite journal}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[Churchill2020-60] أليكس تشرشل، ستيلا بيدرمان، وأوستن هيريك (2020). "ماجيك: ذا غاذرينغ كاملة تورينج". arXiv : 1904.09828 [ cs.AI ].{{cite arXiv}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

[61] "مجموعات لا نهائية في لعبة ماجيك: 39 مجموعة رائعة لتجربتها" .

[Biderman-62] ستيلا بيدرمان (2020). "لعبة ماجيك: ذا غاذرينغ صعبة مثل الحساب". arXiv : 2003.05119 [ cs.AI ].

[63] لوكشتانوف، دانيال؛ سوبركاسو، برناردو (14 مايو 2022). "Wordle هي مسألة صعبة من نوع NP". arXiv : 2203.16713 [ cs.CC ].

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ ملاحظة 1 ]

[ 17 ]

[ 18 ]

[ 19 ]

[ 20 ]

[ 21 ]

[ 22 ]

[ 23 ]

[ 24 ]

[ 25 ]

[ 26 ]

[ 27 ]

[ 28 ]

[ 29 ]

[ 30 ]

[ 31 ]

[ 32 ]

[ 33 ]

[ 34 ]

[ 35 ]

[ 36 ]

[ 37 ]

[ 38 ]

[ 39 ]

[ 40 ]

[ 41 ]

[ 42 ]

[ 43 ]

[ 44 ]

[ 45 ]

[ 46 ]

[ 47 ]

[ 48 ]

[ 49 ]

[ 50 ]

[ 51 ]

[ 52 ]

[ 53 ]

[ 54 ]

[ 55 ]

[ 56 ]

[ 57 ]

[ 58 ]

[ 59 ]

[ 60 ]

[ 61 ]

[ 62 ]

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