تعداد بردها : 35191
نقطه‌ها
اگر فقط می‌خواهید بدانید که چه حرکت‌هایی را باید انجام دهید و دلیل آن را نمی‌خواهید، به قسمت نمودار درختی در انتهای متن بروید. تمام اصطلاحاتی که در متن معرفی می‌شوند در قسمت نمایه جمع‌آوری شده‌اند و می‌توان از آن به عنوان یک مقدمه مختصر و مفید استفاده کرد.
مفاهیم پایه
اصطلاحات: اجازه دهید چند اصطلاح جدید را معرفی کنیم که از آنها برای صحبت در مورد بازی استفاده خواهیم کرد.
یک خانه یک مربع کوچک است که به وسیله 4 نقطه مجاور به عنوان راس‌های آن ساخته می‌شود. تعداد ضلع‌های رسم شده مربع، در هر لحظه از بازی، می‌تواند 0 ، 1 ، 2 ، 3 یا 4 باشد که آنها را به ترتیب، 0-خانه، 1-خانه، 2-خانه، 3-خانه و 4 - خانه می‌نامیم.
منظور از خط یک پاره‌خط است که دو نقطه مجاور را به هم وصل می‌کند.
رسم یک پاره‌خط را انجام یک حرکت نیز می‌نامیم.
اگر یک خط رسم نشده، یک 2-خانه و یک 3-خانه را از هم جداکرده باشد، آنگاه رسم این خط 3 ویژگی دارد: یک 3-خانه را کامل می‌کند که 1 امتیاز دارد، یک 2-خانه را به یک 3-خانه تبدیل می‌کند و این کار به بازیکن اجازه می‌دهد که یک حرکت جدید برای کامل کردن این 3-خانه جدید انجام دهد. ا ین نوع از « حرکت‌های زنجیرهای » بیشتر وقت‌ها اتفاق می‌افتد.
تمام 2-خانه‌های به هم پیوسته یک زنجیر می‌سازند. یک زنجیر که دو انتها داشته باشد را یک زنجیر خطی می‌نامیم، خواه در یک مسیر مستقیم قرار داشته باشد یا نداشته باشند
+ + +---+---+ + +---+
| | , یا | |
+ + +---+---+ +---+ +
|
+---+---+نمایش زنجیرهای شامل 1 ، 2 و 4 خانه.
یک زنجیر ممکن است که انتها نداشته باشد. در این صورت آن را یک زنجیر حلقه‌ای و یا حلقه می‌نامیم، خواه شبیه یک دایره باشد یا نباشد.
+---+---+---+
| |
+ +---+ +
| | |
+---+ + +
| |
+---+---+
در نوشته‌های ریاضی مربوط به این بازی، انجام یک حرکت درون یک زنجیر یا بر روی یکی از دو انتهای آن را باز کردن زنجیر می‌نامند.
اگر یک زنجیر باز شود چه اتفاقی خواهد افتاد؟
اگر یک بازیکن یکی از خط‌های رسم نشده در یک زنجیر را رسم کند، مانند حرکت A1 در
+---+---+---+
| |
+ +A1-+ +
| |
+---+---+آنگاه حداقل یک 2-خانه تبدیل به 3 -خانه می‌شود (در اینجا، خانه بالا و خانه زیر حرکت A1 ) و بازیکن دیگر می‌تواند در حرکت بعد، این خانه(یا خانه‌ها) را به یک 4 -خانه تبدیل کرده و یک یا دو امتیاز بگیرد و بطور همزمان، 2-خانه مجاور آنها را به 3-خانه تبدیل کند ( در اینجا، خانه سمت چپ B1 و سمت راست B2 ) در
+---+---+---+
| B1 |
+ +A1-+ + .
| B2 |
+---+---+هر وقت که یک خانه کامل شود، بازیکن باید یک حرکت دیگر انجام دهد که می‌تواند از آن حرکت برای کامل کردن خانه بعدی و تمام خانه‌های دیگر زنجیر استفاده کند. بعد از کامل کردن آخرین خانه، بازیکن باید یک حرکت دیگر در قسمتی از صفحه انجام دهد مگر اینکه همه خانه‌های صفحه کامل شده باشند.
بازی اولیه
قانون 1 : بدیهی‌ترین قانون این است که هر بازیکن باید از ایجاد 3-خانه خودداری کند، زیرا حریف می‌تواند با کامل کردن آن امتیاز بگیرد. این یک قانون بسیار ساده و مفید است، اما همانطور که بعدا خواهیم دید، یک قانون کامل نیست. در بعضی از مرحلههای بازی ، وقتی که بیشتر از نصف خط‌ها رسم شده باشند، ساختن 3-خانه اجتناب ناپذیر می‌شود. آن وقت چه اتفاقی خواهد افتاد؟ چون زنجیرهای شامل یک یا دو یا بیشتر از 3 خانه، رفتارهای متفاوتی دارند، هر کدام از آنها را جداگانه بررسی می‌کنیم.
اجازه دهید که ابتدا زنجیرهای شامل فقط یک خانه را بررسی کنیم.
آیا یک 3-خانه تنها، یعنی یک زنجیر شامل یک خانه، را همیشه باید کامل کرد؟
+---+
| ?
+---+
بله، بازیکن حتما باید این کار را انجام دهد. اینکه بازیکن خانه را بگیرد و بعد از آن حرکت A را انجام دهد یا خانه را نگیرد و حرکت A را انجام دهد، تاثیری بر روی حرکتی که رقیب او انجام می‌دهد ندارد و چون شما یا حریف خانه را خواهید گرفت، بنابر این، بهتر است که شما خانه را بگیرید.
در مورد زنجیرهای شامل دو خانه چه کار باید کرد و بازیکن باید چگونه بازی کند ؟
زنجیرهای شامل دو خانه به یکی از صورت‌های
+---+---+ +---+---+ +---+---+
یا | یا | |
+---+---+ +---+ + + + +یا دوران یافته و یا قرینه آنها مشاهده می‌شوند. رسم خط میانی در اینجا ما را به
+---+---+ +---+---+ +---+---+
| یا | | یا | | |
+---+---+ +---+ + + + +هدایت می‌کند و آن را بخشش سنگدل می‌نامند.
آیا در این وضعیت، بازیکن همیشه باید هر دو خانه را بگیرد ؟
بله، بازیکن باید هر دو خانه را کامل کند. به همان دلیل که همیشه باید زنجیرهای 1-خانه را بگیرد. لطفا خودتان را قانع کنید.
رسم یک خط بر روی مرز یک زنجیر که شامل دو خانه باشد، ما را به یکی از وضعیت‌های
+---+---+ +---+---+ | یا | | +---+---+ +---+ +
هدایت می‌کند که بخشش سنگدل. نامیده می‌شود.
بعد از رو به رو شدن با یک حرکت بخشش سنگدل، انجام یک حرکت بر روی مرز آن، به وضعیت
+---+---+ | | . +---+---+
منجر می‌شود که
+---+---+ +---+---+ 1) to | +---+---+ +---+---+
معامله دوگانه(DD)
+---+---+---+ +---+---+---+ 2) | to | | +---+---+---+ +---+---+---+
نامیده می‌شود.
رسم خط میانی این زنجیر، هر دو خانه را کامل می‌کند و یک حرکت دو طرفه نامیده می‌شود. هر حلقه همیشه با یک حرکت دو طرفه کامل می‌شود اما یک زنجیر خطی تنها وقتی با حرکت دو طرفه کامل می‌شود که یک حرکت DD بر روی مرز آن، برای در دست گرفتن کنترل بازی، چنانکه بعدا خواهیم گفت، انجام شده باشد. در حقیقت، در چنین وضعیتی، بازیکنی که حرکت دو طرفه را انجام می‌دهد، فریب خورده است و نام این حرکت را به همین دلیل انتخاب کرده‌اند.
آیا همیشه، بعد از یک حرکت DD ، بازیکن بعدی باید هر دو خانه را بگیرد؟
یک حرکت DD در حقیقت، قربانی کردن دو خانه است زیرا، بازیکن می‌توانست ابتدا در میانه زنجیر یک حرکت بخشش سنگدل انجام دهد و سپس بر روی مرز بازی کند و به این روش، دو خانه را تصاحب کند. چرا بازیکن تصمیم می‌گیرد که دو خانه را قربانی کند؟ برای درک این موضوع ادامه متن را بخوانید.
انجام یک حرکت مانند بخشش سنگدل قبل از یک حرکت DD ، که به حریف فرصت می‌دهد تا قربانی بدهد را یک حرکت ضعیف می‌نامند. باید و می‌توان از این حرکت ضعیف اجتناب کرد. مثال دیگری از حرکت‌های ضعیف، حرکت‌هایی هستند که یک زنجیر با 3 خانه یا بیشتر را باز می‌کنند و ممکن است که مجبور به انجام آنها باشیم.
با توجه به حرکت بخشش سنگدل، آیا در چنین وضعیت‌هایی، بازیکن باید همیشه هر دو خانه را بگیرد؟ اگر پاسخ منفی است، در چه وضعیت‌هایی بازیکن باید یک حرکت DD را انجام دهد؟ هر دو حالت را در بازی آزمایش کنید و تفاوت‌های ایجاد شده را ببینید.
اجازه دهید که این تفاوت‌ها را بررسی کنیم. اگر بازیکن یک خانه از یک زنجیر 2 خانه‌ای را بگیرد، همانطور که قبلا دیده‌ایم باید خانه دوم را هم بگیرد. اگر بازیکن هر دو خانه را بگیرد 2 امتیاز کسب کرده‌است، اما بعد از آن باید یک حرکت دیگر در صفحه انجام دهد. این کار شاید به ضرر بازیکن باشد زیرا ممکن است که مجبور شود یک زنجیر با تعداد خانه بیشتر را باز کند و به حریف خودش اجازه بدهد که امتیاز بیشتری کسب کند. اما اگر بازیکن یک حرکت دیگر انجام دهد، یعنی هیچکدام از آن مربع‌ها را تصاحب نکند، او مجبور نیست که حرکت دیگری انجام دهد. با این کار، بازیکن بعدی را مجبور می‌کند که آن دو خانه را بگیرد. بنابر این، هر دو حرکت امکانپذیر است. در مورد اینکه کدام حرکت در یک وضعیت خاص بهتر است باز هم صحبت خواهیم کرد.
اگر بازیکن مجبور باشد که یک زنجیر 2 خانه‌ای را باز کند، به این دلیل که حرکت‌های دیگر ضرر بیشتری دارند، آیا بازیکن باید یک حرکت بخشش سنگدل انجام دهد؟
اگر بازیکن یک حرکت در میانه یک زنجیر انجام دهد ( یک بخشش سنگدل ) آنگاه حریف مجبور می‌شود که هر دو خانه را بگیرد و سپس یک حرکت پر ضرر در جای دیگری انجام دهد.
+---+---+ +---+---+ +---+---+
← | ← | | | به اضافه یک حرکت جدید در جای دیگر
+---+---+ +---+---+ +---+---+
اگر بازیکن یک حرکت در کناره‌های زنجیر انجام دهد ( یک بخشش سنگدل) آنگاه به حریف اختیار می‌دهد که یا هر دو خانه را بگیرد یا یک حرکت DD در کناره دیگر زنجیر انجام دهد:
+---+---+ +---+---+ +---+---+
← | ← | |
+---+---+ +---+---+ +---+---+
چنانکه در ادامه خواهیم دید، این کار می‌تواند بسیار ارزشمند باشد. انجام حرکت‌هایی که به حریف امکانات اضافه‌ای بدهد هرگز نمی‌تواند مناسب باشد، بنابر این، با هدف انجام بهترین بازی، هرگز نباید یک حرکت بخشش سنگدل را انجام داد. در بازی‌های تمرینی، برای پی بردن به مهارت و توانایی رقیب، یا وقتی که از حریف عقب هستیم برای گمراه کردن رقیب، می‌توان حرکت‌های بخشش سنگدل را انجام داد. اما بهترین حرکت به حساب نمی‌آیند.
وقتی که یک زنجیر شامل سه یا تعداد بیشتری مربع باز شده است چه کاری باید انجام داد؟
وقتی که یک زنجیر باز شده باشد، پس شامل حداقل یک 3-خانه است. بازیکن می‌تواند آن 3-خانه و خانه‌های دیگر را کامل کند. اما سوال این است که آیا باید این کار را انجام دهد؟
آیا در یک زنجیر خطی بازشده خانه‌هایی هستند که حتما باید آنها را تصاحب کرد؟
از یک طرف، ما می‌خواهیم تا آنجا که ممکن است خانه‌ها را بگیریم. از طرف دیگر، ممکن است نخواهیم که بعد از این کار، در قسمت دیگری از بازی، امتیازی به حریف بدهیم و زنجیر بزرگتری را برای حریف باز کنیم. کاری که ما باید حتما انجام دهیم این است که همه خانه‌ها، به غیر از دو خانه که قبلا در مورد آن صحبت کرده‌ایم را تصاحب کنیم، که هیچ ضرری برای ما نداشته باشد. اکنون می‌توانیم در مورد گرفتن 2 خانه باقیمانده یا انجام حرکتDD (معامله دوگانه) فکر کنیم در مورد آن بعدا بیشتر صحبت خواهیم کرد.
زنجیرهای شامل 3 خانه یا بیشتر، زنجیر.های بلند نامیده می‌شوند که شامل زنجیرهای خطی و حلقه‌ای هستند.
چرا این زنجیرها یک اسم مخصوص دارند؟
اگر فقط زنجیرهای بلند با حداقل 3 خانه باقی مانده باشند، باز کردن یکی از آنها، به هر شکلی، به این معنی است که حداقل در یک طرف حرکت انجام شده، حداقل 2 خانه مجاور وجود دارد. بنابر این، بازیکن بعدی می‌تواند یک حرکت DD انجام دهد که در تعیین سرنوشت بازی تعیین کننده خواهد بود.
برای ساخت یک زنجیر حلقه‌ای به چند خانه نیاز است؟
کوچکترین حلقه شامل 4 خانه است:
+---+---+ | | + + + | | +---+---+
وقتی که یک زنجیر حلقه‌ای باز می‌شود، آیا بازیکن می‌تواند، با خیال راحت، تمام خانه‌ها به غیر از 2 خانه را تصاحب کند؟
بیایید امتحان کنیم. کوچکترین حلقه باز شده ممکن عبارت است از
+---+---+ | | +---+ + | | +---+---+
البته ما می‌توانیم هر چهار خانه را بگیریم و سپس یک حرکت دیگر انجام دهیم. اما اگر بخواهیم از انجام یک حرکت در جای دیگری فرار کنیم چه کاری باید انجام دهیم؟ اگر دو خانه را بگیریم به وضعیت زیر می‌رسیم
+---+---+ | | | +---+---+ | | +---+---+
اما اکنون باید یک حرکت دیگر نیز انجام دهیم. چون تمام خط‌های کناره‌ای قبلا رسم شده‌اند، بنابر این، نمی‌توانیم در اینجا توقف کنیم و باید دو خانه دیگر را هم بگیریم
+---+---+ | | | +---+---+ | | | +---+---+
و اکنون مجبور هستیم که یک حرکت دیگر انجام دهیم و این حرکت ممکن است زنجیر بزرگتری را در اختیار حریف قرار دهد.
به جای آن، چه کار دیگری می‌توانیم انجام دهیم؟
ما قصد داریم حرکتی انجام دهیم که هیچ مربعی را کامل نکند و مجبور نباشیم که حرکت جدید انجام دهیم. تنها حرکت موجود، بازی کردن در وسط حلقه بازشده است برای ایجاد وضعیت
+---+---+ | | +---+---+ . | | +---+---+
این حرکت، هیچ خانه‌ای را کامل نمی‌کند و در نتیجه حرکت بعدی را باید حریف ما انجام دهد. این حرکت را معامله دوگانه دوگانه می‌نامیم و با DDD نشان می‌دهیم.
اگر یک حلقه بیش از 4 مربع داشته باشد چه کاری باید انجام داد؟
ما می‌توانیم هر تعداد حانه را بگیریم تا وقتی که بعد از آن بتوانیم حرکتی انجام دهیم که یک مربع را کامل نکند. یعنی، می‌توانیم تمام خانه‌ها به غیر از 4 خانه را تصاحب کنیم. برای مثال، باز کردن زنجیر
+---+---+---+---+ +---+---+---+---+ | | | | | + +---+---+ + برای مثال، نتیجه می‌دهد که + +---+---+ + | | | | +---+---+---+---+ +---+---+---+---+
و گرفتن 4 = 4 − 8 خانه ممکن است وضعیتی مانند
+---+---+---+---+ | | | | | + +---+---+---+ . | | | +---+---+---+---+
را نتیجه بدهد. اکنون تصمیم خواهیم گرفت که 4 مربع باقیمانده را هم بگیریم یا اینکه با انجام حرکت
+---+---+---+---+ | | | | | + +---+---+---+ . | | | | +---+---+---+---+
آنها را به حریف واگذار کنیم. در ادامه، در این مورد بیشتر خواهیم گفت.
در صورت باز بودن یک زنجیر، یا حالت بعید و نامطلوب باز بودن چند زنجیر، چند خانه را می‌توان با خیال راحت تصاحب کرد بدو ن اینکه بخواهیم در مورد انجام حرکت DD فکر کنیم.اگر حداقل یک {}زنجیر خطی{} باز شامل دو مربع مجاور وجود داشته باشد، باید تمام خانه‌های دیگر این زنجیر و تمام خانه‌های هر زنجیر باز خطی یا حلقه‌ای دیگر را کامل کنید. در غیر این صورت، اگر فقط یک یا چند زنجیر حلقه‌ای وجود دارد، آنگاه تمام خانه‌های آنها، به غیر از 4 خانه از یک زنجیر، را کامل کنید. بعد از این کار، بازیکن می‌تواند در مورد انجام یک حرکت DD یا DDD تصمیم بگیرد.
ما یاد گرفته‌ایم که بازی را با حرکت‌های تصادفی شروع کنیم و فقط سعی کنیم که تا حد امکان، هیچ 3-خانه‌ای ایجاد نشود. یعنی، حرکت ما باعث باز شدن یک زنجیر نشود. وقتی به مرحله‌ای رسیدیم که چنین حرکت‌هایی وجود ندارند، آن مرحله را به عنوان شروع آخر بازی. در نظر می‌گیریم. بحث را با این مرحله شروع می‌کنیم زیرا ساده‌ترین قسمت تمام بازیها است.
آخر بازی
مانند همه بازی‌های دیگر، هرچه به پایان بازی نزدیکتر میشویم، پیش‌بینی اینکه وضعیت چه کسی در بازی بهتر است و با چه امتیازی برنده خواهد شد آسان‌تر می‌شود. بنابر این، بررسی خود را از مرحله آخر بازی شروع می‌کنیم. در مرحله آخر بازی، تمام حرکت‌ها شامل زنجیرهای باز یا خانه‌های کامل یا حرکت‌های DD و DDD هستند. وقتی که بازیکن مجبور است که زنجیر را باز کند، اولین ایده‌ای که به ذهن او می‌رسد ممکن است این باشد که کوچکترین زنجیر موجود را باز کند تا کمترین تعداد خانه را به حریف بدهد. اجازه دهید آن را در چند مثال امتحان کنیم.
مثال 1
فرض کنید تمام خانه‌ها به غیر از دو زنجیر با 3 و 4 خانه کامل شده‌اند:
+ +---+---+ | | | | + +---+---+ | +---+---+---+ +---+---+---+
بازیکن A که نوبت حرکت با او است، زنجیر کوتاهتر را برای بازیکن B باز می‌کند (با حرکت A1 ) تا اینکه آن 3 خانه را تصاحب کرده و 3 امتیاز بگیرد. او فکر می‌کند که اکنون بازیکن B مجبور است که زنجیر 4 خانه‌ای را باز کند و بازیکن A با کامل کردن مربع‌های زنجیر بزرگتر، 4 امتیاز خواهد گرفت و نتیجه کسب شده توسط دو بازیکن، از خانه‌های این دو زنجیر، به صورت A:B=(0+4):(3+0)=4:3 خوهد بود.
+A9-+---+---+ | | | | +A8-+---+---+ | B5 A6 A7 +---+---+---+ B2 A1 B3 B4 +---+---+---+
به هر حال، حرکت A1 حرکتی است که قبلا آن را به عنوان حرکت ضعیف معرفی کردیم، حرکتی که فرصت قربانی دادن را به حریف می‌دهد.
اما بازیکن B باهوش است و با حرکت B2 فقط یک خانه را می‌گیرد (در نمودار بعدی)، و در حرکت B3 یک حرکت DD انجام می‌دهد. اکنون بازیکن A باید 2 خانه را با حرکت A4 بگیرد و با حرکت بعد، مانند A5 ، مجبور می‌شود که زنجیر بزرگ را باز کند، و بازیکن B چهار خانه باقیمانده را می‌گیرد و نتیجه کسب شده توسط دو بازیکن، از خانه‌های این دو زنجیر، به صورت A:B = (2+0):(1+4)=2:5 خواهد بود.
+B9-+---+---+ | | | | +B8-+---+---+ | A5 B6 B7 +---+---+---+ B2 A1 A4 B3 +---+---+---+در این حالت، می‌بینیم که قربانی کردن دو خانه به نفع بازیکن B است.
مثال 2
فرض کنید تمام مربع‌ها ، به غیر از یک زنجیر با 3 خانه و یک حلقه با 4 خانه کامل شده‌اند.
+---+---+---+ | | | + + +---+ | | | +---+---+---+ +---+---+---+نوبت حرکت با بازیکن A است.
حالت 1 : بازیکن A زنجیر 3 خانه‌ای را باز می‌کند.
اگر بعد از حرکت A1 بازیکن B تمام خانه‌های زنجیر را بگیرد، بازیکن A تمام خانه‌های زنجیر حلقه‌ای را خواهد گرفت و امتیازهای کسب شده از این دو زنجیر به صورت = B:A ) 0+4):(3+0) = 4:3 خواهد بود.
+---+---+---+ | A7 | | +A6-+A8-+---+ | B5 | | +---+---+---+ B2 A1 B3 B4 +---+---+---+
اگر بعد از حرکت A1 ،بازیکن B یک حرکت DD را بازی کند، پس از آن
+---+---+---+ | B7 | | +B6-+B8-+---+ | A5 | | +---+---+---+ B2 A1 A4 B3 +---+---+---+وضعیت امتیاز این دو زنجیر به صورت 5:2) = 4+1):(0+2 = (B:A است، بنابر این، در اینجا نیز انجام یک حرکت DD برا ی بازیکن B مفید است و امتیاز بیشتری خواهد گرفت.
حالت 2 : بازیکن A زنجیرحلقه‌ای را باز می‌کند.
اگر بعد از حرکت A1 ،بازیکن B تمام خانه‌های حلقه را بگیرد، بازیکن A زنجیر کوتاهتر را می‌گیرد و امتیاز این دو زنجیر به صورت A:B = (0+3):(4+0) = 3:4 خواهد بود.
+---+---+---+ | B3 | | +B2-+B4-+---+ | A1 | | +---+---+---+ B5 A6 A7 A8 +---+---+---+
اگر بعد از حرکت A1 ، بازیکن B یک حرکت DDD را با B2 بازی کند، داریم
+---+---+---+ | B2 | | +A3-+A4-+---+ | A1 | | +---+---+---+ B6 A5 B7 B8 +---+---+---+و وضعیت امتیاز این دو زنجیر به صورت A:B = (4+0):(0+3) = 4:3 خواهد بود. در این حالت، بهتر است که بازیکن B حرکت DDD انجام ندهد تا اینکه وضعیت امتیازها به صورت A:B = 3:4 و به نفع او باشد. اگر A ابتدا در زنجیر خطی کوتاهتر بازی کند، A فقط می‌تواند امتیار A:B = 2:5 را کسب کند. در حالی که وقتی A ابتدا حلقه بزرگتر را باز می‌کند، A می‌تواند به نتیجه بهتر A:B = 3:4 برسد.
از این دو حالت چه درسی می‌گیریم؟
اگر A مجبور باشد که یک زنجیر بلند (با بیش از 2 مربع) را باز کند، بازیکن B این انتخاب را خواهد داشت که بعد ازگرفتن مربع‌های آن زنجیر، یک حرکت DD/DDD را بازی کند و بنابر این، زنجیر بعدی را نیز تصاحب کند و دوباره یک حرکت DD/DDD را در آن زنجیر بازی کند و تا پایان بازی ادامه دهد. ما آن را « تحت کنترل بودن » می‌نامیم زیرا اگر بازیکن B نخواهد، بازیکن A هرگز گزینه‌ای برای بازی DD/DDD نخواهد داشت . کاری که بازیکن A می‌تواند انجام دهد این است که ارزش حرکت DD/DDD را بالا ببرد. اگر A یک زنجیر خطی را باز کند، هزینه B برای گرفتن DD قربانی 2 مربع است. اگر A یک زنجیر حقه‌ای را باز کند، هزینه B برای حرکت DDD برابر 4 مربع است. این نشان می‌دهد که هنگام مرتب‌سازی زنجیرها بر اساس ارزش آنها، باید ارزش آنها با کم کردن 2 مربع برای زنجیرهای خطی و کم کردن 4 مربع برای زنجیرهای حلقه‌ای اصلاح شود.
مثال 3
در این مثال، می‌خواهیم در مورد ترتیب باز شدن زنجیرها مطالب بیشتری یاد بگیریم. فرض کنید تمام خانه‌ها، به غیر از دو زنجیر خطی با 3 و 4 خانه و یک زنجیر حلقه‌ای با 4 خانه، کامل شده باشند مانند این وضعیت:
+---+---+ +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
|
+---+---+ +---+بازیکن A اولین حرکت را انجام می‌دهد. واضح است که اگر زنجیر خطی با 3 خانه وجود داشته باشد، بازیکن A زنجیر خطی بزرگتر با 4 خانه را باز نمی‌کند.
حالت 1 : بازیکن A زنجیر 3 خانه‌ای را باز می‌کند.
قبل از تصمیم‌گیر ی در مورد بهترین حرکت برای بازیکن B ، اجازه دهید بررسی کنیم که کدام یک از 2 زنجیر دیگر باید ابتدا باز شود:
+---+---+ +---+ | | | + + +---+ + | | | | +---+---+---+ + | | | | +---+---+---+---+
فرض کنید دو بازیکن C و D هم باشند و C باید حرکت بعدی را انجام دهد.
حالت 1-1 : بازیکن C حلقه را باز می‌کند.
+---+---+ +---+
| | |
+ + +---+ +
| C1 | | |
+---+---+---+ +
| | | |
+---+---+---+---+ اگر بعد از بازیکن C ، بازیکن D در حر کت D2 یک حرکت DDD انجام دهد آنگاه بعد از دنباله حرکت‌های
+---+---+C5-+---+ | D2 | D6 | +C3-+C4-+---+D7-+ | C1 | | | +---+---+---+D8-+ | | | | D9 +---+---+---+---+
نتیجه حاصل از این دو زنجیر به صورت 4:4) = 4+0):(0+4 = (D:C خواهد بود. اگر بازیکن D حرکت DDD انجام ندهد اما حلقه را تصاحب کند، آنگاه بعد از دنباله حرکت‌های
+---+---+D5-+---+ | D3 | C6 | +D2-+D4-+---+C7-+ | C1 | | | +---+---+---+C8-+ | | | | C9 +---+---+---+---+
نتیجه حاصل از این دو زنجیر به صورت 4:4) = 0+4) : (4+0 =(D:C خواهد بود.
حالت 1-2 : بازیکن C زنجیر 4 خانه‌ای را باز می‌کند.
+---+---+C1-+---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
| | | |
+---+---+---+---+ اگر بعد از حرکت C1 ، بازیکن D تمام زنجیر را تصاحب کند آنگاه بعد از دنباله حرکت‌های
+---+---+C1-+---+ | C8 | D2 | +C7-+C9-+---+D3-+ | D6 | | | +---+---+---+D4-+ | | | | D5 +---+---+---+---+
نتیجه امتیازات عبارت است از : 4:4) = 0+4):(4+0 = (D:C اگر بعد از حرکت C1 ، بازیکن D در حرکت D4 یک حرکت DD بازی کند آنگاه بعد از دنباله حرکت‌های
+---+---+C1-+---+ | D8 | D2 | +D7-+D9-+---+D3-+ | C6 | | | +---+---+---+C5-+ | | | | D4 +---+---+---+---+نتیجه امتیازات به صورت 6:2) = 4+2):(0+2 = (D:C خواهد بود. بهترین حالت برای بازیکن D بعد از حرکت C1 اتفاق می‌افتد یعنی : 6:2 = D:C
از این دو حالت چه می‌آموزیم؟
بازیکنی که بعد از بازیکن C بازی می‌کند، بهتر است حلقه را باز کند و به نتیجه 4:4 = D:C برسد، نه اینکه با باز کردن زنجیر خطی وضعیت بدتر 6:2 = D:C را ایجاد کند. اگر زنجیرها را بر اساس اندازه آنها (منهای 2 برای حلقه‌ها) مرتب کنیم تا اینکه بتوانیم تصمیم بگیریم کدام یک را زودتر باز کنیم، آنگاه )4-2 = )2 < 4 نتیجه صحیح را نشان می‌دهد. اکنون می‌توانیم در مورد بهترین حرکت، برای بازیکن B در وضعیت زیر، تصمیم بگیریم
+---+---+- +---+
| | |
+ + +---+ +
| | | |
+---+---+---+ +
A1 |
+---+---+ +---+
آیا بازیکن B باید خانه‌های زنجیر را بگیرد یا یک حرکت DD انجام دهد؟
اگر بازیکن B زنجیر را بگیرد آنگاه بعد از مجموعه حرکت‌های
+---+---+A9-+---+ | A7 | B10 | +A6-+A8-+---+B11+ | B5 | | | +---+---+---+B12+ B2 A1 B3 | B13 +---+---+B4-+---+
نتیجه امتیازات این سه زنجیر به صورت 7:4) = 4+0+3):(0+4+0 = (B:A خواهد بود. اما اگر بازیکن B در حرکت B3 یک حرکت DD انجام دهد آنگاه بعد از انجام حرکت‌های
+---+---+B9-+---+ | B7 | B10 | +B6-+B8-+---+B11+ | A5 | | | +---+---+---+B12+ B2 A1 A4 | B13 +---+---+B3-+---+
نتیجه امتیازات این سه زنجیر به صورت 5:6) = 0+4+1):(4+0+2 = (B:A خواهد بود. بنابر این، بهترین وضعیت امتیازی که بازیکن B بعد از A1 می‌تواند به آن برسد 7:4 = B:A است که توسط بازیکن B و با بازی نکردن یک حرکت DDD به دست می‌آید. در هر دو حالت، از اطلاعات قبلی نتیجه گرفتیم که حلقه باید باز شود.
حالت 2 : بازیکن A حلقه شامل 4 خانه را باز می‌کند:
+---+---+ +---+
| | |
+ + +---+ +
| A1 | | |
+---+---+---+ +
|
+---+---+ +---+
زیرحالت 2-1 : بازیکن B تمام حلقه را تصاحب می‌کند.
واضح است که زنجیر کوچک باید همراه با یک حرکت DD باز شود تا به وضعیت زیر برسیم
+---+---+B9-+---+ | B3 | A10 | +B2-+B4-+---+A11+ | A1 | | | +---+---+---+A12+ B5 A6 B8 | A13 +---+---+A7-+---+نتیجه حاصل از باز شدن این 3 زنجیر به صورت A:B = (0+1+4):(4+2+0) = 5:6 خواهد بود.
زیرحالت 2-2 : بازیکن B حلقه را قربانی (تقدیم به حریف) می‌کند.
باز هم باید زنجیر کوچک همراه با یک حرکت DD باز شود تا به وضعیت زیر برسیم
+---+---+A9-+---+ | B2 | B10 | +A3-+A4-+---+B11+ | A1 | | | +---+---+---+B12+ A5 B6 A8 | B13 +---+---+B7-+---+نتیجه حاصل از باز شدن این 3 زنجیر به صورت A:B = (4+2+0):(0+1+4) = 6:5 خواهد بود.
از دو زیرحالت 2-1 و 2-2 چه درسی می‌گیریم؟
به دلیل ارزش زیاد انجام یک حرکت DDD در یک حلقه، در اینجا بهترین کار برای بازیکن B این است که تمام حلقه را بگیرد و به امتیاز 6:5 = B:A برسد.
از دو حالت 1 و 2 چه می‌آموزیم؟
ما دو زنجیر خطی شامل 3 و 4 خانه و یک حلقه شامل 4 خانه داریم. بهتر است بازیکن A حلقه را باز کند و به امتیاز 6:5 = B:A برسد. اگر بازیکن A زنجیر شامل 3 خانه را باز کند، فقط به وضعیت 7:4 = B:A می‌رسد. واضح است که بازیکن B نباید زنجیر 4 خانه‌ای را قبل از زنجیر 3 خانه‌ای باز کند. بنابراین، برای تعیین اینکه کدام یک از زنجیرها را زودتر باز کنید، مرتب‌سازی آنها بر اساس اندازه به سادگی قابل استفاده نیست. اما مرتب کردن آنها بر اساس اندازه آنها (منهای 2 برای حلقه‌ها) مفیدتر به نظر می‌آید زیرا (4−4) = 0 < 1 = 3 − 2 و نشان می‌دهدکه حلقه باید ابتدا باز شود.
ترتیب باز شدن زنجیرها
با تجربه به دست آمده از مثال‌های بالا، اکنون به دنبال حل مشکل تعیین ترتیب باز شدن و تکمیل زنجیرها هستیم. در ادامه، از این ترتیب زنجیرها استفاده می‌شود تا مشخص شود که یک بازیکن چه زمانی باید یک حرکت DDD/DD بازی کند، چه کسی و با چه امتیازی برنده بازی خواهد بود. یک خبر خوب این است که در مرحله آخر بازی، ترتیب باز کردن زنجیرها به این بستگی ندارد که نوبت حرکت با چه کسی است و یا چه کسی قبلا یک حرکت DDD/DD را بازی کرده‌است. دلیل آن هم این است که در هر مرحله از بازی، فقط خود خط‌های رسم شده دارای اهمیت هستند، نه اینکه توسط چه کسی و به چه ترتیبی رسم شده‌اند. حتی امتیاز فعلی بازیکنان هم نقشی در انتخاب حرکت‌های برتر در ادامه بازی ندارد. یک راه شناخته شده برای حل یک مساله پیچیده، تبدیل آن به دو مساله ساده‌تر است. سختی کار در این مرحله، مشخص کردن بازیکنی است که آخرین حرکت را انجام خواهد داد و باید آن را به دو سوال تبدیل کنیم: یک سوال در مورد ترتیب باز کردن زنجیرها و سوال دیگر در مورد اینکه کدام بازیکن یک حرکت DDD/DD انجام خواهد داد. ابتدا لازم است که به روند کلی مرحله آخر بازی توجه کنیم.
وقتی که به انتهای بازی نزدیکتر میشویم "ارزش" زنجیرهای بازشده کاهش می‌یابد یا افزایش پیدا می‌کند؟
یک زنجیر باز، امتیازی است که به حریف داده می‌شود. بنابر این، زنجیر باید کمترین "ارزش" ممکن را داشته باشد و منظور از ارزش یک زنجیر، در یک نگاه، تعداد خانه‌های آن می‌باشد. بنابر این، "ارزش" زنجیرهایی که به ترتیب باز خواهند شد باید افزایش یابد و یا ثابت بماند، اما کاهش نمی‌یابد. در مثال بالا دیدیم که باز کردن یک زنجیر با کمترین تعداد خانه به ضرر بازیکن بود. اما ما می‌خواهیم زنجیرها را بر اساس یک "ارزش" مرتب کنیم زیرا هر بازیکنی می‌خواهد کم ارزشترین زنجیر را برای حریف باز کند. از نظر حریف، ارزش یک زنجیر فقط تعداد خانه‌های آن نیست. علاوه بر تعداد خانه‌ها، برای او مهم است که آیا زنجیر باز شده برای انجام یک حرکت DDD/DD در آن مناسب است یا خیر. یک روش خوب برای تعیین امکان انجام یک حرکت DD این است که اگر زنجیر یک حلقه باشد، از تعداد خانه‌ها 2 واحد کم شود. بنابر این، برای مرتب‌سازی زنجیرها، اگر زنجیر یک حلقه نباشد، ارزش آن را برابر تعداد خانه‌های زنجیر در نظر می‌گیریم و اگر زنجیر یک حلقه است، ارزش آن را برابر تعداد خانه‌های زنجیر منهای 2 در نظر می‌گیریم.
وضعیت‌هایی را در نظر می‌گیریم که در آنها، حداقل 2 ضلع از هر مربع رسم شده است. در این حالت، می‌توانیم دو قانون وضع کنیم که تمام زنجیرها را مرتب کنند.
قانون 2:برای مرتب کردن زنجیرها، بزرگترین زنجیر خطی را به عنوان آخرین زنجیر انتخاب کنید و اگر زنجیر خطی وجود نداشته باشد، بزرگترین حلقه را به عنوان آخرین زنجیر انتخاب کنید.
توجیه قانون 2 :
بازیکنی که کنترل بازی را در دست دارد، هیچ زنجیری را باز نمی‌کند و نیازی ندارد که زنجیرها را مرتب کند. بنابر این، هر بازیکنی که مرتب‌ساز ی زنجیرها را انجام می‌دهد، می‌خواهد کنترل بازی را در دست بگیرد و یا کنترل بازی توسط حریف (یعنی انجام حرکات DDD/DD )را تا حد امکان برا ی او پر هزینه کند. یک حرکت DD دو خانه و یک حرکت DDD چهار خانه هزینه دارد. این هزینه باید برای همه زنجیرها به جز زنجیر آخر پرداخت شود. بنابر این، برای به حداکثر رساندن هزینه کل برای حریف، در مرتب‌سازی زنجیرها، آخرین زنجیر در صورت امکان باید خطی باشد و حلقه نباشد. ∎
قانون 3 : اگر در انتهای بازی، حداقل 2 ضلع تمام خانه‌ها رسم شده باشد، آنگاه برای مرتب کردن زنجیرها، آنها را بر حسب تعداد خانه‌های آنها (منهای 2 اگر زنجیر یک حلقه است) مرتب کنید.
توجیه قانون 3 :
ابتدا باید زنجیرهای 1-مربعی باز شوند، سپس زنجیرهای 2-مربعی و به همین ترتیب زنجیرهای بلندتر باید باز شوند. با کنار گذاشتن 2 مربع از همه زنجیرهای خطی، زنجیرهای 1-مربعی دارای ارزش 1−2 = −1 و زنجیرهای 2-مربعی دارای ارزش 2−2 = 0 هستند. این مقدارها کوچکتر از ارزش زنجیرهای بلند تر است. یعنی قانون کم کردن 2 مربع در مورد زنجیرهای کوتاه هم ترتیب درستی را نتیجه می‌دهد.
اگر بازیکن بعدی بخواهد بازی را کنترل کند و یا کنترل را به دست بگیرد، ارزش یک زنجیر برابر تعداد خانه‌های آن منهای 2 (اگر یک زنجیر خطی باشد) یا برابر تعداد خانه‌های آن منهای 4 (اگر یک زنجیر حلقه‌ای باشد) است. پس برای مرتب‌سازی زنجیرها، اگر فقط برای حلقه‌ها 2 واحد از تعداد خانه‌ها کم کنیم، نتیجه یکسانی به دست می‌آید. اگر حریف کنترل بازی را در دست نداشته باشد و یا در نوبت بعدی کنترل را به دست نگیرد، چه اتفاقی خواهد افتاد؟ آیا بر اساس این ترتیب، وقتی که حریف یک حلقه باز با دو خانه بیشتر در اختیار داشته باشد، سود بیشتری نخواهد برد تا اینکه یک زنجیر خطی با همان ارزش اما خانه‌های کمتر را تصاحب کند؟ نه! اگر حریف کل حلقه را کامل کند، پس از آن که نوبت این بازیکن می‌رسد، یک حلقه کمتر شده‌است و هزینه کنترل کردن بازی به اندازه آن 2 خانه کمتر خواهد بود. ∎
تاثیر قانون 3 را در مثال 3 حالت 2-1 دیدیم که در آن، پس از اینکه بازیکن A حلقه را با حرکت A1 باز کرد، بازیکن B کل حلقه را گرفت. اما پس از آن، به دست آوردن کنترل بازی با انجام حرکت A7 برای بازیکن A مقرون به صرفه شد و بهترین نتیجه ممکن را به دست آورد.
قوانین فوق در صورتی واضح هستند که هر خانه متعلق به یک زنجیر باشد، یعنی اگر حداقل دو ضلع همه خانه‌ها رسم شده باشند. اما اگر 0-مربع و 1-مربع هم وجود داشته باشد چه اتفاقی می‌افتد؟
این خانه‌ها متعلق به کدام رنجیر هستند؟
قانون 4 :برای ایجاد یک دنباله از زنجیرهایی که بر اساس ارزش آنها مرتب شده باشند، این حرکت‌ها را تکرار کنید تا اینکه بازی تمام شود.
- یکی از زنجیرهایی را که ارزش آن (تعداد خانه‌ها ، یا اگر حلقه است، تعداد خانه‌ها منهای 2 ) کمترین مقدار موجود است را باز کنید، با یک استثنا: اگر هنوز حداقل یک حلقه وجود داشته باشد، چه پیوسته و چه ناپیوسته، یا اگر فقط یک زنجیر خطی ناپیوسته وجود داشته باشد و یا اگر هیچ درخت پیوسته‌ای شامل فقط زنجیرهای خطی وجود نداشته باشد، آخرین زنجیر خطی ناپیوسته را باز نکنید.
- زنجیر باز شده را بدون شمارش خانه‌های آن کامل کنید. رسم خط در انتهای یک زنجیر خطی ممکن است یک 1-مربع را به یک 2-مربع تبدیل کند و در نتیجه، یا دو زنجیر خطی ادغام شوند یا یک حلقه قطع شود.
اگر در مرحله پایان بازی، هنوز 0-مربع و 1-مربع وجود دارد، می‌توان چنین خانه ای را به عنوان یک نقطه در نظر گرفت و زنجیرها را به عنوان خط‌هایی در نظر گرفت که به این نقطه‌ها وصل شده‌اند یا به کناره صفحه می‌رسند و یک نقطه اضافی مصنوعی می‌سازند.
در ریاضیات، مجموعه نقطه‌ها و خط‌هایی که بعضی از آنها را به یکدیگر متصل می‌کنند، یک گراف نامیده می‌شود. در نظریه گراف، هر نقطه را یک راس و هر خط که دو راس را به هم وصل می‌کند یک یال می‌نامند.
یک استثنا در قانون 4 که در زبان «نظریه گراف» فرمول‌بندی شده‌است، می‌گوید: اگر یک زنجیر خطی متناظر با یالی از گراف است که با حذف آن یک گراف ناهمبند ساخته می‌شود بطوریکه شامل یک مولفه همبندی باشد که دارای یک حلقه است و هیچ مولفه همبندی فاقد حلقه (در نظریه گراف یک مولفه همبندی فاقد حلقه را یک درخت می‌نامند.) نداشته باشد، نباید آن زنجیر خطی را باز کرد.
مثال 4 : یک گراف شبیه T
1-مربع مورد نظر با حرف T مشخص شده‌است.
+---+---+---+ + | T | | + + + + + | | | | + + +---+---+ | | | + +---+---+ +
گراف متناظر با این موقعیت بازی، شبیه حرف T و شامل چهار راس است. یک راس در محل تلاقی ـــ و | و سه راس در گوشه‌ها ی T.
کوچکترین زنجیر در میان سه زنجیر متصل به 1-مربع، زنجیر سمت چپ آن است. پس از باز کردن و کامل کردن آن خواهیم داشت
+---+---+---+ + +---+---+---+ + | | | | | | | + + + + + +---+ + + + | | | | | | | | +---+ +---+---+ +---+ +---+---+ | | | | | | + +---+---+ + +---+---+---+ +
خواهیم دید که صفحه شامل دو زنجیر خطی است، یکی شامل 3 خانه (که کامل شده‌است) و دیگری شامل 9 خانه است که در آخرین نوبت کامل خواهد شد.
مثال 5 : یک گراف شبیه P
1-مربع مورد نظر با حرف P مشخص شده‌است.
+---+---+---+---+ | | + +---+---+ + | P | + +---+---+---+ | | +---+---+---+ +
با رسم یک خط در بالا یا سمت راست این 1-مربع، یک زنجیر خطی بزرگ با 12 خانه ایجاد و باز می‌شود
+---+---+---+---+ | | +---+---+---+ + | | + +---+---+---+ | | +---+---+---+ +
که بازیکن نباید تمام آنها را در اختیار حریف قرار دهد. اما رسم یک خط در زیر 1-مربع، صفحه را به دو قسمت مجزا تقسیم می‌کند که یکی از آنها یک زنجیر خطی باز شامل 4 خانه و دیگری یک زنجیر حلقه‌ای شامل 8 خانه است.
+--+--+--+--+ | | + +--+--+ + | | +--+--+--+--+ | | +--+--+--+ +
در قانون 4 بالا، یک استثنا هم بیان شده بود. این مثال، همان حالت استثنا را نشان می‌دهد.
مثال 6 : یک گراف شبیه P همراه با یک زنجیر خطی ناپیوسته
دو زنجیر خطی را می‌توان باز کرد، یک زنجیر در سمت راست و یک زنجیر در پایین.
+---+---+---+---+ + | P | | + + +---+ + + | | | | + +---+---+---+ + | | | +---+---+---+ + +
حالت 1 : باز کردن کوتاهترین زنجیر
21 حرکت انجام شده‌است. اگر بازیکن A بازی را شروع کرده‌است، حرکت بعدی را باید بازیکن B انجام دهد.
اگر بعد از باز کردن کوتاهترین زنجیر به وسیله حرکت B1 ، بازیکن A بلافاصله کنترل بازی را در دست بگیرد، خواهیم داشت
+---+---+---+---+B1-+ | B5 B12 | | +A6-+ +---+ +A2-+ | | | | +A7-+---+---+---+B4-+ | A8 A9 B11 | | +---+---+---+A10+A3-+
و به وضعیت امتیازی A:B = (1+4+6):(2+2+0) = 11:4 می‌رسیم که در آن (2+2+0) به این معنی است که بازیکن B از 3 زنجیر بازشده به ترتیب 2 ، 2 و 0 خانه را تصاحب کرده‌است. چون بازیکن B فقط می‌تواند دومین زنجیر خطی را با حرکت B5 باز کند، بازیکن A می‌تواند با حرکت A10 و دادن فقط 2 خانه به حریف، کنترل بازی را در دست داشته باشد و امتیاز زنجیر حلقه‌ای را بطور کامل بگیرد.
حالت 2 : باز کردن بلندترین زنجیر خطی
بعد از اینکه بازیکن B زنجیر خطی بلندتر را با حرکت B1 (در شکل زیر) باز کند و این زنجیر کامل شود، هرکسی که آخرین خانه (یا خانه‌ها) را به دست آورد باید یک زنجیر را باز کند. طبق قانون 2 ، بازیکن B حلقه بعدی را با حرکت B8 باز می‌کند تا گرفتن یا نگهداشتن کنترل بازی را برای بازیکن A پر هزینه کند. این نقشه به این دلیل مفید است که گرفتن یا حفظ کنترل در حلقه برای بازیکن A منطقی نیست زیرا 4 خانه هزینه دارد در حالیکه در آخرین زنجیر فقط 3 خانه را خواهد گرفت.
+---+---+---+---+A14+ | B1 A13 B8 | | +A2-+A12+---+A9-+B15+ | | A11 A10 | | +A3-+---+---+---+B16+ | A4 A5 B7 | | +---+---+---+A6-+B17+
امتیازات این مرحله به صورت A:B = (4+6+0):(2+0+3) = 10:5 است.
اگر بازیکن A در اولین زنجیر حرکت DD را بازی نکند داریم:
+---+---+---+---+B14+ | B1 B13 A8 | | +A2-+B12+---+B9-+A15+ | | B11 B10 | | +A3-+---+---+---+A16+ | A4 A5 A6 | | +---+---+---+A7-+A17+
B = (6+0+3)_(0+6+0) = 9_6 که به ضرر بازیکن A است. دلیل آن این است که انجام حرکت در حلقه، بعد از اینکه (با حرکت B9 بالا) باز شد، ارزش 3=3−6 امتیاز دارد و حفظ کنترل بازی در اولین زنجیر طولانی، فقط 2 امتیاز هزینه دارد. بنابر این، کنترل بازی در زنجیر اول ارزش بیشتری دارد. برای بازیکن A وضعیت امتیاز 9:6 بهتر از 9:6 است.
با مقایسه حالت‌های 1 و 2 و دو وضعیت امتیازی 11:4 و 10:5 ، واضح است که بازیکن B ابتدا باید زنجیر بلندتر را باز کند. دلیل آن این است که اگر بازیکن B ابتدا زنجیر خطی ناپیوسته را باز کند، آنگاه حلقه آخر کامل می‌شود، به این معنی که بازیکن A مجبور نیست که در هنگام حرکت DDD در حلقه، برای حفظ کنترل بازی 4 امتیاز به حریف بپردازد. ما قانون 2 قبلی خود را نقض می‌کنیم. می‌توان به طور کلی نشان داد که اگر زنجیر قطع شده دارای m خانه، زنجیر خطی پیوسته دارای n خانه و حلقه دارای p خانه باشد آنگاه بازیکن B که زنجیر ناپیوسته را باز می‌کند، با 2 مرتبه انجام حرکت DD ، ابتدا 4 امتیاز به بازیکن B می‌دهد، در حالیکه وقتی بازیکن B زنجیر خطی پیوسته را باز می‌کند، آنگاه امتیاز کسب شده توسط بازیکن B برابر min(p + max(0,m-4),min(6,m+2)) است. کمترین امتیاز وقتی اتفاق می‌افتد که P برابر کمترین مقدار ممکن خودش یعنی 4 باشد (یک زنجیر حلقه‌ای حداقل 4 خانه دارد) و m هم برابر کمترین مقدار خودش یعنی 3 باشد (کوتاهترین زنجیر خطی بلند، اگر کوتاهترین زنجیر فقط 2 خانه داشته باشد بلافاصله باید حرکت بخشش سنگدل بازی شود و فرمول متفاوت خواهد بود.) اگر P=4 و m=3 آنگاه بازیکن B min(4 + max(0,-1),min(6,5)) = min(4+0,5) = 4 امتیاز خواهد گرفت و وقتی که P>4 یا m>4 آنگاه بازیکن B بیش از 4 امتیاز کسب خواهد کرد.
اگر چند زنجیر متفاوت با کمترین امتیاز وجود داشته باشد، چه باید کرد؟
اگر چند زنجیر مختلف، کمترین خانه را داشته باشند، روش ما استفاده از قانونی است که بازکردن یک زنجیر پیوسته را پیشنهاد می‌کند. ایده پشت این قانون این است که این احتمال وجود دارد که از طریق این زنجیر باز شده، یک حلقه ایجاد شود که بتواند گرفتن یا حفظ کردن کنترل بازی را پر هزینه‌تر کند.
در بازیها معمولا یک بازیکن با انجام حرکت DDD/DD در ابتدای مرحله آخر بازی، کنترل را به دست می‌گیرد. اما اگر چند زنجیر شامل 3 خانه و چند حلقه با کمتر از 8 خانه وجود دارد، ممکن است بهتر باشد که حرکت DDD/DD بازی نکنید و کنترل را به دست نگیرید. بنابر این، ما به یک الگوریتم کلی و نه فقط یک قانون سرانگشتی نیاز داریم.
در چه شرایطی باید یک حرکت DDD/DD انجام داد و چه وقتی نباید این کار را کرد؟
در نوشته ها و دستورالعمل‌های باز ی نقطه‌ها، اولین حرکت DDD/DD را به دست گرفتن کنترل بازی نیز می‌نامند. این بدان معنی است که بازیکن، کنترل آخرین زنجیر طولانی را در اختیار می‌گیرد. البته، چنانکه خواهیم دید، این کار ممکن است با در دست گرفتن کنترل بازی و بردن آن با انجام ندادن حرکت DDD/DD یکسان نباشد.
وقتی که یک بازیکن امکان انجام حرکت DDD/DD را داشته باشد، این بازیکن می‌تواند با دادن هزینه 2 امتیازی (DD) یا 4 امتیازی (DDD) نوبت حرکت خود را با حریف جابجا کند. اگر یک بازیکن می‌تواند حداکثر امتیازی که از بازی بهینه در زنجیرهای باقیمانده کسب خواهد کرد را محاسبه کند، می‌تواند تصمیم بگیرد که آیا جابجایی نوبت حرکت، ارزش هزینه کردن 2 امتیاز (اگر زنجیر خطی باشد) یا 4 امتیاز (اگر زنجیر حلقه‌ای باشد) را دارد یا خیر؟ هم زمان با کسب امتیازات حاصل از زنجیر فعلی، می‌توان قبل از باز کردن زنجیر نیز امتیاز را تعیین کرد. در صورتی که دنباله زنجیرهایی که باز خواهند شد را بدانیم، این محاسبه را می‌توان به ترتیب و از پایان باز ی به صورت معکوس انجام داد. چنین ترتیبی را می‌توان به کمک قانون 4 بالا تعیین کرد.
قانون 5 : با استفاده از شبه کد زیر تصمیم بگیرید که حرکت DDD/DD انجام دهید یا خیر؟
در شبه کد کامپیوتری زیر، متغیر A تعداد امتیازهایی است که در ادامه بازی توسط بازیکنی که باید اولین زنجیر را باز کند کسب می‌شود و متغیر B تعداد امتیازهایی است که بازیکن دیگر خواهد گرفت. بنابر این، تعداد خانه‌های باقیمانده برابر A+B است. ما به ترتیب عکس محاسبه می‌کنیم و برای راحتی کار، شماره گذاری زنجیرها را از آخر بازی شروع می‌کنیم. زنجیر شماره 1 آخرین زنجیر باز شده در بازی است، زنجیر قبل از آن، زنجیر شماره 2 و . . . ، زنجیر فعلی زنجیر شماره k است. تعداد خانه‌های زنجیر شماره j را با n_j نشان می‌دهیم. متغیر playDD نشان می‌دهد که آیا حرکت DDD/DD در زنجیر j اُم بازی شده‌است یا خیر.
در دستورات شبه کد زیر
- (1)-(3) مقداردهی اولیه به سه متغیر، با توجه به نتایج بازی در آخرین زنجیر انجام می‌شود.
- (9)-(2) متغیرهای A ، B و playDD به ازای زنجیر j به روز رسانی می‌شوند و متغیر j از زنجیر ماقبل آخر (2=j) شروع شده و به سمت عقب حرکت می‌کند تا به زنجیر فعلی (k=j) برسد.
- (5)-(3) اگر زنجیر j خطی باشد هزینه پرداختی 2 امتیاز است
- (9)-(7) اگر زنجیر j یک حلقه باشد هزینه پرداختی 4 امتیاز است
- (8)-(4) اگر سود دریافتی B-A بزرگتر از هزینه ( 2 یا 4 ) است آنگاه حرکت DD را بازی کنید و مقدار B را به اندازه هزینه کاهش داده و آن را به A اضافه کنید. در هر حالت، B مقدار n_j را خواهد گرفت.
(1) A = 0
(2) B = n_1
(3) playDD = نادرست
(4) برای هر زنجیر j از 2 تا k:
(5) اگر زنجیر j خطی است.:
(6) اگر B > (A + 2):
(7) playDD = درست:
(8) B = B + n_j - 2
(9) A = A + 2
(10) در غیر این صورت:
(11) playDD = نادرست:
(12) B = A + n_j
(13) A = B
(14) در غیر این صورت ← اگر زنجیر j یک حلقه است.:
(15) اگر B > (A + 4):
(16) playDD = درست
(17) B = B + n_j - 4
(18) A = A + 4
(19) در غیر این صورت
(20) playDD = نادرست
(21) B = A + n_j
(22) A = B
بعد از این محاسبات مقدار A برابر امتیاز بازیکنی است که زنجیر فعلی را باز کرده‌است. مقدار B برابر امتیاز حریف او است و مقدار playDD بیان می‌کند که اکنون باید حرکت DDD/DD انجام شود یا خیر. ∎ (پایان قانون 5)
این شبه کد ممکن است برای کسی که برنامه نویس نباشد دشوار به نظر برسد، اما اجرای آن در ذهن فرد آسان است، زیرا فقط به این معنی است که بررسی کنید که آیا مزیت کنترل بازی نسبت به هزینه آن، یعنی هزینه انجام حرکت DDD/DD ، بیشتر است یا خیر.
سوال تستی
می‌دانیم که اولین زنجیر باز شده، زنجیری است که دارای کمترین خانه بوده‌است. آیا به این معنی است که انجام حرکت DDD/DD در پایان بازی سودمندتر خواهد بود؟
به عبارت دیگر، آیا انجام حرکت DDD/DD باید در اولین فرصت انجام شود وگرنه ممکن است حریف کنترل بازی را به دست بگیرد و برنده شود؟
تقریبا در همه موارد، بله. اما در حالت 2 از مثال 6 ،دیدیم که ممکن است برخی از حلقههای کم ارزش تنها پس از تکمیل زنجیرهای خطی با ارزش بالاتر قابل دسترسی باشد. در نتیجه، اگرچه وقتی حلقه باز شد، انگیزه کافی برای حرکت DDD وجود نداشت (آخرین زنجیر فقط 3 خانه داشت در حالی که برای انجام حرکت DDD باید 4 امتیاز هزینه کرد)، اما برای انجام حرکت DD قبلی که فقط 2 امتیاز هزینه دارد انگیزه کافی وجود داشت.
سوال تستی
فرض کنیم یک بازیکن به درستی ارزیابی می‌کند که یک حرکت DDD/DD انجام دهد . او تصمیم می‌گیرد که آن حرکت را بازی کرده و آخرین زنجیر را تصاحب کند.
آیا آن بازیکن همیشه برنده خواهد شد؟
خیر. برای مثال، فرض کنید 5 زنجیر خطی داریم که هر کدام از آنها 3 خانه دارد. گرفتن آخرین زنجیر و کسب 3 امتیاز، انگیزه کافی برای بازیکن ایجاد می‌کند که 3 حرکت DD انجام دهد و در هر حرکت، 2 امتیاز به حریف بدهد و 1 امتیاز خودش بگیرد. این بدان معناست که تمام خانه‌های زنجیر اول گرفته می‌شود و پس از انجام 3 حرکت DD وضعیت امتیازی به صورت A:B=(3+2+2+2+0) : (0+1+1+1+3) = 9:6 خواهد بود و به ضرر بازیکنی است که آخرین زنجیر را گرفتهاست.
آیا قانون‌های ما برای انجام مرحله آخر بازی کامل هستند؟
خیر. هنگامی که یک با زیکن، چندین زنجیر پیوسته به وسیله 0-مربع‌ها و 1-مربع‌ها داشته باشد، ممکن است تعدادی از این زنجیرها طول برابر داشته باشند و با توجه به زنجیرهای دیگری که بعد از تکمیل اولین زنجیر قابل دسترسی هستند، ممکن است به یک ایده جدید یا جستجوی ظریفتر برای انجام بهترین حرکت، نیاز باشد.
قانون زنجیر بزرگ
قانون 6 : اولین بازیکن باید حرکتی انجام دهد که مجموع تعداد نقطه‌ها و تعداد زنجیرهای خطی را به عددی زوج تبدیل کند و بازیکن دوم باید سعی کند این مقدار عددی فرد باشد.
توجیه این قانون
در ابتدا، چند متغیر را معرفی می‌کنیم که در آنها # به معنی «تعداد» است:
nt= تعداد نوبت‌ها (تعداد مرتبه‌هایی که یک بازیکن چند حرکت متوالی انجام می‌دهد.)
nd = تعداد نقطه‌ها
r = تعداد سطرهای شامل نقطه‌ها
c = تعداد ستون‌های شامل نقطه‌ها
nl = تعداد خط‌ها
nb = تعداد خانه‌ها
nc = تعداد زنجیرهای بلند
nz = شماره نوبتی است که اولین زنجیر بلند در مرحله آخر بازی را باز می‌کند.
کار را با پیدا کردن یک رابطه که اتحاد اویلر نامیده می‌شود شروع می‌کنیم.
nb = (r−1)(c−1) = rc − r − c + 1
nd = rc
nl = تعداد خط‌های افقی + تعداد خط‌های عمودی
= r(c−1) + c(r−1)
= 2rc − r − c
و بنابر این، nl = nb + nd − 1 .
این رابطه معادل اتحاد اویلر است که در هر گراف مسطح دلخواه برقرار است، یعنی اگر تعداد nd نقطه به وسیله تعداد nl خط به هم وصل شده باشند بطوریکه صفحه را به تعداد nf ناحیه ،که در اینجا 1 + nb = nf ،تقسیم کرده باشند، اتحاد اویلر به صورت زیر بیان می‌شود: nl − nd + 2 = nf (= nb + 1)
ابتدا تعداد نوبت های کل بازی را محاسبه می‌کنیم.
nt برابر است با nl منهای تعداد خط‌هایی که با رسم آنها حداقل یک خانه کامل می‌شود منهای 1 ( به ازای خطی که آخرین خانه را کامل می کند).
(1)-(3) − تعداد حرکت‌هایی که 2 خانه را کامل می کنند) − nb − (nl = (تعداد حرکت‌هایی که 2 خانه را کامل می‌کنند) + 1 + nb − nl = = nd { nl = nb + nd – 1 فرمول از استفاده با{ ( تعداد حلقه‌ها) + ( تعداد حرکت‌های DD در زنجیرهای خطی) + ( تعداد حرکت‌های DD در حلقه ها) + آخرین مجموع، از این واقعیت نتیجه می‌شود که هنگام کامل کردن یک حلقه، آخرین حرکت همیشه دو خانه را کامل خواهد کرد و اگر یک حرکت DDD در یک حلقه انجام شود، حرکت دیگر 2 خانه را کامل می‌کند. تساوی
(تعداد حلقه ها) + (تعداد حرکت‌های DD در زنجیرهای خطی ) + nd = nt (تعداد حرکت‌های DDDدر حلقه ها ) +
یک قانون دقیق و بدون تقریب است.
محاسبه nz که شماره نوبتی است که اولین زنجیر بلند را باز می‌کند.
بعد از اینکه اولین زنجیر بلند در مرحله آخر بازی باز شد، اگر هیچ حرکت DD یا DDD انجام نشده‌است، پس تعداد نوبت‌های باقیمانده برابر است با تعداد زنجیرهای بلند که هر بازیکن یک زنجیر را کامل می کند.
بنابر این، اگر تعداد حرکت‌های DD و تعداد حرکت‌های DDD برابر صفر باشد، آنگاه
(شماره نویتی که اولین زنجیر بلند در مرحله آخر بازی را باز می‌کند.)
(تعداد زنجیرهای بلند) − (تعداد حلقه ها) + nz=nd
(تعداد زنجیرهای خطی بلند) − nd =
اگر حرکت DDD/DD هم انجام شده باشد، فرمول محاسبه nz صحیح است.
توجیه :
هیچکدام از حرکت‌های DDD/DD نمی‌توانند آنچه که قبلا اتفاق افتاده‌است را تغییر دهند، یعنی نوبت nz که منجر به باز شدن اولین زنجیر طولانی در پایان بازی می‌شود. برا ی هر حرکت DD و DDD که انجام شده‌است، تعداد نوبت‌ها در پایان بازی 1 واحد افزایش می‌یابد (لطفا بررسی کنید) بنابر این، وقتی تعداد نوبت‌های مرحله آخر بازی از تعداد کل نوبت ها کم می‌شود، (تعداد حرکت‌های DD ) و (تعداد حرکت‌های DDD ) با یکدیگر خنثی می‌شوند و nz همان مقدار d به دست می‌آید که حرکت DDD/DD انجام نشده باشد.
بنابر این، هیچ بازیکنی نمی‌خواهد آن حرکت را انجام دهد، یعنی بازیکن اول نمی‌خواهد nz عددی فرد باشد و دوست دارد که nz عددی زوج باشد. 2(×تعداد زنجیرهای خطی بلند) یک عدد زوج است، بنابر این، با اضافه کردن آن به nz ، فرد یا زوج بودن nz تغییری نمی‌کند که در نهایت قانون زیر را نتیجه می‌دهد:
قانون زنجیر بلند : بازیکن اول تلاش می‌کند که مجموع (تعداد نقطه‌ها) + (تعداد زنجیرهای خطی بلند) عددی زوج باشد در حالیکه بازیکن دوم تلاش می‌کند که این مقدار برابر عددی فرد باشد. ∎
یک برداشت اشتباه از قانون زنجیر بلند
در برخی از نوشته‌ها در مورد بازی نقطه‌ها، دو فرض غیر ضروری برای به دست آوردن قانون زنجیر طولانی بیان شده‌است.
1. فرض اگر در مرحله آخر بازی، هر دو بازیکن بهترین حرکت‌های ممکن را انجام دهند، بازیکنی که آخرین حرکت را انجام دهد، به دلیل ارزش بالای آخرین زنجیر که بزرگترین زنجیر است و به دلیل عدم نیاز به انجام حرکت جدید و باز کردن یک زنجیر دیگر برای حریف، برنده بازی خواهد بود.
به این دلیل، اولین بازیکن دوست دارد که nt (تعداد نوبت ها) عددی فرد باشد. چون در این صورت، اولین حرکت و آخرین حرکت را او انجام می‌دهد و برنده خواهد شد.
2و فرض در تمام زنجیرهای بلند به غیر از آخرین زنجیر، حرکت DDD/DD انجام می‌شود. بنابر این، (تعداد حلقه‌ها) + (تعداد حرکت‌های DDD در حلقه‌ها) زوج است و می‌توان آن را نادیده گرفت و nd = nt ( + تعداد حرکت‌های DD در زنجیرها ی خطی( تبدیل به nd = nt( + تعداد زنجیرهای خطی بلند منهای 1) خواهد شد. بنابر این، بازیکن اول می‌خواهد که nt فرد باشد تا اینکه بتواند آخرین حرکت را انجام دهد، یعنی زمانی که (تعداد نقطه‌ها) + (تعداد زنجیرهای خطی بلند) زوج باشد - قانون زنجیر بلند. ∎
اما می‌دانیم که این دو فرض برای درست بودن قانون زنجیر بلند ضروری نیستند. مثال بعد، این موضوع را نشان خواهد داد.
کدام موفقیت برای یک بازیکن توسط قانون تضمین شده‌است؟
قانون زنجیر بلند یک شرط لازم و کافی برای تصمیم گرفتن در این مورد است که در آخر بازی، کدام بازیکن باید یک زنجیر بلند را باز کند. بازیکن P می‌تواند انتخاب کند که یک حرکت DD/DDD بازی کند یا بازی نکند. 2 حالت متفاوت خواهیم داشت :
اگر اولین زنجیر بلند یک زنجیر خطی باشد آنگاه حداقل دارای 3 خانه است و انجام حرکت DD 2 امتیاز هزینه خواهد داشت.
• اگر امتیاز کسب شده توسط بازیکن <2 آنگاه بازیکن P حرکت DD را اانجام نخواهد داد و تمام خانه‌های اولین زنجیر را صتاحب می‌کند و حریف حداکثر 1 امتیاز بیشتر از بقیه زنجیرها خواهد گرفت. بنابر این بازیکن P در آخر بازی حداقل 3−1 = 2 امتیاز بیشتر از حریف خواهد گرفت.
• اگر بازیکن P 2 امتیاز کسب خواهد کرد آنگاه انجام حرکت DD یا عدم انجام آن هیچ تفاوتی نخواهد داشت و در آخر بازی ≥3 خانه را خواهد گرفت.
• اگر بازیکن P ، >2 امتیاز خواهد گرفت آنگاه باید حرکت DD را انجام دهد و در آخر بازی >3 خانه را خواهد گرفت.
اگر اولین زنجیر ، یک حلقه باشد. آنگاه در بدترین حالت ، اولین زنجیر 4 خانه دارد و 4 امتیاز دارد ، صرف نظر از انجام شدن یا انجام نشدن حرکت DDD هر کدام از بازیکن‌ها در آخر بازی امتیاز مشابهی کسب خواهند کرد. اما اگر امتیاز کسب شده >4 باشد آنگاه انجام حرکت DDD بهتر است ولی اگر امتیاز کسب شده <4 باشد نباید حرکت DDD را انجام داد. اگر اولین زنجیر بلند یک حلقه با بیش از 4 خانه باشد آنگاه بازیکن P این امتیازهای اضافه را تصاحب خواهد کرد حتی اگر 4 امتیاز باشد.
اختلاف امتیاز ممکن در شروع مرحله آخر بازی چقدر است؟
• اگر تعداد زنجیرهای شامل 1 خانه و تعداد زنجیرهای شامل 2 خانه عددهایی زوج باشند آنگاه اختلاف امتیازها برابر 0 خواهد بود. br/> • اگر تعداد زنجیرهای شامل 1 خانه عددی زوج و تعداد زنجیرهای شامل 2 خانه عددی فرد باشد آنگاه اختلاف امتیاز دو بازیکن برابر 2 خواهد بود.
• اگر تعداد زنجیرهای شامل 1 خانه عددی فرد باشد بعد از گرفته شدن تمام این زنجیرها اختلاف امتیاز دو بازیکن برابر 1 خواهد بود و سپس با گرفته شدن هر زنجیر شامل 2 خانه این اختلاف امتیاز برابر 1 باقی می‌ماند اما بین دو بازیکن رد و بدل می‌شود. بازیکنی که اولین زنجیر بلند را باز می‌کند، اگر بهترین حرکت‌ها را انجام دهد، در حرحله آخر بازی حداقل 2 امتیاز بیشتر از بازیکن دیگر کسب خواهد کرد و در نتیجه امکان برد و یا حداقل تساوی را خواهد داشت. اما اگرهیچ زنجیر بلند یا حلقه وجود نداشته باشد همان اختلاف امتیاز 0 ، 1 یا 2 نتیجه بازی را مشخص خواهد کرد. البته این وضعیت وقتی اتفاق می‌افتد که صفحه بازی کوچک یا باریک باشد که بازیکن‌ها بتوانند از ایجاد زنجیر بلند یا حلقه جلوگیری کنند.
بنابراین قانون زنجیر بلند چقدر مهم است؟
چه زمانی قانون زنجیر بلند نتیجه را تعیین نمی‌کند؟
آن وقت کدام قانون باید رعایت شود؟
مثال 7 : بررسی این قانون در یک موقعیت غیر عادی
در این صفحه تعداد 5×3 = 15 حرکت انجام شده‌است که عددی فرد است. در حرکت 16 اولین زنجیر بلند باز می‌شود و تساوی مورد نظر ما برقرار است، یعنی : 16 = (تعداد نقطه‌ها) - ( تعداد زنجیرهای بلند خطی) = 4 – 20 هر کسی که این حرکت را انجام دهد، در اینجا بازیکن B ، بازنده خواهد بود اگر بازیکن A یک حرکت DD مناسب را بازی کند.
+-B-+ + + + | | | | | + + + + + | | | | | + + + + + | | | | | + + + + +
بازیکن A بازی را شروع کرده‌است و اکنون بازیکن B باید یک زنجیر را باز کند.
اگر سه حرکت DD بازی شود، وضعیت امتیازها چگونه خواهد بود؟
اگر بازیکن A سه حرکت DD بازی کند آنگاه وضعیت امتیازها به صورت 6:6 = B:A خواهد بود.
+---+---+---+---+ | A | A | A | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+ | B | B | B | A | +---+---+---+---+
وضعیت امتیازی سه زنجیر نهایی به صورت 6:6 = B:A است، بنابر این، انجام حرکت DD در اولین زنجیر با هزینه کردن 2 امتیاز برای گرفتن 1 امتیاز حرکت مناسبی نیست.
اگر دو حرکت DD بازی شود، وضعیت امتیازها چگونه خواهد بود؟
برای بازیکن A بهتر است که تمام زنجیر اول را بگیرد و به وضعیت امتیازی 5:7 = B:A برسد.
+---+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
کدام فرض از نتیجه اشتباه از قانون زنجیر بلند نقض شده است؟
هر دو قانون نقض شده‌اند. بازیکن A برنده است اما آخرین زنجیر را نگرفته‌است. حرکت DD در هر زنجیر خطی بلند انجام نشده‌است.
آیا قانون زنجیر بلند، در این بازی بهینه همچنان برقرار است؟
(تعداد نقطه‌ها) + (تعداد زنجیرهای خطی بلند) = 20 + 4 = 24 که عددی زوج است و اولین بازیکن برنده می‌شود، همانطور که قانون پیش بینی می‌کند. پس این قانون بهتر از برهان جایگزین با فرض‌ها و تفسیرهای نادرست است.
سوال تستی
آیا بازی بهینه به انجام دادن حرکت DDD/DD یا انجام ندادن آن نیاز دارد؟
خیر! هر دو حالت میتوانند به قدر کافی خوب باشند. وقتی که فقط دو زنجیر بلند شامل 3 خانه داشته باشیم، بازیکن A لازم است که حرکت DD انجام دهد تا به وضعیت امتیازی A:B = 4:2 برسد.
+-B-+ + +---+---+ | | | | A | A | + + + +---+---+ | | | ← | B | A | + + + +---+---+ | | | | B | A | + + + +---+---+
بنابر این، انتظار از انجام حرکت DD قبل از این دو زنجیر 2 = 2 − 4 امتیاز است که با هزینه انجام آن برابر است. بنابر این، هر دو بازیکن به امتیازات مشابهی دست خواهند یافت : A:B = (0+1+3):(3+2+0) = 4:5 = (2+2+0):(1+1+3)
+---+---+---+ +---+---+---+ | B | A | A | | B | B | B | +---+---+---+ +---+---+---+ | B | B | A | = | A | A | B | +---+---+---+ +---+---+---+ | B | B | A | | A | A | B | +---+---+---+ +---+---+---+
سوال تستی
آیا در یک بازی بهینه می‌تواند این اتفاق بیفتد که دو بازیکن چندین مرتبه انجام حرکت
DDD/DD را شروع و متوقف کنند؟
بله. ما در بالا دیدیم که چگونه با اضافه کردن یک زنجیر شامل 3 خانه، وضعیت امتیازی از 2:4 به 5:4) = 3+2:(4 تغییر کرد. توقع از حرکت DD قبل از این 3 زنجیر 2 < 1 = 4−5 امتیاز خواهد بود. بنابر این، از هزینه انجام حرکت DD که 2 است کمتر می‌باشد. بنابر این، با چهار زنجیر شامل 3 خانه، در ابتدا حرکت DD بازی نمی‌شود. اگر زنجیر دیگری با 3 خانه وجود داشته باشد، وضعیت امتیازی به صورت (2+5):(1+4 = (5:7 = 5):3+4 (خواهد بود. بنابر این، انتظار از حرکت دوم در 5 زنجیر شامل 3 خانه، 2 = 5−7 امتیاز خواهد بود. پس انجام حرکت DD خوب است و در هر دو مورد، وضعیت امتیازی به صورت (2+5):(1+4 = (5:7 = 5):3+4 (در می‌آید.
+-B-+---+---+---+ | A | B | B | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+ | A | A | A | B | +---+---+---+---+
با اضافه شدن تعداد زنجیرهای شامل 3 خانه، حالت‌های بیشتری برای انجام دادن یا انجام ندادن حرکت DD وجود خواهد داشت.
آیا قانون زنجیر بلند برقرار است؟
به خواننده توصیه می‌کنیم که قانون زنجیر بلند را با مثال‌های بیشتری که شامل حلقه‌ها هستند، بررسی کند.
مثال 8 : کاربرد قانون زنجیر بلند
در این وبسایت ، دیوید ویلسون نشان داده‌است که در وضعیت زیر، تنها یک حرکت مناسب برای برنده شدن بازیکنی که نوبت حرکت با او است، وجود دارد.
+ + + +
|
+ + +---+
+---+---+---+
|
+ +---+ +
اگر هر دو بازیکن از قانون‌های مرحله آخر بازی پیروی کنند، کدام بازیکن برنده خواهد شد؟
در این وضعیت، تعداد نقطه‌ها و همچنین تعداد زنجیرهای بلند عددی زوج است. در آخرین زنجیر بلند حرکت DD انجام نمی‌شود، بنابر این، به طور معمول تعداد حرکت‌های DD که انجام می‌شود عددی فرد است و بنابر این، (تعداد امتیاز) + (تعداد حرکت‌های DD ) عددی فرد خواهد بود و در نتیجه تعداد نوبت ها هم عددی فرد است. پس اولین بازیکن، آخرین زنجیر را خواهد گرفت و پیروز می‌شود. این نتیجه مطابق با "قانون زنجیر بلند" است: «بازیکن اول باید سعی کند مقدار (تعداد نقطه‌ها) + (تعداد زنجیرهای خطی بلند) را به عددی زوج و بازیکن دوم باید سعی کند که آن را به عددی فرد تبدیل کند.»
بازیکن دوم چه کاری می‌تواند انجام دهد؟
بازیکن دوم تعداد نقاط را که نمی‌تواند تغییر دهد، پس باید با قربانی کردن 2 خانه و انجام حرکتی که با B مشخص شده‌است، تعداد حرکت‌های DD را کنترل کند و این تنها حرکت برنده‌ای است که بازیکن دوم در این وضعیت دارد:
+ + + +
|
+ + +---+
+---+---+---+
| B
+ +---+ +این حرکت، تعداد زنجیرهای بلند را از 2 به 1 کاهش می‌دهد و بنابر این، مجموع (تعداد نقطه‌ها) + (تعداد زنجیرهای خطی بلند) را به عددی فرد تبدیل می‌کند و در نتیجه به بازیکن دوم اجازه می‌دهد به جای باخت با اختلاف یک امتیاز، با یک امتیاز اختلاف برنده شود.
این بازی چگونه می‌تواند ادامه یابد؟
تمام حالت‌های زیر به وضعیت امتیازی A:B = 4:5 منجر می‌شوند و بازیکن B با اختلاف 1 امتیاز برنده خواهد شد.
+A8-+B4-+A5-+ B9 | B13 B14 +A3-+A12+---+ A11 B10 B15 B16 +---+---+---+ | B A2 A7 +A1-+---+B6-+ +A5-+A10+B6-+ B13 | B9 A11 +A12+A3-+---+ B4 B14 B15 B16 +---+---+---+ | B A2 B8 +A1-+---+A7-+ +A5-+B4-+B6-+ A10 | B13 B14 +B9-+A13+---+ A11 A3 B15 B16 +---+---+---+ | B A2 B8 +A1-+---+A7-+
انجام این حرکت، قانون 1، که می‌گوید اگر مجبور نیستید 3-خانه ایجاد نکنید، را نقض می‌کند. شکستن قانون 1 چقدر بد است؟
این شکستن قانون 1، حداقل به اندازه انجام حرکت DD عجیب است. همانطور که قبلا دیده‌ایم، انجام یک حرکت DD و پرداخت هزینه 2 امتیازی به منظور تغییر نوبت کاملا طبیعی است. بنابر این، اگر این قربانی هم همان اثر حرکت DD را داشته باشد، یک هزینه حداقلی و خوب است.
تا اینجا اصطلاحات فنی بازی و قوانین آن معرفی و توضیح داده شدند. مرحله پایان بازی با جزئیات بیشتری شرح داده شده‌است و قانون زنجیر بلند، یک راهنمایی برای قسمت اول بازی ارائه کرده‌است. اگر دوست دارید در باره قسمت اول بازی بیشتر بدانید، لطفا [2] و [3] را در بخش مراجع ببینید. نمودار درختی زیر، خلاصه مطالب این صفحه را بیان می‌کند.
نمودار درختی
برای فعال شدن لینک‌های زیر، باید با کلیک کردن، متن بالا را باز کنید
- اگر حداقل یک 3-مربع موجود باشد (یک خانه که می‌تواند کامل شود)، آنگاه تمام زنجیرهایی که به تمام 3-مربع‌ها وصل هستند را مشخص کنید.
- اگر یکی از این زنجیرها خطی است و حداقل 2 خانه مجاور دارد، تمام خانه‌های همه زنجیرهای خطی و همه زنجیرهای حلقه‌ای به غیر از این دو خانه مجاور را کامل کنید. آنگاه انجام حرکت DD را بررسی کنید و سپس یا حرکت DD را انجام دهید یا 2 خانه آخر را هم کامل کنید.
- اگر تمام زنجیرها دارای طول 1 و یا حلقه هستند، ابتدا تمام زنجیرهای طول 1 را کامل کنید و اگر حداقل یک زنجیر حلقه‌ای وجود داشت، تمام زنجیرهای حلقه‌ای به جز 4 خانه آخر یکی از زنجیرهای حلقه‌ای را کامل کنید و سپس انجام حرکت DDD را بررسی کنید و تصمیم بگیرید که باید حرکت DDD را انجام دهید یا 4 خانه آخر را هم کامل کنید.
- اگر هیچ خانه‌ای وجود ندارد که بتوانید آن را کامل کنید، آنگاه
- اگر تمام حرکت‌ها باعث ایجاد 3-مربع می‌شوند، آنگاه
- اگر کوتاهترین زنجیر شامل 2 خانه است
+---+---+ +---+---+
که دو خط کشیده نشده آنها هرجایی هست غیر از یک خانه مشابه، باید خط میانی را بکشید.+---+---+ | +---+---+ - در غیر این صورت، زنجیر بعدی برای باز کردن را مشخص کنید و هر خطی از این زنجیر را که خواستید رسم کنید.
- اگر کوتاهترین زنجیر شامل 2 خانه است
- اگر حرکتی وجود دارد که 3-مربع ایجاد نمی‌کند آنگاه
- اگر در یک بازی حداکثر یک زنجیر (خطی یا حلقه) وجود داشته باشد، مثلا وقتی که صفحه بازی کوچک یا باریک باشد، آنگاه هیچ حرکت DD/DDD انجام نمی‌شود و بازیکنی که آخرین حرکت را انجام می‌دهد برنده بازی خواهد بود و با توجه به فرمول تعداد حرکت‌ها بازیکن اول باید مجموع (تعداد نقطه‌ها) + (تعداد زنجیر ( 0 یا 1 )) را به عددی فرد تبدیل کند و بازیکن دوم آن را به عددی زوج تبدیل کند. چون تعداد نقطه‌ها مقدار ثابتی است پس بازیکن فقط باید 0 یا 1 حلقه را بگیرد. اگر این کار ممکن نیست باید بازیکنی که بازی را شروع خواهد کرد تغییر داد.
- اگر مشخص است که در مرحله پایان بازی حداقل 2 زنجیر بلند وجود خواهد داشت اما تعداد دقیق آن معلوم نیست پس به عنوان بازیکن اول سعی کنید از قانون زنجیر بلند پیروی کنید و مجموع (تعداد نقطه‌ها) + (تعداد زنجیر بلند خطی) را به عددی زوج و به عنوان بازیکن دوم، مجموع را به عددی فرد تبدیل کنید.
- اگر مشخص است که در مرحله پایان بازی، چند زنجیر خطی وجود خواهد داشت و اگر {} قانون زنجیر بلند{} شکست بازی را پیش‌بینی می‌کند، یک قربانی برای کاهش تعداد زنجیرهای بلند در نظر بگیرید،
- اگر تمام حرکت‌ها باعث ایجاد 3-مربع می‌شوند، آنگاه
مراجع
[1] بقیه مراجع را در این آدرس ببینید.Boxes and Dots: Wikipedia
[2] Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1982), "Chapter 16: Dots-and-Boxes", Winning Ways for your Mathematical Plays, Volume 2: Games in Particular, Academic Press, pp. 507–550.
[3] Berlekamp, Elwyn (2000), The Dots-and-Boxes Game: Sophisticated Child's Play, AK Peters, Ltd, ISBN 1-56881-129-2.
[4] Wilson, David, Dots-and-Boxes Analysis Results, University of Wisconsin
نمایه
برای اینکه لینک‌های زیر فعال شوند، باید متن بالا را با کلیک کردن باز کنید
- تعداد . . .
- تعداد . . .
- خانه (مربع)
- یک مربع کوچک که راس‌های آن چهار نقطه مجاور هستند
- ؟-مربع
- 0-مربع، 1-مربع، 2-مربع، 3-مربع خانه‌هایی هستند که به ترتیب 0 ، 1 ، 2 یا 3 ضلع آنها رسم شده‌است.
- زنجیر
- یک دنباله از 2-خانه‌های متوالی است. زنجیرها به دو دسته تقسیم می‌شوند: زنجیر خطی و زنجیر حلقه‌ای (حلقه),
- حرکت دو طرفه
- حرکتی است که 2 خانه مجاور را بطور همزمان کامل می‌کند. این حرکت بلافاصله بعد از انجام یک حرکت معامله دوگانه در یک زنجیر خطی و یا وقتی که یک زنجیر حلقه‌ای کامل شده‌است بازی می‌شود.
- DD
- مختصرنویسی به جای حرکت معامله دوگانه
- DDD
- مختصرنویسی به جای حرکت معامله دوگانه دوگانه
- معامله دوگانه
- انجام یک حرکت که وضعیت زیر را ایجاد می‌کند:
- معامله دوگانه دوگانه
- یک حرکت در میانه‌های یک حلقه بازشده با 4 خانه باقیمانده که یکی از وضعیت‌های زیر را ایجاد می‌کند:
+---+---+ +---+---+---+---+ | | | | | +---+---+ یا +---+---+---+---+ یا | | +---+---+ +---+---+ +---+---+---+ | | | | | +---+---+---+ یا +---+---+ + | | | | +---+---+ +---+- مرحله پایان بازی
- مرحله نهایی بازی است و زمانی شروع می‌شود که انجام هر حرکتی منجر به ایجاد یک 3-خانه می‌شود.
- اتحاد اویلر
- یک قانون کلی در گراف‌های مسطح است. گراف‌هایی که یال‌های آنها یکدیگر را قطع نمی‌کنند. بازی نقطه‌ها یک نمونه از گراف مسطح است. (تعداد یال‌ها) +2=( تعداد راس‌ها) + (تعداد وجه‌ها) که وجه خارجی گراف را هم در نظر می‌گیرند. در بازی نقطه‌ها می‌توانیم بنویسیم: (تعداد خط ها) +1= (تعداد نقطه‌ها) + (تعداد خانه‌ها)
- گراف
- یک مفهوم در ریاضی است که در آن تعدادی نقطه به وسیله تعدادی خط به یکدیگر وصل شده‌اند.
- بخشش سنگدل
- رسم خط میانی در
+---+---+ +---+---+ +---+---+ یا | یا | | +---+---+ +---+ + + + +یا نسخه‌های قرینه و دوران یافته آن ها که نتیجه شده‌اند+---+---+ +---+---+ +---+---+ | یا | | یا | | | +---+---+ +---+ + + + +یا نسخه‌های قرینه یا دوران یافته آنها- بخشش سنگدل
- رسم یک خط بر روی مرز یک زنجیر با دو خانه که نتیجه می‌دهد
+---+---+ +---+---+ | یا | | +---+---+ +---+ +
- خط
- پاره خطی است که دو نقطه مجاور را به صورت افقی یا عمودی به هم وصل می کند.
- زنجیر خطی
- یک زنجیر که دو انتها دارد و لزوما در یک سطر یا یک ستون نیستند.
- قانون زنجیر بلند
- بازیکن اول باید سعی کند که مجموع (تعداد نقطه‌ها )+(تعداد زنجیرهای بلند) عددی زوج باشد و بازیکن دوم باید تلاش کند که این مجموع عددی فرد باشد.
- زنجیر بلند
- یک زنجیر شامل 3 خانه یا بیشتر
- حرکت ضعیف
- یک حرکت که به حریف اجازه می‌دهد تا قربانی بدهد
- حلقه
- خلاصه نویسی برای زنجیر حلقه‌ای
- زنجیر حلقه‌ای
- یک زنجیر بی انتها
- حرکت
- رسم یک خط
- فرمول تعداد حرکت‌ها
- یک فرمول دقیق است که بر اساس قاعده زنجیر بلند بیان می‌شود و در بازی‌های با تعداد نقطه‌های کم می‌تواند به بازیکن کمک کند که تصمیم بگیرد ، خودش بازی را شروع کند یا شروع بازی را به حریف واگذار کند..
- باز کردن یک زنجیر
- انجام یک حرکت در یک زنجیر یا در یکی از دو انتهای زنجیر (اگر آن یک زنجیر خطی باشد) و در نتیجه یک 3-مربع ایجاد شود .
- قانون 1
- بدیهی‌ترین قانون بازی، اجتناب از ایجاد 3-مربع است که حریف امتیاز مربوط به آن را با کامل کردن خانه می‌گیرد.
- قانون 2
- برای مرتب کردن زنجیرها، بزرگترین زنجیر خطی را به عنوان آخرین زنجیر انتخاب کنید و اگر زنجیر خطی وجود ندارد، بزرگترین حلقه را انتخاب کنید.
- قانون 3
- اگر در مرحله پایان بازی، همه خانه‌ها حداقل 2 ضلع دارند، برای مرتب کردن زنجیرها، آنها را بر اساس (تعداد خانه‌ها) برای زنجیرهای خطی و یا (تعداد خانه‌ها منهای 2) برای زنجیرهای حلقه‌ای مرتب کنید.
- قانون 4
- برای ایجاد یک دنباله از زنجیرهای مرتب شده بر اساس تعداد خانه‌های آنها برای بازیکن بعدی، ابتدا کمترین مقدار را در نظر گرفته و دنباله‌ای از حرکت‌ها را انجام دهید (متن را ببینید) تا زمانی که کل صفحه کامل شود.
- قانون 5
- از شبه کد ارائه شده ) متن را ببینید ( برای تصمیم‌گیری در باره انجام دادن یا انجام ندادن حرکت DDD/DD استفاده کنید.
- قانون 6
- به قانون زنجیر بلند
اشاره می‌کند.- گرفتن کنترل
- مانند انجام یک حرکت DDD/DD که به عنوان یک عامل جانبی مهم، امکان تکرار بازی DDD/DD در زنجیرهای دیگر را فراهم می‌کند.
- نوبت
- دنباله‌ای از حرکت‌های متوالی یک بازیکن
برای به روز رسانی عضو شوید و یا ما را دنبال کنید: