بازرسی و ارزیابی در Hex (سحر و جادو)
جک ون ریجسویجک
بخش محاسبه علم دانشگاه آلبرتا ادمونتون
آلبرتا - کاندا T6G2H1
وضعیت هنر در برنامه‌های بازی Hex در حدود سال 2002 این است که کامپیوترها بتوانند به طور کامل روی موقعیت‌ها تا برد 6×6 بازی کنند و در برابری هستند با بهترین بازیکنان انسانی روی اندازه‌های برد تا حدود 9×9.
این گزارش به طور رایج وسایل مورد استفاده و پیشنهادی را برای بازرسی تخته بازی و اعمال ارزیابی کشف کننده را توصیف می‌کند.
1 مقدمه
برای یک مقدمه عالی برای بازی Hex و استراتژی آن نگاهی به کتاب Browne بیندازید.
مقالات مقدمه‌ای در مورد Hex در Scientific American by Gardner and stewart به چشم می‌خورد.
تکامل PSPACE از نسخه عمومی شده Hex توسط Even و Tarjan به اثبات رسیده است.
اثباتی برای خود Hex توسط Reisch عرضه شده بود.
وسایل الگوریتمی برای بازی Hex در این گزارش توصیف شده است که می‌تواند به صورت زیر خلاصه شود:
ارتباطات مجازی در برنامه Vadim Anshelevich Hexy (Ansoo): استفاده شده‌اند.
الگوهای تجزیه توسط Jing yang استفاده شده‌اند تا مقادیر باز 7×7 و 8×8 را اثبات کنند.
(YLPO1, YLPO2a, YLPO2b)
بازرسی الگو بر پایه روش yang است و تست شده است اما هنوز در برنامه Jack Van Rijswick استفاده نشده است.
Queen bee (Rijoo)
مدلهای شبکه در چندین فرم ارائه شده‌اند.
البته به طور قابل توجه در Hexy که یک شبکه الکتریکی مانند آن است.
فاصله هندسی در Queen bee استفاده شده است.
کاهش y توسط Steven Meyers پیشنهاد شده است که بر پایه مشاهدات توسط creaigschensted میباشد.
اولین سه روش در بخش 2 توصیف شده‌اند.
در حالیکه بخش 3 جریان شبکه و روشهای 2 فاصله را توصیف می‌کند.
وسیله کاهش y در بخش 4 ارائه شده است.
AppendixA شامل بعضی پیش زمینه‌ها روی ارائه هندسی Hex است.
2 جستجو (بازرسی)
نه ارتباط مجازی و نه الگوهای تجزیه روشهای بازرسی تخته بازی نیستند.
هر دو روش از الگوهای محلی ارتباطات اثبات شده، ایجاد الگوهای جدید از الگوهای کوچکتر استفاده می‌کنند.
انواعی از استفاده از الگوهای تجزیه که از الگوهای کروی استفاده می‌کنند به عنوان یک افزایش بازرسی تخته‌بازی ایمن در الگو بازرسی استفاده شده‌اند.
1-2- ارتباط مجازی
ارتباطات مجازی الگوهای محلی هستند که یک ارتباط را گارانتی می‌کنند.
دو نوع ارتباط مجازی وجود دارد: قوی و ضعیف، یک ارتباط ضعیف توسط قانون And ایجاد شده است که یک برنده گارانتی شده است که ابتدا بازیکن برنده را تأمین می‌کند.
یک ارتباط قوی توسط قانون or ایجاد شده است که یک برنده است بدون در نظر گرفتن اینکه چه کسی اول بازی می‌کند.
هر ارتباطی یک حامل دارد که نیستی مجموعه‌ای از خانه‌ها است که مورد نیاز است تا برای ارتباط با کار خالی شود.
قانون And در شکل 1-I نمایش داده شده است.
این قانون یک ارتباط ضعیف بین q,p را پایه‌گذاری می‌کند که تأمین می‌کند که برآمدگی میانی m خالی است و ارتباطات قوی بین m,p و بین q,m وجود دارد.
ارتباط می‌تواند توسط بازی در نقطه m ایجاد شود.
قانون And نیاز به 2 حامل دارد که نپوشاند و حامل نتیجه ارتباط ضعیف اتصال این دو حامل به اضافه خانه m است.
شکل 1-II کاربرد قانون or را نشان می‌دهد.
یک ارتباط قوی بین p,q وجود دارد اگر دو یا چند ارتباط ضعیف بین p,q باشد که تأمین می‌کند که حاملین این ارتباطات یک فاصله خالی دارند که مطمئن می‌کند که حریف نمی‌تواند تمام ارتباطات ضعیف را یکباره مسدود کند.
سپس ارتباط می‌تواند توسط قوی کردن یکی از ارتباطات ضعیف غیر متأثر ایمن شود.
حامل نتیجه ارتباط قوی اتصال حاملین ارتباطات ضعیف است.
یک زیان ارتباطات مجازی این است که آنها ناقص هستند.
با این حس که مثالهایی از موقعیت‌هایی وجود دارد که نمی‌توانند با قوانین And-or ثابت شوند.
شکل 2 مثالی می‌دهد که بر پایه داده شده در [Ansoo] است.
موقعیت یک ارتباط مجازی ضعیف است بین q,p جاییکه m یک حرکت برنده است.
روش ارتباط مجازی هدفی است برای اثبات ارتباط.
با پیدا کردن ارتباطات مجازی بین m,p و بین q,m که در این حالت به نتیجه نمی‌رسد.
چون هیچ ارتباط قوی مجازی بین m,p وجود ندارد.
همین داستان برای تنها حرکت برنده دیگر (به طور قرینه مساوی n) به کار می‌رود.
دلیلی که روش ارتباط مجازی نمی‌تواند این موقعیت را ثابت کند این است که قانون And شامل تعهد بی‌شرطی است که ارتباط برنده شدن می‌خواهد از نقطه میانی m استفاده کند.
در این حالت بازی با حریفی که مجبور شده است r را اشغال کند پیش می‌رود.
جواب برنده تک n است.
اگر حریف سپس s را بازی کند، ارتباط می‌تواند پایه ریزی شود اما شامل گره m نمی‌شود.
این شرط اصلی پنهانی قانون And را مختل می‌کند که چرا آن نمی‌تواند توسط بازریس ارتباط مجازی کشف شود
2.2 الگوهای تجزیه الگوهای تجزیه کاملا مشابه با ارتباطات مجازی هستند؛ آنها همچنین از الگوهای کوچکتر ساخته شده‌اند و مطمئن می‌کنند ارتباط بین 2 گروه از مهره‌ها را با یک الگویی از خانه‌ها که نیاز ایت برای این ارتباط با کار خالی باشد.
شکل 3 مثالی را نشان می‌دهد که گروههای b2,b1 یک ارتباط گارانتی شده دارند.
ارتباط از الگوی کوچکتر A استفاده می‌کند که a1 را به a2 مرتبط می‌کند.
دستور برای ارتباط بین a و b به صورت زیر است: ـ اگر حریف در یکی از (8و7و4و3و1) بازی کند سپس در 2 جواب دهد و سپس از الگوی A بین 2 و b2 استفاده کند.
اگر حریف در یکی از (6و5و2) بازی کند و سپس در 4 جواب دهد و از الگوی A استفاده کند بین b1 و 4 و الگوی A بین 4 و b2 .
یک فرق مهم بین ارتباطات مجازی و الگوهای تجزیه این است که الگوهای تجزیه می‌تواند شامل خانه‌های غیر خالی باشد.
یک مثال در شکل 4 نشان داده شده است.
خانه سیاه c1 در وسط مربوط است به گروه C2 در سمت راست که از گروه از خانه‌های دو تایی در سمت چپ استفاده می‌کند.
اگلوهای تجزیه می‌تواند هر موقعیت Hex باشد.
الگوهای تجزیه به طور مشخصی کارا هستند و Jimg yang را قادر می‌کند تا بعضی حرکت‌های باز 7×7 را ثابت کند با استفاده از تنها چندصد الگو که یک بازرسی تخته بازی به ترلیونها گره نیاز خواهد داشت.
بدبختانه هیچ الگوریتم غیرخودکار برای مسافت کتابخانه‌ای از الگوهای تجزیه تا کنون ساخته نشده است.
دلایل yang دستی ساخته شده‌اند و توسط کامپیوتر بازبینی شده‌اند.
3-2 بازرسی الگو بازرسی الگو توسط الگوهای تجزیه روح داده شده‌اند.
اما این الگو از الگوهای جهانی به جای الگوهای محلی استفاده می‌کند.
این الگو یک افزایش از بازرسی تخته‌بازی است.
شکل 5 نشان می‌دهد یک موقعیت تخته را که white برای حرکت کردن از دست داده است.
از دست رفتن آنها بستگی به سلولهای علامت‌گذاری شده «X» دارد.
تنها اگر White تمام خانه‌های بدون علامت را روی تخته اشغال می‌کرد، Black برنده می‌شد.
مجموعه‌ای از خانه‌های x الگوی گزارش است که از بافت‌دهی را ثابت می‌کند.
اگر white مثل شکل 5-II باز می‌کند، موقعیت نتیجه یک برنده است برای Black .
الگوی گزارش تعیین شده در نمودار تمام آنچه است که Black برای برنده شدن نیاز دارد و بدین جهت ثابت می‌کند که تمام خانه‌های بدون علامت در 5-II در حال از دست دادن حرکت‌هایی برای White در موقعیت قبلی بودند.
بدین ترتیب آن 15 حرکت اضافی را به یکباره تکذیب می‌کند برای بهبود بازرسی تخته بازی استاندارد که هر کدام از آن حرکت‌ها به طور مستقل باید تکذیب می‌شدند.
به طور رسیم یک مجموعه از سلولهای خالی در موقعیت Hex p یک الگوی گزارش است اگر نتیجه بازی تغییرناپذیر باشد حتی زمانیکه سمت از دست رفته تمام خانه‌های خالی را نه در اشغال کند.
یک الگوی گزارش برای یک موقعیت تک نیست چون اضافه کردن یک خانه خالی به یک الگوی گزارش همیشه الگوی گزارش معتبر دیگری را ایجاد می‌کند.
آنجا یک الگوی گزارش در هر موقعیتی وجود دارد چون الگو که شامل تمام خانه‌های خالی است همیشه اندکی معتبر است.
در موقعیت که بازی تمام شده است، الگوی گزارش یک بست خالی است.
در هر موقعیت دیگری P یک الگو است که می‌تواند محاسبه شود.
ـ اگر یک حرکت برنده m وجود داشته باشد، سپس p یک برنده است و الگوی گزارش شامل m همراه با از دست دادن الگوی گزارش از موقعیت نتیجه است.
ـ اگر هیچ حرکت برنده شدن نباشد، سپس یک مجموعه‌ای از الگوهای گزارش برنده شدن برای حریف وجود دارد یک فاصله خالی دارد و وحدت این الگوها، الگوی گزارش بازنده شدن برای p را تشکیل می‌دهد.
این دو قانون الگو مانند قوانین ارتباطات مجازی And, or هستند.
2.4 بازرسی الگوی تجزیه الگوهای گزارش منافع خودکار و کامل بودن را ترکیب می‌کنند اما کمتر کارا هستند.
چون الگوها محلی نمی‌باشند.
این مشکلی در موقعیت برنده شدن نیست.
چون تنها یک حرکت برنده شدن نیاز است تا امتحان شود.
اما این یک مشکل است در یک موقعیت بازندگی مثل در شکل I-6 الگوی بازندگی شامل 3 ارتباط محلی مستقل است.
هر گاه White در یکی از سه ارتباط محلی بازی کند، Blank به همان شکل جواب می‌دهد.
هر حرکتی توسط white خارج از الگوی گزارش نامربوط است و Blank می‌تواند در جواب از یک حرکت فرار کند.
در نتیجه تمام خانه‌ها خارج از الگوی گزراش خانه‌های مرده هستند و بازیکن برنده نیاز دارد که هرگز در هیچ کدام از آنها بازی نکند.
هر کدام از ارتباطات محلی می‌توانند به صورت مستقل ثابت شوند.
بازرسی الگو این را تشخیص نداده است.
برای هر حرکتی که White در منطقه c امتحان می‌کند، بازرسی بعدی ارتباطات را دوباره از a,b ثابت می‌کند.
در اینجا ممکن است یک راه برای ایجاد الگوی بازرسی باشد تا به طور مستقل الگوهای محلی را مطرح کند.
زمانیکه White حرکتی را در شکل 6-II امتحان می‌کند، بازرسی یک برنده را برای Black با الگوی تعیین شده برمی‌گرداند.
White اکنون توجه می‌کند که این الگو شامل 3 گروه از خانه‌ها است.
2 تا از این گروهها توسط آخرین حرکت بازی شده White به هم مربوط نمی‌شدند.
بنابراین White ممکن است اکنون موارد زیر را حدس بزند: اگر موقعیت حقیقتا یک بافت باشد و از دست دادن الگوی گزارش شامل زیر الگوهای مستقل باشد و سپس آخرین حرکت بازی شده تنها با یکی از زیر الگوها دخالت داشته باشد.
اجازه دهید گروههای مداخله‌گر آن گروههای الگو در 6-II باشند که همجوار با آخرین حرکت White می‌باشند و دیگر گروهها را دست نخورده بنامید.
اگر این حدس درست باشد سپس گروههای دست نخورده ارتباطات محلی قوی هستند و گروه مداخله شده یک ارتباط محلی ضعیف است.
این ارتباط محلی ضعیف بخشی از یک ارتباط محلی قوی است که هنوز کاملا کشف نشده است.
برای اثبات این حدس، White می‌تواند موقعیت را همانطور که در شکل 6-III نشان داده شده است تغییر دهد.
زیر الگوهای دست نخورده توسط مهره‌های سیاه جایگزین شده‌اند تا ارتباطاتشان را محکم کنند و آنها توسط مهره‌های سفید احاطه شده‌اند.
آخری ضروری است چون حدس این است که بخشهای باقیمانده از الگوی بافت در 6-I مستقل هستند از بخشی که هنوز کشف نشده است.
بدین جهت باید مجبور کرد که Black ببرد بدون استفاده از هیچ یک از خانه‌های مجاور با گروههای دست نخورده که با اضافه کردن مهره‌های سفید احاطه شده به انجام رسیده‌اند.
در موقعیتی که بدین ترتیب ایجاد شده است White تنها نیاز دارد که خانه‌های در گروه مداخله شده از 6-II را بازبینی کند.
اینها 3 خانه‌ای هستند که در 6-II تعیین شده‌اند.
اگر این بافتی را برای White در پی داشته باشد، سپس موقعیت 6-I همچنین بافتی برای White است و الگوی گزارش برای 6-I آن الگویی در 6-II است به اضافه گروههای دست نخورده 6-III .
بازرسی الگوی اکتشافی در حالیکه در تئوری خیلی قدرتمند است، الگوهای گزارش خیلی حساس به حرکت خوب هستند که در تمرین دستور داده شده است.
شکل 7 نشان می‌دهد مثالی را اگر حرکت در a اول امتحان شود، الگوریتم شامل این خواهد شد که موقعیت یک برنده است با الگوی گزارش شامل تنها یک خانه a .
اگر به عبارت دیگر حرکت ابتدا در b امتحان شود برنده ثابت شده است اما نتیجه الگوی گزارش شامل 3 خانه است.
الگو هنوز معتبر و درست است اما بزرگتر است از آنچه که نیاز است باشد.
زماینکه به الگوها برمی‌گردیم، آنها به طور سریع خیلی بزرگ رشد می‌کنند اگر مراقبت خاص نباشد تا آنها را به کوچکی که ممکن است نگه دارد.
یک الگو که تخته کامل را می‌پوشاند معتبر است اما همچنین مضر میباشد.
چون جستجو سپس یک جستجوی استاندارد آلفا-بتا میشود.
جنبه دیگر بازرسی الگو این است که این الگو می‌تواند تنها برنده‌ها و بازنده‌ها را ثابت کند.
این الگو مقادیر اکتشافی را پیدا نمی‌کند زمانیکه هیج دلیلی وجود نداشته باشد.
هر دو این مشکلات می‌توانند با استفاده از بازرسی الگو به عنوان یک افزایش بازرسی اکتشافی استاندارد آلفا- بتا سبک شوند.
اگر عمیق شدن تکراری استفاده شود سریع‌ترین برنده ابتدا در نظر گرفته