بازرسی و ارزیابی در 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 را مختل می‌کند که چرا آن نمی‌تواند توسط بازریس ارتباط مجازی کشف شود