مقالات شطرنج

  • 2157
  • 1620 مرتبه
مساله دانه گندم و صفحه شطرنج

مساله دانه گندم و صفحه شطرنج

1397/07/08 10:40:37 ق.ظ

 

 

 

 

 

 

 

 

شطرنج شاید یکی از معروف‌ترین بازی‌های فکری جهان باشد. این بازی از هند سرچشمه می‌گیرد و کتاب‌‌های بسیاری پیرامون آن نوشته شده است. اما جلوه‌ی دیگری که این بازی می‌تواند به ما نشان دهد بزرگی در عین کوچک بودن است! 


«پادشاه هند به فردی که شطرنج را اختراع کرد گفت هر پاداشی که می‌خواهد بگوید. آن فرد درخواست کرد تا یک صفحه شطرنج بیاورند و گفت به ازای خانه اول ۱ گندم، به ازای خانه دوم ۲ گندم، به ازای خانه سوم ۴ گندم و بدین ترتیب به ازای هر خانه دو برابر قبلی گندم به او پاداش داده شود.

پادشاه که فکر می‌کرد درخواست او ناچیز است فرمان داد سریعاً پاداش او را تهیه کنند اما در واقع با محاسبه معلوم شد تهیه آن از عهده هیچ کسی بر نمی‌آید.»


میزان گندمی که پاشاه باید به او می داد برابر با (۱ -۲۶۴) است به عبارتی ۱۸٬۴۴۶٬۷۴۴٬۰۷۳٬۷۰۹٬۵۵۱٬۶۱۵ دانه گندم، این مقدار گندم تمام سطح هندوستان را تا ارتفاع ۱۵ متر می‌پوشاند یا اگر این میزان گندم پشت هم چیده شود می‌تواند فاصله زمین تا ستاره آلفا قنطورس را که برابر ۴ سال نوری است، دو بار برود و بازگردد.


فرض کنید جمعیت زمین برابر با ۷ میلیارد نفر باشد و هر فرد زمینی با یک فرد فضایی از جهان دیگر، شطرنج یک دقیقه‌ای بازی کند، در پایان هر روز  ۱۰٬۰۸۰٬۰۰۰٬۰۰۰٬۰۰۰ بازی انجام خواهد شد، بعد از گذشت یک سال تعداد بازی ها به عدد ۳٬۶۷۹٬۲۰۰٬۰۰۰٬۰۰۰٬۰۰۰ می رسد و بعد از یک میلیارد سال تعداد بازی های انجام شده برابر خواهد بود با ۱۰۲۴×۳٫۶۷۹۲. عدد بزرگی به نظر می‌رسد اما حتی اگر ما زمان بازی را به یک ثانیه کاهش بدهیم الهه‌ی شطرنج بخاطر مقدار ناچیز تعداد بازی‌هایی که تحلیل کرده‌ایم به ما خواهد خندید. در واقع یک واقعیت جالب وجود دارد که تعداد بازی‌های شطرنج از اتم‌های جهان قابل مشاهده بیشتر است.


می توان تعداد بازی های ممکن در شطرنج را برابر با « عدد شانون» درنظر گرفت. در سال ۱۹۵۰ «کلود شانون» در مقاله ای با نام «برنامه ریزی یک کامپیوتر برای شطرنج بازی کردن»، تشریح کرد که یک ماشین چگونه می‌تواند یک بازی شطرنج قابل قبول از خود به نمایش بگذارد. در این مقاله او عدد ۱۰۱۲۰  را به عنوان تخمینی برای تعداد بازی‌های شطرنج ارائه کرد که اگر این عدد را با تعداد اتم‌های جهان قابل مشاهده که تقریباً برابر با ۱۰۸۰ است مقایسه کنیم در واقع در مقابل هر اتم در هستی میلیارد‌ها بازی شطرنج وجود دارد.


چگونه شانون به این عدد رسید؟ در واقع او با مشاهده بازی های شطرنج در نظر گرفت که در هر موقعیت به طور متوسط ۳۰ حرکت قانونی می توان انجام داد به این ترتیب برای حرکت اول ۹۰۰ حالت به تنهایی ایجاد می شود.


(در شطرنج منظور از حرکت، حرکت سیاه و سفید با هم می باشد در واقع هر حرکت شامل دو نیم حرکت (ply) است) با فرض اینکه متوسط تعداد

حرکات یک بازی شطرنج برابر ۴۰ است تعداد بازی ها برابر با ۳۰۸۰ است که این مقدار تقریباً برابر با ۱۰۱۲۰ می‌شود.


قطعاً این عدد دقیق نیست و فقط یک تقریب برای بازی‌های زیر ۴۰ حرکت است. شانون برای اینکه توضیح دهد اگر یک کامپیوتر بخواهد با اطمینان کامل بازی کند و فرض شود بتواند هر بازی را در زمان یک میکرو ثانیه محاسبه کند، برای اینکه حرکت اولش را انجام دهد به ۱۰۹۰ سال زمان نیاز دارد. تعداد بازی‌های شطرنج از اتم‌های جهان قابل مشاهده بیشتر است.


اگر بخواهیم محاسبات را دقیق تر انجام دهیم، مهره‌های سفید برای نوبت اول ۲۰ حرکت ممکن دارند ( ۱۶ حرکت پیاده و ۴ حرکت اسب)؛ به همین ترتیب مهره‌های سیاه نیز برای نوبت دوم ۲۰ حرکت دارند. بنابراین تنها برای حرکت اول ۴۰۰ حالت مختلف وجود دارد. در نوبت سوم مساله کمی پیچید‌ه‌تر شده و تعداد حالت‌ها به ۸۹۰۲ می‌رسد. در نوبت چهارم این مقدار برابر با ۱۹۷۷۴۲۱ است. به عبارتی تنها با دو حرکت، حدود دویست هزار حالت مختلف ایجاد می‌شود و این روند افزایشی ادامه خواهد داشت.


به منظور رسیدن به پاسخ سوال اصلی، ابتدا باید به این پرسش پاسخ دهیم که «آیا تعداد حرکت های یک بازی شطرنج بی نهایت است؟»


 

خانه ها

از

به

1

1

1

2

2

3

3

4

7

4

8

15

5

16

31

6

32

63

7

64

127

8

128

255

9

256

511

10

512

1,023

11

1,024

2,047

12

2,048

4,095

13

4,096

8,191

14

8,192

16,383

15

16,384

32,767

16

32,768

65,535

17

65,536

131,071

18

131,072

262,143

19

262,144

524,287

20

524,288

1,048,575

21

1,048,576

2,097,151

22

2,087,152

4,194,303

23

2,097,152

8,388,607

24

8,388,608

16,777,215

25

16,777,216

33,554,431

26

33,554,432

67,108,863

27

67,108,864

134,217,727

28

134,217,728

268,435,455

29

268,435,456

536,870,911

30

536,870,912

1,073,741,823

31

1,073,741,824

2,147,483,647

32

2,147,483,648

4,294,967,295

33

4,294,967,296

8,589,934,591

34

8,589,934,592

17,179,869,183

35

17,179,869,184

34,359,738,367

36

34,359,738,368

68,719,476,735

37

68,719,476,736

137,438,953,471

38

137,438,953,472

274,877,906,943

39

274,877,906,944

549,755,813,887

40

549,755,813,888

1,099,511,627,775

41

1,099,511,627,776

2,199,023,255,551

42

2,199,023,255,552

4,398,046,511,103

43

4,398,046,511,104

8,796,093,022,207

44

8,796,093,022,208

17,592,186,044,415

45

17,592,186,044,416

35,184,372,088,831

46

35,184,372,088,832

70,368,744,177,663

47

70,368,744,177,664

140,737,488,355,327

48

140,737,488,355,328

281,474,976,710,655

49

281,474,976,710,656

562,949,953,421,311

50

562,949,953,421,312

1,125,899,906,842,623

51

1,125,899,906,842,624

2,251,799,813,685,247

52

2,251,799,813,685,248

4,503,599,627,370,495

53

4,503,599,627,370,496

9,007,199,254,740,991

54

9,007,199,254,740,992

18,014,398,509,481,983

55

18,014,398,509,481,984

36,028,797,018,963,967

56

36,028,797,018,963,968

72,057,594,037,927,935

57

72,057,594,037,927,936

144,115,188,075,855,871

58

144,115,188,075,855,872

288,230,376,151,711,743

59

288,230,376,151,711,744

576,460,752,303,423,487

60

576,460,752,303,423,488

1,152,921,504,606,846,975

61

1,152,921,504,606,846,976

2,305,843,009,213,693,951

62

2,305,843,009,213,693,952

4,611,686,018,427,387,903

63

4,611,686,018,427,387,904

9,223,372,036,854,775,807

64

9,223,372,036,854,775,808

18,446,744,073,709,551,615

 


[1]. با فرمول تصاعد هندسیs=264 -1/2-1=264– 1)) و با توجه به لگاریتم، عدد فوق به دست می‌آید.

[2]. تعداد قابل شمارش در صد میلیارد سال عدد (3153600000000000000) است که از ضرب عدد 31536000 در 100000000000 بدست می‌آید.


جدول محاسبه برگرفته از سایت جوان پارسی 

 

تمامی مطالب فوق متعلق به باشگاه شطرنج ایران می باشد. کپی مطالب با حفظ منبع بلا مانع می باشد.

خانه و مدرسه تخصصی شطرنج در مشهد