لعبة غو والرياضيات

📅 آخر تحديث: ٢٥ يوليو ٢٠٢٦
✍️ نُشر في: ٢٥ يوليو ٢٠٢٦
📷 يحتوي على 7 صور
الموسوعة الحرة

تُعدّ لعبة غو واحدة من أشهر الألعاب في العالم. وبفضل قواعدها البسيطة والأنيقة، لطالما كانت مصدر إلهام للبحوث الرياضية . وقد قدّر شين كو ، العالم الصيني من القرن الحادي عشر، في كتابه " مقالات بركة الأحلام" أن عدد وضعيات رقعة اللعب الممكنة يبلغ حوالي 10172. وفي السنوات الأخيرة، أدى بحث جون إتش. كونواي في اللعبة إلى تطوير مفهوم الأعداد السريالية ، وساهم في تطوير نظرية الألعاب التوافقية (مع كون "المتناهيات الصغرية في غو " [ 1 ] مثالًا محددًا على استخدامها في لعبة غو).

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

يتم لعب لعبة Go المعممة على لوحات n × n ، ويعتمد التعقيد الحسابي لتحديد الفائز في وضع معين من لعبة Go المعممة بشكل حاسم على قواعد ko .

لعبة Go "تقريبًا" في PSPACE ، لأنه في اللعب العادي، لا يمكن عكس الحركات، ومن خلال الالتقاط فقط توجد إمكانية للأنماط المتكررة اللازمة لتعقيد أكبر.

بدون كو

بدون ko، فإن لعبة Go هي PSPACE-hard . [ 2 ] يتم إثبات ذلك عن طريق اختزال True Quantified Boolean Formula ، المعروفة بأنها PSPACE-complete، إلى الجغرافيا المعممة ، إلى الجغرافيا المعممة المستوية، إلى الجغرافيا المعممة المستوية ذات الدرجة القصوى 3 ، وأخيرًا إلى أوضاع Go.

حكم الكو الياباني

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

مع قواعد "كو" اليابانية، تُعتبر لعبة "جو" كاملة من حيث وقت التجربة . [ 3 ]

سوبركو هو الأفضل

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

لا تزال مسألة تحديد فئة تعقيد لعبة غو في ظل قاعدة سوبركو غير واضحة. فعلى الرغم من أن لعبة غو مع قاعدة كو اليابانية تُعتبر كاملة من حيث الوقت الأمثل (EXPTIME-complete)، إلا أن الحدين الأدنى والأعلى لبرهان روبسون على اكتمالها من حيث الوقت الأمثل [ 3 ] ينكسران عند إضافة قاعدة سوبركو.

من المعروف أن لعبة غو صعبة على الأقل في فضاء PSPACE، لأن البرهان الوارد في [ 2 ] على صعوبة لعبة غو في فضاء PSPACE لا يعتمد على قاعدة ko، أو على غياب قاعدة ko. ومن المعروف أيضًا أن لعبة غو تنتمي إلى فضاء EXPSPACE. [ 4 ]

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

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

تعقيد بعض تكوينات لعبة Go

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

وبناءً على هذا التعريف، فإن نهايات لعبة غو صعبة للغاية (PSPACE-hard). [ 7 ]

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

يُعد تحديد الفريق الفائز في سباق الاستيلاء على السلالم مسألةً كاملةً في فضاء PSPACE، سواءً طُبقت قاعدة "كو" اليابانية أو قاعدة "سوبر كو". [ 8 ] وقد ثبت ذلك من خلال محاكاة لعبة QBF، المعروفة بأنها كاملة في فضاء PSPACE، باستخدام سلالم ترتد على اللوحة كأشعة الضوء.

بما أن كل خانة على رقعة الشطرنج يمكن أن تكون إما فارغة أو سوداء أو بيضاء، فإن هناك إجمالي 3ⁿ² خانة ممكنة على رقعة مربعة طول ضلعها n ؛ ومع ذلك ، ليست جميعها قانونية. وقد استنتج ترومب وفارنباك صيغة تكرارية للخانات القانونية.ل(م،ن){\displaystyle L(m,n)}لوح مستطيل طوله m و n . [ 9 ] العدد الدقيق لـل(19،19){\displaystyle L(19,19)}تم الحصول عليها في عام 2016. [ 10 ] كما وجدوا صيغة تقريبيةل≈أبم+نجمن{\displaystyle L\approx AB^{m+n}C^{mn}}، أينأ≈0.8506399258457145{\displaystyle A\approx 0.8506399258457145}،ب≈0.96553505933837387{\displaystyle B\approx 0.96553505933837387}وج≈2.975734192043357249381{\displaystyle C\approx 2.975734192043357249381}تشير التقديرات إلى أن الكون المرئي يحتوي على حوالي 10 ^80 ذرة، وهو عدد أقل بكثير من عدد المواضع القانونية الممكنة على رقعة لعب عادية (m=n=19). ومع ازدياد حجم الرقعة، تتناقص نسبة المواضع القانونية.

حجم اللوحة ن × ن3 ن 2نسبة قانونيةل{\displaystyle L}(المواقف القانونية) ( A094777 ) [ 11 ]
1 × 1333.33%1
2 × 28170.37%57
3 × 319,68364.40%12,675
4 × 443,046,72156.49%24,318,165
5 × 5847,288,609,44348.90%414,295,148,741
9 × 94.43426488243 × 10 3823.44%1.03919148791 × 10 38
13 × 134.30023359390 × 10 808.66%3.72497923077 × 10 79
19 × 191.74089650659 × 10 1721.20%2.08168199382 × 10 170

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

يشير عالم الحاسوب فيكتور أليس إلى أن الألعاب النموذجية بين الخبراء تستغرق حوالي 150 نقلة، بمتوسط ​​250 خيارًا لكل نقلة، مما يوحي بتعقيد شجرة اللعبة بمقدار 10³⁶⁰ . [ 12 ] بالنسبة لعدد الألعاب الممكنة نظريًا ، بما في ذلك الألعاب المستحيلة عمليًا، قدم ترومب وفارنباك حدين أدنى وأعلى هما 10¹⁰⁴⁸ و10¹⁰⁷¹ على التوالي . [ 9 ] وقد حسّن والرايت وترومب الحد الأدنى إلى 10¹⁰⁸ ، وهو أكبر من غوغولبلكس . [ 13 ] أما الرقم الأكثر شيوعًا لعدد الألعاب الممكنة، وهو 10⁷⁰⁰ [ 14 ]، فهو مشتق من تبديل بسيط لـ 361 نقلة أو 361! ≈1.4 × 10⁷⁶⁸ . هناك اشتقاق شائع آخر وهو افتراض N تقاطعًا و L أطول لعبة لـ N L إجمالي الألعاب. على سبيل المثال، 400 نقلة، كما هو الحال في بعض الألعاب الاحترافية، ستكون واحدة من 361400 أو1.0 × 10 1023 لعبة ممكنة.

يعتمد العدد الإجمالي للألعاب الممكنة على حجم رقعة الشطرنج وعدد النقلات. وبينما تستغرق معظم الألعاب أقل من 400 أو حتى 200 نقلة، إلا أن هناك احتمالات لعدد أكبر بكثير.

حجم اللعبةحجم اللوحة N (التقاطعات)ن !متوسط ​​طول المباراة LN Lأقصى مدة للعبة (عدد النقلات)الحد الأدنى للألعابالحد الأقصى للألعاب
2 × 2424364386,356,909,593 [ 15 ]386,356,909,593
3 × 393.6 × 10 555.9 × 10 4
4 × 4162.1 × 10 1396.9 × 10 10
5 × 5251.6 × 10 25159.3 × 10 20
9 × 9815.8 × 10 120457.6 × 10 85
13 × 131694.3 × 10 304903.2 × 10 200
19 × 193611.4 × 10768​2003.2 × 10 511>4.7 × 10 100 [ 13 ]10 10 108 [ 13 ]10 10 171
21 × 214412.5 × 10976​2501.3 × 10661​

يمكن تقدير العدد الإجمالي للألعاب الممكنة من حجم رقعة الشطرنج بعدة طرق، بعضها أكثر دقة من غيرها. أبسطها، وهو تبديل حجم الرقعة، ( N ) L ، لا يشمل عمليات الاستيلاء غير القانونية والمواقع غير القانونية. باعتبار N حجم الرقعة (19 × 19 = 361) و L أطول لعبة، فإن NL يشكل حدًا أعلى. يُقدَّم حدٌّ أكثر دقة في ورقة ترومب/فارنباك.

أطول لعبة L (19 × 19)( N ) Lالحد الأدنى للألعابالحد الأقصى للألعابملحوظات
1361361362يستسلم الأبيض بعد النقلة الأولى، 361 (362 إذا أُخذت النقلة في الحسبان) متجاهلاً جميع نقاط التناظر بما في ذلك y = x ، وإلا (المسافات من الزاوية) 10 × 10 - 10 = 90، 90 / 2 = 45 + 10 (بإضافة نقاط التناظر x = y ) = 55 (56 إذا أُخذت النقلة في الحسبان).
2129960130682361 (أسود) × 360 (أبيض) + 361 (تمرير أسود) + 361 (تمرير أبيض)
502.1 × 10 1267.5 × 10 127
1001.4 × 10 2495.6 × 10 255
1506.4 × 10 3674.2 × 10 383
2001.9 × 10 4813.2 × 10 511
2112.5 × 10 5054.3 × 10539​متوسط ​​طول المباريات الاحترافية
2508.2 × 10587​2.4 × 10639​
3002.8 × 10684​7.8 × 10766​
3503.6 × 10760​1.3 × 10895​
3611.4 × 10768​1.8 × 10923​أطول مباراة باستخدام 181 حجرًا أسود و180 حجرًا أبيض
411غير متوفر1.3 × 10 1051أطول مباراة احترافية [ 16 ]
500غير متوفر5.7 × 10 1278
1000غير متوفر3.2 × 10 2557
47045881غير متوفر10 10 8361 3 حركات
جميع الألعاب [ 13 ]غير متوفر10 10 10810 10 171أطول لعبة تحتوي على الأقل4.7 × 10 100 حركة.

وبالتالي، فإن الرقم 10700 يمثل تقديرًا مبالغًا فيه لعدد المباريات الممكنة التي يمكن لعبها في 200 نقلة، وتقديرًا أقل من عدد المباريات الممكنة التي يمكن لعبها في 361 نقلة. وبما أن السنة تحتوي على حوالي 31 مليون ثانية، فسيستغرق الأمر حوالي سنتين وربع ، بمعدل 16 ساعة لعب يوميًا ونقلة واحدة في الثانية، للعب 47 مليون نقلة.

انظر أيضاً

ملحوظات

  1. ↑ "استكشف الأعداد المتناهية الصغر في مكتبة سينسي" . senseis.xmp.net . تم الاطلاع عليه بتاريخ 10 فبراير 2022 .
  2. 1 2 ليختنشتاين، ديفيد؛ سيبسر، مايكل (أبريل 1980). "لعبة غو صعبة في فضاء متعدد الحدود" (ملف PDF) . مجلة ACM . 27 (2): 393-401 . doi : 10.1145/322186.322201 . S2CID 29498352 . 
  3. 1 2 روبسون، جون (1983). "تعقيد لعبة جو". وقائع المؤتمر العالمي التاسع للحاسوب التابع للاتحاد الدولي لمعالجة المعلومات : 413-417 .
  4. روبسون ، ج. ( 1984 ). "الألعاب التوافقية ذات مسائل القرار الكاملة في الفضاء الأسي". الأسس الرياضية لعلوم الحاسوب 1984. سلسلة محاضرات في علوم الحاسوب. المجلد 176. الصفحات 498-506 . doi : 10.1007/BFb0030333 . ISBN   978-3-540-13372-8.{{cite book}}تم |journal=تجاهله ( مساعدة )
  5. ↑ أفييزري فرانكل ود. ليختنشتاين (1981). "حساب استراتيجية مثالية للشطرنج من الرتبة n × n يتطلب وقتًا أُسّيًا بالنسبة إلى n" . مجلة نظرية التوافيق أ . 31 (2): 199-214 . doi : 10.1016/0097-3165(81)90016-9 .
  6. ↑ جيه إم روبسون (1984). "لعبة الداما من الرتبة N × N كاملة من حيث الوقت المقدر". مجلة SIAM للحوسبة . 13 (2): 252-267 . doi : 10.1137/0213018 .
  7. ↑ وولف، ديفيد (2002). نوفاكوفسكي، ريتشارد ج. (محرر). "نهايات لعبة غو صعبة من حيث المساحة" (ملف PDF) . المزيد من ألعاب الحظ، منشورات معهد أبحاث العلوم الرياضية 42 : 125-136 . مؤرشف من الأصل (ملف PDF) بتاريخ 10 أغسطس 2017. تم الاطلاع عليه بتاريخ 9 يوليو 2016 .
  8. ↑ كراشمارو، مارسيل؛ ترومب، جون (2000). "السلالم كاملة في فضاء PSPACE". الحواسيب والألعاب . سلسلة محاضرات في علوم الحاسوب. المجلد 2063. سبرينغر. الصفحات 241-249 . CiteSeerX 10.1.1.24.4665 . doi : 10.1007/3-540-45579-5_16 . ISBN    978-3-540-43080-3.
  9. 1 2 ترومب، ج ؛ فارنيباك، ج (2007)، "توافقية لعبة غو"، الحواسيب والألعاب ، سلسلة محاضرات في علوم الحاسوب، المجلد 4630، سبرينغر، برلين، هايدلبرغ، الصفحات 84-99 ، doi : 10.1007/978-3-540-75538-8_8 ، ISBN   978-3-540-75537-1
  10. ↑ https://tromp.github.io/go/legal.html 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935
  11. ↑ "توافيق لغة غو" (ملف PDF) . github.io . تم ​​الاطلاع عليه بتاريخ 17 يونيو 2023 .
  12. ↑ أليس 1994
  13. 1 2 3 4 والرايت، م؛ ترومب، ج (2016)، "مجموعة غوغولبلكس من ألعاب غو"، الحواسيب والألعاب ، سلسلة محاضرات في علوم الحاسوب، المجلد 10068، سبرينغر، برلين، هايدلبرغ، الصفحات 191-201 ، doi : 10.1007/978-3-319-50935-8_18 ، ISBN   978-3-319-50934-1
  14. ↑ "الصفحة الرئيسية - الرابطة الأمريكية للعبة غو" . www.usgo.org . تم الاطلاع عليه بتاريخ 17 يونيو 2023 .
  15. ↑ ترومب 1999
  16. ↑ "إحصائيات حول مدة لعبة غو" .

مراجع