چامپ (به انگلیسی: Chomp) یک بازی ۲ نفره بر روی یک صفحه مستطیلی شکلات تشکیل شده از قطعات کوچک‌تر مربع شکل است. بازیکنان، به ترتیب، یک خانه از صفحه را انتخاب می‌کنند و تمام خانه‌های سمت راست و پایین آن خانه را می خورند. خانه بالا سمت چپ سمی است و بازیکنی که آن را بخورد، بازندهٔ بازی است.

شکلِ شکلاتیِ بازی را دیوید گیل به کار برده است اما شکل دیگر بازی که به صورت انتخاب مقسوم علیه اعداد صحیح ثابت است، نیز توسط فردریک شوا ارائه شده‌است.

بازی نمونه

ویرایش

در زیر، یک سری حرکت در یک بازی ساده با یک صفحه ۳*۵ آورده شده‌است:

ابتدای بازی بازیکن اول بازیکن دوم بازیکن اول بازیکن دوم
                         
                       
                    

بازیکن اول باید آخرین قطعه را بخورد، بنابراین بازنده بازی است.

برنده کیست؟

ویرایش

چامپ، از جمله بازی‌های منصفانه ۲ نفره با اطلاعات کامل است. می توان نشان داد که برای هر صفحه مستطیلی بزرگ تر از ۱*۱، بازیکن اول، برنده است. این موضوع را می‌توان با استدلال سرقت راهبرد نشان داد: در نظر بگیرید که بازیکن دوم، یک راهبرد برد با توجه به هر حرکت اولیه بازیکن اول دارد. سپس، در نظر بگیرید که بازیکن اول، فقط خانه پایین سمت راست را انتخاب می‌کند. با توجه به فرض ما، بازیکن دوم باید یک حرکتی بکند که قطعاً به برنده شدن او بینجامد. اما اگر اینچنین حرکتی موجود باشد، بازیکن اول می‌توانست آن حرکت را انجام دهد که منجر به پیروزی وی شود. در نتیجه، بازیکن دوم، راهبرد پیروزی نخواهد داشت.

رایانه ها، می‌توانند به سادگی حرکات منجر به برد در صفحات ۲ بعدی با اندازه معقول را محاسبه کنند.

تعمیم‌های چامپ

ویرایش

چامپ ۳ بعدی، یک تخته شکلات مکعبی که به صورت (i,j،k) مشخص می‌شود دارد. یک حرکت، تمام خانه‌هایی که شاخص بزرگ تر یا مساوی خانه انتخاب شده را دارند شامل می‌شود. با روش مشابه، می‌توان بازی چامپ را به هر چند بعدی تعمیم داد.

پیوند به بیرون

ویرایش