مقاله در مورد ‌‌بازرسی و ارزیابی در 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 مثالي را نشان مي‌دهد كه گروههاي 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 خانه است. الگو هنوز معتبر و درست است اما بزرگتر است از آنچه كه نياز است باشد. زماينكه به الگوها برمي‌گرديم، آنها به طور سريع خيلي بزرگ رشد مي‌كنند اگر مراقبت خاص نباشد تا آنها را به كوچكي كه ممكن است نگه دارد.
يك الگو كه تخته كامل را مي‌پوشاند معتبر است اما همچنين مضر مي‌باشد. چون جستجو سپس يك جستجوي استاندارد آلفا-بتا مي‌شود. جنبه ديگر بازرسي الگو اين است كه اين الگو مي‌تواند تنها برنده‌ها و بازنده‌ها را ثابت كند. اين الگو مقادير اكتشافي را پيدا نمي‌كند زمانيكه هيج دليلي وجود نداشته باشد. هر دو اين مشكلات مي‌توانند با استفاده از بازرسي الگو به عنوان يك افزايش بازرسي اكتشافي استاندارد آلفا- بتا سبك شوند. اگر عميق شدن تكراري استفاده شود سريع‌ترين برنده ابتدا در نظر گرفته مي‌شود و الگوي گزارش تمايل دارد كه به كوچكترين حد ممكن در نظر گرفته شود. كه جعلي براي يك الگوريتم افزايشي آلفا- بتا در Appendix B شامل شده است.
ارزيابي:

روشهاي رسيدن به ارزيابي‌هاي اكتشافي از موقعيت‌هاي Hex براي پيدا كردن سخت مي‌باشند. مفاهيمي مانند تعادل مواد و جنبش و دگرگوني كه در خيلي ديگر از تخته‌هاي بازي مفيد هستند، در Hex بي‌معني هستند. روشهاي ارزيابي به طور معمول بر پايه اندازه‌گيري خصوصيات نمودار بازي هستند مانند جريان شبكه در Hex y و فاصله نمودار در Quecn bee . تنها روش شناخته شده كه از يك چنين مدلي استفاده نمي‌كند كاهش y است كه در بخش 4 توصيف شده است. مدل‌هاي هندسي مانند جريان شبكه و فاصله از يك ارائه هندسي Hex طوريكه در شكل 8 نشان داده ش

ده است استفاده مي‌كنند كه در آن Black سعي مي‌كند بين t,s ارتباط دهد. هر موقعيت 2 تا از چنين نمودارهايي را دارد، يكي از ديدگاه‌ها Black و ديگري ديدگاه White است. براي توصيف اين نمودارها Appendix A را ببينيد.
3-1 جريان شبكه
نمودار ارائه كاهش از يك موقعيت Hex مي‌تواند ديده شود به عنوان يك جريان شبكه جاييكه مايعات از s به t جريان مي‌يابند. هر پيوند ظرفيت واحدي دارد به جز براي پيوندهايي كه ازs به t سرچشمه مي‌گيرند كه ظرفيت معيني دارد. حداكثر ظرفيت جريان از s به t به عنوان يك ارزيابي اكتشافي از موقعيت گرفته شده است. به طور نزديك بسته به اين هدف مدل جريان الكتريكي است كه مايع نيست اما الكتريسيته است كه از ميان شبكه عبور مي‌كند. ارتباطات شبكه در اين حالت حداكثر ظرفيت را ندارند اما همه آنها مقاومت واحدي دارند. ارتباطات در s و t مقاومت صفر دارند. ارتباطات در s و t مقاومت صفر دارند. مقاومت كل بين s,t به عنوان ارزيابي اكتشافي از موقعيت استفاده شده است. شانون و مور يك ماشين بازي فيزيكي Hex ساختند كه از اين وسيله استفاده كرد. همين روش در Hexy استفاده شده است. اين مدل‌ها همچنين مي‌توانند استفاده شوند تا فراهم كنند ارزشهاي اكتشافي را براي حركت‌هاي موجود كه برپايه مقدار جريان اخير از ميان ارتباطات شبكه است. Hex y از اسراف انرژي استفاده مي‌كند از تمام ارتباطات همجوار با يك گره كه در نمودار ارائه مقادير براي تكميل كردن مربع‌هايي از تمام مسيرها در آن پيوندها، طوريكه پيوندها همگي مقاومت واحدي دارند.
مدل‌هاي جريان شبكه مربوط به مفهوم ارتباط هندسي هستند كه رجوع مي‌كند به تعداد راههاي مشخص كه دو راس را در يك نمودار مربوط مي‌كند. يك درجه بالايي از ارتباط منجر مي‌شود به يك موقعيت مطلوب طوريكه راههاي زيادي براي ارتباط وجود دارد.
3-2 فاصله هندسي
فاصله هندسي بين s و t مي‌تواند به عنوان يك تخمين اكتشافي از موقعيت استفاده شود. طوريكه در n+1 شروع مي‌شود و به 1 مي‌رسد اگر و تنها اگر بازي برنده شود. اين تخمين كمي ضعيف است طوريكه مي‌تواند ديده شود با تشخيص اينكه بازي يك حركت در مركز يك تخته خالي فاصل

ه هندسي را براي حريف كاهش نمي‌دهد. يك روش بهتر اندازه «2 فاصله» است كه در Queen bee استفاده شده است. در معيار فاصله هندسي منظم، فاصله يك راس U به گره t يك برابر بيشتر از فاصله حداقل همجواران u به t است. با اندازه‌گيري فاصله اين راه مقادير براي محاسبه تعداد «حركات آزاد» مورد نياز براي كامل كردن ارتباط چشم‌پوشي از كوشش حريفان براي بستن اين ارتباطات است. 2 فاصله به نظر مي‌رسد در عوض در دومين فاصله كوتاه همسايگان U به t
اين بينش اين است كه حريف مي‌تواند كوتاه‌ترين فاصله را ببندد. Queenbee دو فاصله را به دو مر

ز در نمودار كاهش black خلاصه مي‌كند. كوچكترين اين اعداد به عنوان فاصله كل سياده در نظر گرفته شده‌اند. و تعداد رويدادهاي اين فاصله در برد بالقوه سياه است. زمانيكه دو موقعيت فاصله يكسان بين دو مرز دارند، سپس موقعيت با بالاترين عامل بالقوه ارجح است. گويا كه راههاي بيشتري براي تشخيص اين فاصله وجود دارد. ارزيابي كامل برد توسط محاسبه تعداد يكسان براي White در نمودار سفيدرنگ تهيه شده است و سپس فرق بين اين اعداد را براي مشكي و برا

ي سفيد در نظر مي‌گيرد. حركات توسط جمع كردن اعداد سفيد و سياه در هر سلول ارزيابي شده‌اند. با تشخيص اينكه خانه‌هاي مهم آنهايي هستند كه نزديك به پايه‌ريزي براي يك ارتباط برنده‌شدن براي هر دو بازيكن هستاند. علي رغم جريان شبكه و مدل‌هاي ارتباط 2 فاصله طبيعت حريف از يك بازي 2 بازيكنه را مي‌گيرد. گرچه آن از يك مانع مهم رنج مي‌برد، مي‌تواند گاهي اوقات يك موقعيت را زمانيكه در واقع يك برنده است برچسب بزند. يك مثال در شكل 9 نشان داده شده است. 2 فاصله سياه بين مرزهاي سياه گسترده مي‌باشد. در حاليكه 2 فاصله سفيد بين مرزهاي سفيد اينطور نيست. معيار دو فاصله شامل اين مي‌شود كه سياه بازنده است. در واقع موقعيت يك برنده براي سياه حتي زمانيكه سفيد ابتدا بازي مي‌كند مي‌باشد. چنين موقعيت‌هاي انحراف از حالت طبيعي نادر هستند.اما آنها در بازرسي/جستجوهاي تخته بازي اتفاق مي‌افتند و ممكن است گاه‌گاهي نتيجه جستجو تغيير كند.

4 تبديلy
بازي y توسط Graig Schensted كشف شده است كه به طور نزديك مربوط به Hex مي‌باشد. به علاوه Hex يك حالت خاص از آن باشد. اين بازي را PSPACE كامل مي‌كند و هر روشي براي بازي Y فورا يك روشي را براي بازي Hex ارزاني مي‌دارد. چنين روش كاهش Y است كه بر پايه مشاهدات توسط Graig Schinsted و Steren Meyers مي‌باشد.
4-1 بازي y
بازيy روي يك تخته مثلثي شكل كه با موزاييك‌هاي شش گوش فرش شده است بازي مي‌شود. هدف اين است كه يك زنجيره‌اي بنا نهاده شود كه تمام سه طرف تخته را به هم مرتبط كند مانند شكل 10 شكل 11 شرح مي‌دهد