عدد شانون

عدد طبيعي

عدد شانون، سُمي على إسم عالم الرياضيات الأمريكي كلود شانون، هو الحد الأدنى المحافظ لتعقيد شجرة لعبة الشطرنج البالغ 10 120، استناداً إلى متوسط يبلغ 10 3 احتمالاً لزوج من الحركات مكون من حركة للأبيض متبوعاً بحركة للاسود، وتستغرق اللعبة النموذجية زهاء 40 زوجاً من هذه الحركات.

عدد شانون
معلومات عامة
جانب من جوانب
سُمِّي باسم
الموضوع الرئيس
chess game (en) ترجم عدل القيمة على Wikidata
يدرسه
المكتشف أو المخترع
زمن الاكتشاف أو الاختراع
1950[1] عدل القيمة على Wikidata
عدد الأرقام العشرية
121 عدل القيمة على Wikidata
تعريف الصيغة
[1] عدل القيمة على Wikidata

حساب شانون

عدل

بيّن شانون حساباً للحد الأدنى لتعقيد شجرة لعبة الشطرنج، مسفراً عن حوالي 10 120 لعبة محتملة، لإثبات عدم جدوى حل الشطرنج بأسلوب البحث الشامل، في ورقته البحثية عام 1950 بعنوان "برمجة الحاسوب للعب الشطرنج". [2] (قدمت هذه الورقة المؤثرة مجال الشطرنج الحاسوبي . )

كما قدر شانون عدد الاوضاع الممكنة "للترتيب العام بـ  ، أو ما يقرب من 10 43. وهذا يشمل بعض الاوضاع غير القانونية (على سبيل المثال، بيادق في الصف الأول، وعندما يكون كلا الملكين في وضع "كش ملك") وأستثنى اوضاع قانونية بعد الأسر والترقيات.

عدد النقلات (نصف حركات) عدد الألعاب الممكنة [3] عدد كش ملك [4]
1 20 0
2 400 0
3 8902 0
4 197281 8
5 4،865،609 347
6 119.060.324 10828
7 3،195،901،860 435767
8 84،998،978،956 9،852،036
9 2،439،530،234،167 400191963
10 69،352،859،712،417 8790619155
11 2،097،651،003،696،806 362،290،010،907
12 62،854،969،236،701،747 8،361،091،858،959
13 1،981،066،775،000،396،239 346،742،245،764،219
14 61.885.021.521.585.529.237
15 2،015،099،950،053،364،471،960

بعد أن يقوم كل لاعب بتحريك القطعة 5 مرات كل (10 نقلات)، يكون هناك 69352.859.712417 لعبة يمكن لعبها.

الحدود الأضيق

عدل

الحد الاعلى

عدل

مع الأخذ في الاعتبار أعداد شانون، قام فيكتور أليس بحساب حد أعلى قدره 5 × 10 52 لعدد المواضع، وقدر العدد الحقيقي بأنه حوالي 10 50. [5] وتحسن النتائج الحديثة [6] هذا التقدير، بإثبات حد أعلى قدره 8.7 × 10 45، ومبينةً[7] [8] أن الحد الأعلى يبلغ 4 × 10 37 في غياب الترقيات.

الحد الأدنى

عدل

قدر أليس أيضاً أن تعقيد شجرة اللعبة يبلغ10 123 على الأقل، "بناءً على متوسط عامل تشعب 35 ومتوسط طول لعبة 80". على سبيل المقارنة، يُقدر عدد الذرات في الكون المرئي، والذي يُقارن به غالباً، بنحو 10 80.

التقديرات الدقيقة

عدل

قدّر جون ترومب وبيتر أوسترلوند عدد أوضاع الشطرنج القانونية بمستوى ثقة 95٪ عند ، استناداً إلى تقابلية محسوبة بكفاءة بين الأعداد الصحيحة وأوضاع الشطرنج. [6]

عدد ألعاب الشطرنج المعقولة

عدل

وعلى سبيل المقارنة مع عدد شانون، إذا حُللت لعبة الشطرنج لعدد الألعاب "المعقولة" التي يمكن لعبها (دون احتساب الحركات التافهة أو الواضحة الخسارة للعبة مثل تحريك ملكة ليتم التقاطها على الفور من قبل بيدق دون تعويض)، فإن النتيجة أقرب إلى حوالي 1040لعبة. يعتمد ذلك على وجود خيار من حوالي ثلاث حركات معقولة في كل طية (نصف حركة)، وطول لعبة 80 طية (أو على نحو مكافئ، 40 حركة).[9]

أنظر أيضا

عدل
  • حل الشطرنج
  • لعبة الغو والرياضيات
  • تعقيد اللعبة
  • انفجار توافيقي

ملاحظات ومراجع

عدل
  1. ^ ا ب مذكور في: Programming a Computer for Playing Chess. المُؤَلِّف: كلود شانون. لغة العمل أو لغة الاسم: الإنجليزية. تاريخ النشر: 1949.
  2. ^ Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. ج. 41 ع. 314. مؤرشف من الأصل (PDF) في 2020-05-23.
  3. ^ "A048987 - Oeis". مؤرشف من الأصل في 2023-02-19.
  4. ^ "A079485 - Oeis". مؤرشف من الأصل في 2022-12-22.
  5. ^ Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, جامعة ماسترخت, Maastricht, The Netherlands. ISBN:978-90-900748-8-7. مؤرشف من الأصل (PDF) في 2022-11-07.
  6. ^ ا ب John Tromp (2022). "Chess Position Ranking". غيت هاب. مؤرشف من الأصل في 2023-02-19.
  7. ^ S. Steinerberger (2015). "On the Number of Positions in Chess Without Promotion". International Journal of Game Theory. ج. 44 ع. 3: 761–767. DOI:10.1007/s00182-014-0453-7.
  8. ^ Gourion, Daniel (16 Dec 2021), An upper bound for the number of chess diagrams without promotion (بالإنجليزية), arXiv:2112.09386, Archived from the original on 2022-11-07, Retrieved 2021-12-18
  9. ^ "How many chess games are possible?" Dr. James Grime talking about the Shannon Number and other chess stuff (films by Brady Haran). MSRI, Mathematical Sciences. نسخة محفوظة 2023-01-03 على موقع واي باك مشين.

روابط خارجية

عدل

مراجع

عدل