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

شکل 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 مثالی را نشان می دهد که گروههای b₂,b₁  یک ارتباط گارانتی شده دارند. ارتباط از الگوی کوچکتر A استفاده می کند که a₁ را به a₂  مرتبط می کند. دستور برای ارتباط بین a و b به صورت زیر است:

ـ اگر حریف در یکی از (8و7و4و3و1) بازی کند سپس در 2 جواب دهد و سپس از الگوی A بین 2 و b₂  استفاده کند.

اگر حریف در یکی از (6و5و2) بازی کند و سپس در 4 جواب دهد و از الگوی A استفاده کند بین b_{1 ­} و 4 و الگوی A بین 4 و b₂ . یک فرق مهم بین ارتباطات مجازی و الگوهای تجزیه این است که الگوهای تجزیه می تواند شامل خانه های غیر خالی باشد. یک مثال در شکل 4 نشان داده شده است. خانه سیاه c₁  در وسط مربوط است به گروه C₂    در سمت راست که از گروه از خانه های دو تایی در سمت چپ استفاده می کند.

اگلوهای تجزیه می تواند هر موقعیت 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 هستند.