بتل کد Battle Codeدارد باز می‌شود…

جلسه‌ی 16: استراتژی برد: از آخر به اول Winning Strategies: Work Backwards

در بازی‌های دونفره‌ی بدون شانس، یکی از دو نفر همیشه می‌تواند ببرد. خانه‌های «برد» و «باخت» را از آخرِ بازی به اول پیدا کن؛ با برداشتن سنگ، بازیِ «هر کس آخرین را بردارد می‌بازد» و بازیکن‌هایی با قانون‌های متفاوت.

در این جلسه یاد می‌گیری

درس

۲۱ سنگ. به نوبت ۱ تا ۴ سنگ برمی‌دارید و هر کس آخرین سنگ را بردارد می‌برد. اول خودت شروع کن، بعد بگذار کامپیوتر شروع کند. کدام تعدادها برای کسی که نوبتش است بد است؟

به هر وضعیتِ بازی بگو «باخت» اگر کسی که نوبتش است، هر کاری کند، حریفِ زرنگ می‌برد؛ و «برد» اگر یک حرکت به یک وضعیتِ باخت وجود دارد. از آخر شروع کن:
• ۰ سنگ: نوبتِ تو و چیزی نمانده؛ حریف آخرین را برداشته. باخت.
• ۱ تا ۴: همه را بردار. برد.
• ۵: هر چه برداری (۱ تا ۴)، حریف به ۰ می‌رسانَد. باخت.
• ۶ تا ۹: به ۵ برسان. برد. و ۱۰ باز باخت است.
پس حالت‌های باخت مضرب‌های ۵ هستند و استراتژی: همیشه طوری بردار که مضرب ۵ بماند.

روش جدول: وقتی الگو معلوم نیست، یک جدول بکش. مثلاً اگر فقط ۱، ۳ یا ۴ سنگ بشود برداشت: از ۰ شروع کن و هر عدد را «برد» علامت بزن اگر با یکی از حرکت‌ها به یک «باخت» می‌رسد:
۰ باخت، ۱ برد، ۲ باخت، ۳ برد، ۴ برد، ۵ برد، ۶ برد، ۷ باخت، ۸ برد، ۹ باخت، …
حالت‌های باخت: ۰، ۲، ۷، ۹، ۱۴، ۱۶، … (هر ۷ تا تکرار می‌شود).

حالا برعکس: هر کس آخرین سنگ را بردارد می‌بازد! ۱۳ سنگ، هر نوبت ۱ تا ۳. این بار باید آخرین سنگ را به حریف بدهی: حالت باخت برای کسی که نوبتش است ۱ سنگ است (مجبور است بردارد)، و بعد ۵، ۹، ۱۳، …

اشتباه رایج: «هر بار بیشترین تعداد را بردار» استراتژی نیست. استراتژی یعنی برای «هر» حرکتِ حریف یک جواب داشته باشی. و یادت باشد: اگر از حالتِ باخت شروع کنی، در برابر حریفِ کامل هیچ راهی نداری؛ فقط امیدواری حریف اشتباه کند.

چالش‌ها

  1. Twenty-One Stones (آسان)
  2. The First Move (آسان)
  3. One, Three or Four (متوسط)
  4. Don't Take the Last (متوسط)
  5. Different Rules (سخت)
  6. Race to Thirty (سخت)
  7. Try It in Python: The Win-Lose Table (سخت)

← جلسه‌ی 15: بدترین حالت جلسه‌ی 17: تقارن و جفت‌سازی →