عدد شانون

عدد شانون که به نام کلود شانون نامگذاری شده‌است، مرز پایین‌تر محافظه کارانه (نه یک برآورد) پیچیدگی درخت بازی شطرنج برابر 10 120 است، که براساس میانگین حدود 10 3 احتمال برای یک جفت حرکت شامل یک حرکت برای سفید و پس از آن یک حرکت برای سیاه، در یک بازی معمولی که حدود ۴۰ جفت حرکت طول بکشد، اندازه‌گیری شده‌است.

کلود شانون

محاسبه شانون

شانون در مقاله ۱۹۵۰ خود «برنامه‌نویسی کامپیوتر برای بازی شطرنج» یک محاسبه برای حد پایین‌تر از پیچیدگی درخت بازی شطرنج را نشان داد، که در حدود 10 120 بازی ممکن بود، برای اینکه غیر عملی بودن حل شطرنج توسط روش جستجوی جامع را نمایش دهد.[1] (این مقاله تأثیرگذار، معرفی‌کننده و آغازگر حوزه شطرنج کامپیوتری شد)

شانون همچنین تعدادی از موقعیت‌های احتمالی را برآورد کرد، که دارای مرتبه یا به عبارت دیگر حدود 10 43 بود. این برآورد نقصهایی داشت: برخی از موقعیت‌های غیرقانونی (به عنوان مثال، پیاده هادر ردیف اول، هر دو پادشاه در موقعیت کیش) را نیز شامل می‌شد و همچنین موقعیت‌های قانونی که به دنبال آن‌ها زدن مهره‌ها و ارتقای آن‌ها اتفاق می‌افتاد را نادیده می‌گرفت. با توجه به این موارد، ویکتور آلیس محدوده بالایی از ۵ × 10 52 را برای تعدادی از موقعیت‌ها محاسبه کرد و تخمین زد که تعداد واقعی آن حدود 10 50 [2] باشد. نتایج اخیر[3] این برآورد[3] را با اثبات مرز بالایی تنها 2 155، که کمتر از 10 46.7 است و همچنین نشان دادن[4] حد بالایی ۲ × 10 40 بدون احتساب ارتقای مهره‌ها، بهبود می‌بخشد. آلیس همچنین برآورد کرد که پیچیدگی درخت بازی حداقل 10 123 می‌باشد که "براساس میانگین شعاع ۳۵ و میانگین طول بازی ۸۰ حرکت" محاسبه گردیده‌است. به عنوان یک مقایسه، تعداد اتم‌ها در جهان قابل مشاهده تقریباً 10 80 است.

تعداد حرکت‌ها تعداد بازی‌های ممکن
۱ ۲۰
۲ ۴۰۰
۳ ۸۹۰۲
۴ ۱۹۷٬۲۸۱
۵ ۴٬۸۶۵٬۶۰۹
۶ ۱۱۹٬۰۶۰٬۳۲۴
۷ ۳٬۱۹۵٬۹۰۱٬۸۶۰
۸ ۸۴۹۹۸٬۹۷۸٬۹۵۶
۹ ۲٬۴۳۹٬۵۳۰٬۲۳۴٬۱۶۷
۱۰ ۶۹٬۳۵۲٬۸۵۹٬۷۱۲٬۴۱۷

پس از ۵ بار جفت حرکت (۱۰ تک حرکت) تعداد ۶۹٫۳۵۲٫۸۵۹٫۷۱۲٫۴۱۷ بازی ممکن وجود دارد.

تعداد بازی‌های معقول شطرنج

به عنوان یک مقایسه با عدد شانون، اگر شطرنج برای تعداد بازی‌های «معقول» که می‌توان آن‌ها را بازی کرد، تحلیل شود (بدون در نظر گرفتن حرکت‌های مضحک یا به وضوح منجر به شکست در بازی، مانند حرکت یک وزیر به طوری که بلافاصله توسط یک پیاده زده شود، بدون نقشه ای برای جبران)، نتیجه نزدیک به حدود 10 40 بازی است. این عدد بر مبنای داشتن انتخاب به میزان سه حرکت معقول در هر تک حرکت (نیمه حرکت) و طول بازی ۸۰ تک حرکت(۴۰ جفت حرکت) است.[5]

همچنین نگاه کنید

یادداشت‌ها و مراجع
  1. Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 41 (314). Archived from the original (PDF) on 15 March 2010. Retrieved 29 April 2019.
  2. Victor Allis (1994). Searching for Solutions in Games and Artificial Intelligence (PDF). Ph.D. Thesis, University of Limburg, Maastricht, The Netherlands. ISBN 978-90-900748-8-7.
  3. John Tromp (2010). "John's Chess Playground".
  4. S. Steinerberger (2014). "International Journal of Game Theory". International Journal of Game Theory. 44 (3): 761–767. doi:10.1007/s00182-014-0453-7.
  5. "چند بازی شطرنج ممکن است؟"

پیوند به بیرون
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.