توضیحات کامل :

بازرسی و ارزیابی در Hex (سحر و جادو)

 

بازرسی و ارزیابی در 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 است.